利用局部主方向实现交互式聚类可视化*

卢 颖，张志豪,2，张军平,2+

1.复旦大学 计算机科学技术学院，上海 200433

2.上海市智能信息处理重点实验室，上海 200433

1 引言

聚类是数据挖掘和机器学习的重要研究方向之一，旨在按照一定的准则将无标签数据划分成不同的类或簇。在处理高维数据聚类时，常将数据映射到低维空间，再通过可视分析来完成聚类。然而，如果可分性不好，或数据本身有重叠问题时，单纯依靠聚类算法不能对数据形成好的分析结果。

因此，人们期望结合机器学习和可视化以及人机交互的优点，提出一种可以辅助聚类分析的方法。具体来说，本文提出了一个用于聚类分析的可视化交互系统。首先通过维数约简的方法将数据点降到二维进行可视化，然后计算出感兴趣区域内投影点的主方向，再通过拉伸主方向和其垂直方向上的数据点距离与数据进行交互，减少投影点的堆叠现象，改善聚类分析的效果。

本文的主要贡献包括：

（1）提出了一个用于聚类分析的可视化交互系统。系统利用维数约简的方法将数据投影到二维平面可视化，让用户与数据自由地交互，进行聚类分析。

（2）创新性地利用局部主方向的方法指导聚类。本文提出的“局部主方向+交互”的聚类方法，在可视化领域是一种全新的方法，其充分利用了交互性的优势，提升用户在聚类问题中的参与度；同时该方法又结合了机器学习领域中局部主方向对数据方向性的直观反映，增强了聚类分析的效果。用户可以先查看所选投影点主方向及其垂直方向上的频数直方图，再调节主方向和垂直方向上的比例参数，对投影点之间的距离在两个方向上进行缩放，使得投影点沿着主方向和垂直方向移动，减少重叠现象，增加数据的可分性，达到更好的可视化聚类效果。

（3）通过实验的方法，综合评估讨论了局部主方向方法对交互式可视化聚类分析的影响和有效性。该方法可以有效地改善投影点的可分性，在实现相似聚类效果的同时，减少降维算法的迭代次数，提升聚类分析效率。

（4）使用用户调研的方法，采访记录用户的使用体验，探讨整个交互式可视化系统和局部主方向方法对聚类分析的帮助。结果表明，基于局部主方向的交互式可视分析方法是行之有效的。

2 相关工作介绍

本章将简要介绍聚类算法和减轻高维数据低维投影点重叠的研究。

粗略来讲，聚类算法可划分为5类[1]。

第一类是基于划分的聚类算法，如K-均值（K-means）算法和CLARANS（clustering algorithm based on randomized search）算法[2]等。这类算法旨在将数据点分成若干个小团，每个小团代表一个类，通常假设数据服从某个分布。

第二类是基于层次的聚类算法，典型的层次聚类算法有BIRCH（balanced iterative reducing and clustering using hierarchies）算法[3]和 CURE（clustering using representatives）算法[4]等。这类算法将给定的数据集分解成若干层次，直至满足条件为止。其主要缺点是一旦进行层次分离或合并操作，这一操作将无法撤销。

第三类是基于密度的聚类算法，如DBSCAN（density-based spatial clustering of applications with noise）算法[5]和OPTICS（ordering point to identify the cluster structure）算法[6]等。这类算法能发现离群点和任意形状的簇。

第四类是基于网格的聚类算法，典型的算法有Wave-Cluster算法[7]和 STING（statistical information grid-based method）算法[8]。这类算法因为聚类过程不依赖于具体的数据点，网格的数量又通常远小于数据点数，一般运行速度较快。但是数据分布不规则时，这类算法效果不是很好。

第五类是基于模型的聚类算法，如期望最大化（expectation maximization）算法[9]和自组织映射（selforganizing maps，SOM）算法[10]等。这类算法假设数据由若干潜在的概率分布组合而成，通过不断优化模型让模型和真实的数据分布相符。模型既可以是统计模型，也可以是神经网络。

