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

Консенсусная кластеризация - это метод агрегирования (потенциально противоречивых) результатов нескольких алгоритмов кластеризации. Также называемый кластерными ансамблями или агрегацией кластеризации (или разделов), он относится к ситуации, в которой было получено несколько различных (входных) кластеров для определенного набора данных, и желательно найти один ( консенсус), которая в некотором смысле подходит лучше, чем существующие кластеры. Таким образом, согласованная кластеризация - это проблема согласования информации о кластеризации одного и того же набора данных, поступающей из разных источников или из разных прогонов одного и того же алгоритма. При отнесении к задаче оптимизации консенсусная кластеризация известна как медианное разделение, и было показано, что она NP-Complete, даже когда количество входных кластеров равно трем. Консенсусная кластеризация для обучения без учителя аналогична ансамблевому обучению в обучении с учителем.

• 1 Проблемы с существующими методами кластеризации
• 2 Обоснование использования консенсусной кластеризации
• 3 Консенсусный алгоритм кластеризации Монти
• 4 Потенциал чрезмерной интерпретации алгоритма консенсусной кластеризации Монти
• 5 Связанные работа
• 6 Жесткая ансамблевая кластеризация
  • 6.1 Эффективные консенсусные функции
• 7 Мягкие ансамбли кластеризации
• 8 Источники
• 9 Ссылки

• Текущие методы кластеризации не решают все
• Работа с большим количеством измерений и большим количеством элементов данных может быть проблематичной из-за сложности времени;
• Эффективность метода зависит от определения «расстояния» (для кластеризация на основе расстояния)
• Если очевидной меры расстояния не существует, мы должны «определить» ее, что не всегда легко, особенно в многомерных пространствах.
• Результат кластеризации алгоритм (который во многих случаях сам может быть произвольным) может быть int интерпретируются по-разному.

Все существующие методы кластеризации имеют потенциальные недостатки. Это может затруднить интерпретацию результатов, особенно когда нет информации о количестве кластеров. Методы кластеризации также очень чувствительны к начальным параметрам кластеризации, что может привести к тому, что незначительные данные будут усилены с помощью не повторяющихся методов. Чрезвычайно важным вопросом в кластерном анализе является проверка результатов кластеризации, то есть как получить уверенность в значимости кластеров, предоставляемых методом кластеризации (номера кластеров и назначения кластеров). При отсутствии внешнего объективного критерия (эквивалент известного ярлыка класса в контролируемом анализе) такая проверка становится несколько труднодостижимой. Методы итеративной кластеризации спуска, такие как SOM и кластеризация k-средних, позволяют обойти некоторые недостатки иерархической кластеризации, обеспечивая однозначно определенные кластеры и границы кластеров. Консенсусная кластеризация предоставляет метод, который представляет собой консенсус между несколькими запусками алгоритма кластеризации, для определения количества кластеров в данных и оценки стабильности обнаруженных кластеров. Этот метод также можно использовать для представления консенсуса по нескольким запускам алгоритма кластеризации со случайным перезапуском (например, K-средних, байесовской кластеризации на основе модели, SOM и т. Д.), Чтобы учесть его чувствительность к начальным условиям.. Он может предоставить данные для инструмента визуализации, чтобы проверить номер кластера, членство и границы. Однако им не хватает интуитивной и визуальной привлекательности иерархических дендрограмм кластеризации, и количество кластеров необходимо выбирать априори.

Консенсусный алгоритм кластеризации Монти является одним из самых популярных алгоритмов консенсусной кластеризации и используется для определения количества кластеров, $K\; \{\backslash \; displaystyle\; K\}$. Учитывая набор данных из $N\; \{\backslash \; displaystyle\; N\}$общего количества точек для кластеризации, этот алгоритм работает путем повторной выборки и кластеризации данных для каждого $K\; \{\backslash \; displaystyle\; K\}$и $NXN\; \{\backslash \; displaystyle\; NXN\}$вычисляется консенсусная матрица, где каждый элемент представляет собой долю двух сгруппированных вместе выборок. Совершенно стабильная матрица будет состоять полностью из нулей и единиц, представляя все пары выборок, всегда кластеризованные вместе или не вместе на всех итерациях повторной выборки. Относительная стабильность консенсусных матриц может использоваться для вывода оптимального $K\; \{\backslash \; displaystyle\; K\}$.

