MATLAB kMeans не всегда сходится к глобальным минимумам

Question

Я написал алгоритм k-Means clustering в MATLAB, и я решил попробовать его против MATLABs, построенного в kmeans(X,k).

Однако, для очень простой установки четырех кластеров (см. Рисунок), MATLAB kMeans не всегда сходится к оптимальному решению (слева), но (справа).

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

Answer 1

Как объясняется @Alexandre C., алгоритм K-средних зависит от начальных позиций центроида кластера, и нет гарантии, что он будет сходиться к оптимальному решению.

Лучшее, что вы можете сделать, это повторить эксперимент несколько раз со случайными начальными точками.

Реализация MATLAB предлагает такую ​​опцию: replicates, которая повторяет кластеризацию N раз и выбирает ту, которая имеет самое низкое общее внутри кластерное расстояние между центрами. Вы также можете контролировать, как исходные центроиды выбираются с помощью опции start.

Кроме того, MATLAB обеспечивает выбор среди ряда дистанционных мер (Евклидов, Манхэттен, Косинус, ...). Один опциональный вариант emptyaction позволяет вам контролировать, что происходит, когда кластер теряет все назначенные ему члены во время итераций.

Но реальное преимущество заключается в том, что он использует двухфазный алгоритм: обычные итерации с назначением-повторной выдачей, а затем фазу онлайн-обновления. Обязательно прочитайте раздел алгоритма documentation page для получения дополнительной информации.

Answer 2

K-означает алгоритм весьма чувствителен к начальной догадке для кластерных центров. Вы попробовали оба кода с такими же начальными центрами масс?

Алгоритм прост, и я сомневаюсь, что существует много различий между вашей реализацией и Matlab's.

Answer 3

Вы, вероятно, часто будете разочарованы решением, которое прибегает к любому конкретному запуску «алгоритма k-средних» (то есть алгоритма Ллойда). Это потому, что алгоритм Ллойда часто застревает в плохих локальных минимумах.

К счастью, Ллойд - это всего лишь один из способов решения k-средств. И есть подход, который почти всегда находит лучшие локальные минимумы.

Хитрость заключается в обновлении кластерных присвоений точек данных по одному. Вы можете сделать это эффективно, сохранив подсчет количества очков n, присвоенных каждому среднему значению. Так что вы можете повторно вычислить кластер значит m после удаления точки x следующим образом:

m_new = (n * m - x)/(n - 1) 

И добавить x кластера среднее m с помощью:

m_new = (n * m + x)/(n + 1) 

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

Если вы действительно заинтересованы в получении максимально возможных местных минимумов, и вы не возражаете против использования кластеризации на основе экземпляров, вы должны посмотреть на affinity propagation. Реализации MATLAB доступны на Frey lab affinity propagation page.

Answer 4

Хотя K-Means++ не решит проблему за один проход, она имеет тенденцию давать лучшие результаты, когда она выполняется N раз (по сравнению с запуском оригинального алгоритма K-Средств N раз).

Answer 5

Я бы не назвал это легкой проблемой. На самом деле статья Википедии о кластеризации «k-mean» дает довольно мрачную картину сложности вычислений.

Если вы хотите быть свободным от случайных перезапусков (зависимость от исходного предположения), компромисс - это алгоритм «глобальных k-средств»; бумагу и код MATLAB можно найти здесь: http://lear.inrialpes.fr/~verbeek/software.php