基于期望核密度离群因子的离群点检测算法①

张忠平 孙光旭 姚春辰 刘 硕 齐文旭

(*燕山大学信息科学与工程学院 秦皇岛 066004)

(**河北省计算机虚拟技术与系统集成重点实验室 秦皇岛 066004)

(***信息工程大学信息系统工程学院 郑州 450001)

离群点是指数据集中偏离大多数数据的少量数据对象,它们与正常数据对象存在明显的差异。离群点检测技术致力于消除噪音和干扰或发现潜在的、有价值的信息[1],是数据挖掘的一个重要研究方向。目前,离群点检测技术已经广泛应用于各大领域中,例如网络入侵检测[2-3]、金融欺诈检测[4-5]、工业损伤检测[6]、垃圾邮件检测[7]、医疗与公共卫生检测[8]等领域。

目前离群点检测大致可分为基于统计的[9-10]、基于距离的[11-12]、基于聚类的[13-14]和基于密度的[15-16]方法。

基于统计的方法采用统计学中的标准分布模型拟合数据,若某个数据点与假设的分布模型偏差较大,则视其为离群点。此类方法不适用于高维数据集,并且当数据集不服从任何标准分布或无法判断分布特征时,离群点检测效率将会大幅降低。

基于距离的方法通过计算数据对象之间的距离远近,将距离更远的数据对象标记为离群点,避免了数据分布假设。然而,此类方法只考虑了全局离群点,没有顾及到局部离群点。对此,Ramaswamy 等人[17]提出了一种基于距离的改进离群点检测算法——k 近邻(k-nearest neighbors,KNN)算法。该算法首先对原始数据聚类,计算簇中样本点的k 近邻距离的上下界,排除距离过小的簇,将剩余数据点中k 近邻距离较大的点标记为离群点。文献[18]针对KNN 算法对近邻参数k值敏感的问题,提出了一种基于自然最近邻的离群点检测算法,通过在不同数据集上自适应获取近邻参数,避免了人为设置。

基于聚类的方法将远离正常簇的离群聚类中的数据点以及不属于任何聚类的数据点视为离群点,此类方法通常会引入新的参数。文献[19]提出了一种基于累积全熵的子空间聚类离群点检测算法(subspace outlier detection based on cumulative holoentropy,SODCH),该算法通过计算子空间的累积全熵值选取最优聚类子空间,提高检测效率。文献[20]提出了一种基于聚类离群因子和相互密度的离群点检测算法,算法根据相互邻居而非k 邻域来计算数据的相互密度,通过构造决策图完成聚类,进而识别出离群点。

基于密度的方法是当下离群点检测领域的研究热点。传统的基于密度的方法大多将密度视作距离的倒数,通过数据对象间的距离来计算局部密度,离群点与位于密集区域的正常对象相比密度更低。局部离群因子(local outlier factor,LOF)算法[21]通过计算每个数据对象的局部离群因子来检测数据集中的离群点,作为迄今为止最为经典的离群点检测算法,仍存在精确率低、参数设置敏感等问题。Huang等人[22]针对LOF 近邻参数k选取困难的问题,提出了无参数的基于自然邻居的离群点检测算法——自然离群因子(natural outlier factor,NOF)算法。该算法合并k 邻域和反k 邻域,自适应获取近邻参数k,通过定义离群因子NOF 检测离群点。Li 等人[23]提出了一种基于密度-距离决策图的离群点检测算法,将传统核密度估计(kernel density estimation,KDE)与局部可达距离相结合检测局部离群点,根据密度提升距离的度量标准检测全局离群点,通过密度比和密度提升距离生成决策图,同时检测出局部、全局和聚类离群点。

通过将核密度估计应用于离群点检测算法中,Wahid 等人[24]提出了一种基于相对核密度的离群点检测(relative kernel-density outlier factor,KDOF)算法。该算法使用核密度估计计算数据对象的局部密度,然后计算密度波动及其近邻点的密度差的平方和,最后通过比较其密度波动与近邻点的平均密度波动来描述数据对象的离群程度。基于此,Wahid 等人[25]又提出了一种基于自然邻居的离群点检测(natural neighbor outlier detection,NaNOD)算法,根据自然邻居自适应获取近邻参数k,并采用加权核密度估计计算数据对象的密度,采用高斯核函数保证数据点之间的平滑度,使用自适应核带宽的思想适应数据点之间的密度差异,进一步区分正常点和离群点。上述2 种算法在很多场景下都具有良好的性能,但存在维度灾难的问题,导致算法运行时间过长,离群点检测效率显著下降。

