粒子群改进模糊C 均值的不完整数据聚类

华东计算技术研究所 邴兆虹 黄丽茜

在实际应用中，由于各种原因，采集出来的数据可能是不完整的，比如，数据模糊不清或者是数据丢失。因此在数据库中会经常出现不完整数据，而且没有办法获得数据的真实值[1]，如果不对缺失数据作出相应的处理，对后续工作会造成严重影响。为解决不完整数据聚类的问题，国内外学者根据现有的聚类方法提出了各种新策略。

1 模糊聚类

对于不完整数据的处理方法主要分为两种：一种是通过估算填充缺失值，即用相对应的已知属性值的平均值等方法来替换缺失属性值；另一种方法是直接删除缺失属性。对不完整数据进行模式识别最早开始于20 世纪60 年代，例如，基于概率的估算、EM 算法[2]等。其中基于模糊C 均值处理不完整数据的方法应用最为广泛。

模糊C 均值是一种基于模糊理论的聚类算法，即将数据集中的数据根据其相对于聚类中心的隶属度进行分类[3]。

在模糊C 均值中，随机选择的聚类中心容易使算法在迭代过程中陷入局部收敛[4]，而且对初始值的选取比较敏感，用粒子群改进模糊C 均值可以有效地解决这一问题。粒子群优化算法是一种新的全局优化进化算法，它源于对鸟类捕食行为的模拟。这种算法通过在全部个体中共享信息来寻找最优值。与其他技术相比，粒子群算法更易实现，收敛速度更快，需要调整的参数较少。但基本粒子群存在易陷入局部最优的问题，本文使用变异粒子群优化模糊C 均值解决这一问题。

本文在引用[5]基础上对聚类算法进行了改进，首先用最近邻近点的方法将不完整数据集转换成区间数据；然后用变异粒子群优化后的模糊C 均值算法对数据集进行聚类；最后通过仿真实验，对比其他方法的聚类结果，验证了本文提出方法的有效性。

2 不完整数据的处理

不完整数据的分类分为两个步骤：首先通过各种方法将不完整数据集转换成完整数据集，然后用合适的聚类方法进行聚类。

其中和是与的第j个属性，如果和都是非缺失的，则Ij为1，否则为0。

然后按相关性的大小排列，从中选出6 个距离缺失属性最近的数据，并用其已知属性替换缺失属性；然后在这6 个属性值中找出最大值和最小值，确定缺失属性的区间，这样就将不完整数据转换成了区间数据。

3 粒子群优化模糊C 均值

3.1 区间数据的模糊C 均值

数据集中的数据如果完全属于某一类，则该数据对应该类的隶属度为1；完全不属于，则隶属度为0，其他情况按照如式（7）所示的公式计算隶属度：

模糊C 均值算法首先要初始化隶属度和聚类中心，所以算法过度依赖初值的选取，而且易陷入局部极小，收敛速度较慢。针对以上问题，本文采用变异粒子群对模糊C 均值算法进行优化。

3.2 变异粒子群

粒子群算法中每个粒子代表一个可能的解，群体中每个粒子在每次迭代过程所经历过的最好位置称为个体极值。整个群体所经历过的最好位置称为全局极值。每个粒子都通过上述两个极值不断地更新自己的位置和速度，从而产生新一代群体，在这个过程中整个群体对解空间进行全面搜索[5]。

群体规模为n的粒子群表示为X={x1,x2,...,xn}，第i个粒子的位置表示为xi，速度为vi，它的个体极值记为pb，全局极值记为gb，则粒子的速度和位置更新公式如式（8）、式（9）所示：

其中w为惯性权重，c1，c2是学习因子，rand是随机产生的0～1 之间的数。

汇总本文数据，所有数据均经过SPSS20.0版进行处理，两组高血压伴心力衰竭患者的血压水平与生存质量评分均以均数差表示，用t检验。若P<0.05则代表两组数据比对差异具统计学意义。

基本粒子群的一个缺点是容易停滞，在停滞阶段，粒子的速度几乎为0，粒子会聚集在某一点附近，即陷入局部最优[7]。而在粒子群迭代的过程中加入变异，可以使种群跳出局部最优。当粒子群的全局最优位置的适应值连续A次都没有得到改进，则认为粒子群已经聚集到某一局部最优位置，此时整个粒子群的位置以一定的变异概率进行变异。本文取变异概率为，t为迭代次数，用如式（10）所示的公式改变粒子的位置：

其中max 和min 为搜索空间的上界和下界。

3.3 改进的模糊C 均值算法

粒子群优化模糊C 均值算法中每个粒子要存的是各种分类方式下的聚类中心。用粒子群优化后得到的聚类中心计算隶属度，从而计算出目标函数，将其作为各粒子的适应度值，通过粒子群位置和速度的更新，找到适应度最好的粒子，即最小目标函数作为最终解。

对于一个不完整数据集X={x1,x2,...,xn}，用粒子群优化后的模糊C 均值进行分类的算法流程如下：

（2）确定粒子群中粒子的个数、粒子维数、初始化粒子速度和位置，设定最大迭代次数。

（3）计算隶属度和目标函数。

（4）计算各粒子的适应度值。

（5）对每个粒子，将它的适应度值与它的历史最优的适应度值比较，如果更好，则将其作为历史最优。

（6）对每个粒子，比较它的适应度值和群体所经历的最好位置的适应度值，如果更好，则将其作为全局最优。

（7）判断是否满足变异条件，若满足则进行变异，否则进行下一步。

（8）更新粒子的速度和位置。

（9）判断是否满足终止条件（迭代次数达到最大或者误差小于给定误差），满足则终止，得到分类矩阵和聚类中心，否则转到第（3）步。

4 实验

为验证本文提出方法的有效性，将该方法与最近邻区间法、局部距离法等5 种方法进行对比，同时对UCI数据库里的Iris、Wine 两个数据集进行仿真实验。实验中的有关参数设定如下：粒子群规模为100，最大迭代次数为200 次，最大误差为10-6，数据缺失率分别取5%、10%、15%、20%。

为了测试本文算法的有效性，将引用[7]提出的4 种方法WDS、PDS、OCS、NPS，最近邻近区间法NNI 与本文方法NPF 的实验室结果进行对比。

如表1，表2 所示，可以看出，随着缺失属性的增加，各种方法的准确率都有所下降，第一个数据集的准确率比较稳定，下降幅度不是很大。本文提出的方法在Iris数据集的缺失率为15%，Wine 数据集缺失率为20%时的正确率较低，其他情况下，本文方法的准确率是较高的。同时，本文方法的迭代次数较多，但是在缺失率为15%和20%时，NNI 和NPF 的迭代次数相差并不是很多。

表1 不完整Iris 数据集30 次实验结果的平均值及平均迭代次数Tab.1 Averaged results of 30 trials using incomplete iris data set

表2 不完整Wine 数据集30 次实验结果的平均值及平均迭代次数Tab.2 Averaged results of 30 trials using incomplete Wine data set

5 结论

本文采用变异粒子群改进的模糊C 均值算法对不完整数据进行分类，针对模糊C 均值存在对初值敏感和粒子群易陷入局部最优的缺点，提出用变异粒子群改进模糊C 均值，当粒子群陷入局部最优时，通过对粒子位置的改变，使粒子跳出局部最优。主要过程分为两部分:首先用最近邻近点的方法将不完整数据转换成区间数据；然后用变异粒子群改进的模糊C 均值算法对区间数据分类。通过与各种方法的实验结果对比，说明了本文方法的有效性。