Outlier обнаружение в добыче данных

Question

У меня есть несколько наборов вопросов, касающихся обнаружения выбросов:

1. Можем ли мы найти выбросы с помощью K-средства и это хороший подход?

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

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

4. Каковы преимущества и недостатки каждого подхода?

Answer 1

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

1. Я бы не использовать 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 
   

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

   

   Одним из возможных вариантов, однако, были бы использовать двухэтапный подход, где один-х извлекая экстремальные точки (здесь определяется как вектор далеко от своих кластерных центроидов) итерационным способом, как описаны в следующем бумага: Improving K-Means by Outlier Removal (Hautamäki, et al.).

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

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

   Р.Г. Гарретт (1989). The chi-square plot: a tools for multivariate outlier recognition. Журнал геохимических исследований 32 (1/3): 319-341.

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

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

   Handl, J., Knowles, J., and Kell, D.B. (2005). Computational cluster validation in post-genomic data analysis. Биоинформатика 21 (15): 3201-3212.

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

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

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

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

   • Hodge, V.J. и Austin, J. A Survey of Outlier Detection Methodologies.
   • Vinueza, A. and Grudic, G.Z. Unsupervised Outlier Detection and Semi-Supervised Learning.
   • Escalante, H.J. A Comparison of Outlier Detection Algorithms for Machine Learning.

   
   Родственная тема anomaly detection, о котором вы найдете много статей.

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

Answer 2

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

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

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

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

Answer 3

1) Можно ли найти выбросы с помощью K-средства, является его хороший подход?

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

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

Может быть, вы можете получить ценные знания по этой теме: Dirichlet Process Clustering

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

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

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

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

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

• Ходжи, В. и Остин, Дж «Обзор методик обнаружения резко отклоняющихся значения», журнал искусственного интеллекта Review, 2004.

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

Answer 4

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

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