HMRF半监督近似核<i>k</i>-means算法

摘要/Abstract

摘要： 信息技术的发展催生了海量数据。聚类有助于发现数据的内在联系,从中挖掘有价值的信息。在对数据进行分析时,容易获得一些关于数据的背景知识,使用这些有限的先验信息指导聚类,可以显著改善聚类的结果。基于隐马尔可夫随机场(Hidden Markov Random Fields,HMRF)的半监督聚类使用成对约束作为监督信息,虽然在很多应用场景中有较好的聚类效果,但是其时间和空间复杂度很高,无法满足大规模数据处理的需要。针对该问题,文中首先分析了HMRF半监督聚类与核k-means的数学联系,使用矩阵的迹将两者的目标函数统一起来;然后,为了降低HMRF半监督聚类的复杂度,提出HMRF半监督近似核k-means算法(HMRF semi-supervised Approximate Kernel K-Means,HMRF-AKKM),通过采样构造近似核矩阵,使用近似核k-means优化聚类的目标函数;最后,在基准数据集上将HMRF-AKKM算法与相关的聚类算法进行对比,分析不同算法在实验中的聚类表现。实验结果表明,在相同的聚类任务上,HMRF-AKKM算法与原始的HMRF半监督聚类具有类似的聚类质量,但是HMRF-AKKM算法的聚类时间更短,说明HMRF-AKKM算法继承了HMRF半监督聚类与近似核k-means的优点。该算法一方面可以充分利用成对约束信息改善聚类质量,另一方面通过采样和矩阵近似提高了聚类效率,而且聚类质量和聚类效率可以通过调节采样比例和成对约束数量来平衡。因此,所提出的HMRF-AKKM算法具有良好的可扩展性,适合处理大规模非线性数据的聚类问题。

关键词: HMRF模型, 半监督聚类, 成对约束, 近似核k-means, 矩阵的迹

Abstract: Massive data are produced with the development of information technology.Clustering can help to discover the intrinsic links of data and extract valuable information from them.In data analyzing,it is easy to get some background knowledge about data.Using these limited prior information to guide clustering can significantly improve the clustering results.The semi-supervised clustering based on Hidden Markov Random Fields (HMRF) uses pairwise constraints as the supervision information.Although it has good clustering results in many applications,its time and space complexity are very high,which cannot meet the needs of large-scale data processing.To solve this problem,this paper first analyzed the mathematical relationship between HMRF semi-supervised clustering and kernel k-means,and used matrix trace to unify the objective functions of the two clustering methods.In order to reduce the complexity of HMRF semi-supervised clustering,this paper proposed a HMRF semi-supervised approximate kernel k-means algorithm (HMRF-AKKM),which constructs an approximate kernel matrix by sampling,and used the approximate kernel k-means to optimize the clustering objective function.Finally,the HMRF-AKKM algorithm was compared with the related clustering algorithms on several benchmark datasets and the clustering performances of different algorithms were analyzed in the experiments.The experimental results show that the HMRF-AKKM algorithm has similar clustering quality to the original HMRF semi-supervised clustering on the same clustering task,but the HMRF-AKKM algorithm has shorter clustering time.This indicates that the HMRF-AKKM algorithm inherits the advantages of HMRF semi-supervised clustering and approximate kernel k-means.On the one hand,HMRF-AKKM can make full use of pairwise constraints to achieve high clustering quality.On the other hand,it improves the clustering efficiency by sampling and matrix approximation.Moreover,the clustering quality and clustering efficiency can be balanced by adjusting the sampling ratio and the number of pairwise constraints.Therefore,the proposed HMRF-AKKM algorithm has good scalability and it is suitable for the clustering problems of large-scale nonlinear data.

Key words: Approximate kernel k-means, HMRF model, Matrix trace, Pairwise constraints, Semi-supervised clustering

中图分类号:

TP391

贾洪杰, 王良君, 宋和平. HMRF半监督近似核k-means算法[J]. 计算机科学, 2019, 46(12): 31-37. https://doi.org/10.11896/jsjkx.190600159

JIA Hong-jie, WANG Liang-jun, SONG He-ping. HMRF Semi-supervised Approximate Kernel k-means Algorithm[J]. Computer Science, 2019, 46(12): 31-37. https://doi.org/10.11896/jsjkx.190600159

参考文献