本文针对基于密度的离群点检测方法在不同分布的数据集上检测精度低的问题,提出一种基于期望核密度离群因子的离群点检测(outlier detection algorithm based on expected kernel density outlier factor,EKDOF)算法。首先,算法将k 近邻和反向k 近邻合并为邻域空间,充分考虑数据对象的局部信息;其次,将核密度估计与多元高斯函数相结合估计数据对象的局部密度,同时根据数据点的k 邻域平均距离自适应地选取核带宽,给出了期望距离的概念,进一步区分局部离群点和低密度区域的正常点;最后,利用期望距离与核密度估计的比值定义期望核密度离群因子来刻画数据对象的离群程度。

1 相关工作

下面简要介绍相互k 近邻数搜索算法。其中,D表示数据集,p、q、o为数据集D中的数据点,dist(p,q)表示点p、q之间的欧式距离,k为正整数。

1.1 扩展邻域空间

定义1k距离dk(p)。dk(p) 是指在给定的k值下,点p到点m之间的欧氏距离。其中,数据点m满足:至少存在k个数据点m′ ∈D{m′},满足d(p,m′) ≤d(p,m)。

定义2数据点xi的k 近邻kNN(xi)[22]。kNN(xi)是指在数据集D={x1,x2,…,xn} 中,到数据点xi的距离不大于数据点xi的k距离的点的集合,定义为式(1)。

定义3数据点xi的反向近RNN(xi)[22]。RNN(xi) 是指在数据集D={x1,x2,…,xn} 中,将数据点xi看作k 最近邻居的数据点xj所构成的点的集合,定义为式(2)。

定义4扩展邻域空间(extended neighborhood space,ENS)ENS(xi)[26]。ENS(xi) 是指数据点xi的k 近邻kNN(xi) 和反向近邻RNN(xi) 的并集所组成的集合,定义为式(3)。

1.2 核密度估计

在数据分布未知的情况下,使用核密度估计可以估计出每个数据对象本身的局部密度,更好地反映出数据点本身与其扩展邻域空间内其他数据点之间的密度差异。

定义5核密度估计(KDE)[27]。KDE 是指通过估计样本集中样本的概率密度函数,得出样本集的总体分布情况,定义为式(4)。

其中,n表示数据集D中数据点的个数;h(xj) 表示在数据点xj上的带宽,也称为平滑函数;d表示数据点的维度;‖xi-xj‖表示数据点xi到数据点xj的欧式距离。K()表示核函数,具有期望值为0、非负性和归一性的特征,满足以下条件:

在传统计算核密度的方法中,通常根据经验值将带宽设置为固定带宽,难以体现出不同数据点之间的局部密度差异。局部密度因子(local density factor,LDF)算法[28],提出一种自适应获取核带宽的方法,以适应在不同数据集下数据点局部密度的差异,定义为式(8)。

其中,dk(xi) 表示数据点xi到第k个近邻点的距离,但该方法仍然需要用户事先指定h的取值。

2 EKDOF 算法

2.1 EKDOF 算法相关定义

定义6自适应核带宽h(xj)。h(xj) 是指在给定近邻参数k值时,2 个数据对象的度量参数乘积的拟合值,定义为式(9)。

其中,mi、mj分别表示数据点xi、xj的度量参数,且数据点xj在数据点xi的扩展邻域空间内,即xj∈ENS(xi)。自适应核带宽能够在估计密度时根据数据对象所处区域疏密程度的不同而发生改变。

定义7度量参数mi。mi是指数据点的k 邻域平均距离,定义为式(10)。

其中,kNN(xi) 表示数据点xi的k 近邻点的集合,|kNN(xi) | 表示数据点xi的k 邻域范围内数据点的个数,d(xi,xl) 表示数据点xi到数据点xl的欧式距离。

定义8多元高斯函数K()。K() 是核密度估计的底层函数,定义为式(11)。

其中,d为数据对象的维度,‖x‖ 表示向量x的模。

定义9核密度估计denENS(xi)。denENS(xi) 是指在xi的扩展邻域空间内,结合多元高斯函数和传统核密度估计得到的密度,定义为式(12)。

其中,| ENS(xi)| 表示数据点xi的扩展邻域空间内数据对象的个数。综合式(9) 和(12),得到denENS(xi) 的最终计算式定义为式(13)。

