基于信念子簇切割的模糊聚类算法

doi:10.11772/j.issn.1001-9081.2023050610

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (4): 1128-1138.DOI: 10.11772/j.issn.1001-9081.2023050610

• 数据科学与技术 • 上一篇

基于信念子簇切割的模糊聚类算法

丁雨, 张瀚霖, 罗荣(), 孟华

西南交通大学数学学院，成都 611756

收稿日期:2023-05-22 修回日期:2023-07-06 接受日期:2023-07-14 发布日期:2023-08-01 出版日期:2024-04-10
通讯作者: 罗荣
作者简介:丁雨（1999—），女，四川成都人，硕士研究生，主要研究方向：机器学习、聚类分析
张瀚霖（1998—），男，四川武胜人，硕士研究生，主要研究方向：机器学习、数据的特征提取与降维、聚类分析
罗荣（1980—），男，四川巴中人，副教授，博士，主要研究方向：代数编码、数据挖掘 luorong@swjtu.edu.cn
孟华（1982—），男，河北邢台人，副教授，博士，CCF会员，主要研究方向：深度学习的可解释性、拓扑数据分析、知识表示与推理。
基金资助:
中央高校基本科研业务费专项资金资助项目(2682023ZTPY027)

Fuzzy clustering algorithm based on belief subcluster cutting

Yu DING, Hanlin ZHANG, Rong LUO(), Hua MENG

School of Mathematics，Southwest Jiaotong University，Chengdu Sichuan 611756，China

Received:2023-05-22 Revised:2023-07-06 Accepted:2023-07-14 Online:2023-08-01 Published:2024-04-10
Contact: Rong LUO
About author:DING Yu， born in 1999， M. S. candidate. Her research interests include machine learning， clustering analysis.
ZHANG Hanlin， born in 1998， M. S. candidate. His research interests include machine learning， feature extraction and dimensionality reduction of data， clustering analysis.
LUO Rong， born in 1980， Ph. D.， associate professor. His research interests include algebraic coding， data mining.
MENG Hua， born in 1982， Ph. D.， associate professor. His research interests include interpretability in deep learning， topological data analysis， knowledge representation and reasoning.
Supported by:
Fundamental Research Funds for Central Universities(2682023ZTPY027)

摘要/Abstract

摘要：

信念峰值聚类（BPC）算法是一种基于模糊视角的密度峰值聚类（DPC）算法的新变体，它用模糊数学的观点刻画数据的分布特征与相关性。但BPC算法的信念值计算主要基于局部数据点信息，未考察数据集整体的分布和结构，且原始的分配策略鲁棒性弱。针对以上问题，提出一种基于信念子簇切割的模糊聚类算法（BSCC），所提算法结合了信念峰值和谱方法。首先，通过局部信念信息将数据集划分为众多高纯度子簇；其次，将子簇视作新样本，通过簇间的相似关系，利用谱方法进行割图聚类，从而耦合局部信息与全局信息；最后，将子簇内的点分配至子簇所在类簇以完成最终聚类。与BPC算法相比，BSCC在带有多子簇结构的数据集上具有明显优势，如在americanflag数据集和Car数据集上的准确率（ACC）分别提高了16.38个百分点和21.35个百分点。在合成数据集和真实数据集上的聚类实验结果表明，BSCC在调整兰德系数（ARI）、归一化互信息（NMI）和ACC这3个评价指标上整体优于BPC和其他7种聚类算法。

关键词: 聚类分析, 密度峰值聚类, 信念峰值聚类, 谱聚类, 信念子簇, 子簇合并

Abstract:

Belief Peaks Clustering （BPC） algorithm is a new variant of Density Peaks Clustering （DPC） algorithm based on fuzzy perspective. It uses fuzzy mathematics to describe the distribution characteristics and correlation of data. However， BPC algorithm mainly relies on the information of local data points in the calculation of belief values， instead of investigating the distribution and structure of the whole dataset. Moreover， the robustness of the original allocation strategy is weak. To solve these problems， a fuzzy Clustering algorithm based on Belief Subcluster Cutting （BSCC） was proposed by combining belief peaks and spectral method. Firstly， the dataset was divided into many high-purity subclusters by local belief information. Then， the subcluster was regarded as a new sample， and the spectral method was used for cutting graph clustering through the similarity relationship between clusters， thus coupling local information and global information. Finally， the points in the subcluster were assigned to the class cluster where the subcluster was located to complete the final clustering. Compared with BPC algorithm， BSCC has obvious advantages on datasets with multiple subclusters， and it has the ACCuracy （ACC） improvement of 16.38 and 21.35 percentage points on americanflag dataset and Car dataset， respectively. Clustering experimental results on synthetic datasets and real datasets show that BSCC outperforms BPC and the other seven clustering algorithms on the three evaluation indicators of Adjusted Rand Index （ARI）， Normalized Mutual Information （NMI） and ACC.

Key words: clustering analysis, density peaks clustering, belief peaks clustering, spectral clustering, belief subcluster, subcluster merging

中图分类号:

TP181

丁雨, 张瀚霖, 罗荣, 孟华. 基于信念子簇切割的模糊聚类算法[J]. 计算机应用, 2024, 44(4): 1128-1138.

Yu DING, Hanlin ZHANG, Rong LUO, Hua MENG. Fuzzy clustering algorithm based on belief subcluster cutting[J]. Journal of Computer Applications, 2024, 44(4): 1128-1138.

图/表 12

图1 Bel?δ决策图示例

Fig. 1 Example of Bel?δ decision graph

图2 DPC和BPC算法在Jain数据集上的聚类效果对比

Fig. 2 Clustering effect comparison of DPC and BPC on Jain dataset

图3 3个合成数据集

Fig. 3 Three synthetic datasets

图4 BPC算法关于子簇数的纯度变化

Fig. 4 Relation between subcluster number and purity for BPC algorithm

图5 happy数据集的预聚类

Fig. 5 Preclustering of happy dataset

图6 共享最近邻居连接图

Fig. 6 Connection diagram of shared nearest neighbors

表1 数据集详情

