机器学习：质量度量指标驱动的数据聚合与多维数据可视化

第8卷第4期 智能系统学报 Vol.8 No.4 2013年8月 CAAI Transactions on Intelligent Systems Aug.2013 D0I:10.3969/i.issn.1673-4785.201304039 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20130603.1601.004.html 质量度量指标驱动的数据聚合与多维数据可视化 李杨2，郝志峰23，谢光强2，袁淦钊3 (1.广东工业大学自动化学院，广东广州510006：2.广东工业大学计算机学院，广东广州510006：3.华南理工大 学计算机科学与工程学院，广东广州510006) 摘要：以多维数据可视化为研究对象，在质量度量模型下，采用数据聚合为基本手段，来提高多维数据可视化的图 像质量.在质量度量指标驱动的框架下提出了均分K-means-++数据聚合算法，在传统K-means算法的基础上，专门以 数据可视化为目的对算法进行了改进，使得算法聚合得到的数据既能够较好地保持原数据的大部分特性，又能显著 地提高可视化后的图像质量仿真实验证明，在不同的数据抽象级别DAL下，无论是图像质量指标还是质量度量指 标HDM(直方图差值度量)、NNM(最近邻距离度量)，算法都表现出了较好的仿真结果 关键词：质量度量：数据空间：数据聚合：K均值：多维数据可视化 中图分类号：TP391文献标志码：A文章编号：1673-4785(2013)04-0299-06 中文引用格式：李杨，郝志峰，谢光强等.质量度量指标驱动的数据聚合与多维数据可视化[J].智能系统学报，2013,8(4)：299304. 英文引用格式：LI Yang,HAO Zhifeng,XIE Guangqiang,etal.Quality-metrics driven multi-dimensional data aggregation and visu- alization[J].CAAI Transactions on Intelligent Systems,2013,8(4):299-304. Quality-metrics driven multi-dimensional data aggregation and visualization LI Yang'2,HAO Zhifeng23,XIE Guangqiang'2,YUAN Ganzhao (1.School of Automation,Guangdong University of Technology,Guangzhou 510006,China;2.School of Computers,Guangdong Uni- versity of Technology.Guangzhou 510006,China;3.School of Computer Science and Engineering,South China University of Technolo- gy,Guangzhou 510006,China) Abstract:For the purpose of this research paper,we examined multi-dimensional data visualization with the quality metrics model;taking data aggregation as a basic means in order to improve the multi-dimensional visualization im- age quality.Under the quality-metrics driven framework,we put forward a data aggregation algorithm called equi- partition K-means++based on conventional K-means,and thus,were able to improve the algorithm especially as it pertains to data visualization.The aggregated data obtained by equipartition K-means++may not only preserve most features of the original data,but also improve the image quality after visualization.Our simulation experiments show that at each value of data abstraction level (DAL),equipartition K-means++get good results,not only in visualiza- tion image quality but also quality metrics of histogram difference measure (HDM)and nearest neighbor measure (NNM). Keywords:quality-metrics;data space;data aggregation;K-means;multi-dimensional data visualization 随着信息化社会的全面到来，面向高维海量数高维数据的认知能力有限，在知识发现、信息决策的 据的应用变得越来越普遍，因此，如何分析和使用这 过程中，多维数据可视化技术成为一种辅助人们理 些数据是一个亟待解决的问题，鉴于人类对于海量 解与直观地掌握数据特性的有效手段.多维可视化 技术的目的是尽量反映多维信息及其各属性之间的 收稿日期：2013-04-15.网络出版日期：2013-0603. 基金项目：国家自然科学基金资助项目(61070033)：广东省自然科学 关系信息，帮助数据工程师准确快速地发现数据集 基金资助项目(9251009001000005)：广东省科技计划资助 项目(2010B050400011). 中隐藏的特征信息、关系信息、模式信息、趋势信息 通信作者：李杨.E-mail:kity_lyy@163.com

第 ８ 卷第 ４ 期 智 能 系 统 学 报 Ｖｏｌ．８ №．４ ２０１３ 年 ８ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｕｇ． ２０１３ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１３０４０３９ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１３０６０３．１６０１．００４．ｈｔｍｌ 质量度量指标驱动的数据聚合与多维数据可视化 李杨１，２ ，郝志峰２，３ ，谢光强１，２ ， 袁淦钊３ （１．广东工业大学 自动化学院， 广东 广州 ５１０００６； ２．广东工业大学 计算机学院， 广东 广州 ５１０００６； ３．华南理工大 学 计算机科学与工程学院，广东 广州 ５１０００６） 摘 要：以多维数据可视化为研究对象，在质量度量模型下，采用数据聚合为基本手段，来提高多维数据可视化的图 像质量．在质量度量指标驱动的框架下提出了均分 Ｋ⁃ｍｅａｎｓ＋＋数据聚合算法，在传统 Ｋ⁃ｍｅａｎｓ 算法的基础上，专门以 数据可视化为目的对算法进行了改进，使得算法聚合得到的数据既能够较好地保持原数据的大部分特性，又能显著 地提高可视化后的图像质量．仿真实验证明，在不同的数据抽象级别 ＤＡＬ 下，无论是图像质量指标还是质量度量指 标 ＨＤＭ（直方图差值度量）、ＮＮＭ（最近邻距离度量），算法都表现出了较好的仿真结果． 关键词：质量度量；数据空间；数据聚合；Ｋ⁃均值；多维数据可视化 中图分类号： ＴＰ３９１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１３）０４⁃０２９９⁃０６ 中文引用格式：李杨，郝志峰，谢光强等．质量度量指标驱动的数据聚合与多维数据可视化［Ｊ］． 智能系统学报， ２０１３， ８（４）：２９９⁃３０４． 英文引用格式：ＬＩ Ｙａｎｇ，ＨＡＯ Ｚｈｉｆｅｎｇ，ＸＩＥ Ｇｕａｎｇｑｉａｎｇ， ｅｔ ａｌ． Ｑｕａｌｉｔｙ⁃ｍｅｔｒｉｃｓ ｄｒｉｖｅｎ ｍｕｌｔｉ⁃ｄｉｍｅｎｓｉｏｎａｌ ｄａｔａ ａｇｇｒｅｇａｔｉｏｎ ａｎｄ ｖｉｓｕ⁃ ａｌｉｚａｔｉｏｎ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１３， ８（４）：２９９⁃３０４． Ｑｕａｌｉｔｙ⁃ｍｅｔｒｉｃｓ ｄｒｉｖｅｎ ｍｕｌｔｉ⁃ｄｉｍｅｎｓｉｏｎａｌ ｄａｔａ ａｇｇｒｅｇａｔｉｏｎ ａｎｄ ｖｉｓｕａｌｉｚａｔｉｏｎ ＬＩ Ｙａｎｇ １，２ ， ＨＡＯ Ｚｈｉｆｅｎｇ ２，３ ， ＸＩＥ Ｇｕａｎｇｑｉａｎｇ １，２ ， ＹＵＡＮ Ｇａｎｚｈａｏ ３ （１．Ｓｃｈｏｏｌ ｏｆ Ａｕｔｏｍａｔｉｏｎ， Ｇｕａｎｇｄｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｇｕａｎｇｚｈｏｕ ５１０００６， Ｃｈｉｎａ； ２．Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒｓ， Ｇｕａｎｇｄｏｎｇ Ｕｎｉ⁃ ｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｇｕａｎｇｚｈｏｕ ５１０００６， Ｃｈｉｎａ； ３．Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｓｏｕｔｈ Ｃｈｉｎａ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏ⁃ ｇｙ， Ｇｕａｎｇｚｈｏｕ ５１０００６， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｆｏｒ ｔｈｅ ｐｕｒｐｏｓｅ ｏｆ ｔｈｉｓ ｒｅｓｅａｒｃｈ ｐａｐｅｒ， ｗｅ ｅｘａｍｉｎｅｄ ｍｕｌｔｉ⁃ｄｉｍｅｎｓｉｏｎａｌ ｄａｔａ ｖｉｓｕａｌｉｚａｔｉｏｎ ｗｉｔｈ ｔｈｅ ｑｕａｌｉｔｙ ｍｅｔｒｉｃｓ ｍｏｄｅｌ； ｔａｋｉｎｇ ｄａｔａ ａｇｇｒｅｇａｔｉｏｎ ａｓ ａ ｂａｓｉｃ ｍｅａｎｓ ｉｎ ｏｒｄｅｒ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ｍｕｌｔｉ⁃ｄｉｍｅｎｓｉｏｎａｌ ｖｉｓｕａｌｉｚａｔｉｏｎ ｉｍ⁃ ａｇｅ ｑｕａｌｉｔｙ． Ｕｎｄｅｒ ｔｈｅ ｑｕａｌｉｔｙ⁃ｍｅｔｒｉｃｓ ｄｒｉｖｅｎ ｆｒａｍｅｗｏｒｋ， ｗｅ ｐｕｔ ｆｏｒｗａｒｄ ａ ｄａｔａ ａｇｇｒｅｇａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｃａｌｌｅｄ ｅｑｕｉ⁃ ｐａｒｔｉｔｉｏｎ Ｋ⁃ｍｅａｎｓ＋＋ ｂａｓｅｄ ｏｎ ｃｏｎｖｅｎｔｉｏｎａｌ Ｋ⁃ｍｅａｎｓ， ａｎｄ ｔｈｕｓ， ｗｅｒｅ ａｂｌｅ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｅｓｐｅｃｉａｌｌｙ ａｓ ｉｔ ｐｅｒｔａｉｎｓ ｔｏ ｄａｔａ ｖｉｓｕａｌｉｚａｔｉｏｎ． Ｔｈｅ ａｇｇｒｅｇａｔｅｄ ｄａｔａ ｏｂｔａｉｎｅｄ ｂｙ ｅｑｕｉｐａｒｔｉｔｉｏｎ Ｋ⁃ｍｅａｎｓ＋＋ ｍａｙ ｎｏｔ ｏｎｌｙ ｐｒｅｓｅｒｖｅ ｍｏｓｔ ｆｅａｔｕｒｅｓ ｏｆ ｔｈｅ ｏｒｉｇｉｎａｌ ｄａｔａ， ｂｕｔ ａｌｓｏ ｉｍｐｒｏｖｅ ｔｈｅ ｉｍａｇｅ ｑｕａｌｉｔｙ ａｆｔｅｒ ｖｉｓｕａｌｉｚａｔｉｏｎ． Ｏｕｒ ｓｉｍｕｌａｔｉｏｎ ｅｘｐｅｒｉｍｅｎｔｓ ｓｈｏｗ ｔｈａｔ ａｔ ｅａｃｈ ｖａｌｕｅ ｏｆ ｄａｔａ ａｂｓｔｒａｃｔｉｏｎ ｌｅｖｅｌ （ＤＡＬ）， ｅｑｕｉｐａｒｔｉｔｉｏｎ Ｋ⁃ｍｅａｎｓ＋＋ ｇｅｔ ｇｏｏｄ ｒｅｓｕｌｔｓ， ｎｏｔ ｏｎｌｙ ｉｎ ｖｉｓｕａｌｉｚａ⁃ ｔｉｏｎ ｉｍａｇｅ ｑｕａｌｉｔｙ ｂｕｔ ａｌｓｏ ｑｕａｌｉｔｙ ｍｅｔｒｉｃｓ ｏｆ ｈｉｓｔｏｇｒａｍ ｄｉｆｆｅｒｅｎｃｅ ｍｅａｓｕｒｅ （ＨＤＭ） ａｎｄ ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ ｍｅａｓｕｒｅ （ＮＮＭ）． Ｋｅｙｗｏｒｄｓ：ｑｕａｌｉｔｙ⁃ｍｅｔｒｉｃｓ； ｄａｔａ ｓｐａｃｅ； ｄａｔａ ａｇｇｒｅｇａｔｉｏｎ； Ｋ⁃ｍｅａｎｓ； ｍｕｌｔｉ⁃ｄｉｍｅｎｓｉｏｎａｌ ｄａｔａ ｖｉｓｕａｌｉｚａｔｉｏｎ 收稿日期：２０１３⁃０４⁃１５． 网络出版日期：２０１３⁃０６⁃０３． 基金项目：国家自然科学基金资助项目（６１０７００３３）；广东省自然科学 基金资助项目（９２５１００９００１０００００５）；广东省科技计划资助 项目（２０１０Ｂ０５０４０００１１）． 通信作者：李杨． Ｅ⁃ｍａｉｌ：ｋｉｔｔｙ＿ｌｌｙｙ＠ １６３．ｃｏｍ． 随着信息化社会的全面到来，面向高维海量数 据的应用变得越来越普遍，因此，如何分析和使用这 些数据是一个亟待解决的问题，鉴于人类对于海量 高维数据的认知能力有限，在知识发现、信息决策的 过程中，多维数据可视化技术成为一种辅助人们理 解与直观地掌握数据特性的有效手段．多维可视化 技术的目的是尽量反映多维信息及其各属性之间的 关系信息，帮助数据工程师准确快速地发现数据集 中隐藏的特征信息、关系信息、模式信息、趋势信息