定义10期望k 距离Ek_dist(expected k-distance)。Ek_dist 是指所有数据点到其各自的第k个近邻点的距离平均值,定义为式(14)。

其中,Nk-th表示第k个近邻点,xi为数据集D中的数据点,n表示数据集D中样本个数。期望k 距离是数据集中的每个数据点到第k个近邻点的期望值,反映了在不同k值下,数据点与近邻点之间的距离偏差。

定义11期望k 距离差(difference of expected k-distance)difEk_dist(xi)。difEk_dist(xi) 指数据点xi到第k近邻的距离与期望k 距离的差,定义为式(15)。

其中,d(xi,Nk-th) 表示数据点xi到第k个近邻点的欧式距离。可以看出,期望k 距离差difEk_dist(xi) 的结果可取到正值、负值或者零。如果数据点到第k个近邻点的距离大于期望k 距离,则difEk_dist(xi) 的值为正,否则为负;如果数据点到第k个近邻点的距离刚好等于期望k 距离,则difEk_dist(xi) 的值等于0。期望k 距离差的正值越大,代表数据点本身与邻居点之间越疏远,该点越有可能是离群点;期望k 距离差的负值结果越小,代表数据点本身与邻居点之间越紧密,该点越有可能是正常点。

图1 展示了一个二维数据集部分数据点的分布情况。O1、O2、O3分别表示点p的3 个近邻点;实线表示数据集中所有数据点到第k个近邻点的平均距离,即期望k 距离,分别用E1_dist、E2_dist 和E3_dist 表示;虚线表示数据点p到第k个近邻点的距离与期望k 距离的差,分别用difE1_dist(p)、difE2_dist(p)、difE3_dist(p) 表示。从图1 可以看出,数据点p到第1个近邻点O1的距离大于E1_dist,因此difE1_dist(p)的值为正;数据点p到第2个近邻点O2的距离小于E2_dist,因此difE2_dist(p) 的值为负;数据点p到第3 个近邻点O3的距离大于E3_dist,因此difE3_dist(p)的值为正。

图1 k=3 时,期望k 距离和期望k 距离差的简单示例

定义12期望距离(expected distance)Edist(xi)。Edist(xi)是指在给定k值下,数据点xi的期望k 距离差的和,定义为式(16)。

其中,s表示近邻参数k的值。位于密集区域的正常点与其邻域范围内的数据点之间的相互距离较小,则期望距离的值也会较小;位于稀疏区域的离群点与其邻域范围内的数据点之间的相互距离较大,则期望距离的值也会较大,从而可以进一步区分离群点和位于低密度区域的正常点。

定义13期望核密度离群因子EKDOF(xi)。EKDOF(xi) 是指数据点xi的期望距离与核密度估计的比值,定义为式(17)。

其中,Edist(xi) 表示数据对象的期望距离,denENS(xi) 表示数据对象的核密度估计,两者的比值表明了数据对象的离群程度。由于离群点常常偏离正常点,从而离群点到其第k个近邻点的距离总是大于期望k 距离Ek_dist,其期望k 距离差difEk_dist(xi) 也会更大且总是取到正值,因此离群点的期望距离Edist(xi) 要远大于正常点,又由于离群点总是位于低密度区域,其核密度denENS(xi) 一般较小。因为期望距离Edist(xi) 更大、核密度denENS(xi) 更小,所以离群因子EKDOF(xi) 的值也会更大,该点是离群点的概率也就越大。

2.2 EKDOF 算法思想

EKDOF 算法思想如下。首先,扩大数据对象的邻域范围,引入反向k 近邻关系,将k 近邻和反向k近邻合并作为数据对象的扩展邻域空间,完善了仅考虑k 邻域范围内数据点分布情况的不足;采用自适应核带宽的思想计算核密度,在带宽函数中引入一种度量参数,根据不同数据点之间度量参数的大小来判断数据点所处区域的密集或稀疏程度。核带宽会随着数据点的变化而变化,而不是一个固定值。当数据点位于密集区域时,数据点之间的k 邻域平均距离小,度量参数的值变小,核带宽也就越小;当数据点位于稀疏区域时,数据点之间的k 邻域平均距离大,度量参数的值变大,核带宽也就随之变大。将高斯核函数应用到核密度估计中,在扩展的邻域空间内计算数据点的局部密度。由于基于密度的方法存在低密度模式的问题,位于低密度区域内的正常点和位于密集区域边界的局部离群点的密度大小较为接近,仅凭密度难以区分,因此本文提出期望距离的概念。位于低密度区域内的数据点的期望距离相对较小,而位于密集区域边界的局部离群点的期望距离相对较大,可以进一步区分正常点和离群点。本文将高斯核密度估计与期望距离相结合构造离群因子,通过比较离群因子值的大小检测离群点。

