Обнаружение выбросов при добыче данных

Ответ 1

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

• Я бы не использовал k-средства для определения выбросов в многомерном наборе данных по той простой причине, что алгоритм k-средних не создан для этой цели: вы всегда будете иметь решение, которое минимизирует суммарная сумма квадратов внутри кластера (и, следовательно, максимизирует межкластерную SS, потому что полная дисперсия фиксирована), а outlier (s) не обязательно будут определять свой собственный кластер. Рассмотрим следующий пример в 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, et al.).

  Это имеет некоторое сходство с тем, что сделано в генетических исследованиях для обнаружения и удаления лиц, которые проявляют ошибку генотипирования, или лиц, которые являются братьями/сестрами/близнецами (или когда мы хотим определить субструктуру населения), в то время как мы хотим сохранить не связанных между собой лиц; в этом случае мы используем многомерное масштабирование (которое эквивалентно PCA, с точностью до константы для первых двух осей) и удаляет наблюдения выше или ниже 6 SD на любой из топовых 10 или 20 осей (см., например, Структура населения и Eigenanalysis, Patterson et al., PLoS Genetics 2006 2 (12)).

  Общей альтернативой является использование упорядоченных надежных расстояний mahalanobis, которые могут быть построены (в графике QQ) против ожидаемых квантилей распределения хи-квадратов, как описано в следующей статье:

  R.G. Гарретт (1989). Сюжет хи-квадрат: инструменты для многомерного распознавания выбросов. Журнал геохимических исследований 32 (1/3): 319-341.

  (Он доступен в пакете mvoutlier R.)

• Это зависит от того, что вы называете пользователем. Я интерпретирую ваш вопрос как может ли какой-либо алгоритм автоматически обрабатывать матрицу расстояний или исходные данные и останавливаться на оптимальном количестве кластеров. Если это так и для любого алгоритма разбиения на расстоянии, вы можете использовать любой из доступных индексов действительности для кластерного анализа; хороший обзор приведен в

  Handl, J., Knowles, J., and Kell, D.B. (2005). Проверка вычислительного кластера в анализе постгеномных данных. Биоинформатика 21 (15): 3201-3212.

  который я обсуждал в Cross Validated. Например, можно запустить несколько экземпляров алгоритма для разных случайных выборок (с использованием бутстрапа) данных, для диапазона номеров кластеров (например, k = от 1 до 20) и выбрать k в соответствии с оптимизированными критериями, которые считались (в среднем ширина силуэта, коэффетическая корреляция и т.д.); он может быть полностью автоматизирован, нет необходимости вводить пользователя.

  Существуют другие формы кластеризации, основанные на плотности (кластеры рассматриваются как области, где объекты необычно распространены) или распределение (кластеры - это совокупности объектов, которые следуют за заданным распределением вероятности). Например, кластеризация на основе моделей, как она реализована в Mclust, позволяет идентифицировать кластеры в многомерном наборе данных, охватывая диапазон форму для матрицы дисперсии-ковариации для различного количества кластеров и выбрать лучшую модель в соответствии с критерием BIC.

• Это горячая тема в классификации, а некоторые исследования сосредоточены на SVM для обнаружения выбросов, особенно когда они ошибочно классифицируются. Простой запрос Google возвращает много обращений, например. Поддержка векторной машины для обнаружения извне в прогнозе выживаемости рака молочной железыThongkam et al. (Лекционные заметки в области компьютерных наук 2008 4977/2008 99-109, в эту статью включено сравнение с ансамблевыми методами). Самой основной идеей является использование одноклассового SVM для захвата основной структуры данных путем подгонки для него многомерного (например, гауссовского) распределения; объекты, которые на или за пределами границы могут рассматриваться как потенциальные выбросы. (В определенном смысле кластеризация на основе плотности будет работать одинаково хорошо, так как определение того, что действительно представляет собой выброс, является более простым с учетом ожидаемого распределения.)

  Другие подходы к неконтролируемому, полуконтролируемому или контролируемому обучению легко доступны в Google, например.

  • Ходж, В.Я. и Остин, J. A Обзор методологий обнаружения выбросов.
  • Винуэза, А. и Грудик, Г.З. Неконтролируемое обнаружение извне и полунаучное обучение.
  • Escalante, H.J. A Сравнение алгоритмов обнаружения выбросов для машинного обучения.

  
  Связанная тема обнаружение аномалий, о котором вы найдете много документов.

