Кластеризация многомерных данных

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

Проблемы

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

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

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

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

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

Подходы

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

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

Пример двумерного пространства с кластерами подпространства

Кластеризация подпространства направлена ​​на поиск кластеров в различных комбинациях измерений (т. е. подпространств) и в отличие от многих других подходов к кластеризации не предполагает, что все кластеры в наборе данных находятся в одном и том же наборе измерений. ^[3] Кластеризация подпространства может использовать подходы снизу вверх или сверху вниз. Методы снизу вверх (такие как CLIQUE) эвристически идентифицируют соответствующие измерения, разделяя пространство данных на сетку, выбирая плотные единицы, а затем итеративно связывая их, если они смежные и плотные. ^[3]

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

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

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

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

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

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

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

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

Проекционная кластеризация основана на нелинейной проекции многомерных данных в двумерное пространство. ^[11] Типичные проекционные методы, такие как t-распределенное стохастическое вложение соседей (t-SNE) ^[12] или визуализатор поиска соседей (NerV) ^[13], используются для явного проецирования данных в два измерения, игнорируя подпространства более высокой размерности, чем два, и сохраняя только соответствующие окрестности в многомерных данных. На следующем этапе вычисляется граф Делоне ^[14] между проецируемыми точками, и каждая вершина между двумя проецируемыми точками взвешивается с помощью многомерного расстояния между соответствующими многомерными точками данных. После этого кратчайший путь между каждой парой точек вычисляется с помощью алгоритма Дейкстры . ^[15] Затем кратчайшие пути используются в процессе кластеризации, который включает два выбора в зависимости от типа структуры в многомерных данных. ^[11] Этот логический выбор можно сделать, посмотрев на топографическую карту многомерных структур. ^[16] В сравнительном тестировании 34 сопоставимых методов кластеризации кластеризация на основе проекций оказалась единственным алгоритмом, который всегда мог найти многомерную структуру данных на основе расстояний или плотности. ^[11] Кластеризация на основе проекций доступна в пакете R с открытым исходным кодом "ProjectionBasedClustering" на CRAN. ^[17]

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

Агрегация Bootstrap (бэггинг) может использоваться для создания нескольких кластеров и объединения результатов. Это делается путем взятия случайных подвыборок данных, выполнения кластерного анализа для каждой из них и последующего объединения результатов кластеризации для создания меры различия, которая затем может быть использована для исследования и кластеризации исходных данных. ^{[18] [19]} Поскольку высокоразмерные данные, вероятно, будут иметь много неинформативных признаков, веса могут использоваться в процессе бэггинга для увеличения влияния более информативных аспектов. Это создает «несходства ABC», которые затем могут использоваться для исследования и кластеризации исходных данных, а также для оценки того, какие признаки кажутся более влиятельными при определении кластеров. ^{[20] [21] [22]}

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

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

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

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

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

• ELKI включает в себя различные алгоритмы подпространственной и корреляционной кластеризации.
• FCPS включает в себя более пятидесяти алгоритмов кластеризации ^[25]

Ссылки

