MaxMax
MaxMax — непараметрический алгоритм кластеризации взвешенных графов, позволяющий одной вершине входить в один или несколько кластеров.[1]
Содержание
Применение
Алгоритм MaxMax предназначен для вывода значений слов на основе графа их попарной близости.
Алгоритм
Вход: взвешенный граф .
Инициализация:
, где — ориентированный граф,
Алгоритм:
for for if for
Выход: ориентированный граф , содержащий кластеры в вершинах .
Сложность и время работы
Общее время выполнения алгоритма MaxMax составляет , где — множество вершин исходного графа.
Реализация
Реализация алгоритма на языке Java доступна на GitHub. Перед использованием нужно скачать её и скомпилировать.
$ git clone https://github.com/dustalov/maxmax.git $ cd maxmax $ mvn package
Исходный граф представляется в виде текстового файла, содержащего список рёбер, каждая строка которого записана формате i j weight
, где i
и j
— вершины, weight
— вес ребра. Поля разделяются пробельным табуляцией. Для запуска алгоритма достаточно вызвать скомпилированную программу для заданного входного файла input.txt
и выходного файла output.txt
(он будет создан автоматически).
$ java -jar target/maxmax.jar -in input.txt -out output.txt
Формат выходного файла близок к формату аналогичной операции Chinese Whispers: i n words
, где i
— порядковый номер кластера, n
— количество слов в нём, words
— слова в кластере, разделённые запятой с пробелом. В качестве разделителя полей используется табуляция.
Ссылки
См. также
Примечания
- ↑ D. Hope, B. Keller (2013), MaxMax: A Graph-Based Soft Clustering Algorithm Applied to Word Sense Induction