2.3 EKDOF 算法描述

根据相关定义和算法思想,本节提出了基于期望核密度离群因子的离群点检测算法EKDOF,算法描述如算法1 所示。

首先,将数据点的k 近邻与反向k 近邻合并形成扩展邻域空间,在扩展的邻域空间内,通过将传统核密度估计与多元高斯函数相结合估计每个数据点的密度,同时引入度量参数的概念,根据数据对象的k 邻域平均距离自适应获取数据对象之间的核带宽;其次,根据期望k 距离和期望k 距离差的定义计算每个数据对象的期望距离;最后,用数据对象的期望距离与核密度估计的比值构造离群因子,根据离群因子值进行降序排序,将离群因子值较大的前n个点输出即为离群点。

算法1 中,EKDOF(xi) 中存放的分别是每个数据点xi∈D的期望核密度离群因子的值,算法将EKDOF(xi) 值较大的前n个点输出作为离群点,Soutlier中存放的是算法最终检测到的所有离群点。

2.4 EKDOF 算法分析

2.4.1 正确性分析

在EKDOF 算法中,首先将数据对象的k 近邻和反向k 近邻合并生成扩展邻域空间,充分考虑数据点的邻域信息;将传统核密度估计与多元高斯函数相结合估计数据对象的密度,同时引入自适应核带宽的思想,能够在不同分布的数据集下根据数据对象邻域范围的密集或稀疏程度自动进行调整,平滑了正常点之间的密度差异;通过分析发现,仅凭密度难以辨别出位于低密度区域的正常点和位于密集簇边界区域的局部离群点,因此本算法提出期望距离的概念,能够进一步区分正常点和局部离群点。EKDOF 算法采用数据对象的期望距离与核密度估计的比值构造离群因子,离群因子值越大,该点是离群点的可能性就越大。以上分析说明了所提出的基于期望核密度离群因子的离群点检测算法在原理上是正确的。

2.4.2 时间复杂度分析

EKDOF 算法的时间复杂度主要分为2 部分:(1)在构造扩展邻域空间的过程中,需要计算每个数据点的k 近邻和反向k 近邻,时间复杂度为O(n·logn),其中n表示数据集中数据点的个数;(2)计算数据对象的期望核密度离群因子EKDOF(xi),时间复杂度为O(n)。综合上述分析,所提算法的时间复杂度为O(n·logn)+O(n) 两部分之和,进而得出EKDOF 算法最终的时间复杂度为O(n·logn)。

3 实验与分析

3.1 实验环境配置

表1 给出了验证本文算法性能所采用的实验环境,主要包括软硬件环境以及各配置所对应的参数。

表1 实验环境

3.2 实验评价指标

本文采用的实验评价指标为精确率Pr、AUC(area under curve)值和离群点发现曲线。

精确率Pr是指算法实际检测到的离群点数量与离群点总数之比,定义为式(18)。

其中,FP表示算法把数据集中的正常点当作离群点进行输出的数量,TP表示算法最终检测到的真实离群点的个数。精确率Pr的取值在0～1 之间,Pr的值越接近于1,代表算法检测出的真实离群点的数量越多,算法的性能就越好。

AUC 值是一个介于0 和1 之间的数,AUC 的值越接近于1,代表算法越接近于离群点检测的最佳水平,能把更多的离群点排在正常点之前进行输出,算法的性能就越好。

离群点发现曲线[29]反映的是算法实际检测到的离群点个数随用户查询个数的变化趋势。离群点发现曲线的横坐标是用户想要查询的离群点的个数,纵坐标是算法真正检测到的离群点的个数。离群点发现曲线的斜率越接近于1,代表算法越能满足用户的查询需求,算法的性能就越好。

3.3 人工数据集实验与分析

本文使用图2 所示的二维人工数据集DS5～DS8进行对比实验,其中“ ×”代表离群点,其余点代表正常点。DS5～DS8 的数据特征如表2 所示。

表2 人工数据集的数据特征

图2 EKDOF 算法人工数据集的数据分布图

