Кластеризация K-средних

Кластеризация K-средних

Теоретическая основа

Здравствуйте!!.. и добро пожаловать в этот блог о кластеризации K-средних. До сих пор мы обсуждали несколько методов обучения с учителем, а теперь впервые обсудим алгоритм обучения без учителя. K-means — один из самых простых алгоритмов обучения без учителя. Он предлагает простой способ сгруппировать заданный набор данных в определенное количество взаимосвязанных подмножеств, называемых кластерами. Давайте сначала обсудим некоторые основы.

Контролируемое и неконтролируемое обучение

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

С другой стороны, неконтролируемое обучение работает с немаркированными данными и пытается обнаружить естественные подгруппы или кластеры в предоставленных данных на основе некоторой формы сходства. Например, есть случайный набор шаров. Один из способов разделить их на подгруппы может быть основан на их размерах, скажем, на малые, средние и большие. Другой способ их категоризации может быть основан на их цвете, скажем, красном, синем и зеленом. Кто-то другой может захотеть классифицировать их на основе их материала, веса и так далее. Все это действительные кластеры, основанные на той или иной форме сходства. В этой задаче точные категории, ожидаемые на выходе, заранее не определены, и именно так работает неконтролируемое обучение.

Можно сказать гораздо больше, чтобы описать контролируемое и неконтролируемое обучение. Однако это не основная цель этого блога. Чтобы узнать больше, загляните здесь или в любом из множества информационных ресурсов по этой теме.

Алгоритм К-средних

K-means – это простой алгоритм обучения без учителя, который разбивает набор данных на K кластеров в многомерном пространстве таким образом, чтобы евклидово расстояние между точками внутри кластера было меньше, чем евклидово расстояние между точками в кластерах. . Алгоритм принимает на вход:

• Набор данных X, из N точек данных, где каждая точка лежит в D-мерном пространстве.
• K количество кластеров

K-means использует среднее (также известное как центроид) значение μ каждого кластера для представления этого кластера. Кроме того, rnk — это индикаторная переменная для каждой точки, указывающая на принадлежность этой точки данных к кластеру k.

Среднее значение μ и индикаторная переменная r являются результатом процесса кластеризации. Следовательно, целевая функция процесса кластеризации может быть записана как:

Приведенная выше целевая функция представляет собой сумму квадратов расстояний от каждой точки данных до центра ее кластера. Цель состоит в том, чтобы минимизировать значение J с помощью кластеризации K-средних.

Актуальность индикаторной переменной rnk заключается в том, что она гарантирует, что для каждой точки данных J оценивается только относительно. правильный кластер (r будет равен 0 по отношению ко всем остальным кластерам для nй точки данных).

Алгоритм K-средних работает над поиском этих μk и rnk итеративным способом. Каждая итерация алгоритма K-средних включает 2 ключевых шага:

Шаг 1. Исправьте μk. Найдите rnk, который минимизирует J. Это называется E-шаг и присваивает rn к ближайшему µ такому, что J минимизируется.

Шаг 2. Это называется M-шаг. Предположим, что rnk, определенный на предыдущем шаге E, фиксирован. Теперь найдите µk, которое минимизирует J. J является квадратичной функцией µk. Для оптимизации возьмем производную от J по w.r.t. μk и установите для него значение 0. Это дает —

Здесь вы видите, что числитель — это сумма всех точек в кластере, а знаменатель — это количество точек в кластере. Алгоритм K-средних можно записать следующим образом:

Initialize μk[where k = 1, 2, 3,.., K]
Repeat:
    E-step as described above
    M-step as described above
Until convergence of μk.

Сходимость алгоритма K-средних

Шаги E и M каждой итерации оптимизируют целевую функцию J. Мы останавливаем выполнение, когда —

• Достигнут максимальный заданный предел количества итераций ИЛИ..
• J больше не изменяется, или изменения J больше не являются значительными. В таком случае говорят, что алгоритм сошелся

С каждой итерацией каждый объект назначается своему ближайшему центроиду кластера. После назначения всех объектов центроиды K обновляются. При этом центроиды приближаются к набору объектов, которые уже были их собственными, тем самым еще больше уменьшая расстояние каждой точки от ее центроида. Поэтому каждая итерация является улучшением, и достигается минимум — локальный или глобальный, в зависимости от первоначального выбора центроидов. Значение целевой функции не увеличивается на последующих итерациях.

Выбор начальных центроидов

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

Рассмотрим следующий пример:

На приведенном ниже рисунке у нас есть набор синих точек с левой стороны и набор красных точек с правой стороны. Рассмотрим K = 2, где µ1 и µ2 представлены зелеными точками посередине. С этими значениями μ членство в кластере оценивается на этапе E.

На следующей итерации центроиды μ1 и μ2 корректируются и перемещаются вниз и вверх к центру фигуры. При этом движении средства приближаются к своему набору объектов, и это уменьшает значение Целевой функции J. Дальнейшее изменение принадлежности точек данных не происходит. За несколько таких итераций алгоритм сойдется к минимумам, но это не будут глобальные минимумы. Алгоритм, скорее всего, сойдётся к глобальному минимуму, если начальные значения центроидов выбираются из пространства данных синих и красных точек данных. Это означает, что выбор начальных значений центроидов влияет на тип сходимости и количество шагов, необходимых для сходимости алгоритма.

Несколько дополнительных моментов, на которые следует обратить внимание.

• Он чрезвычайно чувствителен к шуму и выбросам
• Поскольку K-means использует меру на основе расстояния для определения сходства, рекомендуется стандартизировать данные (среднее значение нуля и стандартное отклонение, равное единице) перед применением алгоритма.
• Как видно из приведенного выше примера, разные инициализации могут привести к разным кластерам, поскольку алгоритм K-средних может застрять в локальных минимумах, а не сходиться к глобальным минимумам. Поэтому рекомендуется запускать алгоритм с использованием различных инициализаций центроидов и выбирать результаты запуска, которые дали наименьшее значение целевой функции.
• Оптимальное значение числа кластеров K получается с использованием метода локтя, как показано ранее в K ближайших соседей классификаторе, т. е. с использованием точки поворота кривой целевой функции J в зависимости от количества кластеров

На этом мы завершаем обсуждение теории кластеризации K-средних. Надеюсь, вам понравилось учиться!