On the Equivalence of Nonnegative Matrix Factorization and K-means - Spectral Clustering
On the Equivalence of Nonnegative Matrix Factorization and K-means - Spectral Clustering
复制标题
DOI：
--
复制
发表时间：
2005-12
期刊：
影响因子：
--
通讯作者：
C. Ding;Xiaofeng He;H. Simon;Rong Jin
中科院分区：
文献类型：
--
作者：
C. Ding;Xiaofeng He;H. Simon;Rong Jin
论非负矩阵因式分解与K均值谱聚类的等价性Chris Ding∗何晓峰何晓峰∗Horst D.Simon∗荣进†2005年12月4日本文系统地分析了与数据聚类有关的非负矩阵因式分解。我们将通常的X=F-GT分解推广到对称的W=HH-T和W=HSH-T分解。我们证明了(1)W=HHTT等价于核K-均值聚类和基于拉普拉斯的谱聚类。(2)X=F G T等价于二部图的行和列的同时聚类。我们强调了正交性在NMF中的重要性和NMF的软聚类性质。这些结果通过对人脸图像和新闻组的实验得到了验证。数据矩阵的标准因式分解使用在主成分分析(PCA)中广泛使用的奇异值分解(SVD)。然而，对于许多数据集，如图像和文本，原始数据矩阵是非负的。像奇异值分解这样的因式分解包含负条目，并且在某些应用中被解释为difficult。相反，非负矩阵分解(NMF)[18，19]将矩阵因子中的条目限制为非负。近些年来，NMF已被证明在环境[25]、化学计量学[29]、模式识别[20]、多媒体[6]、文本挖掘[31，26]和DNA基因表达[3]中有许多有用的应用。这也被推广到经典fi阳离子[27]。一些研究集中于进一步开发NMF计算方法[15，22，26，5，21]。设X=(x1，.。。，xn)∈Rp×n为非负元素的数据矩阵。在图像处理中，每一列xi是像素灰度级的2D阵列。在文本处理中，每一列都是一个文档。NMF将X分解为两个非负矩阵X≈FGT，n×k，其中F=(f1，···，fk)∈Rp×k和G=(g1，···，gk)∈R+.K是预先指定的参数。K是预先指定的参数。NMF可以追溯到20世纪70年代(来自吉恩·戈卢布的交流)，并已被Paatero研究[25，29]。Lee和Seung[18，19]的工作引起了机器学习和数据挖掘领域对NMF的极大关注。然而，这其中似乎存在一些困惑。Lee和Seung强调，NMF因子fk包含原始数据(图像)的连贯部分，例如鼻子或眼睛。后来的实验[16，20]不支持NMF的部分整体解释。事实上，Hoyer[16]和Li等人[20]针对fi提出了Sparsifi阳离子方案来实现部分整体图像。加州大学伯克利分校伯克利国家实验室∗†部，邮编：94720。密歇根州立大学计算机科学与工程系，密歇根东兰辛，密歇根州48824。
On the Equivalence of Nonnegative Matrix Factorization and K-means — Spectral Clustering Chris Ding ∗ Xiaofeng He ∗ Horst D. Simon ∗ Rong Jin † December 4, 2005 Abstract We provide a systematic analysis of nonnegative matrix factorization (NMF) relating to data cluster- ing. We generalize the usual X = F G T decomposition to the symmetric W = HH T and W = HSH T decompositions. We show that (1) W = HH T is equivalent to Kernel K-means clustering and the Laplacian-based spectral clustering. (2) X = F G T is equivalent to simultaneous clustering of rows and columns of a bipartite graph. We emphasizes the importance of orthogonality in NMF and soft clustering nature of NMF. These results are verified with experiments on face images and newsgroups. Introduction Standard factorization of a data matrix uses singular value decomposition (SVD) as widely used in principal component analysis (PCA). However, for many dataset such as images and text, the original data matrices are nonnegative. A factorization such as SVD contains negative entries and is difficult to interpret for some applications. In contrast, nonnegative matrix factorization (NMF) [18, 19] restricts the entries in matrix factors to be nonnegative. NMF has been shown recently to be useful for many applications in environment [25], chemometrics [29], pattern recognition [20], multimedia [6], text mining [31, 26] and DNA gene expressions [3]. This is also extended to classification [27]. A number of stuides focus on further developing NMF computational methodologies [15, 22, 26, 5, 21]. Let X = (x 1 , . . . , x n ) ∈ R p×n be the data matrix of nonnegative elements. In image processing, each column x i is a 2D array of pixels gray level. In text processing, each column is a document. The NMF factorizes X into two nonnegative matrices, X ≈ F G T , n×k where F = (f 1 , · · · , f k ) ∈ R p×k and G = (g 1 , · · · , g k ) ∈ R + . k is a pre-specified parameter. NMF can be traced back to 1970s (communication from Gene Golub) and has been studied by Paatero [25, 29]. The work of Lee and Seung [18, 19] brought much attention to NMF in machine learning and data mining communities. There appears to have some confusions, however. Lee and Seung emphasizes[18] that NMF factors f k contain coherent parts of the original data (images), for example a nose or an eye. Later experiments [16, 20] do not support the parts-of-whole interpretation of NMF. In fact, Hoyer[16] and Li, et al[20] specifically propose sparsification schemes to achieve the parts-of-whole pictures. ∗ Lawrence † Department Berkeley National Laboratory, University of California, Berkeley, CA 94720. of Computer Science and Engineering, Michigan State University, East Lansing, MI 48824.