第5期 李建元，等：谱图聚类算法研究进展 。411 的应用都是在某种相似性度量假设基础之上进行 图割优化目标的指导下发现簇数是值得思考的： 的，这些算法的成功依赖于度量方式的选择，而已有 5)探讨基于其他矩阵的谱聚类算法.如文中提 的大多数谱聚类算法对于不相关的特征具有较差的 及的模块度矩阵，它与拉氏矩阵的特性相似但又有 鲁棒性].这种情况需要结合先验知识来解决，在 很大区别，该算法在处理真实网络时表现出很好的 许多情况下，某些先验知识是可以获得的，如文献 性能，但是推广其用于谱聚类，依然有许多问题值得 [78]提及的空间一致性先验信息，文献[79]在相似 探讨 性度量时依靠结合知识来减轻不相关特征造成的影 6)如何在构建相似图的过程中进行自动特征 响，文献[77,80]提出了从数据中自动学习的方式 筛选.例如：针对高维数据，L1图的构建可以有效地 来确定恰当的核或者相似性度量方法，文献[77]提 捕捉最稀疏的特征，从而得到非常高的聚类和分类 供了一个基于实例的相似矩阵学习的总体框架，文 准确性[82] 献[78]提出了一种从数据中学习先验知识的密度 7)如何快速解决大规模或超大规模的谱聚类 敏感的半监督聚类算法等，均取得了较好的效果 问题.随着经济和社会的发展，在许多行业中，需要 处理的数据规模与日俱增，虽然现有的研究已经能 5 结论与展望 够解决10万数量级的问题，但是解决更大规模的问 图分割的本质可以归结为矩阵的迹最小化或最 题仍然具有挑战性. 大化问题，而完成该最小化或最大化的任务需要依 8)应用实例化.与各学科或应用领域相结合，通 靠谱聚类算法.在绝大多数情况下，归一化谱聚类的 过改进典型的谱聚类算法切实解决实际问题。例如， 性能超过非归一化谱聚类的性能，所以归一化谱聚 在网络文档分类中，如何恰当地利用全局一致性信 类的应用更为广泛.它之所以吸引了大批研究者，最 息，如何增量地聚类动态更新的博客社区等 主要的原因有3点：1)它具有坚实的理论基础 参考文献： 代数图论；2)对于较复杂的簇结构，它能得到全局 宽松解；3)它能在多项式时间内解决问题.近年来， [1]LLOYD S P.Least squares quantization in PCM[J].IEEE 在与图和网络相关的领域中，个性化的改进算法层 Transactions on Information Theory,1982,28(2):129- 137. 出不穷，在某种程度上，谱聚类已经成为现代最流行 [2]DEMPSTER A P,LAIRD N M,RUBIN D B.Maximum 的聚类算法之一 likelihood from incomplete data via the EM algorithm[J]. 以下提出今后依然需要探讨的几点问题 Joural of the Royal Statistical Society-Series B:Statistical 1)谱聚类的理论解释.例如，在谱聚类中，采用 Methodology,1977,39(1):1-38. 哪些特征向量最好？应该采用多少个特征向量最 [3]NG A Y,JORDAN M I,WEISS Y.On spectral clustering: 好？为什么？采用部分特征向量张成的子空间，保 analysis and an algorithm[C]//PIETTERICH T G,BECK- 留了什么信息？损失了什么信息？ ER S,GHAHRAMANI Z.Advances in Neural Information 2)如何更恰当地构建相似图，相似图构建的好 Processing Systems.Cambridge,USA:MIT Press,2001: 坏决定着谱聚类性能.近来提出的b-匹配图和拟合 849-856. [4]RAHIMI A,RECHT B.Clustering with normalized cuts is 图就是非常有趣和有用的方法，尽管已有的构建方 法已经不少，但关于该问题依然需要推陈出新，最核 clustering with a hyperplane[C]//Statistical Learning in Computer Vision Workshop in ECCV 2004.Prague,Czech 心的一点是如何本质地描述数据之间的关系， Republic,2004:1-12 3)加权方式或者参数选择.虽然构图的同时已 [5]SHI J B,MALIK J.Normalized cuts and image segmenta- 经加权，但也可以考虑重新加权的问题.例如，流形 tion[J].IEEE Transactions on Pattern Analysis and Ma- 学习领域的一个重要概念“局部线性重构”[川就是 chine Intelligence,2000,22(8):888-905. 一种有效的重加权方式.再比如，高斯核参数是谱聚 [6]MALIK J,BELONGIE S,LEUNG T,et al.Contour and 类中的一个非常敏感的参数，该参数选择的恰当与 texture analysis for image segmentation[J].International 否直接影响着聚类的效果，关于自动选取该参数的 Joumal of Computer Vision,2001,43(1):7-27. [7]ZHANG X R,JIAO L C,LIU F.Spectral clustering ensem- 研究是另一个难题： ble applied to SAR image segmentation[J].IEEE Transac- 4)如何将优化目标与簇数估计相结合，已有的绝 tions on Geoscience and Remote Sensing,2008,46(7): 大多数谱算法并不能根据其图割优化目标来决定簇 2126-2136. 数，也就是说在算法运行之前簇数是给定的.然而，在 [8]陶文兵，金海.一种新的基于图谱理论的图像阈值分割 许多应用场合中，事先知道簇数是不现实的，如何在 方法[J].计算机学报，2007,30(1)：110-119