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

朱二周 等:一种采用新型聚类方法的最佳类簇数确定算法 3087

大值表示对于数据集非重叠类簇的最佳划分.
本文研究了能够对多种类型的数据集信息进行快速精准划分的聚类算法以及能够对划分结果进行有效评
价的聚类有效性指标.综合而言,本文的主要贡献有以下几个方面.
(1) 提出了一种新的 K-means-AHC 混合聚类算法.K-means-AHC 算法充分结合了 K-means 算法简单、高
效和 AHC 算法稳定性好、能够对多种类型的数据集进行处理的优点.首先,采用 K-means 算法的处理
方式将数据集划分为若干个初始类簇,这一做法避免了凝聚层次聚类从单个点开始处理的问题,可在
很大程度上减少将若干较小类簇合并成较大类簇的计算工作量;在形成的初始类簇的基础上,采用
AHC 算法的思想,逐个地将较小类簇合并成较大的类簇,直到满足条件为止;
(2) 提出了一个新的聚类有效性指标 DAS.DAS 运用两个类簇之间的最小距离来衡量簇间分离度,用一个
类簇内部所有样本点的最小生成树的平均权重来衡量簇内紧密度.将类簇内紧密度和类簇间分离度
的线性组合纳入聚类效果的整体质量评估.最终通过应用拐点检测的方法找到目标数据集的最佳类
簇数.通过这种定义方法,DAS 指标的最大值能够被非常清晰地显示出来;
(3) 设计了一种新的确定数据集最佳类簇数的算法.通过将 K-means-AHC 算法和 DAS 指标相结合,设计
并实现了一种确定数据集最佳类簇数的有效方法.合理性分析与实验验证得出,本文提出的聚类方法
是准确和有效的.
1 相关工作

近年来,研究人员在传统聚类算法的基础上提出了许多新的或改进的聚类算法.Zhu 等人 [17] 提出了一种低
秩稀疏子空间聚类算法,该算法通过从低维空间中学习到的关联矩阵而形成最终的聚类结果.Chen 等人 [18] 提出
一种局部邻域搜索技术,并将其应用于改进的 DBSCAN 算法中,以此来减少数据集中各样本之间不必要的距离
计算.在该模糊 C 均值(FCM) [19] 算法的基础上,Qian 等人 [20] 通过应用知识杠杆原型转移(KL-PT)和知识杠杆原
型匹配(KL-PM)这两种知识转移机制,提出了一种新的基于知识利用的迁移模糊 C 均值算法(KL-TFCM).Arora
等人 [21] 提出了一种基于噪声自适应非局部信息的改进型 FCM 算法(MFCM),该算法可用于使用局部和非局部
空间信息对 MRI 脑图像进行有效分割.在基于图论的聚类算法中,谱聚类是一种经典的算法 [22] .在该领域中,Li
等人 [23] 构造了一个新的基于密度的矩阵,以作为谱聚类中的相似性矩阵.在此基础上,提出了基于密度的 K 均值
以实现收敛全局优化,使其能够找到复杂数据的空间分布特征.Airel 等人 [24] 提出了一种新的基于图论的重叠聚
类算法,该算法解决了以往一些重叠算法的局限性,同时具有可接受的计算复杂度.
Rodriguez 等人 [25] 在 2014 年提出了一种基于密度峰值的聚类算法 DPC(clustering by fast search and find of
density peaks).该算法进行如下的假设:(1) 类簇中心点的密度大于周围邻居点的密度;(2) 类簇中心点与更高密
度点之间的距离相对较大.基于这两个假设,该算法可以实现对任意形状类簇的聚类并降低异常点的干扰.针对
DPC 算法的样本局部密度定义和样本分配策略的缺陷,谢娟英等人 [26] 提出一种基于 K 近邻的快速密度峰值搜
索并高效分配样本的聚类算法.该算法利用样本点的 K 近邻信息定义样本局部密度,搜索和发现样本的密度峰
值,并以峰值点样本作为初始类簇中心.在提出的两种基于 K 近邻样本分配策略的基础上,得到数据集样本的分
布模式.纪霞等人 [27] 针对 DPC 算法及其改进算法效率不高的缺陷,提出了一种相对邻域和剪枝策略优化的密度
峰值聚类算法 RP-DPC.针对 DPC 算法无法自行选择类簇中心点的问题,马春来等人 [28] 提出了 DPC 改进算法.
该算法采用类簇中心点自动选择策略,根据类簇中心权值的变化趋势来搜索“拐点”,并以“拐点”之前的一组点
作为各个类簇中心.这一策略有效避免了通过决策图判定类簇中心的方法所带来的误差.徐晓等人 [29] 提出了基
于网格筛选的密度峰值聚类算法,该算法通过稀疏网格筛选去除一部分密度稀疏的点,即不可能成为类簇中心
的点,而只保留稠密网格单元中的点作为候选集进行类簇中心的选取.该算法保持了密度峰值聚类算法寻找类
簇中心的准确性,同时降低了时间复杂度和内存需求,提高了运行效率.褚睿鸿等人 [30] 通过一个基于密度峰值的
聚类集成模型来提升聚类结果的准确性、稳定性和鲁棒性.
在各种基于划分的聚类算法中,最为经典和常用的是 K-means 算法.研究人员在该算法的基础上提出了许