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

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

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

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

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

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

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

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

Если ни один из этих двух результатов не дал удовлетворительных результатов,

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

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