ERDOF：基于相对熵权密度离群因子的离群点检测算法

张忠平，刘伟雄，张玉停，邓禹，魏棉鑫

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

1 引言

离群点是数据集中偏离大部分数据对象的数据，它们的表现和大多数数据对象有着明显的差异。离群点并不等同于错误数据，反而可能蕴含着极其重要的信息。离群点检测就是从海量数据中发现异常数据对象，是数据挖掘中的热门研究方向。目前，离群点检测广泛运用于工业无线传感器网络[1]、医疗处理[2]、欺诈检测[3]、垃圾邮件检测[4]、入侵检测[5-6]等领域，且有很多种分类，包括基于统计的[7-8]、基于距离的[9-10]、基于聚类的[11-13]和基于密度的[14-19]等方法。

基于统计的检测方法是根据现有的数据集结合统计学的方法生成模型，这类方法根据数据对象在模型中是否处于低概率区域来判断离群点。这类检测方法需要充分的数据先验知识，并且对于高维数据集的检测效果较差。

基于距离的检测方法主要通过计算数据集中每个数据对象和邻居点的距离来检测离群点，其中k 最近邻（KNN,k nearest neighbor）算法[9]是基于距离的方法中较常用的算法，基本原理是通过计算数据对象与其k个最近邻居的平均距离，通常离群点会远离正常点，因此平均距离越大，越有可能是离群点。由于KNN 算法通过全局距离来检测离群点，因此无法检测出局部离群点。

基于聚类的检测方法是一种无监督的学习方法，用作聚类的数据集不需要类标签，基本思想是将数据集通过聚类算法得到簇，并将数据对象与簇进行比较，通常离群点不属于任何密集簇。常用的算法有DBSCAN[12]和CHAMELEON[13]。然而此类方法需要根据不同的应用场景和数据本身特征采用不同的聚类方法，因此检测的有效性依赖于聚类方法的选用。

在基于密度的检测方法中，如果一个数据对象为离群点，那它的密度与其周围邻居的密度会有很大的差异。这类密度检测方法主要通过数据对象的局部密度和其邻域密度的差异来判断离群点。为了实现这个想法，研究人员提出了很多基于密度的离群点检测算法。其中局部离群因子（LOF,local outlier factor）算法[14]是最常用的一种离群点检测算法。LOF 代表一个数据对象的离群得分，用于表示该对象与其局部可达邻域之间的差异。该方法利用2 个数据对象之间可达距离来估计该对象的密度，该对象的离群得分是根据数据对象相对于其邻域对象的相对密度得出来的。文献[14]表明，离群得分更高的数据对象更有可能是离群点。之后，研究人员提出了很多基于LOF 的改进算法。Zhang 等[16]提出了一种基于局部距离的离群因子（LDOF,local distance-based outlier factor）算法来度量离群得分。文献[17]在LDOF 算法的基础上，增加了熵权距离的定义，改进并提出了一种基于熵权距离和局部密度的离群点检测（ELDOF,local entropy weight distance-based outlier factor）算法。

近年来，基于核的方法在离群点检测和聚类等领域得到了广泛的应用，基于核的方法利用核函数及其参数建立算法模型。文献[18]提出了一种基于密度的离群点检测算法，该算法将核密度估计（KDE,kernel density estimation）纳入LOF 框架中，并将一个数据对象的KDE 标准化成S分数，与其邻域的KDE 进行比较。

与本文算法最相似的算法是基于自然邻居的离群点检测（NaNOD,natural neighbour-based outlier detection）算法[19]，该算法是一种非监督的基于密度的离群点检测算法，使用自然邻居概念，自适应地获取一个自然值（NV,natural value）的参数，并使用加权核密度估计（WKDE,weighted kernel density estimation）方法来估计数据对象的密度。另外，该算法采用了KNN 以及反向k 最近邻（RNN,reverse k-nearest neighbor），使系统可以灵活地对不同数据模式进行建模，并采用高斯核函数来实现度量的平滑性。此外，该算法使用自适应核宽度概念来增强正常样本与离群样本之间的区分能力。

