Существуют ли алгоритмы, которые могут помочь в иерархической кластеризации? Google-сокращение карты имеет только пример k-кластеризации. В случае иерархической кластеризации я не уверен, как можно разделить работу между узлами. Другим ресурсом, который я нашел, является: http://issues.apache.org/jira/browse/MAHOUT-19 Но не очевидно, какие алгоритмы используются.Распределенная иерархическая кластеризация
Во-первых, вы должны решить, если вы собираетесь строить свою иерархию снизу вверх или сверху вниз.
Нижняя часть называется иерархической агломеративной кластеризацией. Вот простой, хорошо документированный алгоритм: http://nlp.stanford.edu/IR-book/html/htmledition/hierarchical-agglomerative-clustering-1.html.
Распределение алгоритма снизу вверх сложно, потому что для каждого распределенного процесса требуется весь набор данных для выбора подходящих кластеров. Он также нуждается в списке кластеров на своем текущем уровне, поэтому он не добавляет точку данных к нескольким кластерам на одном уровне.
Конструкция иерархии сверху вниз называется Divisive clustering. K-means - это один из способов решить, как разделить узлы вашей иерархии. В настоящем документе рассматривается K-средство и основное разделение разделов (PDDP) для разделения узлов: http://scgroup.hpclab.ceid.upatras.gr/faculty/stratis/Papers/tm07book.pdf. В итоге вам просто нужно разделить каждый родительский узел на относительно сбалансированные дочерние узлы.
Подложку сверху вниз проще распределить. После разделения вашего первого узла каждый созданный узел может быть отправлен в распределенный процесс, который будет снова разделен и так далее ... Каждый распределенный процесс должен знать только о подмножестве набора данных, который он разделяет. Только родительский процесс знает полный набор данных.
Кроме того, каждый раскол может выполняться параллельно.Два примера К-средства:
Вы можете посмотреть на некоторые из работ, выполняемых с помощью самоорганизующихся карт (метод нейронной сети Кохонена) ... ребята в Vienna University of Technology проделали определенную работу по распределенному вычислению их растущего иерархического алгоритма карты.
Это немного на крае вашего кластерного вопроса, поэтому он не может помочь, но я не могу думать ни о чем более тесном;)
Кларк Олсон рассматривает несколько распределенных алгоритмов иерархической кластеризации:
CF Olson. «Параллельные алгоритмы для Иерархическая кластеризация». Parallel , 21: 1313-1325, 1995, doi:10.1016/0167-8191(95)00017-I.
Parunak et al. Описан алгоритм вдохновленный, как муравьи сортировать свои гнезда:
H. Van Dyke Parunak, Ричард Ровер, Теодор С. Belding, и Свен Брюкнер: "децентрализованные Any-Time Иерархическая кластеризация" В Proc. 4-й Международный семинар по инженерной самоорганизующихся систем (ESOA), 2006, doi:10.1007/978-3-540-69868-5
Отъезд этот очень читаемый, если бит от review by Olson (1995). Большинство документов с тех пор требуют платы за доступ. :-)
Если вы используете R, я рекомендую попробовать pvclust, который достигает параллелизма, используя snow, еще один модуль R.
Вы можете увидеть также Finding and evaluating community structure in networks от Newman и Girvan, где они предлагают aproach для оценки сообществ в сетях (и набор алгоритмов на основе этого подхода) и измерение деления сети на качество сообществ (модульность графа).
Знаете ли вы о распределенной иерархической агломерационной кластеризации? – Nullpoet 2012-07-18 19:07:30