基于质心投影波动的离群点检测算法

张忠平，张玉停，刘伟雄，邓 禹

(1.燕山大学 信息科学与工程学院，河北 秦皇岛 066004；2.河北省计算机虚拟技术与系统集成重点实验室，河北 秦皇岛 066004；3.河北省软件工程重点实验室，河北 秦皇岛 066004)

0 引言

离群点检测旨在发现数据集上的特殊数据对象或模式，是数据挖掘的一项重要挑战。离群值检测技术已广泛应用于许多领域，如工业无线传感器网络[1]，欺诈检测[2-3]，入侵检测[4]，心电图异常检测[5]等。离群点检测又称异常点检测，其目的是检测出与绝大多数对象存在差异的对象。一般离群点检测方法分包括基于统计的方法、基于分类的方法、基于近邻的方法等。其中基于近邻的方法主要分为基于距离的方法和基于密度的方法。基于距离的方法以距离体现“近邻性”，基于密度的方法则以密度体现“近邻性”[6]。

KNORR等[7-8]是最早提出使用基于距离的离群点检测算法，该算法克服了基于统计的方法需要提前选定模型和参数的问题。该方法利用每个数据对象到邻居点的距离作为度量数据对象的离群程度，使其适用于各种高维数据集，但也存在算法时间复杂度高，对参数选取较为敏感的问题。同时，由于使用全局阈值，难以检测不同密度区域处的局部离群点。BORIAH等[9]使用k近邻思想提出一种可以处理大数据集的离群点检测算法，但该算法在计算每个数据对象的邻域时需要重新检索整个数据集，使得算法的时空开销较大。

在基于密度的离群点检测方法中，其假设离群点的密度与邻居点的密度区别很大，即一个点的局部密度明显不同于其邻居点，则该点被检测为离群点。基于上述想法，近年来提出众多离群点检测算法，此类算法因计算数据对象的密度方法而不同。文献[10]使用LOF(local outlier factor)值作为衡量一个点的离群程度，提出了LOF算法，该方法通过数据点的邻域可达密度与该点的局部密度的比值得出对应的LOF值，该值越大，表示该点越可能是离群点。该方法通过LOF值表示一个点的离群程度，改变了以往算法对离群点直接给出判定结果的做法。由于现实世界数据的复杂多样，文献[10]中的算法存在很多不足。文献[11]提出反向k近邻“RNN”的概念，并构造了局部离群因子INFLO以提高算法对离群点的检测性能。该方法在计算每个点的局部密度时，不仅考虑k近邻集合，还考虑反向k近邻集合。因此，能够减少在数据分布复杂情况下基于k近邻的算法可能出现的误判。TANG[12]提出一种基于连接的COF算法,该方法提出链距离的概念以有效地确定数据对象的个性化局部空间，进而克服了LOF算法对低密度区域的数据对象不能有效度量的缺陷。除此之外，在LOF算法基础上，还产生了自然邻居因子(Natural Outlier Factor, NOF)算法[13]、局部稀疏系数(Local Sparsity Coefficient, LSC)算法[14]、多粒度偏差系数(Multi-granularity Deviation Factor, MDEF)算法[15]等。基于密度的离群点检测方法可以检测各种复杂的数据形式。但大多数算法对近邻参数k的选取较为敏感且在高维数据集应用时需要很大的时空开销。

近年来在离群点检测领域不断提出新颖的方法。文献[16]利用累计全熵挖掘最佳聚类子空间，并在最佳聚类子空间中检测离群点，大大提高了算法处理的效率;文献[17]将自然邻居搜索算法和密度峰值聚类算法结合，提出一种基于聚类离群因子和相互密度的离群点检测算法，该算法不需要人为指定参数，且有较好的离群点检测性能;JIANG等[18]提出一种基于重力的概念用于离群点检测,该方法首先为数据对象赋予质量定义，利用变形后的万有引力公式计算每个数据对象在其邻域内受到的合力LRF，最后通过不同类型的数据对象合力变化率的差异来识别数据集中的异常点;文献[19]利用自然邻居的概念自适应的获取邻域k值，通过加权核密度估计方法获取数据对象的局部密度。最后利用邻域平均密度与数据对象的局部密度之比获取该点离群程度，进而提高了离群点的检测性能。针对k邻域关系存在的检测效果差，k值选取较为敏感的问题，文献[20]提出一种近邻树(Nearest Neighbors Tree, NNT)的邻域关系用于离群点检测，利用每个数据对象近邻树结构最长边和剩余边均值的比值表示该数据对象的离群程度。该算法相比于基于k邻域关系的算法有更高的准确率且对k值不敏感。

