Существуют ли алгоритмы, которые могут помочь в иерархической кластеризации? Google map-reduce имеет только пример k-кластеризации. В случае иерархической кластеризации я не уверен, как можно разделить работу между узлами. Другим ресурсом, который я нашел, является: http://issues.apache.org/jira/browse/MAHOUT-19 Но это не очевидно, какие алгоритмы используются.
Распределенная иерархическая кластеризация
Ответ 1
Во-первых, вам нужно решить, будете ли вы строить свою иерархию снизу вверх или сверху вниз.
Нижняя сторона называется иерархической агломеративной кластеризацией. Вот простой, хорошо документированный алгоритм: http://nlp.stanford.edu/IR-book/html/htmledition/hierarchical-agglomerative-clustering-1.html.
Распределение алгоритма "снизу вверх" сложно, потому что каждому распределенному процессу требуется весь набор данных для выбора подходящих кластеров. Он также нуждается в списке кластеров на текущем уровне, поэтому он не добавляет точку данных к нескольким кластерам на одном уровне.
Конструкция иерархии сверху вниз называется Делительная кластеризация. K-mean - это один из способов решить, как разделить ваши узлы иерархии. В настоящем документе рассматривается раздел K-средства и разделение на разделение разделов (PDDP) для разделения node: http://scgroup.hpclab.ceid.upatras.gr/faculty/stratis/Papers/tm07book.pdf. В итоге вам просто нужно разделить каждого родителя node на относительно сбалансированные дочерние узлы.
Подпроцесс "сверху вниз" легче распространять. После первого разделения node каждый созданный node может быть отправлен в распределенный процесс, который будет снова разделен и т.д. Каждый распределенный процесс должен знать только о подмножестве набора данных, который он разделяет. Только родительский процесс знает полный набор данных.
Кроме того, каждый раскол может выполняться параллельно. Два примера для k-средних:
Ответ 2
Кларк Олсон рассматривает несколько распределенных алгоритмов иерархической кластеризации:С. Ф. Олсон. "Параллельные алгоритмы для Иерархическая кластеризация". Параллельный Вычисление, 21:1313-1325, 1995, doi: 10.1016/0167-8191 (95) 00017-I.
Parunak et al. описать алгоритм, основанный на том, как муравьи сортируют свои гнезда:
Н. Ван Дайк Парунак, Ричард Рохер, Теодор К. Бельдинг и Свен Брюкнер: "Динамический децентрализованный Иерархическая кластеризация в любое время." Proc. 4-й Международный семинар по инженерным самоорганизующимся системам (ESOA), 2006, doi: 10.1007/978-3-540-69868-5
Ответ 3
Отметьте это очень читабельным, если немного устарел обзор Olson (1995). Большинство документов с тех пор требуют платы за доступ.: -)
Если вы используете R, я рекомендую попробовать pvclust, который достигает parallelism, используя snow, еще один R-модуль.
Ответ 4
Вы также можете увидеть Поиск и оценка структуры сообщества в сетях Newman и Girvan, где они предлагают aproach для оценки сообществ в сетях (и набор алгоритмов на основе этого подхода) и показатель деления сети на качество сообществ (графовая модульность).
Ответ 5
Вы можете посмотреть на некоторые из работ, выполняемых с самоорганизующимися картами (метод нейронной сети Кохонена)... ребята в Венский технологический университет проделали определенную работу по распределенному вычислению их растущего иерархического алгоритма карты.
Это немного на краю вашего вопроса о кластеризации, так что это может не помочь, но я не могу придумать ничего ближе;)