Computer Science ›› 2018, Vol. 45 ›› Issue (11A): 458-461.

• Big Data & Data Mining • Previous Articles     Next Articles

Spectral Clustering Algorithm Based on SimRank Score

LI Peng-qing1, LI Yang-ding1, DENG Xue-lian2, LI Yong-gang1, FANG Yue1   

  1. Guangxi Key Lab of Multi-source Information Mining & Security,Guangxi Normal University,Guilin,Guangxi 541004,China1
    School of Public Health and Management,Guangxi University of Chinese Medicine,Nanning 530200,China2
  • Online:2019-02-26 Published:2019-02-26

Abstract: Traditional spectral clustering algorithms only consider distance between data points,ignoring their intrinsic relation.To deal with this problem,a spectral clustering method based on SimRank score was proposed.Firstly,the method computes the adjacency matrix of the undirected graph data,and obtains the similarity matrix based on SimRank.Secondly,a Laplacian matrix expression is constructed based on similarity matrix,which is then normalized followed by spectral decomposition.Finally,a k-means clustering procedure is performed on the obtained eigenvectors to obtain the final clustering results.Experimental results on benchmark datasets from UCI data repository show that the proposed algorithm is superior to the existing spectral clustering algorithms based on distance similarity in terms of clustering accuracy,standard mutual information and purity.

Key words: Adjacency matrix, k-means clustering, Laplace matrix, Similarity matrix, SimRank score, Spectral clustering

CLC Number: 

  • TP181
