基于相关熵的快速聚类算法

李中衡; 杨奔; 张劲节; 刘银川; 张雪涛; 王飞

doi:10.7652/xjtuxb202106015

您当前的位置：

首页 >

文章列表页 >

基于相关熵的快速聚类算法

更新时间：2025-07-09

- 基于相关熵的快速聚类算法
- Fast Correntropy-Based Clustering Algorithm
- 西安交通大学学报 2021年55卷第6期页码：121-130
- 作者机构：
  
  西安交通大学视觉信息处理与应用国家工程实验室,西安,710049
- 作者简介：
- 基金信息：
  
  : 2021-01-15。作者简介: 李中衡(1991—),男,博士生;王飞(通信作者),男,教授。基金项目: 国家重大科技攻关资助项目(2018ZX01008103);中央大学基础研究基金资助项目
- DOI：10.7652/xjtuxb202106015
  中图分类号： TP181
- 网络首发：2021-06-10，
  
  纸质出版：2021
- 稿件说明：
移动端阅览
李中衡, 杨奔, 张劲节, 等. 基于相关熵的快速聚类算法[J]. 西安交通大学学报, 2021,55(6):121-130.

Fast Correntropy-Based Clustering Algorithm[J]. 2021, 55(6): 121-130.
李中衡, 杨奔, 张劲节, 等. 基于相关熵的快速聚类算法[J]. 西安交通大学学报, 2021,55(6):121-130. DOI： 10.7652/xjtuxb202106015.

Fast Correntropy-Based Clustering Algorithm[J]. 2021, 55(6): 121-130. DOI： 10.7652/xjtuxb202106015.

摘要

针对目前大规模真实数据聚类中存在的效率低和鲁棒性差的问题

提出了一种基于相关熵的快速聚类算法(FCC)。该算法主要分为以下两步:首先对原始数据进行k均值操作

得到粗略的样本类别

作为第二步的标签矩阵; 其次利用原始数据与其锚点构建的锚点图对应的拉普拉斯矩阵作为图约束来探寻数据间的内在结构

从而得到样本的最终类别。整个聚类过程在相关熵准则而不是传统的欧氏距离框架下进行

可有效抑制真实数据中大量存在的非线性和非高斯分布的噪声对聚类鲁棒性的影响。为了验证提出算法的性能

使用5种典型的算法作为对比算法与提出的算法一起在4个大规模真实数据集上运行

结果表明

提出的算法可在大部分情况下提高聚类精度

在WebKB、TDT2和Cora数据集上分别提高8.58%

6.86%和1.86%

同时提高聚类效率几倍甚至几十倍; 为了验证本算法的鲁棒性

分别加入不同程度的随机噪声和泊松噪声到WebKB和Cora上

得到8个含噪数据集

所有算法均在相同条件下运行于这些噪声数据集上

结果表明

相对于其他对比算法

提出的算法能够保持最优的聚类鲁棒性。

Abstract

Aiming at the issue of low efficiency and poor robustness in large-scale real-world data clustering

a fast correntropy-based clustering algorithm(FCC)is proposed. FCC is mainly divided into the following two steps:1)Performing k-means on the original data to obtain rough labels to serve as the label matrix of the second step; 2)Adopting the original data and those anchors to construct the anchor graph and taking Laplacian matrix of the anchor graph as a graph constraint to explore the internal structure of original data so as to obtain the final categories of these samples. Meanwhile

the whole clustering process is carried out under the correntropy instead of the traditional Euclidean distance framework

which can effectively suppress the influence of the large amount of non-linear and non-Gaussian noise in the real-world data on the clustering robustness. To verify the performance of FCC

five state-of-the-art algorithms are developed as baselines to run with FCC on four large-scale real-world data sets. The results show that FCC can improve the clustering accuracy in most cases(by 8.58%

6.86% and 1.86% respectively on WebKB

TDT2 and Cora)while greatly improving the clustering efficiency(by several or even dozens of times). Furthermore

to verify the robustness of FCC

varying degrees of random noise and Poisson noise are added to WebKB and Cora to obtain 8 noisy data sets

and all algorithms are run on these noisy data sets under the same conditions. Compared with the other baseline algorithms

FCC can maintain the optimal clustering robustness.

关键词

Keywords

references

刘涛, 尹红健. 基于半监督学习的K均值聚类算法研究 [J]. 计算机应用研究, 2010, 27(3): 913-916.

LIU Tao, YIN Hongjian. Semi-supervised learning based on K-means clustering algorithm [J]. Application Research of Computers, 2010, 27(3): 913-916.

