Page 128 - 《软件学报》2021年第10期

3100 Journal of Software 软件学报 Vol.32, No.10, October 2021

Table 7 Comparisons of evaluationson the clustering results of the 6 real datasets by 8 indexes (Continued)
表 7 不同指标对 6 个真实数据集聚类结果的评测效果对比(续)
各个指标得到的最佳类簇数
数据集 K opt + + + +
I CSP STR DAS
Column2 2 3(137.797) 2(0.96067) 12(0.1985) 2(0.48024)
Heart 2 7(29.03838 2(0.19605) 2(0.04713) 2(0.38339)
German 2 2(29.1574) 2(0.73878) 3(0.02475) 2(0.30683)
Iris 3 3(1.28141) 2(0.72154) 2(0.42977) 3(0.15744)
Haberman 2 2(11.0046) 2(0.16917) 17(0.0423) 2(0.13945)
Tae 3 2(12.3131) 3(0.66232) 12(0.1186) 3(0.08332)
+
+
由表 7 可以看出,DAS 指标可以得到所有数据集的最佳类簇数.CH 指标可以得到 Iris 和 Tae 两个数据集的


最佳类簇数.COP 指标可以得到 Column2、German 和 Haberman 这 3 个数据集的最佳类簇数.DB 指标可以得
+
到 Heart、Iris 和 Haberman 这 3 个数据集的最佳类簇数.Dunn 指标可以得到 Column2、Heart 和 Haberman 这 3
+
+
个数据集的最佳类簇数.I 指标可以得到 German、Iris 和 Haberman 这 3 个数据集的最佳类簇数.CSP 指标的性
+
能相对较好,可以得到除 Iris 数据集以外其他 5 个数据集的最佳类簇数.STR 指标仅能得到 Heart 数据集的最佳
类簇数.
+
综合对 20 个不同类型的合成数据集和 6 个真实数据集的实验结果来看,DAS 指标比其他已有的 7 个指标
更具稳定性,它能够得到不同结构数据集的最佳类簇数.多种类型的数据集的实验结果表明,本文提出的 DAS +
具有良好的稳定性和有效性.
5 总 结
层次聚类算法虽然可以对多种形状的数据集进行聚类,但其时间复杂度较高;而 K-means 算法虽然收敛快,
但是对非凸型数据集的处理效果不好.本文将 K-means 算法和 AHC 算法处理数据集的思想相结合,提出了一种
新的 K-means-AHC 混合聚类算法.新算法首先利用 K-means 算法的思想,快速形成数据集的初始类簇;在初始类
簇的基础上,利用 AHC 算法的思想逐步合并初始类簇,直至形成数据集的最终划分.实验结果表明:K-means-
AHC 算法在聚类精度、时间开销和稳定性等方面均有较大幅度的提升.在聚类结果评价方面,本文基于拐点的
思想设计了一个新的 DAS 聚类有效性指标.针对不同类型数据集的实验结果表明,DAS 指标在稳定性上要优于
当前已有的经典聚类有效性指标.但是,在数据集中存在大量噪声点时,本文算法在精度上有所降低.因此,未来
的工作将集中在如何解决数据集噪声点的问题上.

References:
[1] Sun JG, Liu J, Zhao LY. Clustering algorithms research. Ruan Jian Xue Bao/Journal of Software, 2008,19(1):4861 (in Chinese
with English abstract). http://www.jos.org.cn/1000-9825/19/48.htm [doi: 10.3724/SP.J.1001.2008.00048]
[2] Mur A, Dormido R, Duro N, Dormido-Canto S, Vega J. Determination of the optimal number of clusters using a spectral clustering
optimization. Expert Systems with Applications, 2016,65:304314. [doi: 10.1016/j.eswa.2016.08.059]
[3] Xu DK, Tian YJ. A comprehensive survey of clustering algorithms. Annals of Data Science, 2015,2(2):165193. [doi: 10.1007/
s40745-015-0040-1]
[4] Jain AK. Data clustering: 50 years beyond K-means. Pattern Recognition Letters, 2010,31(8):651666. [doi: 10.1016/j.patrec.2009.
09.011]
[5] Zhou SB, Xu ZY, Liu F. Method for determining the optimal number of clusters based on agglomerative hierarchical clustering.
IEEE Trans. on Neural Networks and Learning Systems, 2017,28(12):30073017. [doi: 10.1109/TNNLS.2016.2608001]
[6] Olson CF. Parallel algorithms for hierarchical clustering. Parallel Computing, 1995,21(8):13131325. [doi: 10.1016/0167-8191(95)
00017-I]
[7] Zhou SB, ZY. A novel internal validity index based on the cluster center and the nearest neighbor cluster. Applied Soft Computing,
2018,71:7888. [doi: 10.1016/j.asoc.2018.06.033]