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

Question

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

Answer 1

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

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

Answer 2

Деревья принятия решений популярны для эффективной работы в высокоразмерных пространствах. Проверьте Clustering Via Decision Tree Construction.

Кроме того, Randomized Forests являются чрезвычайно эффективными учащимися и OpenCV implementation exists, если вы хотите поиграть с ним.

Answer 3

Я слышал, что semantic hashing достигает отличных результатов. Однако глубокие сети убеждений довольно практичны. Возможно, вы захотите попробовать минутное хеширование (это вероятностный подход) или locality sensistive hashing for euclidean spaces.

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

Answer 4

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

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

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

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