Tab. 1 Details of datasets

类型	数据集	样本数	特征数	类别数
合成数据集	Aggregation	788	2	7
	R15	600	2	15
	Spiral	312	2	3
	Flame	240	2	2
	Jain	373	2	2
	circle	299	2	3
	happy	266	2	3
	Compound	499	2	6
	fourlines	600	2	4
	S1	5 000	2	15
真实数据集	Iris	150	4	3
	Car	1 728	6	4
	Seeds	210	7	3
	Pima	768	8	2
	Wine	178	13	3
	heartdisseaseh	294	13	5
	congressEW	435	16	2
	vote	435	16	2
	labo	57	16	2
	mfeat-fou	2 000	76	10
	semeionEW	1 593	256	10
	americanflag	873	892	3
	cactus	919	892	3
	worldmap	935	899	3
	leukemia	72	7 070	2

表2 9种聚类算法在10个合成数据集上的聚类性能

Tab. 2 Clustering performance of nine clustering algorithms on ten synthetic datasets

数据集	评价指标	BSCC	BPC	BPEC	FHC-LDP	DPC-DBFN	LDP-MST	DPC-KNN	DPC	SC
数据集	评价指标	$K$ / $k$	$K$	$K$	$k$	$k$	$d i m$	$k$	$d c$	$k$
Aggregation	ARI	0.995 6	0.781 1	0.687 4	1.000 0	0.992 7	0.995 6	0.995 6	0.754 8	0.978 3
	NMI	0.992 4	0.857 8	0.810 6	1.000 0	0.988 3	0.992 4	0.992 4	0.893 5	0.975 4
	ACC	0.997 5	0.785 5	0.821 1	1.000 0	0.996 2	0.997 5	0.997 5	0.818 5	0.989 8
	Arg-	30/4	15	25	6	30	2	21	2	4
R15	ARI	0.992 8	0.992 8	0.992 8	0.992 8	0.996 4	0.989 1	0.992 8	0.992 8	0.992 8
	NMI	0.994 2	0.994 2	0.994 2	0.994 2	0.997 1	0.991 3	0.994 2	0.994 2	0.994 2
	ACC	0.996 7	0.996 7	0.996 7	0.996 7	0.998 3	0.995 0	0.996 7	0.996 7	0.996 7
	Arg-	25/4	25	15	7	39	2	2	0.1	5
Spiral	ARI	1.000 0	0.235 9	0.007 5	1.000 0	0.148 7	1.000 0	1.000 0	1.000 0	1.000 0
	NMI	1.000 0	0.355 7	0.015 9	1.000 0	0.157 4	1.000 0	1.000 0	1.000 0	1.000 0
	ACC	1.000 0	0.669 9	0.381 4	1.000 0	0.554 5	1.000 0	1.000 0	1.000 0	1.000 0
	Arg-	10/3	50	85	3	4	2	6	2	2
Flame	ARI	1.000 0	1.000 0	0.511 7	1.000 0	0.966 6	0.933 9	1.000 0	0.586 1	0.950 1
	NMI	1.000 0	1.000 0	0.470 0	1.000 0	0.926 9	0.875 2	1.000 0	0.577 3	0.899 1
	ACC	1.000 0	1.000 0	0.858 3	1.000 0	0.991 7	0.983 3	1.000 0	0.883 3	0.987 5
	Arg-	25/3	70	45	7	6	2	4	0.1	4
Jain	ARI	1.000 0	0.662 3	0.537 6	1.000 0	0.800 8	1.000 0	0.757 7	0.714 6	1.000 0
	NMI	1.000 0	0.582 3	0.520 5	1.000 0	0.718 8	1.000 0	0.674 7	0.652 2	1.000 0
	ACC	1.000 0	0.916 9	0.868 6	1.000 0	0.951 7	1.000 0	0.941 0	0.924 9	1.000 0
	Arg-	10/5	10	90	7	43	2	37	0.5	4
circle	ARI	1.000 0	0.510 1	0.230 5	1.000 0	0.460 6	1.000 0	0.187 9	0.214 9	1.000 0
	NMI	1.000 0	0.664 9	0.367 2	1.000 0	0.639 6	1.000 0	0.323 0	0.345 5	1.000 0
	ACC	1.000 0	0.642 1	0.575 3	1.000 0	0.739 1	1.000 0	0.602 0	0.568 6	1.000 0
	Arg-	10/6	100	15	7	17	2	36	0.2	4
happy	ARI	1.000 0	1.000 0	0.526 2	1.000 0	0.522 1	1.000 0	0.717 9	0.601 7	1.000 0
	NMI	1.000 0	1.000 0	0.617 1	1.000 0	0.609 4	1.000 0	0.787 1	0.679 1	1.000 0
	ACC	1.000 0	1.000 0	0.815 8	1.000 0	0.815 8	1.000 0	0.898 5	0.849 6	1.000 0
	Arg-	10/5	45	15	8	2	2	17	0.1	4
Compound	ARI	0.844 3	0.777 5	0.766 6	0.848 3	0.808 7	0.833 8	0.808 7	0.546 0	0.533 7
	NMI	0.897 2	0.811 0	0.798 3	0.855 3	0.838 2	0.852 0	0.850 0	0.736 5	0.724 6
	ACC	0.854 6	0.814 5	0.774 4	0.882 2	0.852 1	0.807 0	0.869 7	0.666 7	0.646 6
	Arg-	45/3	25	15	5	5	2	3	1	21
S1	ARI	0.990 6	0.988 9	0.988 0	0.988 9	0.988 0	0.988 5	0.989 7	0.989 7	0.988 4
	NMI	0.990 3	0.989 0	0.988 6	0.988 9	0.987 8	0.988 7	0.989 6	0.989 6	0.988 8
	ACC	0.995 6	0.994 8	0.994 4	0.994 8	0.994 4	0.994 6	0.995 2	0.995 2	0.994 8
	Arg-	15/37	80	55	43	28	2	13	2	36