尽管聚类算法在很多方面都取得了好的效果，但在处理高维数据时受维数灾难问题影响，往往难以获得直观且好的聚类效果。一种策略是通过维数约简投影到低维，通过可视化由人来进行后期评估。其原因是，按格式塔理论[11]，人的视觉系统具有很强的聚类能力，可以将相似的目标自动聚成团。然而，可视分析的难易度受数据点投影的重叠程度影响。如果聚类算法不能得到好的可分性，数据则有可能在低维产生混叠，导致随后的分析变得困难。

为了减少数据点重叠给后期分析带来的困难，研究者做了大量相关研究，这些研究可划分成4类。

第一类工作是通过增加视觉通道来改善视觉效果，比如为散点图的数据点选择不同的尺寸、透明度、形状和布局等。Woodruff等人[12]通过绘制尺寸不同的投影点来增强可视化的视觉效果。Dang等人[13]则是通过改变数据点的布局来解决二维平面上的重叠问题。这类做法虽然直观和简单，但增加的视觉编码可能会给用户造成视觉假象，影响其对数据属性的理解。

第二类工作的主要思想是对投影点进行密度估计，计算密度场，建立颜色和密度之间的映射关系。Bachthaler等人[14]提出了一个严格、精确、通用的数学模型来创建连续的散点图。但是在同一视图内对多个密度场进行颜色编码对用户具有一定的误导性。

第三类工作试图将高密度区域的投影点移动到其他空间较大的区域，以此缓解投影点重叠的问题。基于这一想法，Janetzko等人[15]提出可以用椭球像素分布改变原始投影点的分布，减少投影点的重叠。但这种可视化方式会改变低维空间中投影点的分布情况和拓扑结构，使得用户无法从低维空间中获得高维数据的真实情况。

第四类工作是借助诸如放缩（zoom）、鱼眼（fisheye）、上下文聚焦（focus+context）等交互的方法探索重叠的投影点。这类典型的工作有Yuan等人[16]提出的交互探索分析高维数据子空间的方法。Chen等人[17]综合运用了上述4种交互技巧，提出了一种基于多类蓝噪声采样[18]的方法，在尽量保留数据点的分布和相对密度的同时，解决重叠问题。

数据投影点的重叠使得聚类的边界变得模糊，容易困扰甚至误导用户，并使其最终做出错误的判断。而可视分析中的交互技术赋予了用户与投影点交互的能力，让用户直接参与到聚类的探索过程中，对整个聚类过程有较好的掌控。受文献[19]的启发，本文选取局部主方向作为提示信息给用户，帮助其进行交互探索。局部主方向作为数据点的局部朝向，可以编码为一个新的可视通道，从而帮助用户区分不同类别。鉴于此，本文提出了一种基于局部主方向的交互式可视聚类分析方法。

3 基于局部主方向的交互式聚类可视化

本章分五部分来介绍基于局部主方向的交互式聚类可视化方法。

3.1 可视分析方法

用户利用整个系统进行聚类分析的过程如下：

如算法1所示，用户首先选择一种降维方法得到数据集的初始可视化效果。降维方法的选取依赖于先验知识或是多次对比尝试。

算法1初始可视化算法

输入：数据集dataset，降维方法f。

输出：初始可视化结果，数据点平面坐标result。

在初始可视化效果基础上，用户选取感兴趣的区域（如投影密度较大的区域）进行进一步探索（见算法2）。

算法2兴趣区探索

输入：兴趣区数据点平面坐标data，主方向上直方图组数b1，主方向垂直方向上直方图组数b2，主方向上缩放比例k1，主方向垂直方向上缩放比例k2。

探索过程中，用户通过查看该区域主方向及其垂直方向，以及两个方向上的频数直方图，从直观上了解区域内投影点的分布情况。在此基础上，用户可以缩放主方向及其垂直方向上的点点距离，减少数据点的重叠，便于聚类分析。

