有效地决定数据集中的一个点是否没有近邻

Question

我有一个包含大约 10K 个点的数据集，每个点有 200 个数字描述符。在这 10K 个点中，我想找到离群点，我将其定义为距离最近的 10 个邻居很远的点（多远？就与第 10 个邻居的其他距离而言，到第 10 个邻居的距离是离群点, 离群值被照常定义）。

我已经尝试计算整个距离矩阵 (10K x 10K)，对每一行应用部分排序以找到 10 个最近的邻居。太贵了。

我也检查了快速 kNN 选项，但它们也太贵了。

我认为这可以更有效地完成的原因是因为我们并不真正关心实际距离，而只关心它们的相对排名。

示例数据矩阵可以生成如下：

df = matrix(rnorm(2000000), nrow = 10000, ncol = 200)

有什么创意吗？

Answer 1

首先一个问题，为什么10个最近的邻居都远呢？是否试图避免 9 个离群值彼此靠近的情况？
什么是'too slow'？您是否尝试过 CoverTree 之类的东西？对于高维度，它具有非常快的 kNN。
加速：您尝试过使用 L1/Manhattan/Taxi 距离吗？它往往比欧氏距离更快。
一般来说，随着维数的增加，kNN 变得越来越无意义，因为所有点的平均距离趋于相等，除非你有一个强聚类的数据集。
总体思路：如果您以某种方式计算出已知为 'to far' 的距离，您可以简单地使用 window 查询来检查 [=43] 中是否还有其他点=]距离。在这里我建议使用 PH-Tree，它具有非常快的 window 查询，尤其是当结果大小很小（0 或 1 次命中）时。它也可以适用于在 1 次或 10 次命中后中止 window 并且只是 return 有更多的命中（或没有）。这应该比 kNN 更快。问题是 window 查询在高维度上变得越来越低效，至少在使用 L2 距离（欧几里德）时是这样。 L1应该更有效率。
另外，看看K-means clustering。它对此了解不多，但它也可能提供异常值检测。至少，它应该为您提供一种确定 'too far away' 有多远的方法。
机器学习中（例如）使用的一种技术是降维。这有点棘手，但如果你能将维度降低到 10 左右，kNN 算法（或任何其他算法）可能会快得多，

编辑

我使用 Java 实现在我的计算机 (I7-4790) 上进行了一些性能测试：具有 10K 个点和 200 个维度的数据集（点稍微聚集，每个维度都在 0.0 和 1.0 之间）。

CoverTree：加载10000点需要1.6秒。 10000 次 1-最近邻查询大约需要 3.1 秒。
PH-tree：加载10000点需要0.07秒。 10000 window 次查询（选择 window 大小使得平均结果大小 = 1）大约需要 5.5 秒。

Answer 2

这是一个想法，尽管我怀疑它是否适用于随机数据。

# primarily for lag and lead
library(dplyr)

# sample data
df <- mtcars %>%
  select(mpg, disp, drat, wt, qsec) %>%
  do(as.data.frame(scale(.))) %>%
  filter_all(all_vars(!duplicated(.)))

knn <- 4L
distance <- 0.3

colwise_outlier <- sapply(1L:ncol(df), function(j) {
  column <- df[, j]
  order_ids <- order(column)
  column <- column[order_ids]

  n <- (knn + 2L) %/% 2L
  outlier <- column - lag(column, n=n, default=-Inf) > distance & 
    lead(column, n=n, default=Inf) - column > distance

  # return with original order
  outlier[order_ids]
})

is_outlier <- apply(colwise_outlier, 1L, function(r) {
  Reduce("&", r)
})

outliers <- df[is_outlier,]

它所做的是首先单独检查每一列，并且仅当最多 knn 个值在 distance 范围内时才将一行标记为异常值。然后它只保留所有列中满足此条件的行。

编辑：您甚至可以为每一列设置不同的 distance 值，如果您的数据未标准化。

有效地决定数据集中的一个点是否没有近邻

efficiently decide whether a point in a data set has no close neighbors

r

distance

nearest-neighbor