fourlines	ARI	1.000 0	0.704 0	1.000 0	1.000 0	0.831 1	1.000 0	0.789 0	0.546 5	1.000 0
	NMI	1.000 0	0.821 2	1.000 0	1.000 0	0.875 6	1.000 0	0.860 5	0.758 7	1.000 0
	ACC	1.000 0	0.745 0	1.000 0	1.000 0	0.933 3	1.000 0	0.855 0	0.650 0	1.000 0
	Arg-	10/7	30	55	9	35	2	5	0.1	6

表2 9种聚类算法在10个合成数据集上的聚类性能

Tab. 2 Clustering performance of nine clustering algorithms on ten synthetic datasets

数据集	评价指标	BSCC	BPC	BPEC	FHC-LDP	DPC-DBFN	LDP-MST	DPC-KNN	DPC	SC
数据集	评价指标	$K$ / $k$	$K$	$K$	$k$	$k$	$d i m$	$k$	$d c$	$k$
Aggregation	ARI	0.995 6	0.781 1	0.687 4	1.000 0	0.992 7	0.995 6	0.995 6	0.754 8	0.978 3
	NMI	0.992 4	0.857 8	0.810 6	1.000 0	0.988 3	0.992 4	0.992 4	0.893 5	0.975 4
	ACC	0.997 5	0.785 5	0.821 1	1.000 0	0.996 2	0.997 5	0.997 5	0.818 5	0.989 8
	Arg-	30/4	15	25	6	30	2	21	2	4
R15	ARI	0.992 8	0.992 8	0.992 8	0.992 8	0.996 4	0.989 1	0.992 8	0.992 8	0.992 8
	NMI	0.994 2	0.994 2	0.994 2	0.994 2	0.997 1	0.991 3	0.994 2	0.994 2	0.994 2
	ACC	0.996 7	0.996 7	0.996 7	0.996 7	0.998 3	0.995 0	0.996 7	0.996 7	0.996 7
	Arg-	25/4	25	15	7	39	2	2	0.1	5
Spiral	ARI	1.000 0	0.235 9	0.007 5	1.000 0	0.148 7	1.000 0	1.000 0	1.000 0	1.000 0
	NMI	1.000 0	0.355 7	0.015 9	1.000 0	0.157 4	1.000 0	1.000 0	1.000 0	1.000 0
	ACC	1.000 0	0.669 9	0.381 4	1.000 0	0.554 5	1.000 0	1.000 0	1.000 0	1.000 0
	Arg-	10/3	50	85	3	4	2	6	2	2
Flame	ARI	1.000 0	1.000 0	0.511 7	1.000 0	0.966 6	0.933 9	1.000 0	0.586 1	0.950 1
	NMI	1.000 0	1.000 0	0.470 0	1.000 0	0.926 9	0.875 2	1.000 0	0.577 3	0.899 1
	ACC	1.000 0	1.000 0	0.858 3	1.000 0	0.991 7	0.983 3	1.000 0	0.883 3	0.987 5
	Arg-	25/3	70	45	7	6	2	4	0.1	4
Jain	ARI	1.000 0	0.662 3	0.537 6	1.000 0	0.800 8	1.000 0	0.757 7	0.714 6	1.000 0
	NMI	1.000 0	0.582 3	0.520 5	1.000 0	0.718 8	1.000 0	0.674 7	0.652 2	1.000 0
	ACC	1.000 0	0.916 9	0.868 6	1.000 0	0.951 7	1.000 0	0.941 0	0.924 9	1.000 0
	Arg-	10/5	10	90	7	43	2	37	0.5	4
circle	ARI	1.000 0	0.510 1	0.230 5	1.000 0	0.460 6	1.000 0	0.187 9	0.214 9	1.000 0
	NMI	1.000 0	0.664 9	0.367 2	1.000 0	0.639 6	1.000 0	0.323 0	0.345 5	1.000 0
	ACC	1.000 0	0.642 1	0.575 3	1.000 0	0.739 1	1.000 0	0.602 0	0.568 6	1.000 0
	Arg-	10/6	100	15	7	17	2	36	0.2	4
happy	ARI	1.000 0	1.000 0	0.526 2	1.000 0	0.522 1	1.000 0	0.717 9	0.601 7	1.000 0
	NMI	1.000 0	1.000 0	0.617 1	1.000 0	0.609 4	1.000 0	0.787 1	0.679 1	1.000 0
	ACC	1.000 0	1.000 0	0.815 8	1.000 0	0.815 8	1.000 0	0.898 5	0.849 6	1.000 0
	Arg-	10/5	45	15	8	2	2	17	0.1	4
Compound	ARI	0.844 3	0.777 5	0.766 6	0.848 3	0.808 7	0.833 8	0.808 7	0.546 0	0.533 7
	NMI	0.897 2	0.811 0	0.798 3	0.855 3	0.838 2	0.852 0	0.850 0	0.736 5	0.724 6
	ACC	0.854 6	0.814 5	0.774 4	0.882 2	0.852 1	0.807 0	0.869 7	0.666 7	0.646 6
	Arg-	45/3	25	15	5	5	2	3	1	21
S1	ARI	0.990 6	0.988 9	0.988 0	0.988 9	0.988 0	0.988 5	0.989 7	0.989 7	0.988 4
	NMI	0.990 3	0.989 0	0.988 6	0.988 9	0.987 8	0.988 7	0.989 6	0.989 6	0.988 8
	ACC	0.995 6	0.994 8	0.994 4	0.994 8	0.994 4	0.994 6	0.995 2	0.995 2	0.994 8
	Arg-	15/37	80	55	43	28	2	13	2	36
fourlines	ARI	1.000 0	0.704 0	1.000 0	1.000 0	0.831 1	1.000 0	0.789 0	0.546 5	1.000 0
	NMI	1.000 0	0.821 2	1.000 0	1.000 0	0.875 6	1.000 0	0.860 5	0.758 7	1.000 0
	ACC	1.000 0	0.745 0	1.000 0	1.000 0	0.933 3	1.000 0	0.855 0	0.650 0	1.000 0
	Arg-	10/7	30	55	9	35	2	5	0.1	6

图7 9种算法在Jain数据集上的聚类结果

