Консенсусная кластеризация
Метод агрегации результатов из нескольких алгоритмов кластеризации

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

Проблемы с существующими методами кластеризации

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

Обоснование использования консенсусной кластеризации

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

Алгоритм кластеризации консенсуса Монти

Алгоритм консенсусной кластеризации Монти [5] является одним из самых популярных алгоритмов консенсусной кластеризации и используется для определения количества кластеров, . При наличии набора данных с общим количеством точек для кластеризации этот алгоритм работает путем повторной выборки и кластеризации данных, для каждого и вычисляется консенсусная матрица, где каждый элемент представляет собой долю времени, в течение которого два образца кластеризуются вместе. Идеально стабильная матрица будет состоять полностью из нулей и единиц, представляя все пары образцов, всегда кластеризующиеся вместе или не вместе на всех итерациях повторной выборки. Относительная стабильность консенсусных матриц может быть использована для вывода оптимального . К {\displaystyle К} Н {\displaystyle N} K {\displaystyle K} N × N {\displaystyle N\times N} K {\displaystyle K}

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

M h ( i , j ) = { 1 , if  points i and j belong to the same cluster 0 , otherwise {\displaystyle M^{h}(i,j)={\begin{cases}1,&{\text{if}}{\text{ points i and j belong to the same cluster}}\\0,&{\text{otherwise}}\end{cases}}}

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

C ( i , j ) = ( ∑ h = 1 H M h ( i , j ) ∑ h = 1 H I h ( i , j ) ) {\displaystyle C(i,j)=\left({\frac {\textstyle \sum _{h=1}^{H}M^{h}(i,j)\displaystyle }{\sum _{h=1}^{H}I^{h}(i,j)}}\right)}

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

Потенциал избыточной интерпретации алгоритма кластеризации консенсуса Монти

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

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

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

  1. Кластерный ансамбль (Штрель и Гош) : Они рассмотрели различные формулировки проблемы, большинство из которых сводят ее к проблеме разбиения гиперграфа . В одной из своих формулировок они рассматривали тот же граф, что и в задаче корреляционной кластеризации. Решение, которое они предложили, состоит в вычислении наилучшего k -разбиения графа, которое не учитывает штраф за слияние двух узлов, находящихся далеко друг от друга. [1]
  2. Кластеризация агрегации (Ферн и Бродли) : они применили идею кластеризации агрегации к набору мягких кластеризаций, которые они получили с помощью случайных проекций. Они использовали агломеративный алгоритм и не штрафовали за слияние разнородных узлов. [10]
  3. Фред и Джейн : Они предложили использовать единый алгоритм связывания для объединения нескольких запусков алгоритма k -средних. [11]
  4. Дана Кристофор и Дэн Симовичи : Они наблюдали связь между кластеризацией агрегации и кластеризацией категориальных данных . Они предложили меры расстояния теории информации и генетические алгоритмы для поиска наилучшего решения агрегации. [12]
  5. Топчи и др.: Они определили кластерную агрегацию как задачу оценки максимального правдоподобия и предложили EM-алгоритм для поиска консенсусной кластеризации. [13]

Жесткая кластеризация ансамбля

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

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

  1. Алгоритм разбиения на основе кластерного сходства (CSPA) : в CSPA сходство между двумя точками данных определяется как прямо пропорциональное числу составляющих кластеризаций ансамбля, в котором они кластеризованы вместе. Интуиция заключается в том, что чем более похожи две точки данных, тем выше вероятность того, что составляющие кластеризации поместят их в один и тот же кластер. CSPA — это простейшая эвристика, но ее вычислительная сложность и сложность хранения квадратичны по n . SC3 — пример алгоритма типа CSPA. [14] Следующие два метода являются менее затратными в вычислительном отношении:
  2. Алгоритм разбиения гиперграфа (HGPA) : алгоритм HGPA использует совершенно другой подход к поиску консенсусной кластеризации, чем предыдущий метод. Задача кластерного ансамбля формулируется как разбиение гиперграфа путем разрезания минимального числа гиперребер. Они используют hMETIS, который является системой пакетов разбиения гиперграфа.
  3. Алгоритм метакластеризации (MCLA) : Алгоритм метакластеризации (MCLA) основан на кластеризации кластеров. Сначала он пытается решить проблему соответствия кластеров, а затем использует голосование для помещения точек данных в окончательные консенсусные кластеры. Проблема соответствия кластеров решается путем группировки кластеров, идентифицированных в индивидуальных кластеризациях ансамбля. Кластеризация выполняется с использованием METIS и спектральной кластеризации.

Мягкие кластерные ансамбли

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

  1. sCSPA : расширяет CSPA, вычисляя матрицу сходства. Каждый объект визуализируется как точка в размерном пространстве, где каждое измерение соответствует вероятности его принадлежности к кластеру. Этот метод сначала преобразует объекты в пространство меток, а затем интерпретирует скалярное произведение между векторами, представляющими объекты, как их сходство.
  2. sMCLA : расширяет MCLA, принимая мягкие кластеризации в качестве входных данных. Работу sMCLA можно разделить на следующие этапы:
    • Построить мягкий метаграф кластеров
    • Группировка кластеров в мета-кластеры
    • Свернуть метакластеры с помощью взвешивания
    • Соревнуйтесь за предметы
  3. sHBGF : представляет ансамбль как двудольный граф с кластерами и экземплярами в качестве узлов и ребрами между экземплярами и кластерами, к которым они принадлежат. [16] Этот подход может быть тривиально адаптирован для рассмотрения мягких ансамблей, поскольку алгоритм разбиения графа METIS принимает веса на ребрах графа, который должен быть разделен. В sHBGF граф имеет n  +  t вершин, где t — общее число базовых кластеров.
  4. Байесовская консенсусная кластеризация (BCC) : определяет полностью байесовскую модель для мягкой консенсусной кластеризации, в которой множественные исходные кластеризации, определяемые различными входными данными или различными моделями вероятности, как предполагается, слабо придерживаются консенсусной кластеризации. [17] Полная апостериорная вероятность для отдельных кластеризаций и консенсусная кластеризация выводятся одновременно с помощью выборки Гиббса .
  5. Средние нечеткие кластерные значения ансамбля (ECF-средние) : ECF-средние — это алгоритм кластеризации, который объединяет различные результаты кластеризации в ансамбле, достигнутые различными запусками выбранного алгоритма ( k-средних ), в единую окончательную конфигурацию кластеризации. [18]

Ссылки

  1. ^ ab Strehl, Alexander ; Ghosh, Joydeep (2002). "Cluster ensembles – a knowledge reuse framework for combined multiple partitions" (PDF) . Journal on Machine Learning Research (JMLR) . 3 : 583–617. doi :10.1162/153244303321897735. S2CID  3068944. В этой статье рассматривается проблема объединения нескольких разделов набора объектов в одну консолидированную кластеризацию без доступа к функциям или алгоритмам, которые определили эти разделы. Сначала мы определяем несколько сценариев применения для результирующей структуры "повторного использования знаний", которую мы называем кластерными ансамблями. Затем проблема кластерного ансамбля формализуется как комбинаторная задача оптимизации в терминах общей взаимной информации
  2. ^ VEGA-PONS, SANDRO; RUIZ-SHULCLOPER, JOSÉ (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. S2CID  1515525.
  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. ^ abcd Şenbabaoğlu, Y.; Michailidis, G.; Li, JZ (2014). "Критические ограничения консенсусной кластеризации в обнаружении классов". Scientific Reports . 4 : 6207. Bibcode :2014NatSR...4E6207.. doi :10.1038/srep06207. PMC 4145288 . PMID  25158761. 
  7. ^ ab Şenbabaoğlu, Y.; Michailidis, G.; Li, JZ (февраль 2014 г.). «Переоценка консенсусной кластеризации для обнаружения классов». bioRxiv 10.1101/002642 . 
  8. ^ ab Лю, Юфэн; Хейс, Дэвид Нил; Нобель, Эндрю; Маррон, Дж. С. (2008-09-01). "Статистическая значимость кластеризации для данных высокой размерности и малого размера выборки". Журнал Американской статистической ассоциации . 103 (483): 1281–1293. doi :10.1198/016214508000000454. ISSN  0162-1459. S2CID  120819441.
  9. ^ Тибширани, Роберт; Вальтер, Гюнтер; Хасти, Тревор (2001). «Оценка количества кластеров в наборе данных с помощью статистики разрывов». Журнал Королевского статистического общества, серия B (статистическая методология) . 63 (2): 411–423. doi : 10.1111/1467-9868.00293 . ISSN  1467-9868. S2CID  59738652.
  10. ^ Ферн, Сяоли; Бродли, Карла (2004). «Кластерные ансамбли для кластеризации высокой размерности: эмпирическое исследование». J Mach Learn Res . 22 .
  11. ^ Фред, Ана Л. Н.; Джейн, Анил К. (2005). «Объединение множественных кластеризаций с использованием накопления доказательств» (PDF) . Труды IEEE по анализу шаблонов и машинному интеллекту . 27 (6). Институт инженеров по электротехнике и электронике (IEEE): 835–850. doi :10.1109/tpami.2005.113. ISSN  0162-8828. PMID  15943417. S2CID  10316033.
  12. ^ Дэна Кристофор, Дэн Симовичи (февраль 2002 г.). «Поиск медианных разделов с использованием генетических алгоритмов, основанных на теории информации» (PDF) . Журнал универсальной компьютерной науки . 8 (2): 153–172. doi :10.3217/jucs-008-02-0153.
  13. ^ Александр Топчий, Анил К. Джейн, Уильям Панч. Кластерные ансамбли: модели консенсуса и слабых разделов. Международная конференция IEEE по интеллектуальному анализу данных, ICDM 03 и Международная конференция SIAM по интеллектуальному анализу данных, SDM 04
  14. ^ Киселев, Владимир Ю.; Киршнер, Кристина; Шауб, Майкл Т.; Эндрюс, Таллула; Йиу, Эндрю; Чандра, Тамир; Натараджан, Кедар Н.; Рейк, Вольф; Барахона, Маурисио; Грин, Энтони Р.; Хемберг, Мартин (май 2017 г.). "SC3: консенсусная кластеризация данных РНК-секвенирования отдельных клеток". Nature Methods . 14 (5): 483–486. doi :10.1038/nmeth.4236. ISSN  1548-7091. PMC 5410170 . PMID  28346451. 
  15. ^ Кунал Пунера, Джойдип Гхош. Консенсусные ансамбли мягких кластеризаций
  16. ^ Решение задач кластерного ансамбля с помощью разбиения двудольного графа, Сяоли Чжан Ферн и Карла Бродли , Труды двадцать первой международной конференции по машинному обучению
  17. ^ Лок, Э. Ф.; Дансон, Д. Б. (2013). «Байесовская консенсусная кластеризация». Биоинформатика . 29 (20): 2610–2616. arXiv : 1302.7280 . Bibcode : 2013arXiv1302.7280L. doi : 10.1093/bioinformatics/btt425. PMC 3789539. PMID  23990412 . 
  18. ^ Zazzaro, Gaetano; Martone, Angelo (2018). "ECF-means - Ensemble Clustering Fuzzification Means. Новый алгоритм для кластеризации, агрегации, фаззификации и оптимизации". IMM 2018: Восьмая международная конференция по достижениям в области интеллектуального анализа информации и управления .[1]
  • Аристидес Гионис, Хейкки Маннила , Панайотис Цапарас. Кластерная агрегация. 21-я Международная конференция по инженерии данных (ICDE 2005)
  • Хонгджун Ван, Ханхуай Шан, Ариндам Баннерджи. Байесовские кластерные ансамбли [ постоянная нерабочая ссылка ] , Международная конференция SIAM по интеллектуальному анализу данных, SDM 09
  • Нгуен, Нам; Каруана, Рич (2007). «Консенсусные кластеризации». Седьмая международная конференция IEEE по интеллектуальному анализу данных (ICDM 2007) . IEEE. стр. 607–612. doi :10.1109/icdm.2007.73. ISBN 978-0-7695-3018-5. ...мы решаем проблему объединения нескольких кластеризаций без доступа к базовым признакам данных. Этот процесс известен в литературе как кластерные ансамбли, кластерная агрегация или консенсусная кластеризация. Консенсусная кластеризация дает стабильную и надежную окончательную кластеризацию, которая согласуется с множественными кластеризациями. Мы обнаружили, что итеративный EM-подобный метод является исключительно эффективным для этой проблемы. Мы представляем итеративный алгоритм и его вариации для поиска консенсуса кластеризации. Обширное эмпирическое исследование сравнивает наши предлагаемые алгоритмы с одиннадцатью другими методами консенсусной кластеризации на четырех наборах данных с использованием трех различных метрик производительности кластеризации. Экспериментальные результаты показывают, что новые методы кластеризации ансамблей создают кластеризации, которые так же хороши, а часто и лучше, чем эти другие методы.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Consensus_clustering&oldid=1234809234"