Improved analysis of spectral algorithm for clustering
Improved analysis of spectral algorithm for clustering
复制标题
聚类谱算法的改进分析
DOI：
10.1007/s11590-020-01639-3
复制
发表时间：
2021
影响因子：
1.6
通讯作者：
Tomohiko Mizutani
中科院分区：
文献类型：
--
作者：
田村 豊貴;水科 晴樹;山本 健詞;陶山 史朗;Tomohiko Mizutani
谱算法是通过使用谱嵌入映射将图的节点集划分为组的图划分算法。基于该算法的聚类技术被称为谱聚类，并广泛应用于数据分析。为了更好地理解为什么谱聚类是成功的，Peng et al.（见：第28届学习理论会议论文集（COLT），第40卷，第1423-1455页，2015年）和Kolev和Mehlhorn（见：第24届欧洲算法年会（ESA 2016），第57卷，第57页：1-57页：14，2016）研究了一类图的某种类型的谱算法的行为，称为良好聚类图。他们研究的算法使用了Shi和Malik开发的谱嵌入映射（IEEE Trans Pattern Anal Mach Intell 22（8）：888-905，2000）。在本文中，我们改进了他们的结果，在较弱的假设下给出了更好的性能保证。我们还使用Ng等人开发的谱嵌入图评估了谱算法的性能（见：神经信息处理系统进展14（NIPS），第849-856页，2001年）。
Spectral algorithms are graph partitioning algorithms that partition a node set of a graph into groups by using a spectral embedding map. Clustering techniques based on the algorithms are referred to as spectral clustering and are widely used in data analysis. To gain a better understanding of why spectral clustering is successful, Peng et al. (In: Proceedings of the 28th conference on learning theory (COLT), vol 40, pp 1423–1455, 2015) and Kolev and Mehlhorn (In: 24th annual European symposium on algorithms (ESA 2016), vol 57, pp 57:1–57:14, 2016) studied the behavior of a certain type of spectral algorithm for a class of graphs, called well-clustered graphs. Specifically, they put an assumption on graphs and showed the performance guarantee of the spectral algorithm under it. The algorithm they studied used the spectral embedding map developed by Shi and Malik (IEEE Trans Pattern Anal Mach Intell 22(8):888–905, 2000). In this paper, we improve on their results, giving a better performance guarantee under a weaker assumption. We also evaluate the performance of the spectral algorithm with the spectral embedding map developed by Ng et al. (In: Advances in neural information processing systems 14 (NIPS), pp 849–856, 2001).
DOI：
--
发表时间：
2015
期刊：
arXiv: Discrete Mathematics
影响因子：
--
作者：
Pavel Kolev;K. Mehlhorn
通讯作者：
K. Mehlhorn
分区为扩展器
影响因子：
3.5
作者：
S. Gharan;L. Trevisan
通讯作者：
L. Trevisan
关于谱聚类的注释
DOI：
10.4230/lipics.esa.2016.57
发表时间：
2015
期刊：
ArXiv
影响因子：
--
作者：
Pavel Kolev;K. Mehlhorn
通讯作者：
K. Mehlhorn