1 Свойства и структура алгоритма

Алгоритм k средних (k-means)

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Алгоритм k средних (англ. k-means) - один из алгоритмов машинного обучения, решающий задачу кластеризации. Этот алгоритм является неиерархическим^[1], итерационным методом кластеризации^[2], он получил большую популярность благодаря своей простоте, наглядности реализации и достаточно высокому качеству работы. Был изобретен в 1950-х годах математиком Гуго Штейнгаузом^[3] и почти одновременно Стюартом Ллойдом^[4]. Особую популярность приобрел после публикации работы МакКуина^[5] в 1967.
Алгоритм представляет собой версию EM-алгоритма^[6], применяемого также для разделения смеси гауссиан. Основная идея алгоритма k-means заключается в том, что данные произвольно разбиваются на кластеры, после чего итеративно перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем векторы разбиваются на кластеры вновь в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике.
Цель алгоритма заключается в разделении n наблюдений на k кластеров таким образом, чтобы каждое наблюдение принадлежало ровно одному кластеру, расположенному на наименьшем расстоянии от наблюдения.

1.2 Математическое описание алгоритма

Дано:

• 
  набор из n наблюдений X={x1,x2,...,xn},xi∈Rd, i=1,...,n;
  
• 
  k - требуемое число кластеров, k∈N, k≤n.
  

Требуется:
Разделить множество наблюдений X на k кластеров S1,S2,...,Sk:

• 
  Si∩Sj=∅,i≠j
  

• 
  ⋃ki=1Si=X
  

Действие алгоритма:
Алгоритм k-means разбивает набор X на k наборов S1,S2,...,Sk, таким образом, чтобы минимизировать сумму квадратов расстояний от каждой точки кластера до его центра (центр масс кластера). Введем обозначение, S={S1,S2,...,Sk}. Тогда действие алгоритма k-means равносильно поиску:

argminS∑i=1k∑x∈Siρ(x,μi)2,

(1)

где μi – центры кластеров, i=1,...,k,ρ(x,μi) – функция расстояния между x и μi