一种采用新型聚类方法的最佳类簇数确定算法-朱二周，孙悦，张远翔，高新，马汝辉，李学俊.pdf

上善若水

403

19页

5次

2022-05-26

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2021,32(10):30853103 [doi: 10.13328/j.cnki.jos.006016] http://www.jos.org.cn

一种采用新型聚类方法的最佳类簇数确定算法





朱二周

1,2

孙

悦

张远翔

高

新

马汝辉

李学俊

(计算智能与信号处理教育部重点实验室(安徽大学),安徽合肥 230601)

(安徽大学计算机科学与技术学院,安徽合肥 230601)

(上海交通大学电子信息与电气工程学院,上海 200240)

通讯作者: 朱二周, E-mail: ezzhu@ahu.edu.cn

摘要: 聚类分析是统计学、模式识别和机器学习等领域的研究热点.通过有效的聚类分析,数据集的内在结构与

特征可以被很好地发掘出来.然而,无监督学习的特性使得当前已有的聚类方法依旧面临着聚类效果不稳定、无法

对多种结构的数据集进行正确聚类等问题.针对这些问题,首先将 K-means 算法和层次聚类算法的聚类思想相结合,

提出了一种混合聚类算法 K-means-AHC;其次,采用拐点检测的思想,提出了一个基于平均综合度的新聚类有效性

指标 DAS(平均综合度之差,difference of average synthesis degree),以此来评估 K-means-AHC 算法聚类结果的质量;

最后,将 K-means-AHC 算法和 DAS 指标相结合,设计了一种寻找数据集最佳类簇数和最优划分的有效方法.实验将

K-means-AHC 算法用于测试多种结构的数据集,结果表明:该算法在不过多增加时间开销的同时,提高了聚类分析

的准确性.与此同时,新的 DAS 指标在聚类结果的评价上要优于当前已有的常用聚类有效性指标.

关键词: 聚类分析;聚类算法;聚类有效性指标;最佳类簇数;数据挖掘

中图法分类号: TP181

中文引用格式: 朱二周,孙悦,张远翔,高新,马汝辉,李学俊.一种采用新型聚类方法的最佳类簇数确定算法.软件学报,2021,

32(10):30853103. http://www.jos.org.cn/1000-9825/6016.htm

英文引用格式: Zhu EZ, Sun Y, Zhang YX, Gao X, Ma RH, Li XJ. Optimal clustering number determining algorithm by the new

clustering method. Ruan Jian Xue Bao/Journal of Software, 2021,32(10):30853103 (in Chinese). http://www.jos.org.cn/1000-

9825/6016.htm

Optimal Clustering Num ber Determining Algorithm by the New Clustering Method

ZHU Er-Zhou

1,2

, SUN Yue

, ZHANG Yuan-Xiang

, GAO Xin

, MA Ru-Hui

, LI Xue-Jun

(Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, Anhui University, Hefei 230601, China)

(School of Computer Science and Technology, Anhui University, Hefei 230601, China)

(School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China)

Abstra ct : Clustering analysis is a hot research topic in the fields of statistics, pattern recognition, and machine learning. Through

effective clustering analysis, the intrinsic structure and characteristics of datasets can be well discovered. However, due to the

unsupervised learning feature, the existing clustering methods are still facing the problems of unstable and inaccurate on processing

different types of datasets. In order to solve these problems, a hybrid clustering algorithm, K-means-AHC, is firstly proposed based on the

combination of the K-means algorithm and the hierarchical clustering algorithm. Then, based on the inflexion point detection, a new

clustering validity index, DAS (difference of average synthesis degree), is proposed to evaluate the results of the K-means-AHC clustering

algorithm. Finally, through the combination of the K-means-AHC algorithm and the DAS index, an effective method of finding the

optimal clustering numbers and optimal partitions of datasets is designed. The K-means-AHC algorithm is used to test many kinds of

 基金项目: 安徽省自然科学基金(2008085MF188); 国家自然科学基金(61972001)

Foundation item: Natural Science Foundation of Anhui Province, China (2008085MF188); National Natural Science Foundation of

China (61972001)

收稿时间: 2019-09-09; 修改时间: 2019-11-17, 2020-01-18; 采用时间: 2020-02-13

3086

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

datasets. The experimental results have shown that the proposed algorithm improves the accuracy of clustering analysis while without too

much time overhead. At the same time, the new DAS index is superior to the current commonly used clustering validity indexes in the

evaluation of clustering results.

Key words: clustering analysis; clustering algorithm; clustering validity index; optimal clustering number; data mining

作为一种无监督学习方法,聚类分析在数据挖掘领域具有重要的作用.聚类分析是在缺少先验信息的情况

下,根据一些相似性标准将样本点划分为多个类簇.它使得在同一个类簇中的样本点尽可能地相似,而不同类簇

中的样本点最大程度的不同

[1]

