基于夹角几何的I-niceMO增强算法

doi:10.16182/j.issn1004731x.joss.21-1333

系统仿真学报 ›› 2023, Vol. 35 ›› Issue (4): 797-808.doi: 10.16182/j.issn1004731x.joss.21-1333

• 论文 • 上一篇

基于夹角几何的I-niceMO增强算法

何一帆¹(), 何玉林¹^,²(), 蔡湧达¹, 黄哲学¹^,²

^1.深圳大学计算机与软件学院，广东深圳 518060
^2.深圳大学大数据系统计算技术国家工程实验室，广东深圳 518000

收稿日期:2021-12-23 修回日期:2022-02-09 出版日期:2023-04-29 发布日期:2023-04-12
通讯作者: 何玉林 E-mail:396981852@qq.com;yulinhe@gml.ac.cn
作者简介:何一帆(1997-)，男，硕士生，研究方向为数据挖掘和机器学习算法及其应用。E-mail：396981852@qq.com
基金资助:
国家自然科学基金面上项目(61972261);深圳市基础研究项目(JCY20210324093609026)

I-niceMO Enhanced Algorithm Based on Intersection Angel Geometry

Yifan He¹(), Yulin He¹^,²(), Yongda Cai¹, Zhexue Huang¹^,²

^1.College of Computer Science and Software Engineering, Shenzhen University, Shenzhen 518060, China
^2.National Engineering Laboratory for Big Data System Computing Technology, Shenzhen University, Shenzhen 518000, China

Received:2021-12-23 Revised:2022-02-09 Online:2023-04-29 Published:2023-04-12
Contact: Yulin He E-mail:396981852@qq.com;yulinhe@gml.ac.cn

摘要/Abstract

摘要：

针对I-niceMO算法在候选聚类中心合并时中心数目难以确定和中心点识别不准确的问题，提出了基于夹角几何的I-niceMO增强(I-niceMOEn)算法。利用观测点与数据点之间的距离和角度分布情况找出数据中尽可能多的候选聚类中心，以避免多类别数据聚类中出现的类别丢失的情况；利用谱聚类算法对候选聚类中心进行聚类，根据拉普拉斯矩阵特征值的大小自动地对候选聚类中心进行合并；根据合并后的聚类中心的数量确定最终的数据聚类类别数。I-niceMOEn算法实现了对数据类别数的自动确定，并且在聚类过程中不需要人为设置参数。实验结果表明：I-niceMOEn算法在收敛的同时能够获得优于传统自动聚类算法和I-niceMO算法的类中心确定表现。

关键词: 自动聚类, I-nice聚类, 谱聚类, 无监督学习, 观测点机制

Abstract:

To exactly determine the number of cluster centers and correctly identify the candidate cluster centers, an I-niceMO enhanced(I-niceMOEn) algorithm based on intersection angel geometry is proposed. As many distributions of intersection angles and distances as possible between observation points and data points are utilized to recognize the candidate cluster centers to avoid the neglection of cluster centers. The spectral clustering algorithm is used to automatically merge the candidate cluster centers according to the eigenvalues of Laplacian matrices. The number of final cluster centers is determined by the number of merged candidate cluster centers. The number of clusters can be automatically determined by I-niceMOEn algorithm and the manual parameter input for clustering is not needed. The experimental results show that I-niceMOEn algorithm is convergent and outperforms the traditional automatic clustering methods and I-niceMO algorithm.

Key words: automatic clustering, I-nice clustering, spectral clustering, unsupervised learning, observation point mechanism

中图分类号:

TP391

何一帆, 何玉林, 蔡湧达, 黄哲学. 基于夹角几何的I-niceMO增强算法[J]. 系统仿真学报, 2023, 35(4): 797-808.

Yifan He, Yulin He, Yongda Cai, Zhexue Huang. I-niceMO Enhanced Algorithm Based on Intersection Angel Geometry[J]. Journal of System Simulation, 2023, 35(4): 797-808.

图/表 15

图1

图2

图3

图4

图5

表1

表2

图6

图7

图8

图9

表3

表4

表5

表6

参考文献 27

1	Havens T C, Bezdek J C, Palaniswami M. Scalable Single Linkage Hierarchical Clustering for Big Data[C]//2013 IEEE Eighth International Conference on Intelligent Sensors, Sensor Networks and Information Processing. Melbourne, VIC, Australia: IEEE, 2013: 396-401.
2	金建国. 聚类方法综述[J]. 计算机科学, 2014, 41(增2): 288-293.
	Jin Jianguo. Review of Clustering Method[J]. Computer Science, 2014, 41(S2): 288-293.