Fig. 7 Clustering results of nine algorithms on Jain dataset

图8 9种算法在Aggregation数据集上的聚类结果

Fig. 8 Clustering results of nine algorithms on Aggregation dataset

表3 9种聚类算法在15个真实数据集上的聚类性能

Tab. 3 Clustering performance of nine clustering algorithms on fifteen real-world datasets

数据集	评价指标	BSCC	BPC	BPEC	FHC-LDP	DPC-DBFN	LDP-MST	DPC-KNN	DPC	SC
数据集	评价指标	$K$ / $k$	$K$	$K$	$k$	$k$	$d i m$	$k$	$d c$	$k$
Iris	ARI	0.903 8	0.903 8	0.922 2	0.903 8	0.851 0	0.745 5	0.903 8	0.609 6	0.851 5
	NMI	0.885 1	0.885 1	0.901 1	0.885 1	0.836 6	0.798 0	0.885 1	0.705 1	0.862 2
	ACC	0.966 7	0.966 7	0.973 3	0.966 7	0.946 7	0.900 0	0.966 7	0.813 3	0.946 7
	Arg-	10/4	10	15	9	21	4	2	5	4
Car	ARI	0.429 2	0.181 8	0.117 0	0.147 5	0.153 5	-0.021 3	0.310 9	0.216 5	0.255 0
	NMI	0.295 5	0.220 0	0.170 8	0.123 7	0.101 6	0.161 5	0.249 4	0.328 6	0.255 0
	ACC	0.694 4	0.480 9	0.406 8	0.636 6	0.608 8	0.342 0	0.693 3	0.483 2	0.558 4
	Arg-	25/10	95	35	5	50	5	11	0.1	10
Seeds	ARI	0.797 0	0.789 5	0.715 1	0.728 9	0.766 4	0.570 2	0.766 4	0.744 8	0.826 1
	NMI	0.758 4	0.750 8	0.689 2	0.694 2	0.734 3	0.630 7	0.734 3	0.719 4	0.798 1
	ACC	0.928 6	0.923 8	0.895 2	0.900 0	0.914 3	0.819 0	0.914 3	0.904 8	0.938 1
	Arg-	15/5	30	50	12	2	5	4	0.1	4
Pima	ARI	0.149 7	0.013 1	0.072 0	0.014 3	0.078 5	0.019 6	0.014 3	0.141 2	0.085 3
	NMI	0.092 8	0.003 5	0.044 7	0.004 2	0.043 6	0.013 2	0.004 2	0.459 2	0.049 3
	ACC	0.696 6	0.648 4	0.636 7	0.649 7	0.651 0	0.658 9	0.649 7	0.516 9	0.649 7
	Arg-	45/49	25	40	7	46	4	2	0.1	45
Wine	ARI	0.865 1	0.834 9	0.848 5	0.726 9	0.831 8	0.362 7	0.726 9	0.672 4	0.914 9
	NMI	0.835 2	0.821 5	0.816 0	0.743 5	0.795 3	0.432 7	0.743 5	0.710 4	0.892 6
	ACC	0.955 1	0.943 8	0.949 4	0.904 5	0.943 8	0.713 5	0.904 5	0.882 0	0.971 9
	Arg-	15/20	55	30	17	3	2	17	2	15
heartdisseaseh	ARI	0.206 7	0.042 1	0.172 9	0.344 3	0.159 6	0.178 7	0.168 4	0.123 3	0.134 1
	NMI	0.170 9	0.101 6	0.187 3	0.181 5	0.191 7	0.112 7	0.160 1	0.177 8	0.170 8
	ACC	0.485 7	0.445 6	0.445 6	0.598 6	0.438 8	0.574 8	0.418 4	0.370 7	0.418 4
	Arg-	85/2	90	85	6	13	7	5	0.1	3
congressEW	ARI	0.650 1	0.628 1	0.037 1	0.536 7	0.536 3	0.557 2	0.613 5	0.564 1	0.592 1
	NMI	0.565 1	0.547 7	0.023 2	0.464 3	0.432 9	0.489 2	0.526 5	0.505 9	0.520 4
	ACC	0.903 4	0.896 6	0.600 0	0.866 7	0.866 7	0.873 6	0.892 0	0.875 9	0.885 1
	Arg-	30/3	30	10	23	2	15	4	2	9
vote	ARI	0.650 0	0.620 7	0	0.564 0	0.503 5	0.523 2	0.650 0	0.530 0	0.557 2
	NMI	0.551 6	0.532 1	0	0.475 8	0.463 7	0.441 7	0.544 7	0.459 5	0.489 2
	ACC	0.903 4	0.894 3	0.613 8	0.875 9	0.855 2	0.862 1	0.903 4	0.864 4	0.873 6
	Arg-	65/12	30	10	33	4	14	3	2	25
labo	ARI	0.359 0	0.317 3	0.283 3	0.275 4	0.073 4	0.035 8	0.275 4	0.241 6	0.243 7
	NMI	0.254 3	0.219 3	0.224 8	0.184 8	0.061 8	0.033 8	0.184 8	0.163 5	0.172 9
	ACC	0.807 0	0.789 5	0.771 9	0.771 9	0.649 1	0.614 0	0.771 9	0.754 4	0.754 4
	Arg-	25/6	35	45	12	2	7	24	0.5	39
mfeat-fou	ARI	0.463 5	0.305 7	0.359 0	0.470 8	0.145 0	0.685 5	0.331 9	0.363 1	0.533 0
	NMI	0.657 9	0.523 1	0.482 7	0.610 4	0.371 5	0.765 1	0.523 1	0.509 1	0.666 1
	ACC	0.630 0	0.431 5	0.550 5	0.639 0	0.310 5	0.789 5	0.484 0	0.523 5	0.675 4
	Arg-	10/28	100	50	15	6	50	4	0.5	4