随着数据类型越来越复杂以及数据维度不断增加，基于k近邻关系的离群点检测算法检测效果不够理想。引入新的邻域关系可以为离群点检测提供新的研究方向。针对上述问题引入近邻树(NNT)的邻域关系，提出一种基于质心投影波动的离群点检测算法(Outlier Detection algorithm based on Fluctuation of Centroid Projection, FCPOD)。该算法引入近邻树关系，为每个数据对象提供一个质心投影。质心投影既能考虑样本点到邻居点的距离，也能考虑样本点与其邻域集合的分布特征。随着k值的增加，离群点区域的质心投影波动要远高于内部正常点。最后，利用数据对象的质心投影波动刻画每个点的离群程度。

1 相关工作

1.1 相关定义

给定数据集D={xi},i=1,…,n,xi∈Rd，其中d为数据对象xi的维度个数，算法涉及的概念和定义如下。

定义1点p的近邻树。给定数据集D，顶点集N，边集E和参数k，则以点p为起始点的近邻树NNTk(p)定义为式(1)所示：

NNTm(p)=

(1)

式中：k表示近邻树边的个数，1NN(·)表示距离第一个最近的邻居点；Nm-1表示第m-1次迭代后近邻树的顶点集。为避免NNT树形成环，式(1)中1NN(q)∉Nm-1。

近邻树构造：点p的NNT树构造过程和最小生成树类似，首先将数据对象p放入顶点集N中，寻求距离顶点集N中数据对象最近的邻居点，且该邻居点不在顶点集N中。然后将该点和对应的边分别加入顶点集和边集中。不断迭代该过程直到NNT中边的个数达到k，则点p的近邻树构造结束。

如图1所示为点1，6，10的近邻树结构。其中：k=4，点1，6，7为离群点，其他点为正常点。点1的近邻树结构为NNT4(1)={1,2,2,3,3,4,3,5}，点6的近邻树结构为NNT4(6)={6,7,6,8,8,9,9,3}，点10的近邻树结构为NNT4(10)={10,11,10,12,10,13,11,14}，从图1中可以看出以1，6，7为代表的离群点近邻树关系可以快速扩展到高密度区域。且由于近邻树邻域关系的特殊性，相比传统的k近邻邻域关系，离群点的邻居点有更高概率出现在的离群点的一侧。当面对不同类簇的影响时，离群点的邻居点更倾向出现在第一个最近点所在的类簇。这种特性可用于下文离群点的检测。

定义2点p的邻域。给定数据集D，点p近邻树顶点集N中数据对象的集合称为点p的邻域，记作NN(p)。

定义3点p的质心(邻域质心)。给定数据集D，点p的邻域集合中数据对象的重心称为点p的质心，记作c(p)，

(2)

式中：k为邻域集合数据对象的个数;q为包含d个维度的向量。不包括数据点本身的邻域质心更能刻画出数据点到邻域质心的距离和邻居分布。

定义4点p的质心向量。点p指向其质心c的向量称为点p的质心向量，记作pc。

定义5点p的质心投影。点p指向其邻域集合中数据对象形成的向量沿着pc方向的投影称为点p的质心投影，记作CenV(p,k)，

(3)

在图3中，P1为离群点，P2为内部点。其中，P1到P4的距离比P1到P3的距离稍大。使用传统的k近邻关系选定P1的邻居点会依次包含P3和P4，使得P1在左右两个类簇中都存在邻居点，因此可能难以检测出P1为离群点。为解决上述问题，本文使用近邻树邻域关系刻画数据对象的邻域点，由于P1到P3的距离比P1到P4的距离稍近，P1会首先选中P3为第一个邻居点，然后由于近邻树的特性，P3所在类簇中的部分点会被依次选为P1点的邻居点，使用近邻树邻域关系可以使离群点P1的邻居点集中在最靠近离群点的类簇中，减少了不同类簇对离群点判定的影响。离群点P1随着邻居点的增加，质心投影的值不断增大且方向大致相同。内部点P2随着邻居的增加，质心投影基本保持不变且由于邻居点分散在P2点周围，投影方向也较为均匀地指向其周围。因此，可以看出随着k值的增加离群点和内部点质心投影变化不同。

