MaxMax

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

Применение

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

Ссылки

• MaxMax на GitHub

См. также

• Chinese Whispers
• TextRank
• Watset