杨 红 ，李丹宁 ，王雅洁

（1.贵州大学 大数据与信息工程学院，贵州 贵阳 550025；2.贵州省食品安全检测应用工程技术研究中心有限公司，贵州 贵阳 550022）

0 引 言

伴随着大数据时代的发展，各种数据信息呈现出爆炸式的增长，计算机软硬件的不断升级，让各种数据层出不穷，为了更好的利用数据中隐藏的信息，数据挖掘技术顺应时代的发展出现在了学者与研究人员的视野。进而聚类分析也再次出现在了潮流的前沿，在图像处理、模式识别、病毒入侵检测等等习以为常的地方总是能够出现蕨类分析的身影。应用广泛、理论基础扎实、方便实用等优点，使得聚类分析几十年来一直是研究者们的心头所爱。

以划分为目的的算法更是频频出现在各种场合，为人们解决了无数问题。而K-means作为其中最具有代表性的算法，被列入了“十大经典算法”，其产生的价值自然不必都说。虽说K-means 算法易于实现，速度理想，然而人无完人，金无足赤，该算法也理所当然的存在些许不尽如人意的地方：（1）初始聚类中心是随机产生，进而直接导致聚类结果也存在随机性，准确性低；（2）聚类个数K值不好确定，K值的选取直接决定了聚类结果的准确度；（3）数据集中离群点的存在也会影响聚类结果，如若将离群点选为初始中心点，不仅仅会降低速度，增加时间复杂度，甚至可能会出现错误[1-2]。

很多学者针对K-means存在的不足之处提出了相应的改进方法。杨莉云等[3]提出引入谢林模型，使孤立点能够自动移动到其邻居所在位置，消除孤立点，但是此方法对数据集进行了改变，数据集发生了变化。唐泽坤等[4]在K-means算法的基础上权衡了密度和距离对聚类的影响，对数据进行加权处理，在权值基础上引入“最小最大原则”选择初始聚类中心，自动确定类中心个数。以上方法都在一定程度上对算法的聚类结果进行了优化。

1 K-means算法

聚类算法是一种无监督学习算法；何谓的无监督学习？简而言之，就是输入的数据没有标签，目标是通过对无标签数据的学习来了解数据之间的内在联系和本质，为下一步的数据处理及数据分类提供扎实的基础。其算法步骤如下：

输入无标签数据集X，聚类数K；

i：在数据集中随机选取K个样本作为初始质心；

ii：分别计算数据集中每个样本对象Xm到K个质心的欧式距离；

iii：找到与每个样本对象Xm距离最小的质心ci，同时将该样本对象Xm归为与ci相同的簇中；

iv：计算同一簇中的平均值，所得即为新的质心；

v：重复i-iv，直到质心不再发生改变

通常对于欧式空间的样本数据，以平方误差和（Sum of Squared Error，SSE）作为聚类的目标函数，同时也可以衡量不同聚类结果的好坏。

表示样本点x到簇点中心ci的的距离平方和，最优的聚类结果应使得SSE达到最小值[5]。

K-means算法具有执行效率高、易于实现等优点，但是分类效果会受到多种因素的影响，如数据集本身、K值的确定，初始簇中心的确定等等。

为了使最终输出的聚类效果更加理想，文中提出利用离群点检测算法先对数据进行预处理，剔除算法检测出的离群点，然后再用K-means算法对处理过的数据集进行分类。

2 离群点检测（Local Outlier Factor，LOF）算法

在数据挖掘方面，数据正式使用之前通常要进行预处理，本文便利用离群点检测算法对数据进行了预处理，既对数据集中的离群点进行筛选，目的是减小异常点对聚类效果的影响，提高算法效率。离群点检测算法原理介绍如下：

LOF算法相关定义：

（1）d(A,O)点A与点O之间的欧式距离。

（2）第k距离（k-distance）

点A的第k距离dk(A)：dk(A)=d(A,O)，从通俗意义上来讲，A的第k距离，就是距离A第k远的点到A的距离（不包括A本身）。

（3）第k距离领域（k-distance neighborhood）

点A的第k距离领域，就是以A为圆心，以第k距离为半径的区域以内的所有点（包括圆上的点）。因此A的第k领域点的个数至少是k个。

（4）可达距离（reach-distance）

