基于证据空间有效性指标的聚类选择性集成

doi:10.11959/j.issn.1000-436x.2015146

摘要/Abstract

摘要：

首先针对距离空间在描述数据复杂结构信息方面的不足给出证据空间的概念。然后基于证据空间扩展有效性指标 Davies-Bouldin，同时利用聚类成员的类别相关矩阵度量差异性。最后以较高有效性和较大差异性为目标选择聚类成员并用于集成。实验结果显示所提方法能够有效提高聚类集成算法的有效性。

关键词: Davies-Bouldin指标, 证据空间, 聚类选择性集成, 互相关矩阵

Abstract:

At first,the concept of evidence space was proposed to overcome the weakness of distance space for describing the complex structure of data sets.And then,the Davies-Bouldin index was extended based on the evidence space proposed.Meanwhile the label-correlation matrix was used to measure the difference of clusters members.At last,the cluster members with better effectiveness and bigger differences were selected for cluster ensemble.The experimental results show that the proposed method is able to improve the effectiveness of cluster ensemble.

Key words: Davies-Bouldin index, evidence space, cluster ensemble selection, co-association matrix

毕凯,王晓丹,邢雅琼. 基于证据空间有效性指标的聚类选择性集成[J]. 通信学报, 2015, 36(8): 135-145.

Kai BI,Xiao-dan WANG,Ya-qiong XING. Cluster ensemble selection based on validity index in evidence space[J]. Journal on Communications, 2015, 36(8): 135-145.

图/表 9

图1

图2

表1

图3

表2

欧氏距离空间与证据空间量化对比"

数据集		距离空间			证据空间
数据集	SS	SD	$\frac{S S}{S D}$	SS	SD	$\frac{S S}{S D}$
iris	0.828 8	0.503 9	1.644 8	0.189 5	0.005 1	36.973
wine	0.644 3	0.440 0	1.464 3	0.186 1	0.004 2	43.991
soybean	0.527 2	0.305 8	1.723 7	0.095 4	0.013 6	6.998 9
sonar	0.486 2	0.463 1	1.049 8	0.082 5	0.040 4	2.043 8
ionosphere	0.637 1	0.539 8	1.180 3	0.154 0	0.039 3	3.920 0
vehicle	0.656 2	0.614 0	1.068 8	0.101 9	0.035 3	2.885 7
segment	0.778 3	0.536 9	1.450 0	0.305 8	0.0215	14.234
yeast1	0.798 3	0.743 1	1.074 3	0.120 8	0.048 8	2.478 0
2-ring	0.580 0	0.490 1	1.183 6	0.098 2	0	+∞
2-line	0.818 2	0.358 6	2.281 9	0.112 9	0	+∞
3-gauss	0.829 2	0.493 4	1.680 6	0.163 8	0.001 5	112.773
half-ring	0.767 9	0.282	2.720	0.100 6	0.000	5 030

表2

图4

图5

表3

表4

参考文献 16

