Кластеризация десятков миллионов многомерных данных - PullRequest
3 голосов
/ 15 сентября 2011

У меня есть набор из 50 миллионов фрагментов текста, и я хотел бы создать из них несколько кластеров.Размерность может быть где-то между 60k-100k.Средняя длина фрагмента текста будет 16 слов.Как вы можете себе представить, частотная матрица была бы довольно разреженной.Я ищу программный пакет / libray / sdk, который позволил бы мне найти эти кластеры.Я пробовал CLUTO в прошлом, но это кажется очень сложной задачей для CLUTO.Из моих онлайн-исследований я обнаружил, что BIRCH - это алгоритм, который может справиться с такими проблемами, но, к сожалению, я не смог найти в Интернете никакого программного обеспечения для реализации BIRCH (я нашел только пару специальных реализаций, таких как проекты заданий, в которых не было ни одноговроде документации вообще).Есть предложения?

Ответы [ 4 ]

3 голосов
/ 17 января 2015

Вас может заинтересовать алгоритм потокового EM-дерева, который использует представление TopSig. Оба они из моей кандидатской диссертации. Диссертация на тему крупномасштабной кластеризации документов.

Недавно мы сгруппировали 733 миллиона документов на одном 16-ядерном компьютере (http://ktree.sf.net).. Потребовалось около 2,5 дней для индексации документов и 15 часов для их кластеризации.

Алгоритм потокового EM-дерева можно найти в https://github.com/cmdevries/LMW-tree. Он работает с двоичными векторами документов, созданными TopSig, которые можно найти в http://topsig.googlecode.com.

Ранее я писал в блоге об аналогичном подходе http://chris.de -vries.id.au / 2013/07 / large-scale-document-clustering.html . Однако дерево EM лучше масштабируется для параллельного выполнения, а также создает кластеры лучшего качества.

Если у вас есть какие-либо вопросы, свяжитесь со мной по адресу chris@de-vries.id.au.

.
1 голос
/ 08 марта 2014

Мой профессор сделал реализацию алгоритма BIRCH в Java. Легко читать с некоторыми встроенными комментариями.

0 голосов
/ 20 декабря 2012

Полагаю, вы ищете что-то вроде all-pair search.

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

Я только что нашел реализацию BIRCH в C ++ .

0 голосов
/ 18 декабря 2011

Попробуйте с алгоритмом разбиения графа.Это может помочь вам сделать возможной кластеризацию на многомерных данных

...