Иерархическая кластеризация 1 миллиона объектов

Может ли кто-нибудь указать мне на иерархический инструмент кластеризации (предпочтительнее в python), который может кластеризовать ~ 1 миллион объектов? Я пробовал hcluster, а также Orange.

hcluster имел проблемы с объектами 18k. Оранжевый смог скрыть 18 тыс. Объектов за считанные секунды, но не смог с 100 тыс. Объектов (насыщенная память и в конечном итоге разбилась).

Я работаю на 64-битном процессоре Xeon (2,53 ГГц) и 8 ГБ оперативной памяти + 3 ГБ на Ubuntu 11.10.

Ответы

Ответ 1

Чтобы победить O (n ^ 2), вам нужно сначала уменьшить свои 1M очки (документы) например, 1000 сваи по 1000 пунктов каждая или 100 кусков по 10 тыс. Каждый, или... Два возможных подхода:

  • построить иерархическое дерево из 15k точек, а затем добавить остальные по одному: время ~ 1M * treedepth

  • сначала создайте 100 или 1000 плоских кластеров, затем создайте свое иерархическое дерево из 100 или 1000 кластерных центров.

Насколько хорошо любой из них может работать, критически по размеру и форме вашего целевого дерева - сколько уровней, сколько листьев?
Какое программное обеспечение вы используете, и сколько часов/дней вам нужно выполнить кластеризацию?

Для подхода с плоскими кластерами, K-d_tree s отлично работает для очков в 2d, 3d, 20d, даже 128d - не ваш случай. Я почти ничего не знаю о кластеризации текста; Locality-sensitive_hashing?

Взгляните на scikit-learn кластеризация - он имеет несколько методов, включая DBSCAN.

Добавлено: см. также
google-all-pairs-similarity-search "Алгоритмы поиска всех подобных пар векторов в разреженных векторных данных", Beyardo et al. 2007
SO иерархическая-кластеризация-эвристика

Ответ 2

Вероятно, проблема состоит в том, что они попытаются вычислить полную 2D-матрицу расстояний (примерно 8 ГБ наивно с двойной точностью), и тогда их алгоритм будет работать в O(n^3) в любом случае.

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

Если вы действительно хотите продолжить иерархическую кластеризацию, я верю, что ELKI (Java хотя) имеет реализацию O(n^2) SLINK. Что на 1 миллион объектов должно быть примерно в 1 миллион раз быстрее. Я не знаю, есть ли у них уже CLINK. И я не уверен, существует ли какой-либо алгоритм sub O(n^3) для других вариантов, чем однострочный и полный канал.

Рассмотрим использование других алгоритмов. k-средства, например, очень хорошо масштабируются с количеством объектов (это просто не очень хорошо, как правило, либо, если ваши данные не являются очень чистыми и регулярными). DBSCAN и OPTICS неплохо, на мой взгляд, когда вы почувствуете параметры. Если ваш набор данных является маломерным, их можно значительно ускорить с соответствующей структурой индекса. Затем они должны выполняться в O(n log n), если у вас есть индекс с запросом времени O(log n). Что может иметь огромное значение для больших наборов данных. Я лично использовал OPTICS в наборе данных 110k без проблем, поэтому могу представить, что он масштабируется до 1 миллиона в вашей системе.