.png){kind=icon}
返回
Recursive kernel trick for network segmentation
.png){kind=icon}
PRE
AI
DOI：10.1002/rnc.1723.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Kernel K-means has been a powerful unsupervised machine learning tool for cluster discovery. This paper explores its application towards network segmentation, a type of cluster discovery. Very commonly we encounter networks of extremely large size, making computational complexity a major issue in the algorithmic development. In this regard, the sparse structure of kernel matrices can be an invaluable asset. For partitioning nonvectorial data such as network graphs, we need to use a vector-free clustering criterion for K-means. The kernel matrix constructed from nonvectorial data usually needs to be preprocessed to assure Mercer's condition, which is required to guarantee monotonic convergence of the kernel K-means algorithm. This paper describes a centroid-free criterion for K-means so that it can be applied to nonvectorial data such as network segmentation. Such a criterion leads to our introduction of pattern-centroid similarity which ultimately leads to a kernel trick algorithm based on updating of the pattern-centroid similarity. Furthermore, by adopting a recursive updating scheme, the recursive kernel-trick allows a computational saving from O(N-2/K) to O(N). For networks with high sparsity structure, the amount of computation required can be further reduced from O(N) to O(N-s), where N-s is the average number of nonzero elements per column in the kernel matrix. Copyright (C) 2011 John Wiley & Sons, Ltd.
Keyword:
graph partitioning
kernel k-means for cluster discovery and network segmentation
recursive kernel trick
sparsity
computational saving
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
3.2
论文数:
7.0K
被引数:
1.4W
.png){kind=icon}
