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

Question

Я написал алгоритм k-Means для кластеризации в MATLAB, и я подумал, что попробую его с MATLAB, встроенными в kmeans(X,k).

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

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

Answer 1

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

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

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

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

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

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

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

И добавить x к среднему значению кластера m, используя:

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

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

Если вы действительно стремитесь получить наилучшие возможные локальные минимумы и не возражаете против использования кластеризации на основе примеров, вам следует взглянуть на распространение сродства . Реализации MATLAB доступны на странице распространения аффинности в лаборатории Frey .