12

我有几组关于异常值检测的问题：

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

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

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

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

4

4 回答 4

38

我将把自己限制在我认为对你所有问题提供一些线索的必要性上，因为这是很多教科书的主题，它们可能在单独的问题中得到更好的解决。

  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-Means（Hautamäki 等人）。

    这与基因研究中检测和移除表现出基因分型错误的个体或兄弟姐妹/双胞胎个体（或当我们想要识别种群亚结构时）所做的工作有一些相似之处，而我们只想保留无关的个体；在这种情况下，我们使用多维缩放（相当于 PCA，前两个轴为常数）并在前 10 或 20 个轴中的任何一个轴上删除高于或低于 6 SD 的观察值（例如，参见Population结构和特征分析，Patterson 等人，PLoS 遗传学2006 2(12))。

    一种常见的替代方法是使用有序的稳健马氏距离，该距离可以（在 QQ 图中）针对卡方分布的预期分位数进行绘制，如下文所述：

    RG 加勒特 (1989)。卡方图：多元异常值识别的工具。地球化学勘探杂志32（1/3）：319-341。

    （它在mvoutlier R 包中可用。）

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

    Handl, J.、Knowles, J. 和 Kell, DB (2005)。后基因组数据分析中的计算集群验证。 生物信息学21（15）：3201-3212。

    我在Cross Validated上讨论过。例如，您可以在数据的不同随机样本（使用引导程序）上运行算法的多个实例，以获取一系列簇数（例如，k=1 到 20），并根据考虑的优化标准选择 k（平均轮廓宽度、相关相关性等）；它可以完全自动化，无需用户输入。

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

  3. 这是分类中的一个热门话题，一些研究集中在 SVM 以检测异常值，尤其是当它们被错误分类时。一个简单的谷歌查询将返回很多命中，例如Thongkam 等人在乳腺癌生存能力预测中进行异常值检测的支持向量机。(计算机科学讲义2008 4977/2008 99-109；本文包括与集成方法的比较）。最基本的想法是使用一类 SVM 通过拟合多元（例如，高斯）分布来捕获数据的主要结构。边界上或边界外的物体可能被视为潜在的异常值。（在某种意义上，基于密度的聚类的表现与在给定预期分布的情况下定义异常值的真实情况一样好。）

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


    一个相关的主题是异常检测，你会发现很多关于它的论文。

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

于 2011-05-25T09:58:28.547 回答
3

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

基于聚类的方法是寻找聚类的最佳方法，可用于检测异常值作为副产品。在聚类过程中，异常值会影响聚类中心的位置，甚至聚合为一个微聚类。这些特征使得基于集群的方法对于复杂的数据库是不可行的。

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

也许您可以在这个主题上获得一些有价值的知识： Dirichlet Process Clustering

基于狄利克雷的聚类算法可以根据观测数据的分布情况自适应地确定聚类个数。

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

任何监督学习算法都需要足够的标记训练数据来构建分类器。然而，平衡的训练数据集并不总是可用于现实世界的问题，例如入侵检测、医学诊断。根据 Hawkins Outlier 的定义（“Identification of Outliers”. Chapman and Hall, London, 1980），正常数据的数量远大于异常值。大多数监督学习算法无法在上述不平衡数据集上实现有效的分类器。

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

在过去的几十年里，异常值检测的研究从全局计算到局部分析，异常值的描述从二进制解释到概率表示。根据异常检测模型的假设，异常检测算法可以分为四种：基于统计的算法、基于聚类的算法、基于最近邻的算法和基于分类器的算法。关于异常值检测有几个有价值的调查：

  • Hodge, V. 和 Austin, J. “异常值检测方法的调查”，人工智能评论杂志，2004 年。

  • Chandola, V. 和 Banerjee, A. 和 Kumar, V. “异常值检测：一项调查”，ACM 计算调查，2007 年。

于 2012-04-18T09:26:13.277 回答
2

  1. k-means 对数据集中的噪声相当敏感。事先删除异常值时效果最佳。

  2. 没有。任何声称无参数的聚类分析算法通常都受到严格限制，并且通常具有隐藏参数——例如，一个常见的参数是距离函数。任何灵活的聚类分析算法至少会接受自定义距离函数。

  3. 一类分类器是一种流行的机器学习方法来检测异常值。然而，监督方法并不总是适合检测_previously_unseen_ 对象。此外，当数据已经包含异常值时，它们可能会过度拟合。

  4. 每种方法都有其优点和缺点，这就是它们存在的原因。在真实环境中，您将不得不尝试其中的大多数，以查看适合您的数据和设置的方法。这就是为什么异常值检测被称为知识发现- 如果你想发现新的东西，你必须探索......

于 2011-11-26T10:51:25.917 回答
1

您可能想看看ELKI 数据挖掘框架。它应该是异常值检测数据挖掘算法的最大集合。它是开源软件，用 Java 实现，包含大约 20 多种异常值检测算法。请参阅可用算法列表。

请注意，这些算法中的大多数不是基于聚类的。许多聚类算法（尤其是 k-means）将尝试“无论如何”对实例进行聚类。只有少数聚类算法（例如 DBSCAN）真正考虑了可能并非所有实例都属于集群的情况！因此，对于某些算法，异常值实际上会阻止良好的聚类！

于 2012-12-31T15:54:15.557 回答