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

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

(Различия между версиями)
Перейти к: навигация, поиск

Volokno (Обсуждение | вклад)
(Новая: == Аннотация == Данная работа посвящена решению задачи кластеризации. Рассматривается задача кластер...)
К следующему изменению →

Версия 11:16, 9 мая 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, будем называть высокой.
Определение. Вероятностный алгоритм, получающий на вход данные оптимизационной задачи и параметр \epsilon>0, который за полиномиальное время с высокой вероятностью получает решение, не более чем в (1+\epsilon) раз превышающее оптимальное, будем называть полиномиальной рандомизированной аппроксимационной схемой (PRAS).
Определение. Если PRAS находит оптимальное решение с высокой вероятностью для любого \epsilon>0, то такой алгоритм будем называть вероятностным алгоритмом типа Монте-Карло.

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

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

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

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

Алгоритм

В состоянии правки

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

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

Исходный код

Литература

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

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

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

Личные инструменты