谱聚类算法及其在图像分割中的应用

的类, 因此图像的分割既具有随机性又具有多尺度特性, 称之为基于谱聚类的图像多尺度随机树分割(multiscale stochastic hierarchical image segmentation by spectral clustering, 简写为MSHISSC).

图三. 基于MSHISSC 与基于Normalized cut 和Min-max cut

的图像分割算法的比较结果

其中第1 列是原始图像, 第2 列是利用MSHISSC 得到的分割结果, 第3 列是利用Normalized cut 到的分割结果，第4 列是利用Min-max cut 得到的分割结果。

4 谱聚类算法中的关键问题和未来的研究方向

尽管谱聚类算法具有坚实的理论基础——谱图理论，并且在实践中也取得了很好的效果，但是它仍然存在一些关键问题：

1．如何构造邻接矩阵w；在谱聚类算法中，边的权值是顶点i与j的相似度sim(i,j)，故表示图的邻接矩阵也是样本空间的相似度矩阵。相似度矩阵的构造依赖于两个样本间相似度的构造。而单纯地依赖人为选择的相似度函数是带有一定的局限性的。我们应该引入相关领域知识，学习构造邻接矩阵。

2．自动地确定聚类的数目：聚类数目的确定对聚类的质量有很大的影响。当聚类数目大于实际聚类数，k-way谱聚类方法的效果差。因此如何自动地确定聚类数目是一个关键的问题，是未来研究的方向。

3．如何解决模糊聚类的问题：尽管在文档聚类中，谱聚类取得了很好的效果。但是在文档聚类中，单个词可能属于多个类，单个文档可能是多主题的文档。这就需要我们用模糊聚类的方法解决。如何确定基于模糊聚类与谱方法的联合：如建立模糊标准的图划分的目标函数等，是我们的研究方向。

4．运用到海量数据中去：当我们用谱聚类，不可避免地要计算矩阵的特征值与特征向量。通常这种计算的代价很大，求解非稀疏矩阵的所有特征向量的标准解法需要O(n3)。同时当应用到海量数据时，相似度矩阵也很大，可能会超出计算机的内存。DhillonE 在研究了谱聚类和核k-means聚类方法的关系后，将谱聚类问题用核k-means算法求解，并且运用到核k-means算法的优化技巧，来解决海量数据的计算。但该方法只用于非二分图的谱聚类方法，对二分图的聚类问题仍然是我们未来的研究方向。

参考文献

[1] 章毓晋. 图像分割. 北京: 科学出版社, 2001

[2] Zhang Y J. A Survey on Evaluation Methods for Image Segmentation. Pattern Recognition, 1996, 29(8): 1335~1346

[3] Hagen L, Kahng A B. New spectra1 methods for ratio cut partitioning and clustering. IEEE Trans. Computer-Aided Design, 1992, 11(9):1074～1085

[4] Shi J, Malik J．Normalized cuts and image segmentation．IEEE Transactions on Pattern Analysis and Machine Intelligence，2000,22(8)：888～ 905

[5] Ng A，Jordan M，Weiss Y．On spectral clustering ：Analysis and an algorithm, Advances in Neural Information Processing Systems 14．MIT Press，2001 [6] Meila M，Shi J．A random walks view of spectra1 segmentation． In: 8th International Workshop on Artificia1 Intelligence and Statistics，2001

[7] Zha H, He X．Ding C，Gu M, Simon H D. Bipartite Graph Partitioning and Data clustering．In：Proc．of ACM 10th Int’l Conf．Information and Knowledge Management(CIKM 2001)，Atlanta，2001．25～ 31

[8] Dhilion I S. Co-clustering documents and words using Bipartite Spectra1 Graph Partitioning．KDD 2001 San Francisco. California, USA

[9] Ding H Q. Unsupervised feature selection via two-way ordering in gene expression analysis． http://bioinformatics.oupJoumals．org/cgi/reprint/19/10/1259 [10] Cu M, Zha H, Ding C, He X, Simon H, Xia J. Spectra1 relaxation models and

structure analysis for K—why graph clustering and bi-clustering． http:// citeseer.st.psu.edu/context/2380189/639394

[11] Dhillon I, Guan Y, Kulis R. A Unified View of Kernel k means, Spectra1 Clustering and Graph Cuts. In ICPR02. 2002．289～292

[12] Damnjanovic Uros , Izquierdo Ebroul. Asymmetric and Normalized Cuts for Image Clustering and Segmentation. Neural Network Applications in Electrical Engineering. Sept. 2006: 5 – 9

[13] O'Callaghan, R.J. Bull, D.R. Combined morphological-spectral unsupervised

image segmentation. Image Processing, IEEE Transactions on Volume 14, Issue 1, Jan. 2005 Page(s):49 - 62

[14] Alzate, C. Suykens, J.A.K. Image Segmentation using a Weighted Kernel PCA

Approach to Spectral Clustering. Computational Intelligence in Image and Signal Processing. April 2007: 208 - 213

[15] 司文武,钱法涛. 一种基于谱聚类的半监督聚类方法. 计算机应用. 25(6),

2005.7: 1347-1349

[16] Kamvar S D, Klein D, Manning C D. Spectra1 Learning．CAI-03，2005 [17] 李小斌,田 铮. 基于谱聚类的图像多尺度随机树分割. 中国科学E辑: 信息

科学. 37 (8), 2007: 1073~1085