·300. 智能系统学报 第8卷 及聚类信息等 然而，在对海量数据进行可视化时，情况更为复 1 均分K-means++:一种多维数据可 杂，应用传统的数据可视化技术及流程时，往往会出 现图像叠加严重、可视化图像质量低、辨识性差等现 视化中的数据聚合方法 实问题，数据聚合是解决该问题的一种有效方法，也 K-means算法具有简单、聚类速度快的优点.在 就是在数据可视化之前先进行数据抽象.现有的数 大量的实验中发现，在进行海量数据的聚合运算中， 据聚合方法往往没有为数据可视化进行专门的优化 K-means算法具有以下缺，点： 和改进，更为重要的是，缺少针对可视化所作的数据 1)在聚合运算，特别是海量数据的聚合运算 聚合质量度量，对数据聚合的质量没有量化和理论 中，K值往往较大，这种情况下，传统的K-means算 支撑，本文研究的质量度量指标驱动的数据聚合弥 法会出现迭代次数过大的情况，极大地影响了聚合 补了上述不足 速度 为了弥补人类视觉感知能力的不足，帮助人们理 2)传统的K-means-+算法[]虽然改进了初始点 解多维数据，研究人员提出了相当数量的数据可视化 的选择，但仍然以最小化近邻点距离之和为目的，往 方法，这些方法将多维数据通过降维转换并映射到三 往会出现各个聚簇的点数分布极不均匀的情况，某 维或者二维可视空间来实现多维信息的可视化根据其 些聚簇只有几个点，某些聚簇则有成百上千个点.但 可视化的原理不同可以划分为基于几何的技术、面向 是，在数据聚合中，往往希望聚合前的数据能在聚合 像素的技术、基于图标的技术、基于层次的技术、基于 后的各个中心点上均匀分布，使聚合后的数据更好 图形的技术和基于降维映射的技术等2]」 地反映原数据的分布。 在数据量较大时，为了提高数据可视化的图像 鉴于现有的K-means及其改进算法在数据聚合 质量，降低图像叠加的问题，通常会对数据进行抽 中存在的缺陷，本文提出了均分K-means++的数据 象，数据抽象的目的是在数据精简的同时，保持原数 聚合方法，仿真实验证明，该算法大大减少了迭代次 据的各种特性，提高数据抽象后可视化的图像质量. 数，在分布上与原数据更加吻合，从而更加适用于数 抽样和聚合是2种常用的数据抽象方法.Bertini 据可视化中的数据聚合运算， 等)提出了利用聚类聚合的方法在散点图中自动 算法1均分K-means 降低图像叠加；Johansson等提出了基于距离变化 1)输入d维空间[0,1]的n个点P1,P2,…, 的数据抽样方法，并在屏幕空间对图像质量进行了 pn,随机选择k个初始点C={c1,c2,…,cz} 度量 质量度量的研究由来已久，随着数据可视化技 2)设a=cei(),ceil(·)为向上取整函数将每 术的发展，数据可视化中的质量度量越来越引起学 个样本点P:划分到最近的中心点c:所在的集合S,如 者们的注意，越来越多的成果发表在数据可视化领 果数目IS,|≥α，则表示该集合已满，继续寻找次近的中 域的重要期刊和会议上，这些方法也极大地促进了 心点所在的集合，直至找到一个未满（集合现有点数小 数据可视化技术本身的发展.根据数据可视化度量 于α)的较近的中心点所在的集合.用以上方法将样本 指标所实施的对象不同，现有的质量度量方法可以 集合{P:}划分成S,S2,…,S 被分成两大类：实施于数据空间和图像空间[).在数 3)对于1≤j≤k,计算集合S,内点之和sum= 据空间方面，C等[6)研究了在抽象和聚合2种不 ∑：es:和数目num=1S,l,S,=sum/num为集合S,新 同的数据抽象方法下计算数据抽象质量，权衡如何 的中心点 在数据精简和数据损失方面取得平衡：在图像空间 4)重复2)~3)，直至C不再变化或迭代次数达 方面，Tatu等)使用Hough变换对感兴趣的散点图 到上限 进行分级，以提高可视化图像质量.但是，图像空间 算法2均分K-means+ 的质量度量存在着受限于某种单个数据可视化方法 令D(x)表示一个数据点到离它最近的已经选出 的缺点 的中心点的距离.则均分K-means+算法定义如下： 本文提出一种数据空间质量度量驱动下的数据 1)输入d维空间[0,1]4的n个点P1P2,…Pn 聚合方法均分K-means+-+,这一方法面向多维数据， ①均匀随机地在X中选出第1个中心点. 广泛适用于大部分数据可视化方法，在质量度量指 标的驱动下进行多维数据的可视化. ②以D(x)2 ∑eD(x) 的概率选择x∈X作为新的中

