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

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

Проблемы

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

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

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

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

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

Подходы

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

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

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

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

На соседнем изображении показано простое двумерное пространство, в котором можно идентифицировать несколько кластеров. В одномерных подпространствах кластеры $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, СУБКЛЮ . Также возможно определить подпространство, используя разную степень релевантности для каждого измерения - подход, используемый iMWK-Means, EBK-режимы и режимы CBK.

кластеризация

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

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

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

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

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

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

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

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

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

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

Корреляционная

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

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

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