6 谱聚类

顶点之间的相似信息可以自然地表示为一个矩阵，向量模型可以解释成为一个图。谱聚类涉及在图中寻找一个切割来产生好的聚类。如图4和5。

图4：一个多路分割示意图

图5：二分图分割。虚线表示一个分割，产生一个同时对term-document的行和列联合聚类。

问题是如何在图中寻找到好的分割？这就出现了大量的准则函数，谱聚类算法需要最优化它们来得到好的分割。其中最常用的包括多路ratio cut，normalized cut（NCut）和max-min cut。这些不同目标函数的求解可能会用到特征值（特征向量）或者奇异值（奇异向量）。

对于ratio cut，normalized cut（NCut）和max-min cut，如果集群是很好的分离,所有三个不同的分割都会给出一个非常相似的和准确的结果；当集群是略微分开的，NCut和max-min cut会给出更好的结果；当集群明显地重叠，max-min cut往往给更紧凑平衡集群[7]。

7 降维

尽管预处理可以实现向量空间的大小显著减少,但后检索应用程序要求更高的效率。因此我们需要更好的降维算法。这部分我们介绍三种最常用的降维技术，它们不仅可以显著地减少文档向量的大小，还能提高聚类的准确率。实际上这些方法本身也可以看作是聚类方法。

7.1 主成分分析（PCA）

      PCA[8]是一个著名的维度降低算法，离散K-L装换是它的理论基础。

主成分分析有两个重要的属性,这些属性使它适合聚类:近似和可区别性。近似是说PCA在降维的同时，引进了一个可控制的误差使得近似最优化。另外实验表明PCA使得相似的文档更加相似，不相似的文档更加不相似，增加了可区分性这使得聚类更加容易。

当然PCA也有一系列的问题。（1）近似得到结果中包含负值,所以降维的空间不能直接解释为一个聚类，但是可以在降维的空间上执行传统的聚类方法(如k-means)产生最后的聚类结果,而且它实际上生产聚类比直接在原来的向量空间上进行更准确；（2）另一个问题是,主成分是正交的。这是对于文本数据是有问题的,如文档可能跨越多个主题,所以在这种情况潜在的语义变量将不会是正交的；（3）计算协方差矩阵的特征值和特征向量时间花销是很大的，而且不能迭代的进行求解，使得奇异值分解的求解不是一个优化过程也无法产生一个中间值。

7.2 奇异值分解（SVD）  

   可以看出SVD与PCA相似[9]，只是在计算特征空间上略有区别，所以它和PCA有着共同的优点和问题。

7.3 非负矩阵分解（NMF）

   非负矩阵分解(NMF)[10],原本为计算机视觉应用,已经被有效地用于文档聚类[2]。NMF产生的近似矩阵只包含非负的因素,这意味着可以从降维的空间直接得到一个可解释的聚类而不需要进一步的后处理。

和上述两种降维方法相比，NMF不需要派生的潜在语义空间是正交的，并且保证每个文档在所有潜在语义方向上都取非负值。并且NMF有以下优点：

（1）当聚类之间存在重叠，NMF 仍然可以为每个聚类找到潜在的语义方向，而由奇异值分解的正交要求或特征向量计算使得派生潜在语义的方向，不太可能对应于每个聚类。

（2）利用NMF，一个文档是基础潜在语义的加法的组合，使得在文本域中更有意义。

（3）每个文档的聚类成员可以直接从 NMF的结果中得到，而从谱聚类所得的潜在语义空间对每个数据点的分布不提供直接指示，因此，必须利用传统的数据聚类 K-均值等方法来找到最终的文档聚类结果。

8 总结

文档聚类算法有多种多样，每一种算法都有自己的优缺点，并不能说哪一种算法是最好的，哪一种算法是最坏的，根据不同的应用选择适合的算法才是正确的。比如小规模的聚类，由于它的简单易于实现等特点选择k-means会更好，又比如对于大规模的数据聚类，先对元数据进行降维处理会取得更好的效率和准确率。