及聚类信息等． 然而，在对海量数据进行可视化时，情况更为复 杂，应用传统的数据可视化技术及流程时，往往会出 现图像叠加严重、可视化图像质量低、辨识性差等现 实问题，数据聚合是解决该问题的一种有效方法，也 就是在数据可视化之前先进行数据抽象．现有的数 据聚合方法往往没有为数据可视化进行专门的优化 和改进，更为重要的是，缺少针对可视化所作的数据 聚合质量度量，对数据聚合的质量没有量化和理论 支撑，本文研究的质量度量指标驱动的数据聚合弥 补了上述不足． 为了弥补人类视觉感知能力的不足，帮助人们理 解多维数据，研究人员提出了相当数量的数据可视化 方法，这些方法将多维数据通过降维转换并映射到三 维或者二维可视空间来实现多维信息的可视化．根据其 可视化的原理不同可以划分为基于几何的技术、面向 像素的技术、基于图标的技术、基于层次的技术、基于 图形的技术和基于降维映射的技术等［１⁃２］ ． 在数据量较大时，为了提高数据可视化的图像 质量，降低图像叠加的问题，通常会对数据进行抽 象，数据抽象的目的是在数据精简的同时，保持原数 据的各种特性，提高数据抽象后可视化的图像质量． 抽样和聚合是 ２ 种常用的数据抽象方法． Ｂｅｒｔｉｎｉ 等［３］提出了利用聚类聚合的方法在散点图中自动 降低图像叠加；Ｊｏｈａｎｓｓｏｎ 等［４］ 提出了基于距离变化 的数据抽样方法，并在屏幕空间对图像质量进行了 度量． 质量度量的研究由来已久，随着数据可视化技 术的发展，数据可视化中的质量度量越来越引起学 者们的注意，越来越多的成果发表在数据可视化领 域的重要期刊和会议上，这些方法也极大地促进了 数据可视化技术本身的发展．根据数据可视化度量 指标所实施的对象不同，现有的质量度量方法可以 被分成两大类：实施于数据空间和图像空间［５］ ．在数 据空间方面，Ｃｕｉ 等［６］ 研究了在抽象和聚合 ２ 种不 同的数据抽象方法下计算数据抽象质量，权衡如何 在数据精简和数据损失方面取得平衡；在图像空间 方面，Ｔａｔｕ 等［７］使用 Ｈｏｕｇｈ 变换对感兴趣的散点图 进行分级，以提高可视化图像质量．但是，图像空间 的质量度量存在着受限于某种单个数据可视化方法 的缺点． 本文提出一种数据空间质量度量驱动下的数据 聚合方法均分 Ｋ⁃ｍｅａｎｓ＋＋，这一方法面向多维数据， 广泛适用于大部分数据可视化方法，在质量度量指 标的驱动下进行多维数据的可视化． １ 均分 Ｋ⁃ｍｅａｎｓ＋＋：一种多维数据可 视化中的数据聚合方法 Ｋ⁃ｍｅａｎｓ 算法具有简单、聚类速度快的优点．在 大量的实验中发现，在进行海量数据的聚合运算中， Ｋ⁃ｍｅａｎｓ 算法具有以下缺点： １）在聚合运算，特别是海量数据的聚合运算 中，Ｋ 值往往较大，这种情况下，传统的 Ｋ⁃ｍｅａｎｓ 算 法会出现迭代次数过大的情况，极大地影响了聚合 速度． ２）传统的 Ｋ⁃ｍｅａｎｓ＋＋算法［８］虽然改进了初始点 的选择，但仍然以最小化近邻点距离之和为目的，往 往会出现各个聚簇的点数分布极不均匀的情况，某 些聚簇只有几个点，某些聚簇则有成百上千个点．但 是，在数据聚合中，往往希望聚合前的数据能在聚合 后的各个中心点上均匀分布，使聚合后的数据更好 地反映原数据的分布． 鉴于现有的 Ｋ⁃ｍｅａｎｓ 及其改进算法在数据聚合 中存在的缺陷，本文提出了均分 Ｋ⁃ｍｅａｎｓ＋＋的数据 聚合方法，仿真实验证明，该算法大大减少了迭代次 数，在分布上与原数据更加吻合，从而更加适用于数 据可视化中的数据聚合运算． 算法 １ 均分 Ｋ⁃ｍｅａｎｓ １）输入 ｄ 维空间［０，１］ ｄ 的 ｎ 个点 ｐ１ ，ｐ２ ，…， ｐｎ ，随机选择 ｋ 个初始点 Ｃ ＝ ｛ｃ１ ，ｃ２ ，…，ｃｋ｝． ２）设 α＝ｃｅｉｌ（ ｎ ｋ ），ｃｅｉｌ（·）为向上取整函数．将每 个样本点 ｐｉ 划分到最近的中心点 ｃｊ 所在的集合 Ｓｊ，如 果数目｜Ｓｊ ｜≥α，则表示该集合已满，继续寻找次近的中 心点所在的集合，直至找到一个未满（集合现有点数小 于 α）的较近的中心点所在的集合．用以上方法将样本 集合｛ｐｉ｝划分成 Ｓ１，Ｓ２，…，Ｓｋ ． ３）对于 １≤ｊ≤ｋ，计算集合 Ｓｊ 内点之和 ｓｕｍ ＝ ∑ｉ∈Ｓｊ ｐｉ 和数目 ｎｕｍ ＝ ｜ Ｓｊ ｜ ，ｃｊ ＝ ｓｕｍ ／ ｎｕｍ 为集合 Ｓｊ 新 的中心点． ４）重复 ２） ～３），直至 Ｃ 不再变化或迭代次数达 到上限． 算法 ２ 均分 Ｋ⁃ｍｅａｎｓ＋＋ 令 Ｄ（ｘ）表示一个数据点到离它最近的已经选出 的中心点的距离．则均分 Ｋ⁃ｍｅａｎｓ＋＋算法定义如下： １）输入 ｄ 维空间［０，１］ ｄ 的 ｎ 个点 ｐ１ ，ｐ２ ，…，ｐｎ ． ①均匀随机地在 Ｘ 中选出第 １ 个中心点 ． ②以 Ｄ（ｘ） ２ ∑ｘ∈ＸＤ（ｘ） ２的概率选择 ｘ∈Ｘ 作为新的中 ·３００· 智 能 系 统 学 报 第 ８ 卷

第4期 李杨，等：质量度量指标驱动的数据聚合与多维数据可视化 ·301· 心点c 2.2质量度量对象 ③重复②，直至选出k个中心点. 根据数据可视化度量指标所实施的对象不同， 2)继续算法1的2)~4)步. 现有的质量度量方法可以被分成两大类：实施于数 2质量度量指标驱动的数据可视化 据空间或图像空间 1)数据空间 数据可视化中的质量度量通常基于以下目的： 在数据空间计算的度量指标只使用可视化前后 寻找感兴趣的预测结果、降低图像叠加、发现有意义 的数据进行计算，不涉及到任何视图信息， 的模式等.近年来，虽然数据可视化中的质量度量研 2)图像空间. 究发展很快，但很少有人将这些成果总结，并指出它 面向图像空间的度量指标计算则绕过数据，直 们之间的联系，本文建立一个多维数据可视化质量 接对输出的图像信息进行计算，这类方法通常需要 评价模型，用来量化数据可视化中的聚合数据质量， 辅助复杂的图像处理方法。 从而驱动数据可视化图像质量的改善 2.3质量度量指标 2.1质量度量模型 1)聚类质量 可视化质量评价模型如图1所示.图中描述了 聚类质量指标用于度量可视化后的数据，保持 质量评价模型下的数据可视化过程，包括3个阶段： 分组信息的程度，对于明显分组的数据是否比较容 1)数据转换（源数据→转换后数据）.数据转换 易识别列 的主要目的是改变数据形式为更利于可视化的格 2)相关性指标。 式，例如对于一些高维数据，需要进行特征选择、投 相关性指标用于度量可视化后的数据保持原数 影等降维操作，对于海量数据，常见的操作是聚合和 据二维或多维之间相关性的程度.二维数据之间的 采样 Pearson相关性和多维数据之间的全局相关性都在 2)数据映射（转换后数据→可视化结构）.数据 映射是整个模型的核心部分，这一步将数据的每一 该指标考虑的范围之内[© 维表现为可视化结构中的可视特征同样的数据可 3)离群点指标。 离群点指标用于度量可视化后的数据保持那些 能映射为多种不同的可视化结构，质量评价指标需 要对这些过程进行评价.例如，不同的维序对应不同 与大部分其他数据明显不同的数据（即离群点）的 的可视化结构，相应的质量度量评价也是不同的. 能力) 3)视图转换（可视化结构→视图）.视图转换将 4)复杂模式指标 可视化结构翻译为特定的图像形式（如像素），这样 Wilkinson等提出一种度量发现复杂模式能 做的目的是为了突出图像空间的作用，因为某些质 力的指标，这些复杂模式不能在之前提出的分类中 量评价指标直接以可视化结构所对应的像素为计算 被发现，如“某种针织质地”、“某种身材指标”等 对象，不过，相对于数据空间质量评价而言，直接对 5)图像质量指标 图像空间进行的质量评价相对较少 图像质量指标不关心各种模式被保持的程度， 而是度量可视化后的图像质量，例如图形是否大量 重叠等 质量驱动的多维数据可视化 6)特征保持指标 特征保持指标度量可视化后的数据保持原数据 源数据 聚合数据 数据工程师 特征的程度这些特征包括原数据的分类信息[7,1)] 可视化中的抽象数据相对于原数据而言的信息损 图1总体框架 Fig.1 Overall framework 失[34]等用户感兴趣的特征信息 质量评价模型可以帮助数据分析者选择一个 2.4数据空间质量度量指标 可靠的过程组合.通常在一种情况下会有一个或者 图像空间中的质量度量对具体的数据可视化方 多个解决方案供数据分析者选择，整个选择过程都 法敏感，因此，本文选择的抽象数据级别(data ab- 是由质量评价指标驱动的，因为质量评价指标可以 straction level,.DAL)、直方图差值度量(histogram 量化每个阶段的数据或视图质量（向上箭头），计算 difference measure,HDM)、最近邻距离度量(nearest 结果最终影响整个处理过程（向下箭头） neighbor measure,NNM)3个指标是数据空间中的

