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

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

多改进算法.Capo 等人 [31] 提出了针对海量数据的 K-means 问题的有效近似方法,通过利用近似次优距离代替真
实距离以有效降低距离计算的工作量.Zhang 等人 [32] 提出了一种基于密度的改进 K-means 算法,该算法通过合
适的类簇数和最佳初始种子选取,提高了 K-means 的准确性和稳定性.Jiang 等人 [33] 从异常值检测的角度考虑
K-modes 聚类的初始化,并提出了两种不同的 K-modes 聚类初始化算法.通过使用两种离群值检测技术来计算
每个对象的离群程度,进而避开了所选择的初始类簇中心是异常值的可能.Ismkhan [34] 通过在每次迭代中移除
一个类簇,再划分另一个类簇,然后再重新聚类来提高 K-means 的聚类质量和精度.K-means++ [35] 通过增量方式
选取类簇中心,在该算法中,第 1 个初始类簇中心是随机选取的.一旦第 1 个中心被确定下来,增量选取的其余类
簇中心将距已选取的中心尽可能地远.Grid-K-means 算法 [16] 将网格划分的思想应用于改进 K-means 算法,该算
法使用动态变化的网格操作代替 K-means 算法中的样本点的操作.得益于网格操作的快速性,Grid-K-means 具
备快速且准确处理大型数据集的能力.关于 K-means 算法的最新改进算法还有基于密度参数的改进 K-means
算法(DPI-K-means) [36] 、基于 Density Canopy 的改进 K-means 算法(DC-K-means) [32] 和基于可压缩近邻表示的聚
类方法 Bit k-means [37] 等.以上这些改进算法都对传统的 K-means 算法的缺陷做出了某方面的改进,但是都没有
充分考虑 K-means 对非球状分布数据集的不适应性.本文在 K-means 算法的基础上,结合 AHC 算法的特点,提出
了 K-means-AHC 混合算法.该算法具备快速处理多种形状分布的数据集的能力.
聚类有效性指标用于判断目标数据集应被划分为多少类簇更为合适.近年来,除了一些经典的指标,如 CH
指标、COP 指标、DB 指标、Dunn 指标以及 I 指标等,研究人员提出了许多新的聚类有效性指标以应对传统聚
[7]
类有效性指标的不足.Zhou 等人 根据类簇中对象的几何分布,提出了一个基于类簇中心和最邻近距离的新的
内部聚类有效性指标.Ahmed 等人 [38] 提出了一个基于 Jeffrey divergence 的聚类有效性指标,其中,Jeffrey
divergence 用来衡量类簇之间的分离性.Yue 等人 [39] 基于两种常用的分区聚类算法——C-means 和模糊 C-means
以及它们的变体,提出了一种新的度量来表示类簇之间的分离性.根据这个度量,他们提出了一种新的聚类有效
性指标来评估分区算法的聚类性能.Lin 等人 [40] 基于分散度和重叠度提出了一种新的有效性指标,其中,离散度
估计数据集中类簇的总体数据密度,而重叠度则估算所有类簇之间的隔离程度.Yang 等人 [41] 利用基于标准欧氏
距离和 ReliefF 算法的优化形态相似度距离来创建新的有效性指标,该指标可以平衡类簇内部和类簇之间的一
[5]
致性问题.基于层次聚类算法,Zhou 等人 提出的 CSP 指标可以有效评估多种结构的数据集的聚类结果.黄晓辉
等人 [42] 根据每个类簇中心不但能代表本簇的数据对象,且可尽可能地远离不属于本簇的数据对象的思想,设计
了一个优化聚类算法的目标函数(P).Starczewski [43] 提出的 STR 指标使用了拐点检测的方法来衡量数据集的划
分准确性.Zhao 等人 [44] 指出,拐点检测通常是必需的,因为大多数指标随着类簇数量的增加显示出单调性.因此,
具有明确的最小值或最大值的指数是优选的.鉴于拐点检测的必要性,本文提出的 DAS 指标将类簇内紧密度和
类簇间分离度的线性组合纳入聚类效果的整体质量评估.最终,通过应用拐点检测的方法找到目标数据集的最
佳类簇数.在文献[45]中,张远翔对 DAS 指标的相关背景、设计与实现进行了更加详尽的阐述.

2 K-means-AHC:基于 K-means 和 AHC 的混合算法

为了充分利用 K-means 算法和 AHC 算法的优点,本文将这两种算法的思想相结合,并提出了一种改进的混
合算法,即 K-means-AHC.总体来讲,K-means-AHC 首先运用 K-means 算法处理数据的方式形成数据集的初始划
分.在形成的初始划分的基础上,运用 AHC 算法处理数据的方式得到数据集的最优划分.K-means-AHC 算法的
m
设计基于如下假设,即:在欧氏空间 R 中,数据集 D={x 1 ,x 2 ,…,x n }具有 n 个样本点.每个样本点 x i ={x i1 ,x i2 ,…,x im }
具有 m 个属性.在数据集 D 中,样本点 x i 和 x j 之间的欧氏距离 dist(x i ,x j )定义为
2 1/2
2
dist(x i ,x j )=((x i1 x j1 ) +…+(x im x jm ) ) .
在给定的数据集 D 和类簇数 K 的情况下,首先,通过运用 K-means 算法处理数据的方法,将数据集 D 划分成
K 1 个类簇.与其他算法不同的是,这一步骤生成的初始类簇的数量是一个较大预估值(K 1 > n ).故初始类簇的数
量 K 1 要远远大于算法最终生成的类簇的数量 K.其次,在生成的 K 1 个初始类簇的基础上,运用 AHC 算法处理数
据的方法将 K 1 个初始类簇逐步合并,直到生成的类簇的数量等于 K 为止.K-means-AHC 算法的具体流程如图 1