Распределенная иерархическая кластеризация

Question

Существуют ли алгоритмы, которые могут помочь с иерархической кластеризацией? Google Map-Reduce имеет только пример k-кластеризации. В случае иерархической кластеризации я не уверен, как можно разделить работу между узлами. Другой ресурс, который я нашел: http://issues.apache.org/jira/browse/MAHOUT-19 Но неясно, какие алгоритмы используются.

Answer 1

Во-первых, вы должны решить, собираетесь ли вы строить свою иерархию снизу вверх или сверху вниз.

Внизу называется Иерархическая агломерационная кластеризация. Вот простой, хорошо документированный алгоритм: http://nlp.stanford.edu/IR-book/html/htmledition/hierarchical-agglomerative-clustering-1.html.

Распространение алгоритма «снизу вверх» сложно, поскольку каждому распределенному процессу необходим весь набор данных для выбора подходящих кластеров. Ему также нужен список кластеров на его текущем уровне, поэтому он не добавляет точку данных более чем в один кластер на одном уровне.

Построение иерархии сверху вниз называется Разделительная кластеризация . K-означает - это один из вариантов, чтобы решить, как разделить узлы вашей иерархии. В этой статье рассматриваются разделение K-средних и деление главного направления (PDDP) для разделения узлов: http://scgroup.hpclab.ceid.upatras.gr/faculty/stratis/Papers/tm07book.pdf. В конце вам просто нужно разделить каждый родительский узел на относительно хорошо сбалансированные дочерние узлы.

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

Кроме того, каждое разделение может выполняться параллельно. Два примера для k-средних:

• http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.1882&rep=rep1&type=pdf
• http://www.ece.northwestern.edu/~wkliao/Kmeans/index.html.

Answer 2

Проверьте это очень читабельное, если немного устарело обзор Olson (1995) . Большинство газет с тех пор требуют плату за доступ. : -)

Если вы используете R, я рекомендую попробовать pvclust , который достигает параллелизма, используя snow , другой модуль R.

Answer 3

Кларк Олсон рассматривает несколько распределенных алгоритмов иерархической кластеризации:

C. Ф. Олсон. «Параллельные алгоритмы для Иерархическая кластеризация. " Параллель Computing , 21: 1313-1325, 1995, doi: 10.1016 / 0167-8191 (95) 00017-I .

Parunak et al. опишите алгоритм, основанный на том, как муравьи сортируют свои гнезда:

H. Ван Дайк Парунак, Ричард Ровер, Теодор С. Белдинг и Свен Брюкнер: «Динамичный децентрализованный Иерархическая кластеризация в любое время ". В Proc. 4-й международный семинар по инженерным самоорганизующимся системам (ESOA) , 2006, doi: 10.1007 / 978-3-540-69868-5

Answer 4

Вы также можете увидеть Поиск и оценку структуры сообщества в сетях Ньюмана и Гирвана, где они предлагают подход для оценки сообществ в сетях (и набор алгоритмов, основанных на этом подходе) и меру разделения сети в качество сообществ (модульность графа).

Answer 5

Вы можете посмотреть на некоторые работы, выполняемые с помощью самоорганизующихся карт (метод нейронной сети Кохонена) ... ребята из Венского технического университета проделали некоторую работу по распределенному вычислению их роста алгоритм иерархической карты.

Это немного на грани вашего вопроса о кластеризации, так что это может не помочь, но я не могу придумать ничего более подходящего;)