分析近年来较新颖的基于密度的离群点检测算法和相关算法思想可以发现，大多数基于密度的检测算法在一些低密度的区域内和在高维数据集上的检测效果会有所下降。因此，本文在已有算法的基础上，考虑到在低密度区域内局部离群点与内部点密度相近的问题，提出相对距离的概念，可以有效地将其区分开来，从而提高算法在低密度区域处理局部离群点的能力。此外，本文还考虑到高维度对于离群点检测的影响，并不是所有属性对离群点检测都是有作用的，因此本文引用了信息熵加权距离（EWdist,entropy-weighted distance）的概念，取代传统算法中的欧氏距离，为数据对象的不同属性分配不同的权重，给离群属性分配更高的权重，能放大离群点的离群程度，从而提高算法在一些高维数据集中的检测能力。针对上述问题，本文提出了一种基于相对熵权密度离群因子的离群点检测（ERDOF,outlier detection based on entropy weight distance and relative density outlier factor）算法来检测离群点。

2 相关工作

2.1 自然邻居

Zhu 等[20]提出了一个新的无参数邻居的概念，称为自然邻居。如果数据对象x把数据对象y看作自己的邻居，同时y也把x看作自己的邻居，那么就把x看作y的自然邻居。一般地，在稀疏区域内的数据对象拥有较少的邻居，而在稠密区域内的数据对象则拥有更多的邻居。

更重要的是，自然邻居可以在不使用任何参数的情况下有效地计算邻域。其主要思路是不断扩展邻居的搜索范围，每次搜索时记录每个数据对象被看作其他对象的邻居的次数，直到不被其他数据对象看作邻居的对象个数不变。由于数据对象在数据集中的KNN以及RNN的搜索代价较高，因此本文在自然邻居搜索算法[20]中使用Ball-Tree[21]。Ball-Tree是一个轻量级的二叉树，在高维数据集上性能良好且查询效率高。自然邻居搜索算法[20]流程如算法1所示。

算法1自然邻居搜索算法

输入初始数据集D

输出自然近邻值NV

18) 输出自然近邻值NV

在算法1 中，r表示邻域搜索范围，NaN(x)表示对象x被其他对象看作邻居的次数，KNNr(x)表示对象x的r最近邻域，RNNr(y)表示对象y的反向r最近邻域。本文在算法1 中应用了Ball-Tree 来提高邻域的搜索效率，时间复杂度为O(nlogn)，其中n表示数据集中对象的数量。

定义1自然邻域。KNNk(xi)和RNNk(xi)合并生成对象xi的扩展邻域空间称为自然邻域，定义为IS(xi)=KNNk(xi) ∪RNNk(xi)。其中，邻域的k值不是人为设定的，而是通过算法1 自适应得出的自然近邻值NV。

2.2 熵权距离

本文在计算数据对象之间的距离的时候，使用熵权距离取代传统算法中的欧氏距离，下面，给出信息熵加权距离的定义和信息熵加权算法[17]的流程描述。

设数据集D={x1,x2,…,xn]，其中n为数据样本大小。设属性集A={A1,A2,…,Ad}，其中d为数据样本维度数量。信息熵表示信息的不确定程度。熵值越大，信息的不确定程度越大，信息熵计算方法如式(1)所示。

其中，S(Ai)是属性Ai(i=1,2,…,d)所有可能的取值的集合。

定义2离群属性。在数据集D中，若属性Ai的信息熵大于或等于数据集的平均信息熵，则称之为离群属性。

通过式(2)的判断，符合条件的属性Ai看作离群属性。根据条件判断公式分类属性后，各属性的权重wi取值如式(3)所示，其中l＞ 1。

在数据集中，并非所有属性对离群点检测都是有作用的，因此，在计算距离时，为离群属性提供更大的权值能更好地突显离群点的离群程度，从而提高离群点和内部点的区分能力，其中参数l在本文中默认设定为1.5。

定义3熵权距离。熵权距离是具有信息熵加权的欧氏距离。对象o与对象p的熵权距离定义如式(4)所示。

其中，fAi(o) 为对象o在属性Ai上的取值，wi(i=1,2,…,d)为属性Ai相应的权值。

