9.2 离群点检测（一）在线视频

离群点的检测方法有很多

每种方法在检测时

都会对正常数据对象

或离群点做出假设

从这个假设的角度考虑

离群点检测方法可以分为

基于统计学的离群点检测

基于近邻的离群点检测

基于聚类的离群点检测

以及基于分类的离群点检测

此图给出了基于统计分布的检测流程

基于统计的方法是研究最多的

早期的许多关于离群点挖掘

都是利用统计学的方法

它是针对小概率的事件进行分析鉴别

其主要思想是

利用在海量数据集中

多数的数据服从一定的模型分布

然后通过不一致检测

分离出那些严重偏离分布曲线的记录

作为离群点

这类离群挖掘方法多数是从

针对不同分布的离群检测方法发展起来的

该方法为数据集构建一个概率统计模型

例如正态 泊松 二项式分布等

其中的参数由数据求得

然后根据模型采用不和谐检验识别离群点

不和谐检验过程中

需要样本空间数据集的参数知识

例如

假设的数据分布

分布的参数知识

例如期望和方差

以及期望的离群点数目

不和谐检验需要检查两个假设

工作假设和备择假设

工作假设指的是

如果某样本点的某个统计量

相对于数据分布

其显著性概率充分小

则认为该样本点是不和谐的

工作假设被拒绝

此时备择假设被采用

即该样本点来自于另一个分布模型

如果某个样本点不符合工作假设

那么认为它是离群点

如果它符合备择假设

则认为它是

符合某一备择假设分布的离群点

工作假设H为

假设n个对象的整个数据集

来自一个初始的分布模型F

即

H为oˇ∈F

其中i=12…n

不和谐检验就是检查对象oˇi

关于分布F是否显著得大或小

具有期望值μ

方差σ＾2的正态分布N（μ,σ＾2）

曲线具有以下特点

正态分布曲线N（μ,σ＾2）

变量值落在

（μ-σ,μ+σ）区间的概率是68.27%

变量值落在

（μ-2σ,μ+2σ）区间的概率是95.44%

变量值落在

（μ-3σ,μ+3σ）区间的概率是99.73%

如图所示

也就是落在

（μ-3σ,μ+3σ）区间以外的概率是0.27%

因此

一种简单的离群点检测法是

如果某数据对象的值

落在（μ-3σ,μ+3σ）区间以外

它就是离群点

一般的

设属性X取自具有期望值μ

方差σ＾2的正态分布

N（μ,σ＾2）

如果属性X满足

P(|X|≥C)=α

其中C是一个选定的常量

则X以概率1-α为离群点

例1

基于统计方法检测年龄离群点

设儿童上学的具体年龄总体服从正态分布

所给的数据集

是某地区随机选取的

开始上学的20名儿童的年龄

具体的年龄特征如下

相应的统计参数是

均值m=9.1

标准差σ=2.3

如果选择数据分布的阈值q

按如下公式计算

q=m±2σ

则阈值下限与上限分别为

4.5和13.7

如果将工作假设描述为

儿童上学的年龄分布

在阈值设定区间内

则依据不和谐检验

不符合工作假设的

即

在[4.5,13.7]区间以外的年龄数据

都是潜在的离群点

将最大值取整为13

所以年龄为14的孩子可能是个例外

而且由均值可知

此地的孩子普遍上学比较晚

基于统计学的离群点检测方法

建立在非常标准的统计学原理之上

易于理解

实现起来也比较方便

当数据充分或分布已知时

检验十分有效

但是存在如下不足

①多数情况下

数据的分布是未知的

或数据几乎不可能用标准的分布来拟合

虽然可以使用混合分布对数据建模

基于这种模型开发功能更强的

离群挖掘方法

但这种模型更复杂

难以理解和使用

②当观察到的分布

不能适当地用任何标准的分布建模时

基于统计方法的挖掘

不能确保所有的离群点被发现

而且要确定哪种分布

最好的拟合数据集的代价也非常大

③即使这类方法在低维

如一维或二维时的数据分布己知

但在高维情况下

估计数据对象的分布是极其困难的

对每个点进行分布测试

需要花费更大的代价

综上所述

基于统计学的离群点检测方法

主要通过令当前的数据集

含有某种概率分布规则

并且通过某种数据集构建

其特定分布规律

再利用分布模型的不和谐检验特性

来检测离群点

当没有特定的检验时

或观察到的分布

不能恰当地被任何标准的分布来模拟时

基于统计学的检测方法

就不能确保所有的离群点被发现

基于统计学的检测方法只适用于低维数据

不能很好解决多维数据集

和未知的数据集的分布规律

在样本空间中

可以使用对象之间的距离

或对象所属领域的密度

来量化对象之间的近邻性

给出近邻性方法的假设

离群点对象与它最近邻的邻近性

显著偏离数据集中

其它对象与它们近邻之间的邻近性

基于距离的离群点检测

与基于密度的离群点检测

都是近邻性方法

在基于距离的离群点检测方法中

离群点就是远离大部分对象的点

即与数据集中的大多数对象的距离

都大于某个阈值的点

基于距离的检测方法

考虑的是对象给定半径的邻域

