Chinese Whispers

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

Chinese Whispers (рус. испорченный телефон) — алгоритм кластеризации графов, построенный на принципах одноимённой детской игры.[1]

Применение

Алгоритм применяется в задачах вывода значений слов без учителя на основе графов близости слов. Кроме того, метод применяется для поиска сообществ в социальных графах.

Алгоритм

Вход: граф G=(V, E).

Инициализация: (\forall v_i \in V) \textit{class}(v_i) \gets i.

Алгоритм:

   while метки \textit{class}(\cdot) изменяются
   
       for v \in V в случайном порядке
       
           \textit{class}(v) \gets наибольшее значение \textit{class}(\cdot) среди соседей v

Выход: номера кластеров \textit{class}(\cdot).

Реализация

Реализация алгоритма на языке Java доступна на GitHub. Перед использованием нужно скачать её и скомпилировать.

$ git clone https://github.com/tudarmstadt-lt/chinese-whispers.git
$ cd chinese-whispers
$ mvn package

Исходный граф представляется в виде текстового файла, содержащего список рёбер, каждая строка которого записана формате i j weight, где i и j — вершины, weight — вес ребра. Поля разделяются пробельным символом, например, табуляцией. Из-за особенностей реализации, для каждого ребра (x, y) должно также передаваться ребро (y, x), чтобы программа корректно работала с неориентированным графом. Кроме того, файл должен быть отсортирован, например, при помощи sort -u.

Для запуска алгоритма на данных необходимо воспользоваться классом de.tudarmstadt.lt.cw.global.CWGlobal. Программа поддерживает как текстовые данные, так и данные, сжатые архиватором gzip.

$ java -Xms4G -Xmx4G -cp target/chinese-whispers.jar de.tudarmstadt.lt.cw.global.CWGlobal -N 200 -in input.txt -out output.txt
- [input.txt] Starting to process... (162 bytes total)
Reading input graph...
- [input.txt] Processed 100.0%


Running CW sense clustering...
found 2 clusters

Ссылки

См. также

Примечания

  1. C. Biemann (2006), Chinese Whispers - an Efficient Graph Clustering Algorithm and its Application to Natural Language Processing Problems