MaxMax

Материал из NLPub
Перейти к: навигация, поиск

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 — слова в кластере, разделённые запятой с пробелом. В качестве разделителя полей используется табуляция.

Ссылки

См. также

Примечания