在可视分析中系统地结合降维投影与聚类方法(Towards a Systematic Combination of Dimension Reduction and Clustering in Visual Analytics)

在高维数据分析中,聚类(Clustering)与降维(Dimension Reduction)都是常用的机器学习方法。前者尝试对数据进行归纳分类,而后者则试图压缩维度并尽可能地保留分布信息。可视分析往往结合两者的优点,以帮助用户更好地挖掘数据隐含的信息。在具体应用中,我们应该如何挑选聚类和降维方法呢?两者的结合都有哪些因素需要考虑,又有哪几种不同的方案呢?这篇发表于IEEE VAST 2017的文章[1] 便系统地探讨了这些问题。

  1. 算法的选择

聚类是一种经典的无监督机器学习方法,其目的是根据相似性对数据进行分组,以便于数据的概括描述。聚类算法可分为硬聚类(Hard Clustering)与软聚类(Soft Clustering),前者有“非此即彼”的组别划分,而后者则给出数据在各个类别下的概率分布。硬聚类中,又可根据类别的层次架构分为层次聚类(Hierarchical Clustering)与划分聚类(Partitional Clustering)。其中前者包含了不同层次的分组信息,更适合于大规模、多粒度的数据聚类分析。

同样是无监督的机器学习方法,降维投影则服务于高维数据的可视化。投影算法可分为线性投影(Linear Projection)与非线性投影(Non-Linear Projection)两种。其中前者依托于高维空间中的低维线性平面,后者则能够表现复杂流形上的数据分布。

不论聚类还是降维,不同的算法适用于不同的数据与分析任务,并不存在唯一的“最优选项”。我们需要结合实际应用需求,选用不同算法。

 

  1. 结合降维与聚类

作者对以往的可视化研究作了调研,并总结出了六种在可视分析系统中结合降维与聚类的方案。

1). 相互独立

即分别对数据进行降维与聚类处理,并在降维投影图上表现聚类信息[2]。分别处理的优势,在于两种算法都能最大程度上优化自身结果,但相对地、也需要付出巨大的运算开销作为代价。同时,聚类信息对投影算法透明,导致投影图上的各个聚类有可能相互混杂、难以分辨。

图1. 聚类与降维相互独立

图1. 聚类与降维相互独立

2). 先作降维,后作聚类

即先对数据作降维处理,然后在低维空间中对数据作聚类[3]。降维使得数据规模减小,能大为降低聚类算法的复杂度。然而,降维过程往往会丢失数据信息,导致低维空间无法准确反映原高维空间的数据关系,而且维度越高、降维可能造成的信息损失也就越大。在高维空间中分离较远的数据,有可能在降维以后被错误归入同一个聚类中,反之亦然。类似的投影误差的存在,使得低维聚类结果变得不可靠。

图2. 先作降维,后作聚类

图2. 先作降维,后作聚类

3). 先作聚类,后作降维

先在高维空间作数据聚类,然后依据聚类结果来引导降维投影[4]。线性判别分析(Linear Discriminant Analysis, LDA)算法便是该思路的一种体现。由于投影算法充分考虑并强调了数据类别,相应的投影图也能够较好地展现聚类信息。然而,也正是由于投影体现了聚类结果,投影信息的正确性会受到聚类算法质量的影响。

图3. 先作聚类,后作降维

图3. 先作聚类,后作降维

4). 同时进行聚类与降维

通过同一种算法、同时达到聚类和降维的目的。相应的例子,如维度与样本空间的双聚类(Bi-Clustering)[5]、自组织图(Self-Organizing Map, SOM)等等,能够通过较低的运算成本得到经过聚类的低维数据表示。然而,由于聚类与降维算法相互影响,其结果可能不如单独算法来得准确。而考虑维度的聚类,也不一定适用于所有数据和分析任务。此外,各个聚类可能有不同的维度特征,往往难以用同一个降维投影图表现。

图4. 同时进行聚类与降维

图4. 同时进行聚类与降维

5). 全局降维,局部聚类

通过降维决定数据的全局分布,并利用聚类来进行局部的数据调整[6]。该思路可用于数据的快速降维:即先对数据进行区块划分、并提取各区块的代表性样本,对样本进行快速的降维布局后,在其邻域填充局部的数据。

图5. 全局降维,局部聚类

图5. 全局降维,局部聚类

6). 降维与聚类的迭代调整