用户还可以对不同的类进行着色，增强视觉效果。为了避免距离缩放导致的数据点重合问题和非选区内数据点干扰缩放效果问题，探索过程中用户可以隐藏选区外的数据点，获得更好的用户体验。

3.2 友好的交互界面

如图1所示，系统主要分为三部分：信息栏、可视化探索区域、主方向参数栏。为了让用户专注于数据探索和聚类分析，可视化探索区域的面积较大，且处于视觉聚焦的中间位置。

（1）信息栏。如图2所示，信息栏中包含的信息有数据集、降维方法、降维方法中所用距离度量信息。用户可以导入不同的数据集进行探索。由于数据集的性质各不相同，用户需要选择合适的降维方法和距离度量才能获得一个比较好的初始可视化效果。除此之外，信息栏还提供当前用户已经标注的类别标记信息。为了防止误操作，提供删除标记功能。

（2）可视化探索区域。图3中的可视化探索区域主要分为两部分：数据显示区域和辅助按钮区域。

在数据显示区域内，用户可以通过点击数据点与数据交互，查看高维空间中的原始信息。对于图像类数据（如MNIST），提示框内会显示原始的图像；对于数值类型的数据，提示框内则显示各个维度上的数值信息。

Fig.1 User interface of system图1 系统界面

Fig.2 Information column图2 信息栏

Fig.3 Visual exploration area图3 可视化探索区域

利用辅助按钮区域的按钮，用户可以和数据进行更多的交互操作。用户可以选择查看或隐藏数据的原始标签。系统为用户提供多边形笔刷来选中感兴趣的区域。用户还可以隐藏未选中的数据点，便于探索。对于选区内的数据点，用户可以标注成一个类，也可以利用主方向方法进一步探索。方便起见，系统提供了一键复位的按钮，可以让用户将所有数据点放回原位。

（3）主方向参数栏。图4中右侧的主方向参数栏包含与主方向方法相关的一些辅助按钮和信息。在可视化探索区域确定选区后，用户可以选择显示或是隐藏该区域内数据的主方向和垂直方向，两者分别用红色箭头和蓝色箭头表示。如果没有进行区域选取操作，则默认计算所有数据点的主方向。在查看主方向的同时，用户可以通过两个方向上的频数直方图来获得数据分布信息，并且可以通过调节频数直方图的组数来获得更好的分析体验。此外，用户可以调节主方向及其垂直方向上的缩放比例，令选区内数据点沿着两个方向移动，减少数据点的重叠，获得更好的聚类效果。

Fig.4 Selected data and corresponding principal direction column图4 选中数据区域和对应的主方向栏

3.3 降维方法的选择

在整个系统的使用过程中，用户首先需要选择一种降维方法得到较好的初始可视化效果。

降维方法分为线性降维方法和非线性降维方法。线性降维方法如主成分分析（principal component analysis，PCA）[20]、多维标度分析（multidimensionalscaling，MDS）[21]等；非线性降维方法包括t-SNE（t-distributed stochastic neighbor embedding）[22]、LLE（local linear embedding）[23]等。线性降维方法的降维结果通常是原本维度的线性组合，而非线性降维方法的结果可能难以解释。但在聚类分析中，并不关心降维结果的实际意义，只是关心数据在约简后维度上的可分性和离群点的保留情况。

对于同一数据集，不同降维方法产生的可视化效果不同，比如在MNIST[24]数据集上，t-SNE[22]的可视化效果比MDS[25]的效果好。同样的降维方法，在不同的数据集上效果也各不相同。与MNIST[24]数据集上相反，在UCI的wine数据集[25]上，MDS[21]方法可以获得比较好的可视化效果，而t-SNE[22]的效果却并不理想。

基于此，系统提供了多种降维方法供用户选择，以减少单一降维方法可能导致的初始可视化结果不够理想的问题。

3.4 主方向的意义和计算

3.4.1 主方向

在二维平面上，如果样本点在某个方向上的投影的方差最大，则称该方向为主方向。从技术上来说，计算主方向等价于对二维平面上点坐标进行主成分分析，找到最大化投影点方差的方向。

