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

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

---

Версия 11:16, 9 мая 2011

Содержание 1 Аннотация 2 Постановка задачи 3 Алгоритм 4 Вычислительный эксперимент 5 Исходный код 6 Литература

Аннотация

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

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

Пусть задан граф ( – множество вершин графа, – множество ребер, – весовая функция) и целое число .

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

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

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

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

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

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

Алгоритм

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

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

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

Исходный код

Литература

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