MaxMax

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

MaxMax — непараметрический алгоритм кластеризации взвешенных графов, позволяющий одной вершине входить в один или несколько кластеров.[1]

Применение

Алгоритм MaxMax предназначен для вывода значений слов на основе графа их попарной близости.

Алгоритм

Вход: взвешенный граф G=(V, E).

Инициализация:

   G' \gets (V, E'), где G' — ориентированный граф, E' \gets \emptyset
   
   (\forall v \in V) \textit{root}(v) \gets \textit{true}

Алгоритм:

   for (u, v, w) \in E
   
       E' \gets E' \cup (v, u) \iff \max_{(u, v', w')} w' = w
       
       E' \gets E' \cup (u, v) \iff \max_{(u', v, w')} w' = w
   
   for v \in V
   
       if \textit{root}(v) = \textit{true}
       
           for v' \in \textit{descendants}(G', v) \setminus v
           
               \textit{root}(v') \gets \textit{false}

Выход: ориентированный граф G', содержащий кластеры в вершинах v \in V: \textit{root}(v) = \textit{true}.

Сложность и время работы

Общее время выполнения алгоритма MaxMax составляет O(|E|), где E — множество вершин исходного графа.

Реализация

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

Ссылки

См. также

Примечания

  1. D. Hope, B. Keller (2013), MaxMax: A Graph-Based Soft Clustering Algorithm Applied to Word Sense Induction