记原坐标系为x-y坐标系，记以主方向与其垂直方向为正交基的坐标系为xmd-ymd坐标系，对坐标系x-y中的样本X=(x1,x2,…,xn)∈ℝ2×n，经变换后得到在xmd-ymd坐标系下的样本：

其中，W∈ℝ2×2为变换矩阵；Z∈ℝ2×n是样本在xmdymd坐标系下的表达。

坐标变换后的样本点的方差为要使方差最大化，也即：

求解W的过程也就是进行主成分分析的过程（见算法3）。

算法3获取主方向和垂直方向

输入：数据D={d1,d2,…,dn}。

输出：主方向md及其垂直方向mdv。

v为特征值和特征向量*/

显然，在主方向上所有数据点满足最近重构性和最大可分性，相比其他方向，在主方向上样本点的可分性比较好。

3.4.2 拉伸变换

因为主方向具有最大可分性，在该方向上数据点的投影能够尽可能地分开，所以令初始数据点沿着主方向进行变换可以减少数据点的重叠，增加视觉上的可分性。如图5所示，对主方向和其垂直方向上单位长度大小进行变换（见算法4），图中红色的方向为主方向，蓝色的方向为垂直方向，步骤②中主方向上缩放比例为229%，垂直方向上为443%。可以在保持选区内数据点结构的同时，减少数据点的堆叠现象，使数据变得可分。

Fig.5 Stretching demo along principal direction图5 沿主方向拉伸的示意图

算法4收缩拉伸点点距离

输入：数据D={(x1,y1),(x2,y2),…,(xn,yn)}，主方向上拉伸倍数k1，主方向垂直方向上拉伸倍数k2，主方向md，主方向垂直方向mdv。

输出：变换后数据坐标D′={(x1′,y1′),(x2′,y2′),…,(xn′,yn′)}。

如图6所示，记原始坐标系为x-y坐标系，以主方向与其垂直方向为正交基的坐标系为xmd-ymd坐标系。在x-y坐标系下，原点为O，对点P(x,y)，记OP=r，OP与x轴的夹角为α，显然有：

点P(x,y)在xmd-ymd坐标系下的坐标P(xmd,ymd)：

设拉伸变换Sk1,k2(P(x,y))表示点P(x,y)在xmd-ymd坐标系下，沿主方向xmd扩大k1倍，沿垂直方向ymd扩大k2倍，也即变换后的点P′(x′,y′)=Sk1,k2(P(x,y))在xmd-ymd坐标系下的坐标为P′(k1xmd,k2ymd)，则点P′在x-y坐标系下的坐标P′(x′,y′)：

Fig.6 Stretching transformation图6 拉伸变换

3.5 频数直方图的使用

频数直方图可以反映主方向和其垂直方向上数据点的分布情况。通过频数直方图，用户可以直观地感受到数据的一些内在信息，从而更好地进行聚类分析。

如图7所示，右侧的主方向栏中的主方向频数直方图中有两个峰值，这说明主方向上有两块区域数据点比较密集，可能存在两个类；左侧的数据点的颜色标签对应了数据的类别，可以看出大致有红蓝两类，与频数直方图反应出的数据信息相一致。

Fig.7 Selected data and corresponding principal direction histogram and tangent direction histogram图7 选中区域数据点的主方向频数直方图和垂直方向频数直方图

图8能够反映出直方图组数的选取对判断数据分布情况的影响。图8是图7中数据点在主方向上的频数直方图。对比组数k=10时得到的直方图和组数k=20时得到的直方图，可知组数k=20时的直方图中的双峰更为明显；而当k=100时，由于分组过多，直方图上更像是有3个类。如果直方图的组数k选取不当，偏大或者偏小，都不能达到较好的辅助数据分析的目的。但是直方图组数的选取并没有一个通用的标准，需要根据具体情况、具体数据来决定。因此系统中设置了可以更改组数的滑动条，令用户能够根据实际情况对直方图的组数进行调整，获得较好的效果。