[1]刘紫涵,吴鹏海,吴艳兰,等.三种谱聚类算法及其应用研究[J].计算机应用研究,2017,34(4):1026-1031.
[2]MIGUEL C.On the diameter of the commuting graph of the matrix ring over a centrally finite division ring[J].Linear Algebra &Its Applications,2016,509:276-285.
[3]LI X,DU Y,WEI Y,et al.The research of concept context graph layer division based on six degrees of separation theory[J].Journal of Computational Information Systems,2013,9(22):9219-9226.
[4]ZHANG J M,SHEN Y X.Review on spectral methods for clustering[C]∥Control Conference.IEEE,2015:3791-3796.
[5]CHE W F,FENG G C.Spectral clustering:A semi-supervised approach[J].Neuro Computing,2012,77(1):119-228.
[6]ZHAO Y C,ZHANG S C.Generalized Dimension-Reduction Framework for Recent-Biased Time Series Analysis[J].IEEE Transactions on Knowledge and Data Engineering,2006,18(2):231-244.
[7]LANGONE R,MALL R,ALZATE C,et al.Kernel Spectral Clustering and Applications[M]∥Unsupervised Learning Algorithms.Springer International Publishing,2016.
[8]李瑞琳,赵永华,黄小磊.一种基于MPI的稀疏化局部尺度并行谱聚类算法的研究与实现[J].计算机工程与科学,2016,38(5):839-847.
[9]LIU G,LIN Z,YAN S,et al.Robust recovery of subspace structures by low-rank representation [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(1):171-184.
[10]ELHAMIFAR E,VIDAL R.Sparse subspace clustering [C]∥CVPR.2009:2790-2797.
[11]LU C Y,MIN H,ZHAO Z Q,et al.Robust and efficient subspace segmentation via least squares regression[C]∥ECCV.2012:347-360.
[12]邹小林,冯国灿.基于正则割(Ncut)的多阈值图像分割方法[J].计算机工程与应用,2012,48(19):174-178.
[13]WANG S,SISKIND J M.Image Segmentation with Ratio Cut [J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2003,25(6):675-690.
[14]SRINIVASARAO P,SURESH K,RAVI K B.Image Segmentation using Clustering Algorithms[J].International Journal of Computer Applications,2015,120:36-38.
[15]刘萍,黄纯万.基于SimRank的作者相似度计算[J].情报理论与实践,2015,38(6):109-114.
[16]ZHENG W,ZOU L,CHEN L,et al.Efficient SimRank-Based Similarity Join[J].Acm Transactions on Database Systems,2017,42(3):16.
[17]CHEN W F,FENG G C.Spectral clustering with discriminate cuts[J].Knowledge-Based Systems,2012,28(7):27-37.
[18]BOOBALAN M P,LOPEZ D,GAO X Z.Graph clustering using k-Neighbourhood Attribute Structural similarity[J].Applied Soft Computing,2016,47:216-223.
[19]ALZATE C,SUYKENS J A.Hierarchical kernel spectral clustering[J].Neural Networks,2012,35(2):21-30.
[20]刘敏,韩宾,郭有倩.一种改进的基于K-means的信息聚类算法研究[J].信息通信,2015(9):35-36.
[21]FANG R,POUYANFAR S,YANG Y,et al.Computational Health Informatics in the Big Data Age:A Survey[J].ACM Computing Surveys,2016,49(1):12.
[22]ZHU X F,LI X L,ZHANG S C.Block-Row Sparse Multiview Multilabel Learning for Image Classification[J].IEEE Transactions on Cybernetics,2016,46(2):450-461.
[23]李翠平.一种基于SimRank的结点相似度计算方法:CN104933312 A[P].2015.
[24]GAO Y,WANG M,TAO D C,et al.3-D object retrieval and recognition with hypergraph analysis [J].IEEE Transactions on Image Processing a Publication of the IEEE Signal Processing Society,2012,21(9):4290-4303.
[1] LI Bin, WAN Yuan. Unsupervised Multi-view Feature Selection Based on Similarity Matrix Learning and Matrix Alignment [J]. Computer Science, 2022, 49(8): 86-96.
[2] ZHANG Jie, YUE Shao-hua, WANG Gang, LIU Jia-yi, YAO Xiao-qiang. Multi-agent System Based on Stackelberg and Edge Laplace Matrix [J]. Computer Science, 2021, 48(8): 253-262.
[3] GUO Yi-shan, LIU Man-dan. Anomaly Detection Based on Spatial-temporal Trajectory Data [J]. Computer Science, 2021, 48(6A): 213-219.
[4] LI Peng, LIU Li-jun, HUANG Yong-dong. Landmark-based Spectral Clustering by Joint Spectral Embedding and Spectral Rotation [J]. Computer Science, 2021, 48(6A): 220-225.
[5] GONG Zhui-fei, WEI Chuan-jia. Link Prediction of Complex Network Based on Improved AdaBoost Algorithm [J]. Computer Science, 2021, 48(3): 158-162.
[6] XU Shou-kun, NI Chu-han, JI Chen-chen, LI Ning. Image Caption of Safety Helmets Wearing in Construction Scene Based on YOLOv3 [J]. Computer Science, 2020, 47(8): 233-240.
[7] YAO Li-shuang, LIU Dan, PEI Zuo-fei, WANG Yun-feng. Real-time Network Traffic Prediction Model Based on EMD and Clustering [J]. Computer Science, 2020, 47(11A): 316-320.
[8] HOU Yuan-yuan, HE Ru-han, LI Min, CHEN Jia. Clothing Image Retrieval Method Combining Convolutional Neural Network Multi-layerFeature Fusion and K-Means Clustering [J]. Computer Science, 2019, 46(6A): 215-221.
[9] ZHANG Xiao-qin, AN Xiao-dan, CAO Fu-yuan. Detecting Community from Bipartite Network Based on Spectral Clustering [J]. Computer Science, 2019, 46(4): 216-221.
[10] LIU Shu-dong, WEI Jia-min. Multilayer Perceptron Classification Algorithm Based on Spectral Clusteringand Simultaneous Two Sample Representation [J]. Computer Science, 2019, 46(11A): 194-198.
[11] HU Meng-qi, ZHENG Ji-ming. Blind Image Identification Algorithm Based on HSV Quantized Color Feature and SURF Detector [J]. Computer Science, 2019, 46(11A): 268-272.
[12] WANG Ying and YANG Yu-wang. KNN Similarity Graph Algorithm Based on Heap and Neighborhood Coexistence [J]. Computer Science, 2018, 45(5): 196-200.
[13] CHANG Jia-wei, DAI Mu-hong. Personalized Recommendation Algorithm Based on PageRank and Spectral Method [J]. Computer Science, 2018, 45(11A): 398-401.
[14] BAO Zhi-qiang, ZHAO Yuan-yuan, ZHAO Yan, HU Xiao-tian, GAO Fan. Segmentation of Baidu Takeaway Customer Based on RFA Model and Cluster Analysis [J]. Computer Science, 2018, 45(11A): 436-438.
[15] CHEN Jun-fen, ZHANG Ming, HE Qiang. Heuristically Determining Cluster Numbers Based NJW Spectral Clustering Algorithm [J]. Computer Science, 2018, 45(11A): 474-479.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!