Велоспорт в алгоритме k-средних

9

Согласно вики, наиболее широко используемый критерий конвергенции - «назначение не изменилось». Мне было интересно, может ли ехать на велосипеде, если мы используем такой критерий сходимости? Я был бы рад, если бы кто-то указал ссылку на статью, которая приводит пример езды на велосипеде или доказывает, что это невозможно.

clustering algorithms k-means Томек Тарчинский
источник
2
Позвольте мне подчеркнуть (поскольку это часто упускается из виду), что для доказательства сходимости требуется (квадрат) евклидово расстояние , чтобы функция расстояния и функция среднего значения оптимизировали один и тот же критерий. Если вы используете другое расстояние (на самом деле вы должны использовать не расстояние, а «наименьшую сумму квадратов»), вы можете потерять сходимость в k-средних.
Выйти - Anony-Mousse

Ответы:

7

Эта статья доказывает сходимость за конечное число шагов.

Саймон Бирн
источник
1
Именно то, что я искал!
Томек Тарчинский
4

К- означает, что целевая функция строго уменьшается с каждым изменением присвоения, что автоматически подразумевает сходимость без цикличности. Кроме того, разделы производятся на каждом этапеК-средства удовлетворяют «свойству Вороного» в том, что каждая точка всегда присваивается своему ближайшему центру. Это подразумевает верхнюю границу общего числа возможных разделов, которая дает конечную верхнюю границу времени завершения дляК-средства.

Суреш Венкатасубраманян
источник
Спасибо, интуитивно понятно, что целевая функция уменьшается, но я не был уверен, что она строго уменьшается. Я хотел убедиться, что нет патологического случая, как в линейном программировании
Томек Тарчинский,
Ну да и нет. Хотя это сходится, это может занять экспоненциальное время, так же, как и симплекс. Более того, для обеих задач можно показать, что «сглаженные» варианты сходятся за полиномиальное время
Суреш Венкатасубраманян
2

В конечной точности может появиться езда на велосипеде.

Езда на велосипеде частая с одинарной точностью, исключительная с двойной точностью.

Когда значение близко к локальному минимуму, целевая функция может иногда немного увеличиваться из-за ошибок округления. Это часто безвредно, поскольку функция алгоритма снова уменьшается и в конечном итоге достигает локального минимума. Но иногда алгоритм переходит к ранее посещенному назначению и запускает цикл.

Легко и безопасно наблюдать за циклами в реальных реализациях критериев остановки.

Франсуа Пэйс
источник