[1]	ZHUANG W W , YE Y F , CHEN Y ,et al. Ensemble clustering for internet security applications[J]. IEEE Transactions on Systems,Man,and Cybernetics-Part C:Applications and Reviews, 2012,42(6): 1784-1796.
[2]	GLLAVATA J , QELI E , FREISLEBEN B . Detecting text in videos using fuzzy clustering ensembles[A]. Proc of 8th IEEE International Symposium on Multimedia[C]. 2006. 283-290.
[3]	卢志茂, 李纯, 张琦 . 近邻传播的文本聚类集成谱算法[J]. 哈尔滨工程大学学报, 2012,33(7): 899-905. LU Z M , LI C , ZHANG Q . A document cluster ensemble spectral algorithm based on affinity propagation[J]. Journal of Harbin Engineering University, 2012,33(7): 899-905.
[4]	邓晓政, 焦李成, 卢山 . 基于非负矩阵分解的谱聚类集成SAR图像分割[J]. 电子学报, 2011,39(12): 899-905. DENG X Z , JIAO L C , LU S . Spectral clustering ensemble applied to SAR image segmentation using nonnegative matrix factorization[J]. Acta electronica sinica, 2011,39(12): 899-905.
[5]	ALEXANDER S , JOYDEEP G . Cluster ensembles-a knowledge reuse framework for combining partitionings[A]. AAAI[C]. 2002. 93-98.
[6]	FRED A L N , JAIN A K . Combining multiple clusterings using evidence accumulation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005,27(6): 835-850.
[7]	TOPCHY A , JAIN A K , WILLIAM P . Clustering ensembles:models of consensus and weak partitions[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005,27(12): 1866-1881.
[8]	罗会兰, 孔繁胜, 李一啸 . 聚类集成中的差异性度量研究[J]. 计算机学报, 2007,30(8): 1315-1324. LUO H L , KONG F S , LI Y X . An analysis of diversity measures in clustering ensembles[J]. Chinese Journal of Computers, 2007,30(8): 1315-1324.
[9]	HADJITODOROV S T , KUNCHEVA L I , TODOROVA L P . Moderate diversity for better cluster ensembles[J]. Information Fusion, 2006,7: 264-275.
[10]	HONG Y , SAM K , WANG H L ,et al. Resampling-based selective clustering ensembles[J]. Pattern Recognition Letters, 2009,30: 298-305.
[11]	JIA J H , XIAO X , LIU B X ,et al. Bagging-based spectral clustering ensemble selection[J]. Pattern Recognition Letters, 2011,32: 1456-1467.
[12]	NALDI M C , CARVALHO A C P L F , CAMPELLO R J G B . Cluster ensemble selection based on relative validity indexes[J]. Data Min Knowl Disc, 2013,27: 259-289.
[13]	周林, 平西建, 徐森等 . 基于谱聚类的聚类集成算法[J]. 自动化学报, 2012,38(8): 1335-1342. ZHOU L , PING X J , XU S ,et al. Cluster ensemble based on spectral clustering[J]. Acta Automatica sinica, 2012,38(8): 1335-1342.
[14]	LOURENGCO A , BULO S R , FRED A ,et al. Consensus clustering with robust evidence accumulation[A]. EMMCVPR[C]. LNCS, 2013. 307-320.
[15]	DAVIES D L , BOULDIN D W . A cluster separation measure[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1979,1(2): 224-227.
[16]	ZHOU Z H , WU J X , TANG W . Ensembling neural networks:Many could be better than all[J]. Artificial Intelligence, 2002,137(1-2): 239-263.

数据集		选择规模：10			选择规模：20			选择规模：30
数据集	DB	NMI	DB^ES	DB	NMI	DB^ES	DB	NMI	DB^ES
iris	0.823 8	0.831 3	0.844 7	0.843 6	0.838 7	0.850 3	0.866 8	0.856 6	0.869 9
wine	0.899 4	0.916 3	0.912 8	0.909 9	0.917 9	0.920 2	0.912 9	0.913 7	0.915 4
soybean	0.588 3	0.585 6	0.595 9	0.590 8	0.585 0	0.587 3	0.586 5	0.585 2	0.586 9
sonar	0.540 9	0.616 0	0.639 9	0.563 7	0.601 1	0.567 1	0.580 0	0.571 4	0.565 8
ionosphere	0.633 0	0.628 2	0.627 4	0.615 8	0.624 3	0.630 2	0.607 0	0.625 5	0.620 2
vehicle	0.373 2	0.377 5	0.370 3	0.375 7	0.379 0	0.380 4	0.378 3	0.379 2	0.379 7
segment	0.550 5	0.621 3	0.551 2	0.581 0	0.633 6	0.591 5	0.577 7	0.629 6	0.587 1
yeast1	0.307 5	0.294 1	0.310 8	0.308 2	0.292 3	0.291 1	0.285 2	0.292 5	0.290 1
2-ring	0.693 7	1.000 0	1.000 0	0.919 2	1.000 0	1.000 0	1.000 0	1.000 0	1.000 0
2-line	1.000 0	1.000 0	1.000 0	1.000 0	1.000 0	1.000 0	1.000 0	1.000 0	1.000 0
3-gauss	0.949 6	0.968 9	0.966 1	0.966 2	0.971 3	0.968 0	0.971 7	0.971 3	0.970 9
half-ring	0.879 5	0.950 2	1.000 0	0.856 4	1.000 0	1.000 0	1.000 0	1.000 0	1.000 0

数据集		选择规模：10			选择规模：20			选择规模：30
数据集	DB	NMI	DB^ES	DB	NMI	DB^ES	DB	NMI	DB^ES
iris	0.904 1	0.902 8	0.912 7	0.904 1	0.913 9	0.908 2	0.867 9	0.865 6	0.899 3
wine	0.853 6	0.883 6	0.903 3	0.856 8	0.900 3	0.904 6	0.834 9	0.892 6	0.879 3
soybean	0.710 4	0.590 2	0.599 4	0.825 8	0.595 2	0.587 0	0.825 8	0.619 7	0.579 7
sonar	0.646 5	0.591 7	0.627 3	0.668 4	0.615 5	0.626 8	0.668 4	0.629 7	0.632 2
ionosphere	0.649 9	0.667 9	0.646 3	0.632 5	0.662 5	0.664 4	0.695 0	0.658 5	0.699 8
vehicle	0.382 2	0.385 7	0.384 2	0.379 7	0.356 2	0.382 2	0.374 4	0.347 7	0.344 3
segment	0.613 5	0.621 3	0.620 2	0.600 1	0.612 8	0.610 7	0.610 4	0.614 3	0.620 0
yeast1	0.303 1	0.307 3	0.343 2	0.343 1	0.274 0	0.291 9	0.311 1	0.288 9	0.315 7
2-ring	1.000 0	1.000 0	1.000 0	1.000 0	1.000 0	1.000 0	1.000 0	1.000 0	1.000 0
2-line	1.000 0	1.000 0	1.000 0	1.000 0	1.000 0	1.000 0	1.000 0	1.000 0	1.000 0
3-gauss	0.961 2	0.974 7	0.978 6	0.953 4	0.966 1	0.977 3	0.853 9	0.961 3	0.975 9
half-ring	1.000 0	1.000 0	1.000 0	1.000 0	1.000 0	1.000 0	1.000 0	1.000 0	1.000 0