Кластеризация многомерных данных - Clustering high-dimensional data

Кластеризация многомерных данных это кластерный анализ данных от нескольких десятков до многих тысяч размеры. Такие многомерные пространства данных часто встречаются в таких областях, как лекарство, где Микрочип ДНК технология может производить множество измерений одновременно, и кластеризация текстовые документы, где, если используется вектор частоты слов, количество измерений равно размер словарного запаса.

Проблемы

Для кластеризации многомерных данных необходимо преодолеть четыре проблемы:^[1]

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

{ displaystyle lim _ {d to infty} { frac {dist _ { max} -dist _ { min}} {dist _ { min}}} = 0}

Кластер предназначен для группировки связанных объектов на основе наблюдений за значениями их атрибутов. Однако, учитывая большое количество атрибутов, некоторые из них обычно не имеют смысла для данного кластера. Например, в обследование новорожденных кластер образцов может идентифицировать новорожденных, у которых одинаковые значения крови, что может привести к пониманию значимости определенных показателей крови для заболевания. Но для разных заболеваний разные значения крови могут образовывать кластер, а другие значения могут не коррелировать. Это известно как релевантность местной особенности проблема: разные кластеры могут быть найдены в разных подпространствах, поэтому глобальной фильтрации атрибутов недостаточно.
Учитывая большое количество атрибутов, вполне вероятно, что некоторые атрибуты коррелированный. Следовательно, кластеры могут существовать в произвольно ориентированных аффинные подпространства.

Недавние исследования показывают, что проблемы распознавания возникают только тогда, когда существует большое количество нерелевантных измерений, и что подходы с общим ближайшим соседом могут улучшить результаты.^[2]

Подходы

Подходы к кластеризации в параллельных осях или произвольно ориентированных аффинные подпространства различаются тем, как они интерпретируют общую цель, заключающуюся в нахождении кластеров в данных с высокой размерностью.^[1] В целом другой подход - найти кластеры на основе шаблон в матрице данных, часто называемый бикластеризация, который часто используется в биоинформатика.

Подпространственная кластеризация

Пример 2D-пространства с подпространственными кластерами

На соседнем изображении показано простое двухмерное пространство, в котором можно идентифицировать несколько кластеров. В одномерных подпространствах кластеры ${ displaystyle c_ {a}}$ (в подпространстве ${ Displaystyle {х }}$ ) и ${ displaystyle c_ {b}}$ , ${ displaystyle c_ {c}}$ , ${ displaystyle c_ {d}}$ (в подпространстве ${ Displaystyle {у }}$ ) можно найти. ${ displaystyle c_ {c}}$ нельзя рассматривать как кластер в двумерном (подпространстве), поскольку он слишком редко распределен в ${ displaystyle x}$ ось. В двух измерениях два кластера ${ displaystyle c_ {ab}}$ и ${ displaystyle c_ {ad}}$ можно идентифицировать.

Проблема кластеризации подпространств обусловлена тем, что есть ${ displaystyle 2 ^ {d}}$ различные подпространства пространства с ${ displaystyle d}$ Габаритные размеры. Если подпространства не параллельны осям, возможно бесконечное количество подпространств. Следовательно, алгоритмы кластеризации подпространств используют некоторый вид эвристический чтобы оставаться выполнимым с точки зрения вычислений, с риском получения худших результатов. Например, свойство закрытия вниз (ср. правила ассоциации ) может использоваться для построения подпространств более высокой размерности только путем объединения подпространств более низкой размерности, так как любое подпространство T, содержащее кластер, приведет к тому, что полное пространство S также будет содержать этот кластер (то есть S ⊆ T), подход, используемый большинством традиционных алгоритмов, таких как CLIQUE,^[3] SUBCLU.^[4] Также возможно определить подпространство, используя разные степени релевантности для каждого измерения, подход, принятый iMWK-Means,^[5] EBK-режимы^[6] и CBK-режимы.^[7]

Прогнозируемая кластеризация

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

Например, алгоритм PreDeCon проверяет, какие атрибуты, по-видимому, поддерживают кластеризацию для каждой точки, и настраивает функцию расстояния так, чтобы размеры с низкими отклонение усиливаются в функции расстояния.^[8] На рисунке выше кластер ${ displaystyle c_ {c}}$ можно найти с помощью DBSCAN с функцией расстояния, которая уделяет меньше внимания ${ displaystyle x}$ -оси и, таким образом, преувеличивает небольшую разницу в ${ displaystyle y}$ -axis достаточно, чтобы сгруппировать точки в кластер.

PROCLUS использует аналогичный подход с k-medoid кластеризация.^[9] Угадываются исходные медоиды, и для каждого медоида определяется подпространство, охватываемое атрибутами с низкой дисперсией. Баллы присваиваются ближайшему медоиду с учетом только подпространства этого медоида при определении расстояния. Затем алгоритм работает как обычный PAM алгоритм.

Если функция расстояния оценивает атрибуты по-разному, но никогда не с 0 (и, следовательно, никогда не отбрасывает нерелевантные атрибуты), алгоритм называется "мягкий" прогнозируемый алгоритм кластеризации.

Гибридные подходы

Не все алгоритмы пытаются либо найти уникальное назначение кластера для каждой точки, либо для всех кластеров во всех подпространствах; многие соглашаются на промежуточный результат, когда обнаруживается ряд, возможно, перекрывающихся, но не обязательно исчерпывающих групп. Примером является ПОЖАРЫ, который по своему базовому подходу представляет собой алгоритм кластеризации подпространств, но использует эвристический слишком агрессивен, чтобы достоверно создать все подпространственные кластеры.^[10] Другой гибридный подход состоит в том, чтобы включить человека в алгоритмический цикл: опыт человека в области может помочь сократить экспоненциальное пространство поиска за счет эвристического отбора образцов. Это может быть полезно в области здравоохранения, где, например, врачи сталкиваются с многомерными описаниями состояний пациента и измерениями успешности определенных методов лечения. Важным вопросом в таких данных является сравнение и корреляция состояния пациентов и результатов терапии с комбинациями параметров. Количество измерений часто очень велико, следовательно, их необходимо сопоставить с меньшим количеством соответствующих измерений, чтобы они были более удобными для экспертного анализа. Это связано с тем, что нерелевантные, избыточные и конфликтующие измерения могут отрицательно повлиять на эффективность и результативность всего аналитического процесса. ^[11]

Корреляционная кластеризация

Другой тип подпространств рассматривается в Корреляционная кластеризация (интеллектуальный анализ данных).

Программного обеспечения

ELKI включает в себя различные алгоритмы подпространственной и корреляционной кластеризации

Рекомендации