3	Ma Z, Lai Y, Xie J, et al. Dirichlet Process Mixture of Generalized Inverted Dirichlet Distributions for Positive Vector Data with Extended Variational Inference[J]. IEEE Transactions on Neural Networks and Learning Systems(S1045-9227), 2021, 99: 1-14.
4	Masud M A, Huang J Z, Zhong M, et al. Generate Pairwise Constraints from Unlabeled Data for Semi-Supervised Clustering[J]. Data & Knowledge Engineering(S0169-023X), 2019, 123: 101715.
5	Meyer C, Race S, Valakuzhy K. Determining the Number of Clusters Via Iterative Consensus Clustering[C]//2013 SIAM International Conference on Data Mining. Texas, USA: Society for Industrial and Applied Mathematics, 2013: 94-102.
6	De Amorim R C, Hennig C. Recovering the Number of Clusters in Data Sets with Noise Features Using Feature Rescaling Factors[J]. Information Sciences(S0020-0255), 2015, 324: 126-145.
7	Thorndike R L. Who Belongs in the Family?[J]. Psychometrika(S0033-3123), 1953, 18(4): 267-276.
8	Rousseeuw P J. Silhouettes: A Graphical Aid to the Interpretation and Validation of Cluster Analysis[J]. Journal of Computational and Applied Mathematics(S0377-0427), 1987, 20: 53-65.
9	Sinaga K P, Yang M S. Unsupervised K-means Clustering Algorithm[J]. IEEE Access(S2169-3536), 2020, 8: 80716-80727.
10	贾瑞玉, 李玉功. 类簇数目和初始中心点自确定的K-means算法[J]. 计算机工程与应用, 2018, 54(7): 152-158.
	Jia Ruiyu, Li Yugong. K-means Algorithm of Clustering Number and Centers Self-Determination[J]. Computer Engineering and Applications, 2018, 54(7): 152-158.
11	Masud M A, Huang J Z, Wei C, et al. I-nice: A New Approach for Identifying the Number of Clusters and Initial Cluster Centres[J]. Information Sciences(S0020-0255), 2018, 466: 129-151.
12	He Y, Wu Y, Qin H, et al. Improved I-nice Clustering Algorithm Based on Density Peaks Mechanism[J]. Information Sciences(S0020-0255), 2021, 548: 177-190.
13	Ng A Y, Jordan M I, Weiss Y. On Spectral Clustering: Analysis and an Algorithm[C]//14th International Conference on Neural Information Processing Systems: Natural and Synthetic. Cambridge, MA, United States: MIT Press, 2001: 849-856.
14	Zhu X, Zhu Y, Zheng W. Spectral Rotation for Deep One-Step Clustering[J]. Pattern Recognition(S0031-3203), 2020, 105: 107175
15	Wen G. Robust Self-Tuning Spectral Clustering[J]. Neurocomputing(S0925-2312), 2020, 391: 243-248.
16	Vladimir Druskin, Mamonov Alexander V, Mikhail Zaslavsky. Distance Preserving Model Order Reduction of Graph-Laplacians and Cluster Analysis[J]. Journal of Scientific Computing(S0885-7474), 2022, 90(1): 1-30.
17	Jang J, Hitchcock D B. Model-Based Cluster Analysis of Democracies[J]. Journal of Data Science(S1683-8602), 2021, 10(2): 297-319.
18	Hastie T, Tibshirani R, Walther G. Estimating the Number of Data Clusters via the Gap Statistic[J]. Journal of the Royal Statistical Society Series B-Statistical Methodology(S1369-7412), 2001, 63: 411-423.
19	卢鹏丽, 才彦姣. 一种自动确定特征向量与类别数目的谱聚类算法[J]. 兰州理工大学学报, 2018, 44(2): 90-94.
	Lu Pengli, Cai Yanjiao. A Spectral Clustering Algorithm for Automatic Determination of Eigenvectors and Category Quantity[J]. Journal of Lanzhou University of Technology, 2018, 44(2): 90-94.
