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

Кластеризация — это проблема разбиения точек данных на группы на основе их сходства. Корреляционная кластеризация предоставляет метод кластеризации набора объектов в оптимальное количество кластеров без предварительного указания этого количества. ^[1]

Описание проблемы

В машинном обучении корреляционная кластеризация или редактирование кластера работают в сценарии, где известны отношения между объектами, а не фактические представления объектов. Например, если задан взвешенный граф , где вес ребра указывает, являются ли два узла похожими (положительный вес ребра) или разными (отрицательный вес ребра), задача состоит в том, чтобы найти кластеризацию, которая либо максимизирует соглашения (сумма положительных весов ребер внутри кластера плюс абсолютное значение суммы отрицательных весов ребер между кластерами), либо минимизирует разногласия (абсолютное значение суммы отрицательных весов ребер внутри кластера плюс сумма положительных весов ребер по кластерам). В отличие от других алгоритмов кластеризации, здесь не требуется выбирать количество кластеров заранее, поскольку цель — минимизировать сумму весов срезанных ребер — не зависит от количества кластеров. $G=(V,E)$ $к$

Может оказаться невозможным найти идеальную кластеризацию, где все похожие элементы находятся в кластере, а все непохожие — в разных кластерах. Если граф действительно допускает идеальную кластеризацию, то простое удаление всех отрицательных ребер и поиск связанных компонентов в оставшемся графе вернет требуемые кластеры.

Но, в общем случае, граф может не иметь идеальной кластеризации. Например, если заданы узлы a, b, c, такие, что a, b и a, c похожи, а b, c различны, идеальная кластеризация невозможна. В таких случаях задача состоит в том, чтобы найти кластеризацию, которая максимизирует количество соглашений (количество + ребер внутри кластеров плюс количество − ребер между кластерами) или минимизирует количество несогласованностей (количество − ребер внутри кластеров плюс количество + ребер между кластерами). Эта задача максимизации соглашений является NP-полной (задача многоходового разреза сводится к максимизации взвешенных соглашений, а задача разбиения на треугольники ^[2] может быть сведена к невзвешенной версии).

Формальные определения

Пусть будет графом с узлами и ребрами . Кластеризация — это разбиение его множества узлов с и для . Для заданной кластеризации пусть обозначает подмножество ребер, конечные точки которых находятся в различных подмножествах кластеризации . Теперь пусть будет функцией, которая назначает неотрицательный вес каждому ребру графа, и пусть будет разбиением ребер на притягивающие ( ) и отталкивающие ( ) ребра. $G=(V,E)$ $V$ $E$ $G$ $\Pi =\{\pi _{1},\dots,\pi _{k}\}$ $V=\pi _{1}\cup \dots \cup \pi _{k}$ $\pi _{i}\cap \pi _{j} =\emptyset$ $i\neq j$ $\Пи$ $\delta (\Pi)=\{\{u,v\}\in E\mid \{u,v\} \not \subseteq \pi \;\forall \pi \in \Pi \}$ $G$ $\Пи$ $w\двоеточие E\to \mathbb {R} _{\geq 0}$ $E=E^{+}\чашка E^{-}$ $E^{+}$ $E^{-}$

Задача кластеризации корреляции с минимальным расхождением — это следующая задача оптимизации: Здесь набор содержит притягивающие ребра, конечные точки которых находятся в разных компонентах относительно кластеризации , а набор содержит отталкивающие ребра, конечные точки которых находятся в одном и том же компоненте относительно кластеризации . Вместе эти два набора содержат все ребра, которые не согласны с кластеризацией . ${\begin{aligned}&{\underset {\Pi }{\operatorname {minimize} }} &&\sum _{e\in E^{+}\cap \delta (\Pi)}w_{e }+\sum _{e\in E^{-}\setminus \delta (\Pi )}w_{e}\;.\end{aligned}}$ $E^{+}\cap \delta (\Pi)$ $\Пи$ $E^{-}\setminus \delta (\Pi)$ $\Пи$ $\Пи$

