一种新的基于遗传算法的动态聚类算法

　　1　引言

　　聚类分析的目标是将一个数据集划分成若干个簇,使同一个簇中的对象尽可能的相似,而不同簇对象间的差异尽可能的大。聚类分析主要解决的两个问题就是确定聚类数目和相应的聚类。绝大多数的研究都关注第二个问题,就是在事先给定聚类数目的情况下进行聚类。但是在现实中,对于很多数据集,人们无法事先确定聚类数目。为了决定数据集中的聚类的数目,在文献[1]中,提出了一个GCUK-cluste-ring算法。在设置聚类数目变化区间[Kmin,Kmax]之后,在范围[Kmin,Kmax]中产生的一个随机数K,i染色体初始化成　　Ki个聚类的类中心。然后该算法通过聚类数目的演化得到最接近最优结果的簇分布。但是这个算法缺少一个有效的方法来确定Kmax的值,而这个值决定了聚类算法的结果。

　　而且该算法不能有效地处理带有孤立点的数据集。根据聚类采用的方法可以分为:划分聚类(partitional clustering)、层次聚类(hierarchical clustering)、基于密度的聚类(density-based clustering)、基于网格的聚类(grid-based clustering)以及基于模型的聚类(gird-based clustering)。本文主要讨论划分聚类,并提出了一种的新的动态聚类方法,实验结果表明该算法能够有效地进行聚类。该方法分为两个阶段:

　　1)最近邻聚类阶段:用最近邻方法来建立初始的聚类集。根据最近邻方法把最相似的实例聚到一个类,并根据一些相似性或相异性度量有效地过滤掉“噪声”数据。

　　2)遗传优化阶段:利用动态聚类评估函数,动态的合并初始聚类集,从而获得接近最优的解。

　　2　最近邻聚类阶段

　　最近邻聚类算法[2-3]的基本思想是:空间中的每一点和与之最近的点属于同一类的可能性最大。如果两个距离最近的点之间的距离小于设定的距离阈值d,那么就认为它们属于同一类。最近邻聚类算法试图把两个最近邻的点归为一类。对于数据集合X = {X1,X2,…,Xn},其中n为数据集中对象的数目。对X中任一个数据对象Xj建立一个五元组的属性

　　3　遗传优化阶段

　　经过最近邻聚类阶段得到初始的聚类集。在遗传优化阶段,初始的聚类集用来建立初始的染色体。遗传优化阶段的处理过程如图1。　　

　　3.4　迭代聚类

　　如果以等同概率产生0或1的二进制串作为染色体的编码,产生1的个数的值最大概率的情况下是染色体长度的一半。以这种染色体为依据进行动态聚类,最终聚类数为染色体中值为1的基因的个数,也就是大约为染色体长度的一半。但是一般的情况下实际聚类数要大大地小于染色体的长度。在这个情况下,算法要收敛到最优值需要很长的时间。为了加快算法的收敛速度,将一个迭代聚类的过程与遗传算法结合起来使用。迭代聚类过程的描述如下: