Spectral Clustering Algorithm for Density Adaptive Neighborhood Based on Shared Nearest Neighbors

doi:10.19678/j.issn.1000-3428.0058893

Abstract

Abstract: Without prior information, it is difficult for spectral clustering algorithms to build appropriate similarity graphs for datasets with complex shapes and different densities. At the same time, the similarity measure of Gaussian kernel functions based on Euclidean distance ignores global consistency. To address the problem, a spectral clustering algorithm (SC-DANSN) for density adaptive neighborhood based on shared nearest neighbors is proposed. An undirected graph is constructed by using a parameter-free density adaptive neighborhood construction method, and shared nearest neighbors are used to measure the similarity between samples. This measurement eliminates the influence of parameters on similarity graph construction, as it reflects both global consistency and local consistency. The experimental results show that the SC-DANSN algorithm has a higher clustering accuracy than the K-means algorithm and Spectral Clustering based on K Nearest Neighbor (SC-KNN). At the same time, SC-DANSN is less sensitive to the selection of parameters than SC-KNN.

Key words: Spectral Clustering(SC), similarity matrix, density adaptive neighborhood, shared nearest neighbor, K Nearest Neighbor(KNN)

摘要： 在谱聚类算法没有先验信息的情况下，对于具有复杂形状和不同密度变化的数据集很难构建合适的相似图，且基于欧氏距离的高斯核函数的相似性度量忽略了全局一致性。针对该问题，提出一种基于共享最近邻的密度自适应邻域谱聚类算法（SC-DANSN）。通过一种无参数的密度自适应邻域构建方法构建无向图，将共享最近邻作为衡量样本之间的相似性度量进而消除参数对构建相似图的影响，体现全局和局部的一致性。实验结果表明，SC-DANSN算法相比K-means算法和基于K最近邻的谱聚类算法（SC-KNN）具有更高的聚类精度，同时相比SC-KNN算法对参数的选取敏感性更低。

关键词: 谱聚类, 相似性矩阵, 密度自适应邻域, 共享最近邻, K最近邻

CLC Number:

TP391

GE Junwei, YANG Guangxin. Spectral Clustering Algorithm for Density Adaptive Neighborhood Based on Shared Nearest Neighbors[J]. Computer Engineering, 2021, 47(8): 116-123.

葛君伟, 杨广欣. 基于共享最近邻的密度自适应邻域谱聚类算法[J]. 计算机工程, 2021, 47(8): 116-123.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0058893

http://www.ecice06.com/EN/Y2021/V47/I8/116

Figures/Tables 15

References

[1] AGGARWAL C C, REDDY C K.Data clustering:algorithms and applications[M]. London, UK:Taylor and Francis Group, 2014:4-7.
[2] ANTER A, HASSENIAN A E, OLIVA D.An improved fast fuzzy c-means using crow search optimization algorithm for crop identification in agricultural[J]. Expert Systems with Applications, 2019, 118:340-354.
[3] DING S, JIA H, ZHANG L, et al. Research of semi-supervised spectral clustering algorithm based on pairwise constraints[J]. Neural Computer&Applications, 2014, 24:211-219.
[4] WANG L, DING S, JIA H.An improvement of spectral clustering via message passing and density sensitive similarity[J]. IEEE Access, 2019, 7:101054-101062.
[5] LUXBURG U V, A tutorial on spectral clustering[J]. Statist.Comput, 2007, 17(4): 395-416.
[6] 牛科, 张小琴, 贾郭军.基于距离度量学习的集成谱聚类[J]. 计算机工程, 2015, 41(1): 207-210. NIU K, ZHANG X Q, JIA G J.Integrated spectral clustering based on distance metric learning[J]. Computer Engineering, 2015, 41(1): 207-210.(in Chinese)
[7] 乔晓明, 潘晓英.基于稀疏图的鲁棒谱聚类算法[J]. 计算机应用研究, 2018, 35(6): 1-2. QIAO X M, PAN X Y.Robust spectral clustering algorithm based on sparse graph[J]. Application Research of Computers, 2018, 35(6): 1-2.(in Chinese)
[8] ZELNIK-MANOR L, PERONA P.Self-tuning spectral clustering[C]//Proceedings of the Advances in Neural Information Processing Systems.Cambridge, USA:MIT Press, 2004:1601-1608.
[9] LIU X Y, LI J W, YU H, et al. Adaptive spectral clustering based on shared nearest neighbors[J]. Journal of Chinese Computer System, 2011, 32(9): 1876-1880.
[10] TAO X M, SONG S Y, CAO P D, et al. A spectral clustering algorithm based on manifold distance kernel[J]. Information and Control, 2012, 41(3): 307-313.
[11] NG A Y, JORDAN M I, WEISS Y.On spectral clustering:analysis and an algorithm[C]//Proceedings of Advances in Neural Information Processing Systems.Cambridge, USA:MIT Press, 2002:849-856.
[12] LI Z, LIU J, CHEN S, et al. Noise robust spectral clustering[C]//Proceedings of the 11th IEEE International Conference on Computer Vision.Washington D.C., USA:IEEE Press, 2007:361-368.
[13] ZHANG X, LI J, YU H.Local density adaptive similarity measurement for spectral clustering[J]. Pattern Recognition Letters, 2011, 32(2): 352-358.
[14] CAO J, CHEN P, YUN Z, et al. A max-flow-based similarity measure for spectral clustering[J]. ETRI Journal, 2013, 35(2): 311-320.
[15] XIONG C, JOHNSON D M, CORSO J J.Spectral active clustering via purification of the $k$-nearest neighbor graph[C]//Proceedings of International Conference on Data Mining.Washington D.C., USA:IEEE Press, 2012.
[16] 程士卿, 郝问裕, 李晨, 等. 低秩张量分解的多视角谱聚类算法[J]. 西安交通大学学报, 2019, 54(3): 119-125. CHENG S Q, HAO W Y, LI C, et al. Low-rank tensor decomposition based multi-view spectral clustering algorithm[J]. Journal of Xi'an Jiaotong University, 2019, 54(3): 119-125.(in Chinese)
[17] SUN L, LIU R, XU J, et al. An affinity propagation clustering method using hybrid Kernel function with LLE[J]. IEEE Access, 2018, 6:68892-68909.
[18] JANANI R, VIJAYARANI S.Text document clustering using spectral clustering algorithm with particle swarm optimization[J]. Expert Systems with Applications, 2019, 134:192-200.
[19] NKAYA T, KAYALGIL S, ÖZDEMIRAL N E.An adaptive neighborhood construction algorithm based on density and connectivity[J]. Pattern Recognition Letters, 2014, 52:17-24.
[20] TAO X M, WANG R T, CHANG R, et al. Spectral clustering algorithm using density-sensitive distance measure with global and local consistencies[J]. Knowledge-Based Systems, 2019, 170:26-42.

Please choose a citation manager

Content to export