Разбиение наборов векторов на заданное число кластеров

Алгоритм разбиения на заданное число кластеров (К-средних)

Метрика расстояния

Формула

fl-.-xl 1=1

max(x, - у, )

(*-y)/(HHWI)

Евклидова

Манхеттен (City Block)

Шахматная доска

Мера косинуса

Рассматривается задача идентификации кластеров векторов {x₁,...,x,_v} в многомерном пространстве с Евклидовой мерой расстояния ||..||. Цель состоит в разбиении этого набора на заданное число К кластеров. С интуитивной точки зрения кластер может представляться как группа векторов, расстояние между которыми меньше, чем расстояние до векторов за пределами кластера. Это может быть формализовано, посредством введения набора = 1,АГ -центров кластеров. Тогда цель состоит в назначении векторов кластерам, так что сумма квадратов расстояний векторов до векторов = ,К является минимальной. Для каждого вектора х_; вводится бинарная индикаторная переменная r_ik е {0,1},? = ,К , описывающая, какому из К кластеров назначен вектор х, (если вектор х_; назначен кластеру к то r_jk - 1, и к. = 0 для / # к). Целевая функция имеет вид

•^,=ЕЕ^11^Х<-НЛ² • (5-1)

/=1 *=i

Минимизация J (5.1) может быть выполнена посредством итеративной процедуры, в которой каждая итерация включает два последовательных шага, соответствующих последовательной оптимизации по отношению к r_ik,i = 1,TV,к = 1,К и ц,,к = 1,К . В качестве исходных значений для ц_к,к = 1,К выбираются некоторые вектора из {xj,...,x_w}. Затем на первом шаге J (5.1) минимизируется относительно r_ik,i - l,N,k - ,К при фиксированном i_k,k = i,K . На втором шаге J минимизируется относительно = 1, К при фиксированном r_ik,i = ,N,k = 1, К. Эта двух шаговая процедура оптимизации повторяется до достижения сходимости.

Более формально, на первом шаге нулю приравнивается производная по r_ik,i - ,N,k - ,К

,k =argmin||x. -|ij|

(5.2)

О, в противном случае

На втором шаге нулю приравнивается производная по ц_к,к = ,К

?л(х,.-ц₄) = О (5.3)

j=l

В результате

/ N

/Тл (⁵-4)

Знаменатель (5.4) равен числу точек, назначенных кластеру к, так что результат (5.4) имеет простую интерпретацию, а именно, щ равно среднему всех точек х,, назначенных кластеру к. Два шага переназначения точек кластерам и повторного вычисления средних по кластерам повторяются до тех пор, пока происходит изменение назначений (или пока нс превышено максимальное число итераций). Каждый шаг уменьшает целевую функцию J (5.1), поэтому сходимость алгоритма гарантируется. Однако он может сходиться к локальному, а не к глобальному минимуму J.