2.3 高斯核密度估计

设数据集D={x1,x2,…,xn}，其中n为数据样本大小。为了计算数据对象不同于其自然邻域的偏差程度，首先进行局部密度的估计。由于不确定数据集的分布情况，本文选用无参数的高斯核密度估计（GKDE,Gaussian kernel density estimation）方法[22]来估计数据对象的密度，该方法使用自适应核宽度概念来提高离群点和内部点之间的区分能力和平滑正常样本点（内部点）之间的差异。

使用GKDE 在随机样本x1,x2,…,xn(xi∈Dd)上进行局部密度估计，计算方法如式(5)所示。

其中，K(·)表示核函数；hj表示对应数据对象j自适应得出的核带宽，用于控制密度估计的平滑度。本文选用零均值、单位标准差的多变量d维的高斯核函数，计算方法如式(6)所示。

本文选用的GKDE 方法[22]只通过数据对象的邻域去估计对象xi的局部密度，而不是通过整个数据集去估计。因为如果通过整个数据集去估计，有可能无法检测到局部的离群点。

局部离群点如图1 所示。从图1 可以看出，C2集合的点整体间距、密度和分散情况较一致，可以认为是同一个簇；虽然相较于C2集合的点，C1集合的点较分散，但不难看出，C1集合的点也属于同一个簇。o1、o2相对孤立，可以视作离群点或异常点。如果通过整个数据集去估计对象的密度，全局离群点o1可以较容易地分离出来，但局部离群点o2的密度与C1簇中的点的密度相近，有可能无法检测到局部离群点o2，导致算法的准确率下降。

图1 局部离群点

在基于全局的离群点检测算法中，KNN 算法[9]是较常用的算法，为了验证KNN 算法在此类数据分布中的不足，本文使用KNN 算法在图1 数据集上进行离群得分的计算，结果如表1 所示。KNN 算法中离群得分越大的点越有可能是离群点，而局部离群点o2的离群得分比C1簇的最大离群得分低，因此KNN 算法无法检测出局部离群点o2。

表1 KNN 算法在图1 上的离群得分

此外，通过整个数据集进行密度估计的计算成本较高（O(n2)）。

为了更好地估计数据对象在邻居中的密度，本文使用数据对象xi的 k 最近邻（ρIS(xi)=和反向k 最近邻（RNNk）的并集作为数据对象的邻域。其中数据对象xi的RNNk表示把xi看作自己的k 最近邻的集合，实验表明RNNk可以更好地提供局部分布信息，将其用于检测离群点有较好的效果[23]。

因此，式(5)对于对象xi的密度估计的计算如式(7)所示。

综合式(6)和式(7)，对象xi的密度估计的计算如式(8)所示。

2.4 自适应核带宽

本文选用了高斯核密度估计方法[22]对数据对象进行密度估计，在传统的核密度估计方法里，核带宽都是预先设置好且固定的。但在使用的过程中会发现，在一些高密度区域里，使用过高的核带宽会使密度估计结果过于平滑，影响实验结果；此外，在一些低密度区域里，使用过低的核带宽会导致产生噪声估计。

图2(a)表示在高密度区域设置不同核带宽对数据点密度估计的影响。当设置合适的核带宽时，各个数据点的密度为虚线所对应的曲线，能较准确地表示数据点的密度分布。当设置过高的核带宽时，各个数据点的密度为实线所对应的曲线，过高的核带宽会导致高密度区域的密度分布过于平滑，掩盖了数据大部分的基础结构，从而影响实验结果。

图2(b)表示在低密度区域设置不同核带宽对数据点密度估计的影响。当设置合适的核带宽时，各个数据点的密度为虚线所对应的曲线，能较准确地表示数据点的密度分布。当设置过低的核带宽时，各个数据点的密度为实线所对应的曲线，过低的核带宽会导致低密度区域数据点的密度分布波动较剧烈，会产生大量噪声估计，从而影响实验结果。

图2 核带宽对密度估计影响

