基于异常检测的K-means改进算法研究

薛晨杰 林婷薇

摘 要：K-means算法作为较为普遍的聚类算法，聚类效果受孤立点、噪声点和初始聚类中心影响较大。结合Isolation Forest算法计算数据中每个样本的异常度系数，根据离群值过滤比例计算得到异常度系数阈值，对高度异常值加以隔离，并对隔离后的数据集使用平均插值法求得初始聚类中心。运用改进K-means算法对真实数据集进行聚类分析，与此同时，通过比较多个离群值过滤比例下的聚类结果，找到离群值过滤比例的最优取值。仿真结果表明，相比于原始算法，新算法显著提升了聚类准确性，聚类效果更佳。

关键词：K-means算法;聚类算法;异常检测;异常度系数;离群过滤比例

DOI：10. 11907/rjdk. 182467

中图分类号：TP312文献标识码：A文章编号：1672-7800（2019）004-0074-05

0 引言

随着数据挖掘技术的迅速发展，日常生活产生的海量数据中隐含的信息及商业价值越来越多地被挖掘与展现出来。聚类分析是数据挖掘中的常用分析方法[1]，其目的是将输入的数据样本通过聚类找到数据特征，然后根据样本相似程度将数据集合分成若干个簇，使每一个簇中的数据点达到最大同质化，而使不同簇之间的差异最大化。聚类算法研究历史悠久，早在1975年Hartigan[2]即在其专著《Clustering Algorithms》中对聚类算法进行了系统论述。研究者通过观察聚类分析结果可以发现数据中隐藏的联系与差异，从而将该数据分析结果作为新研究中的依据[3]。

K-means[4]聚类算法是目前最基本且被广泛应用的聚类分析方法之一，是由MacQueen总结Cox[5]、Fisher[6]、Sebestyen[7]等研究成果而提出的一种经典的以数据点到簇中心距离作为优化目标的函数聚类方法，但其仍然存在一些缺陷，比如受孤立点、噪声点以及初始聚类中心影响较大等。因此，学者们对此进行了大量研究。Metropolis等[8]提出的模拟物理学上固体退火过程的优化算法，有着更好的聚类效果，但会增加算法复杂度;Dong 等[9]首先通过二分K-means算法将数据集分为 K 个大类，再利用模拟退火算法优化聚类中心，从而提高了聚类准确度;Bhuyan等[10]提出可用遗传算法改进聚类效果，随后Jones等[11]、Babu等[12]也相继提出应用遗传算法改进K-means算法初始聚类中心的思路。以上改进算法都是基于优化算法，与此同时也有不少学者基于密度分布情况选择聚类中心。Katsavounidis等[13]提出一种通过尽可能分散初始聚类中心的解决方法，从而有效避免了被选择的聚类中心过于密集的情况;Khan等[14]提出的 CCIA 算法，利用数据点的均值、标准差、百分位数等统计信息提供数据点密度分布信息，从而得到初始聚类中心;牛琨等[15]提出基于密度指针的初始聚类中心选择算法DP，根据密度差异确定密度指针方向，并计算出聚集因子，最后将具有较大局部聚集因子的重心作为初始聚类中心。

本文结合Isolation Forest算法[16]计算数据异常度系数后对高度异常值加以隔离，并使用平均插值法求得初始聚类中心，以减少孤立点和噪声点对算法聚类效果的影响，从而对算法加以改进。最后选取若干个现实数据集对改进前后的算法进行实验，并对实验结果进行分析检验。验证结果表明，改进的K-means算法相较于原始算法具有更好的性能及聚类效果。

1 K-means聚类算法简介

K-means算法选择期望的簇中心K，通过不断迭代和重新计算聚类中心，以极小化整个簇内方差，将得到紧凑且相互獨立的簇作为算法最终目标。利用函数的求极值方法，调整迭代次数阈值获得最佳聚类效果。

原始K-means算法具体流程如下：

（4）重复执行步骤（2）-（4），直到聚类中心不再发生变化为止。

