Улучшено ускорение кластеризации K-средних (критерий Уорда)
Я использую кластеризацию k-средних со случайной инициализацией для идентификации кластеров. Алгоритм хорошо работает для хороших данных. Но если я работаю с данными с большим количеством шумов, то мой алгоритм k-средних теряет устойчивость и дает разные решения для каждого запуска одного и того же набора данных.
Поэтому я решил улучшить свою кластеризацию k-средних, чтобы минимизировать критерий Уорда:
- У стандартной кластеризации k-средних
- Пройдите через точки и все кластеры и найдите точку P и кластеры A и B, так что если бы я переместил точку P из кластера A в кластер B, тогда критерий Уорда для этой кластеризации будет минимальным
- Если такая точка найдена, переместите ее с A на B, обновите центры кластеров и продолжайте с 2
Я написал этот алгоритм на с ++ Вот. Однако проблема в том, что этот подход чрезвычайно медленный, я имею дело с кластерами с примерно 20 000 точек на каждый.
Можете ли вы предложить мне лучшее решение, или вы могли бы помочь мне ускорить этот алгоритм?
Решение
Я наконец нашел решение. Я понял, что:
- Мой подход с Уордом был действительно бесполезным
- PCA был непригоден для меня, потому что я работаю только с 1D кластерами.
- После того, как я реализовал k-means ++, как сказал Мика, надежность k-means была улучшена. Тем не менее, иногда это все еще давало плохие решения. (экспериментально 1 из 5 кластеров по одним и тем же данным была плохой)
Что определенно помогло мне Средняя нормализация. Я сделал 5x k-средних, рассчитанное среднее для центров кластеров от каждой итерации. И, наконец, запустите k-средних с вычисленными средствами в качестве начального решения.
Другие решения