Кластеризация огромного векторного пространства

Question

Я провожу некоторые тесты, кластеризуя большое количество очень больших разреженных векторов, представляющих частоту-термин-обратная-частота-документ различных гипертекстовых документов. Какой алгоритм вы бы предложили для кластеризации этих данных, принимая во внимание пропорции набора данных? Размерность векторов будет> 3 · 10 ⁵ , а число векторов может быть около 10 ⁹ . Я взглянул на алгоритмы dbscan и оптики. Количество кластеров не известно априорным. И пространственный индекс с такой высокой размерностью кажется сложным.

Answer 1

Я получил почти такие же хорошие результаты с простой кластеризацией K-средних, как и все остальное, и это определенно быстрее, чем большинство альтернатив. Я также получил хорошие результаты с парной агломерацией, но это немного медленнее. Для K-средних вы должны начать с некоторого предполагаемого количества кластеров, но вы можете настроить его алгоритмически по мере продвижения. Если вы найдете два кластера со средствами, которые находятся слишком близко друг к другу, вы уменьшите количество кластеров. Если вы обнаружите кластеры с слишком большим диапазоном вариаций, попробуйте больше кластеров. Я нашел, что sqrt (N) - разумная отправная точка - но я обычно начинаю с 10 ^ 7 документов, а не с 10 ^ 9. Для 10 ^ 9, возможно, имеет смысл несколько уменьшить это.

Однако, если бы это зависело от меня, я бы очень задумался о том, чтобы начать с уменьшения размерности с помощью чего-то вроде Landmark MDS, , а затем , выполняющего кластеризацию.

Answer 2

При кластеризации данных я всегда пробовал бы по крайней мере эти два алгоритма в следующем порядке:

1. K-Means: попробуйте настроить результаты как можно больше. Если вы можете заставить K-Means работать на вас и обеспечивать приличные результаты, вы почти наверняка не добьетесь большего успеха, чем любой другой алгоритм.

2. Максимизация ожиданий: алгоритм K-средних был фактически разработан, чтобы быть дешевой и хорошей альтернативой алгоритму EM. Алгоритм EM более сложен для понимания и более дорог для вычисления, но результаты от EM превосходны. Вы можете узнать больше о EM http://en.wikipedia.org/wiki/Expectation-maximization_algorithm. Существует реализация EM OpenCv: http://opencv.willowgarage.com/documentation/expectation-maximization.html

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

Answer 3

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

В общем, кластеризация в таких пространствах с высокой размерностью затруднена из-за проклятия размерности и того факта, что большинство предметов имеют одинаковые расстояния друг от друга. Стандартные подходы, такие как K-Means, могут сработать, если заранее уменьшить размерность с помощью SOM или PCA.

Answer 4

Деревья решений популярны для эффективной работы в многомерных пространствах. Проверьте Кластеризация с помощью построения дерева решений .

Кроме того, Рандомизированные Леса являются чрезвычайно эффективными учениками, и реализация OpenCV существует , если вы хотите поиграть с ней.