Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Описание проблемы [ править ]

Основная статья: Кластерный анализ

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

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

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

Алгоритмы [ править ]

Bansal et al. [3] обсуждают доказательство NP-полноты, а также представляют как алгоритм аппроксимации с постоянным коэффициентом, так и схему аппроксимации за полиномиальное время, чтобы найти кластеры в этой настройке. Ailon et al. [4] предлагают рандомизированный 3- приближенный алгоритм для той же задачи.

CC-точка поворота (G = (V, E + , E - )) Выбрать случайную точку опоры i ∈ V Установить , V '= Ø Для всех j ∈ V, j ≠ i; Если (i, j) ∈ E +, то Добавить j в C Иначе (Если (i, j) ∈ E - ) Добавить j к V ' Пусть G '- подграф, индуцированный V' Возврат кластеризации C, CC-Pivot (G ')

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

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

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

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

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

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

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

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

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

Ссылки [ править ]

  1. ↑ Беккер, Хила, «Обзор корреляционной кластеризации», 5 мая 2005 г.
  2. ^ Garey, М. и Джонсон, D (WH Freeman и Company). (2000). Компьютеры и непоколебимость: руководство по теории NP-полноты .CS1 maint: несколько имен: список авторов ( ссылка )
  3. ^ Bansal, N .; Blum, A .; Чавла, С. (2004). «Корреляционная кластеризация» . Машинное обучение . 56 (1–3): 89–113. DOI : 10,1023 / Б: MACH.0000033116.57574.95 .
  4. ^ Ailon, N .; Charikar, M .; Ньюман, А. (2005). «Агрегирование противоречивой информации». Материалы тридцать седьмого ежегодного симпозиума ACM по теории вычислений - STOC '05 . п. 684. DOI : 10,1145 / 1060590,1060692 . ISBN 1581139608.
  5. ^ Чавла, Шучи ; Макарычев, Константин; Шрамм, Целил; Ярославцев, Григорий . «Почти оптимальный алгоритм округления LP для корреляционной кластеризации на полных и полных k-долевых графах». Материалы 46-го ежегодного симпозиума ACM по теории вычислений .
  6. ^ Карпинский, М .; Шуди, В. (2009). «Схема линейной аппроксимации времени для игры Гейла-Берлекампа и связанных с ней задач минимизации». Материалы 41-го ежегодного симпозиума ACM по теории вычислений - STOC '09 . п. 313. arXiv : 0811.3244 . DOI : 10.1145 / 1536414.1536458 . ISBN 9781605585062.
  7. ^ Багон, S .; Галун, М. (2011) «Оптимизация крупномасштабной корреляционной кластеризации» arXiv : [https://arxiv.org/abs/1112.2903v1 1112.2903v1]
  8. ^ Böhm, C .; Kailing, K .; Kröger, P .; Зимек, А. (2004). «Вычислительные кластеры корреляционно связанных объектов». Материалы международной конференции ACM SIGMOD 2004 по управлению данными - SIGMOD '04 . п. 455. CiteSeerX 10.1.1.5.1279 . DOI : 10.1145 / 1007568.1007620 . ISBN  978-1581138597.
  9. ^ Zimek, A. (2008). «Корреляционная кластеризация» . Cite journal requires |journal= (help)
  10. ^ Kriegel, HP ; Kröger, P .; Зимек, А. (2009). «Кластеризация многомерных данных». ACM-транзакции при обнаружении знаний из данных . 3 : 1–58. DOI : 10.1145 / 1497577.1497578 .