Аналогично задаче кластеризации корреляции минимального несогласия задача кластеризации корреляции максимального согласия определяется как Здесь набор содержит притягивающие ребра, конечные точки которых находятся в одном компоненте относительно кластеризации , а набор содержит отталкивающие ребра, конечные точки которых находятся в разных компонентах относительно кластеризации . Вместе эти два набора содержат все ребра, которые согласуются с кластеризацией . ${\begin{aligned}&{\underset {\Pi }{\operatorname {maximize} }}&&\sum _{e\in E^{+}\setminus \delta (\Pi)}w_{e }+\sum _{e\in E^{-}\cap \delta (\Pi )}w_{e}\;.\end{aligned}}$ $E^{+}\setminus \delta (\Pi)$ $\Пи$ $E^{-}\cap \delta (\Pi)$ $\Пи$ $\Пи$

Вместо формулировки проблемы корреляционной кластеризации в терминах неотрицательных весов ребер и разбиения ребер на притягивающие и отталкивающие ребра, проблема также формулируется в терминах положительных и отрицательных стоимостей ребер без явного разбиения множества ребер. Для заданных весов и заданного разбиения ребер на притягивающие и отталкивающие ребра, стоимости ребер могут быть определены как для всех . $w\двоеточие E\to \mathbb {R} _{\geq 0}$ $E=E^{+}\чашка E^{-}$ ${\begin{aligned}c_{e}={\begin{cases}\;\;w_{e}&{\text{if }}e\in E^{+}\\-w_{e}&{\text{if }}e\in E^{-}\end{cases}}\end{aligned}}$ $e\in E$

Ребро, конечные точки которого находятся в разных кластерах, называется разрезом. Набор всех разрезаемых ребер часто называют мультиразрезом ^[3] из . $\delta (\Pi )$ $G$

Задача о минимальной стоимости многоразрезных графов — это задача нахождения кластеризации , при которой сумма стоимостей ребер, конечные точки которых находятся в разных кластерах, минимальна: $\Pi$ $G$ ${\begin{aligned}&{\underset {\Pi }{\operatorname {minimize} }}&&\sum _{e\in \delta (\Pi )}c_{e}\;.\end{aligned}}$

Подобно задаче о минимальной стоимости многоразрезных графов, генерация коалиционной структуры в играх с взвешенными графами ^[4] представляет собой задачу поиска кластеризации, при которой сумма стоимостей ребер, которые не разрезаются, максимальна: Эта формулировка также известна как задача о разделении клик. ^[5] ${\begin{aligned}&{\underset {\Pi }{\operatorname {maximize} }}&&\sum _{e\in E\setminus \delta (\Pi )}c_{e}\;.\end{aligned}}$

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

Алгоритмы

Бансал и др. ^[6] обсуждают доказательство NP-полноты, а также представляют как алгоритм аппроксимации постоянного фактора, так и схему аппроксимации полиномиального времени для поиска кластеров в этой настройке. Эйлон и др. ^[7] предлагают рандомизированный алгоритм 3-аппроксимации для той же проблемы.