因此本文需要为数据对象设置一个相对较优的核带宽，这一般取决于数据对象在数据集中所处的特定位置。为了获取这样的核带宽，本文引入自适应核带宽的概念[22]，目的是提高离群点和内部点的区分能力和平滑正常样本点（内部点）之间的差异。对于数据对象xi，取其KNNk邻域内平均距离，记为davg(xi)，如式(9)所示。

此外，取数据集{davg(xi)|i=1,2,3,…,n}中的最大值和最小值，分别记为dmax和dmin。自适应核带宽hi的计算方法如式(10)所示。

其中，θ(θ＞ 0)是密度估计中用于控制平滑度的参数；δ是一个非常小的正数，是为了防止核带宽取值为0。

3 ERDOF 算法

3.1 相对距离

本文提出了一种相对距离的概念，记为σi。考虑到在低密度区域内局部离群点与内部点的密度相近的问题，因此在计算数据对象的离群程度时，除了考虑数据对象的密度外，增加对数据对象相对距离的计算，进一步刻画数据对象的离群程度，能有效地把局部离群点和内部点、边界点区分开，从而提高算法在低密度区域处理局部离群点的能力。

定义4相对距离。相对距离是指数据对象到相对于密度比它大的数据对象的距离中的最小值。

对于密度最大的数据对象，本文通常给它取一个很小的正数作为该数据对象的相对距离。通常情况下，内部点处于一个密度较相近的区域内，相对距离的取值较小，而离群点常处于稀疏区域，密度比其大的点通常处于相对较远的位置，所以离群点的相对距离的值会比较大。通过该方法得出的相对距离，能够有效地提高ERDOF 算法区分内部点和离群点的能力。

在完成对所有数据对象的密度估计以及相对距离的计算后，为了更好地刻画数据对象的离群程度，本文提出了相对熵权密度离群因子的概念，进一步刻画数据对象的离群程度，进而提出了一种基于相对熵权密度离群因子的离群点检测算法ERDOF 来检测数据集中的离群点。

3.2 相对熵权密度离群因子

定义5相对熵权密度离群因子。相对熵权密度离群因子是由相对距离和核密度的比值所构成的，计算方法如式(12)所示。

该离群因子由相对距离和核密度的比值构成。从密度上看，本文首先通过计算自然邻居自适应获取k值，然后对数据集上的属性进行信息熵的计算，划分离群属性和非离群属性，为离群属性在计算距离时提供更大的权值。运用高斯核密度估计[22]结合自然邻居和熵权距离的概念计算每个数据对象的密度，为了在不同数据分布都能得到较优的密度估计，本文引用了自适应核带宽的概念自适应获取相对较优的核带宽。其中密度相对较高的对象通常处于簇的内部，而密度相对较低的对象则有可能为离群点。同时考虑到在一些低密度区域和边界上的数据对象难以仅凭密度的大小进行判断。因此，本文提出了相对距离的概念，在低密度区域的簇中的内部对象和边界上对象的相对距离会相对较小，而离群点的相对距离通常相对较大，可以有效地提高内部点和离群点的区分能力。本文通过距离和密度的比值的形式构成相对熵权密度离群因子，通常情况下相对熵权密度离群因子较大的点更有可能为离群点，因此算法选取排序后的离群因子中前o个点作为离群点输出，在算法实际应用中，o的取值是根据实际数据集的情况人为设定的。在本文实验中，为了验证算法在各数据集上的有效性，o的取值根据数据集已有的离群点标签个数设定。

算法2ERDOF 离群点检测算法

输入初始数据集D和Ball-Tree

输出数据集D中前o个离群点

3.3 ERDOF 算法正确性

算法2 详细描述了所提算法。其中熵权距离是基于信息熵计算得出的，在多维数据集中，并不是每个属性对检测离群点都是有帮助的，通过给属性分配权重能有效地提高检测精度。生成的扩展局部邻域 ISk(x)是由KNNk(x)和RNNk(x)合并而成的，其中RNNk(x)能有效地提高对于局部离群点的检测精度。基于 ISk(x)对每个数据对象进行密度估计，然后根据密度分别计算每个数据对象的相对距离。最后通过计算相对熵权密度离群因子，对其进行降序排列，输出前o个离群点。