.目前,聚类分析被广泛用于数据分析、模式识别以及图像处理等多个领域.聚类

分析过程中通常要解决两个问题,即如何划分一个给定的数据集并使得划分结果最优以及将数据集划分为多

少个类簇最为合适.其中,第 1 个问题通常由聚类算法来解决,而第 2 个问题则由聚类有效性指标来评价

[2]

聚类算法是聚类分析的基础.根据类簇的不同形成方式,当前常用的聚类算法主要有基于划分的聚类算

法、基于层次的聚类算法、基于模糊理论的聚类算法、基于分布的聚类算法、基于密度的聚类算法、基于图

论的聚类算法、基于网格的聚类算法、基于分形理论的聚类算法以及基于模型的聚类算法等

[3]

.目前使用较多

的有基于划分的聚类算法和基于层次的聚类算法.基于划分的聚类算法首先将数据集分为 K 个类簇,然后从这

K 个类簇开始,并通过将某个准则最优化以达到最终的聚类结果.作为一种经典的基于划分的聚类算法,

K-means 具有实现简单、能够对大型数据集进行高效划分的特点.然而,由于受收敛规则的影响,K-means 算法对

初始类簇中心点的选取非常敏感.不恰当的中心点的选取,会使得该算法非常容易陷入局部最优问题.与此同

时,除了凸型数据集以外,K-means 算法不能对诸如条形、环形等类型的非凸型数据集进行很好的处理

[4]

另一方面,层次聚类算法则是通过将数据组织成若干组,并将其形成一个相应的树状图来进行聚类

[5]

.根据

树状图从上到下和从下到上的处理方式,可以将层次聚类分为两类,即分裂法和凝聚法.分裂法首先将数据集中

的所有样本点归为一个类簇,然后依据某种准则对初始类簇进行逐步的分裂,直至达到某种预设条件或预定的

类簇数为止;相反地,凝聚法在初始时将数据集的每个样本点当作一个类簇,然后依据某种准则合并这些初始的

类簇,直至达到某种预设条件或预定的类簇数为止

[6]

.作为层次聚类算法的代表,凝聚层次聚类(agglomerative

hierarchical clustering,简称 AHC)算法具有稳定性好、能够对多种类型的数据集进行较好处理等优点.然而,与

K-means 算法相比,AHC 算法的计算复杂度较高,故不适合直接用于大型数据集的聚类分析.

鉴于 K-means 算法和 AHC 算法的优缺点,本文将这两种算法的思想相结合,提出了一种新的混合聚类算法,

即 K-means-AHC 算法.K-means-AHC 算法首先利用 K-means 算法的处理方式,将数据集划分为若干个初始类簇;

其次,在形成的初始类簇的基础上,采用 AHC 算法的思想,将较小的初始类簇合并成符合要求的更大的类簇.新

的 K-means-AHC 算法不仅能够有效避免传统 K-means 算法对初始类簇中心点选取敏感和不能很好地处理非

凸型数据集的问题,而且可以有效缩短 AHC 算法的计算时间.

对聚类分析而言,不同算法甚至同一算法的不同参数配置都有可能产生同一数据集的不同划分

[7]

.与此同

时,很多聚类算法需要提前获得目标数据集的类簇数目.然而,这个数据通常是不能提前获取的.聚类分析通常

的做法是:先反复运行聚类算法,直到满足预定的条件为止;然后,运用聚类有效性指标来对聚类算法的划分结

果进行评价.作为聚类分析的一个重要组成部分,聚类有效性指标是寻找目标数据集最佳类簇数的关键

[8]

.聚类

有效性问题的研究一般是通过建立一个指标函数,即聚类有效性指标来完成的.而最佳类簇数的确定,是在不同

K 值的情况下分别运行聚类算法来获取的.在聚类算法运行的过程中,当指标函数取值达到最优(最大指标值或

最小指标值)时,对应的 K 值即为最佳类簇数

[9]

根据聚类有效性指标构成成分的不同,可以将其分为仅考虑数据集几何结构信息的聚类有效性指标、仅考

虑隶属度的聚类有效性指标和同时考虑数据集几何结构信息和隶属度的聚类有效性指标

[10]

.聚类有效性一直

是聚类分析领域的研究热点,一些经典和常用的指标有 CH 指标

[11]

、COP 指标

[12]

、DB 指标

[13]

、Dunn 指标

[14]

和 I 指标

[15]

等.然而研究表明,没有哪一种聚类有效性指标可以最优地处理所有类型的数据集.许多现有的聚类

有效性指标存在着一些缺点,比如在寻找最佳类簇数时不稳定、无法对多种形状的数据集进行正确评价等

[16]

为了能够稳定地处理多种类型的数据集,本文提出了一个基于平均综合度的新的聚类有效性指标,即 DAS.其最

of 19

免费下载

软件学报计算机技术

关注

评论