一种基于动态填充的不完备数据聚类算法

裴卫杰，庞天杰

(太原师范学院 计算机科学与技术系，山西 晋中 030619)

0 引言

聚类分析是机器学习领域中一个重要的研究方向，其主要思想是将数据对象划分成不同的簇，使得同一簇中的数据对象具有较高的相似度，而不同簇中的数据对象具有较低的相似度.目前，基于划分、层次、密度、网格等的诸多聚类算法在社会科学、地球科学、生物学以及医学等领域有广泛的应用[1-3].然而针对带有缺失值的不完备数据，众多学者提出了不同的处理策略，Hathaway等[4]针对缺失数据对象利用模糊C均值聚类(FCM)算法提出两种舍弃策略，但是由于舍弃缺失数据而丢失了大量信息，导致聚类效果欠佳.目前，不完备数据的聚类主要采用了填充策略[5].Li等[6]针对缺失数据提出了一种最近邻区间填充法，将不完备数据集转化为完备的区间型数据集，而后通过改进的FCM算法进行聚类；苏婷等[7]利用q近邻填充法对不完备数据进行填充，然后在完备的数据集上进行聚类；史倩玉等[8]分别使用均值填充法、K最近邻填充法和有序最近邻填充法将缺失值填充，然后在3种填充后的数据集上通过K-Prototypes算法多次产生基聚类，最后将基聚类结果进行集成，得到最终聚类结果.虽然上述方法较好地解决了不完备数据聚类问题，但是由于传统填充法都是一次性填充，而且填充策略带有一定的主观性，进而影响了聚类结果的准确性.因此，针对数值型不完备数据，如何有效利用含缺失值数据的信息，对其进行动态填充并聚类显得十分重要.

本文针对不完备数据，提出一种基于动态填充的不完备数据聚类算法.该算法利用均值填充法对缺失数据进行初始化填充，然后对填充后的数据集用K-means算法进行聚类，将缺失值用其所在类的类中心的对应属性值进行再次填充，直到聚类结果不再变化时停止.

1 相关工作

1.1 不完备信息系统

I=(U，A，V，f)是一个不完备信息系统[9].其中，U={x1，x2，…，xn}是非空有限数据对象集合，称为论域，n是论域中对象的个数；A={a1，a2，…，am}是非空有限属性集合，m是对象属性的个数；V={V1，V2，…，Vm}是属性的值域集，Vi是ai的值域；f是信息函数，f：Vil=f(xi，al)∈Vl,表示对象xi在属性al上的取值为Vil,f(xi，al)=″*″表示属性值缺失.

xi为第i个对象，具有|A·=m个属性，即xi=(xi1，xi2，…，xip，…，xim)T,其中，xi表示第i个对象xi的第p维属性值，(j=1，2，…，n；p=1，2，…，m).

在其基础上，将U分为两个子集，即缺失数据集合UM和非缺失数据集UC,且满足U=UM∪UC和UM∩UC=Ø.其中，UM是所有含缺失属性值对象的集合，UC是所有不含缺失属性值对象的集合.

1.2 缺失值填充方法

目前，相关学者针对缺失值问题提出了很多解决策略，其中，填充法是一种重要的处理技术.该方法是利用数据集中的完备数据对缺失值进行填充，达到不完备数据完备化的效果.其中均值填充法[10]、随机热卡填充法[10]和近邻填充法[8]由于简单有效而得到广泛应用.

1.2.1 均值填充法

均值填充法是通过UC中所有非缺失对象相应属性值的平均值对UM中的缺失属性值进行填充.该填充法利用数据集中非缺失数据的平均信息对缺失值进行估计，通过最可能的属性值进行填充，具有简单易行的优点.

1.2.2 随机抽样热卡填充法

随机抽样热卡填充法是在UC中随机抽取一个对象利用其相应的属性值对UM中的缺失属性值进行填充.该填充法通过随机抽样的方式，避免了均值填充法所导致的方差低估问题.但是该方法中的填充值为数据集中的随机值，准确性较低.

1.2.3K近邻填充法

K近邻填充法是将UM中的缺失属性值通过UC中最相似的K个非缺失对象平均值的相应属性值进行填充.对象间的距离通过局部欧式距离公式[4]计算，该公式只使用缺失对象中没有缺失的属性来计算它们之间的距离，具体公式如下：

(1)

2 基于动态填充的不完备数据聚类算法