CC-Pivot (G=(V,E ⁺ ,E ⁻ )) Выбрать случайный опорный элемент i ∈ V Положим , V'=Ø Для всех j ∈ V, j ≠ i; Если (i,j) ∈ E ^{+ ,}то $C=\{i\}$   Добавить j к C Иначе (Если (i,j) ∈ E ⁻ ) Добавьте j к V' Пусть G' — подграф, индуцированный V' Возврат кластеризации C,CC-Pivot(G')

Авторы показывают, что приведенный выше алгоритм является 3- аппроксимационным алгоритмом для корреляционной кластеризации. Лучший полиномиальный алгоритм аппроксимации, известный на данный момент для этой проблемы, достигает аппроксимации ~2,06 путем округления линейной программы, как показано Чавлой , Макарычевым, Шраммом и Ярославцевым . ^[8]

Карпински и Шуди ^[9] доказали существование полиномиальной схемы аппроксимации времени (PTAS) для этой задачи на полных графах и фиксированном числе кластеров.

Оптимальное количество кластеров

^{В 2011 году Бэгон и Галун [10]} показали , что оптимизация функционала кластеризации корреляции тесно связана с хорошо известными методами дискретной оптимизации . В своей работе они предложили вероятностный анализ базовой неявной модели, которая позволяет функционалу кластеризации корреляции оценивать базовое число кластеров. Этот анализ предполагает, что функционал предполагает равномерное априорное распределение по всем возможным разбиениям независимо от их числа кластеров. Таким образом, возникает неравномерное априорное распределение по числу кластеров.

В этой работе предлагается несколько алгоритмов дискретной оптимизации, которые изящно масштабируются с числом элементов (эксперименты показывают результаты с более чем 100 000 переменных). Работа Бэгона и Галуна также оценивала эффективность восстановления базового числа кластеров в нескольких приложениях.

Корреляционная кластеризация (интеллектуальный анализ данных)

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

Корреляции между подмножествами атрибутов приводят к различным пространственным формам кластеров. Следовательно, сходство между кластерными объектами определяется с учетом локальных корреляционных моделей. С этим понятием термин был введен в ^[11] одновременно с понятием, обсуждаемым выше. Различные методы корреляционной кластеризации этого типа обсуждаются в ^[12] , а связь с различными типами кластеризации обсуждается в. ^[13] См. также Кластеризация многомерных данных .

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

Ссылки

^ Беккер, Хила, «Обзор корреляционной кластеризации», 5 мая 2005 г.
^ Гэри, М.; Джонсон, Д. (2000). Компьютеры и неразрешимость: Руководство по теории NP-полноты . WH Freeman and Company.
^ Деза, М.; Грётшель , М.; Лоран , М. (1992). «Кликово-паутинные грани для многогранников с несколькими разрезами». Математика исследования операций . 17 (4): 981–1000. doi :10.1287/moor.17.4.981.
^ Бахрах, Йорам; Кохли, Пушмит; Колмогоров, Владимир; Задимогхаддам, Мортеза (2013). «Генерация оптимальной коалиционной структуры в кооперативных графовых играх». Труды конференции AAAI по искусственному интеллекту . Том 27. С. 81–87.{{cite conference}}: CS1 maint: multiple names: authors list (link)
^ Грётшель, Г.; Вакабаяши, И. (1989). «Алгоритм плоскости отсечения для задачи кластеризации». Математическое программирование . 45 (1–3): 59–96. doi :10.1007/BF01589097.
^ Бансал, Н.; Блюм, А.; Чавла, С. (2004). «Корреляционная кластеризация». Машинное обучение . 56 (1–3): 89–113. doi : 10.1023/B:MACH.0000033116.57574.95 .
^ Ailon, N.; Charikar, M.; Newman, A. (2005). "Aggregating inconsistent information". Труды тридцать седьмого ежегодного симпозиума ACM по теории вычислений – STOC '05 . стр. 684. doi :10.1145/1060590.1060692. ISBN 1581139608.
^ Чавла, Шучи ; Макарычев, Константин; Шрамм, Целиль; Ярославцев, Григорий . «Почти оптимальный алгоритм LP-округления для корреляционной кластеризации на полных и полных k-дольных графах». Труды 46-го ежегодного симпозиума ACM по теории вычислений .
^ Карпински, М.; Шуди, В. (2009). «Линейные схемы аппроксимации времени для игры Гейла-Берлекэмпа и связанных с ней задач минимизации». Труды 41-го ежегодного симпозиума ACM по Симпозиуму по теории вычислений – STOC '09 . стр. 313. arXiv : 0811.3244 . doi : 10.1145/1536414.1536458. ISBN 9781605585062.
^ Бэгон, С.; Галун, М. (2011) «Оптимизация кластеризации корреляций в больших масштабах» arXiv :1112.2903v1
^ Бём, К.; Кайлинг, К.; Крёгер, П.; Зимек, А. (2004). «Вычислительные кластеры корреляционно-связанных объектов». Труды международной конференции ACM SIGMOD 2004 года по управлению данными – SIGMOD '04 . стр. 455. CiteSeerX 10.1.1.5.1279 . doi :10.1145/1007568.1007620. ISBN 978-1581138597. S2CID 6411037.
^ Зимек, А. (2008). Корреляционная кластеризация (Текст. Кандидатская диссертация). Людвиг-Максимилианс-Мюнхенский университет.
^ Кригель, HP ; Крёгер, П.; Зимек, А. (2009). «Кластеризация многомерных данных». Труды ACM по обнаружению знаний из данных . 3 : 1–58. doi :10.1145/1497577.1497578. S2CID 17363900.