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

Question

Существуют ли какие-либо алгоритмы, которые могут помочь с иерархической кластеризацией?Map-Reduce от Google содержит только пример 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

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

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

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

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

Answer 3

Посмотрите это очень читабельно, хотя и немного устаревшее обзор Олсона (1995).С тех пор доступ к большинству статей требует платы.:-)

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

Answer 4

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

Answer 5

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

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