Я знаю, что k-средних обычно оптимизируется с использованием максимизации ожиданий . Однако мы можем оптимизировать его функцию потерь так же, как мы оптимизируем любую другую!
Я нашел несколько работ, которые на самом деле используют стохастический градиентный спуск для больших k-средних, но я не смог получить ответ на свой вопрос.
Итак, кто-нибудь знает, почему это? Это потому, что ожидание максимизации сходится быстрее ? Есть ли какая-то конкретная гарантия? Или это историческая причина ?
Ответы:
Как упоминается в OP, можно решить k-средних с использованием градиентного спуска, и это может быть полезно в случае крупномасштабных задач.
Существуют, безусловно, исторические причины преобладания алгоритмов в стиле EM для решения k-средних (то есть алгоритма Ллойда). Алгоритм Ллойда настолько популярен, что люди иногда называют его «алгоритмом k-средних» и даже могут не знать, что существуют другие подходы. Но эта популярность не является незаслуженной.
Bottou и Bengio (1995) показали, что алгоритм Ллойда эквивалентен оптимизации функции стоимости k-средних с использованием метода Ньютона. В общих задачах оптимизации методы второго порядка, такие как метод Ньютона, могут сходиться быстрее, чем методы первого порядка, такие как градиентный спуск, поскольку они используют информацию о кривизне целевой функции (а методы первого порядка - нет). В эксперименте с известным набором данных Iris они показали, что алгоритм Ллойда действительно сходился быстрее градиентного спуска. Было бы интересно увидеть это сравнение на более широком наборе данных.
Ссылки:
Ботту и Бенжио (1995) . Свойства сходимости алгоритмов k-средних.
источник
Кластеризация K-средних не контролируется, а ближайшим неконтролируемым методом, в котором используется EM, является кластеризация на основе моделей (модели гауссовой смеси, GMM). Раздражающая проблема с кластеризацией на основе модели GMM возникает, когда многие особенности коррелированы, что вызывает почти сингулярность в ковариационной (корреляционной) матрице признаков. В этой ситуации функция правдоподобия становится нестабильной, а индексы условий достигают бесконечности, что приводит к полному отказу GMM.
Таким образом, отбросьте идею EM и kNN - поскольку она основана на ковариационных (корреляционных) матрицах для неконтролируемого анализа. Ваш запрос на оптимизацию очень напоминает отображение Саммона и классическое метрическое и неметрическое многомерное масштабирование (MDS). Отображение Саммона основано на производных итерациях, в то время как различные формы MDS обычно являются итеративными или одношаговыми собственными разложениями, которые, тем не менее, можно оптимизировать во время одношаговой операции матрицы.
Еще раз оглядываясь на ваш запрос: ответ: это уже было сделано в картографии Саммона.
источник