Кластеризация графов без использования метрик (пример)
Материал из MachineLearning.
Содержание |
Аннотация
Данная работа посвящена решению задачи кластеризации. Рассматривается задача кластеризации на графах, на которых не задана метрика. Подобная задача может встретиться, например, при анализе групп знакомств в социальных сетях. Для ее решения предлагается использовать вероятностный алгоритм построения дендрограммы.
Постановка задачи
Пусть задан граф (
– множество вершин графа,
– множество ребер,
– весовая функция) и целое число
.
Задача кластеризации заключается в поиске разбиения на
непересекающихся подмножеств (
), с минимизацией заданного функционала
. В качестве такого функционала будем рассматривать сумму весов ребер между подмножествами, т.е.
Введем ряд определений, которыми будем пользоваться в дальнейшем.
Определение. Вероятность, превышающую , будем называть высокой.
Определение. Вероятностный алгоритм, получающий на вход данные оптимизационной задачи и параметр , который за полиномиальное время с высокой вероятностью получает решение, не более чем в
раз превышающее оптимальное, будем называть полиномиальной рандомизированной аппроксимационной схемой (PRAS).
Определение. Если PRAS находит оптимальное решение с высокой вероятностью для любого , то такой алгоритм будем называть вероятностным алгоритмом типа Монте-Карло.
В дальнейшем граф будем считать связным, а веса ребер – единичными. Несколько слов о модификации алгоритма для решения задачи в случае взвешенного графа будет сказано в следующем разделе.
Первое условие не накладывает никаких дополнительных ограничений, поскольку в случае несвязного графа можно каждую отдельную компоненту связности рассматривать в качестве одного из кластеров.
Второе условие возникает из конструкции алгоритма и приводит к тому, что минимизируемый функционал будет представлять собой число ребер между кластерами. Для того чтобы рассмотреть задачу в более общем случае потребуется дерандомизация исследуемого алгоритма, что приведет к возрастанию его трудоемкости.
Заметим, что рассматривается задача с заранее заданным число кластеров. Подбор оптимального значения числа можно в дальнейшем осуществить простым перебором.
Алгоритм
В состоянии правки
Вычислительный эксперимент
Вычислительный эксперимент будет проведен на ряде модельных графов. Представлены графы с различным числом вершин, результаты кластеризации данных графов, полученные рассматриваемым алгоритмом, и получены графики зависимости времени работы и качества работы алгоритма от числа вершин в графе.
Исходный код
Литература
| Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
