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

Шаги алгоритма:

1. 
   Начальный шаг: инициализация кластеров
   

Выбирается произвольное множество точек μi, i=1,...,k, рассматриваемых как начальные центры кластеров: μ(0)i=μi,i=1,...,k

2. 
   Распределение векторов по кластерам
   

Шаг t:∀xi∈X, i=1,...,n:xi∈Sj⟺j=argminkρ(xi,μ(t−1)k)2

3. 
   Пересчет центров кластеров
   

Шаг t:∀i=1,...,k:μ(t)i=1|Si|∑x∈Six

4. 
   Проверка условия останова:
   
   • 
     if ∃i∈1,k¯¯¯¯¯¯¯:μ(t)i≠μ(t−1)i then
     
     • 
       t=t+1;
       
     • 
       goto 2;
       
   • 
     else
     
     • 
       stop
       

1.3 Вычислительное ядро алгоритма

Вычислительным ядром являются шаги 2 и 3 приведенного выше алгоритма: распределение векторов по кластерам и пересчет центров кластеров.
Распределение векторов по кластерам предполагает вычисление расстояний между каждым вектором xi∈X, i=1,...,n и центрами кластера μj, j=1,...,k. Таким образом, данный шаг предполагает kn вычислений расстояний между d-мерными векторами.
Пересчет центров кластеров предполагает k вычислений центров масс μi множеств Si, i=1,...,k, представленных выражением в шаге 3 представленного выше алгоритма.

1.4 Макроструктура алгоритма

Инициализация центров масс μ1,...,μk.
Наиболее распространенными являются следующие стратегии:

• 
  Метод Forgy
  В качестве начальных значений μ1,...,μk берутся случайно выбранные векторы.
  
• 
  Метод случайно разделения (Random Partitioning)
  Для каждого вектора xi∈X, i=1,...,n, выбирается случайным образом кластер S1,...,Sk, после чего для каждого полученного кластера вычисляются значения μ1,...,μk.
  

Распределение векторов по кластерам
Для этого шага алгоритма между векторами xi∈X, i=1,...,n, и центрами кластеров μ1,...,μk вычисляются расстояния по формуле (как правило, используется Евлидово расстояние):

v1,v2∈Rd,ρ(v1,v2)=∥v1−v2∥=∑di=1(v1,i−v2,i)2−−−−−−−−−−−−−−√

(2)