Computer Science ›› 2019, Vol. 46 ›› Issue (6A): 452-456.

• Big Data & Data Mining • Previous Articles     Next Articles

Clustering Method Based on Hypergraph Morkov Relaxation

GUO Peng1,2, LI Ren-fa1, HU Hui3   

  1. College of Computer Science and Electronic Engineering,Hunan University,Changsha 410082,China1;
    College of Computer and Communication,Hunan Institute of Engineering,Xiangtan,Hunan 411104,China2;
    School of Electrical and Information,Hunan Institue of Engineering,Xiangtan,Hunan 411104,China3
  • Online:2019-06-14 Published:2019-07-02

Abstract: How to embed high dimention spatial-temporal feature into low dimention semantic feature word bag is a typic clustering problem in the Internet of vehicle .Spectral clustering algorithm is recently focused because of its simple computing and global optimal solution,however,the research about the numbers of clusters is relatively little.Tranditional eigengap heuristic method works well if the clusters in the data are very well pronounced.However,the more noisy or overlapping the clusters are,the less effective this heuristic is.This paper proposed a clustering method based on hypergraph markov relaxation (HS-MR method).The basic idea of this algorithm is using the Markov process to formally describe hypergraph and start random walk.In the relaxation process of hypergraph Markov chain,meaningful geometric distribution of data set is found through tth power of random transfer matrix P and diffusion mapping.Then,the objective function based on mutual information is proposed to automatically converge the clustering number.Finally,the experimental results show that the algorithm is superior to simple graph spectral clustering algorithm and hypergraph spectral clustering algorithm in accuracy rate.

Key words: Hypergraph laplacian, Markov relaxation, Diffusion map, Mutual informaion

CLC Number: 

  • TP391