4 实验与结果

4.1 人工合成数据集

第一组实验采用了一个人工合成的数据集。该数据集共有492个数据点，7个分类，每个数据点有4个维度和1个标签。数据集内包含了3组高维的平行线和一些随机噪声点。

在降维方法的选取上，分别选择了MDS[21]方法和t-SNE[22]方法来进行实验。

Fig.8 Different bin numbers cause different visual effects图8 不同组数对频数直方图效果的影响

使用了MDS降维后得到的数据点如图9所示，对中间的一块直线区域进行探索。通过拉伸垂直方向的点点距离，可以清楚地看出所选区域内数据点的可分性有了显著的提升，原本堆叠在一起的数据点大致分成了两条直线，还有一些噪声点。观察这次实验中主方向和垂直方向上的频数直方图，可以发现主方向的频数直方图上有4个峰值，垂直方向的频数直方图上仅有一个峰值。结合实际的数据标签来看，频数直方图只能从某种程度上反映出有限的数据信息，并不能完全依赖于直方图进行聚类，沿着主方向和垂直方向进行拉伸的操作更为有效。

使用了t-SNE降维后得到的数据点如图10所示，对其中的一块区域进行探索。从原始标记中可以看出，选中区域内除了噪声（粉色）之外有两个类。但是经过t-SNE的降维，噪声点和数据点混合均匀，甚至两个类的数据点均匀混合，频数直方图上的信息用途有限。利用拉伸方法进行调节后，可视化效果并没有得到很明显的改善。这说明了选取合适降维方法的重要性，也说明了提供若干降维方法供用户选择的合理性。

4.2 MNIST数据集

第二组实验采用了MNIST[24]手写数字数据集。由于原始数据集过大，考虑到实验的需求，本文选取一个MNIST的子集来近似模拟在MNIST全局上的聚类过程，其中包含了1 797个数据点。使用t-SNE来可视化MNIST数据集可以得到非常好的可视化效果，但是由于需要迭代到收敛，t-SNE的运行速度较慢。针对t-SNE的运行速度较慢这一问题，有很多加速t-SNE的方法，如Barnes-Hut-SNE[26]和LargeVis[27]等。但是这些优化都是从算法层面进行时间开销的优化，从而提升收敛速度。收敛之前计算出的中间信息是否有用？是否可能在收敛之前提前结束迭代，通过可视化的交互探索手段，达到同样的聚类效果？实验证明，减少40%的迭代次数，再通过沿主方向调整的方法，也可以得到较好的聚类结果。

Fig.9 Choosing MDS as initial dimension reduction method on artificial dataset图9 使用MDS作为初始降维方法对人工合成数据集进行探索

Fig.10 Choosing t-SNE as initial dimension reduction method on artificial dataset图10 使用t-SNE作为初始降维方法对人工合成数据集进行探索

图11是在MNIST数据集上t-SNE迭代到收敛所得到的效果图。经过实验证明，这个过程大约需要迭代140次。以下实验指出，只需要迭代80次，再加上适当的主方向拉伸操作，就能够实现比较好的聚类效果。

首先让t-SNE迭代80次得到一个初步的可视化结果。显然，此时得到的图12可分性相比图11较为糟糕，只能在右图中找到8个类。通过对两块数据密集的区域（4号区域和7号区域）利用主方向进行探索（见图13和图14），可以将两个看似重叠的类分离开来，找到10个类。

Fig.11 Visualization result of applying t-SNE to MNIST dataset until convergence图11 MNIST数据集利用t-SNE迭代到收敛的可视化结果

4.3 分析与讨论

本文提出的交互式聚类方法的有效性主要体现在两点：一是使用维数约简对数据进行可视分析的有效性；二是利用交互式方法减轻投影重叠，提升聚类分析效率的有效性。