为进一步验证随着k值增大不同类型点质心投影变化不同这一特征，在人工数据集A1上进一步进行验证。图4表现的是在不同k值下，离群点和内部点质心投影的变化。可以清楚地看出，随着k值的增大，离群点的质心投影不断增大，波动较为剧烈。内部点的质心投影虽有波动但较为平稳且一直维持在较低的水平。由图3和图4可以看出随着数据对象使用近邻树关系得到的邻居点不断增多，离群点的质心投影波动要远大于内部点的质心投影波动。因此，通过质心投影变化波动可以很好地刻画数据对象的离群程度，数据点质心投影波动越大，表示该数据点越有可能是离群点。

2 基于质心投影波动的离群点检测算法

由于传统使用k近邻关系算法中离群点易受不同类簇影响而导致检测效果不佳，本文引入近邻树邻域关系，使得离群点通过近邻树邻域关系可以快速得到高密度区域的邻居点。同时，由于近邻树邻域关系的特性，离群点邻居点的更倾向出现在距离离群点最近的一个类簇中，因此可以避免传统使用k近邻关系算法离群点检测存在的问题。由于离群点的质心投影波动要远远大于内部点的质心投影波动，本文使用质心投影波动来刻画数据对象的离群程度。数据对象的质心投影波动越大，表明该数据对象越有可能是离群点。

2.1 算法思想

从定义5的分析可以看出，由于离群点和内部点的邻居分布不同，随着邻居点的增加，离群点的质心投影不断增大，内部点的质心投影基本保持不变。因此，可使用不同k值下，质心投影波动进行刻画数据对象的离群程度。

定义6点p的质心投影变化。给定数据集D，参数k，点p在k和k+1下质心投影的差值称为点p在k值下的质心投影变化，记作ΔCenV(p,k)，

ΔCenV(p,k)=|CenV(p,k+1)-

CenV(p,k)|,

k=2,…,K。

(4)

定义7点p的质心投影波动。给定数据D，点p在不同k值下质心投影变化的总和称为点p的质心投影波动，记作ΘCenV(p,K)，

(5)

式中K为算法设定的最大k值。

由于不同类型的数据对象使用近邻树邻域关系得到的邻域集合的分布不同，利用质心向量投影波动可以很好地刻画出数据对象的离群程度。如图5所示为人工数据集A5中离群点和内部点的质心投影波动，其中箭头长度为数据对象质心投影波动值，箭头方向为K值下的质心向量方向。数据点“”代表离群点，其质心投影波动要远远大于内部点，因此使用数据对象的质心投影波动能很好地区分离群点和内部点。

基于上述分析，本文提出FCPOD算法。首先，引入近邻树邻域关系来代替传统基于k近邻的邻域关系，使得数据对象的邻居点可以快速扩展到高密度区域，也减少了因获取不同类簇的邻居点对离群点检测造成的影响。同时，不同类型点使用近邻树获取的邻居点分布不同，离群点的邻居点主要分布在其一侧，内部点的邻居点一般分布在其四周。然后利用该特性，使用数据对象的质心投影刻画不同类型点的邻居分布特性。随着k值的增大，离群点的质心投影变化要远大于内部点的质心投影变化。因此，本文最后使用质心投影波动衡量数据点的离群程度，数据点的质心投影波动越大，该数据点越有可能是离群点。

2.2 FCPOD算法描述

本节主要描述FCPOD算法的执行过程。FCPOD算法需要输入数据集D和邻居点个数K，其输出为top-n个数据对象的索引值。该算法利用质心投影波动值衡量数据对象的离群程度。首先构建每个数据的近邻树结构获取其邻居点，每指定一个k值可得到对应的质心投影。然后，将数据对象质心投影的变化进行加和以获取最终的质心投影波动。最后，利用该质心投影波动对数据对象进行排序，将排序结果得分最高的top-n个点视为离群点。

根据2.1节算法思想及相关定义，FCPOD描述如下：

算法1FCPOD算法。

输入:DatasetD，K;

输出:top-noutlier inD。

1.初始化：index=∅，k=1

2.创建数据集D的KD树 //用于加快邻居检索

3.For each p∈D do

4. For k in 2 to K

5. Create NNT(p); //创建p点的NNT树

6. Get NN(p); //获取p点的邻域集合

7. Get c of p //获取p点的质心

8. Get CenV(p,k) //获取p点的质心投影

9. IF k>2

10. Get ΔCenV(p,k) //获取p点的质心投影变化

11. End IF

12. End For