3.4 ERDOF 算法复杂性

ERDOF 算法的时间复杂度主要由以下2 个部分组成：1) 为得到自适应的NV 和自然邻域而构建的Ball-Tree，时间复杂度为O(nlogn)，其中n为数据集的数据对象的个数；2) 计算数据对象的相对熵权密度离群因子ERDOFk(x)，时间复杂度为O(nk)，其中k为NV，因此ERDOF 算法总的时间复杂度为O(nlogn)。

4 实验与分析

为验证本文所提算法ERDOF 在各种复杂数据分布上的性能，本节在人工数据集和真实数据集上进行实验验证。在实验中，将本文算法与常用的6 种离群点检测算法（NaNOD[19]、IForest[24]、LDF[25]、RDOS[26]、NOF[27]、COPOD[28]）进行对比实验。实验环境如表2 所示。

表2 实验环境

4.1 算法有效性检测指标

在离群点检测实验中，大多数的数据集是高度不平衡的，即正常数据大量存在，而异常数据则十分稀有，这使准确率可能不适合作为离群点检测的性能指标。因此，本文使用接收器工作特性（ROC,receiver operating characteristics）曲线下方的面积（AUC,area under curve）作为实验结果的评价指标，AUC 在离群点检测领域是最常见且有效的评价指标。ROC 曲线是真阳性率随假阳性率变化的曲线，其中真阳性率和假阳性率的定义分别如式(13)和式(14)所示。

其中，TP 表示预测为离群点且实际上也是离群点的个数；FP 表示预测为离群点但实际上是正常点的个数；TN 表示预测为正常点且实际上也是正常点的个数；FN 表示预测为正常点但实际上是离群点的个数。

AUC 的取值范围为0～1，一个随机算法会产生一条近似于对角线的曲线（AUC=0.5），AUC 的取值越大，意味着在该算法里离群点的离群得分有更大的概率排在正常点之前[29]，因此AUC 的取值越大，离群点检测算法效果越好。

F1 分数（F1-Score）是统计学中用来衡量二分类模型精确度的一种指标，它同时兼顾了分类模型的准确率和查全率。F1 分数可以看作模型准确率和查全率的一种加权平均，它的取值为0～1。

在参数的选择上，本文选用各算法在相应文献中的默认值进行后续实验。在本文算法中，自适应核带宽的平滑参数θ设置为0.015，为了防止核带宽为0，将极小正数δ设置为10-4；在信息熵权距离中，离群属性的权值l设置为1.5。

为了验证参数θ和参数l取值的有效性，本文选取了人工数据集D2和真实数据集Ionosphere 进行实验。其中人工数据集是二维数据集，数据集特征较相似，故选用样本个数和离群点比例均适中的D2数据集；真实数据集Ionosphere 的离群点占比较大，因此该数据集能更好地检测出参数的变化对实验结果的影响。

图3 是本文算法在人工数据集D2和真实数据集Ionosphere 上采用不同自适应核带宽的平滑参数θ的准确度的实验结果。从图3 可以看出，在人工数据集上，参数θ在0.01～0.06 保持高效稳定；在真实数据集上，当参数θ大于0.03 时准确率大幅度下降，因此选取0.015 作为参数θ在本文算法上的默认取值。

图3 不同参数θ 的准确度的实验结果

图4 是本文算法在人工数据集D2和真实数据集Ionosphere 上采用不同的离群属性的权值参数l的准确度的实验结果。从图4 可以看出，当离群属性的权重大于1 时，在真实数据集上，准确率有了大幅提高，并且在1.4～2.0 保持稳定，而信息熵加权距离主要适用于维度较高的数据集，人工数据集对参数l的设置并不敏感，因此选取1.5 作为参数l在本文算法上的默认取值。

图4 不同参数l 的准确度的实验结果

4.2 人工数据集

为了验证本文算法在各种复杂数据分布下的性能，本文使用图5 所示的6 种二维人工数据集进行实验，其中离群点为“o”代表的点，人工数据集的数据特征如表3 所示。