结合图2 和表2 可以看出,本算法选取的人工数据集的数据分布复杂程度不同,既包括离群点和正常点分布较为明显的数据集,也包括离群点交错地分布在正常点所构成的聚类簇的周围或边界区域的数据集。因此,在这些数据集上进行实验可以有效地验证EKDOF 算法的性能,同时有助于与其他对比算法作出区分。

表3 和图3 展示了在4 个人工数据集下,EKDOF算法和其他4 种对比算法在精确率上的实验结果。

表3 不同算法在人工数据集上的精确率

图3 不同算法在人工数据集上的精确率对比

结合表3 和图3 可以看出,EKDOF 算法在人工数据集上的精确率均为最优,且在DS8 数据集上,EKDOF 算法的精确率为0.97,在所有人工数据集中达到了最高。在所有数据集中EKDOF 算法的精确率均高于同样使用了核密度估计方法的LOLED 算法和LDF 算法,特别是在DS5 数据集上EKDOF 算法的精确率为0.95,而LOLED 算法的精确率为0.79。这是因为EKDOF 算法同时将k 邻域和反向k 邻域作为邻域空间,更加全面地考虑数据对象的局部信息,使用期望距离能够进一步区分离群点和位于低密度区域的正常点,因此提高了本文算法的检测精度。在DS6 数据集上,每种算法的精确率均有所下降,EKDOF 算法的精确率为0.88,仍高于对比算法。在4 个人工数据集上,EKDOF 算法的精确率均优于同样使用了扩展邻域空间的INFLO 算法和NOF算法,特别是在DS7 数据集上,EKDOF 算法的精确率为0.91,高于NOF 算法0.54。综上所述,EKDOF 算法在所有数据集上的精确率都是最高的,从而验证了本文所提出的基于期望核密度离群因子的离群点算法在精确率上的有效性。

表4 和图4 展示了4 个人工数据集上,EKDOF算法和其他4 种对比算法在AUC 值上的实验结果。

表4 不同算法在人工数据集上的AUC 值

图4 不同算法在人工数据集上的AUC 值对比

结合表4 和图4 可以看出,EKDOF 算法在人工数据集上的AUC 值均为最优,其中在DS7 和DS8数据集上,其AUC 值均达到了1.00。在DS5 和DS6数据集上,EKDOF 算法的AUC 值均为0.97,除NOF算法在DS6 数据集上的AUC 值为0.75 之外,其他算法在这2 个数据集上的AUC 值均保持在0.80 以上。在DS7 数据集上,LOLED 算法、LDF 算法和NOF 算法的AUC 值均有所下降,其中NOF 算法的AUC 值仅为0.30,这是因为DS7 数据集分布较为复杂,通过密度难以区分出局部离群点和低密度区域的正常点,难以检测出更多的离群点,因此造成算法AUC 值减小。综上,EKDOF 算法在4 个人工数据集上的AUC 值都是最高的,证明本文提出的基于期望核密度离群因子的离群点检测算法在AUC 值上的有效性。

图5 展示了4 个人工数据集上,EKDOF 算法和4 种对比算法的离群点发现曲线的实验结果。

图5 不同算法在人工数据集上的离群点发现曲线对比

观察图5(a)～(d)的曲线变化趋势可以看出,当查询条件相同时,EKDOF 算法能够查询到更多的离群点反馈给用户,表明EKDOF 算法相比于其他算法具有更优秀的检测能力。NOF 算法在DS8 数据集上的表现和其他算法较为相似,但在DS6 和DS7数据集上的检测效果与其他算法相比相差较多。在DS8 数据集上,EKDOF 算法的离群点发现曲线的斜率最接近于1,当用户的查询数量从5 依次递增至40 时,EKDOF 算法查询到的离群点个数与用户设置的查询个数始终相等,说明EKDOF 算法检测到的前40 个数据点都是离群点。综上所述,EKDOF算法的离群点发现曲线在4 个人工数据集上的表现都是最优的,从而验证了本文所提出的EKDOF 算法在离群点检测方面的良好性能。

3.4 真实数据集实验与分析

4 个真实数据集的数据特征如表5 所示,它们均来自于UCI 真实数据集[30]。由表5 可知,EKDOF算法所选取的真实数据集的样本数量从129～1 641,数据维度从7～17,离群点数量从10～25,离群点占比从1.2%～14.8%。由此可知,本算法选取的真实数据集的数据分布较为复杂,有包含几百个数据点的小规模数据集,也有包含上千个数据点的大规模数据集。因此,在这些数据集上进行实验可以有效地对比各离群点检测算法的性能。

