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: Diffusion map, Hypergraph laplacian, Markov relaxation, 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] CHEN Zhi-qiang, HAN Meng, LI Mu-hang, WU Hong-xin, ZHANG Xi-long. Survey of Concept Drift Handling Methods in Data Streams [J]. Computer Science, 2022, 49(9): 14-32.
[2] WANG Ming, WU Wen-fang, WANG Da-ling, FENG Shi, ZHANG Yi-fei. Generative Link Tree:A Counterfactual Explanation Generation Approach with High Data Fidelity [J]. Computer Science, 2022, 49(9): 33-40.
[3] ZHANG Jia, DONG Shou-bin. Cross-domain Recommendation Based on Review Aspect-level User Preference Transfer [J]. Computer Science, 2022, 49(9): 41-47.
[4] ZHOU Fang-quan, CHENG Wei-qing. Sequence Recommendation Based on Global Enhanced Graph Neural Network [J]. Computer Science, 2022, 49(9): 55-63.
[5] SONG Jie, LIANG Mei-yu, XUE Zhe, DU Jun-ping, KOU Fei-fei. Scientific Paper Heterogeneous Graph Node Representation Learning Method Based onUnsupervised Clustering Level [J]. Computer Science, 2022, 49(9): 64-69.
[6] CHAI Hui-min, ZHANG Yong, FANG Min. Aerial Target Grouping Method Based on Feature Similarity Clustering [J]. Computer Science, 2022, 49(9): 70-75.
[7] ZHENG Wen-ping, LIU Mei-lin, YANG Gui. Community Detection Algorithm Based on Node Stability and Neighbor Similarity [J]. Computer Science, 2022, 49(9): 83-91.
[8] LYU Xiao-feng, ZHAO Shu-liang, GAO Heng-da, WU Yong-liang, ZHANG Bao-qi. Short Texts Feautre Enrichment Method Based on Heterogeneous Information Network [J]. Computer Science, 2022, 49(9): 92-100.
[9] XU Tian-hui, GUO Qiang, ZHANG Cai-ming. Time Series Data Anomaly Detection Based on Total Variation Ratio Separation Distance [J]. Computer Science, 2022, 49(9): 101-110.
[10] NIE Xiu-shan, PAN Jia-nan, TAN Zhi-fang, LIU Xin-fang, GUO Jie, YIN Yi-long. Overview of Natural Language Video Localization [J]. Computer Science, 2022, 49(9): 111-122.
[11] CAO Xiao-wen, LIANG Mei-yu, LU Kang-kang. Fine-grained Semantic Reasoning Based Cross-media Dual-way Adversarial Hashing Learning Model [J]. Computer Science, 2022, 49(9): 123-131.
[12] ZHOU Xu, QIAN Sheng-sheng, LI Zhang-ming, FANG Quan, XU Chang-sheng. Dual Variational Multi-modal Attention Network for Incomplete Social Event Classification [J]. Computer Science, 2022, 49(9): 132-138.
[13] DAI Yu, XU Lin-feng. Cross-image Text Reading Method Based on Text Line Matching [J]. Computer Science, 2022, 49(9): 139-145.
[14] QU Qian-wen, CHE Xiao-ping, QU Chen-xin, LI Jin-ru. Study on Information Perception Based User Presence in Virtual Reality [J]. Computer Science, 2022, 49(9): 146-154.
[15] ZHOU Le-yuan, ZHANG Jian-hua, YUAN Tian-tian, CHEN Sheng-yong. Sequence-to-Sequence Chinese Continuous Sign Language Recognition and Translation with Multi- layer Attention Mechanism Fusion [J]. Computer Science, 2022, 49(9): 155-161.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!