K-средства против онлайн K-средства

K-средних - это хорошо известный алгоритм кластеризации, но есть также онлайн-вариант такого алгоритма (онлайн-K-средства). Каковы плюсы и минусы этих подходов и когда следует отдавать предпочтение каждому из них?

K-средства онлайн (более известные как последовательные k-средства ) и традиционные k-средства очень похожи. Разница в том, что онлайн-средство k-средних позволяет обновлять модель по мере получения новых данных.

K-средства онлайн должны использоваться, когда вы ожидаете, что данные будут получены один за другим (или, возможно, порциями). Это позволяет вам обновлять модель по мере получения дополнительной информации о ней. Недостаток этого метода заключается в том, что он зависит от порядка, в котором получены данные ( ссылка ).

Оригинальная публикация MacQueen k-means (первая, которая использовала название «kmeans») - это онлайн-алгоритм.

MacQueen, JB (1967). «Некоторые методы классификации и анализа многомерных наблюдений». Материалы 5-го Симпозиума по Беркли по математической статистике и вероятности 1. Университет Калифорнии Пресс. С. 281–297

После назначения каждой точки среднее значение постепенно обновляется с использованием простой формулы средневзвешенного значения (старое среднее значение взвешивается с n, новое наблюдение взвешивается с 1, если среднее значение имело n наблюдений ранее).

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

MacQueen обычно требует меньше итераций, чем Lloyds, чтобы сойтись, если ваши данные перемешаны (потому что это обновляет среднее значение быстрее!). На заказанных данных могут возникнуть проблемы. С другой стороны, он требует больше вычислений для каждого объекта, поэтому каждая итерация занимает немного больше времени (очевидно, дополнительные математические операции).