semeionEW	ARI	0.488 2	0.407 7	0.304 0	0.525 9	0.299 7	0.446 7	0.220 2	0.266 2	0.567 0
	NMI	0.637 0	0.579 8	0.409 5	0.646 5	0.442 9	0.637 1	0.406 7	0.426 0	0.671 0
	ACC	0.661 0	0.531 1	0.534 8	0.699 3	0.480 2	0.630 3	0.317 6	0.425 6	0.671 7
	Arg-	15/12	90	70	18	3	15	48	0.2	3
americanflag	ARI	0.220 3	0.014 8	-0.014 3	0.070 1	-0.013 6	-0.020 1	0.028 3	0.077 3	0.011 5
	NMI	0.140 3	0.029 3	0.099 0	0.111 5	0.048 4	0.052 2	0.039 6	0.052 9	0.023 7
	ACC	0.627 7	0.463 9	0.429 6	0.572 7	0.378 0	0.529 2	0.423 8	0.497 1	0.568 7
	Arg-	20/5	25	40	21	6	3	5	2	3
cactus	ARI	0.246 1	0.010 3	0.102 6	0.149 1	0.193 6	0.188 8	0.134 7	0.060 1	0.013 2
	NMI	0.123 9	0.012 7	0.127 5	0.068 7	0.089 1	0.112 3	0.079 7	0.048 9	0.015 9
	ACC	0.706 2	0.664 9	0.526 7	0.638 7	0.669 2	0.707 3	0.697 5	0.551 7	0.666 7
	Arg-	30/5	10	25	11	20	6	2	0.1	6
worldmap	ARI	0.253 7	0.211 9	0.141 6	0.125 6	0.080 1	0.224 4	0.192 4	0.072 1	0.005 8
	NMI	0.142 6	0.109 8	0.042 3	0.129 3	0.021 7	0.120 2	0.083 1	0.038 8	0.012 3
	ACC	0.738 0	0.713 4	0.664 2	0.699 5	0.591 4	0.730 5	0.718 7	0.503 7	0.713 4
	Arg-	60/8	30	15	17	46	5	15	0.1	3
leukemia	ARI	0.547 6	0.395 0	0.268 5	0.381 7	0.159 5	0.292 2	0.347 2	0.105 2	0.117 2
	NMI	0.459 4	0.282 8	0.213 7	0.325 0	0.107 3	0.196 3	0.270 4	0.143 9	0.082 6
	ACC	0.875 0	0.819 4	0.763 9	0.819 4	0.708 3	0.777 8	0.805 6	0.708 3	0.680 6
	Arg-	20/2	10	50	9	43	26	4	1	7

表3 9种聚类算法在15个真实数据集上的聚类性能

Tab. 3 Clustering performance of nine clustering algorithms on fifteen real-world datasets

数据集	评价指标	BSCC	BPC	BPEC	FHC-LDP	DPC-DBFN	LDP-MST	DPC-KNN	DPC	SC
数据集	评价指标	$K$ / $k$	$K$	$K$	$k$	$k$	$d i m$	$k$	$d c$	$k$
Iris	ARI	0.903 8	0.903 8	0.922 2	0.903 8	0.851 0	0.745 5	0.903 8	0.609 6	0.851 5
	NMI	0.885 1	0.885 1	0.901 1	0.885 1	0.836 6	0.798 0	0.885 1	0.705 1	0.862 2
	ACC	0.966 7	0.966 7	0.973 3	0.966 7	0.946 7	0.900 0	0.966 7	0.813 3	0.946 7
	Arg-	10/4	10	15	9	21	4	2	5	4
Car	ARI	0.429 2	0.181 8	0.117 0	0.147 5	0.153 5	-0.021 3	0.310 9	0.216 5	0.255 0
	NMI	0.295 5	0.220 0	0.170 8	0.123 7	0.101 6	0.161 5	0.249 4	0.328 6	0.255 0
	ACC	0.694 4	0.480 9	0.406 8	0.636 6	0.608 8	0.342 0	0.693 3	0.483 2	0.558 4
	Arg-	25/10	95	35	5	50	5	11	0.1	10
Seeds	ARI	0.797 0	0.789 5	0.715 1	0.728 9	0.766 4	0.570 2	0.766 4	0.744 8	0.826 1
	NMI	0.758 4	0.750 8	0.689 2	0.694 2	0.734 3	0.630 7	0.734 3	0.719 4	0.798 1
	ACC	0.928 6	0.923 8	0.895 2	0.900 0	0.914 3	0.819 0	0.914 3	0.904 8	0.938 1
	Arg-	15/5	30	50	12	2	5	4	0.1	4
Pima	ARI	0.149 7	0.013 1	0.072 0	0.014 3	0.078 5	0.019 6	0.014 3	0.141 2	0.085 3
	NMI	0.092 8	0.003 5	0.044 7	0.004 2	0.043 6	0.013 2	0.004 2	0.459 2	0.049 3
	ACC	0.696 6	0.648 4	0.636 7	0.649 7	0.651 0	0.658 9	0.649 7	0.516 9	0.649 7
	Arg-	45/49	25	40	7	46	4	2	0.1	45
Wine	ARI	0.865 1	0.834 9	0.848 5	0.726 9	0.831 8	0.362 7	0.726 9	0.672 4	0.914 9
	NMI	0.835 2	0.821 5	0.816 0	0.743 5	0.795 3	0.432 7	0.743 5	0.710 4	0.892 6
	ACC	0.955 1	0.943 8	0.949 4	0.904 5	0.943 8	0.713 5	0.904 5	0.882 0	0.971 9
	Arg-	15/20	55	30	17	3	2	17	2	15
heartdisseaseh	ARI	0.206 7	0.042 1	0.172 9	0.344 3	0.159 6	0.178 7	0.168 4	0.123 3	0.134 1
	NMI	0.170 9	0.101 6	0.187 3	0.181 5	0.191 7	0.112 7	0.160 1	0.177 8	0.170 8
	ACC	0.485 7	0.445 6	0.445 6	0.598 6	0.438 8	0.574 8	0.418 4	0.370 7	0.418 4
	Arg-	85/2	90	85	6	13	7	5	0.1	3
