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

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

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

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

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

Но в целом граф может не иметь идеальной кластеризации. Например, если узлы 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$ . Для данной кластеризации $\Pi$ , позволять $\delta (\Pi )=\{\{u,v\}\in E\mid \{u,v\}\not \subseteq \pi \;\forall \pi \in \Pi \}$ обозначим подмножество ребер $G$ чьи конечные точки находятся в разных подмножествах кластеризации $\Pi$ . Теперь позвольте $w\colon E\to \mathbb {R} _{\geq 0}$ — функция, которая присваивает неотрицательный вес каждому ребру графа, и пусть $E=E^{+}\cup 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 )$ содержит притягивающие ребра, концы которых находятся в разных компонентах относительно кластеризации $\Pi$ и набор $E^{-}\setminus \delta (\Pi )$ содержит отталкивающие ребра, конечные точки которых находятся в одном компоненте относительно кластеризации $\Pi$ . Вместе эти два набора содержат все ребра, не соответствующие кластеризации. $\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 )$ содержит привлекательные ребра, конечные точки которых находятся в одном компоненте относительно кластеризации $\Pi$ и набор $E^{-}\cap \delta (\Pi )$ содержит отталкивающие ребра, конечные точки которых находятся в разных компонентах относительно кластеризации $\Pi$ . Вместе эти два набора содержат все ребра, соответствующие кластеризации. $\Pi$ .

Вместо формулировки задачи корреляционной кластеризации в терминах неотрицательных весов ребер и разделения ребер на притягивающие и отталкивающие ребра, проблема также формулируется в терминах положительных и отрицательных стоимостей ребер без явного разделения множества ребер. Для заданных весов $w\colon E\to \mathbb {R} _{\geq 0}$ и данный раздел $E=E^{+}\cup 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$ .

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

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

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

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

Алгоритмы

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

CC-Pivot(G=(V,E⁺,E⁻))
    Pick random pivot i ∈ V
    Set  $C=\{i\}$ , V'=Ø
    For all j ∈ V, j ≠ i;
        If (i,j) ∈ E⁺ then
            Add j to C
        Else (If (i,j) ∈ E⁻)
            Add j to V'
    Let G' be the subgraph induced by V'
    Return clustering C,CC-Pivot(G')

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

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

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

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

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

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

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

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

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

Ссылки

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

[1] Беккер, Хила, «Обзор корреляционной кластеризации», 5 мая 2005 г.

[2] Гари, М.; Джонсон, Д. (2000). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . WH Фриман и компания.

[3] Деза, М .; Гретшель, М .; Лоран, М. (1992). «Фасеты клик-паутины для многоразрезных многогранников». Математика исследования операций . 17 (4): 981–1000. дои : 10.1287/moor.17.4.981 .

[4] Бахрах, Йорам; Кохли, Пушмит; Колмогоров Владимир; Задимогаддам, Мортеза (2013). «Генерация оптимальной коалиционной структуры в кооперативных графовых играх». Материалы конференции AAAI по искусственному интеллекту . Том. 27. С. 81–87. {{cite conference}}: CS1 maint: несколько имен: список авторов ( ссылка )

[5] Гретшель, Г.; Вакабаяши, Ю. (1989). «Алгоритм секущей плоскости для задачи кластеризации». Математическое программирование . 45 (1–3): 59–96. дои : 10.1007/BF01589097 .

[6] Бансал, Н.; Блюм, А.; Чавла, С. (2004). «Корреляционная кластеризация» . Машинное обучение . 56 (1–3): 89–113. дои : 10.1023/B:MACH.0000033116.57574.95 .

[7] Эйлон, Н.; Чарикар, М.; Ньюман, А. (2005). «Агрегация противоречивой информации». Материалы тридцать седьмого ежегодного симпозиума ACM по теории вычислений – STOC '05 . п. 684. дои : 10.1145/1060590.1060692 . ISBN 1581139608 .

[8] Чавла, Сучи ; Макарычев Константин; Шрамм, Целиль; Ярославцев Григорий . «Почти оптимальный алгоритм округления LP для корреляционной кластеризации на полных и полных k-раздельных графах». Материалы 46-го ежегодного симпозиума ACM по теории вычислений .

[9] Карпинский, М.; Шуди, В. (2009). «Схемы аппроксимации линейного времени для игры Гейла-Берлекампа и связанные с ней проблемы минимизации». Материалы 41-го ежегодного симпозиума ACM по теории вычислений – STOC '09 . п. 313. arXiv : 0811.3244 . дои : 10.1145/1536414.1536458 . ISBN 9781605585062 .

[10] Багон, С.; Галун, М. (2011) «Крупномасштабная оптимизация корреляционной кластеризации» arXiv : 1112.2903v1

[11] Бём, К.; Кайлинг, К.; Крегер, П.; Зимек, А. (2004). «Вычисление кластеров корреляционно связанных объектов». Материалы международной конференции ACM SIGMOD 2004 г. по управлению данными – SIGMOD '04 . п. 455. CiteSeerX 10.1.1.5.1279 . дои : 10.1145/1007568.1007620 . ISBN 978-1581138597 . S2CID 6411037 .

[12] Зимек, А. (2008). Корреляционная кластеризация (Текст. Кандидатская диссертация). Мюнхенский университет Людвига-Максимилиана.

[13] Кригель, HP ; Крегер, П.; Зимек, А. (2009). «Кластеризация многомерных данных». Транзакции ACM по извлечению знаний из данных . 3 :1–58. дои : 10.1145/1497577.1497578 . S2CID 17363900 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]