高维数据因为维数过多，各维度之间通常存在冗余，且数据点在高维空间内过于稀疏，难以挖掘数据的本质信息和结构。对高维数据进行维数约简，不仅可以压缩数据，去除数据中噪声的影响，同时也可以尽可能地在低维空间保留数据在高维空间的一些结构和统计特性，从而比较好地提升数据的可分性，使得聚类分析能够取得比较好的效果。

Fig.12 Visualization result of applying t-SNE to MNIST dataset(80 iteration times)图12MNIST数据集用t-SNE迭代了80次后的可视化结果

Fig.13 ExploringArea 4 in Fig.12 with principal direction图13 利用主方向对图12中的区域4进行探索

Fig.14 ExploringArea 7 in Fig.12 with principal direction图14 利用主方向对图12中的区域7进行探索

采用可视化的方法对维数约简后的数据在低维空间中进行展示，能够让用户对数据的结构和分布有更为直观的理解。用户对数据的理解在交互式的探索中有着至关重要的作用。

投影重叠的问题一方面来自于选取的降维方法不当，低维空间的数据点不能有效地保持高维空间数据的结构性质和分布规律；另一方面来自于低维空间的点点距离不是均匀分布的，为了在有限的空间内可视化所有数据点，并且保持相对距离与高维空间相符，距离较近的数据点之间会产生视觉上的重叠，令用户难以观察数据的局部相对距离和局部性质，影响聚类分析的效果。

局部主方向能够反映出局部数据的方向性，由于主方向具有最大可分性，在该方向上数据点的投影能够尽可能地分开。在局部主方向上采用频数直方图来表征数据的分布，能一定程度上体现出数据的总体趋势和统计规律。而采用沿局部主方向改变点点距离的交互手段，数据点移动的过程能够让用户对数据的局部主方向有比较清晰的认识。拉伸点点距离能够调节局部数据点距离之间的差异性，使得原本在视觉上堆叠的数据点被区分开来，令用户对数据的局部结构和性质有比较深刻的了解，从而更好地辅助其进行聚类分析。交互式的探索方法能够提升用户在聚类分析任务中的兴趣和参与度，充分利用视觉系统的聚类能力，提升聚类分析的效率以及聚类分析结果和算法的可解释性。

4.4 局限与不足

本文的交互式聚类方法需要降维方法提供一个初始的可视化效果。图15为在MNIST数据集上使用不同降维方法后的初始可视化效果，降维方法分别 为 Isomap[28]、LLE[23]、Random Projection、Spectral Embedding[29]、LTSA[30]、MDS[21]、t-SNE[22]。不同的降维方法初始可视化效果差异较大，对后续交互式聚类会造成不同的影响。比如随机投影的初始化效果较差，几乎所有的数据点都均匀地混杂在一起，给用户的局部数据点选取和后续的聚类分析都造成了比较大的困难。

5 用户调研

本文采用了用户调研的方法，邀请了11位参与者使用该系统进行聚类分析并进行一定的评估。采用t-SNE算法在MNIST数据集上迭代80次的结果作为初始的可视化效果。参与者们在此之前对该系统没有任何的先验知识。调研设置了3个有具体选项的问题和1次对系统的综合评估采访，询问他们使用该系统进行聚类分析的体验。

当问及系统对用户进行聚类分析时的帮助时，有72.7%（8/11）的调查对象选择了“有帮助”或“很有帮助”，另外3名调查对象则选择了“中立”。3名选择“中立”的参与者表示，他们随意选取了3~5个数据点比较密集的区域，利用主方向的方法进行探索，但并没有发现更多的类别或是有趣的离群点，因而认为该系统的作用比较有限。让觉得系统“有帮助”和“很有帮助”的参与者对频数直方图和拉伸方法的帮助度进行满分为5分的数值评价，频数直方图得分均值为3.250。方差为0.188；拉伸方法得分均值为3.625，方差为0.484（见图16）。由此看来，拉伸方法相对更有效。在采访中，参与者表达出了这样的困惑：一开始先从哪个区域开始探索？探索到什么程度能够中止？当潜在的可探索区域较多时，参与者表示并不是非常愿意对所有的区域进行探索。总之，尽管仍有需要改进之处，大部分参与者们认为该系统对于辅助聚类分析是有效的，并且认可了频数直方图和局部主方向的方法在可视化聚类分析中的重要性。

