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

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]
中的样本点最大程度的不同 .目前,聚类分析被广泛用于数据分析、模式识别以及图像处理等多个领域.聚类
分析过程中通常要解决两个问题,即如何划分一个给定的数据集并使得划分结果最优以及将数据集划分为多
[2]
少个类簇最为合适.其中,第 1 个问题通常由聚类算法来解决,而第 2 个问题则由聚类有效性指标来评价 .
聚类算法是聚类分析的基础.根据类簇的不同形成方式,当前常用的聚类算法主要有基于划分的聚类算
法、基于层次的聚类算法、基于模糊理论的聚类算法、基于分布的聚类算法、基于密度的聚类算法、基于图
[3]
论的聚类算法、基于网格的聚类算法、基于分形理论的聚类算法以及基于模型的聚类算法等 .目前使用较多
的有基于划分的聚类算法和基于层次的聚类算法.基于划分的聚类算法首先将数据集分为 K 个类簇,然后从这
K 个类簇开始,并通过将某个准则最优化以达到最终的聚类结果.作为一种经典的基于划分的聚类算法,
K-means 具有实现简单、能够对大型数据集进行高效划分的特点.然而,由于受收敛规则的影响,K-means 算法对
初始类簇中心点的选取非常敏感.不恰当的中心点的选取,会使得该算法非常容易陷入局部最优问题.与此同
[4]
时,除了凸型数据集以外,K-means 算法不能对诸如条形、环形等类型的非凸型数据集进行很好的处理 .
[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 值的情况下分别运行聚类算法来获取的.在聚类算法运行的过程中,当指标函数取值达到最优(最大指标值或
[9]
最小指标值)时,对应的 K 值即为最佳类簇数 .
根据聚类有效性指标构成成分的不同,可以将其分为仅考虑数据集几何结构信息的聚类有效性指标、仅考
虑隶属度的聚类有效性指标和同时考虑数据集几何结构信息和隶属度的聚类有效性指标 [10] .聚类有效性一直
是聚类分析领域的研究热点,一些经典和常用的指标有 CH 指标 [11] 、COP 指标 [12] 、DB 指标 [13] 、Dunn 指标 [14]
和 I 指标 [15] 等.然而研究表明,没有哪一种聚类有效性指标可以最优地处理所有类型的数据集.许多现有的聚类
有效性指标存在着一些缺点,比如在寻找最佳类簇数时不稳定、无法对多种形状的数据集进行正确评价等 [16] .
为了能够稳定地处理多种类型的数据集,本文提出了一个基于平均综合度的新的聚类有效性指标,即 DAS.其最