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