Fig.15 Initial visualization of MNIST using different dimension reduction methods图15 在MNIST数据集上使用不同降维方法后的初始可视化效果

Fig.16 Comparison between stretching method and histogram method based on mean and standard deviation图16 频数直方图和拉伸方法得分均值和方差比较

6 总结与展望

本文创新性地提出了一种基于局部主方向的交互式可视化聚类方法，帮助用户进行聚类分析任务。同时提出了一个用于聚类分析的可视化交互系统。在系统中利用降维方法将数据投影到二维平面，然后对于用户感兴趣区域内的数据，提供主方向及其垂直方向上的频数直方图，让用户了解数据投影的分布情况。用户可以通过调节主方向和垂直方向上的缩放比例参数，拉伸距离，使得数据点沿着主方向和垂直方向移动，减少数据堆叠的情况，增加数据点的可分性。利用本文系统在人工数据集和真实数据集上进行了多组实验，获得了较好的效果。并且通过用户调研，证明了本文方法的有效性。

本文方法还存在一些局限性，这也是下一步工作中需要考虑解决的问题。首先是初始可视化结果对降维方法的依赖。一个不好的降维方法会带来比较糟糕的用户体验和聚类结果，增加用户进行聚类分析的难度。其次，数据探索区域的选取依靠用户的先验知识或是兴趣爱好，没有一个统一的标准；缩放的比例也没有统一的大小，也需要依靠用户的先验知识或是多次尝试。再者，根据用户的反馈情况，系统缺乏对用户的引导，需要添加对用户的启发性指导，帮助用户开始和停止探索。

:

[1]Fahad A,Alshatri N,Tari Z,et al.A survey of clustering algorithms for big data:taxonomy and empirical analysis[J].IEEE Transactions on Emerging Topics in Computing,2014,2(3):267-279.

[2]Ng R T,Han Jiawei.CLARANS:a method for clustering objects for spatial data mining[J].IEEE Transactions on Knowledge and Data Engineering,2002,14(5):1003-1016.

[3]Zhang Tian,Ramakrishnan R,Livny M.BIRCH:an efficient data clustering method for very large databases[C]//Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data,Montreal,Jun 4-6,1996.New York:ACM,1996:103-114.

[4]Guha S,Rastogi R,Shim K.CURE:an efficient clustering algorithm for large databases[C]//Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data,Seattle,Jun 2-4,1998.New York:ACM,1998:73-84.

[5]Ester M,Kriegel H P,Sander J,et al.A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining,Portland,Aug 2-4,1996.Menlo Park:AAAI,1996:226-231.

[6]Ankerst M,Breunig M M,Kriegel H P,et al.OPTICS:ordering points to identify the clustering structure[C]//Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data,Philadelphia,Jun 1-3,1999.New York:ACM,1999:49-60.

[7]Sheikholeslami G,Chatterjee S,Zhang Aidong.WaveCluster:a multi-resolution clustering approach for very large spatial databases[C]//Proceedings of the 24th International Conference on Very Large Data Bases,New York,Aug 24-27,1998.San Mateo:Morgan Kaufmann,1998:428-439.

[8]Wang Wei,Yang Jiong,Muntz R R.STING:a statistical information grid approach to spatial data mining[C]//Proceedings of the 23rd International Conference on Very Large Data Bases,Athens,Aug 25-29,1997.San Mateo:Morgan Kaufmann,1997:186-195.

[9]Dempster A P,Laird N M,Rubin D B.Maximum likelihood from incomplete data via the EM algorithm[J].Journal of the Royal Statistical Society:Series B Methodological,1977,39(1):1-38.

[10]Kohonen T.The self-organizing map[J].Neurocomputing,1998,21(1/3):1-6.