13. Compute ΘCenV(p,K) //获取p点的质心投影波动

14.End For

15.Sort ΘCenV(p,K)in descending order //降序排序离群因子

16.Output top-n outlier

FCPOD算法的时间复杂度主要来源于以下两部分：①为得到每个数据对象的K个最近邻居而构建的KD-tree，时间复杂度为O(n·logn)，n为数据集的数据对象个数；②计算数据对象质心投影波动ΘCenV(p,K)，时间复杂度为O(n·K)，K≪logn

3 实验评估

为评估FCPOD算法的性能，使用局部离群因子(Local Outlier Factor, LOF)[10]连接异常因子(Connective Outlier Factor, COF)[12]、孤立森林(Isolation forest, IForest)[21]、直方图的异常因子(Histogram-based Outlier Score, HBOS)[22]和局部结构异常因子(local structure outlier factor, LSOF)[19]算法在人工数据集和真实数据集上进行实验验证，比较分析本文算法的性能。本文FCPOD算法和上述选定的5个对比算法一样，不再二元化地判断每个数据对象是否是离群点，而是为每个数据对象赋予一个离群程度，然后利用该离群程度对数据对象进行排序，选取前n个点为检测出的离群点。同时，选定上述5个对比算法也是为了方便绘制下文中算法的离群点发现曲线[23-24]。

其中，LOF算法是基于密度的离群点检测算法中最为经典的算法，多用于算法性能比较的基准算法。COF算法在LOF算法基础上进行改进，LOF和COF算法能基本代表基于密度的离群点检测算法，由于LOF算法和COF均未使用特殊的邻居检索策略，其时间复杂度均为O(n2)。HBOS算法是一种基于直方图估计密度的无监督异常检测算法，本质上是一种基于统计的离群点检测算法，其时间复杂度为O(n·logn)。IForest算法由于具有线性的时间复杂度和很好的检测性能，一直是离群点检测算法最为经典的代表之一。LSOF算法是第一个将近邻树邻域关系引入离群点检测的算法，在使用如KD-Tree这类的结构用于检索邻居点后，其时间复杂度为O(n·logn)。本文选用基于密度的离群点检测算法、基于统计的离群点检测算法、IForest和LSOF算法与本文算法进行对比分析，能较为全面且有效地比较分析FCPOD算法的性能。实验环境如表1所示。

表1 实验环境

3.1 评价指标

在大多数实际应用中，相比大量存在的正常数据，含异常值的数据显得很稀有，使得在离群点检测过程中出现数据不平衡现象。因此，在离群点检测领域很少有研究者直接使用传统度量指标如准确率、精确率等来衡量离群点检测性能。ROC曲线(receiver operating characteristics curve)即受试者工作特征曲线，可以综合考虑敏感性和特异性的影响，使得其被广泛用于度量非平衡数据集。ROC曲线是指真阳性率随着假阳性率变化的曲线，其中真阳性率和假阳性率定义分别如式(6)和式(7)所示。

(6)

(7)

其中：TP表示判断为离群点实际也为离群点的个数；FP表示判断为离群点实际却是内部点的个数；TN表示判断为内部点实际也为内部点的个数；FN表示判断为内部点实际却是离群点的个数。

AUC(area under curve)值描述的是在ROC曲线下方的面积，其值范围为0～1。AUC值大的离群点检测算法意味着有更大的概率将离群点排在内部点之前[25]。因此，AUC值越大算法表现越好。

离群点发现曲线(outlier discovery curve)[23-24]用于描述算法检测出离群点个数与查询个数之间的关系。离群点发现曲线中横坐标为离群点检测算法查询前n个点中真实的离群点个数，纵坐标为查询的个数n。离群点检测算法对应的离群点发现曲线爬升越快，表明它比同类算法能更加准确有效地检测离群点。

本文主要使用ROC曲线中的AUC值和离群点发现曲线衡量离群点检测算法的性能。LOF、COF、LSOF和本文FCPOD算法都需要指定一个k值以确定邻居点的个数。实验使用的k值为2～100。IForest算法是基于树结构的经典算法，为避免不平衡的隔离树对算法性能造成影响。实验中为IForest算法在每个数据集上进行100次实验取其平均值来衡量算法性能。实验各个算法均取其最优表现。

3.2 人工数据集实验