在降维投影与聚类算法之间反复、并迭代地进行调整[7]。在这个框架下,聚类与降维都是独立进行的,其结果会相互影响。通过迭代调整两种算法的结果,能够渐渐达到收敛。这一思路的好处是保证了两种算法的独立性和算法质量,但运算成本也相对较大。

图6. 降维与聚类的迭代调整

图6. 降维与聚类的迭代调整

 

  1. 可视化设计

除了结合聚类与降维的框架,文章中还探讨了相应的可视化设计,包括视觉映射与交互设计。

1). 视觉映射

表现降维投影的方法包括有散点图、点边图、凸包等等。其中最常见的降维投影图当属各类二维或三维的散点图。表现聚类的方法同样有很多,例如通过距离表现分组关系的散点图、通过连边表现分组的点边图、通过凸包轮廓表现分组的各类集合可视化方法(如Line Set、Bubble Set、GMap)等等[8]。

2). 交互设计

具体的交互方式可分为两类:基于参数的交互,以及基于视图对象的交互。

其中前者将算法与可视化的各类参数暴露给用户,如投影图中各个维度的权重、聚类算法中的聚类个数等等,允许用户通过调参来优化计算与显示。但参数交互需要用户对于参数有较好的理解,而且用户往往难以预期参数变动所带来的影响,容易陷入枯燥
单调的试错过程。

图7. 基于参数的交互[9]

图7. 基于参数的交互[9]

而后一种交互,则允许用户直接操作视图对象,通过交互地调整放置视觉元素来表达自己的认知与需求、从而推动算法的进一步优化。举例来说,用户可以拖动投影图中的散点、来自由调整其中的数据聚类。降维算法根据用户交互的结果来进一步优化、寻求最符合该聚类情况的投影图。

图8. 基于视图对象的交互[3]

图8. 基于视图对象的交互[3]

  1. 总结

对高维数据而言,降维与聚类都是必不可少的处理方法。其中前者提炼了数据特征、促进了数据的可视化展现,后者凝练了数据关系、为大规模数据处理提供了可能。这篇文章对以往的可视化相关工作进行了总结,归纳出六种结合降维投影与聚类算法的思路,并探讨了算法选择、视觉映射、交互设计等设计与决策空间。如何根据数据特点与分析任务、更好地结合降维与聚类,还有待我们进一步探索。

 

参考文献:

[1] Wenskovitch, J., Crandell, I., Ramakrishnan, N., House, L., and North, C. Towards a Systematic Combination of Dimension Reduction and Clustering in Visual Analytics. IEEE transactions on visualization and computer graphics, 2018 (to appear).

[2] Lee, H., Kihm, J., Choo, J., Stasko, J., & Park, H. iVisClustering: An interactive visual document clustering via topic modeling. Computer Graphics Forum. Blackwell Publishing Ltd, 2012, 31(3pt3): 1155-1164.

[3] Wenskovitch J., North C. Observation-level interaction with clustering and dimension reduction algorithms. Proceedings of the 2nd Workshop on Human-In-the-Loop Data Analytics. ACM, 2017: 14.

[4] Liu, S., Bremer, P. T., Jayaraman, J. J., Wang, B., Summa, B., & Pascucci, V. The Grassmannian Atlas: A General Framework for Exploring Linear Projections of High‐Dimensional Data. Computer Graphics Forum. 2016, 35(3): 1-10.

[5] Watanabe, K., Wu, H. Y., Niibe, Y., Takahashi, S., & Fujishiro, I. Biclustering multivariate data for correlated subspace mining. Visualization Symposium (PacificVis), 2015 IEEE Pacific. IEEE, 2015: 287-294.

[6] Pezzotti, N., Höllt, T., Lelieveldt, B., Eisemann, E., & Vilanova, A. Hierarchical stochastic neighbor embedding. Computer Graphics Forum. 2016, 35(3): 21-30.

[7] Niu D, Dy J, Jordan M. Dimensionality reduction for spectral clustering. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics. 2011: 552-560.

[8] Saket, B., Simonetto, P., Kobourov, S., & Börner, K. Node, node-link, and node-link-group diagrams: An evaluation. IEEE transactions on visualization and computer graphics, 2014, 20(12): 2231-2240.

[9] Alsakran, J., Chen, Y., Zhao, Y., Yang, J., & Luo, D. STREAMIT: Dynamic visualization and interactive exploration of text streams. Pacific Visualization Symposium (PacificVis), 2011 IEEE. IEEE, 2011: 131-138.

评论关闭。