Этапы алгоритма K-средних:
1-Введите количество кластеров (k) и примеры обучающего набора.
2-Случайная инициализация k центроидов кластера.
3-Для фиксированных центроидов кластера назначьте каждый пример обучения ближайшим центрам.
4-Обновление центров для назначенных точек
5- Повторяйте 3 и 4 до схождения.
Определение функции стоимости:
После каждой итерации мы получаем k центроидов с назначением обучающих примеров соответствующим кластерам. Таким образом, наша целевая функция определяется как сумма евклидова расстояния каждого обучающего примера с его центром кластера, и это суммируется по k кластерам. Мы можем написать это так:
Минимизация функции затрат:
Минимизация функции стоимости зависит от двух шагов итераций. После каждой полной итерации наша цель — продолжать минимизировать функцию стоимости.
Шаг А:
Первый шаг — выбор оптимального назначения переменной a для фиксированных центров (µ1,µ2...,µk).
Чтобы минимизировать общее евклидово расстояние для фиксированных центров, мы выберем a = 1 для каждого обучающего примера, который находится ближе всего к определенному центру кластера.
Этого можно достичь, используя приведенные ниже уравнения:
Шаг Б:
Это включает в себя поиск оптимальных центров (µ) для фиксированного назначения точек (т.е. для фиксированного а). Для этого случая мы устанавливаем градиент по отношению к µ как 0 для фиксированного a.
Шаг 1:
Это можно рассматривать как суммирование по k кластерам. Итак, когда мы находим производное по отношению к определенному кластеру. Мы можем записать функцию стоимости как:
Производная по j-му кластеру:
Шаг 2:
Расширяя термин евклидовой нормы, мы можем написать так:
Шаг 3.
Теперь, взяв градиент, мы приходим к следующим уравнениям:
Шаг 4:
Итак, для точек, назначенных j-му кластеру, мы знаем, что aij=1. Итак, мы получаем:
Шаг 5.
На этом шаге мы проверим, что это конкретное значение соответствует минимуму функции стоимости, а не максимуму. Для доказательства этого мы докажем, что гессиан является PSD или PD, тогда это будет соответствующий минимум для функции стоимости. Итак, теперь давайте найдем матрицу Хессейна-
Давайте думать о центрах кластеров как о векторе-столбце, указанном ниже:
Полученный градиент относительно некоторого j-го центра был равен
Теперь, вычислив второй градиент относительно j, мы придем к тому, что все диагональные элементы матрицы Гессе и все недиагональные элементы будут равны 0.
Таким образом, все диагональные элементы матрицы Гессе будут иметь этот вид для каждого j от 1 до k. Мы можем видеть, что суммирование по a дает количество точек, принадлежащих определенному кластеру j (т.е. nj)
Это доказывает, что все диагональные элементы будут больше 0. Следовательно, у этой матрицы все собственные значения будут положительными. Следовательно, это будет положительно определенная матрица. Отсюда можно сказать, что значение соответствует минимуму.
Вывод:
Мы видим, что это простое вычислительное упражнение подтверждает тот факт, что значение µ, которое дает нам функцию минимальной стоимости, равно среднему значению обучающих примеров, принадлежащих этому кластеру. Целью этой статьи было обосновать интуицию, которой мы следуем, чтобы математически минимизировать функцию стоимости.
Спасибо за просмотр статьи.