心点 ｃｉ ． ③重复②，直至选出 ｋ 个中心点． ２）继续算法 １ 的 ２） ～４）步． ２ 质量度量指标驱动的数据可视化 数据可视化中的质量度量通常基于以下目的： 寻找感兴趣的预测结果、降低图像叠加、发现有意义 的模式等．近年来，虽然数据可视化中的质量度量研 究发展很快，但很少有人将这些成果总结，并指出它 们之间的联系，本文建立一个多维数据可视化质量 评价模型，用来量化数据可视化中的聚合数据质量， 从而驱动数据可视化图像质量的改善． ２．１ 质量度量模型 可视化质量评价模型如图 １ 所示．图中描述了 质量评价模型下的数据可视化过程，包括 ３ 个阶段： １）数据转换（源数据→转换后数据）．数据转换 的主要目的是改变数据形式为更利于可视化的格 式，例如对于一些高维数据，需要进行特征选择、投 影等降维操作，对于海量数据，常见的操作是聚合和 采样． ２）数据映射（转换后数据→可视化结构）．数据 映射是整个模型的核心部分，这一步将数据的每一 维表现为可视化结构中的可视特征．同样的数据可 能映射为多种不同的可视化结构，质量评价指标需 要对这些过程进行评价．例如，不同的维序对应不同 的可视化结构，相应的质量度量评价也是不同的． ３）视图转换（可视化结构→视图）．视图转换将 可视化结构翻译为特定的图像形式（如像素），这样 做的目的是为了突出图像空间的作用，因为某些质 量评价指标直接以可视化结构所对应的像素为计算 对象，不过，相对于数据空间质量评价而言，直接对 图像空间进行的质量评价相对较少． 图 １ 总体框架 Ｆｉｇ．１ Ｏｖｅｒａｌｌ ｆｒａｍｅｗｏｒｋ 质量评价模型可以帮助数据分析者选择一个 可靠的过程组合．通常在一种情况下会有一个或者 多个解决方案供数据分析者选择，整个选择过程都 是由质量评价指标驱动的，因为质量评价指标可以 量化每个阶段的数据或视图质量（向上箭头），计算 结果最终影响整个处理过程（向下箭头）． ２．２ 质量度量对象 根据数据可视化度量指标所实施的对象不同， 现有的质量度量方法可以被分成两大类：实施于数 据空间或图像空间． １）数据空间． 在数据空间计算的度量指标只使用可视化前后 的数据进行计算，不涉及到任何视图信息． ２）图像空间． 面向图像空间的度量指标计算则绕过数据，直 接对输出的图像信息进行计算，这类方法通常需要 辅助复杂的图像处理方法． ２．３ 质量度量指标 １）聚类质量． 聚类质量指标用于度量可视化后的数据，保持 分组信息的程度，对于明显分组的数据是否比较容 易识别［９］ ． ２）相关性指标． 相关性指标用于度量可视化后的数据保持原数 据二维或多维之间相关性的程度．二维数据之间的 Ｐｅａｒｓｏｎ 相关性和多维数据之间的全局相关性都在 该指标考虑的范围之内［１０］ ． ３）离群点指标． 离群点指标用于度量可视化后的数据保持那些 与大部分其他数据明显不同的数据（即离群点） 的 能力［１１］ ． ４）复杂模式指标． Ｗｉｌｋｉｎｓｏｎ 等 ［１２］提出一种度量发现复杂模式能 力的指标，这些复杂模式不能在之前提出的分类中 被发现，如“某种针织质地”、“某种身材指标”等． ５）图像质量指标． 图像质量指标不关心各种模式被保持的程度， 而是度量可视化后的图像质量，例如图形是否大量 重叠等． ６）特征保持指标． 特征保持指标度量可视化后的数据保持原数据 特征的程度．这些特征包括原数据的分类信息［７，１３］ 、 可视化中的抽象数据相对于原数据而言的信息损 失［３⁃４］等用户感兴趣的特征信息． ２．４ 数据空间质量度量指标 图像空间中的质量度量对具体的数据可视化方 法敏感，因此，本文选择的抽象数据级别（ ｄａｔａ ａｂ⁃ ｓｔｒａｃｔｉｏｎ ｌｅｖｅｌ， ＤＡＬ）、直方图差值度量 （ ｈｉｓｔｏｇｒａｍ ｄｉｆｆｅｒｅｎｃｅ ｍｅａｓｕｒｅ， ＨＤＭ）、最近邻距离度量（ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ ｍｅａｓｕｒｅ， ＮＮＭ） ３ 个指标是数据空间中的 第 ４ 期 李杨，等：质量度量指标驱动的数据聚合与多维数据可视化 ·３０１·