^ ^а ^б Кригель, Х.; Kröger, P .; Зимек, А. (2009). «Кластеризация многомерных данных». Транзакции ACM при обнаружении знаний из данных. 3: 1–58. Дои:10.1145/1497577.1497578.
^ Houle, M.E .; Кригель, Х.; Kröger, P .; Schubert, E .; Зимек, А. (2010). Могут ли расстояния между общими соседями победить проклятие размерности? (PDF). Управление научно-статистической базой данных. Конспект лекций по информатике. 6187. п. 482. Дои:10.1007/978-3-642-13818-8_34. ISBN 978-3-642-13817-1.
^ Agrawal, R .; Gehrke, J .; Gunopulos, D .; Рагхаван, П. (2005). «Автоматическая подпространственная кластеризация данных большой размерности». Интеллектуальный анализ данных и обнаружение знаний. 11: 5–33. CiteSeerX 10.1.1.131.5152. Дои:10.1007 / s10618-005-1396-1.
^ Kailing, K .; Кригель, Х.; Крегер, П. (2004). Связанная с плотностью кластеризация подпространств для данных большой размерности. Материалы Международной конференции SIAM 2004 года по интеллектуальному анализу данных. стр.246. Дои:10.1137/1.9781611972740.23. ISBN 978-0-89871-568-2.
^ De Amorim, R.C .; Миркин Б. (2012). «Метрика Минковского, взвешивание признаков и инициализация аномального кластера в кластеризации K-средних». Распознавание образов. 45 (3): 1061. Дои:10.1016 / j.patcog.2011.08.012.
^ Карбонера, Джоэл Луис; Абель, Мара (ноябрь 2014 г.). Основанный на энтропии алгоритм кластеризации подпространств для категориальных данных. 2014 26-я Международная конференция IEEE по инструментам с искусственным интеллектом. IEEE. Дои:10.1109 / ictai.2014.48. ISBN 9781479965724.
^ Карбонера, Джоэл Луис; Абель, Мара (2015). CBK-Modes: основанный на корреляции алгоритм для категориальной кластеризации данных. Материалы 17-й Международной конференции по корпоративным информационным системам. SCITEPRESS - Научно-технические публикации. Дои:10.5220/0005367106030608. ISBN 9789897580963.
^ Böhm, C .; Kailing, K .; Кригель, Х. -П.; Крегер, П. (2004). Кластеризация, связанная с плотностью, с предпочтениями локального подпространства (PDF). Четвертая международная конференция IEEE по интеллектуальному анализу данных (ICDM'04). п. 27. Дои:10.1109 / ICDM.2004.10087. ISBN 0-7695-2142-8.
^ Aggarwal, C.C .; Wolf, J. L .; Ю. П. С .; Procopiuc, C .; Парк, Дж. С. (1999). «Быстрые алгоритмы прогнозируемой кластеризации». Запись ACM SIGMOD. 28 (2): 61. CiteSeerX 10.1.1.681.7363. Дои:10.1145/304181.304188.
^ Кригель, Х.; Kröger, P .; Ренц, М .; Вурст, С. (2005). Общая структура для эффективной подпространственной кластеризации многомерных данных (PDF). Пятая Международная конференция IEEE по интеллектуальному анализу данных (ICDM'05). п. 250. Дои:10.1109 / ICDM.2005.5. ISBN 0-7695-2278-5.
^ Hund, M .; Böhm, D .; Sturm, W .; Sedlmair, M .; Schreck, T .; Keim, D.A .; Majnaric, L .; Хольцингер, А. (2016). «Визуальная аналитика для исследования концепций в подпространствах групп пациентов: понимание сложных наборов данных с помощью врача-в-петле». Информатика мозга. 3 (4): 233–247. Дои:10.1007 / s40708-016-0043-5. ЧВК 5106406. PMID 27747817.

[survey-1] а ^б Кригель, Х.; Kröger, P .; Зимек, А. (2009). «Кластеризация многомерных данных». Транзакции ACM при обнаружении знаний из данных. 3: 1–58. Дои:10.1145/1497577.1497578.

[2] Houle, M.E .; Кригель, Х.; Kröger, P .; Schubert, E .; Зимек, А. (2010). Могут ли расстояния между общими соседями победить проклятие размерности? (PDF). Управление научно-статистической базой данных. Конспект лекций по информатике. 6187. п. 482. Дои:10.1007/978-3-642-13818-8_34. ISBN 978-3-642-13817-1.

[3] Agrawal, R .; Gehrke, J .; Gunopulos, D .; Рагхаван, П. (2005). «Автоматическая подпространственная кластеризация данных большой размерности». Интеллектуальный анализ данных и обнаружение знаний. 11: 5–33. CiteSeerX 10.1.1.131.5152. Дои:10.1007 / s10618-005-1396-1.

[4] Kailing, K .; Кригель, Х.; Крегер, П. (2004). Связанная с плотностью кластеризация подпространств для данных большой размерности. Материалы Международной конференции SIAM 2004 года по интеллектуальному анализу данных. стр.246. Дои:10.1137/1.9781611972740.23. ISBN 978-0-89871-568-2.

[5] De Amorim, R.C .; Миркин Б. (2012). «Метрика Минковского, взвешивание признаков и инициализация аномального кластера в кластеризации K-средних». Распознавание образов. 45 (3): 1061. Дои:10.1016 / j.patcog.2011.08.012.

[6] Карбонера, Джоэл Луис; Абель, Мара (ноябрь 2014 г.). Основанный на энтропии алгоритм кластеризации подпространств для категориальных данных. 2014 26-я Международная конференция IEEE по инструментам с искусственным интеллектом. IEEE. Дои:10.1109 / ictai.2014.48. ISBN 9781479965724.

[7] Карбонера, Джоэл Луис; Абель, Мара (2015). CBK-Modes: основанный на корреляции алгоритм для категориальной кластеризации данных. Материалы 17-й Международной конференции по корпоративным информационным системам. SCITEPRESS - Научно-технические публикации. Дои:10.5220/0005367106030608. ISBN 9789897580963.

[8] Böhm, C .; Kailing, K .; Кригель, Х. -П.; Крегер, П. (2004). Кластеризация, связанная с плотностью, с предпочтениями локального подпространства (PDF). Четвертая международная конференция IEEE по интеллектуальному анализу данных (ICDM'04). п. 27. Дои:10.1109 / ICDM.2004.10087. ISBN 0-7695-2142-8.

[9] Aggarwal, C.C .; Wolf, J. L .; Ю. П. С .; Procopiuc, C .; Парк, Дж. С. (1999). «Быстрые алгоритмы прогнозируемой кластеризации». Запись ACM SIGMOD. 28 (2): 61. CiteSeerX 10.1.1.681.7363. Дои:10.1145/304181.304188.

[10] Кригель, Х.; Kröger, P .; Ренц, М .; Вурст, С. (2005). Общая структура для эффективной подпространственной кластеризации многомерных данных (PDF). Пятая Международная конференция IEEE по интеллектуальному анализу данных (ICDM'05). п. 250. Дои:10.1109 / ICDM.2005.5. ISBN 0-7695-2278-5.

[11] Hund, M .; Böhm, D .; Sturm, W .; Sedlmair, M .; Schreck, T .; Keim, D.A .; Majnaric, L .; Хольцингер, А. (2016). «Визуальная аналитика для исследования концепций в подпространствах групп пациентов: понимание сложных наборов данных с помощью врача-в-петле». Информатика мозга. 3 (4): 233–247. Дои:10.1007 / s40708-016-0043-5. ЧВК 5106406. PMID 27747817.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]