K-means算法作为经典聚类算法，有着高效简洁的优点，但同时传统K-means算法也存在较为明显的缺陷[17]。笔者总结列出以下两点较为普遍的缺陷：

（1）孤立点和噪声点对算法聚类效果影响较大。传统K-means算法不适合应用于样本差异过大的簇，其对于孤立点和噪声点数据十分敏感，即使是少量孤立数据都会对算法性能与结果造成很大影响，从而使平均值产生偏离。

（2）初始聚类中心选取对聚类效果影响较大[18]。在K-means算法中需要先根据初始聚类中心确定初始簇的划分，再对簇进行优化。算法聚类结果对初值选取的依赖性很强，一旦初始聚类中心选择不佳，可能无法得到最好的聚类结果。

2 算法改进

针对K-means算法存在的问题，提出如下改进方案：

（1）在使用K-means算法进行聚类之前，首先根据Isolation Forest异常检测算法，得到每个数据样本的异常度系数，将异常度系数值大于阈值的所有样本标记为异常离群点，然后对这些点进行过滤，在进行簇中心计算时不再使用这些异常数据点和离群数据点。

（2）在初始化簇中心时，不采用随机初始化方法，而是首先统计出除异常值和离群值外的数据样本在每个维度上的取值范围，再根据需要计算类簇数，使用平均差值法得到初始聚类中心。

2.1 Isolation Forest算法

Isolation Forest算法采用二叉树对数据进行切分，数据点在二叉树当中所处的深度反应了该数据在集合中的离散程度。该算法性能好、效率高，能有效处理多维数据及海量数据。算法流程可大致分为以下两步：①构建。抽取一批数据样本，构建多棵二叉树并组合成森林;②计算。综合每个二叉树结果，计算集合中每个数据点异常值。

（1）构建：对给定的数据集D，随机选择一个属性，并在该属性最大值与最小值之间随机选择一个值，将数据集中小于该值的数据划分到二叉树左分支，大于等于该值的数据划分到右分支。重复上述步骤直到数据集只有一条或多条相同记录，或二叉树达到限定高度，算法流程如下：

算法1 生成树

输入： 数据样本集合[D]，当前树高[h]，限定高度[l]

输出： 生成的二叉树

1： 检测树高是否大于限定高度，D中是否只包含一条数据或全部数据相同

2： 若是则输出节点数

3： 否则随机选取包含于样本集合D的数据属性

4： 随机在该属性最大值和最小值之间选取一个参数值

5： 将样本中小于该值的划分到左分支

6： 将样本中大于该值的划分到右分支

7： [重复上述]步骤直到满足步骤1条件为止

8： 结束，返回二叉树

（2）计算：由于异常点对于数据集而言十分稀有，所以可以通过根节点和叶节点的路径[h（x）]判断一个数据点[x]是否为异常点，采用公式（3）进行计算。

从异常度系数公式中可以发现，数据点在每棵树中的平均路径越短，公式值越接近1，则表示数据是异常点的可能性高;反之，数据在每棵树中平均路径越长，公式值越接近0，表示数据是正常点的可能性较高。如果大部分样本系数都趋近于0.5，说明整个数据集没有明显异常值。

2.2 改进K-means算法

通过使用上述Isolation Forest算法得到每个样本异度系数之后，选取所需的类簇数[k]和离群值过滤比例[r]。离群值过滤比例是指过滤数据个数占总数据样本个数的百分比，即使用改进K-means算法需要过滤多少比例的离群点后再进行聚类，默认为0.1。由于需要聚类的数据样本集合中的数据个数通常有限，因此直接将离群过滤比例值基于样本个数进行隔离，通常会造成隔离数据量过大而产生不必要的误差。针对该问题，笔者根据异常度系数[θ]和离群过滤比例r，拟定异常度系数阈值公式：[t=θmax-（θmax-][θmin）×r]，即对异常度系数[θ]大于t的数据加以隔离，以避免由于隔离数据数目过大造成的误差。