[1] BLEI D,NG A,JORDAN M.Latent dirichlet allocation[J].Journal of Machine Learning Research,2003,3(1):993-1022.
[2] HOFMANN T.Unsupervised learning by probabilistic latent semantic analysis[J].Machine Learning,2001,42(1):177-196.
[3] SELIM S Z.K-Means-Type Algorithms:A Generalized Convergence Theorem and Characterization of Local Optimality[J].IEEE Transactions on Pattern Analysis & Machine,1984,6(1):81-87.
[4] 李永森.空间聚类算法中的K值优化问题研究[J].系统仿真学报,2006,18(3):573-576.
[5] 周水庚.基于数据分区的DBSCAN算法[J].计算机研究与发展,2000,37(10):1153-1159.
[6] LUXBURG U V.A tutorial on spectral clustering[J].Statistics and Computing,2007,17(4):395-416.
[7] SHI J,MALIK J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(8):888-905.
[8] LUXBURG U V,BOUSQUET O.Limits of spectral clustering[C]∥Advances in Neural Information Processing Systems (NIPS).2005:857-864.
[9] SCHÖLKOPF B.Learning with Hypergraphs:Clustering,Classification,and Embedding[C]∥Conference on Advances in Neural Information Pr.2006:1601-1608.
[10] ZHAN Y.A semi-supervised incremental learning method based on adaptive probabilistic hypergraph for video semantic detection[J].Multimedia Tools and Applications,2015,74(15):5513-5531.
[11] LIU X.Event-Based Media Enrichment Using an Adaptive Probabilistic Hypergraph Model[J].IEEE Transactions on Cybernetics,2015,45(11):2461-2471.
[12] MICHOEL T.Alignment and integration of complex networks by hypergraph-based spectral clustering[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2012,86(5 Pt 2):1188-1205.
[13] LIU J.Learning semantic features for action recognition via diffusion maps[J].Computer Vision & Image Understanding,2012,116(3):361-377.
[14] LU L.Recognizing human actions by two-level Beta process hidden Markov model[J].Multimedia Systems,2015:1.
[15] LANGE T.Stability-based validation of clustering solutions[J].Neural Computation,2004,16(6):1299-323.
[16] ZHOU D.Beyond pairwise classification and clustering using hypergraphs[C]∥Max Plank Institute for Biological Cybernetics.Tübingen,Germany,2005.
[17] NADLER B,LAFON S.Diffusion maps,spectral clustering and reaction coordinates of dynamical systems[J].Applied & Computational Harmonic Analysis,2005,21(1):113-127.
[18] COIFMAN R R,LAFON S.Diffusion Maps[J].Submitted to Applied Computational and Harmonic Analysis,2004.
[19] MOUYSSET S,NOAIUES J,RUIZ D,et al.Spectral Clustering:Interpretation and Gaussian Parameter[M].Data Analysis Machine Learning and Knowledge Discovery,2014.
[20] 夏利民.基于信息瓶颈算法的图像语义标注[J].模式识别与人工智能,2008,21(6):812-818.
[1] GE Meng-fan, LIU Zhen, WANG Na-na, TIAN Jing-yu. Cross-domaing Item Recommendation Algorithm Including Tag Transfer [J]. Computer Science, 2019, 46(10): 1-6.
[2] YI Xiao-qun, LI Tian-rui, CHEN Chao. Sunburst Visualization for Comment Text Data [J]. Computer Science, 2019, 46(10): 14-18.
[3] YU Ying, CHEN Ke, SHOU Li-dan, CHEN Gang, WU Xiao-fan. Sentiment Analysis of User Comments Based on Extraction of Key Words and Key Sentences [J]. Computer Science, 2019, 46(10): 19-26.
[4] ZHANG Qi, LIU Ling, WEN Jun-hao. Recommendation Algorithm with Field Trust and Distrust Based on SVD [J]. Computer Science, 2019, 46(10): 27-31.
[5] WANG Bin, MA Jun-jie, FANG Xin-xiu, WEI Tian-you. Association Rule Mining Algorithm Based on Timestamp and Vertical Format [J]. Computer Science, 2019, 46(10): 71-76.
[6] FENG Yun-fei, CHEN Hong-mei. Topological Structure Based Density Peak Algorithm for Overlapping Community Detection [J]. Computer Science, 2019, 46(10): 39-48.
[7] CHEN Feng, MENG Zu-qiang. Study on Heterogeneous Multimodal Data Retrieval Based on Hash Algorithm [J]. Computer Science, 2019, 46(10): 49-54.
[8] WANG Wei-hong, LIANG Chao-kai, MIN Yong. Multi-recording Complex Webpage Information Extraction Algorithm Based on Visual Block [J]. Computer Science, 2019, 46(10): 63-70.
[9] CHEN Jiong, ZHANG Hu, CAO Fu-yuan. Study on Point-of-interest Collaborative Recommendation Method Fusing Multi-factors [J]. Computer Science, 2019, 46(10): 77-83.
[10] WANG Peng-fei, ZHANG Hang. Sub-sampling Signal Reconstruction Based on Principal Component Under Underdetermined Conditions [J]. Computer Science, 2019, 46(10): 103-108.
[11] LI Hao, LIU Yong-jian, XIE Qing, TANG Ling-li. Distant Supervision Relation Extraction Model Based on Multi-level Attention Mechanism [J]. Computer Science, 2019, 46(10): 252-257.
[12] HAN Xu-li, ZENG Bi-qing, ZENG Feng, ZHANG Min, SHANG Qi. Sentiment Analysis Based on Word Embedding Auxiliary Mechanism [J]. Computer Science, 2019, 46(10): 258-264.
[13] CHEN Jian-ping, ZOU Feng, LIU Quan, WU Hong-jie, HU Fu-yuan, FU Qi-ming. Reinforcement Learning Algorithm Based on Generative Adversarial Networks [J]. Computer Science, 2019, 46(10): 265-272.
[14] TANG Wen-liang, TANG Shu-fang, ZHANG Ping. Research and Improvement of Web Fingerprint Identification Algorithm Based on Cosine Measure [J]. Computer Science, 2019, 46(10): 295-398.
[15] ZHU Wei, YI Yao, WANG Tu-qiang, ZHENG Ya-yu. Fast Coding Unit Partition Algorithm for Depth Maps [J]. Computer Science, 2019, 46(10): 286-294.
Full text



[1] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105, 130 .
[2] HAN Kui-kui, XIE Zai-peng and LV Xin. Fog Computing Task Scheduling Strategy Based on Improved Genetic Algorithm[J]. Computer Science, 2018, 45(4): 137 -142 .
[3] WEI Qin-shuang, WU You-xi, LIU Jing-yu and ZHU Huai-zhong. Distinguishing Sequence Patterns Mining Based on Density and Gap Constraints[J]. Computer Science, 2018, 45(4): 252 -256 .
[4] JIN Rui, LIU Zuo-xue. Synchronization Protocol of TDMA Ad hoc Network Based on Time Slot Alignment[J]. Computer Science, 2018, 45(6): 84 -88,110 .
[5] ZHANG Wen-bo and HOU Xiao-rong. Estimation Algorithm of Atmospheric Light Based on Gaussian Distribution[J]. Computer Science, 2018, 45(4): 301 -305 .
[6] XIANG Ying-zhuo, TAN Ju-xian, HAN Jie-si, SHI Hao. Survey of Graph Matching Algorithms[J]. Computer Science, 2018, 45(6): 27 -31,45 .
[7] ZHANG Pan-pan, PENG Chang-gen, HAO Chen-yan. Privacy Protection Model and Privacy Metric Methods Based on Privacy Preference[J]. Computer Science, 2018, 45(6): 130 -134 .
[8] CHEN Jin-yin, XIONG Hui, ZHENG Hai-bin. Parameters Optimization for SVM Based on Particle Swarm Algorithm[J]. Computer Science, 2018, 45(6): 197 -203 .
[9] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Geographic Routing Algorithm Based on Location Prediction in WSN[J]. Computer Science, 2018, 45(5): 59 -63 .
[10] ZENG An, GAO Cheng-si and XU Xiao-qiang. Collaborative Filtering Algorithm Incorporating Time Factor and User Preference Properties[J]. Computer Science, 2017, 44(9): 243 -249 .