congressEW	ARI	0.650 1	0.628 1	0.037 1	0.536 7	0.536 3	0.557 2	0.613 5	0.564 1	0.592 1
	NMI	0.565 1	0.547 7	0.023 2	0.464 3	0.432 9	0.489 2	0.526 5	0.505 9	0.520 4
	ACC	0.903 4	0.896 6	0.600 0	0.866 7	0.866 7	0.873 6	0.892 0	0.875 9	0.885 1
	Arg-	30/3	30	10	23	2	15	4	2	9
vote	ARI	0.650 0	0.620 7	0	0.564 0	0.503 5	0.523 2	0.650 0	0.530 0	0.557 2
	NMI	0.551 6	0.532 1	0	0.475 8	0.463 7	0.441 7	0.544 7	0.459 5	0.489 2
	ACC	0.903 4	0.894 3	0.613 8	0.875 9	0.855 2	0.862 1	0.903 4	0.864 4	0.873 6
	Arg-	65/12	30	10	33	4	14	3	2	25
labo	ARI	0.359 0	0.317 3	0.283 3	0.275 4	0.073 4	0.035 8	0.275 4	0.241 6	0.243 7
	NMI	0.254 3	0.219 3	0.224 8	0.184 8	0.061 8	0.033 8	0.184 8	0.163 5	0.172 9
	ACC	0.807 0	0.789 5	0.771 9	0.771 9	0.649 1	0.614 0	0.771 9	0.754 4	0.754 4
	Arg-	25/6	35	45	12	2	7	24	0.5	39
mfeat-fou	ARI	0.463 5	0.305 7	0.359 0	0.470 8	0.145 0	0.685 5	0.331 9	0.363 1	0.533 0
	NMI	0.657 9	0.523 1	0.482 7	0.610 4	0.371 5	0.765 1	0.523 1	0.509 1	0.666 1
	ACC	0.630 0	0.431 5	0.550 5	0.639 0	0.310 5	0.789 5	0.484 0	0.523 5	0.675 4
	Arg-	10/28	100	50	15	6	50	4	0.5	4
semeionEW	ARI	0.488 2	0.407 7	0.304 0	0.525 9	0.299 7	0.446 7	0.220 2	0.266 2	0.567 0
	NMI	0.637 0	0.579 8	0.409 5	0.646 5	0.442 9	0.637 1	0.406 7	0.426 0	0.671 0
	ACC	0.661 0	0.531 1	0.534 8	0.699 3	0.480 2	0.630 3	0.317 6	0.425 6	0.671 7
	Arg-	15/12	90	70	18	3	15	48	0.2	3
americanflag	ARI	0.220 3	0.014 8	-0.014 3	0.070 1	-0.013 6	-0.020 1	0.028 3	0.077 3	0.011 5
	NMI	0.140 3	0.029 3	0.099 0	0.111 5	0.048 4	0.052 2	0.039 6	0.052 9	0.023 7
	ACC	0.627 7	0.463 9	0.429 6	0.572 7	0.378 0	0.529 2	0.423 8	0.497 1	0.568 7
	Arg-	20/5	25	40	21	6	3	5	2	3
cactus	ARI	0.246 1	0.010 3	0.102 6	0.149 1	0.193 6	0.188 8	0.134 7	0.060 1	0.013 2
	NMI	0.123 9	0.012 7	0.127 5	0.068 7	0.089 1	0.112 3	0.079 7	0.048 9	0.015 9
	ACC	0.706 2	0.664 9	0.526 7	0.638 7	0.669 2	0.707 3	0.697 5	0.551 7	0.666 7
	Arg-	30/5	10	25	11	20	6	2	0.1	6
worldmap	ARI	0.253 7	0.211 9	0.141 6	0.125 6	0.080 1	0.224 4	0.192 4	0.072 1	0.005 8
	NMI	0.142 6	0.109 8	0.042 3	0.129 3	0.021 7	0.120 2	0.083 1	0.038 8	0.012 3
	ACC	0.738 0	0.713 4	0.664 2	0.699 5	0.591 4	0.730 5	0.718 7	0.503 7	0.713 4
	Arg-	60/8	30	15	17	46	5	15	0.1	3
leukemia	ARI	0.547 6	0.395 0	0.268 5	0.381 7	0.159 5	0.292 2	0.347 2	0.105 2	0.117 2
	NMI	0.459 4	0.282 8	0.213 7	0.325 0	0.107 3	0.196 3	0.270 4	0.143 9	0.082 6
	ACC	0.875 0	0.819 4	0.763 9	0.819 4	0.708 3	0.777 8	0.805 6	0.708 3	0.680 6
	Arg-	20/2	10	50	9	43	26	4	1	7

图9 BSCC在4个数据集上随最近邻K和k值改变的ACC值变化

Fig. 9 ACC value of BSCC algorithm changing with values of nearest neighbors K and k on four datasets

参考文献 45

1	HAN J， KAMBER M， PEI J. 数据挖掘：概念与技术［M］. 范明，孟小峰，译.北京：机械工业出版社，2012：196-222. 10.1016/b978-0-12-381479-1.00005-8
	HAN J， KAMBER M， PEI J. Data Mining： Concept and Technology ［M］. FAN M， MENG X F， translated. Beijing： China Machine Press， 2012： 196-222. 10.1016/b978-0-12-381479-1.00005-8