喻金平, 郑杰, 梅宏标. 基于改进人工蜂群算法的K均值聚类算法 [J]. 计算机应用, 2014, 34(4): 1065-1069, 1088.

YU Jinping, ZHENG Jie, MEI Hongbiao. K-means clustering algorithm based on improved artificial bee colony algorithm [J]. Journal of Computer Applications, 2014, 34(4): 1065-1069, 1088.

林涛, 赵璨. 最近邻优化的k-means聚类算法 [J]. 计算机科学, 2019, 46(S2): 216-219.

LIN Tao, ZHAO Can. Nearest neighbor optimization k-means clustering algorithm [J]. Computer Science, 2019, 46(S2): 216-219.

胡卓娅, 翁健. 基于人工蜂群算法的自适应谱聚类算法 [J]. 重庆理工大学学报(自然科学), 2020, 34(3): 137-144.

HU Zhuoya, WENG Jian. Adaptive spectral clustering algorithm based on artificial bee colony algorithm [J]. Journal of Chongqing University of Technology(Natural Science), 2020, 34(3): 137-144.

原虹. 基于稀疏子空间聚类的文本谱聚类算法研究 [J]. 电子技术与软件工程, 2020(13): 156-157.

葛君伟, 杨广欣. 基于共享最近邻的密度自适应邻域谱聚类算法 [J/OL]. 计算机工程. [2020-12-20]. https: ∥doi.org/10.19678/j.issn.1000-3428.0058893.

BANERJEE A, MERUGU S, DHILLON I, et al. Clustering with Bregman divergences [C]∥Proceedings of the 2004 SIAM International Conference on Data Mining. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2004: 1705-1749.