·302· 智能系统学报 第8卷 质量度量指标，能够较好地验证算法2在聚类质量 ③)标准化所有最小距离的平均值为NNM表 图像质量和特征保持指标上的表现 示抽象前数据集的大小 1)DAL. ∑D DAL是数据抽象级别的缩写，用来表示数据抽 NNM=1 i=1 象的程度，计算公式如式(1)： R DAL=N./N。 (1) 3 仿真实验 式中：N表示抽象后的数据集大小，N。表示原数据 集的大小 在几大类数据可视化方法中，基于几何的技术、 2)HDM. 面向像素的技术、基于层次的技术和基于图形的技 HDM定义为抽象前后2个直方图的标准差，取 术均适用于本文提出的方法.基于几何技术的基本 值范围是[0,1]，0表示2个直方图所对应的每一对 思想是以点、线等几何画法将多维数据展现在二维、 桶都有其中一个是空的，1则表示2个直方图所对 三维空间，适合于维数高但数据量相对不多的数据 应的每一对桶都完全一致，用式(2)来表示2个直 集，其代表方法为平行坐标法[4，其他方法还包括 方图第i个桶的差值： 放射坐标系[us)、散点图矩阵[16]、Andrews曲线法[ P=P。-P (2) 等.面向像素的技术利用像素的颜色代表数据的值， 式中：P。是抽象前数据落入第i个桶的比例，P,是抽 空间被分割成多个子窗口，每个子窗口对应多维数 象后数据落入第i个桶的比例，P。是2个桶的差值. 据中的一维，比较有代表性的方法包括VisDB18] 圆形分段法[等.基于层次的技术可以对数据进行 P= ∑P,=∑Ip,-P,l. 层次划分，将数据以层次结构的方式组织并以图形 式中：P。是2个直方图的差值，N是直方图中桶的 表示出来，在不同层次上表示不同维度的元素值，适 数量 用于每一维数据之间具有层次关系的多维数据.包 HDM =1-P..- (3) 括维堆[20]、嵌套坐标系[2)等方法.基于图形的技术 利用图形的大小、颜色等属性表示数据，代表方法包 如式(3)定义，HDM是直方图标准差，P,是P最 括多线图、Survey Plot!2],这2种方法都是在平行坐 大值 标法的基础上发展而来的. 对于n维数据集的HDM定义为n个一维HDM 上述的数据可视化方法的共同点是其可视化图 平均值默认的桶宽使用式(4)计算： 像质量容易受到数据集大小的影响，因此，在应用本 W=3.49×S×Num3. (4) 文提出的数据聚合方法时，既能够提高可视化图像 式中：S为某一维数据的标准差，um为数据集的大小 质量，又能保持原数据的大部分特性.限于篇幅，本 3)NNM. 文只展示了2种最具代表性的数据可视化方法：平 NNM定义为每条记录与其抽象后代表它的记 行坐标法和散点图法 录之间的标准化距离平均值，计算公式如下： 文中涉及的算法实现编程环境为MATLAB7.1, ①n维空间内2条记录U、V之间的欧氏距离为 数据可视化工具为XmdvTool],实验环境为Win- ∑(U-V)2 dows XP3.6GHz,2.00GB,实验中的所有数据都被规 D(U.= 范化至[O,1]6,3个质量评价指标DAL、HDM、NNM n 的取值范围均为[0,1].数据基本信息如表1所示. ②对抽象前数据集中的第i条记录，计算它与 表1实验数据信息 抽象后数据集中每一条记录之间的距离，选择其中 Table 1 Experimental data 距离最小的值作为D 数据集 属性 数据集 D:minD(X:,Y). 属性数 记录数 = 名称 数据类型 别名 式中：X,是抽象前数据集中的第i条记录，y是抽象 后数据集中的第j条记录，A表示抽象后数据集的 AAUP(25] 14 real 1161 DS 大小，D,代表第i条记录的距离. out5d[2s] 5 real 16384 DS

质量度量指标，能够较好地验证算法 ２ 在聚类质量、 图像质量和特征保持指标上的表现． １）ＤＡＬ． ＤＡＬ 是数据抽象级别的缩写，用来表示数据抽 象的程度，计算公式如式（１）： ＤＡＬ ＝ Ｎａ ／ Ｎｏ ． （１） 式中：Ｎａ 表示抽象后的数据集大小，Ｎｏ 表示原数据 集的大小． ２）ＨＤＭ． ＨＤＭ 定义为抽象前后 ２ 个直方图的标准差，取 值范围是［０，１］，０ 表示 ２ 个直方图所对应的每一对 桶都有其中一个是空的，１ 则表示 ２ 个直方图所对 应的每一对桶都完全一致，用式（２）来表示 ２ 个直 方图第 ｉ 个桶的差值： Ｐｂ ｉ ＝｜ Ｐｏ ｉ － Ｐｓ ｉ ｜ ． （２） 式中：Ｐｏ ｉ 是抽象前数据落入第 ｉ 个桶的比例，Ｐｓ ｉ 是抽 象后数据落入第 ｉ 个桶的比例，Ｐｂ ｉ 是 ２ 个桶的差值． Ｐｈ ＝ ∑ Ｎ ｉ ＝ １ Ｐｂ ｉ ＝ ∑ Ｎ ｉ ＝ １ ｜ Ｐｏ ｉ － Ｐｓ ｉ ｜ ． 式中：Ｐｈ 是 ２ 个直方图的差值，Ｎ 是直方图中桶的 数量． ＨＤＭ ＝ １ － Ｐｈ Ｐｈ， ｍａｘ ． （３） 如式（３）定义，ＨＤＭ 是直方图标准差，Ｐｈ， ｍａｘ是 Ｐｈ 最 大值． 对于 ｎ 维数据集的 ＨＤＭ 定义为 ｎ 个一维 ＨＤＭ 平均值．默认的桶宽使用式（４）计算： Ｗ ＝ ３．４９ × Ｓ × Ｎｕｍ １ ３ ． （４） 式中：Ｓ 为某一维数据的标准差，Ｎｕｍ 为数据集的大小． ３）ＮＮＭ． ＮＮＭ 定义为每条记录与其抽象后代表它的记 录之间的标准化距离平均值，计算公式如下： ①ｎ 维空间内 ２ 条记录 Ｕ、Ｖ 之间的欧氏距离为 Ｄ（Ｕ，Ｖ） ＝ ∑ ｎ ｋ ＝ １ （Ｕｋ － Ｖｋ） ２ ｎ ． ②对抽象前数据集中的第 ｉ 条记录，计算它与 抽象后数据集中每一条记录之间的距离，选择其中 距离最小的值作为 Ｄｉ ． Ｄｉ ＝ ｍｉｎ Ａ ｊ ＝ １ Ｄ（Ｘｉ，Ｙｊ）． 式中：Ｘｉ 是抽象前数据集中的第 ｉ 条记录，Ｙｊ 是抽象 后数据集中的第 ｊ 条记录，Ａ 表示抽象后数据集的 大小，Ｄｉ 代表第 ｉ 条记录的距离． ③）标准化所有最小距离的平均值为 ＮＮＭ 表 示抽象前数据集的大小． ＮＮＭ ＝ １ － ∑ Ｒ ｉ ＝ １ Ｄｉ Ｒ ． ３ 仿真实验 在几大类数据可视化方法中，基于几何的技术、 面向像素的技术、基于层次的技术和基于图形的技 术均适用于本文提出的方法．基于几何技术的基本 思想是以点、线等几何画法将多维数据展现在二维、 三维空间，适合于维数高但数据量相对不多的数据 集，其代表方法为平行坐标法［１４］ ，其他方法还包括 放射坐标系［１５］ 、散点图矩阵［１６］ 、Ａｎｄｒｅｗｓ 曲线法［１７］ 等．面向像素的技术利用像素的颜色代表数据的值， 空间被分割成多个子窗口，每个子窗口对应多维数 据中的一维，比较有代表性的方法包括 ＶｉｓＤＢ ［１８］ 、 圆形分段法［１９］等．基于层次的技术可以对数据进行 层次划分，将数据以层次结构的方式组织并以图形 表示出来，在不同层次上表示不同维度的元素值，适 用于每一维数据之间具有层次关系的多维数据．包 括维堆［２０］ 、嵌套坐标系［２１］ 等方法．基于图形的技术 利用图形的大小、颜色等属性表示数据，代表方法包 括多线图、Ｓｕｒｖｅｙ Ｐｌｏｔ ［２２］ ，这 ２ 种方法都是在平行坐 标法的基础上发展而来的． 上述的数据可视化方法的共同点是其可视化图 像质量容易受到数据集大小的影响，因此，在应用本 文提出的数据聚合方法时，既能够提高可视化图像 质量，又能保持原数据的大部分特性．限于篇幅，本 文只展示了 ２ 种最具代表性的数据可视化方法：平 行坐标法和散点图法． 文中涉及的算法实现编程环境为ＭＡＴＬＡＢ ７．１， 数据可视化工具为 ＸｍｄｖＴｏｏｌ ［２３］ ，实验环境为 Ｗｉｎ⁃ ｄｏｗｓ ＸＰ ３．６ＧＨｚ，２．００ＧＢ，实验中的所有数据都被规 范化至［０，１］ ６ ，３ 个质量评价指标 ＤＡＬ、ＨＤＭ、ＮＮＭ 的取值范围均为［０，１］．数据基本信息如表 １ 所示． 表 １ 实验数据信息 Ｔａｂｌｅ １ Ｅｘｐｅｒｉｍｅｎｔａｌ ｄａｔａ 数据集 名称 属性数 属性 数据类型 记录数 数据集 别名 ＡＡＵＰ ［２５］ １４ ｒｅａｌ １ １６１ ＤＳ１ ｏｕｔ５ｄ ［２５］ ５ ｒｅａｌ １６ ３８４ ＤＳ２ ·３０２· 智 能 系 统 学 报 第 ８ 卷

第4期 李杨，等：质量度量指标驱动的数据聚合与多维数据可视化 ·303- 3.1质量度量驱动的平行坐标图聚合前后对比 数据集DS,采用算法2分别以数据抽象级别 DAL=0.07,0.04,0.02时进行数据聚合.图2包含了 数据聚合前后的平行坐标图，可以发现，在DAL=1, 即数据聚合前，数据叠加严重，难以辨识其中任何的 (a)DAL=1 (b)DAL=0.07 数据，而聚合后的数据不仅保持了较高的质量度量 指标（如图3所示），图像质量也有了明显的提高。 (c)DAL=0.04 (d)DAL=0.02 图4不同DAL下DS2的散点图 Fig.4 Scatter plots of DS,at different DAL (a)DAL=I (b)DAL=0.07 触 1.0 0.8 0.6 (c)DAL=0.04 (d)DAL=0.02 图2不同DAL下DS,的平行坐标图 Fig.2 Parallel coordinates of DS,at different DALS 0.2 0.02 .04 0.07 DAL 图5不同DAL下DS,的质量度量指标 Fig.5 Quality metrics of DS,at different DAL 0.8 0.6 4结束语 0.4 质量度量指标驱动下的数据聚合加入了质量量 化指标，聚合数据的质量可以被精确量化，可以帮助 0.2 数据工程师在数据可视化的过程中根据实际需求调 整度量指标参数，以获取聚合数据质量与可视化图 0.02 0.04 0.07 DAL 像质量之间的平衡.本文提出了一种均分K-means++ 图3不同DAL下DS,的质量度量指标 数据聚合算法，仿真实验表明，与传统的聚类算法相 Fig.3 Quality metrics of DS,at different DAL 比，均分K-means-++更适用于以提高数据可视化图 3.2质量度量驱动的散点图聚合前后对比 像质量为目的的数据聚合.目前，均分K-means++数 图4是数据集DS,用算法2进行数据聚合前 据聚合算法存在的问题是当K增大到一定程度时， (DAL=1)及聚合后(DAL为0.02,0.04,0.07)的散 初始点的计算效率较低，下一步将研究如何在海量 点图矩阵.不难发现，在DAL=1时，各个数据，点叠加 数据集上提高算法效率， 严重，很难辨识其中的任何有用信息，也难以发现两 维属性之间的关系，而聚合后的数据即使在DAL= 参考文献： 0.02时，也能很容易地发现其中存在的属性关联信 [1]孙扬，封孝生，唐九阳，等.多维可视化技术综述[J刀].计 息.图5展示了聚合后的DS2同样保持了较高的质 算机科学，2008,35(11)：1-7. 量度量指标.当数据维度较小时，聚合后的数据在散 SUN Yang,FENG Xiaosheng,TANG Jiuyang,et al.Survey 点图上的表现更好 on the research of multidimensional and multivariate data vi- sualization[]].Computer Science,2008.35(11):1-7

３．１ 质量度量驱动的平行坐标图聚合前后对比 数据集 ＤＳ１ 采用算法 ２ 分别以数据抽象级别 ＤＡＬ ＝ ０．０７，０．０４，０．０２ 时进行数据聚合．图 ２ 包含了 数据聚合前后的平行坐标图，可以发现，在 ＤＡＬ ＝ １， 即数据聚合前，数据叠加严重，难以辨识其中任何的 数据，而聚合后的数据不仅保持了较高的质量度量 指标（如图 ３ 所示），图像质量也有了明显的提高． 图 ２ 不同 ＤＡＬ 下 ＤＳ１ 的平行坐标图 Ｆｉｇ．２ Ｐａｒａｌｌｅｌ ｃｏｏｒｄｉｎａｔｅｓ ｏｆ ＤＳ１ ａｔ ｄｉｆｆｅｒｅｎｔ ＤＡＬＳ 图 ３ 不同 ＤＡＬ 下 ＤＳ１ 的质量度量指标 Ｆｉｇ．３ Ｑｕａｌｉｔｙ ｍｅｔｒｉｃｓ ｏｆ ＤＳ１ ａｔ ｄｉｆｆｅｒｅｎｔ ＤＡＬ ３．２ 质量度量驱动的散点图聚合前后对比 图 ４ 是数据集 ＤＳ２ 用算法 ２ 进行数据聚合前 （ＤＡＬ ＝ １）及聚合后（ＤＡＬ 为 ０．０２，０．０４，０．０７）的散 点图矩阵．不难发现，在 ＤＡＬ ＝ １ 时，各个数据点叠加 严重，很难辨识其中的任何有用信息，也难以发现两 维属性之间的关系，而聚合后的数据即使在 ＤＡＬ ＝ ０．０２时，也能很容易地发现其中存在的属性关联信 息．图 ５ 展示了聚合后的 ＤＳ２ 同样保持了较高的质 量度量指标．当数据维度较小时，聚合后的数据在散 点图上的表现更好． 图 ４ 不同 ＤＡＬ 下 ＤＳ２ 的散点图 Ｆｉｇ．４ Ｓｃａｔｔｅｒ ｐｌｏｔｓ ｏｆ ＤＳ２ ａｔ ｄｉｆｆｅｒｅｎｔ ＤＡＬ 图 ５ 不同 ＤＡＬ 下 ＤＳ２ 的质量度量指标 Ｆｉｇ．５ Ｑｕａｌｉｔｙ ｍｅｔｒｉｃｓ ｏｆ ＤＳ２ ａｔ ｄｉｆｆｅｒｅｎｔ ＤＡＬ ４ 结束语 质量度量指标驱动下的数据聚合加入了质量量 化指标，聚合数据的质量可以被精确量化，可以帮助 数据工程师在数据可视化的过程中根据实际需求调 整度量指标参数，以获取聚合数据质量与可视化图 像质量之间的平衡．本文提出了一种均分Ｋ⁃ｍｅａｎｓ＋＋ 数据聚合算法，仿真实验表明，与传统的聚类算法相 比，均分Ｋ⁃ｍｅａｎｓ＋＋更适用于以提高数据可视化图 像质量为目的的数据聚合．目前，均分 Ｋ⁃ｍｅａｎｓ＋＋数 据聚合算法存在的问题是当 Ｋ 增大到一定程度时， 初始点的计算效率较低，下一步将研究如何在海量 数据集上提高算法效率． 参考文献： ［１］孙扬， 封孝生， 唐九阳，等． 多维可视化技术综述［ Ｊ］．计 算机科学， ２００８， ３５（１１）： １⁃７． ＳＵＮ Ｙａｎｇ， ＦＥＮＧ Ｘｉａｏｓｈｅｎｇ， ＴＡＮＧ Ｊｉｕｙａｎｇ， ｅｔ ａｌ． Ｓｕｒｖｅｙ ｏｎ ｔｈｅ ｒｅｓｅａｒｃｈ ｏｆ ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ ａｎｄ ｍｕｌｔｉｖａｒｉａｔｅ ｄａｔａ ｖｉ⁃ ｓｕａｌｉｚａｔｉｏｎ［Ｊ］． Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， ２００８， ３５（１１）： １⁃７． 第 ４ 期 李杨，等：质量度量指标驱动的数据聚合与多维数据可视化 ·３０３·

·304. 智能系统学报 第8卷 [2]KEIM D A,ANKERST M.Visual data mining and explora- [16]MATRIX S.Scatter plot matrics[EB/OL].[2012-09-20]. tion of large databases[C]//PKDD.Freiburg,Germany, http://www.itl.nist.Gov/div898/hand book/eda/section3/ 2001:104-109. eda33qb.html. [3]BERTINI E,SANTUCCI G.Quality metrics for 2D scatter- [17]ANDREWS D F.Plots of high-dimensional data[J].Bio- plot graphics:automatically reducing visual clutter[C] metrics.1972.28(1):125-136. Smart Graphics 4th International Symposium.Banff,Cana- [18]KEIM D A,KRIEGEL H P.VisDB:database exploration da,2004:10-15. using multidimensional visualization[J].Computer Graph- [4]JOHANSSON J,COOPER M.A screen space quality meth- ics Applications,1994,14(5):40-49. od for data abstraction[J].Computer Graphics Forum, [19]HOFMAN P E.Table visualizations:a formal model and 2008,27(3):1039-1046. its applications[D].Lowell,USA:University of Massa- [5]BERTINI E,TATU A,KEIM D.Quality metrics in high-di- chusetts,1999:25. mensional data visualization:an overview and systematiza- [20]WARD M O,LEBLANC J,TIPNIS R.N-Land:a graph- tion[J].IEEE Trans on Visualization and Computer Graph- ical tool for exploring n-dimensional data[C]//Computer ics,2011,17(12):2203-2212. Graphics International Conference.Melbourne,Australia, [6]CUI Q,WARD M,RUNDENSTEINER E,et al.Measuring 1994:1-14. data abstraction quality in multiresolution visualizations[]. [21]FEINER S,BESHERS C.Worlds within worlds:meta- IEEE Trans on Visualization and Computer Graphics,2006, phors for exploring n-dimensional virtual worlds [C]// 23(12):709-716. ACM Proceedings Conference on User Interface Software [7]ALBUQUERQUE T A,EISEMANN G.Combining automa- Design.New York,USA,1990:76-83. ted analysis and visualization techniques for effective explo- [22]LOHNINGER H.INSPECT,a program system to visualize ration of high-dimensional data C]//Proc IEEE Symp Vis- and interpret chemical data[J].Chemometrics and Intelli- ual Analytics Science and Technology.Atlantic City,USA, gent Laboratory Systems,1994,22(1):147-153. 2009:59-66. [23]WARD M0.“Xmdvtool"[EB/0L].[2012-09-23].Xmw [8]ARTHUR D,VASSILVITSKII S.K-means++:the advanta- Users Group.http://davis.wpi.edu/xmdv/datasets.html. ges of careful seeding[C]//Symposium on Discrete Algo- 作者简介： rithms.Philadelphia,USA,2007:1027-1035. 李杨，女，1980年生，讲师，博士研 [9]FERDOSI B J,BERNOULLI J.Finding and visualizing rele- 究生，主要研究方向为数据可视化、机 vant subspaces for clustering high-dimensional astronomical 器学习.获云浮市科技进步奖二等奖1 data using connected morphological operators [C]//IEEE 项，发明专利授权1项，实用新型专利1 Conf Visual Analytics Science and Technology.Salt Lake 项发表学术论文8篇。 City,USA,2010:35-42. [10]JOHANSSON S,JOHANSSON J.Interactive dimensionali- ty reduction through user-defined combinations of quality 郝志峰，男，1968年生，教授，博士 metrics[J].IEEE Trans on Visualization and Computer 生导师，主要研究方向为机器学习、仿 Graphics,2009,15(6):993-1000. 生算法、生物信息学.共主持国家自然 [11]PENG W,WARD M O,RUNDENSTEINER E A.Clutter 科学基金、教育部霍英东基金、广东省 reduction in multi-dimensional data visualization using di- 自然科学基金、广东省科技攻关项目、 mension reordering C//IEEE Symp Information Visual- 广东省省部产学研项目等省部级以上 ization.Austin,USA,2004:89-96. 项目22项.获国家、省部级各类奖项20余项，广东省科技最 [12]WILKINSON L,ANAND A,GROSSMAN R.Graph-theo- 高个人荣誉“丁颖科技奖”，发表学术论文60余篇。 retic scagnostics[C]//IEEE Symp Information Visualiza- tion.Chicago,USA,2005:157-164. 谢光强，男，1979年生，副教授，硕 [13]SIPS M,NEUBERT B,LEWIS J P,et al.Selecting good 士生导师，主要研究方向为多智能体、 views of high-dimensional data using class consistency[]. 智能控制.主持省部产学研等科研项目 Computer Graphics Forum,2009,28(3):30-41. 11项，获得专利和软件著作权10项，指 [14]INSELBERG A.The plane with parallel coordinates [J]. 导学生获各类国家、省级奖项30余项， The Visual Computer,1985,1(2):69-91. 发表学术论文11篇，其中被I和ISTP [15]HOFFMAN P E,GRINSTEIN GG,MARX K,et al. 检索4篇。 DNA visual and analytic data mining[C]//IEEE Visual- ization Phoenix.Phoenix,USA,1997:437-441

