Spectral clustering is discussed from many perspectives, by extending it to rectangular arrays and discrepancy minimization too. Near optimal clusters are obtained with singular value decomposition and with the weighted $k$-means algorithm. In case of rectangular arrays, this means enhancing the method of correspondence analysis with clustering, and in case of edge-weighted graphs, a normalized Laplacian based clustering. In the latter case it is proved that a spectral gap between the $(k-1)$th and $k$th smallest positive eigenvalues of the normalized Laplacian matrix gives rise to a sudden decrease of the inner cluster variances when the number of clusters of the vertex representatives is $2^{k-1}$, but only the first $k-1$ eigenvectors, constituting the so-called Fiedler-carpet, are used in the representation. Application to directed migration graphs is also discussed.


翻译:从许多角度讨论频谱集群,将之扩大到矩形阵列和差异最小化。接近最佳的集群是以单值分解和加权美元平均算法获得的。对于矩形阵列,这意味着加强与集群的对应分析方法,对于边加权图,则意味着一个基于边加权图的标准化拉普拉西亚组合。在后一种情况下,事实证明,在(k-1)美元和(k-1)美元等标准拉普拉西安矩阵最小正值之间的光谱差距导致内部集群差异的突然缩小,因为顶层代表群的数量是2 ⁇ k-1美元,但代表中只使用了构成所谓的Fiedler-carpet的第一批$-1美元电子元。还讨论了定向迁移图的应用。

0
下载
关闭预览

相关内容

专知会员服务
84+阅读 · 2020年12月5日
图节点嵌入(Node Embeddings)概述,9页pdf
专知会员服务
39+阅读 · 2020年8月22日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
Github项目推荐 | 知识图谱文献集合
AI研习社
26+阅读 · 2019年4月12日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2022年2月21日
Eternal Domination and Clique Covering
Arxiv
0+阅读 · 2022年2月21日
Arxiv
0+阅读 · 2022年2月18日
VIP会员
相关VIP内容
专知会员服务
84+阅读 · 2020年12月5日
图节点嵌入(Node Embeddings)概述,9页pdf
专知会员服务
39+阅读 · 2020年8月22日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
相关资讯
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
Github项目推荐 | 知识图谱文献集合
AI研习社
26+阅读 · 2019年4月12日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员