如果在某个对象的领域内

没有足够的其它的点

则称此对象为离群点

基于距离的离群点算法有

嵌套-循环算法

基于索引的算法

和基于单元的算法

下面主要介绍嵌套-循环算法

对于对象集D

指定一个距离阈值r

来定义对象的合理邻域

设对象(d,d’)属于D

考察d的r-邻域中的其它对象的个数

如果D中大多数对象远离d

则视d为一个离群点

设 r(r>0)是距离阈值

α大于等于0

小于等于1

为分数阈值

如果对象d满足

如下公式

那么d

就是一个

DB（r,α）的离群点

对于集合元素d'

其中 dist(d,d')是距离度量

同样

可以通过检查d

与它第k个最近邻dk之间的距离

来确定对象是否为DB（r,α）离群点

其中k=α*‖D‖向下取整

如果dist(d,dˇk)>r

则对象d是离群点

因为

此时在d的r-邻域内

除了d之外对象少于k个

嵌套-循环是一种简单的

计算DB（r,α）离群点的方法

通过检查每个对象的r-邻域

对每个对象 dˇi(1≤i≤=n)

计算其与其他对象之间的距离

并统计r-邻域内的对象的个数

如果找到α*n个对象

则停止此对象的计算

进行下一个对象的计算

因为在此对象的r-邻域内的对象

不少于α*n个

所以它不是离群点

否则其是离群点

嵌套-循环算法计算复杂度为O(n＾2)

即平方阶

它把内存的缓冲空间

分为两半

把数据集合分为若干个逻辑块

通过选择逻辑块

装入每个缓冲区域的顺序

避免了索引结构的构建

提高了效率

基于距离的方法

不需要用户拥有任何领域的知识

在概念上更加直观

基于密度的离群点检测方法

基于密度的离群点检测方法

考虑的是

对象与它近邻的密度

如果一个对象的密度

相对于它的近邻低的多

则视此对象为离群点

基于密度的离群点检测算法

效果正在不断地改进

逐渐突破密度差异大等条件的限制

并平衡不同密度聚类簇

对数据点离群度的影响

其最基础的算法

是基于局部离群因子的离群点检测算法

局部离群因子

是在一个实际检测问题的基础上提出的

在如图所示的数据集中

聚类簇Cˇ1

属于低密度区域

聚类簇Cˇ2

属于高密度区域

依据传统的基于密度的离群点检测算法

只能检测出数据点pˇ1

是离群点

而Cˇ1中任何一个数据点

与其近邻的距离

大于数据点pˇ2

与其在Cˇ2中的近邻的距离

数据点pˇ2

会被看作是正常点

因此

提出了基于近邻密度差异的

离群点检测算法

该算法考虑利用数据局部知识

而非全局知识

对于任何给定的数据点

LOF算法计算的离群度

等于数据点p的k近邻集合的

平均局部数据密度

与数据点自身局部数据密度的比值

为了计算数据点的局部数据密度

首先确定数据点包含k个近邻的

最小超球的半径r

然后利用超球的体积

除以近邻数k

得到数据点的局部数据密度

正常数据点位于高密度区域

它的局部数据密度

与其近邻非常相近

离群度接近1

而离群数据

位于相对低密度区域

它的局部数据密度

比其近邻平均局部数据密度要小

离群度大于1

那么

离群度越高越大于1

就表示数据点p的局部数据密度

相比其近邻平均局部数据密度越小

p越极有可能是离群点

如图所示的数据集中

因为LOF算法通过利用局部数据信息

考虑了Cˇ1和Cˇ2数据密度的差异性

就能比较好地检测出离群数据点pˇ1和pˇ2

数据集中的数据点x和xˇi

x到xˇi的可达距离

reach_distˇk(x,xˇi)

=max{distˇ k(xˇi)dist(x,xˇi)}

其中

distˇk(xˇi)

指数据点xˇi到其第k个近邻的距离

dist(x,xˇi)指数据点x和xˇi的距离

通常距离度量选用欧式距离

而且x到xˇi的可达距离

reach_distˇk(x,xˇi)

与xˇi到x的可达距离

reach_distˇk(xˇi,x)

一般并不相同

已知可达距离的定义

计算数据点x的局部可达密度

可以利用其到

自身k近邻集合的平均可达距离

作为依据

将该平均距离求倒数

作为局部可达密度的定量表示

这符合基于密度的

离群点的假设

数据点x的局部可达密度

lrdˇk(x)定义为

其中KNN(x)指数据点x的k近邻的集合

最后

通过数据点x的k近邻可达数据密度

与x的可达数据密度比值的平均值

作为数据点x的局部离群因子

即LOFˇ(x)=

LOF算法计算的离群度

不在一个通常便于理解的范围

[0,1]之间

而是一个大于1的数

并且没有固定的范围

而且数据集通常数量比较大

内部结构复杂

LOF极有可能因为取到的近邻点

属于不同数据密度的聚类簇

使得计算数据点的

近邻平均数据密度产生偏差

而得出与实际差别较大

甚至相反的结果

通过基于密度的局部离群点检测

就能在样本空间数据分布不均匀的情况下

也可以准确发现离群点