表5 真实数据集的数据特征

表6 和图6 展示了在4 个真实数据集下,EKDOF 算法和其他4 种对比算法在精确率上的实验结果。

表6 不同算法在真实数据集上的精确率

图6 不同算法在真实数据集上的精确率对比

结合表6 和图6 可以看出,除了在Ecoli 数据集上本文算法和INFLO 算法的精确率相等以外,在其他3 个数据EKDOF 算法的精确率都要比另外几种算法好,特别是在PenDigits 数据集上达到了0.95。INFLO 算法在对比算法中的表现相对较好,而另外3 种对比算法的精确率表现较差且波动幅度较大。NOF 算法的稳定性最差,虽然在Ecoli 数据集上有0.48 的检测精度,但在WBC 数据集上根本没有检测出离群点,而本文算法的精确率仍然可以达到0.90。综上所述,EKDOF 算法在每个真实数据集上都能检测出更多的离群点且稳定性也是最好的,从而验证了本文所提出基于期望核密度离群因子的离群点检测算法在精确率上的有效性。

表7 和图7 展示了在4 个真实数据集下,EKDOF 算法和其他4 种对比算法在AUC 值上的实验结果。

表7 不同算法在真实数据集上的AUC 值

图7 不同算法在真实数据集上的AUC 值对比

结合表7 和图7 可以看出,EKDOF 算法在每个真实数据集上的AUC 值都有着不错的实验结果,在PenDigits、Ecoli 和WBC 这3 个数据集上,EKDOF算法的AUC 值均为1.00,说明EKDOF 算法能把检测出来的所有离群点排在正常点之前进行输出。在PenDigits 数据集上,EKDOF 算法和INFLO 算法的AUC 值相同。NOF 算法在所有真实数据集上的AUC 值和稳定性表现仍是最差的,由于NOF 算法在WBC 数据集上未检测出离群点,其AUC 值为0.00。INFLO 算法的稳定性也一般,在WBC 数据集上的AUC 值仅有0.41,但在PenDigits 数据集上的AUC值能达到1.00。LDF 算法在4 个对比算法中的表现最为平稳,其AUC 值一直保持在0.75 以上。综合上述的分析,EKDOF 算法在每个真实数据集上的AUC 值都是最高的,从而验证了本文所提出的基于期望核密度离群因子的离群点检测算法在AUC 值上的有效性。

图8 展示了4 个真实数据集下,EKDOF 算法和4 种对比算法离群点发现曲线的实验结果。

观察图8(a)～(d),当用户的查询数量逐渐增加时,从各算法对应的离群点发现曲线的变化趋势可以得出,在WBC 数据集和wine 数据集上,EKDOF算法离群点发现曲线的线性上升的速度与其他算法相比优势更加明显,突出了EKDOF 算法在动态变化的查询条件下更能满足用户的期望。在Ecoli 数据集上,除NOF 算法整体表现较差外,本文算法和另外几种算法具有类似的性能,但整体上仍然优于其余对比算法。在PenDigits 数据集上,本文所提出的EKDOF 算法和INFLO 算法的离群点发现曲线基本重合,但整体上本文算法离群点发现曲线的斜率更接近于1,最终本文算法比INFLO 算法多检测出1 个离群点。LOLED 算法和LDF 算法在Ecoli 数据集上的表现都较为良好,但在其他3 个数据集上的表现却差强人意。综合上述的分析,EKDOF 算法的离群点发现曲线在每个真实数据集上的表现都是最优的,从而验证了本文所提出的基于期望核密度离群因子的离群点检测算法具有良好的检测精度和稳定性。

4 结论

本文分析了近年来较新颖的基于密度的离群点检测算法和相关思想,针对基于密度的方法存在的问题进行了深入研究,提出了一种基于期望核密度离群因子的离群点检测算法。使用k 近邻和反向k近邻扩展邻域空间代替传统的k 邻域空间,充分考虑数据点邻域范围内的数据分布;将传统核密度估计的方法与多元高斯函数相结合,引入自适应核带宽的思想,避免了人为设定核带宽,更好地适应不同数据集的数据分布。本文提出了期望距离,并定义了期望核密度离群因子刻画数据对象离群程度,从而检测出离群点。对所提算法的正确性和复杂性进行分析,在人工数据集和真实数据集上的实验证明,EKDOF 算法具有良好的检测精度和稳定性,能够在各种分布的数据集上表现出优越的性能。