2	XIA Y， NIE L， ZHANG L， et al. Weakly supervised multilabel clustering and its applications in computer vision ［J］. IEEE Transactions on Cybernetics， 2016， 46（12）： 3220-3232. 10.1109/tcyb.2015.2501385
3	SONG Q， WU C， TIAN X， et al. A novel self-learning weighted fuzzy local information clustering algorithm integrating local and non-local spatial information for noise image segmentation ［J］. Applied Intelligence， 2022， 52： 6376-6397. 10.1007/s10489-021-02722-7
4	ARNARSSON I Ö， FROST O， GUSTAVSSON E， et al. Natural language processing methods for knowledge management — applying document clustering for fast search and grouping of engineering documents ［J］. Concurrent Engineering， 2021， 29（2）： 142-152. 10.1177/1063293x20982973
5	CHAKRABARTI S. Data mining for hypertext： a tutorial survey ［J］. ACM SIGKDD Explorations Newsletter， 2000， 1（2）： 1-11. 10.1145/846183.846187
6	JOLLIFFE I T， CADIMA J. Principal component analysis： a review and recent developments ［J］. Philosophical Transactions of the Royal Society A： Mathematical， Physical and Engineering Sciences， 2016， 374（2065）： 20150202. 10.1098/rsta.2015.0202
7	H-S PARK， C-H JUN. A simple and fast algorithm for K-medoids clustering ［J］. Expert Systems with Applications， 2009， 36（2）： 3336-3341. 10.1016/j.eswa.2008.01.039
8	ESTER M， H-P KRIEGEL， SANDER J， et al. A density-based algorithm for discovering clusters in large spatial databases with noise ［C］// Proceedings of the Second International Conference on Knowledge Discovery and Data Mining. Palo Alto： AAAI Press， 1996： 226-231.
9	ANKERST M， BREUNIG M M， H-P KRIEGEL， et al. OPTICS： ordering points to identify the clustering structure ［J］. ACM SIGMOD Record， 1999， 28（2）： 49-60. 10.1145/304181.304187
10	ZHANG T， RAMAKRISHNAN R， LIVNY M. BIRCH： an efficient data clustering method for very large databases ［J］. ACM SIGMOD Record， 1996， 25（2）： 103-114. 10.1145/235968.233324
11	GUHA S， RASTOGI R， SHIM K. CURE： an efficient clustering algorithm for large databases ［J］. ACM SIGMOD Record， 1998， 27（2）： 73-84. 10.1145/276305.276312
12	WANG W， YANG J， MUNTZ R R. STING： a statistical information grid approach to spatial data mining ［C］// Proceedings of 23rd International Conference on Very Large Data Bases. San Francisco， CA： Morgan Kaufmann Publishers Inc.， 1997： 186-195.
13	AGRAWAL R， GEHRKE J， GUNOPULOS D， et al. Automatic subspace clustering of high dimensional data for data mining applications ［C］// Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data. New York： ACM， 1998： 94-105. 10.1145/276305.276314
14	RASMUSSEN C. The infinite Gaussian mixture model ［J］. Advances in Neural Information Processing Systems， 1999， 12： 554-560.
15	KOHONEN T. The self-organizing map ［J］. Proceedings of the IEEE， 1990， 78（9）： 1464-1480. 10.1109/5.58325
16	LUXBURG U. A tutorial on spectral clustering ［J］. Statistics and Computing， 2007， 17（4）： 395-416. 10.1007/s11222-007-9033-z
17	SI X， YIN Q， ZHAO X， et al. Robust deep multi-view subspace clustering networks with a correntropy-induced metric ［J］. Applied Intelligence， 2022， 52（13）： 14871-14887. 10.1007/s10489-022-03209-9
18	NIE F， WANG X， JORDAN M， et al. The constrained laplacian rank algorithm for graph-based clustering ［J］. Proceedings of the AAAI Conference on Artificial Intelligence， 2016， 30（1）： 1969-1976. 10.1609/aaai.v30i1.10302
19	BAO H Q， VAN HOAI T. A deep embedded clustering algorithm for the binning of metagenomic sequences ［J］. IEEE Access， 2022， 10： 54348-54357. 10.1109/access.2022.3176954
20	RODRIGUEZ A， LAIO A. Clustering by fast search and find of density peaks ［J］. Science， 2014， 344（6191）： 1492-1496. 10.1126/science.1242072
21	TONG W， LIU S， GAO X-Z. A density-peak-based clustering algorithm of automatically determining the number of clusters ［J］. Neurocomputing， 2021， 458： 655-666. 10.1016/j.neucom.2020.03.125
22	DU H， HAO Y， WANG Z. An improved density peaks clustering algorithm by automatic determination of cluster centres ［J］. Connection Science， 2022， 34（1）： 857-873. 10.1080/09540091.2021.2012422
23	DU M， DING S， JIA H. Study on density peaks clustering based on k-nearest neighbors and principal component analysis ［J］. Knowledge-Based Systems， 2016， 99： 135-145. 10.1016/j.knosys.2016.02.001
24	LIU R， WANG H， YU X. Shared-nearest-neighbor-based clustering by fast search and find of density peaks ［J］. Information Sciences， 2018， 450： 200-226. 10.1016/j.ins.2018.03.031
25	GUAN J， LI S， HE X， et al. Fast hierarchical clustering of local density peaks via an association degree transfer method ［J］. Neurocomputing， 2021， 455： 401-418. 10.1016/j.neucom.2021.05.071
26	CHENG D， ZHU Q， HUANG J， et al. Clustering with local density peaks-based minimum spanning tree ［J］. IEEE Transactions on Knowledge and Data Engineering， 2021， 33（2）： 374-387. 10.1109/tkde.2019.2930056
27	巩树凤，张岩峰.EDDPC：一种高效的分布式密度中心聚类算法［J］.计算机研究与发展，2016，53（6）：1400-1409. 10.7544/issn1000-1239.2016.20150616
	GONG S F， ZHANG Y F. EDDPC： an efficient distributed density peaks clustering algorithm［J］. Journal of Computer Research and Development， 2016， 53（6）： 1400-1409. 10.7544/issn1000-1239.2016.20150616
28	徐晓，丁世飞，孙统风，等.基于网格筛选的大规模密度峰值聚类算法［J］.计算机研究与发展，2018，55（11）：2419-2429. 10.7544/issn1000-1239.2018.20170227
	XU X， DING S F， SUN T F， et al. Large-scale density peaks clustering algorithm based on grid screening ［J］. Journal of Computer Research and Development， 2018， 55（11）： 2419-2429. 10.7544/issn1000-1239.2018.20170227
