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

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

Проблемы

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

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

\lim _{d\to \infty }{\frac {dist_{\max }-dist_{\min }}{dist_{\min }}}=0

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

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

Подходы

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

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

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

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

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

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

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

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

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

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

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

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

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

Кластеризация на основе начальной загрузки

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

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

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

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

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

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

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

Ссылки

^ Jump up to: ^а ^б Кригель, HP ; Крегер, П.; Зимек, А. (2009). «Кластеризация многомерных данных». Транзакции ACM по извлечению знаний из данных . 3 :1–58. дои : 10.1145/1497577.1497578 . S2CID 17363900 .
^ Хоул, Мэн; Кригель, HP ; Крегер, П.; Шуберт, Э.; Зимек, А. (2010). Могут ли расстояния между общими соседями победить проклятие размерности? (PDF) . Управление научными и статистическими базами данных. Конспекты лекций по информатике. Том. 6187. с. 482. дои : 10.1007/978-3-642-13818-8_34 . ISBN 978-3-642-13817-1 .
^ Jump up to: ^а ^б Парсонс, Лэнс; Хак, Этешам; Лю, Хуан (1 июня 2004 г.). «Подпространственная кластеризация для данных большой размерности: обзор» . Информационный бюллетень об исследованиях ACM SIGKDD . 6 (1): 90–105. дои : 10.1145/1007730.1007731 . ISSN 1931-0145 .
^ Агравал, Р.; Герке, Дж.; Гунопулос, Д.; Рагхаван, П. (2005). «Автоматическая подпространственная кластеризация многомерных данных». Интеллектуальный анализ данных и обнаружение знаний . 11 :5–33. CiteSeerX 10.1.1.131.5152 . дои : 10.1007/s10618-005-1396-1 . S2CID 9289572 .
^ Кайлинг, К.; Кригель, HP ; Крегер, П. (2004). Кластеризация подпространств, связанных по плотности, для многомерных данных . Материалы Международной конференции SIAM 2004 г. по интеллектуальному анализу данных. стр. 246 . дои : 10.1137/1.9781611972740.23 . ISBN 978-0-89871-568-2 .
^ Де Аморим, RC; Миркин, Б. (2012). «Метрика Минковского, взвешивание признаков и инициализация аномального кластера в кластеризации K-средних». Распознавание образов . 45 (3): 1061. Бибкод : 2012PatRe..45.1061C . дои : 10.1016/j.patcog.2011.08.012 .
^ Карбонера, Джоэл Луис; Абель, Мара (ноябрь 2014 г.). «Алгоритм кластеризации подпространства на основе энтропии для категориальных данных». 26-я Международная конференция IEEE по инструментам с искусственным интеллектом , 2014 г. IEEE. стр. 272–277. дои : 10.1109/ictai.2014.48 . ISBN 9781479965724 . S2CID 7208538 .
^ Карбонера, Джоэл Луис; Абель, Мара (2015). «Режимы CBK: алгоритм категориальной кластеризации данных на основе корреляции». Материалы 17-й Международной конференции по информационным системам предприятия . SCITEPRESS - Публикации по науке и технологиям. стр. 603–608. дои : 10.5220/0005367106030608 . ISBN 9789897580963 .
^ Бём, К.; Кайлинг, К.; Кригель, Х.-П. ; Крегер, П. (2004). Кластеризация по плотности связности с настройками локального подпространства (PDF) . Четвертая Международная конференция IEEE по интеллектуальному анализу данных (ICDM'04). п. 27. дои : 10.1109/ICDM.2004.10087 . ISBN 0-7695-2142-8 .
^ Аггарвал, CC; Вольф, Дж.Л.; Ю, ПС; Прокопюк, К.; Парк, Дж.С. (1999). «Быстрые алгоритмы прогнозируемой кластеризации». Запись ACM SIGMOD . 28 (2): 61. CiteSeerX 10.1.1.681.7363 . дои : 10.1145/304181.304188 .
^ Jump up to: ^а ^б ^с Трун, М.К., и Ульч, А.: Использование кластеризации на основе проекций для поиска кластеров на основе расстояния и плотности в многомерных данных, J. Classif., стр. 1–33, doi: 10.1007/s00357-020-09373-2 .
^ Ван дер Маатен, Л., и Хинтон, Г.: Визуализация данных с использованием t-SNE, Журнал исследований машинного обучения, Vol. 9 (11), стр. 2579-2605. 2008.
^ Венна Дж., Пелтонен Дж., Нибо К., Айдос Х. и Каски С.: Перспектива поиска информации для нелинейного уменьшения размерности для визуализации данных, Журнал исследований машинного обучения, Vol. 11 , стр. 451-490. 2010.
^ Delaunay, B.: Sur la sphere vide, Izv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk, Vol. 7 (793-800), pp. 1-2. 1934.
^ Дейкстра, EW: Заметка о двух проблемах, связанных с графиками, Numerische mathematik, Vol. 1 (1), стр. 269-271. 1959.
^ Трун, М.К., и Ульч, А.: Раскрытие многомерных структур проекций с помощью методов уменьшения размерности, MethodsX, Vol. 7, стр. 101093, номер документа: 10.1016/j.mex.20200.101093,2020 .
^ «CRAN — Пакетная кластеризация на основе проекций» . Архивировано из оригинала 17 марта 2018 г.
^ Дюдуа С. и Фридлянд Дж. (2003). Пакетирование для повышения точности процедуры кластеризации. Биоинформатика, 19/9, 1090–1099. doi:10.1093/биоинформатика/btg038.
^ Стрел, А. и Гош, Дж. (2002). Кластерные ансамбли — структура повторного использования знаний для объединения нескольких разделов. Журнал исследований машинного обучения. 3. 583-617. 10.1162/153244303321897735.
^ Амаратунга Д., Кабрера Дж. и Ковтун В.. (2008). Обучение микрочипов с помощью ABC. Биостатистика. 9. 128-36. 10.1093/биостатистика/kxm017.
^ Амаратунга, Д., Кабрера, Дж. и Ли, Ю.С. (2014). Меры сходства на основе повторной выборки для многомерных данных. Журнал вычислительной биологии. 22. 10.1089/смб.2014.0195.
^ Черкас Ю., Амаратунга Д., Рагхаван Н., Сасаки Дж. и Макмиллиан М. (2016). Ранжирование генов ABC для прогнозирования холестаза, вызванного лекарственными препаратами, у крыс, Toxicology Reports, 3: 252–261.
^ Кригель, Х .; Крегер, П.; Ренц, М.; Вурст, С. (2005). Общая основа для эффективной подпространственной кластеризации многомерных данных (PDF) . Пятая Международная конференция IEEE по интеллектуальному анализу данных (ICDM'05). п. 250. дои : 10.1109/ICDM.2005.5 . ISBN 0-7695-2278-5 .
^ Хунд, М.; Бём, Д.; Штурм, В.; Седлмайр, М.; Шрек, Т.; Кейм, окружной прокурор; Майнарик, Л.; Хольцингер, А. (2016). «Визуальная аналитика для исследования концепций в подпространствах групп пациентов: понимание сложных наборов данных с помощью «Доктора в цикле»» . Мозговая информатика . 3 (4): 233–247. дои : 10.1007/s40708-016-0043-5 . ПМК 5106406 . ПМИД 27747817 .
^ Трун, MC, и Стир, Q.: Пакет фундаментальных алгоритмов кластеризации, SoftwareX, Vol. 13(C), стр. 100642, doi: 10.1016/j.softx.2020.100642, 2021 .

[survey-1] Jump up to: ^а ^б Кригель, HP ; Крегер, П.; Зимек, А. (2009). «Кластеризация многомерных данных». Транзакции ACM по извлечению знаний из данных . 3 :1–58. дои : 10.1145/1497577.1497578 . S2CID 17363900 .

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

[:1-3] Jump up to: ^а ^б Парсонс, Лэнс; Хак, Этешам; Лю, Хуан (1 июня 2004 г.). «Подпространственная кластеризация для данных большой размерности: обзор» . Информационный бюллетень об исследованиях ACM SIGKDD . 6 (1): 90–105. дои : 10.1145/1007730.1007731 . ISSN 1931-0145 .

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

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

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

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

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

[9] Бём, К.; Кайлинг, К.; Кригель, Х.-П. ; Крегер, П. (2004). Кластеризация по плотности связности с настройками локального подпространства (PDF) . Четвертая Международная конференция IEEE по интеллектуальному анализу данных (ICDM'04). п. 27. дои : 10.1109/ICDM.2004.10087 . ISBN 0-7695-2142-8 .

[10] Аггарвал, CC; Вольф, Дж.Л.; Ю, ПС; Прокопюк, К.; Парк, Дж.С. (1999). «Быстрые алгоритмы прогнозируемой кластеризации». Запись ACM SIGMOD . 28 (2): 61. CiteSeerX 10.1.1.681.7363 . дои : 10.1145/304181.304188 .

[:0-11] Jump up to: ^а ^б ^с Трун, М.К., и Ульч, А.: Использование кластеризации на основе проекций для поиска кластеров на основе расстояния и плотности в многомерных данных, J. Classif., стр. 1–33, doi: 10.1007/s00357-020-09373-2 .

[12] Ван дер Маатен, Л., и Хинтон, Г.: Визуализация данных с использованием t-SNE, Журнал исследований машинного обучения, Vol. 9 (11), стр. 2579-2605. 2008.

[13] Венна Дж., Пелтонен Дж., Нибо К., Айдос Х. и Каски С.: Перспектива поиска информации для нелинейного уменьшения размерности для визуализации данных, Журнал исследований машинного обучения, Vol. 11 , стр. 451-490. 2010.

[14] Delaunay, B.: Sur la sphere vide, Izv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk, Vol. 7 (793-800), pp. 1-2. 1934.

[15] Дейкстра, EW: Заметка о двух проблемах, связанных с графиками, Numerische mathematik, Vol. 1 (1), стр. 269-271. 1959.

[16] Трун, М.К., и Ульч, А.: Раскрытие многомерных структур проекций с помощью методов уменьшения размерности, MethodsX, Vol. 7, стр. 101093, номер документа: 10.1016/j.mex.20200.101093,2020 .

[17] «CRAN — Пакетная кластеризация на основе проекций» . Архивировано из оригинала 17 марта 2018 г.

[18] Дюдуа С. и Фридлянд Дж. (2003). Пакетирование для повышения точности процедуры кластеризации. Биоинформатика, 19/9, 1090–1099. doi:10.1093/биоинформатика/btg038.

[19] Стрел, А. и Гош, Дж. (2002). Кластерные ансамбли — структура повторного использования знаний для объединения нескольких разделов. Журнал исследований машинного обучения. 3. 583-617. 10.1162/153244303321897735.

[20] Амаратунга Д., Кабрера Дж. и Ковтун В.. (2008). Обучение микрочипов с помощью ABC. Биостатистика. 9. 128-36. 10.1093/биостатистика/kxm017.

[21] Амаратунга, Д., Кабрера, Дж. и Ли, Ю.С. (2014). Меры сходства на основе повторной выборки для многомерных данных. Журнал вычислительной биологии. 22. 10.1089/смб.2014.0195.

[22] Черкас Ю., Амаратунга Д., Рагхаван Н., Сасаки Дж. и Макмиллиан М. (2016). Ранжирование генов ABC для прогнозирования холестаза, вызванного лекарственными препаратами, у крыс, Toxicology Reports, 3: 252–261.

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

[24] Хунд, М.; Бём, Д.; Штурм, В.; Седлмайр, М.; Шрек, Т.; Кейм, окружной прокурор; Майнарик, Л.; Хольцингер, А. (2016). «Визуальная аналитика для исследования концепций в подпространствах групп пациентов: понимание сложных наборов данных с помощью «Доктора в цикле»» . Мозговая информатика . 3 (4): 233–247. дои : 10.1007/s40708-016-0043-5 . ПМК 5106406 . ПМИД 27747817 .

[25] Трун, MC, и Стир, Q.: Пакет фундаментальных алгоритмов кластеризации, SoftwareX, Vol. 13(C), стр. 100642, doi: 10.1016/j.softx.2020.100642, 2021 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]