эффективно решить, не имеет ли точка в наборе данных близких соседей - PullRequest
Новая
       6

эффективно решить, не имеет ли точка в наборе данных близких соседей

0 голосов
/ 23 июня 2018

У меня есть набор данных с примерно 10K точек, каждый из которых имеет 200 числовых дескрипторов. Из 10 тысяч точек я хотел бы найти выбросы, которые я определяю как те, чьи 10 ближайших соседей находятся далеко (насколько далеко? Расстояние до 10-го соседа является выбросом с точки зрения других расстояний до 10-го соседа). , Выброс определяется как обычно).

Я попытался вычислить всю матрицу расстояний (10K x 10K), для каждой строки примените частичную сортировку, чтобы найти 10 ближайших соседей. Слишком дорого.

Я также проверил варианты быстрого kNN, но они также слишком дороги.

Причина, по которой я думаю, что это может быть сделано гораздо эффективнее, заключается в том, что мы на самом деле не заботимся о реальных расстояниях, а только об их относительных разрядах.

Пример матрицы данных может быть сгенерирован следующим образом: 

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

Какие-нибудь креативные идеи?

Ответы [ 2 ]

0 голосов
/ 24 июня 2018

Вот идея, хотя я сомневаюсь, что она может работать для случайных данных. 

# 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 для каждого столбца, если ваши данные не нормализованы.

0 голосов
/ 23 июня 2018
  • Сначала вопрос, почему все 10 ближайших соседей находятся далеко?Пытаетесь избежать ситуаций, когда 9 посторонних находятся близко друг к другу?
  • Что такое «слишком медленно»?Вы пробовали что-то вроде CoverTree ?У него очень быстрый kNN для высокой размерности.
  • Ускорение: Вы пробовали использовать расстояние L1 / Манхэттен / Такси?Это имеет тенденцию быть быстрее, чем евклидово расстояние.
  • Вообще говоря, с увеличением размерности kNN становится все более бессмысленным, поскольку среднее расстояние имеет тенденцию становиться равным для всех точек, если у вас нет сильно кластеризованного набора данных.
  • Общая идея: если вы каким-то образом рассчитали расстояние, которое, как известно, находится «далеко», вы можете просто использовать оконные запросы, чтобы проверить, есть ли какие-либо другие точки на расстоянии «слишком далеко».Здесь я хотел бы предложить использовать PH-Tree , у него очень быстрые оконные запросы, особенно когда размер результата мал (0 или 1 попадание).Он также может быть адаптирован для отмены окна после 1 или 10 попаданий и просто возврата, что есть больше попаданий (или нет).Это должно быть быстрее, чем кНН.Проблема в том, что оконные запросы становятся все более неэффективными с высокой размерностью, по крайней мере, при использовании L2-расстояния (евклидово).L1 должен быть более эффективным.
  • Также обратите внимание на К-среднюю кластеризацию .Он мало что знает об этом, но может также обеспечить обнаружение выбросов.По крайней мере, он должен предоставить вам способ определить, как далеко «слишком далеко».
  • Одна из техник, используемых (например) в машинном обучении, - уменьшение размерности.Это немного сложно, но если вы можете уменьшить размерность до 10 или около того, алгоритмы kNN (или любой другой алгоритм) могут быть намного быстрее,

EDIT

Я провел несколько тестов производительности на своем компьютере (I7-4790) с использованием реализаций Java: Набор данных с точкой 10K и 200 измерениями (точки слегка кластеризованы, все между 0,0 и 1,0 в каждом измерении).

  • CoverTree: загрузка 10000 точек занимает 1,6 секунды.10000 запросов к ближайшему соседу - около 3,1 секунды.
  • PH-дерево: загрузка 10000 точек занимает 0,07 секунды.10000 оконных запросов (размер окна выбран таким, что средний размер результата = 1) составляет около 5,5 секунд.
...