为测试本文算法在各种复杂数据分布下的性能。本文使用图6所示的6种二维的人工数据集A1～A6进行实验，其中离群点为“o”代表的点。人工数据集的属性特征如表2所示。其中A1和A3数据集为包含若干类簇且类簇之间的密度有差异的人工数据集，A2,A4,A5,A6为包含各种复杂数据分布的非球状类簇的数据集，选用图6所示的6种数据集能较为全面地检测本文算法在各种复杂数据分布下的离群点检测效果。

表2 人工数据集数据特征

图7展示了本文FCPOD算法和对比算法在人工数据集上的实验结果。由图7中可以看出，在人工数据集A2，A3，A4，A6中，随着查询数据点个数的增加，本文FCPOD算法查询出的真实离群点个数一直是最多的，而且离群点发现曲线基本维持在一条在直线上。FCPOD算法在人工数据集A1和A5上表现分别和IForest算法，LOF算法性能接近。FCPOD算法虽不在各个数据集都表现最优，但整体性能远远好于其他算法。因此，该实验验证了FCPOD算法可以适应各种复杂形状的数据分布且有较好的性能表现。

3.3 真实数据集实验

本文采用的6个真实数据集均来自UCI数据集，数据集的维度在4～60之间，离群点所占比例在4.4%～35.8%之间，以较为全面的检测FCPOD算法的真实性能，表3展示了真实数据集的数据特征。在数据预处理阶段使用式(8)进行归一化处理：

Xnorm=(X-Xmin)/(Xmax-Xmin)。

(8)

其中：Xnorm表示归一化后的数据对象，Xmax和Xmin分别为各个维度上最大和最小的值。对于缺失的空值属性使用数据集对应属性的均值代替。

表3 真实数据集数据特征

如表4所示为真实数据集下各个算法的AUC值，同时标注出每个真实数据集下表现最优的前两个算法。FCPOD算法在所有真实数据集上AUC值均属于表现最优的前两个算法。尤其在Iris，Sonar数据集上离群点检测性能远远好于表现次优的其他算法。在包含离群点数量多的Lonosphere数据集中，本文FCPOD算法也能保存较好的检测效果。Sonar数据有60个维度，随着数据集维度的增多，一般基于近邻性的算法检测效果较差，FCPOD算法不仅考虑数据对象到邻居点的距离，还考虑了数据对象与邻居点的分布关系，因此检测效果较好。

如图8所示为各算法在真实数据集上的离群点发现曲线。在Lonosphere，Iris，Sonar数据集的实验中，FCPOD算法在每次查询过程中检测出的离群点都是最多的。特别在Lonosphere数据集上，FCPOD算法检测出的离群点数量是HBOS算法的两倍左右。在Wbc数据集上LSOF，LOF和COF算法检测效果较差，而FCPOD算法和IForest算法表现较好。HBOS算法在Sonar数据集表现最差。总体上看，本文FCPOD算法能在各个数据集上都有较为出色的离群点检测效果，从而验证了本文算法能全面准确的检测到离群点。

表4 真实数据集各算法AUC值

从上述实验分析可知，本文FCPOD算法在人工数据集和真实数据集上都表现良好而且性能稳定。其中，本文算法选定数据集中数据分布较为复杂，而在集成制造领域中，工业数据集种类繁多且数据分布复杂，使用传统的k近邻关系的离群点检测算法由于数据集中不同类簇的相互影响导致算法难以快速有效地检测离群点。因此，本文算法比传统基于k近邻关系的离群点检测算法能更有效地处理工业数据集的离群点检测，而且算法性能较为稳定。

4 结束语

本文首先分析了传统基于近邻性的离群点检测相关算法思想和近年来较为新颖的算法。针对传统近邻关系检测离群点存在的问题，引入一种称为近邻树的邻域关系，采用质心投影刻画数据对象和其邻居点的关系，并利用离群点和内部点质心投影波动不同提出一种基于质心投影波动的离群点检测算法(FCPOD)。对FCPOD算法进行了详细阐述，并进行了时间复杂度的分析，同时也给出了对比算法的时间复杂度分析。最后对本文提出的FCPOD算法在人工数据集和真实数据集上进行实验验证，通过对实验结果的比较分析，验证了本文算法能有效且全面的检测离群点。虽然FCPOD算法在AUC值和离群点发现曲线上表现较好，但随着数据集的规模和数据维度越来越大，在不断出现的繁杂多变的数据集中，算法的检测精度和效率需要进一步的提高。因此，针对有数量庞大的、数据维度高的数据集，研究出检测精度高、耗时少的离群点检测算法是今后的主要研究方向。