聚类算法结果对初值选取的依赖性很强[19]，因此选取优质的初始聚类中心是改进算法的重要一步。本文通过统计样本在各维度上的取值范围，结合平均插值法思想进行初始聚类中心选取，即尽可能将初值均匀选取在数据集合内部，减少边界值对初始聚类中心选取的影响。对于取值范围为[i，j]的属性T，根据所需类簇数k，应用公式（5）计算初始聚类中心。

获得高质量的初值之后，将过滤的异常样本归入剩余样本集合中，进行多次迭代，直至函数收敛，改进算法如下：

3 实验仿真

本节通过对多个真实数据集分别使用原始K-means算法及改进后的K-means算法进行聚类，获得两种聚类算法得到的结果并加以对比，再根据多种聚类效果评估算法对结果进行评估，直观展示改进聚类算法的聚类效果。

3.1 数据准备及预处理

实验选择8个真实数据集进行聚类，分别为动物数据集、红酒数据集、森林类型数据集、鸢尾花数据集、小麦种子数据集、脊柱数据集、ILDP（印度肝脏患者）数据集和病树数据集，具体如表1所示。

聚类算法目标是实现簇内相似度最高且簇之间相似度最低[20]，这是一个集群质量内部标准，但是良好的内部标准并不一定在应用中转化效果最好，因此需要对聚类结果的应用效果进行直接评估。本次实验准备采用如下几种评估聚类质量算法：

（1）purity是一种简单、透明的评价方法，每个簇都被分配给最频繁出现的类，然后通过计算正确数目测量准确性，如式（6）所示。

（2）Rand Index假设数据集合中存在N个样本，则有[N（N-1）2]个集合对，并将同一类样本分配到同一个簇和不同簇分别定义为TP和FN，将不同类样本分配到同一个簇和不同簇分别定义为FP和TN。Rand Index计算公式如式（7）所示。

Rand Index存在的缺陷是对假阳性和假阴性给出了相同权重，分离相似样本有时比在同一个簇中放置成对的不同样本效果更差。对此可以使用F测量方法通过选择一个值对假阴性结果进行更强的惩罚，从而加大召回权重，以提高评估准确性。F测量方法如式（8）-式（10）所示，其中Presicion和Recall数值分别由P和R表示。

3.2 实验及结果分析

本文首先采用动物园数据集，该数据集包含动物园中生活的101种动物，并根据动物们具有的如水陆生、胎卵生、哺乳类还是两栖类、是否有毒等17个特征属性，将全部动物集分为7个大类。

处理完数据集之后，利用改进前后的兩种算法分别对数据集进行聚类，设置离群值过滤比例[r]为0.1，获得的聚类结果如图1、图2所示。

观察图1、图2可以发现，原始K-menas算法虽然对数据集进行了聚类，但总体仍十分杂乱。运用改进算法进行聚类后，绝大部分相同属性的样本被归到同一类簇中，而不同属性样本被分开在不同簇中，分类效果较原始结果有明显提升。

仅通过观察图得出结论并不十分可靠，所以采用上文提到的聚类算法评价指标对结果进行评估。分别使用原始K-means算法和改进K-means算法聚类后的结果进行多项指标评估，得到如表2所示评价结果，其中Pro-Kmeans算法为改进后的K-means算法。

将实验数据绘制成折线图，如图3所示。

比较上述聚类算法评价结果可以发现，改进K-means算法较原始算法对数据集有着更好的聚类效果，算法性能更佳。为验证算法的改进效果，对剩余的被选数据集进行实验，得到实验结果如表3所示。

为使改进算法的结果更具有说服力，将改进算法中的离群值过滤比例[r]在[0.1，0.5]范围内选取多个不同数值，根据不同离群值过滤比例再次对算法聚类效果进行实验，获得结果如表4所示。

将4个数据集在不同离群值过滤比例下的F值绘制成折线图，与对应的原始K-means进行对比，如图4所示。