1. Кригель, HP ; Крёгер, П.; Зимек, А. (2009). «Кластеризация многомерных данных». Труды ACM по обнаружению знаний из данных . 3 : 1–58. doi :10.1145/1497577.1497578. S2CID  17363900.
2. Хоул, ME; Кригель, HP ; Крёгер, P.; Шуберт, E.; Зимек, A. (2010). Могут ли расстояния между соседями победить проклятие размерности? (PDF) . Управление научными и статистическими базами данных. Конспект лекций по информатике. Том 6187. стр. 482. doi :10.1007/978-3-642-13818-8_34. ISBN 978-3-642-13817-1.
3. Парсонс, Лэнс; Хак, Эхтешам; Лю, Хуан (2004-06-01). «Кластеризация подпространства для многомерных данных: обзор». ACM SIGKDD Explorations Newsletter . 6 (1): 90–105. doi :10.1145/1007730.1007731. ISSN  1931-0145.
4. Агравал, Р.; Герке, Дж.; Гунопулос, Д.; Рагхаван, П. (2005). «Автоматическая кластеризация подпространств многомерных данных». Data Mining and Knowledge Discovery . 11 : 5–33. CiteSeerX 10.1.1.131.5152 . doi :10.1007/s10618-005-1396-1. S2CID  9289572. 
5. Kailing, K.; Kriegel, HP ; Kröger, P. (2004). Density-Connected Subspace Clustering for High-Dimensional Data . Труды Международной конференции SIAM 2004 года по интеллектуальному анализу данных. С. 246. doi : 10.1137/1.9781611972740.23 . ISBN 978-0-89871-568-2.
6. Де Аморим, RC; Миркин, Б. (2012). «Метрика Минковского, взвешивание признаков и инициализация аномальных кластеров в кластеризации K-средних». Распознавание образов . 45 (3): 1061. Bibcode : 2012PatRe..45.1061C. doi : 10.1016/j.patcog.2011.08.012.
7. Карбонера, Джоэл Луис; Абель, Мара (ноябрь 2014 г.). «Алгоритм кластеризации подпространств на основе энтропии для категориальных данных». 2014 IEEE 26-я международная конференция по инструментам с искусственным интеллектом . IEEE. стр. 272–277. doi :10.1109/ictai.2014.48. ISBN 9781479965724. S2CID  7208538.
8. Карбонера, Джоэл Луис; Абель, Мара (2015). "CBK-Modes: основанный на корреляции алгоритм для кластеризации категориальных данных". Труды 17-й Международной конференции по корпоративным информационным системам . SCITEPRESS - Science and Technology Publications. стр. 603–608. doi :10.5220/0005367106030608. ISBN 9789897580963.
9. Бём, К.; Кайлинг, К.; Кригель, Х. -П.; Крёгер, П. (2004). Связанная по плотности кластеризация с предпочтениями локального подпространства (PDF) . Четвертая международная конференция IEEE по интеллектуальному анализу данных (ICDM'04). стр. 27. doi :10.1109/ICDM.2004.10087. ISBN 0-7695-2142-8.
10. Aggarwal, CC; Wolf, JL; Yu, PS; Procopiuc, C.; Park, JS (1999). "Быстрые алгоритмы для прогнозируемой кластеризации". ACM SIGMOD Record . 28 (2): 61. CiteSeerX 10.1.1.681.7363 . doi :10.1145/304181.304188. 
11. Thrun, MC, & Ultsch, A.: Использование кластеризации на основе проекций для поиска кластеров на основе расстояний и плотности в многомерных данных, J. Classif., стр. 1-33, doi: 10.1007/s00357-020-09373-2.
12. Ван дер Маатен, Л. и Хинтон, Г.: Визуализация данных с использованием t-SNE, Журнал исследований машинного обучения, т. 9 (11), стр. 2579-2605. 2008.
13. Venna, J., Peltonen, J., Nybo, K., Aidos, H., & Kaski, S.: Перспектива поиска информации для нелинейного снижения размерности для визуализации данных, Журнал исследований машинного обучения, том 11 , стр. 451-490. 2010.
14. Делоне, Б.: Sur la Sphere vide, Изв. Акад. Наук СССР, Отделение Математический и Естественный наук, Том. 7 (793-800), стр. 1-2. 1934 год.
15. Дейкстра, EW: Заметка о двух проблемах, связанных с графиками, Numerische mathematik, Vol. 1 (1), стр. 269-271. 1959.
16. Трун, М. К. и Ульч, А.: Раскрытие многомерных структур проекций с помощью методов снижения размерности, MethodsX, т. 7, стр. 101093, doi: 10.1016/j.mex.20200.101093,2020.
17. "CRAN - Пакет ProjectionBasedClustering". Архивировано из оригинала 2018-03-17.
18. Дюдуа, С. и Фридлянд, Дж. (2003). Бэггинг для повышения точности процедуры кластеризации. Биоинформатика, 19/9, 1090–1099. doi:10.1093/bioinformatics/btg038.
19. Штрель, А. и Гош, Дж. (2002). Кластерные ансамбли — структура повторного использования знаний для объединения нескольких разделов. Журнал исследований машинного обучения. 3. 583-617. 10.1162/153244303321897735.
20. Амаратунга, Д., Кабрера, Дж. и Ковтун, В.. (2008). Обучение микрочипов с помощью ABC. Биостатистика. 9. 128-36. 10.1093/biostatistics/kxm017.
21. Амаратунга, Д. и Кабрера, Дж. и Ли, YS (2014). Меры сходства на основе повторной выборки для многомерных данных. Журнал вычислительной биологии. 22. 10.1089/cmb.2014.0195.
22. Черкас Ю., Амаратунга Д., Рагхаван Н., Сасаки Дж. и Макмиллиан М. (2016). Ранжирование генов ABC для прогнозирования холестаза, вызванного лекарственными препаратами, у крыс, Toxicology Reports, 3: 252–261.
23. Кригель, Х .; Крёгер, П.; Ренц, М.; Вюрст, С. (2005). Общая структура для эффективной кластеризации подпространств многомерных данных (PDF) . Пятая международная конференция IEEE по интеллектуальному анализу данных (ICDM'05). стр. 250. doi :10.1109/ICDM.2005.5. ISBN 0-7695-2278-5.
24. Hund, M.; Böhm, D.; Sturm, W.; Sedlmair, M.; Schreck, T.; Keim, DA; Majnaric, L.; Holzinger, A. (2016). «Визуальная аналитика для исследования концепций в подпространствах групп пациентов: понимание сложных наборов данных с помощью врача-в-круге». Brain Informatics . 3 (4): 233–247. doi :10.1007/s40708-016-0043-5. PMC 5106406 . PMID  27747817. 
25. Трун, MC, и Стир, Q.: Набор фундаментальных алгоритмов кластеризации, SoftwareX, т. 13(C), стр. 100642, doi: 10.1016/j.softx.2020.100642, 2021.