数据挖掘中的异常检测

Question

关于异常值检测,我有几组问题:

1. 我们可以使用k-means找到异常值,这是一个好方法吗？

2. 是否有任何聚类算法不接受用户的任何输入？

3. 我们可以使用支持向量机或任何其他监督学习算法进行异常值检测吗？

4. 每种方法的优缺点是什么？

Answer 1

我将自己局限于我认为对于提出所有问题的线索至关重要的内容,因为这是许多教科书的主题,它们可能在不同的问题中得到更好的解决.

1. 我不会使用k-means来识别多变量数据集中的异常值,原因很简单,k-means算法不是为此目的而构建的:你总是会得到一个最小化集群内总和的解决方案.正方形(因此最大化群集间SS,因为总方差是固定的),并且异常值不一定定义它们自己的群集.考虑R中的以下示例:

   set.seed(123)
   sim.xy <- function(n, mean, sd) cbind(rnorm(n, mean[1], sd[1]),
                                         rnorm(n, mean[2],sd[2]))
   # generate three clouds of points, well separated in the 2D plane
   xy <- rbind(sim.xy(100, c(0,0), c(.2,.2)),
               sim.xy(100, c(2.5,0), c(.4,.2)),
               sim.xy(100, c(1.25,.5), c(.3,.2)))
   xy[1,] <- c(0,2)     # convert 1st obs. to an outlying value
   km3 <- kmeans(xy, 3) # ask for three clusters
   km4 <- kmeans(xy, 4) # ask for four clusters
   

   从下图中可以看出,外围值永远不会如此恢复:它将始终属于其他集群之一.

   

   然而,一种可能性是使用两阶段方法,其中一个人以迭代的方式去除极值点(这里定义为远离其群集质心的向量),如下文所述:通过异常值去除来改善K均值(Hautamäki等人).

   这与遗传研究中用于检测和去除表现出基因分型错误的个体,或者是兄弟/双胞胎的个体(或者当我们想要识别群体亚结构时)的情况有些相似,而我们只想保持不相关的个​​体; 在这种情况下,我们使用多维缩放(相当于PCA,前两个轴的常数),并在前10或20轴中的任何一个上移除高于或低于6 SD的观测值(例如,参见人口结构和特征分析,Patterson等,PLoS Genetics 2006 2(12)).

   一种常见的替代方法是使用有序的稳健马哈拉诺比斯距离,可以根据预期的卡方分布分数绘制(在QQ图中),如下文所述:

   RG Garrett(1989).卡方图:多变量异常值识别的工具.地球化学勘探杂志 32(1/3):319-341.

   (它可以在mvoutlier R包中找到.)

2. 这取决于你所谓的用户输入.我将您的问题解释为某些算法是否可以自动处理距离矩阵或原始数据并停止在最佳数量的聚类上.如果是这种情况,并且对于任何基于距离的分区算法,则可以使用任何可用的有效性指数进行聚类分析; 给出了一个很好的概述

   Handl,J.,Knowles,J.,and Kell,DB(2005).后基因组数据分析中的计算群集验证. Bioinformatics 21(15):3201-3212.

   我在Cross Validated上讨论过.例如,您可以在数据的不同随机样本(使用引导程序)上运行算法的多个实例,用于一系列簇编号(例如,k = 1到20),并根据优化的标准选择k(taht)轮廓宽度,共生相关性等); 它可以完全自动化,无需用户输入.

   存在其他形式的聚类,基于密度(聚类被视为对象异常常见的区域)或分布(聚类是遵循给定概率分布的对象集).例如,在Mclust中实现的基于模型的聚类允许通过跨越不同数量的聚类的方差 - 协方差矩阵的形状范围来识别多变量数据集中的聚类,并根据该聚类选择最佳模型.BIC标准.

3. 这是分类中的一个热门话题,一些研究侧重于SVM来检测异常值,特别是当它们被错误分类时.一个简单的谷歌查询将返回大量的点击,例如Thongkam等人在乳腺癌生存能力预测中用于异常值检测的支持向量机.(计算机科学讲义 2008 4977/2008 99-109;本文包括与集合方法的比较).最基本的想法是使用一类SVM通过拟合多变量(例如,高斯)分布来捕获数据的主要结构; 边界上或边界外的物体可能被视为潜在的异常值.(从某种意义上说,基于密度的聚类在预测分布的情况下,定义异常值的确更为直接.)

   用于无监督,半监督或监督学习的其他方法在Google上很容易找到,例如

   • Hodge,VJ和Austin,J.对异常值检测方法的调查.
   • Vinueza,A.和Grudic,GZ 无监督离群检测和半监督学习.
   • Escalante,HJ 机器学习异常值检测算法的比较.

   
   一个相关的主题是异常检测,你会发现很多论文.

4. 这真的值得一个新的(可能更集中的)问题:-)