Chinese Whispers

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

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

Применение

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

Алгоритм

Вход: граф .

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

Алгоритм:

   while метки  изменяются
   
       for  в случайном порядке
       
            наибольшее значение  среди соседей 

Выход: номера кластеров .

Реализация

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

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

Исходный граф представляется в виде текстового файла, содержащего список рёбер, каждая строка которого записана формате i j weight, где i и j — вершины, weight — вес ребра. Поля разделяются пробельным символом, например, табуляцией. Из-за особенностей реализации, для каждого ребра должно также передаваться ребро , чтобы программа корректно работала с неориентированным графом. Кроме того, файл должен быть отсортирован, например, при помощи 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

Ссылки

См. также

Примечания