表3 人工数据集数据特征

图5 数据集D1～D6的数据分布

表4 展示了在6 种人工数据集上各算法的AUC得分结果，加黑字体表示每个数据集中表现最优的算法。在D4中，本文ERDOF 算法的AUC 得分为0.99，在所有对比算法中为最高得分。从表4 中可以看出，本文ERDOF 算法在所有数据集上的AUC得分基本都是最优的，与近年来较热门的算法相比，实验效果突出。虽然本文ERDOF 算法并不在所有数据集上都表现最优，但整体性能远超其他对比算法。因此，该实验证明ERDOF 算法可以适应各种复杂形状的数据分布且有较好的性能表现。

表4 各算法在人工数据集上的AUC 得分

4.3 真实数据集

本文采用的6 种真实数据集均来自UCI 数据集，数据集的维度为4～166，离群点所占比例为4.1%～35.8%，从维度和离群点占比上全面检测ERDOF 算法的真实有效性，其中真实数据集的数据特征如表5 所示。

表5 真实数据集数据特征

图6 是各算法在真实数据集上的离群点检测准确率。为了提高实验结果的可靠性，引入F1 得分的概念对算法效果进行评测，结果如表6 所示。从图6可以看出，ERDOF 算法在各个真实数据集上的准确率均不低于0.8，ERDOF 算法与所有对比算法相比，在真实数据集上的准确率整体上达到最高。ERDOF 算法在真实数据集Wbc 上的准确率和F1值均略低于IForest 算法，但均高于与NaNOD 算法和NOF 算法。通过分析发现，真实数据集Wbc属性列密度分布都较均匀，使各个属性列的信息熵都较接近，进而导致熵权距离效果不佳，但由于本文使用相对距离去刻画密度分布均匀或低密度区域的密度分布，使ERDOF 算法依旧保持较好的检测效果。其中在Wdbc 和Ionosphere 这2 个高维数据集上，ERDOF 算法保持了较高的准确率，其余算法受维度灾难的影响，效果相对较差。ERDOF 算法在Wdbc 数据集上的F1 得分为0.92，在所有对比算法中为最高得分。从表6 中可以看出，ERDOF 算法在各个真实数据集上整体性能远超其他对比算法。实验验证了本文算法能全面准确地检测出离群点。

表6 各算法在真实数据集上的F1 得分

图6 各算法在真实数据集上的离群点检测准确率

各算法在真实数据集上的运行时间如图7 所示。从图7 可以看出，在中低维度的数据集中各算法的运行时间基本持平，而在高维数据集中除了COPOD 和IForest 算法的运行时间保持平稳外，其余算法均大幅度增大。但综合准确率来看，除了ERDOF 算法和LDF 算法在高维数据集上保持了较高的准确率，其余算法的准确率均大幅降低。ERDOF 算法在时间效率上对比其余算法没有太大的优化，但在可接受的时间差范围内，为了提高离群点的检测精度，本文选用检测性能更好的熵权距离和相对距离，因此牺牲了一些时间效率，但准确率有较大提高。

图7 各算法在真实数据集上的运行时间

从图6 和图7 中可以看出，本文算法在维度4～34时，时间效率和准确率都保持较高的水平，而随着维度的增大，准确率依旧保持较高的水平，且时间效率的优势大幅度增加，因此本文算法考虑时间效率和准确率，在可接受的时间差范围内，本文算法可以应对的维度的大致范围在2～100。

5 结束语

本文分析了近年来较新颖的基于密度的离群点检测算法和相关算法思想，针对基于密度的方法存在的问题，提出了相对熵权密度离群因子来刻画数据对象的离群程度，进而提出了一种基于相对熵权密度离群因子的离群点检测算法，其中用熵权距离取代传统的欧氏距离，提高离群属性在计算距离中的权重。本文首先提出相对距离的概念，提高算法在低密度区域处理局部离群点的能力；然后对算法进行了正确性、复杂性的分析；最后在人工数据集和真实数据集上对ERDOF 算法进行实验验证，通过对实验结果的比较分析，验证了ERDOF 算法能有效且全面地检测离群点。