结合遗传k均值改进的密度峰值聚类算法

卜秋瑾，段隆振，段文影

(南昌大学 信息工程学院，江西 南昌 330031)

0 引 言

传统的聚类算法[1,2]虽然具有自己独特的优势，但是也存在一些严重的缺陷，例如，k均值虽操作简单、聚类速度比较快，但需要事先指定具体簇个数及簇中心；DBSCAN 算法虽能发现不规则形状数据集中的类，但却易受算法中参数的影响，微小的变化都会导致不同的结果。

Alex Rodriguez等[3]于Science上提出了CFSFDP算法。该算法可以找到任意形状数据集的簇中心，具有参数少、无需迭代、实现原理简单等优点，被应用到了多目标跟踪[4]、图像分割[5]、摘要自动提取[6]、室内定位[7]等众多领域中。同时，关于该算法的研究也有很多，例如，文献[8]基于网格来解决CFSFDP算法计算所有数据点间的距离时,时间代价大的问题。文献[9]将测地距离的概念引入到CFSFDP方法中，解决CFSFDP算法对具有任意形状或流形结构的数据分组不佳问题。文献[10]中CFSFDP算法引入KNN思想来计算样本局部密度，同时引入PCA解决数据高维度问题。

通过对CFSFDP算法的分析，发现该算法依靠人工经验选取簇中心易造成簇的误划分。针对该缺陷，本文提出一种结合遗传k均值改进的CFSFDP算法。首先使用CFSFDP算法找出数据集的可能簇中心，然后使用基于可变染色体长度编码的遗传k均值对其进行全局搜索，从而找到最优聚类中心，同时根据进化代数和种群收敛情况对遗传k均值的交叉概率进行改进，使其能够自适应变化。实验结果表明，改进算法能够有效解决所指出的问题，同时具有良好的聚类效果。

1 密度峰值聚类算法

CFSFDP算法表示密度高于其相邻点，且与其它密度峰值点距离较远的点为簇中心，同时，定义了如下两个参数：

(1)样本局部密度ρi定义为

(1)

其中，dij为样本i与j间的某种距离，dc为截断距离，通常将所有数据对象间的距离按照升序排序后的前2%作为截断距离[11]。

(2)样本i与最近较高密度点样本j之间的距离δi定义为

(2)

2 结合遗传k均值改进的密度峰值聚类算法

2.1 遗传k均值算法

遗传k均值算法将遗传算法与k均值相结合来弥补k均值算法的不足。首先，确定遗传算法的染色体编码规则，每条染色体表示一种聚类结果；然后，初始化种群进行遗传操作；最后，得到适应度值最大的染色体，具体步骤参见文献[12]。

(1)确定采用的染色体编码方式，聚类的个数k，种群的规模M，交叉概率Pc， 变异概率Pm， 种群迭代数G；

(2)从样本中随机选择k个点作为一组聚类中心，形成一条染色体，重复M次，形成规模为m的初始种群；

(3)根据k均值聚类算法对每条染色体进行聚类，并计算每条染色体的适应度值；

(4)依据某种规则进行选择操作，再依Pc、Pm进行交叉变异操作，形成新的种群；

(5)重复执行(3)、(4)，直到算法找到最优解或者达到最大迭代次数，算法终止。

2.2 结合遗传k均值改进的密度峰值聚类算法

当CFSFDP算法 (ρ,δ) 决策图中簇中心与非簇中心分度不高或者存在多密度峰值时，凭借人工经验选取聚类中心方法容易造成簇的误分裂或者选中的簇个数小于实际簇的问题。因此，本文中密度峰值聚类算法将与改进的遗传k均值相结合，借助其全局搜索能力自动确定最优的聚类中心。算法流程如图1所示。

图1 本文算法流程

(1)染色体编码

采用可变染色体长度实数编码[13]，每条染色体的基因由初始聚类中心对应的点在样本集中的编号表示，染色体的长度即为聚类中心的个数。该编码方式缩短了染色体的长度，提高了遗传k均值算法的速度，对于求解大规模数据的聚类问题效果较好。

(2)种群初始化改进

首先，计算所有样本的λi=ρi·δi， 绘制 (n,λ) 降序排序图，找出突变点对应的样本数，记为k′， 从排序图中选取前ks(ks=2k′) 个点作为CFSFDP算法的可能簇中心；然后，从中随机选择k(k∈[2,ks]) 个点构成一条新的染色体。假设种群大小为M，则重复选取M次，形成初始种群。

(3)遗传操作

由于聚类事先不能确定每个样本的类别，所以应当选用类标签未知的评价指标。本文参考文献[14]中的评价函数来定义遗传算法的适应度值，具体见式(3)-式(5)。类间距越大与类内距越小，聚类质量越好，适应度值越大。适应度函数f的定义式如下

(3)

Inter_dist表示类间距，即所有聚类簇中的元素之间距离的平均值，定义如下

(4)

其中，k为聚类数目，ci，cj为簇Ci和簇Cj的聚类中心；

Intra_dist表示类内距，即各类簇内元素间距离的平均值，定义如下

(5)

选择操作通过适应度值的大小选择优质个体而抛弃劣质个体，遵循“适者生存”的原理。本文采用轮盘赌法和最优个体保存相结合进行选择操作；同时，采用两点交叉和基本位变异方式，具体公式如下：

(6)

