Spectral Clustering by Ellipsoid and Its Connection to Separable Nonnegative Matrix Factorization
Spectral Clustering by Ellipsoid and Its Connection to Separable Nonnegative Matrix Factorization
复制标题
DOI：
--
复制
发表时间：
2015-03
期刊：
影响因子：
--
通讯作者：
Tomohiko Mizutani
中科院分区：
文献类型：
--
作者：
Tomohiko Mizutani
提出了一种改进的归一化割谱聚类算法。虽然归一化切割算法将K-均值算法应用于归一化图拉普拉斯的特征向量来寻找聚类，但是我们的算法对它们使用最小体积封闭椭球。我们证明了该算法与可分非负矩阵分解的椭球舍入算法有相似之处。我们的理论见解表明，该算法可以作为谱聚类和可分离NMF之间的桥梁。K-Means算法存在初始点的选择影响聚类的构建，某些选择会导致聚类性能不佳的问题。归一化切割算法继承了这些问题，因为它结合了K-均值，而本文提出的算法没有。给出了一个实验研究来检验该算法的性能。
This paper proposes a variant of the normalized cut algorithm for spectral clustering. Although the normalized cut algorithm applies the K-means algorithm to the eigenvectors of a normalized graph Laplacian for finding clusters, our algorithm instead uses a minimum volume enclosing ellipsoid for them. We show that the algorithm shares similarity with the ellipsoidal rounding algorithm for separable nonnegative matrix factorization. Our theoretical insight implies that the algorithm can serve as a bridge between spectral clustering and separable NMF. The K-means algorithm has the issues in that the choice of initial points affects the construction of clusters and certain choices result in poor clustering performance. The normalized cut algorithm inherits these issues since K-means is incorporated in it, whereas the algorithm proposed here does not. An empirical study is presented to examine the performance of the algorithm.