高个人荣誉 “丁颖科技奖” ， 发表学术论文 ６０ 余篇． 科学基金、教育部霍英东基金、广东省 ［２］ＫＥＩＭ Ｄ Ａ， ＡＮＫＥＲＳＴ Ｍ． Ｖｉｓｕａｌ ｄａｔａ ｍｉｎｉｎｇ ａｎｄ ｅｘｐｌｏｒａ⁃ ｔｉｏｎ ｏｆ ｌａｒｇｅ ｄａｔａｂａｓｅｓ ［ Ｃ］ ／ ／ ＰＫＤＤ． Ｆｒｅｉｂｕｒｇ， Ｇｅｒｍａｎｙ， ２００１： １０４⁃１０９． ［３］ＢＥＲＴＩＮＩ Ｅ， ＳＡＮＴＵＣＣＩ Ｇ． Ｑｕａｌｉｔｙ ｍｅｔｒｉｃｓ ｆｏｒ ２Ｄ ｓｃａｔｔｅｒ⁃ ｐｌｏｔ ｇｒａｐｈｉｃｓ： ａｕｔｏｍａｔｉｃａｌｌｙ ｒｅｄｕｃｉｎｇ ｖｉｓｕａｌ ｃｌｕｔｔｅｒ ［ Ｃ］ ／ ／ Ｓｍａｒｔ Ｇｒａｐｈｉｃｓ ４ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ． Ｂａｎｆｆ， Ｃａｎａ⁃ ｄａ， ２００４： １０⁃１５． ［４］ＪＯＨＡＮＳＳＯＮ Ｊ， ＣＯＯＰＥＲ Ｍ． Ａ ｓｃｒｅｅｎ ｓｐａｃｅ ｑｕａｌｉｔｙ ｍｅｔｈ⁃ ｏｄ ｆｏｒ ｄａｔａ ａｂｓｔｒａｃｔｉｏｎ ［ Ｊ ］． Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ Ｆｏｒｕｍ， ２００８， ２７（３）： １０３９⁃１０４６． ［５］ＢＥＲＴＩＮＩ Ｅ， ＴＡＴＵ Ａ， ＫＥＩＭ Ｄ． Ｑｕａｌｉｔｙ ｍｅｔｒｉｃｓ ｉｎ ｈｉｇｈ⁃ｄｉ⁃ ｍｅｎｓｉｏｎａｌ ｄａｔａ ｖｉｓｕａｌｉｚａｔｉｏｎ： ａｎ ｏｖｅｒｖｉｅｗ ａｎｄ ｓｙｓｔｅｍａｔｉｚａ⁃ ｔｉｏｎ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｖｉｓｕａｌｉｚａｔｉｏｎ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈ⁃ ｉｃｓ， ２０１１， １７（１２）： ２２０３⁃２２１２． ［６］ＣＵＩ Ｑ， ＷＡＲＤ Ｍ， ＲＵＮＤＥＮＳＴＥＩＮＥＲ Ｅ， ｅｔ ａｌ． Ｍｅａｓｕｒｉｎｇ ｄａｔａ ａｂｓｔｒａｃｔｉｏｎ ｑｕａｌｉｔｙ ｉｎ ｍｕｌｔｉｒｅｓｏｌｕｔｉｏｎ ｖｉｓｕａｌｉｚａｔｉｏｎｓ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｖｉｓｕａｌｉｚａｔｉｏｎ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ， ２００６， ２３（１２）： ７０９⁃７１６． ［７］ＡＬＢＵＱＵＥＲＱＵＥ Ｔ Ａ， ＥＩＳＥＭＡＮＮ Ｇ． Ｃｏｍｂｉｎｉｎｇ ａｕｔｏｍａ⁃ ｔｅｄ ａｎａｌｙｓｉｓ ａｎｄ ｖｉｓｕａｌｉｚａｔｉｏｎ ｔｅｃｈｎｉｑｕｅｓ ｆｏｒ ｅｆｆｅｃｔｉｖｅ ｅｘｐｌｏ⁃ ｒａｔｉｏｎ ｏｆ ｈｉｇｈ⁃ｄｉｍｅｎｓｉｏｎａｌ ｄａｔａ［Ｃ］ ／ ／ Ｐｒｏｃ ＩＥＥＥ Ｓｙｍｐ Ｖｉｓ⁃ ｕａｌ Ａｎａｌｙｔｉｃｓ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ． Ａｔｌａｎｔｉｃ Ｃｉｔｙ， ＵＳＡ， ２００９： ５９⁃６６． ［８］ＡＲＴＨＵＲ Ｄ， ＶＡＳＳＩＬＶＩＴＳＫＩＩ Ｓ． Ｋ⁃ｍｅａｎｓ＋＋： ｔｈｅ ａｄｖａｎｔａ⁃ ｇｅｓ ｏｆ ｃａｒｅｆｕｌ ｓｅｅｄｉｎｇ ［ Ｃ］ ／ ／ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｄｉｓｃｒｅｔｅ Ａｌｇｏ⁃ ｒｉｔｈｍｓ． Ｐｈｉｌａｄｅｌｐｈｉａ， ＵＳＡ， ２００７： １０２７⁃１０３５． ［９］ＦＥＲＤＯＳＩ Ｂ Ｊ， ＢＥＲＮＯＵＬＬＩ Ｊ． Ｆｉｎｄｉｎｇ ａｎｄ ｖｉｓｕａｌｉｚｉｎｇ ｒｅｌｅ⁃ ｖａｎｔ ｓｕｂｓｐａｃｅｓ ｆｏｒ ｃｌｕｓｔｅｒｉｎｇ ｈｉｇｈ⁃ｄｉｍｅｎｓｉｏｎａｌ ａｓｔｒｏｎｏｍｉｃａｌ ｄａｔａ ｕｓｉｎｇ ｃｏｎｎｅｃｔｅｄ ｍｏｒｐｈｏｌｏｇｉｃａｌ ｏｐｅｒａｔｏｒｓ ［ Ｃ］ ／ ／ ＩＥＥＥ Ｃｏｎｆ Ｖｉｓｕａｌ Ａｎａｌｙｔｉｃｓ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ． Ｓａｌｔ Ｌａｋｅ Ｃｉｔｙ， ＵＳＡ， ２０１０： ３５⁃４２． ［１０］ＪＯＨＡＮＳＳＯＮ Ｓ， ＪＯＨＡＮＳＳＯＮ Ｊ． Ｉｎｔｅｒａｃｔｉｖｅ ｄｉｍｅｎｓｉｏｎａｌｉ⁃ ｔｙ ｒｅｄｕｃｔｉｏｎ ｔｈｒｏｕｇｈ ｕｓｅｒ⁃ｄｅｆｉｎｅｄ ｃｏｍｂｉｎａｔｉｏｎｓ ｏｆ ｑｕａｌｉｔｙ ｍｅｔｒｉｃｓ［ Ｊ］． ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｖｉｓｕａｌｉｚａｔｉｏｎ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ， ２００９， １５（６）： ９９３⁃１０００． ［１１］ＰＥＮＧ Ｗ， ＷＡＲＤ Ｍ Ｏ， ＲＵＮＤＥＮＳＴＥＩＮＥＲ Ｅ Ａ． Ｃｌｕｔｔｅｒ ｒｅｄｕｃｔｉｏｎ ｉｎ ｍｕｌｔｉ⁃ｄｉｍｅｎｓｉｏｎａｌ ｄａｔａ ｖｉｓｕａｌｉｚａｔｉｏｎ ｕｓｉｎｇ ｄｉ⁃ ｍｅｎｓｉｏｎ ｒｅｏｒｄｅｒｉｎｇ ［ Ｃ］ ／ ／ ＩＥＥＥ Ｓｙｍｐ Ｉｎｆｏｒｍａｔｉｏｎ Ｖｉｓｕａｌ⁃ ｉｚａｔｉｏｎ． Ａｕｓｔｉｎ， ＵＳＡ， ２００４： ８９⁃９６． ［１２］ＷＩＬＫＩＮＳＯＮ Ｌ， ＡＮＡＮＤ Ａ， ＧＲＯＳＳＭＡＮ Ｒ． Ｇｒａｐｈ⁃ｔｈｅｏ⁃ ｒｅｔｉｃ ｓｃａｇｎｏｓｔｉｃｓ ［ Ｃ］ ／ ／ ＩＥＥＥ Ｓｙｍｐ Ｉｎｆｏｒｍａｔｉｏｎ Ｖｉｓｕａｌｉｚａ⁃ ｔｉｏｎ． Ｃｈｉｃａｇｏ， ＵＳＡ， ２００５： １５７⁃１６４． ［１３］ＳＩＰＳ Ｍ， ＮＥＵＢＥＲＴ Ｂ， ＬＥＷＩＳ Ｊ Ｐ， ｅｔ ａｌ． Ｓｅｌｅｃｔｉｎｇ ｇｏｏｄ ｖｉｅｗｓ ｏｆ ｈｉｇｈ⁃ｄｉｍｅｎｓｉｏｎａｌ ｄａｔａ ｕｓｉｎｇ ｃｌａｓｓ ｃｏｎｓｉｓｔｅｎｃｙ［Ｊ］． Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ Ｆｏｒｕｍ， ２００９， ２８（３）： ３０⁃４１． ［１４］ ＩＮＳＥＬＢＥＲＧ Ａ． Ｔｈｅ ｐｌａｎｅ ｗｉｔｈ ｐａｒａｌｌｅｌ ｃｏｏｒｄｉｎａｔｅｓ ［ Ｊ］． Ｔｈｅ Ｖｉｓｕａｌ Ｃｏｍｐｕｔｅｒ， １９８５， １（２）： ６９⁃９１． ［１５］ ＨＯＦＦＭＡＮ Ｐ Ｅ， ＧＲＩＮＳＴＥＩＮ Ｇ Ｇ， ＭＡＲＸ Ｋ， ｅｔ ａ１． ＤＮＡ ｖｉｓｕａｌ ａｎｄ ａｎａｌｙｔｉｃ ｄａｔａ ｍｉｎｉｎｇ［Ｃ］ ／ ／ ＩＥＥＥ Ｖｉｓｕａｌ⁃ ｉｚａｔｉｏｎ Ｐｈｏｅｎｉｘ． Ｐｈｏｅｎｉｘ， ＵＳＡ， １９９７： ４３７⁃４４１． ［１６］ＭＡＴＲＩＸ Ｓ． Ｓｃａｔｔｅｒ ｐｌｏｔ ｍａｔｒｉｃｓ［ＥＢ／ ＯＬ］．［２０１２⁃０９⁃２０］． ｈｔｔｐ： ／ ／ ｗｗｗ．ｉｔｌ．ｎｉｓｔ．Ｇｏｖ ／ ｄｉｖ８９８ ／ ｈａｎｄ ｂｏｏｋ ／ ｅｄａ ／ ｓｅｃｔｉｏｎ３ ／ ｅｄａ３３ｑｂ．ｈｔｍｌ． ［１７］ＡＮＤＲＥＷＳ Ｄ Ｆ． Ｐｌｏｔｓ ｏｆ ｈｉｇｈ⁃ｄｉｍｅｎｓｉｏｎａｌ ｄａｔａ［ Ｊ］． Ｂｉｏ⁃ ｍｅｔｒｉｃｓ， １９７２， ２８（１）： １２５⁃１３６． ［１８］ＫＥＩＭ Ｄ Ａ， ＫＲＩＥＧＥＬ Ｈ Ｐ． ＶｉｓＤＢ： ｄａｔａｂａｓｅ ｅｘｐｌｏｒａｔｉｏｎ ｕｓｉｎｇ ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ ｖｉｓｕａｌｉｚａｔｉｏｎ［ Ｊ］． Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈ⁃ ｉｃｓ Ａｐｐｌｉｃａｔｉｏｎｓ， １９９４， １４（５）： ４０⁃４９． ［１９］ＨＯＦＭＡＮ Ｐ Ｅ． Ｔａｂｌｅ ｖｉｓｕａｌｉｚａｔｉｏｎｓ： ａ ｆｏｒｍａｌ ｍｏｄｅｌ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎｓ ［Ｄ］． Ｌｏｗｅｌｌ， ＵＳＡ： Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｍａｓｓａ⁃ ｃｈｕｓｅｔｔｓ， １９９９： ２５． ［２０］ＷＡＲＤ Ｍ Ｏ， ＬＥＢＬＡＮＣ Ｊ， ＴＩＰＮＩＳ Ｒ． Ｎ⁃Ｌａｎｄ： ａ ｇｒａｐｈ⁃ ｉｃａｌ ｔｏｏｌ ｆｏｒ ｅｘｐｌｏｒｉｎｇ ｎ⁃ｄｉｍｅｎｓｉｏｎａｌ ｄａｔａ ［ Ｃ］ ／ ／ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ． Ｍｅｌｂｏｕｒｎｅ， Ａｕｓｔｒａｌｉａ， １９９４： １⁃１４． ［２１］ ＦＥＩＮＥＲ Ｓ， ＢＥＳＨＥＲＳ Ｃ． Ｗｏｒｌｄｓ ｗｉｔｈｉｎ ｗｏｒｌｄｓ： ｍｅｔａ⁃ ｐｈｏｒｓ ｆｏｒ ｅｘｐｌｏｒｉｎｇ ｎ⁃ｄｉｍｅｎｓｉｏｎａｌ ｖｉｒｔｕａｌ ｗｏｒｌｄｓ ［ Ｃ］ ／ ／ ＡＣＭ Ｐｒｏｃｅｅｄｉｎｇｓ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｕｓｅｒ Ｉｎｔｅｒｆａｃｅ Ｓｏｆｔｗａｒｅ Ｄｅｓｉｇｎ． Ｎｅｗ Ｙｏｒｋ， ＵＳＡ， １９９０： ７６⁃８３． ［２２］ＬＯＨＮＩＮＧＥＲ Ｈ． ＩＮＳＰＥＣＴ， ａ ｐｒｏｇｒａｍ ｓｙｓｔｅｍ ｔｏ ｖｉｓｕａｌｉｚｅ ａｎｄ ｉｎｔｅｒｐｒｅｔ ｃｈｅｍｉｃａｌ ｄａｔａ［Ｊ］． Ｃｈｅｍｏｍｅｔｒｉｃｓ ａｎｄ Ｉｎｔｅｌｌｉ⁃ ｇｅｎｔ Ｌａｂｏｒａｔｏｒｙ Ｓｙｓｔｅｍｓ， １９９４， ２２（１）： １４７⁃１５３． ［２３］ ＷＡＲＤ Ｍ Ｏ． “Ｘｍｄｖｔｏｏｌ” ［ＥＢ／ ＯＬ］． ［２０１２⁃０９⁃２３］． Ｘｍｄｖ Ｕｓｅｒｓ Ｇｒｏｕｐ． ｈｔｔｐ：／ ／ ｄａｖｉｓ．ｗｐｉ．ｅｄｕ／ ｘｍｄｖ ／ ｄａｔａｓｅｔｓ．ｈｔｍｌ． 作者简介： 李杨，女，１９８０ 年生，讲师，博士研 究生，主要研究方向为数据可视化、机 器学习．获云浮市科技进步奖二等奖 １ 项，发明专利授权 １ 项，实用新型专利 １ 项．发表学术论文 ８ 篇． 郝志峰，男，１９６８ 年生，教授，博士 生导师，主要研究方向为机器学习、仿 生算法、生物信息学． 共主持国家自然 自然科学基金、广东省科技攻关项目、 广东省省部产学研项目等省部级以上 项目 ２２ 项．获国家、省部级各类奖项２０ 余项，广东省科技最 ３０４· 谢光强，男，１９７９ 年生，副教授，硕 士生导师，主要研究方向为多智能体、 智能控制．主持省部产学研等科研项目 １１ 项，获得专利和软件著作权 １０ 项，指 导学生获各类国家、省级奖项 ３０ 余项， 发表学术论文 １１ 篇，其中被 ＥＩ 和 ＩＳＴＰ 检索 ４ 篇． · 智 能 系 统 学 报 第 ８ 卷