[11]Arnheim R.The Gestalt theory of expression[J].Psychological Review,1949,56(3):156-171.

[12]Woodruff A,Landay J A,Stonebraker M.Constant density visualizations of non-uniform distributions of data[C]//Proceedings of the 11th Annual ACM Symposium on User Interface Software and Technology,San Francisco,Nov 1-4,1998.New York:ACM,1998:19-28.

[13]Dang T N,Wilkinson L,Anand A.Stacking graphic elements to avoid over-plotting[J].IEEE Transactions on Visualization and Computer Graphics,2010,16(6):1044-1052.

[14]Bachthaler S,Weiskopf D.Continuous scatterplots[J].IEEE Transactions on Visualization and Computer Graphics,2008,14(6):1428-1435.

[15]Janetzko H,Hao M C,Mittelstädt S,et al.Enhancing scatter plots using ellipsoid pixel placement and shading[C]//Proceedings of the 46th Hawaii International Conference on System Sciences,Wailea,Jan 7-10,2013.Washington:IEEE Computer Society,2013:1522-1531.

[16]Yuan Xiaoru,Ren Donghao,Wang Zuchao,et al.Dimension projection matrix/tree:interactive subspace visual exploration and analysis of high dimensional data[J].IEEE Transactions on Visualization and Computer Graphics,2013,19(12):2625-2633.

[17]Chen Haidong,Chen Wei,Mei Honghui,et al.Visual abstraction and exploration of multi-class scatterplots[J].IEEE Transactions on Visualization and Computer Graphics,2014,20(12):1683-1692.

[18]Wei Liyi.Multi-class blue noise sampling[J].ACM Transactions on Graphics,2010,29(4):79.

[19]Zhang Junping,Wang Xiaodan,Krüger U,et al.Principal curve algorithms for partitioning high-dimensional data spaces[J].IEEE Transactions on Neural Networks,2011,22(3):367-380.

[20]Jolliffe I.Principal component analysis[M].New York:John Wiley&Sons,Inc,2002.

[21]Brandes U,Pich C.Eigensolver methods for progressive multidimensional scaling of large data[C]//LNCS 4372:Proceedings of the 14th International Symposium on Graph Drawing,Karlsruhe,Sep 18-20,2006.Berlin,Heidelberg:Springer,2006:42-53.

[22]van der Maaten L,Hinton G.Visualizing data using t-SNE[J].Journal of Machine Learning Research,2008,9(11):2579-2605.

[23]Roweis S T,Saul L K.Nonlinear dimensionality reduction by locally linear embedding[J].Science,2000,290(5500):2323-2326.

[24]LeCun Y,Cortes C,Burges C J C.The MNIST database of handwritten digits[EB/OL].AT&T Labs.(2010-02)[2017-03-31].http://yann.lecun.com/exdb/mnist.

[25]Forina M,Aeberhard S,Leardi R.Wine data set[EB/OL].(1991-07-01)[2017-03-31].http://archive.ics.uci.edu/ml/datasets/Wine.

[26]van der Maaten L.Accelerating t-SNE using tree-based algorithms[J].Journal of Machine Learning Research,2014,15(1):3221-3245.

[27]Tang Jian,Liu Jingzhou,Zhang Ming,et al.Visualizing largescale and high-dimensional data[C]//Proceedings of the 25th International Conference on World Wide Web,Montreal,Apr 11-15,2016.New York:ACM,2016:287-297.

[28]Tenenbaum J B,de Silva V,Langford J C.A global geometric framework for nonlinear dimensionality reduction[J].Science,2000,290(5500):2319-2323.

[29]Belkin M,Niyogi P.Laplacian eigenmaps for dimensionality reduction and data representation[J].Neural Computation,2003,15(6):1373-1396.

[30]Zhang Zhenyue,Zha Hongyuan.Principal manifolds and nonlinear dimensionality reduction via tangent space alignment[J].SIAM Journal on Scientific Computing,2004,26(1):313-338.