• Это действительно заслуживает нового (и, вероятно, более целенаправленного) вопроса: -)

Ответ 2

1) Можем ли мы найти выбросы с использованием k-средств, это хороший подход?

Кластерные подходы оптимальны для поиска кластеров и могут использоваться для обнаружения выбросов как побочные продукты. В процессах кластеризации выбросы могут влиять на местоположение центров кластера, даже агрегируя в качестве микрокластера. Эти характеристики делают кластерные подходы неосуществимыми для сложных баз данных.

2) Существует ли какой-либо алгоритм кластеризации, который не принимает никаких данных от пользователя?

Возможно, вы можете получить некоторые ценные знания по этой теме: Кластеризация процессов Дирихле

Алгоритм кластеризации на основе Дирихле может адаптивно определять количество кластеров в соответствии с распределением данных наблюдений.

3) Можем ли мы использовать машину векторной поддержки или любой другой контролируемый алгоритм обучения для обнаружения выбросов?

Любой программируемый алгоритм обучения требует достаточной маркировки данных обучения для построения классификаторов. Однако сбалансированный набор учебных материалов не всегда доступен для решения реальных проблем, таких как обнаружение вторжений, медицинская диагностика. Согласно определению Hawkins Outlier ( "Идентификация выбросов", Chapman and Hall, London, 1980), число нормальных данных намного больше, чем количество выбросов. Большинство контролируемых алгоритмов обучения не могут обеспечить эффективный классификатор на вышеупомянутом несбалансированном наборе данных.

4) В чем преимущества и недостатки каждого подхода?

В течение последних нескольких десятилетий исследование обнаружения выбросов варьировалось от глобального расчета до локального анализа, а описания выбросов варьировались от бинарных интерпретаций до вероятностных представлений. Согласно гипотезам моделей обнаружения выбросов, алгоритмы обнаружения выбросов можно разделить на четыре типа: алгоритмы на основе статистики, алгоритмы на основе кластеров, алгоритмы Nearest Neighborhood и алгоритмы на основе классификаторов. Существует несколько ценных обзоров по обнаружению выбросов:

• Ходж, В. и Остин, Дж. "Обзор методологий обнаружения выбросов", журнал "Анализ искусственного интеллекта", 2004 г.

• Chandola, V. and Banerjee, A. and Kumar, V. "Обнаружение выбросов: опрос", ACM Computing Surveys, 2007.

Ответ 3

• k-средство довольно чувствительно к шуму в наборе данных. Он работает лучше всего, когда вы заранее удаляете выбросы.

• Нет. Любой алгоритм кластерного анализа, который, как утверждается, не имеет параметров, обычно сильно ограничен и часто имеет скрытые параметры. Например, общий параметр - это функция расстояния. Любой алгоритм гибкого кластерного анализа, по крайней мере, примет пользовательскую функцию расстояния.

• классификаторы одного класса являются популярным методом машинного обучения для обнаружения выбросов. Однако контролируемые подходы не всегда подходят для обнаружения объектов _previously_unseen_. Кроме того, они могут переработать, когда данные уже содержат выбросы.

• Каждый подход имеет свои плюсы и минусы, поэтому они существуют. В реальной настройке вам придется попробовать большинство из них, чтобы посмотреть, что работает для ваших данных и настроек. Это почему обнаружение outlier называется обнаружение знаний - вам нужно исследовать, хотите ли вы открыть что-то новое...

Ответ 4

Возможно, вам захочется взглянуть на структуру интеллектуального анализа данных ELKI. Это, по-видимому, самая большая коллекция алгоритмов интеллектуального анализа данных обнаружения выбросов. Это программное обеспечение с открытым исходным кодом, реализованное на Java, и включает в себя более 20 алгоритмов обнаружения обнаружения. См. список доступных алгоритмов.

Обратите внимание, что большинство этих алгоритмов не основаны на кластеризации. Многие алгоритмы кластеризации (в частности, k-средства) будут пытаться группировать экземпляры "независимо от того, что". Только несколько алгоритмов кластеризации (например, DBSCAN) фактически рассматривают случай, когда, возможно, не все экземпляры принадлежат кластерам! Поэтому для некоторых алгоритмов выбросы будут фактически препятствовать хорошей кластеризации!