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

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

2.丢弃远离其他簇的小簇
　　一种利用聚类检测离群点的方法是丢弃远离其他簇的小簇。通常，该过程可以简化为丢弃小于某个最小阔值的所有簇。
　　这个方法可以和其他任何聚类技术一起使用，但是需要最小簇大小和小簇与其他簇之间距离的阈值。而且这种方案对簇个数的选择高度敏感，使用这个方案很难将离群点得分附加到对象上。
　　在下图图1中，聚类簇数K=2，可以直观地看出其中一个包含5个对象的小簇远离大部分对象，可以视为离群点。

3.基于原型的聚类
　　另一种比较系统的方法，首先聚类所有对象，然后评估对象属于簇的程度（离群点得分）。在这种方法中，可以用对象到它的簇中心的距离来度量属于簇的程度。特别的，如果删除一个对象导致该目标的明显改进，则可将该对象视为离群点。例如，在K均值算法中，删除远离其相关簇中心的对象能够显著地改进该簇的误差平方和（SSE）。
　　对于基于原型的聚类，评估对象属于簇的程度（离群点得分）主要有两种方法：一是度量对象到簇原型的距离，并用它作为该对象的离群点得分；二是考虑到簇具有不同的密度，可以度量簇到原型的相对距离，相对距离是点到质心的距离与簇中所有点到质心距离的中位数之比。
　　可以注意到，在基于聚类的离群点检测中，对象是否被认为是离群点可能高度依赖于簇的个数（如K很大时的噪声簇）。该问题也没有一个简单的答案，这里提供两种解决思路：一种是改变簇的个数重复检测分析，另一种是聚类得到大量小簇，此时若存在离群点，则它多半真的是一个离群点（但这样的缺点是一组离群点可能形成小簇从而逃避检测）。

4.基于聚类的离群点检测的改进
　　离群点对初始聚类的影响：通过聚类检测离群点时，离群点会影响聚类结果。为了处理该问题，可以使用的方法有：对象聚类、删除离群点、对象再次聚类（这个不能保证产生最优结果）。
　　还有一种更复杂的方法：取一组不能很好地拟合任何簇的特殊对象，这组对象代表潜在的离群点。随着聚类过程的进展，簇在变化。不再强属于任何簇的对象被添加到潜在的离群点集合；测试当前在该集合中的对象，如果它现在强属于一个簇，就可以将它从潜在的离群点集合中移除。聚类过程结束时还留在该集合中的点被分类为离群点（这种方法也不能保证产生最优解，甚至不比前面的简单算法好，在使用相对距离计算离群点得分时，这个问题特别严重）。
　　对象是否被认为是离群点可能依赖于簇的个数（如 K 很大时的噪声簇）。该问题也没有简单的答案。一种策略是对于不同的簇个数重复该分析。另一种方法是找出大量小簇，其想法如下：
　　(1) 较小的簇倾向于更加凝聚；
　　(2) 如果存在大量小簇时，一个对象是离群点，则它多半是一个真正的离群点。 不利的一面是一组离群点可能形成小簇从而逃避检测。 利用前面的数据进行聚类分析，并计算各个样本到各自聚类中心的距离，分析离群样本，得到距离误差图。