Должны ли мы использовать k-средних ++ вместо k-средних?

Question

Алгоритм k-средних ++ помогает в двух следующих точках оригинального алгоритма k-средних:

1. Оригинальный алгоритм к-средних имеет худшее время выполнения супер-полиномиальный по входному размеру, в то время как k-means ++ объявил O (log k).
2. Найденное приближение может дать не столь удовлетворительный результат в отношении целевой функции по сравнению с оптимальной кластеризацией.

Но есть ли недостатки у k-means ++?Должны ли мы всегда использовать его вместо k-средних?

Answer 1

Никто не утверждает, что k -значений ++ выполняется за O (lg k ) время;качество его решения O (LG K ) - конкурентоспособный с оптимальным решением.И k -средство ++, и общий метод, называемый алгоритмом Ллойда, являются приближениями к проблеме NP-сложной оптимизации.

Я не уверен, какое наихудшее время выполнения k - означает ++ is;обратите внимание, что в оригинальном описании *1015* Артура и Васильвицкого шаги 2-4 алгоритма относятся к алгоритму Ллойда.Они утверждают, что на практике это работает и лучше, и быстрее, потому что начинается с лучшей позиции.

Недостатки k -средств ++, таким образом:

1. Он также может найти неоптимальное решение (это все еще приближение).
2. Это не всегда быстрее, чем алгоритм Ллойда (см. Таблицы Артура и Васильвицкого).
3. Это сложнее, чем алгоритм Ллойда.
4. Это относительно новое, в то время как Lloyd's доказало, что оно стоит более 50 лет.
5. Могут существовать лучшие алгоритмы для определенных метрических пространств.

Тем не менее, если ваш * 1035Библиотека * k -means поддерживает k -means ++, а затем непременно попробуйте.

Answer 2

Не ваш вопрос, но простое ускорение любого метода kmeans для большого N:

1) сначала сделайте k-средства на случайной выборке, скажем, sqrt (N) из точек
2) затем запустите полный k-средних из этих центров.

Я нашел это в 5-10 раз быстрее, чем kmeans ++ для N 10000, k 20, с похожими результатами.
Насколько хорошо это работает для вас, будет зависеть от того, насколько хорошо пример sqrt (N) аппроксимирует целое, а также на N, dim, k, ninit, delta ...

Какие у вас N (количество точек данных), dim (количество функций) и k?
Огромный диапазон пользовательских N, dim, k, шума данных, метрик ... не говоря уже об отсутствии общедоступных тестов, затрудняется сравнение методов.

Добавлено: код Python для kmeans () и kmeanssample () здесь на SO; комментарии приветствуются.