20	Wang Shuliang, Li Qi, Zhao Chuanfeng, et al. Extreme Clustering-A Clustering Method via Density Extreme Points[J]. Information Sciences(S0020-0255), 2020, 542: 24-39.
21	Campello R J G B, Kröger P, Sander J, et al. Density-Based Clustering[J]. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery(S1942-4787), 2020, 10(2): e1343.
22	Rodriguez A, Laio A. Clustering by Fast Search and Find of Density Peaks[J]. Science(S0036-8075), 2014, 344(6191): 1492-1496.
23	陈晋音, 何辉豪. 基于密度的聚类中心自动确定的混合属性数据聚类算法研究[J]. 自动化学报, 2015, 41(10): 1798-1813.
	Chen Jinyin, He Huihao. Research on Density-Based Clustering Algorithm for Mixed Data with Determine Cluster Centers Automatically[J]. Journal of Automatica Sinica, 2015, 41(10): 1798-1813.
24	Masud M A, Rahman M M, Bhadra S, et al. Improved K-Means Algorithm Using Density Estimation[C]//2019 International Conference on Sustainable Technologies for Industry 4.0(STI). Dhaka, Bangladesh: IEEE, 2019: 1-6.
25	Azhar M, Huang J Z, Masud M A, et al. A Hierarchical Gamma Mixture Model-Based Method for Estimating the Number of Clusters in Complex Data[J]. Applied Soft Computing(S1568-4946), 2020, 87: 105891.
26	Kang Z, Pan H, Hoi S C H, et al. Robust Graph Learning from Noisy Data[J]. IEEE Transactions on Cybernetics(S2168-2267), 2019, 50(5): 1833-1843.
27	Zelnik-Manor L, Perona P. Self-tuning Spectral Clustering[C]//17th International Conference on Neural Information Processing Systems. Cambridge, MA, United States: MIT Press, 2004: 1601-1608.

数据集	数据量	类别数	维度
Wine	178	3	13
Iris	150	3	4
Breast	569	2	30

数据集	类别数	Elbow	Silhouette	I-niceSO	I-niceMO	I-niceMOEn
Wine	3	7	2	2	5	3
Iris	3	6	2	2	4	3
Breast	2	6	2	4	6	2

数据集	类别数	I-niceSO/%	I-niceMO/%	I-niceMOEn/%
S1	10	72.9	87.1	100
S2	20	79.1	100	98.6
S3	30	82.6	100	99.3
S4	40	82.4	92.8	98.5
S5	10	91.0	100	100
S6	20	83.8	73.5	100
S7	30	76.3	100	100
S8	40	49.6	97.6	100

数据集	类别数	I-niceSO/%	I-niceMO/%	I-niceMOEn/%
Wine	3	68.5	85.0	96.0
Iris	3	66.6	95.0	88.0
Breast	2	87.7	85.9	89.5

基于夹角几何的I-niceMO增强算法

I-niceMO Enhanced Algorithm Based on Intersection Angel Geometry

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 15

参考文献 27

相关文章 1

编辑推荐

Metrics

本文评价

数据集	数据量	类别数	维度
S1	1 000	10	10
S2	2 000	20	10
S3	3 000	30	10
S4	4 000	40	10
S5	1 000	10	20
S6	2 000	20	20
S7	3 000	30	20
S8	4 000	40	20

数据集	类别数	Elbow	Silhouette	I-niceSO	I-niceMO	I-niceMOEn
S1	10	13	10	7	9	10
S2	20	28	19	15	20	20
S3	30	36	33	24	25	30
S4	40	56	46	34	37	40
S5	10	12	9	9	10	10
S6	20	25	18	17	18	20
S7	30	44	27	25	30	30
S8	40	56	41	24	39	40

数据集	类别数	Elbow	Silhouette	I-niceSO	I-niceMO	I-niceMOEn
S1	10	13	10	7	9	10
S2	20	28	19	15	20	20
S3	30	36	33	24	25	30
S4	40	56	46	34	37	40
S5	10	12	9	9	10	10
S6	20	25	18	17	18	20
S7	30	44	27	25	30	30
S8	40	56	41	24	39	40

数据集	类别数	Elbow	Silhouette	I-niceSO	I-niceMO	I-niceMOEn
S1	10	13	10	7	9	10
S2	20	28	19	15	20	20
S3	30	36	33	24	25	30
S4	40	56	46	34	37	40
S5	10	12	9	9	10	10
S6	20	25	18	17	18	20
S7	30	44	27	25	30	30
S8	40	56	41	24	39	40