Я читал, что алгоритм k-средних сходится только к локальному минимуму, а не к глобальному минимуму. Почему это? Я могу логически подумать о том, как инициализация может повлиять на окончательную кластеризацию, и есть вероятность неоптимальной кластеризации, но я не нашел ничего, что математически доказало бы это.
Кроме того, почему k-означает итеративный процесс? Разве мы не можем просто частично дифференцировать целевую функцию по центроидам, приравнять ее к нулю, чтобы найти центроиды, которые минимизируют эту функцию? Почему мы должны использовать градиентный спуск, чтобы шаг за шагом достичь минимума?
clustering
k-means
convergence
gradient-descent
minimum
Пратик Кулкарни
источник
источник
Ответы:
Вы можете рассматривать k-means как специальную версию алгоритма EM, которая может немного помочь.
Допустим , вы оценки многомерного нормального распределения для каждого кластера с ковариационной матрицей , прикрепленного к единичной матрице для всех, но переменная среднее , где я есть индекс кластера. Очевидно, что если параметры { μ i } известны, вы можете назначить каждой точке p свой кластер максимального правдоподобия (т. Е. Μ i, для которого расстояние до pμя я { μя} п μя п минимально). EM-алгоритм для этой задачи почти эквивалентен k-средних.
С другой стороны, если вы знаете, какие точки принадлежат к какому кластеру, вы можете оценить оптимальный . Замкнутая форма решения этого (что находит глобальный оптимум) в основном говорит , что найти модели по методу максимального правдоподобия { μ яμя { μ^я} вы проинтегрировать все возможные задания точек для кластеров. Поскольку даже с тридцатью точками и двумя кластерами существует около миллиарда таких возможных назначений, это невозможно рассчитать.
Вместо этого мы можем сделать некоторые предположения относительно скрытых параметров (или параметров модели) и повторить два шага (с возможностью оказаться в локальном максимуме). Если вы позволите каждому кластеру взять на себя частичную ответственность за точку, вы получите EM, если вы просто назначите оптимальный кластер, вы получите k-средних.
Итак, резюме: в вероятностных терминах существует глобальное решение, но оно требует от вас перебора всех возможных кластеризаций. Очевидно, что если у вас есть объективная функция, то же самое верно. Вы можете перебирать все решения и максимизировать целевую функцию, но количество итераций экспоненциально зависит от размера ваших данных.
источник
Это проблема, которую вы хотите решить:
Двоичная переменная указывает, назначена ли точка i кластеру j . Символы p i и c j обозначают координаты i- й точки и центроида j- го кластера соответственно. Они оба расположены в R d , где d - размерность точек данных.xij i j pi cj i j Rd d
Первая группа ограничений говорит, что каждая точка должна быть назначена ровно одному кластеру. Вторая группа ограничений (которые мы не определили математически) говорят, что координаты центроида кластера самом деле зависят от значений переменных x i j . Мы можем, например, выразить это ограничение следующим образом: c j = ∑ i x i j p i jj xij
Однако вместо того, чтобы иметь дело с этими нелинейными ограничениями, в K-средстве мы (приблизительно) решаем другую задачу, которая имеет такое же оптимальное решение, как и наша исходная задача:
Вместо того чтобы минимизировать расстояние до центроидов, мы минимизируем расстояние до любого набора точек, который даст лучшее решение. Оказывается, что эти точки - точно центроиды.
Теперь, чтобы решить эту проблему, мы повторяем шаги 2-3 этого алгоритма до сходимости:
На каждом шаге целевая функция улучшается (или остается неизменной, когда алгоритм сходится), поскольку решение, найденное на предыдущем шаге, находится в пространстве поиска текущего шага. Однако, поскольку мы фиксируем некоторые переменные на каждом шаге, это локальная процедура поиска, которая не гарантирует оптимальность.
источник
Простой пример может помочь ..
Давайте определим набор точек, которые будут сгруппированы как
A = {1,2,3,4}
.Скажем, вы пытаетесь найти 2 подходящих кластера для A (2-средних). Существуют (как минимум) две разные настройки, которые удовлетворяют стационарному состоянию k-средних.
Настройка 1:
Здесь цель 2. На самом деле это седло (попробуйте
center1 = 1 + epsilon
иcenter1 = 1 - epsilon
)Настройка 1:
здесь цель 1/4.
Если k-means будет инициализировано в качестве первого параметра, то оно застрянет ... и это ни в коем случае не глобальный минимум.
Вы можете использовать вариант предыдущего примера для создания двух разных локальных минимумов. Для
A = {1,2,3,4,5}
настройкиcluster1={1,2}
иcluster2={3,4,5}
приведет к тому же объективному значению, чтоcluster1={1,2,3}
иcluster2={4,5}
Наконец, что произойдет, если вы выберете
против
?
источник
[Это было до того, как @Peter ответил]
После небольшого обсуждения (в разделе комментариев) я чувствую, что должен ответить на свой вопрос.
Я считаю, что когда я частично дифференцирую целевую функцию по одному центроиду, точки в скоплении другого центроида исчезают в производной. Таким образом, центроид, который мы можем получить, минимизирует только сумму квадратов расстояний только определенного кластера.
@whuber добавляет:
Было бы здорово, если бы кто-нибудь еще мог добавить.
источник
Все все объяснили, но я хотел бы добавить, что если выборочные данные не распространяются как распределение Гаусса, то они могут привязываться к локальным минимумам. В алгоритме K-средних мы на самом деле пытаемся это получить.
источник