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

doi:10.11896/jsjkx.190600159

摘要/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: Semi-supervised clustering, HMRF model, Approximate kernel k-means, Matrix trace, Pairwise constraints

中图分类号:

TP391

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

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.

参考文献 22

[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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed