Консенсусная кластеризация
Консенсусная кластеризация — это метод агрегирования (потенциально противоречивых) результатов нескольких алгоритмов кластеризации . Также называемые кластерными ансамблями [1] или агрегирование кластеров (или разделов), это относится к ситуации, в которой для определенного набора данных было получено несколько различных (входных) кластеризаций, и желательно найти единственную (консенсусную) кластеризацию, которая лучше подходит для некоторых смысл, чем существующие кластеризации. [2] Таким образом, консенсусная кластеризация — это проблема согласования информации о кластеризации об одном и том же наборе данных, поступающей из разных источников или из разных запусков одного и того же алгоритма. Консенсусная кластеризация, рассматриваемая как задача оптимизации, называется медианным разделением и, как было показано, является NP-полной . [3] даже если количество входных кластеризаций равно трем. [4] Консенсусная кластеризация для обучения без учителя аналогична ансамблевому обучению в обучении с учителем.
Проблемы с существующими методами кластеризации
[ редактировать ]- Современные методы кластеризации не отвечают всем требованиям должным образом.
- Работа с большим количеством измерений и большим количеством элементов данных может быть проблематичной из-за временных затрат;
- Эффективность метода зависит от определения понятия « расстояние » (для кластеризации на основе расстояний).
- Если очевидной меры расстояния не существует, мы должны ее «определить», что не всегда легко, особенно в многомерных пространствах.
- Результат работы алгоритма кластеризации (который во многих случаях сам по себе может быть произвольным) можно интерпретировать по-разному.
Обоснование использования консенсусной кластеризации
[ редактировать ]У всех существующих методов кластеризации есть потенциальные недостатки. Это может затруднить интерпретацию результатов, особенно если нет данных о количестве кластеров. Методы кластеризации также очень чувствительны к первоначальным настройкам кластеризации, что может привести к усилению несущественных данных в неповторяющихся методах. Чрезвычайно важным вопросом кластерного анализа является проверка результатов кластеризации, то есть как получить уверенность в значимости кластеров, обеспечиваемых методом кластеризации (номера кластеров и их назначений). При отсутствии внешнего объективного критерия (эквивалента известной метки класса в контролируемом анализе) эта проверка становится несколько неуловимой.Методы итеративной кластеризации спуска, такие как SOM и кластеризация k-средних, обходят некоторые недостатки иерархической кластеризации , обеспечивая однозначно определенные кластеры и границы кластеров. Консенсусная кластеризация представляет собой метод, который представляет собой консенсус при нескольких запусках алгоритма кластеризации, чтобы определить количество кластеров в данных и оценить стабильность обнаруженных кластеров. Этот метод также можно использовать для представления консенсуса при нескольких запусках алгоритма кластеризации со случайным перезапуском (например, K-средние, байесовская кластеризация на основе модели, SOM и т. д.), чтобы учесть его чувствительность к начальным условиям. . Он может предоставить данные для инструмента визуализации для проверки количества, членства и границ кластера. Однако им не хватает интуитивной и визуальной привлекательности дендрограмм иерархической кластеризации, и количество кластеров необходимо выбирать априори.
Алгоритм консенсусной кластеризации Монти
[ редактировать ]Алгоритм консенсусной кластеризации Монти [5] является одним из самых популярных алгоритмов консенсусной кластеризации и используется для определения количества кластеров, . Учитывая набор данных общее количество точек для кластеризации. Этот алгоритм работает путем повторной выборки и кластеризации данных для каждой и Рассчитывается консенсусная матрица, где каждый элемент представляет долю раз, когда два образца сгруппированы вместе. Совершенно стабильная матрица будет полностью состоять из нулей и единиц, представляя все пары выборок, которые всегда группируются или не группируются вместе на всех итерациях повторной выборки. Относительная стабильность консенсусных матриц может быть использована для вывода оптимального варианта. .
Более конкретно, учитывая набор точек для кластеризации, , позволять быть списком возмущенные (пересэмплированные) наборы данных исходного набора данных , и пусть обозначают матрица связности, полученная в результате применения алгоритма кластеризации к набору данных . Записи определяются следующим образом:
Позволять быть матрица идентификатора, где -я запись равна 1, если точки и находятся в одном и том же возмущенном наборе данных , и 0 в противном случае. Матрица индикаторов используется для отслеживания того, какие выборки были выбраны во время каждой итерации повторной выборки на этапе нормализации. Матрица консенсуса определяется как нормализованная сумма всех матриц связности всех возмущенных наборов данных, и для каждого вычисляется другая матрица. .
Это запись в матрице консенсуса — это количество точек, умноженных на и были сгруппированы вместе, разделенные на общее количество раз, когда они были выбраны вместе. Матрица симметрична, и каждый элемент определяется в диапазоне . Матрица консенсуса рассчитывается для каждого для проверки, а стабильность каждой матрицы, то есть то, насколько матрица находится от матрицы идеальной стабильности (только нули и единицы), используется для определения оптимального . Один из способов количественной оценки стабильности Консенсусная матрица проверяет свою кривую CDF (см. ниже).
Потенциал чрезмерной интерпретации алгоритма консенсусной кластеризации Монти
[ редактировать ]
Консенсусная кластеризация Монти может быть мощным инструментом для идентификации кластеров, но ее необходимо применять с осторожностью, как показали Шенбабаоглу и др. [6] Было показано, что алгоритм консенсусной кластеризации Монти может претендовать на очевидную стабильность случайного разделения нулевых наборов данных, взятых из унимодального распределения, и, таким образом, может привести к чрезмерной интерпретации стабильности кластера в реальном исследовании. [6] [7] Если кластеры плохо разделены, консенсусная кластеризация может привести к выводу о видимой структуре, когда ее нет, или к заявлению о стабильности кластера, когда она незначительна. Выявление ложноположительных кластеров является распространенной проблемой в кластерных исследованиях. [8] и решается такими методами, как SigClust [8] и GAP-статистика. [9] Однако эти методы основаны на определенных предположениях для нулевой модели, которые не всегда могут быть подходящими.
Шенбабаоглу и др . [6] продемонстрировал исходную метрику дельта 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 указывает на ровный средний сегмент и низкий уровень несогласованных присвоений в перестановочных запусках кластеризации. Таким образом, можно определить оптимальное количество кластеров по значение, имеющее наименьший PAC. [6] [7]
Связанная работа
[ редактировать ]- Ансамбль кластеризации (Штрель и Гош) : они рассмотрели различные формулировки проблемы, большинство из которых сводят проблему к проблеме разделения гиперграфа . В одной из своих формулировок они рассматривали тот же граф, что и в задаче корреляционной кластеризации. Предложенное ими решение — вычислить лучшее k -разделение графа, не учитывающее штраф за слияние двух узлов, находящихся далеко друг от друга. [1]
- Агрегация кластеров (Ферн и Бродли) : они применили идею агрегации кластеров к набору мягких кластеризаций, полученных ими с помощью случайных проекций. Они использовали агломеративный алгоритм и не наказывали за слияние разнородных узлов. [10]
- Фред и Джейн : Они предложили использовать один алгоритм связи для объединения нескольких прогонов алгоритма k -средних. [11]
- Дана Кристофор и Дэн Симовичи : Они наблюдали связь между агрегированием кластеров и кластеризацией категориальных данных . Они предложили теоретико-информационные меры расстояния и генетические алгоритмы для поиска наилучшего решения агрегации. [12]
- Топчий и др. : Они определили агрегацию кластеров как задачу оценки максимального правдоподобия и предложили EM-алгоритм для поиска консенсусной кластеризации. [13]
Жесткая ансамблевая кластеризация
[ редактировать ]Этот подход Штреля и Гоша представляет проблему объединения нескольких разделов набора объектов в единую консолидированную кластеризацию без доступа к функциям или алгоритмам, которые определяли эти разделения. Они обсуждают три подхода к решению этой проблемы для получения высококачественных консенсусных функций. Их методы имеют низкие вычислительные затраты, и это позволяет оценить каждый из методов, обсуждаемых ниже, и прийти к лучшему решению путем сравнения результатов с целевой функцией.
Эффективные функции консенсуса
[ редактировать ]- Алгоритм разделения по сходству на основе кластеров (CSPA) . В CSPA сходство между двумя точками данных определяется как прямо пропорциональное количеству составляющих кластеров ансамбля, в котором они сгруппированы вместе. Интуиция заключается в том, что чем более похожи две точки данных, тем выше вероятность того, что составляющие кластеры поместят их в один и тот же кластер. CSPA — простейшая эвристика, но ее вычислительная сложность и сложность хранения квадратичны по n . SC3 является примером алгоритма типа CSPA. [14] Следующие два метода являются менее затратными в вычислительном отношении:
- Алгоритм разделения гиперграфа (HGPA) . Алгоритм HGPA использует совершенно другой подход к поиску консенсусной кластеризации, чем предыдущий метод. Задача кластерного ансамбля формулируется как разбиение гиперграфа путем разрезания минимального числа гиперребер. Они используют hMETIS , систему пакетов разбиения гиперграфов.
- Алгоритм метакластеризации (MCLA) : Алгоритм метакластеризации (MCLA) основан на кластеризации кластеров. Сначала он пытается решить проблему соответствия кластеров, а затем использует голосование для помещения точек данных в окончательные консенсусные кластеры. Проблема соответствия кластеров решается путем группировки кластеров, выделенных в отдельные кластеризации ансамбля. Кластеризация выполняется с использованием METIS и спектральной кластеризации.
Мягкие кластерные ансамбли
[ редактировать ]Пунера и Гош распространили идею ансамблей жесткой кластеризации на сценарий мягкой кластеризации. Каждый экземпляр мягкого ансамбля представлен конкатенацией r апостериорных распределений вероятностей членства, полученных с помощью алгоритмов кластеризации составляющих. Мы можем определить меру расстояния между двумя экземплярами, используя расхождение Кульбака – Лейблера (KL) , которое вычисляет «расстояние» между двумя распределениями вероятностей. [15]
- sCSPA : расширяет CSPA путем вычисления матрицы подобия. Каждый объект визуализируется как точка в многомерном пространстве, где каждое измерение соответствует вероятности его принадлежности к кластеру. Этот метод сначала преобразует объекты в пространство меток, а затем интерпретирует скалярное произведение между векторами, представляющими объекты, как их сходство.
- sMCLA : расширяет MCLA, принимая в качестве входных данных мягкую кластеризацию. Работу sMCLA можно разделить на следующие этапы:
- Постройте мягкий метаграф кластеров
- Сгруппируйте кластеры в метакластеры.
- Свернуть метакластеры с помощью взвешивания
- Соревнуйтесь за объекты
- sHBGF : представляет ансамбль в виде двудольного графа с кластерами и экземплярами в качестве узлов, а также ребрами между экземплярами и кластерами, к которым они принадлежат. [16] Этот подход можно тривиально адаптировать для рассмотрения мягких ансамблей, поскольку алгоритм разделения графа METIS принимает веса на ребрах графа, подлежащего разбиению. В sHBGF граф имеет n + t вершин, где t — общее количество базовых кластеров.
- Байесовская консенсусная кластеризация (BCC) : определяет полностью байесовскую модель для мягкой консенсусной кластеризации, в которой предполагается, что кластеризация с несколькими источниками, определяемая разными входными данными или разными вероятностными моделями, слабо соответствует консенсусной кластеризации. [17] Полная апостериорная информация для отдельных кластеров и консенсусная кластеризация выводятся одновременно с помощью выборки Гиббса .
- Средства фаззификации кластеризации ансамбля (ECF-средства) : ECF-средства — это алгоритм кластеризации, который объединяет в ансамбле различные результаты кластеризации, достигнутые различными запусками выбранного алгоритма ( k-средства ), в единую окончательную конфигурацию кластеризации. [18]
Ссылки
[ редактировать ]- ^ Перейти обратно: а б Штрель, Александр ; Гош, Джойдип (2002). «Кластерные ансамбли — структура повторного использования знаний для объединения нескольких разделов» (PDF) . Журнал исследований машинного обучения (JMLR) . 3 : 583–617. дои : 10.1162/153244303321897735 . S2CID 3068944 .
В этой статье рассматривается проблема объединения нескольких разбиений набора объектов в единую консолидированную кластеризацию без доступа к функциям или алгоритмам, которые определяли эти разбиения. Сначала мы определяем несколько сценариев применения получившейся в результате структуры «повторного использования знаний», которую мы называем кластерными ансамблями. Затем проблема кластерного ансамбля формализуется как задача комбинаторной оптимизации с точки зрения общей взаимной информации.
- ^ ВЕГА-ПОНС, САНДРО; РУИС-ШУЛКЛОПЕР, ХОСЕ (1 мая 2011 г.). «Обзор алгоритмов кластерного ансамбля». Международный журнал распознавания образов и искусственного интеллекта . 25 (3): 337–372. дои : 10.1142/S0218001411008683 . S2CID 4643842 .
- ^ Фильков, Владимир (2003). «Интеграция данных микрочипов путем консенсусной кластеризации». Слушания. 15-я Международная конференция IEEE по инструментам с искусственным интеллектом . стр. 418–426. CiteSeerX 10.1.1.116.8271 . дои : 10.1109/TAI.2003.1250220 . ISBN 978-0-7695-2038-4 . S2CID 1515525 .
- ^ Бониццони, Паола; Делла Ведова, Джанлука; Донди, Риккардо; Цзян, Тао (2008). «О приближении корреляционной кластеризации и консенсусной кластеризации» . Журнал компьютерных и системных наук . 74 (5): 671–696. дои : 10.1016/j.jcss.2007.06.024 .
- ^ Монти, Стефано; Тамайо, Пабло; Месиров, Джилл; Голуб, Тодд (1 июля 2003 г.). «Консенсусная кластеризация: метод на основе повторной выборки для обнаружения классов и визуализации данных микрочипов экспрессии генов» . Машинное обучение . 52 (1): 91–118. дои : 10.1023/А:1023949509487 . ISSN 1573-0565 .
- ^ Перейти обратно: а б с д Шенбабаоглу, Ю.; Михаилидис, Г.; Ли, JZ (2014). «Критические ограничения консенсусной кластеризации при открытии классов» . Научные отчеты . 4 : 6207. Бибкод : 2014NatSR...4E6207. . дои : 10.1038/srep06207 . ПМК 4145288 . ПМИД 25158761 .
- ^ Перейти обратно: а б Шенбабаоглу, Ю.; Михаилидис, Г.; Ли, JZ (февраль 2014 г.). «Переоценка консенсусной кластеризации для открытия классов». биоRxiv 10.1101/002642 .
- ^ Перейти обратно: а б Лю, Юфэн; Хейс, Дэвид Нил; Нобель, Эндрю; Маррон, Дж. С. (1 сентября 2008 г.). «Статистическая значимость кластеризации для крупномерных данных с малым размером выборки». Журнал Американской статистической ассоциации . 103 (483): 1281–1293. дои : 10.1198/016214508000000454 . ISSN 0162-1459 . S2CID 120819441 .
- ^ Тибширани, Роберт; Вальтер, Гюнтер; Хасти, Тревор (2001). «Оценка количества кластеров в наборе данных с помощью статистики разрывов» . Журнал Королевского статистического общества, серия B (статистическая методология) . 63 (2): 411–423. дои : 10.1111/1467-9868.00293 . ISSN 1467-9868 . S2CID 59738652 .
- ^ Папоротник, Сяоли; Бродли, Карла (2004). «Кластерные ансамбли для многомерной кластеризации: эмпирическое исследование» . J Mach Learn Res . 22 .
- ^ Фред, Ана Л.Н.; Джайн, Анил К. (2005). «Объединение нескольких кластеров с использованием накопления доказательств» (PDF) . Транзакции IEEE по анализу шаблонов и машинному интеллекту . 27 (6). Институт инженеров по электротехнике и электронике (IEEE): 835–850. дои : 10.1109/tpami.2005.113 . ISSN 0162-8828 . ПМИД 15943417 . S2CID 10316033 .
- ^ Дана Кристофор, Дэн Симовичи (февраль 2002 г.). «Нахождение медианных разделов с использованием генетических алгоритмов, основанных на теории информации» (PDF) . Журнал универсальной информатики . 8 (2): 153–172. дои : 10.3217/jucs-008-02-0153 .
- ^ Александр Топчий, Анил К. Джайн, Уильям Панч. Кластерные ансамбли: модели консенсуса и слабых разделов . Международная конференция IEEE по интеллектуальному анализу данных, ICDM 03 и Международная конференция SIAM по интеллектуальному анализу данных, SDM 04
- ^ Киселев Владимир Ю; Киршнер, Кристина; Шауб, Майкл Т; Эндрюс, Таллула; Ю, Эндрю; Чандра, Тамир; Натараджан, Кедар Н; Рейк, Вольф; Бараона, Маурисио; Грин, Энтони Р.; Хемберг, Мартин (май 2017 г.). «SC3: консенсусная кластеризация данных секвенирования одноклеточной РНК» . Природные методы . 14 (5): 483–486. дои : 10.1038/nmeth.4236 . ISSN 1548-7091 . ПМК 5410170 . ПМИД 28346451 .
- ^ Кунал Пунера, Джойдип Гош. Ансамбли мягких кластеров, основанные на консенсусе
- ^ Решение проблем кластерного ансамбля путем разделения двудольного графа, Сяоли Чжан Ферн и Карла Бродли , Материалы двадцать первой международной конференции по машинному обучению
- ^ Замок, EF; Дансон, Д.Б. (2013). «Байесовская консенсусная кластеризация» . Биоинформатика . 29 (20): 2610–2616. arXiv : 1302.7280 . Бибкод : 2013arXiv1302.7280L . doi : 10.1093/биоинформатика/btt425 . ПМЦ 3789539 . ПМИД 23990412 .
- ^ Заззаро, Гаэтано; Мартоне, Анджело (2018). «ECF-средства - средства фаззификации ансамблевой кластеризации. Новый алгоритм кластеризации, фаззификации и оптимизации». IMM 2018: Восьмая международная конференция по достижениям в области интеллектуального анализа и управления информацией . [1]
- Аристидес Гионис, Хейкки Маннила , Панайотис Цапарас. Кластерная агрегация . 21-я Международная конференция по инженерии данных (ICDE 2005)
- Хунцзюнь Ван, Ханьхуай Шань, Ариндам Банерджи. Байесовские кластерные ансамбли [ постоянная мертвая ссылка ] , Международная конференция SIAM по интеллектуальному анализу данных, SDM 09
- Нгуен, Нам; Каруана, Рич (2007). «Консенсусные кластеры». Седьмая международная конференция IEEE по интеллектуальному анализу данных (ICDM 2007) . IEEE. стр. 607–612. дои : 10.1109/icdm.2007.73 . ISBN 978-0-7695-3018-5 .
...мы решаем проблему объединения нескольких кластеров без доступа к основным функциям данных. Этот процесс известен в литературе как кластеризация ансамблей, кластеризация или консенсусная кластеризация. Консенсусная кластеризация дает стабильную и надежную окончательную кластеризацию, которая согласуется с множественными кластеризациями. Мы обнаружили, что итерационный метод, подобный EM, чрезвычайно эффективен для решения этой проблемы. Мы представляем итерационный алгоритм и его варианты для поиска консенсуса по кластеризации. В обширном эмпирическом исследовании предложенные нами алгоритмы сравниваются с одиннадцатью другими методами консенсусной кластеризации на четырех наборах данных с использованием трех различных показателей производительности кластеризации. Результаты экспериментов показывают, что новые методы ансамблевой кластеризации создают кластеры, которые не хуже, а часто и лучше, чем другие методы.