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

基于聚类的方法主要目的是产生聚类簇

离群点的发现

往往是作为聚类分析的副产品而被发现的

基于聚类的方法有以下两个特点

①先采用特殊的聚类算法处理输入数据

而得到聚类

再在聚类的基础上来检测离群点

②只需要扫描数据集若干次

效率较高

适用于大规模数据集

基于聚类的离群点检测方法共分两个阶段

第一阶段对数据进行聚类

第二阶段计算对象或簇的离群因子

将离群因子大的对象

或稀疏簇中的对象判定为离群点

即首先聚类所有对象

然后评估对象属于簇的程度

如果一个对象不强属于任何簇

则称该对象为基于聚类的离群点

基于对象离群因子法

对于基于原型的聚类

可以用对象到它的簇中心的距离

来度量对象属于簇的程度

假设数据集D被聚类算法划分为k个簇

C={C1C2…Ck}

对象p的离群因子OF1(p)

定义为p

与所有簇间距离的加权平均值

如下所示

其中d(pC_j)

表示对象p与第j个簇Cj之间的距离

两阶段离群点挖掘方法如下

①对数据集D采用聚类算法进行聚类

得到聚类结果C={Cˇ1Cˇ2…Cˇk}

②计算数据集D中

所有对象p的离群因子OF1(p)

及其平均值

Ave_OF

和标准差Dev_OF

满足条件

OF1(p)≥Ave_OF+"β"*"Dev_OF

(1≤β≤2)" 的对象判定为离群点

通常取"β=1" 或1.285

例2基于对象的离群因子法

对于如图所示的二维数据集

比较点pˇ1坐标为6,8

pˇ2坐标为5,2

哪个更有可能成为离群点

假设数据集经过聚类后

得到聚类结果为

C={Cˇ1Cˇ2Cˇ3}

图中红色圆圈标注

三个簇的质心分别为

Cˇ1坐标为5.5,7.5

Cˇ2坐标为5,2

Cˇ3坐标为1.75,2.25

试计算所有对象的离群因子

解

根据对象p的离群因子OF1(p)的定义

对于pˇ1点有

对于pˇ2有

可见点pˇ1较pˇ2更可能成为离群点

同理可求得所有对象的离群因子

结果如表所示

进一步求得所有点的离群因子平均值

Ave_OF=2.95

标准差Dev_OF=1.3

假设β=1

则阈值E=Ave_OF+β*Dev_OF

=2.95+1.3=4.25

离群因子大于4.25的对象可视为离群点

pˇ1的离群银子大于4.25

pˇ1可视为离群点

基于簇的离群因子法

假设数据集D

被聚类算法划分为k个簇

C={Cˇ1Cˇ2…Cˇk}

簇Cˇi离群因子OF2(Cˇi)

定义为簇Cˇi

与其他所有簇间距离的加权平均值

如果一个簇离几个大簇的距离都比较远

则表明该簇偏离整体比较远

其离群因子也较大

OF2(Cˇi)度量了

簇Cˇi偏离整个数据集的程度

其值越大

说明Cˇi偏离整体越远

基于簇的离群因子离群点检测算法

描述如下

①聚类

对数据集D进行聚类

得到聚类结果C={Cˇ1Cˇ2…Cˇk}

②确定离群簇

计算每个簇Cˇi

(1≤i≤k)的离群因子OF2(Cˇi)

按OF2(Cˇi)递减的顺序重新排列Cˇi

(1≤i≤k)

求满足

将簇Cˇ1Cˇ2…Cˇb标识为

“outlier”类

即每个对象均看成离群

而将Cˇb+1Cˇb+2…Cˇk标识为

“normal”类

即其中每个对象均看成正常的

例3

基于簇的离群因子法

仍以上例为例

对于如图所示的二维数据集

聚类后得到三个簇

C={Cˇ1Cˇ2Cˇ3}

簇心分别为

Cˇ1坐标为5.5,7.5

Cˇ2坐标为5,2

Cˇ3坐标为1.75,2.25

按照欧氏距离计算簇之间的距离

分别为

d(Cˇ1Cˇ2)=

√((5.5-5)^2+(7.5-2)^2 )=5.52

d(Cˇ1Cˇ3)=

√((5.5-1.75)^2+(7.5-2.25)^2 )=6.45

d(Cˇ2Cˇ3)=

√((5-1.75)^2+(2-2.25)^ 2)=3.26

进一步计算三个簇的离群因子

具体如下

OF2(Cˇ1)=

1/11*d(Cˇ1Cˇ2)+8/11*d(Cˇ1Cˇ3)

计算结果为5.19

OF2(Cˇ2)=2/11*d(Cˇ2Cˇ1)+8/11

*d(Cˇ2Cˇ3)

计算结果为3.37

OF2(Cˇ3)=2/11*d(Cˇ3Cˇ1)+1/11

*d(Cˇ3Cˇ2)

计算结果为1.47

可见簇Cˇ1的离群因子最大

其中包含的对象判定为离群点

与例2得到的结论相同

基于聚类的离群点检测方法

具如下优点

首先

它们可以检测离群点

而不要求数据是有标号的

即它们以无监督方式检测

它们对许多类型的数据都有效

簇可以看做数据的概括

一旦得到簇

基于聚类的方法

只需要把对象与簇进行比较

以确定该对象是否是离群点

这一过程通常很快

因为与对象总数相比

簇的个数通常很小

基于聚类的方法的缺点是

它的有效性高度

依赖于所使用的聚类方法

这些方法对于离群点检测而言

可能不是最优的

对于大型数据集

聚类方法通常开销很大

这可能成为一个瓶颈

使用基于分类检测离群点的时候

分类器可以使用前面介绍的

常用的分类器

如SVM

KNN 决策树等

构造分类器时

训练数据的分布可能极不均衡

简单来说

就是正常的数据可能会非常多

离群点的数据可能会非常少

这会造成在构建分类器的时候

精度受到很大的影响

为解决正常数据

和离群点数据分布的不均衡

可以使用一类模型进行分类

简单来说

就是构建一个描述正常数据的分离器

不属于正常的数据就是离群点

例4使用SVM检测离群点

在图中

三个圆圈内的样本是正常数据

圆圈外的数据是离群点

可以使用圆圈内的正常数据

训练一个决策边界

通过这个边界

就可以区分数据是正常数据

还是非正常数据

即离群点

即

如果给定的新对象

在正常类的决策边界内

则被视为正常的

如果新对象在边界外

则被视为离群点

这样就不需要训练离群点数据模型

避免了由于数据分布不均衡

造成的分类器准确率低的现象

使用分类模型进行离群点检测

具有如下优势

可以检测所有的离群点

只要在决策边界外

即可认为是离群点

数据和正常数据的距离变得不重要了

避免了提取离群点数据的

繁重的工作

避免了由于正常数据和离群点分布不均衡

造成的分类器效果不好的现象的出现

使用基于分类的方法

进行离群点的识别

在实际应用中

用的并不是很多

这是因为

这种方式受训练数据的影响非常大

而在实际应用中

训练数据的质量并不能得到很好的保证