代码之家 › 专栏 › 技术社区 › Omry Atia

有效地确定数据集中的点是否没有相邻点

nearest-neighbor distance r

1

Omry Atia · 技术社区 · 7 年前

我有一个数据集,大约有10个点,每个点有200个数字描述符。在10公里点中,我想找出异常值,我把它定义为10个最近的邻居离得很远(多远?到第10个邻居的距离相对于到第10个邻居的其他距离而言是一个离群值,离群值的定义与通常一样)。

我试过计算整个距离矩阵(10公里x 10公里),每行应用部分排序来查找10个最近的邻居。太贵了。

我还查看了快速KNN选项,但它们也太贵了。

我认为这样做更有效的原因是因为我们不关心实际距离,只关心它们的相对等级。

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

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

有创意吗?

2 回复 | 直到 7 年前

1

TilmannZ 7 年前

首先是一个问题,为什么10个最近的邻居都要远离?是否试图避免9个异常值彼此接近的情况?
CoverTree
一般来说,随着维数的增加,knn变得越来越没有意义,因为对于所有点,平均距离趋于相等,除非有一个强聚集的数据集。
PH-Tree
K-means clustering .它不太了解它,但也可能提供异常检测。至少,它应该提供一种方法来确定“太远”的距离。

编辑

2

0

Alexis 7 年前

尽管我怀疑它是否适用于随机数据。

# 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

距离