Convex programming based spectral clustering
Convex programming based spectral clustering
复制标题
DOI：
10.1007/s10994-020-05940-1
复制
发表时间：
2018-05
期刊：
影响因子：
7.5
通讯作者：
Tomohiko Mizutani
中科院分区：
文献类型：
--
作者：
Tomohiko Mizutani
聚类是数据分析中的一项基本任务，谱聚类被认为是一种很有前途的方法。给出一个描述数据之间关系的图，谱聚类分两个阶段探索潜在的集群结构。第一阶段将图中的节点嵌入到真实空间中，第二阶段将嵌入的节点分组为若干簇。在分组阶段使用k-均值方法是目前的标准做法。我们提出了一种在分组阶段使用凸规划的谱聚类算法，并研究了该算法的性能。该算法是基于以下观察结果设计的。如果图具有良好的聚类性，则可以通过计算嵌入在实空间中的节点的封闭椭球来找到每个簇中度最大的节点，并利用这些节点来识别簇。我们证明，对于良好的聚类图，该算法可以找到具有最小电导的节点的簇。并对该算法的性能进行了实验评估。
Clustering is a fundamental task in data analysis, and spectral clustering has been recognized as a promising approach to it. Given a graph describing the relationship between data, spectral clustering explores the underlying cluster structure in two stages. The first stage embeds the nodes of the graph in real space, and the second stage groups the embedded nodes into several clusters. The use of thek-means method in the grouping stage is currently standard practice. We present a spectral clustering algorithm that uses convex programming in the grouping stage and study how well it works. This algorithm is designed based on the following observation. If a graph is well-clustered, then the nodes with the largest degree in each cluster can be found by computing an enclosing ellipsoid of the nodes embedded in real space, and the clusters can be identified by using those nodes. We show that, for well-clustered graphs, the algorithm can find clusters of nodes with minimal conductance. We also give an experimental assessment of the algorithm’s performance.