[1]ZHANG X T,ZHANG X C,LIU H.Weighed Multi-Task Clustering by Feature and Instance Transfer [J].Chinese Journal of Computers,2019,42(36):1-17.(in Chinese)
张晓彤,张宪超,刘晗.基于特征和实例迁移的加权多任务聚类[J].计算机学报,2019,42(36):1-17.
[2]MARIN D,TANG M,AYED I B,et al.Kernel clustering:density biases and solutions [J].IEEE Transactions on Pattern Ana-lysis and Machine Intelligence,2019,41(1):136-147.
[3]LIU X,ZHU X,LI M,et al.Multiple kernel k-means with incomplete kernels [OL].https://doi.org/10.1109/TPAMI.2019.2892416.
[4]CHITTA R,JIN R,HAVENS T C,et al.Scalable kernel clustering:Approximate kernel k-means [J].arXiv:1402.3849.
[5]MEHRKANOON S,ALZATE C,MALL R,et al.Multiclass Semisupervised Learning Based Upon Kernel Spectral Clustering [J].IEEE Transactions on Neural Networks & Learning Systems,2015,26(4):720-733.
[6]GAN H,FAN Y,LUO Z,et al.Local homogeneous consistent safe semi-supervised clustering [J].Expert Systems with Applications,2018,97:384-393.
[7]WANG W,YANG C,CHEN H,et al.Unified Discriminative and Coherent Semi-Supervised Subspace Clustering [J].IEEE Transactions on Image Processing,2018,27(5):2461-2470.
[8]YU Z,LUO P,LIU J,et al.Semi-supervised ensemble clustering based on selected constraint projection [J].IEEE Transactions on Knowledge and Data Engineering,2018,30(12):2394-2407.
[9]REN Y,HU K,DAI X,et al.Semi-supervised deep embedded clustering [J].Neurocomputing,2019,325:121-130.
[10]MEI J P.Semi-supervised fuzzy clustering with partition information of subsets[OL].https://doi.org/10.1109/TFUZZ.2018.2889010.
[11]NGUYEN B,DE BAETS B.Kernel-Based Distance Metric Learning for Supervised k-Means Clustering [OL].https://doi.org/10.1109/TNNLS.2018.2890021.
[12]WU B,ZHANG Y,HU B G,et al.Constrained clustering and its application to face clustering in videos[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.IEEE,2013:3507-3514.
[13]WANG S,GITTENS A,MAHONEY M W.Scalable kernel K-means clustering with Nyström approximation:relative-error bounds [J].The Journal of Machine Learning Research,2019,20(1):431-479.
[14]KULIS B,BASU S,DHILLON I,et al.Semi-supervised graph clustering:a kernel approach [J].Machine Learning,2009,74(1):1-22.
[15]BÜHLER T,HEIN M.Spectral clustering based on the graph p-Laplacian[C]//Proceedings of the 26th International Confe-rence on Machine Learning.ACM,2009:81-88.
[16]CAI D,HE X,HAN J,et al.Graph regularized nonnegative matrix factorization for data representation [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(8):1548-1560.
[17]BAGHSHAH M S,AFSARI F,SHOURAKI S B,et al.Scalable semi-supervised clustering by spectral kernel learning [J].Pattern Recognition Letters,2014,45:161-171.
[18]BHATT R B,DHALL A.Skin Segmentation Dataset.UCI Machine Learning Repository[OL].https://archive.ics.uci.edu/ml/index.html.
[19]KLEIN D,KAMVAR S D,MANNING C D.From Instance-le- vel Constraints to Space-Level Constraints:Making the Most of Prior Knowledge in Data Clustering[C]//Proceedings of the 19th International Conference on Machine Learning.ACM,2002:307-314.
[20]JIA H J,DING S F,SHI Z Z.Approximate weighted kernel k-means for large-scale spectral clustering [J].Journal of Software,2015,26(11):2836-2846.(in Chinese)
贾洪杰,丁世飞,史忠植.求解大规模谱聚类的近似加权核k-means算法[J].软件学报,2015,26(11):2836-2846.
[21]YANG Y,TAN W,LI T,et al.Consensus clustering based on constrained self-organizing map and improved Cop-Kmeans ensemble in intelligent decision support systems [J].Knowledge-Based Systems,2012,32:101-115.
[22]DING S,JIA H,DU M,et al.A semi-supervised approximate spectral clustering algorithm based on HMRF model [J].Information Sciences,2018,429:215-228. SHI Y,OTTO C,JAIN A K.Face clustering:representation and pairwise constraints .IEEE Transactions on Information Forensics and Security,2018,13(7):1626-1640. HE L,RAY N,GUAN Y,et al.Fast large-scale spectral clustering via explicit feature mapping .IEEE Transactions on Cybernetics,2018,49(3):1058-1071. ZHAO X,LIANG J,DANG C.A stratified sampling based clustering algorithm for large-scale data . Knowledge-Based Systems,2019,163:416-428.

相关文章 15

[1]	赵敏, 刘惊雷. 基于高斯场和自适应图正则的半监督聚类 Semi-supervised Clustering Based on Gaussian Fields and Adaptive Graph Regularization 计算机科学, 2021, 48(7): 137-144. https://doi.org/10.11896/jsjkx.200800190
[2]	杨帆, 王俊斌, 白亮. 基于安全性的成对约束扩充算法 Extended Algorithm of Pairwise Constraints Based on Security 计算机科学, 2020, 47(9): 324-329. https://doi.org/10.11896/jsjkx.200700092
[3]	秦悦, 丁世飞. 半监督聚类综述 Survey of Semi-supervised Clustering 计算机科学, 2019, 46(9): 15-21. https://doi.org/10.11896/j.issn.1002-137X.2019.09.002
[4]	王楠, 孙善武. 基于半监督聚类分析的无人机故障识别 UAV Fault Recognition Based on Semi-supervised Clustering 计算机科学, 2019, 46(6A): 192-195.
[5]	程雪梅,杨秋辉,翟宇鹏,陈伟. 基于半监督聚类方法的测试用例选择技术 Test Case Selection Technique Based on Semi-supervised Clustering Method 计算机科学, 2018, 45(1): 249-254. https://doi.org/10.11896/j.issn.1002-137X.2018.01.044
[6]	梁辰,李成海. 一种新的半监督入侵检测方法 Novel Intrusion Detection Method Based on Semi-supervised Clustering 计算机科学, 2016, 43(5): 87-90. https://doi.org/10.11896/j.issn.1002-137X.2016.05.016
[7]	王纵虎,刘速. 一种成对约束限制的半监督文本聚类算法 Pairwise Constrained Semi-supervised Text Clustering Algorithm 计算机科学, 2016, 43(12): 183-188. https://doi.org/10.11896/j.issn.1002-137X.2016.12.033
[8]	冯晨菲,杨燕,王红军,徐英歌,王韬. 一种基于数据相关性的半监督模糊聚类集成方法 Semi-supervised Fuzzy Clustering Ensemble Approach with Data Correlation 计算机科学, 2015, 42(6): 41-45. https://doi.org/10.11896/j.issn.1002-137X.2015.06.009
[9]	苏赢彬,杜学绘,夏春涛,曹利峰,陈华成. 基于半监督聚类的文档敏感信息推导方法 Sensitive Information Inference Method Based on Semi-supervised Document Clustering 计算机科学, 2015, 42(10): 132-137.
[10]	邱烨，何振峰. 面向限制K-means算法的迭代学习分配次序策略 Iterative Learning Assignment Order for Constrained K-means Algorithm 计算机科学, 2012, 39(8): 196-198.
[11]	兰远东,邓辉舫,陈涛. 基于图收缩的半监督聚类算法 Semi-supervised Clustering Algorithm Based on Graph Contraction 计算机科学, 2012, 39(4): 236-239.
[12]	齐鸣鸣,向阳. 融合稀疏保持的成对约束投影 Pairwise Constraint Projections Inosculating Sparsity Preserving 计算机科学, 2012, 39(11): 212-215.
[13]	李岩波.宋琼,郭新辰. 基于流形距离的人工免疫半监督聚类算法 Artificial Immune Clustering Semi-supervised Algorithm Based on Manifold Distance 计算机科学, 2012, 39(11): 204-207.
[14]	崔鹏，张汝波. 一种用于处理高维稀疏数据的半监督聚类算法 Novel Semi-supervised Clustering for High Dimensional Data 计算机科学, 2010, 37(7): 205-207.
[15]	李琳娜,陈海蕊,王映龙. 基于高阶逻辑的复杂结构数据半监督聚类 Semi-supervised Clustering of Complex Structured Data Based on Higher-order Logic 计算机科学, 2009, 36(9): 196-200.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

HMRF半监督近似核k-means算法

HMRF Semi-supervised Approximate Kernel k-means Algorithm

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0