Кластеризация графов без использования метрик (пример)

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(→Литература)
(→Исходный код)
Строка 76: Строка 76:
== Исходный код ==
== Исходный код ==
 +
[https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/kargerClustering/ SourceForge, kargerClustering]
== Литература ==
== Литература ==

Версия 04:13, 24 мая 2011

Содержание

Аннотация

Данная работа посвящена решению задачи кластеризации. Рассматривается задача кластеризации на графах, на которых не задана метрика. Подобная задача может встретиться, например, при анализе групп знакомств в социальных сетях. Для ее решения предлагается использовать вероятностный алгоритм построения дендрограммы.

Постановка задачи

Пусть задан граф G(V,E,w): \; |V|=n, \; |E|=m (V – множество вершин графа, E – множество ребер, w:E\rightarrow\mathbb{R}^+ – весовая функция) и целое число k.

Задача кластеризации заключается в поиске разбиения V на k непересекающихся подмножеств (V=\{V_1,\dots,V_k\}), с минимизацией заданного функционала f(G). В качестве такого функционала будем рассматривать сумму весов ребер между подмножествами, т.е.

f(G)=\sum_{i=1}^{k-1} \sum_{j=i+1}^k \sum_{\substack{v_1\in V_i \\ v_2\in V_j}} w(\{v_1,v_2\})\rightarrow\min

Введем ряд определений, которыми будем пользоваться в дальнейшем.
Определение. Вероятность, превышающую 1-\frac1n, будем называть высокой.
Определение. Вероятностный алгоритм, получающий на вход данные оптимизационной задачи и параметр \varepsilon>0, который за полиномиальное время с высокой вероятностью получает решение, не более чем в (1+\varepsilon) раз превышающее оптимальное, будем называть полиномиальной рандомизированной аппроксимационной схемой (PRAS).
Определение. Если PRAS находит оптимальное решение с высокой вероятностью для любого \varepsilon>0, то такой алгоритм будем называть вероятностным алгоритмом типа Монте-Карло.

В дальнейшем граф G будем считать связным, а веса ребер – единичными. Несколько слов о модификации алгоритма для решения задачи в случае взвешенного графа будет сказано в следующем разделе.

Первое условие не накладывает никаких дополнительных ограничений, поскольку в случае несвязного графа можно каждую отдельную компоненту связности рассматривать в качестве одного из кластеров.

Второе условие возникает из конструкции алгоритма и приводит к тому, что минимизируемый функционал f(G) будет представлять собой число ребер между кластерами. Для того чтобы рассмотреть задачу в более общем случае потребуется дерандомизация исследуемого алгоритма, что приведет к возрастанию его трудоемкости.

Заметим, что рассматривается задача с заранее заданным число кластеров. Подбор оптимального значения числа k можно в дальнейшем осуществить простым перебором.

Алгоритм

В качестве алгоритма для кластеризации предлагается использовать вероятностный алгоритм типа Монте-Карло, придуманный Каргером в работе [] для решения задачи минимального k-разреза.

Введем дополнительную процедуру, для описания данного алгоритма. Эта процедура представляет собой построение дендрограммы до заранее заданного уровня.

Слияние (G,m)
Вход: граф G, число m.
Выход: гиперграф G.
Процесс:
Пока |V_G | \geq m
Выбирается произвольное ребро (u,v) \in E_G
G \leftarrow G/\{u,v\}
Вернуть G.

Здесь и далее граф задается симметричной матрицей инцидентности, и все операции слияния вершин реализованы как работа со строками и столбцами этой матрицы. Функционал f(G) тогда равен половине суммы всех недиагональных элементов матрицы. Собственно алгоритм описывается следующим образом:

Алгоритм Каргера
Вход: граф G, число k, число r - количество итераций алгоритма.
Выход: k-разрез G.
Процесс: Инициализация: i=1.
Повторять пока i \leq r
Слияние (G,k)
i=i+1
Из получившихся дендрограмм выбираем \min_i C_i

Здесь во внутреннем цикле (процедура Слияние) происходит построение дендрограммы. Поскольку алгоритм сливает вершины совершенно произвольно, то мы не можем гарантировать нахождение оптимального решения. Однако можно оценить вероятность этого.

P(succeed)=P(C_i=C_{opt})\geq\frac1{\binom{n+k-2}{2k-2}}

Внешний цикл представляет собой процедуру вероятностной амплификации. Повторив внутренний цикл r раз мы получим, что

P(succeed) \geq 1 - (1-\frac1{С_{n+k-2^{2k-2}}})^r,

откуда для r=\binom{n+k-2}{2k-2} \ln n выполнено P(succeed) \geq 1-\frac1n.
Получаем, что поскольку r=n^{2k-2} \ln n, трудоемкость алгоритма составляет O(rn^2)=O(n^{2k} \log n).


Так как каждый внешний цикл алгоритма выполняется независимо от остальных, алгоритм Каргера можно модифицировать и уменьшить время его работы, используя параллельные вычисления. Если задействовать n^{2k-2} \ln n процессоров и выполнить на каждом из них по одному вычислению внешнего цикла алгоритма, то трудоемкость такого распределенного алгоритма будет O(n^2). Таким образом, в зависимости от существующих мощностей можно подобрать оптимальное соотношение между количеством используемых процессоров и трудоемкостью получающейся задачи.

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

Вычислительный эксперимент

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

Исходный код

SourceForge, kargerClustering

Литература

Данная статья является непроверенным учебным заданием.
Студент: Козлов Илья
Преподаватель: В.В.Стрижов
Срок: 9 мая 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

  • Karger D. Global min-cuts in RNC and other ramifications of a simple mincut algorithm // Proc. of the 4-th ACM-SIAM Symp. on Discrete Algorithms. – 1993. – P. 21-30.
  • Karger D., Stein C. A new approach to the minimum cut problem // JACM, 43. – 1996. – P. 601-640.
  • Kumar V., Tan P., Steinbach M. Introduction to Data Mining. – Addison-Wesley, 2005. – 769 pp.
  • Nagamochi H., Ibaraki T. Computing edge connectivity in multigraphs and capacitated graphs // SIAM J. Disc. Math., 5. – 1992. – P. 54-66.
Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2_%D0%B1%D0%B5%D0%B7_%D0%B8%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D0%BA_%28%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80%29»