基于聚类的离群点检测

小灰灰 2022-08-20 08:13 206阅读 0赞

在利用R软件进行数据挖掘时，离群点检测经常是必不可少的一部分。离群点检测的任务是发现与大部分其它对象显著不同的对象。大部分数据挖掘方法都将这种差异信息视为噪声丢弃，然而在部分情况下，罕见的数据可能蕴含着更大的研究价值。

离群点检测的方法很多，例如：  
基于统计的离群点检测：在已知目标概率分布模型的前提下，计算该对象符合该模型的概率，对于高维数据的检验效果不佳；  
基于邻近度的离群点检测：量化数据集之间的邻近度，把邻近度低的视为离群点，缺点是不适合大数据集，不能处理具有不同区域密度的数据集；  
基于密度：定义一个密度值，一个对象的离群点得分是该对象周围密度的逆，缺点是大数据集不适用，参数选择也十分困难；  
基于聚类：基于聚类技术来发现离群点可能是高度有效的，聚类算法产生的簇的质量对该算法产生的离群点的质量影响非常大；

鉴于数据挖掘中对于高维数据的大数据集的处理需要，以及各个离群点检测方法的优劣。这里我们重点讨论基于聚类的离群点检测。

## 基于聚类的离群点检测 ##

聚类分析用于发现局部强相关的对象组，而异常检测用来发现不与其他对象强相关的对象。因此，聚类分析非常自然的可以用于离群点检测。这里介绍两种基于聚类的离群点检测方法：  
1.丢弃远离其他簇的小簇：  
一种利用聚类检测离群点的方法是丢弃远离其他簇的小簇。通常，该过程可以简化为丢弃小于某个最小阈值的所有簇。  
这个方法可以与任何其它聚类技术一起使用，但是需要最小簇大小和小簇与其他簇之间距离的阈值。而且这种方案对簇个数的选择高度敏感，使用这个方案很难将离群点得分附加到对象上。

2.基于原型的聚类：  
另一种比较系统的方法，首先聚类所有对象，然后评估对象属于簇的程度（离群点得分）。在这种方法中，可以用对象到它的簇中心的距离来度量属于簇的程度。特别的，如果删除一个对象导致该目标的明显改进，则可将该对象视为离群点。例如，在K均值算法中，删除远离其相关簇中心的对象能够显著地改进该簇的误差平方和（SSE）。

对于基于原型的聚类，评估对象属于簇的程度（离群点得分）主要有两种方法：一是度量对象到簇原型的距离，并用它作为该对象的离群点得分；二是考虑到簇具有不同的密度，可以度量簇到原型的相对距离，相对距离是点到质心的距离与簇中所有点到质心距离的中位数之比。

可以注意到，在基于聚类的离群点检测中，对象是否被认为是离群点可能高度依赖于簇的个数（如K很大时的噪声簇）。该问题也没有一个简单的答案，这里提供两种解决思路：一种是改变簇的个数重复检测分析，另一种是聚类得到大量小簇，此时若存在离群点，则它多半真的是一个离群点（但这样的缺点是一组离群点可能形成小簇从而逃避检测）。

下面提供一个示例，利用数据文件consumption\_data.csv（此文件包含940个样本，4个属性）进行聚类分析，并计算各个样本到各自聚类中心的距离，分析离群样本，示例程序如下：

DATA=read.csv("consumption_data.csv")
    DATA1=scale(DATA[2:4])
    set.seed(12)
    km=kmeans(DATA1,center=3)
    #各样本欧式距离
    x1=matrix(km$centers[1,],nrow=940,ncol=3,byrow=T)
    juli1=sqrt(rowSums((DATA1-x1)^2))
    x2=matrix(km$centers[2,],nrow=940,ncol=3,byrow=T)
    juli2=sqrt(rowSums((DATA1-x2)^2))
    x3=matrix(km$centers[3,],nrow=940,ncol=3,byrow=T)
    juli3=sqrt(rowSums((DATA1-x3)^2))
    dist=data.frame(juli1,juli2,juli3)
    #欧氏距离最小值
    y=apply(dist,1,min)
    #记住这种区分点的方式！
    sub=which(y>2.5)
    y1=y[-sub]
    y2=y[sub]
    plot(1:length(y),y,xlim=c(0,length(y)),xlab="样本点",ylab="欧氏距离",col="blue")
    points(which(y>2.5),y2,pch=19,col="red")
    DATA$Id[sub]

运行上面的代码可以得到如图：  
![离群点检测][20160217001531167]  
以及对应的离群点序号：

> DATA$Id[sub]
    [1]  30  39 226 339 484 525 654 670 935

实际应用中可以暂时不设置阈值，先做散点图，观察散点图并针对散点图的具体情况设置阈值，此处设置的阈值为2.5，那么所给的数据中有9个离散点，在聚类以及相关的数据挖掘时，这些数据应该剔除。

上述只是一个比较简单通用的寻找离散点的方法，可适用于高维数据，其它还有许多方法，各有优劣。

[20160217001531167]: /images/20220731/2832464280ce43ffb0de7be424431ab2.png