目前，不完备数据聚类算法主要是利用填充法对不完备数据进行填充，进而对其聚类.因此，填充方法的优劣直接影响聚类结果的好坏.而传统填充方法通常先对数据集进行某种假设，然后基于该假设填充缺失值.如均值填充法将数据集视为基于高斯分布，利用最可能的均值对缺失值进行填充.这些填充方法具有一定的主观性，且没有对已知数据充分利用，往往填充效果较差，进而对聚类结果造成影响.基于此，本文提出一种基于动态填充的不完备数据聚类算法.在该方法中，首先利用均值填充法进行初始化填充，然后通过基于类中心的算法进行动态填充，直到聚类相似度达到阈值为止.

2.1 初始化填充方法

在不完备数据进行聚类时，需要利用全体数据集的分布信息对缺失值进行动态填充.因此，在聚类之前，需要对缺失数据进行初始化填充.由于均值填充法简单高效，同时可以反映数据的分布情况，所以采用其对不完备数据进行初始化填充.将缺失值利用非缺失数据集UC中所有对象均值的相应属性值进行填充.

令∀xj∈UM,xj=(xj1，xj2，…，xjm)T,其中，xjp=″*″.缺失值xjp的填充公式为

(2)

其中，|UC·表示非缺失数据集UC中对象的个数.通过公式(2)，将缺失数据集UM进行填充，令填充后的数据集为U′.

2.2 动态填充方法

通过以上分析，为消除均值填充法因主观假设所带来的不良影响，本文采用基于聚类中心的填充法对缺失值进行填补.首先利用K-means算法[11]对填充后的数据集U′进行聚类，得到聚类中心c={c1，c2，…，cK}(其中，cs∈c,cs=(cs1，cs2，…，csm)T)和聚类结果C={C1，C2，…，CK}.对缺失数据集UM中缺失值通过其所在类中心的相应属性值再次填充.

令∀xj∈UM且xj∈Cr,xj=(xj1，xj2，…，xjm)T,xjp=″*″.缺失值xjp的再次填充公式为

xjp=crp.

(3)

通过公式(3)，将缺失数据集UM进行再次填充，令填充后的数据集为U1.

该方法有效地利用聚类算法自动寻找近邻的功能，对缺失值用最可能的值进行填充，进而降低初始填充法对填充效果的误差.具体算法如表1所示.

表1 基于类中心的填充算法(算法1)

算法1的时间复杂度分为O(Knmt+Km),其中，O(Knmt)为K-means算法的时间复杂度(即第2步的时间复杂度)，O(Km)为缺失值填充的时间复杂度(即第3步的时间复杂度)，K是聚类个数，n是不完备数据集U的对象总数，m是属性个数，t是K-means最大迭代次数.

通过以上分析，尽管填充效果有较大的提高，但是填充后数据集的改变及K-means算法对初始点敏感不可避免地带来了部分填充误差.为尽可能地降低这部分误差，本文设计了一种动态填充方法.该方法利用聚类中心对缺失值进行填充，然后在填充后的数据集上聚类得到聚类中心，并将缺失值通过其所在的类中心进行动态填充.此方法充分利用了数据集中的已知信息，有效消除了初始填充法所带来的主观性问题.同时所采用的K-means算法[12]不仅简单易行，而且具有稳定性和收敛性，有利于保证聚类结果的稳定.

2.3 聚类终止条件

上述方法利用聚类中心对缺失值进行填充，通过多次迭代，可以得到一个较好的聚类结果.因此，在迭代过程中需要对聚类效果进行评价，进而确定聚类终止条件.我们利用聚类相似度作为终止准则，同时衡量动态填充的充分程度.由于K-means算法具有稳定性，当相邻聚类结果极其相似时，动态填充后的数据集已经趋于稳定，不完备数据集充分填充.本文采用分类准确度[13]来度量相邻聚类结果的相似度.相似度S表示如下：

(4)

其中，K为类个数，bi表示两个聚类结果中对应类Ci中共有的对象个数，n表示对象总数.

为了解决类标签对应问题，本文采用周志华等[12]提出的最大覆盖法进行合并类标签.相似度算法具体如表2的所示.

表2 相似度算法(算法2)

算法2只需要K×K的空间来存储相似度矩阵，时间复杂度为O(K2).

2.4 一种基于动态填充的不完备数据聚类算法

基于以上分析，本文提出了一种基于动态填充的不完备数据聚类算法(IDCA-DF算法)，具体如表3所示.

表3 IDCA-DF算法(算法3)

