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

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

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

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

источник

2012-02-06 user940154

Ваши очки в 2d, 3d, 10d, 128d? – denis

@Denis Я не понимаю, что вы подразумеваете под этим. AS, такое ограничение, по-видимому, связано с тем, что матрица расстояний nxn для объектов 1M не может быть помещена в память, и каждая из библиотек кластеризации, о которых я говорил выше (оранжевый и scipy), принимает матрицу расстояний в памяти в качестве входных данных (что не является возможно предоставить в качестве входных данных для объектов 1M ...) – user940154

точки/объекты - это простые текстовые файлы, которые я пытаюсь скопировать на основе текста, который они содержат .... можете ли вы также объяснить мне, является ли это 2d или что? Благодарю. – user940154

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

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

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

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

Посмотрите на scikit-learn clustering - он имеет несколько методов, включая DBSCAN.

Добавлено: смотрите также
google-all-pairs-similarity-search «Алгоритмы для нахождения всех подобных пар векторов в разреженных векторных данных», Beyardo и др эл. 2007
SO hierarchical-clusterization-heuristics

источник

2012-02-27 14:22:32 denis

Я не думаю, что существует общий способ победить иерархию кластеров 'O (n^2)' для *. Вы можете сделать некоторые вещи для конкретного случая одиночной ссылки (см. Мой ответ), и, конечно, вы можете использовать * другие * алгоритмы (например, 'DBSCAN'). Это гораздо более разумно для этих больших данных в любом случае, чем * иерархическая кластеризация *. Обратите внимание, что 'scikit-learn' 'DBSCAN'' O (n^2) ', так как AFAIK не использует индексы. –

On O (n^2): если вы принимаете более высокие частоты ошибок, вы можете выбрать (мое первое тривиальное предложение) или LSH. Есть много [документы о быстрой кластеризации] (http://scholar.google.de/scholar?as_q=fast-clustering&btnG=Search+Scholar&as_occt=title) некоторые из них только для записи. О иерархической кластеризации, я согласен, , но было бы неплохо, если бы ОП сказал, насколько большое дерево он хочет, и почему. – denis

Проблема в том, что они попытаются вычислить полную 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 миллиона в вашей системе.

источник

2012-02-06 08:59:00

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

ответ

Смежные вопросы