29	BEZDEK J C， EHRLICH R， FULL W. FCM： the fuzzy c-means clustering algorithm ［J］. Computers & Geosciences， 1984， 10（2/3）： 191-203. 10.1016/0098-3004(84)90020-7
30	LEI T， JIA X， ZHANG Y， et al. Superpixel-based fast fuzzy C-means clustering for color image segmentation ［J］. IEEE Transactions on Fuzzy Systems， 2019， 27（9）： 1753-1766. 10.1109/tfuzz.2018.2889018
31	TANG Y， REN F， PEDRYCZ W. Fuzzy C-means clustering through SSIM and patch for image segmentation ［J］. Applied Soft Computing， 2020， 87： 105928. 10.1016/j.asoc.2019.105928
32	M-H MASSON， DENOEUX T. ECM： an evidential version of the fuzzy c-means algorithm ［J］. Pattern Recognition， 2008， 41（4）： 1384-1397. 10.1016/j.patcog.2007.08.014
33	DENOEUX T， KANJANATARAKUL O. Evidential clustering： a review ［C］// Proceedings of the 15th International Symposium on Integrated Uncertainty in Knowledge Modelling and Decision Making. Cham： Springer， 2016： 24-35. 10.1007/978-3-319-49046-5_3
34	XIE J， GAO H， XIE W， et al. Robust clustering by detecting density peaks and assigning points based on fuzzy weighted K-nearest neighbors ［J］. Information Sciences， 2016， 354： 19-40. 10.1016/j.ins.2016.03.011
35	LOTFI A， MORADI P， BEIGY H. Density peaks clustering based on density backbone and fuzzy neighborhood ［J］. Pattern Recognition， 2020， 107： 107449. 10.1016/j.patcog.2020.107449
36	BIAN Z， F-L CHUNG， WANG S. Fuzzy density peaks clustering ［J］. IEEE Transactions on Fuzzy Systems， 2021， 29（7）： 1725-1738. 10.1109/tfuzz.2020.2985004
37	SU Z-G， DENOEUX T. BPEC： belief-peaks evidential clustering ［J］. IEEE Transactions on Fuzzy Systems， 2019， 27（1）： 111-123. 10.1109/tfuzz.2018.2869125
38	GONG C， SU Z-G， WANG P-H， et al. An evidential clustering algorithm by finding belief-peaks and disjoint neighborhoods ［J］. Pattern Recognition， 2021， 113： 107751. 10.1016/j.patcog.2020.107751
39	GONG C， SU Z-G， WANG P-H， et al. Cumulative belief peaks evidential K-nearest neighbor clustering ［J］. Knowledge-Based Systems， 2020， 200： No. 105982. 10.1016/j.knosys.2020.105982
40	MENG J， FU D， TANG Y. Belief-peaks clustering based on fuzzy label propagation ［J］. Applied Intelligence， 2020， 50（4）： 1259-1271. 10.1007/s10489-019-01576-4
41	SHAFER G. A mathematical Theory of Evidence ［M］. Princeton： Princeton University Press， 1976： 39-40.
42	LONG Z， GAO Y， MENG H， et al. Clustering based on local density peaks and graph cut ［J］. Information Sciences， 2022， 600： 263-286. 10.1016/j.ins.2022.03.091
43	XU W， LIU X， GONG Y. Document clustering based on non-negative matrix factorization ［C］// Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM， 2003： 267-273. 10.1145/860435.860485
44	YANG Y， XU D， NIE F， et al. Image clustering using local discriminant models and global integration ［J］. IEEE Transactions on Image Processing， 2010， 19（10）： 2761-2773. 10.1109/tip.2010.2049235
45	STEINLEY D. Properties of the Hubert-Arable adjusted rand index ［J］. Psychological Methods， 2004， 9（3）： 386-396. 10.1037/1082-989x.9.3.386

[1]	郭茂祖, 张雅喆, 赵玲玲. 基于空间语义和个体活动的电动汽车充电站选址方法[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2819-2827.
[2]	马志峰, 于俊洋, 王龙葛. 多样性表示的深度子空间聚类算法[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 407-412.
[3]	李文博, 刘波, 陶玲玲, 罗棻, 张航. L1正则化的深度谱聚类算法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3662-3667.
[4]	李文全, 毛伊敏, 彭新东. 基于犹豫模糊集的凝聚式层次聚类算法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3755-3763.
[5]	赖星锦, 郑致远, 杜晓颜, 徐莎, 杨晓君. 基于超像素锚图二重降维的高光谱聚类算法[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2088-2093.
[6]	杜洁, 马燕, 黄慧. 基于局部引力和距离的聚类算法[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1472-1479.
[7]	李由之, 胡志华, 陈春, 杨培蓓, 董雅静. 基于双长短期记忆网络组合的网络货运平台成交定价预测模型[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1616-1623.
[8]	张琦, 郑伯川, 张征, 周欢欢. 基于随机分块的稀疏子空间聚类方法[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1148-1154.
[9]	祝承, 赵晓琦, 赵丽萍, 焦玉宏, 朱亚飞, 陈建英, 周伟, 谭颖. 基于谱聚类半监督特征选择的功能磁共振成像数据分类[J]. 计算机应用, 2021, 41(8): 2288-2293.
[10]	戴嫣然, 戴国庆, 袁玉波. 基于肤色学习的多人脸前景抽取方法[J]. 计算机应用, 2021, 41(6): 1659-1666.
[11]	郭佳, 韩李涛, 孙宪龙, 周丽娟. 自动确定聚类中心的比较密度峰值聚类算法[J]. 计算机应用, 2021, 41(3): 738-744.
[12]	吕佳, 鲜焱. 结合改进密度峰值聚类和共享子空间的协同训练算法[J]. 计算机应用, 2021, 41(3): 686-693.
[13]	高冉, 陈花竹. 改进的基于谱聚类的子空间聚类模型[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3645-3651.
[14]	陈港, 孟相如, 康巧燕, 阳勇. 基于拓扑分割与聚类分析的虚拟软件定义网络映射算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3309-3318.
[15]	李杏峰, 黄玉清, 任珍文. 联合低秩稀疏的多核子空间聚类算法[J]. 计算机应用, 2020, 40(6): 1648-1653.

基于信念子簇切割的模糊聚类算法

Fuzzy clustering algorithm based on belief subcluster cutting

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 45

相关文章 15

编辑推荐

Metrics