通过分析可知，本文提出算法的时间复杂度为O((1-r)*n+Knmtl+K(m+K)(l-1)),均值填充K-means算法的时间复杂度为O((1-r)*n+Knmt),k近邻填充K-means的时间复杂度为O(r(1-r)n2+Knmt),其中r是缺失数据占对象总数的百分比，K是聚类个数，n是不完备数据集U的对象总数，m是属性个数，t是K-means最大迭代次数，l是动态填充最大次数.由于现实数据中n≫m,n≫t,n≫l,所以当n足够大时，O((1-r)*n+Knmtl)和O((1-r)*n+Knmt)相对于n来说是线性的，O(r(1-r)n2+Knmt)相对于n来说是超线性.

3 实验分析

3.1 实验数据与实验环境

从UCI真实数据集中选取了数据规模不同的7个完备数据集进行实验，数据集信息如表4所示.

表4 数据集描述

实验的计算机环境为：处理器Inter i7-4790 3.6 GHz ，内存4G ，操作系统Windows7 ，编程环境MATLAB2013a.

3.2 聚类有效性度量指标

为了对聚类结果的有效性进行评价，本文采用外部评价指标分类准确率CA[13]和内部评价准则CUN[14]对聚类结果进行评价.

3.2.1 分类准确率CA

(5)

其中，K为类个数，ci表示正确聚类与对应类Ci中共有的对象个数，n表示对象总数.CA在已知数据真实类划分的情况下，用来评价聚类结果与真实类标签的相似度.

3.2.2 有效性函数CUN

(6)

可见，CA值越大，CUN值越大，聚类效果越好.

3.3 实验与结果分析

本文选取三种传统的填充法将不完备数据集完备化后，通过K-means算法产生聚类结果.对比算法一是对不完备数据集通过均值填充法填充后再用K-means算法聚类；对比算法二是对不完备数据集通过随机抽样热卡填充法填充后再用K-means算法聚类；对比算法三是对不完备数据集通过k近邻填充法填充后再用K-means算法聚类.

在实验过程中，针对表4中的每个数据集分别随机删除10%对象的20%属性值(不为整数时，向上取整)作为不完备数据集.分别将本文算法与三种对比算法运行20次，计算CA和CUN的平均值与标准偏差以及聚类的平均时间.在k近邻填充法中，k取值为5.本文提出的算法与三种对比算法在不同评价指标下实验结果的平均值和标准偏差如表5和表6所示，不同算法的平均运行时间如表7所示.

表5 不同算法CA的平均值±标准偏差比较

表6 不同算法CUN的平均值±标准偏差比较

其中，表5和表6中每个数据集上不同算法的最优实验结果用粗体标识.通过对表5和表6中数据分析可知，对于以上7个数据集，除了Glass数据集外，本文提出的算法在两种指标下均优于三种对比算法；在Glass数据集上，本文算法的CA值最优而CUN值次优.

表7 不同算法每次运行的时间/s

由于本文算法利用每次聚类的类中心对缺失值动态地进行填充，多次有效地利用了含缺失值数据的已知信息，使得填充效果更好，从而聚类结果更优.相较于三种对比算法，本文算法在填充缺失值的同时，不断地寻找更接近于真实数据的聚类中心，从而得到更优的聚类结果.对于以上的7个数据集，除了ImageSeg数据集，本文算法在CA指标下的标准偏差都最小；除了Wine数据集，本文算法在CUN指标下的标准偏差都最小.由于使用的K-means算法是收敛算法，将所得到的聚类中心对缺失属性值填充，不仅合理地将聚类结果融入缺失值填充过程中，而且利用了K-means算法的收敛性，使得聚类效果相对稳定.从Iris，optdigis和pendigits三个数据集的CA和CUN值可知，K-means算法在数据集上效果越好，本文算法聚类准确率提高幅度越大.

表7中最长运行时间用粗体标识.通过表7中数据分析可知，当数据规模较小时，本文提出的算法耗时较多；当数据量较大时，本文算法的运行时间要低于对比算法三，而高于对比算法一和对比算法二.从mGamma数据集的运行时间对比可知，本文算法的运行时间取决于对缺失属性值进行填充的次数，对缺失属性值进行填充的次数越少，运行时间越短.从ImageSeg,optdigits和pendigits数据集的运行时间对比可知，本文运行时间相对于对比算法一的运行时间越长，聚类效果较好.

4 结论

针对不完备数据聚类问题，本文提出了一种动态填充的聚类算法，在UCI数据集上，通过与传统填充聚类算法进行实验对比分析，结果表明提出的算法可以得到较好的聚类效果.