参考文献：

[1] Andrews, Nicholas O. and Fox, Edward A. Recent Developments inDocument Clustering.Technical Report TR-07-35, Computer Science, VirginiaTech, 2007.

[2] Wei Xu, Xin Liu, YihongGong.Document Clustering Based On Non-negative Matrix factorization .In Proceedings of the 26th annualinternational ACM SIGIR conference on Research and development in informaionretrieval, 2003, pp. 267-273.

[3] Marques JP,Written; Wu YF, Trans. Pattern Recognition Concepts, Methods and Applications.2nd ed., Beijing: Tsinghua University Press, 2002. 51−74 (in Chinese).

[4] Fred ALN, LeitãoJMN. Partitional vs hierarchical clustering using a minimum grammar complexityapproach. In: Proc. of the SSPR&SPR 2000. LNCS 1876, 2000, pp. 193−202.

[5] Inderjit S.Dhillon and Dharmendra S. Modha. Concept decompositions for large sparse textdata using clustering. Mach. Learn., 2001, 42(1-2):143–175.

[6] R. Neal and G.Hinton. A view of the em algorithm that justifies incremental, sparse, andother variants.In M. I. Jordan, editor, Learning in Graphical Models. Kluwer,1998.

[7] Chris H. Q.Ding, Xiaofeng He, Hongyuan Zha, Ming Gu, and Horst D. Simon. A min-max cutalgorithm for graph partitioning and data clustering. In ICDM ’01: Proceedingsof the 2001 IEEE International Conference on Data Mining, pages 107–114,Washington, DC, USA, 2001. IEEE Computer Society.

[8] M. Turk and A.Pentland. Eigenfaces for recognition. Journal of Cognitive Neuroscience, vol.26, 2004, pp. 71-86.

[9]Wall, Michael E., Andreas Rechtsteiner, LuisM. Rocha.  Singular value decompositionand principal component analysis. In D.P. Berrar, W. Dubitzky, M. Granzow. APractical Approach to Microarray Data Analysis. Norwell, MA: Kluwer. 2003, pp.91–109.

[10] Daniel D. Leeand Sebastian H. Seung. Learning the parts of objects by non-negative matrixfactorization. Nature, 401(6755):788–791, October 1999.

[11] Dee, D.D. &Seung, H.S.. Algorithms for Non-negative Matrix Factorization. Advances inNeural Information Processing, 13, 2001.

[12] Kim, H. &Park, K.. Non-negative Matrix Factorization Based on Alternating Non-negativityConstrained Least Squares and Active Set Method. SIAM J. Matrix Anal. Appl.,30(2), 2008, pp.713–730.

[13] Cichocki, A.,Zdunek, R. & Amari, S.. Hierarchical ALS Algorithms for Nonnegative Matrixand 3D Tensor Factorization. Lecture Notes in Computer Science, Springer, 4666,2007, pp.169–176.

[14] Cichocki, A.,Zdunek, R. & Amari, S.. Non-negative Matrix Factorization with Quasi-NewtonOptimization. Lecture Notes in Artificial Intelligence, Springer, 4029, 2006,pp.870–879.

[15] Lin, C.-J..Projected Gradient Methods for Nonnegative Matrix Factorization. NeuralComputation,MIT press, 19, 2007, pp.2756–2779.

[16]Gillis, N.. Nonnegative Matrix Factorization:Complexity, Algorithms and Applications. Université catholique de Louvain, PhDThesis, 2011.

[17] NicolasGillis1an,Francois Glineur. Accelerated Multiplicative Updates and HierarchicalALS Algorithms for Nonnegative Matrix Factorization. Neural Computation,2011.

[18] K. M. Hammouda and M. S. Kamel. Efficient phrase-baseddocument indexing for web document clustering. IEEE Transactions on knowledgeand data engineering, 16(10):1279–1296, 2004.