(4)改进的交叉算子

交叉变异概率要满足以下基本要求：为保存优秀者、淘汰差个体，适应度值低于平均值的个体的交叉变异概率应相对高于适应度高于平均值的个体；同时，交叉变异概率应随着进化代数的增加呈现出下降趋势。因此，交叉概率不但要考虑种群的进化代数，还应考虑当前种群的收敛情况。在种群进化初期，为了保证遗传算法迭代正常进行，种群个体具有相对较高的交叉概率；在种群进化后期，如果种群收敛，则发生交叉的概率应相对较低；但如果后期种群仍未收敛，则个体应具有适当的交叉变异概率来保证新个体的产生，避免后期常出现的进化停滞现象。

本文基于标准自适应交叉算子[15]，对遗传算法的交叉概率做出改进，具体见式(7)

(7)

其中，Pc代表交叉概率，f′代表交叉个体中的较大适应度值，fa代表交叉个体的平均适应度值，fmax代表当代种群中的最大适应度值，Pc1为算法收敛时的极限交叉概率，取0.01。

3 实验与分析

为了验证改进算法的有效性，从文献[16]中选取5个常用数据集作为实验数据，分别是Iris、Wine、Seeds、Libras Movement(LM)、Waveform，详细信息见表1。

表1 实验数据集

在不同规模和不同维度的数据集上，将本文算法与k-means、CFSFDP、GKA、本文算法染色体长度固定时进行对比实验。本文参考文献[17]中聚类指标ARI来评价算法性能，ARI取值范围为为[-1,1]，公式如下

(8)

以上算法分别在每个数据集进行15次实验，遗传算法中设种群规模M=30、迭代次数G=100，交叉概率中相关系数a=0.03；根据数据集事先指定k-means、GKA算法聚类的个数。

在Iris、Wine、Seeds、Waveform上，本文改进后的算法能找到正确的类簇中心点，且从图2可以看出，本文算法的聚类质量要明显优于CFSFDP算法；LM数据集类簇数较多，每个簇含有样本数较少，CFSFDP算法只能找到9个分布在7个类簇的类簇中心，但是本文算法是选取了决策图中的18个点来进行遗传k均值算法种群初始化，因此提高了覆盖类簇中心的可能性；同时，利用遗传k均值的迭代寻优优势使得本文算法最终的聚类质量优于CFSFDP；在Waveform上，4种算法表现的不是很好，但本文算法仍然保持优势。由于数据集规模较小时，GKA算法能够遍历较多的可能性，所以在前4个数据集上，本文算法稍优于GKA，但在Waveform上，本文算法聚类效果明显优于GKA算法。虽然k-means算法事先也被指定k值，但由于最优解受初始聚类中心的影响，聚类质量很不稳定，在实验中聚类质量与其它几算法相比较差。

图2 不同算法的ARI值

从图3发现，本文算法每次均能找到正确的簇个数，而当本文算法染色体采用定长染色体编码时在Iris、Wine、Seeds、Waveform上最优解对应的簇个数会偶尔性出错，其中，在LM数据集上最优解对应的簇个数很不稳定。由于基于定长染色体编码时，遗传算法无法迭代出在种群初始化时未定义的染色体长度，所以造成了上述问题；但是，采用了可变染色体长度编码的遗传算法能够自适应调整染色体长度，进而找出正确的簇个数以及合适的簇中心。在Iris、Wine、Seeds、Waveform上，尽管CFSFDP算法能找到正确的类簇中心，但在LM上，由于簇中样本较少却只能发现包含在7个簇中的9个密度峰值点；同时，由于CFSFDP算法每次实验都依据相同的密度计算方法、样本分配策略、同样的类簇中心选择方法，一旦根据决策图确定了类簇中心，则会使每次实验结果都一样，势必导致实验结果的唯一性。如果确定的密度峰值点与真实类簇中心差别较大，也会造成聚类质量不理想。与CFSFDP相比，本文算法考虑了更多的类簇可能点，同时通过遗传k均值算法进行迭代寻优找到合适的簇中心，进而提高聚类质量。

图3 染色体长度对本文算法最优解簇个数的影响

从图4和图5看出，在Iris、Waveform数据集上，本文算法在前5次迭代左右就能找到最优解，收敛速度明显优于GKA算法，因为本文使用CFSFDP聚类结果来初始种群，为遗传k均值算法种群初始化提供了有效的参考值。与GKA算法相比，避免了随机选取初始聚类中心的盲目性，加快了算法的收敛速度。

图4 Iris上的适应度值走势

图5 Waveform上适应度值走势

4 结束语

本文提出的结合遗传k均值改进的密度峰值算法，使用改进的遗传k均值的全局搜索能力从CFSFDP算法确定的可能聚类中心搜索出最优簇中心，与k-means、CFSFDP、GKA算法、本文算法基于定长染色体编码时的实验结果相比，本文算法能找到准确簇个数同时避免算法陷入局部最优，在提高聚类质量的同时保证了聚类质量的稳定性，同时，减少了算法的迭代次数。但由于样本密度计算方法的不足，导致聚类质量有所提高但并没有非常的理想，所以接下来的主要任务是寻找合适的样本点密度考量方法，同时还会考虑将本文算法应用到大规模海量数据处理，实现算法的并行化，使其在保证聚类质量同时提高算法运行效率，提高算法的扩展性和可行性。