点O到点A的第k可达距离定义为：

也就是点O到点A的第k可达距离取dk(A)与d(A,O)两者之间的较大值。

（5）局部可达密度（local reachability density）

点A的局部可达密度表示为：

表示点A的第k领域内的点的平均可达距离的倒数。

Irdk(A)代表一个密度，密度越高，代表A周围的点越多，显而易见，我们认为A越可能与周围的点属于同一簇，相反，密度越低越可能是离群点。概括来说就是，局部可达密度与成为离群点的概率成反比。

（6）局部离群因子（Local Outlier Factor）

点A的局部离群因子表示为：

点A的邻域点Nk(p)的局部可达密度与点A的局部可达密度之比的平均数。

如果这个比值越接近1，说明A的其邻域点密度差不多，A可能和邻域同属一簇；如果这个比值越小于1，说明A的密度高于其邻域点密度，A为密集点；如果这个比值越大于1，说明A的密度小于其邻域点密度，A越可能是异常点[6]。

3 LOF-K-means算法介绍

为了优化算法，本文提出了利用离群点检测算法（LOF）对离群点进行筛选，其算法步骤如下：

输入：数据集X，聚类数K；

输出：聚类结果；

i 将LOF算法应用与iris数据集，得到每个数据的局部离群因子，从而得到一个密集点数据集iris-1和一个离群点数据集iris-2；

ii 用K-means算法对数据集iris-1进行聚类，得到该数据集的聚类结果；

iii 将数据集iris-2直接按iris-1的结果进行分类，无需重新计算质心，进行循环；

iv 输出最终分类结果。

算法流程图如图1所示。

在本文提出的算法中也对传统K-means的准则函数进行了改进，传统准则函数仅仅考虑到类内的相似性，改进后的准则函数将类与类之间的差异性也做了充分考虑[7]。

其中，SSE1为传统K-means算法中的准则函数，仅考虑类间相似度，d(ci,cj)为第i个质心和第j个质心间的欧式距离。

SSE2由类间距离和类内距离共同决定。类内距离小的同时类间距离大的聚类结果则是理想的聚类结果。SSE2的值与类内聚类成正比，与类间距离成反比。既分子越小，分母越大，SSE2的值就越小，聚类效果就越好。

图1 LOF-K-means流程

4 实验仿真与分析

为验证文中算法的有效性及合理性，本文选用了UCI标准数据集中的鸢尾花卉数据集（iris）进行仿真实验。该数据集包含150个数据集，分为3类，每类50个数据，每个数据包含4个属性，文中利用二维数据集进行实验，筛选了数据属性中的前2个属性，即花萼长度和花瓣宽度。

iris数据集原图如图2所示。开始未对数据进行预处理，直接采用K-means对数据集分类，其中k=4，分类结果如图3所示。

图2 iris数据集原图

图3 iris数据集K-means分类

之后采用离群点检测算法（LOF）对数据集进行预处理，筛选并剔除原数据集10%（15个）的离群点之后再利用K-means分类，结果如图4所示。

图4 LOF分类结果

本文采用质心两两之间距离的平均值来衡量类间的离散程度，质心之间的距离越大说明类间的离散程度越大，聚类效果越好，仿真结果如表1所示，由表1的数据可以看出，本文的算法比传统的K-means算法得出的分类效果类间距离更大，类间离散效果更理想。

表1 4个质心两两之间距离的平均值

同时以平方误差和（SSE）作为目标函数来评价类内聚合度。两种算法得到的聚类效果分析数据如表2所示，由表2可知，从整体来看，本文算法得到的SSE小于传统K-means算法得到的SSE，4种聚类结果的平方误差和分别在原来的基础上提高了41%、29%、46%、40%，类内聚合度平均提高了39%。由此来看本文采用的算法在提高类内聚合度上表现良好，可以在较大程度上使类内的聚合效果更加理想。

表2 两种算法SSE比较

5 结 语

本文提出了将离群点检测算法与K-means算法相结合，对数据集进行预处理之后再进行分类的算法，巧妙地避免了离群点对聚类效果带来的不良影响，同时对传统的准则函数进行了改进，本文采用的准则函数不仅考虑到了类内的相似度，也考虑到了类与类之间的差异性，使得聚类结果进一步优化。