Более конкретно, учитывая набор точек для кластеризации, $D\; =\; \{e\; 1,\; e\; 2,...\; e\; N\}\; \{\backslash \; displaystyle\; D\; =\; \backslash \; \{e\_\; \{1\},\; e\_\; \{2\},...\; e\_\; \{N\}\; \backslash \}\}$, пусть $D\; 1,\; D\; 2,...,\; DH\; \{\backslash \; displaystyle\; D\; ^\; \{1\},\; D\; ^\; \{2\},...,\; D\; ^\; \{H\}\}$будет списком $H\; \{\backslash \; displaystyle\; H\}$преобразованные (передискретизированные) наборы данных исходного набора данных $D\; \{\backslash \; displaystyle\; D\}$, и пусть $M\; h\; \{\backslash \; displaystyle\; M\; ^\; \{h\}\}$обозначает $NXN\; \{\backslash \; displaystyle\; NXN\}$матрица связности, полученная в результате применения алгоритма кластеризации к набору данных $D\; h\; \{\backslash \; displaystyle\; D\; ^\; \{h\}\}$. Записи $M\; h\; \{\backslash \; displaystyle\; M\; ^\; \{h\}\}$определяются следующим образом:

$M\; h\; (i,\; j)\; =\; \{1,\; если\; точки\; i\; и\; j\; принадлежат\; тот\; же\; кластер\; 0,\; в\; противном\; случае\; \{\backslash \; displaystyle\; M\; ^\; \{h\}\; (i,\; j)\; =\; \{\backslash \; begin\; \{cases\}\; 1,\; \{\backslash \; text\; \{if\}\}\; \{\backslash \; text\; \{точки\; i\; и\; j\; принадлежат\; одному\; кластеру\}\}\; \backslash \backslash \; 0,\; \{\backslash \; text\; \{else\}\}\; \backslash \; end\; \{cases\}\}\}$

Пусть $I\; h\; \{\backslash \; displaystyle\; I\; ^\; \{h\}\}$будет $NXN\; \{\; \backslash \; displaystyle\; NXN\}$матрица идентификатора, где $(i,\; j)\; \{\backslash \; displaystyle\; (i,\; j)\}$-й элемент равен 1, если точки $i\; \{\backslash \; displaystyle\; i\}$и $j\; \{\backslash \; displaystyle\; j\}$находятся в одном наборе возмущенных данных $D\; h\; \{\backslash \; displaystyle\; D\; ^\; \{h\}\}$и 0 в противном случае. Индикаторная матрица используется для отслеживания того, какие образцы были выбраны во время каждой итерации повторной выборки для этапа нормализации. Матрица консенсуса $C\; \{\backslash \; displaystyle\; C\}$определяется как нормализованная сумма всех матриц связности всех возмущенных наборов данных, и для каждого $K\; \{\backslash \; displaystyle\; K\}\; вычисляется\; другая.$.

$С\; (я,\; j)\; знак\; равно\; (\sum \; час\; =\; 1\; ЧМ\; час\; (я,\; j)\; \sum \; час\; =\; 1\; привет\; час\; (я,\; j))\; \{\backslash \; displaystyle\; C\; (i,\; j)\; =\; \backslash \; left\; (\{\backslash \; frac\; \{\backslash \; textstyle\; \backslash \; sum\; \_\; \{h\; =\; 1\}\; ^\; \{H\}\; M\; ^\; \{h\}\; (i,\; j)\; \backslash \; displaystyle\}\; \{\backslash \; sum\; \_\; \{h\; =\; 1\}\; ^\; \{H\}\; I\; ^\; \{h\}\; (i,\; j)\}\}\; \backslash \; right)\}$

Это запись $(i,\; j)\; \{\backslash \; displaystyle\; (i,\; j)\}$в матрице консенсуса - это количество точек $i\; \{\backslash \; displaystyle\; i\}$и $j\; \{\backslash \; displaystyle\; j\}$были сгруппированы вместе, разделенные на общее количество раз, когда они были выбраны вместе. Матрица симметрична, и каждый элемент определяется в диапазоне $[0,\; 1]\; \{\backslash \; displaystyle\; [0,1]\}$. Консенсусная матрица вычисляется для каждого $K\; \{\backslash \; displaystyle\; K\}$, подлежащего проверке, и стабильности каждой матрицы, то есть того, насколько далеко матрица находится от матрицы идеальной стабильности (только нули и единица) используется для определения оптимального $K\; \{\backslash \; displaystyle\; K\}$. Один из способов количественной оценки стабильности $K\; \{\backslash \; displaystyle\; K\}$th матрицы консенсуса - изучить ее кривую CDF (см. Ниже).

Показатель PAC (доля неоднозначной кластеризации) объяснен. Оптимальный K - это K с наименьшим значением PAC.

Консенсусная кластеризация Монти может быть мощным инструментом для идентификации кластеров, но ее следует применять с осторожностью, как показано Ченбабаоглу и др. Было показано, что консенсусный алгоритм кластеризации Монти может заявлять о очевидной стабильности случайного разбиения нулевых наборов данных, взятых из унимодального распределения, и, таким образом, может привести к чрезмерной интерпретации стабильности кластера в реальном исследовании. Если кластеры плохо разделены, консенсусная кластеризация может привести к заключению очевидной структуры, когда ее нет, или к декларации стабильности кластера, когда она неуловима. Выявление ложноположительных кластеров является общей проблемой во всех исследованиях кластеров, и ее решали с помощью таких методов, как SigClust и GAP-statistic. Однако эти методы полагаются на определенные предположения для нулевой модели, которые не всегда могут быть подходящими.

enbabaoğlu et al продемонстрировали исходную метрику дельта K, чтобы решить, что $K\; \{\backslash \; displaystyle\; K\}$в алгоритме Монти работает плохо, и предложили новую улучшенную метрику для измерения стабильности матрицы консенсуса с использованием их кривых CDF. На кривой CDF согласованной матрицы нижняя левая часть представляет пары выборок, которые редко сгруппированы вместе, верхняя правая часть представляет те, которые почти всегда сгруппированы вместе, тогда как средний сегмент представляет пары с неоднозначным назначением в разных прогонах кластеризации. Доля показателя неоднозначной кластеризации (PAC) количественно определяет этот средний сегмент; и определяется как доля пар выборок с согласованными индексами, попадающими в интервал (u 1, u 2) ∈ [0, 1], где u 1 - значение, близкое к 0, а u 2 - значение, близкое к 1 (например, u 1 = 0,1 и u 2 = 0,9). Низкое значение PAC указывает на плоский средний сегмент и низкую частоту несогласованных назначений в переставленных циклах кластеризации. Следовательно, можно сделать вывод об оптимальном количестве кластеров по значению $K\; \{\backslash \; displaystyle\; K\}$, имеющему самый низкий PAC.

1. Ансамбль кластеризации (Штрел и Гош) : они рассмотрели различные формулировки проблемы, большинство из которых сводят проблему к проблеме разделения гиперграфа. В одной из своих постановок они рассматривали тот же граф, что и в задаче корреляционной кластеризации. Предложенное ими решение состоит в том, чтобы вычислить лучшее k-разбиение графа, которое не учитывает штраф за слияние двух узлов, находящихся далеко друг от друга.

2. Агрегация кластеров (Fern and Brodley) : они применили идею агрегации кластеризации к набору мягких кластеров, полученных путем случайных проекций. Они использовали агломеративный алгоритм и не наказывали за слияние разнородных узлов.

3. Фред и Джейн : Они предложили использовать один алгоритм связывания для объединения нескольких прогонов алгоритма k-средних.

4. Дана Кристофор и Дэн Симовичи : Они наблюдали связь между агрегированием кластеров и кластеризацией категориальных данных. Они предложили теоретико-информационные меры расстояния и предложили генетические алгоритмы для поиска лучшего решения для агрегирования.

5. Топчи и др. : Они определили агрегацию кластеризации как задачу оценки максимального правдоподобия и предложили алгоритм EM для поиска консенсусной кластеризации.

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

Эффективные консенсусные функции

1. Алгоритм разделения на основе подобия на основе кластеров (CSPA)

В CSPA сходство между двумя точками данных определяется как прямо пропорциональное количеству составляющих кластеров ансамбля, в котором они объединены вместе. Интуиция подсказывает, что чем больше схожих двух точек данных, тем выше вероятность того, что составляющие кластеры поместят их в один и тот же кластер. CSPA - это простейшая эвристика, но ее вычислительная сложность и сложность хранения квадратичны по n. SC3 - это пример алгоритма типа CSPA. Следующие два метода менее затратны в вычислительном отношении:

2. Алгоритм разделения гиперграфа (HGPA)

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

3. Алгоритм метакластеризации (MCLA)

Алгоритм мета-кластеризации (MCLA) основан на кластеризации кластеров. Сначала он пытается решить проблему соответствия кластеров, а затем использует голосование для помещения точек данных в окончательные согласованные кластеры. Проблема соответствия кластеров решается путем группирования кластеров, идентифицированных в отдельных кластерах ансамбля. Кластеризация выполняется с использованием METIS и спектральной кластеризации.

Пунера и Гош расширили идею ансамблей жесткой кластеризации до сценария мягкой кластеризации. Каждый экземпляр в мягком ансамбле представлен конкатенацией r распределений апостериорной вероятности членства, полученных из составляющих алгоритмов кластеризации. Мы можем определить меру расстояния между двумя экземплярами, используя дивергенцию Кульбака – Лейблера (KL), которая вычисляет «расстояние» между двумя распределениями вероятностей.

1. sCSPA

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

2. sMCLA

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

• Построение мягкого мета-графа кластеров
• Группировка кластеров в мета-кластеры
• Свернуть мета-кластеры с использованием взвешивания
• Соревнуйтесь за объекты

3. sHBGF

HBGF представляет ансамбль как двудольный граф с кластерами и экземплярами в качестве узлов и ребрами между экземплярами и кластерами, которым они принадлежат. Этот подход может быть тривиально адаптирован для рассмотрения мягких ансамблей, поскольку алгоритм разбиения графа METIS принимает веса на ребрах разбиваемого графа. В sHBGF граф имеет n + t вершин, где t - общее количество лежащих в основе кластеров.

4. Байесовская консенсусная кластеризация (BCC)

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

1. ^Штрел, Александр; Гош, Джойдип (2002). «Кластерные ансамбли - структура повторного использования знаний для объединения нескольких разделов» (PDF). Журнал исследований в области машинного обучения (JMLR). 3 : 583–617.
2. ^VEGA-PONS, SANDRO; РУИЗ-ШУЛЬКЛОПЕР, ХОЗЕ (1 мая 2011 г.). «Обзор алгоритмов кластеризации ансамбля». Международный журнал распознавания образов и искусственного интеллекта. 25 (3): 337–372. doi : 10.1142 / S0218001411008683. S2CID 4643842.
3. ^Филков, Владимир (2003). Интеграция данных микрочипов путем согласованной кластеризации. В материалах 15-й Международной конференции IEEE по инструментам с искусственным интеллектом. С. 418–426. CiteSeerX 10.1.1.116.8271. doi : 10.1109 / TAI.2003.1250220. ISBN 978-0-7695-2038-4.
4. ^Бониццони, Паола; Делла Ведова, Джанлука; Донди, Риккардо; Цзян, Тао (2008). «Об аппроксимации корреляционной кластеризации и консенсусной кластеризации». Журнал компьютерных и системных наук. 74 (5): 671–696. doi : 10.1016 / j.jcss.2007.06.024.
5. ^Монти, Стефано; Тамайо, Пабло; Месиров, Джилл; Голуб, Тодд (2003-07-01). «Консенсусная кластеризация: метод на основе повторной выборки для обнаружения классов и визуализации данных микрочипа экспрессии генов». Машинное обучение. 52 (1): 91–118. doi : 10.1023 / A: 1023949509487. ISSN 1573-0565.
6. ^ enbabaolu, Y.; Michailidis, G.; Ли, Дж. З. (2014). «Критические ограничения консенсусной кластеризации при обнаружении классов». Научные отчеты. 4 : 6207. Bibcode : 2014NatSR... 4E6207.. doi : 10.1038 / srep06207. PMC 4145288. PMID 25158761.
7. ^ enbabaolu, Y.; Michailidis, G.; Ли, Дж. З. (февраль 2014 г.). «Переоценка консенсуса кластеризации для обнаружения классов». bioRxiv 10.1101 / 002642.
8. ^ Лю, Юйфэн; Хейс, Дэвид Нил; Нобель, Андрей; Маррон, Дж. С. (01.09.2008). «Статистическая значимость кластеризации для данных большой размерности с малым размером выборки». Журнал Американской статистической ассоциации. 103 (483): 1281–1293. doi : 10.1198 / 016214508000000454. ISSN 0162-1459.
9. ^Тибширани, Роберт; Вальтер, Гюнтер; Хасти, Тревор (2001). «Оценка количества кластеров в наборе данных с помощью статистики пробелов». Журнал Королевского статистического общества: серия B (статистическая методология). 63 (2): 411–423. DOI : 10.1111 / 1467-9868.00293. ISSN 1467-9868.
10. ^Киселев Владимир Ю; Киршнер, Кристина; Шауб, Майкл Т; Эндрюс, Таллула; Ю, Эндрю; Чандра, Тамир; Натараджан, Кедар Н; Рейк, Вольф; Бараона, Маурисио; Грин, Энтони Р.; Хемберг, Мартин (май 2017 г.). «SC3: консенсусная кластеризация одноклеточных данных РНК-seq». Природные методы. 14 (5): 483–486. doi : 10,1038 / nmeth.4236. ISSN 1548-7091. PMC 5410170. PMID 28346451.
11. ^Решение задач кластерного ансамбля с помощью разделения двудольного графа, Сяоли Чжан Ферн и Карла Бродли, Труды двадцать первой международной конференции по машинному обучению
12. ^Замок, EF; Дансон, Д. (2013). «Байесовская консенсусная кластеризация». Биоинформатика. 29 (20): 2610–2616. arXiv : 1302.7280. Bibcode : 2013arXiv1302.7280L. doi : 10.1093 / bioinformatics / btt425. PMC 3789539. PMID 23990412.

• Александр Стрел и Дж. Гош, Кластерные ансамбли - структура повторного использования знаний для объединения нескольких разделов, Журнал по машинному обучению Research (JMLR) 2002, 3, 583–617.
• Кунал Пунера, Джойдип Гош. Основанные на консенсусе ансамбли мягких кластеров.
• Аристидес Гионис, Хейкки Маннила, Панайотис Цапарас. Агрегация кластеров. 21-я Международная конференция по инженерии данных (ICDE 2005)
• Хунджун Ван, Ханхуай Шань, Ариндам Банерджи. Байесовские кластерные ансамбли, Международная конференция SIAM по интеллектуальному анализу данных, SDM 09
• Нам Нгуен, Рич Каруана. Консенсусные кластеризации. Седьмая Международная конференция IEEE по интеллектуальному анализу данных.
• Александр Топчий, Анил К. Джайн, Уильям Панч. Кластерные ансамбли: модели консенсуса и слабых разделов. Международная конференция IEEE по интеллектуальному анализу данных, ICDM 03 и Международная конференция SIAM по интеллектуальному анализу данных, SDM 04