CAMASTRA F, VERRI A. A novel kernel method for clustering [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(5): 801-805.

LI Yeqing, NIE Feiping, HUANG Heng, et al. Large-scale multi-view spectral clustering via bipartite graph [C]∥Proceedings of the 29th National Conference on Artificial Intelligence. Palo Alto, CA, USA: AAAI, 2015: 2750-2756.

ZHANG Ruiqi, LU Zhiwu. Large scale sparse clustering [C]∥Proceedings of the 25th International Joint Conference on Artificial Intelligence. California, USA: IJCAI, 2016: 2336-2342.

LI Xuelong, CUI Guosheng, DONG Yongsheng. Graph regularized non-negative low-rank matrix factorization for image clustering [J]. IEEE Transactions on Cybernetics, 2017, 47(11): 3840-3853.

PENG Siyuan, SER W, CHEN Badong, et al. Correntropy based graph regularized concept factorization for clustering [J]. Neurocomputing, 2018, 316: 34-48.

NIE Feiping, WANG Chenglong, LI Xuelong. K-multiple-means: a multiple-means clustering method with specified K clusters [C]∥Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery Data Mining. New York, USA: ACM, 2019: 959-967.

BERKHIN P. A survey of clustering data mining techniques [M]∥Grouping Multidimensional Data. Cham, Germany: Springer, 2006: 25-71.

NG A Y, JORDAN M I, WEISS Y. On spectral clustering: analysis and an algorithm [C]∥Proceedings of the 14th International Conference on Neural Information Processing Systems. Palo Alto, CA, USA: AAAI, 2001: 849-856.

JAIN A K. Data clustering: 50 years beyond k-means [J]. Pattern Recognition Letters, 2010, 31(8): 651-666.

XU Wei, GONG Yihong. Document clustering by concept factorization [C]∥Proceedings of the 27th Annual International Conference on Research and Development in Information Retrieval. New York, USA: ACM, 2004: 202-209.

LEE D, SEUNG H S. Algorithms for non-negative matrix factorization [C]∥Proceedings of the 13th International Conference on Neural Information Processing Systems. Vancouver, Canada: NIPS, 2000: 556-562.

CHEN Mulin, LI Xuelong. Concept factorization with local centroids [J]. IEEE Transactions on Neural Networks and Learning Systems, 2020(10): 1-7.

HUANG Jin, NIE Feiping, HUANG Heng. Spectral rotation versus k-means in spectral clustering [C]∥Proceedings of the 27th AAAI Conference on Artificial Intelligence. Palo Alto, CA, USA: AAAI, 2013: 431-437.

NIE Feiping, WANG Xiaoqian, JORDAN M I, et al. The constrained Laplacian rank algorithm for graph-based clustering [C]∥Proceedings of the 30th AAAI Conference on Artificial Intelligence. Palo Alto, CA, USA: AAAI, 2016: 1969-1976.

WANG Hua, NIE Feiping, HUANG Heng, et al. Fast nonnegative matrix tri-factorization for large-scale data co-clustering [C]∥Proceedings of the 22nd International Joint Conference on Artificial Intelligence. California, USA: IJCAI, 2011: 1553-1558.

HAN Junwei, SONG Kun, NIE Feiping, et al. Bilateral k-means algorithm for fast co-clustering [C]∥Proceedings of the 31st AAAI Conference on Artificial Intelligence. Palo Alto, CA, USA: AAAI, 2017: 1969-1975.

CAI Deng, CHEN Xinlei. Large scale spectral clustering via landmark-based sparse representation [J]. IEEE Transactions on Cybernetics, 2015, 45(8): 1669-1680.

SHINNOU H, SASAKI M. Spectral clustering for a large data set by reducing the similarity matrix size [C]∥Proceedings of the 6th International Conference on Language Resources and Evaluation. Luxemburg: ELRA, 2008: 201-204.

CHEN W Y, SONG Yangqiu, BAI Hongjie, et al. Parallel spectral clustering in distributed systems [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(3): 568-586.

HE Ran, HU Baogang, ZHENG Weishi, et al. Robust principal component analysis based on maximum correntropy criterion [J]. IEEE Transactions on Image Processing, 2011, 20(6): 1485-1494.

PENG Chong, KANG Zhao, HU Yunhong, et al. Robust graph regularized nonnegative matrix factorization for clustering [J]. ACM Transactions on Knowledge Discovery from Data, 2017, 11(3): 1-30.

YAN Hui, LIU Siyu, YU P S. From joint feature selection and self-representation learning to robust multi-view subspace clustering [C]∥Proceedings of the 2019 IEEE International Conference on Data Mining. Piscataway, NJ, USA: IEEE, 2019: 1414-1419.

PRINCIPE J C. Information theoretic learning: Renyi's entropy and kernel perspectives [M]. Cham, Germany: Springer, 2010: 123-130.

HE Ran, ZHENG Weishi, HU Baogang. Maximum correntropy criterion for robust face recognition [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(8): 1561-1576.

LU Canyi, TANG Jinhui, LIN Min, et al. Correntropy induced L2 graph for robust subspace clustering [C]∥Proceedings of the 2013 IEEE International Conference on Computer Vision. Piscataway, NJ, USA: IEEE, 2013: 1801-1808.

ZHOU N, XU Y, CHENG H, et al. Maximum correntropy criterion-based sparse subspace learning for unsupervised feature selection [J]. IEEE Transactions on Circuits and Systems for Video Technology, 2017, 29(2): 404-417.

NIE Feiping, ZHU Wei, LI Xuelong. Unsupervised large graph embedding [C]∥Proceedings of the 31st AAAI Conference on Artificial Intelligence. Palo Alto, CA, USA: AAAI, 2017: 2422-2428.

CAI Deng, HE Xiaofei, WU Xiaoyun, et al. Non-negative matrix factorization on manifold [C]∥Proceedings of the 2008 8th IEEE International Conference on Data Mining. Piscataway, NJ, USA: IEEE, 2008: 63-72.

LECUN Y, BOTTOU L, BENGIO Y, et al. Gradient-based learning applied to document recognition [J]. Proceedings of the IEEE, 1998, 86(11): 2278-2324.

SEN P, NAMATA G, BILGIC M, et al. Collective classification in network data [J]. AI Magazine, 2008, 29(3): 93.

WU Mingrui, SCHÖLKOPF B. A local learning approach for clustering [C]∥Proceedings of the 19th International Conference on Neural Information Processing Systems. Vancouver, Canada: NIPS, 2006: 1529-1536.

JOHNSON D S, PAPADIMITRIOU C H, STEIGLITZ K. Combinatorial optimization: algorithms and complexity [J]. The American Mathematical Monthly, 1984, 91(3): 209.

STREHL A, GHOSH J. Cluster ensembles: a knowledge reuse framework for combining multiple partitions [J]. Journal of Machine Learning Research, 2002, 3(12): 583-617.

MANNING C D, RAGHAVAN P, SCHÜTZE H. An introduction to information retrieval [M]. New York, USA: Cambridge University Press, 2008: 139-162.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

隧道内燃料电池汽车氢气泄漏扩散特性及影响因素

语义区分和子图整合驱动的知识图谱表示学习方法

电动车辆间接热系统快速除湿响应迟滞机理及优化控制策略

超临界水异常区域热力学特性研究

冷库水平空气幕热湿阻隔性能数值模拟研究