Участник:Илья Егоров/Алгоритм k-средних

Алгоритм k-средних (k-means)
Последовательный алгоритм
Последовательная сложность	[math]O()[/math]
Объём входных данных	[math]\frac{()}{}[/math]
Объём выходных данных	[math]\frac{ ()}{}[/math]

Страница создана группой "Илья Егоров — Евгений Богомазов"

1 ЧАСТЬ. Свойства и структура алгоритмов

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

Алгоритм кластеризации k-средних впервые был предложен в 1950-х годах математиками Гуго Штейнгаузом и Стюартом Ллойдом независимо друг от друга. Наибольшую популярность он получил после работы Маккуина.

Алгоритм позволяет при заданном числе [math]k[/math] построить [math]k[/math] кластеров, расположенных на максимальном расстоянии друг от друга. Таким образом, наибольшей точности результат выполнения алгоритма достигает при полной осведомленности Пользователя о характере кластеризуемых объектов и, как следствие, при обладании максимально корректной информацией о числе кластеров.

В общем случае выбор числа [math]k[/math] может базироваться на любых значимых факторах, в том числе на результатах предшествующих исследований, теоретических соображениях или интуиции.

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

Исходные данные:

• [math]\{a_i\}, i = 1 \dots m[/math] — множество из [math]n[/math] объектов, подлежащих кластеризации и определяющихся вектором длины [math]dim[/math],
• [math]k[/math] — предполагаемое количество кластеров.

Вычисляемые данные:

• Центр предполагаемого кластера (центроид) — на первом шаге объявляется равным случайному объекту, а затем сдвигается в центр масс элементов кластера.

Если [math]\{s_1 \dots s_k\}[/math] — центроиды, где [math]1 \dots k[/math] — номера кластеров, то объект [math]a[/math] относится к кластеру [math]P[/math], если суммарное квадратичное отклонение точек кластеров от центров этих кластеров минимально:

[math]a_i \in P \Leftrightarrow \left|a_i - s_P\right| \rightarrow \min_P[/math]

Альтернатива:

Исходные данные:

• Совокупность n d-мерных векторов [math] X = \{x_1 \dots x_n\} , [/math] где [math] x_i = \{x_{i1} \dots x_{id}\} [/math]
• Предполагаемое количество кластеров k

Выходные данные:

• Разбиение X на множество [math] S = \{S_1 \dots S_k \}, \bigcup S_i = X, S_i \cap S_j = \emptyset, i \neq j [/math]
• k центров кластеров [math] \Mu = \{\mu_1 \dots \mu_k \} [/math], где [math] \mu_i = \{\mu_{i1} \dots \mu_{id} \} [/math], [math] \mu_i = argmin_y \sum_{x \in S_i} ||x-y||^2_E [/math] и [math] argmin_\Mu \sum_{i \in k} \sum_{x \in S_i} ||x-\mu_i||^2_E [/math]

Алгоритм:

1) [math] \mu_{ij} = random [/math]

2) [math] S_i = \{x| argmin_j ||x-\mu_j|| = i\} i = 1 \dots k [/math]

3) [math] \tilde{\mu_{i}} = E_{x \in S_i}(x) [/math]

4) Если для [math] \forall i: \mu_i = \tilde{\mu_i} [/math] то алгоритм завершен, иначе [math] \mu_i = \tilde{\mu_i} [/math] и перейти на пункт 2)

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

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

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

Алгоритм k-средних базируется на алгоритме вычисления расстояния между векторами, расстояние на каждом шаге высчитывается [math]k\cdot n[/math] раз.

Помимо этого, в конце каждого шага вычисляется центр масс объектов кластера, для всех объектов потребуется [math]n-1[/math] суммирование и [math]k[/math] делений.

1.5 Схема реализации последовательного алгоритма

Последовательность шагов алгоритма следующая:

   1. Шаг инициализации
       По какому-либо правилу выбираем [math]k[/math] объектов для кластеризации, объявляем их центроидами
       
   2. Шаг классификации
       Классифицируем каждый объект на предмет принадлежности к кластеру:
       
       [math]a_i \in P \Leftrightarrow \left|a_i - s_P\right| \rightarrow \min_P[/math]
       
   3. Шаг перерасчета центроидов
       Вычисляем центр масс каждого из кластеров.
       
   3.а Если для какого-либо кластера его центр масс отличается от центроида, то 
           * переносим центроид этого кластера во вновь образованный центр масс,
           * проделываем эту операцию для всех других кластеров
           * переходим к Шагу 2
       
   3.б Если для каждого кластера его центр масс совпадает с центроидом, то
           Выход из алгоритма, объекты классифицированы.

1.6 Последовательная сложность алгоритма

   1. Шаг инициализации
       
       Сложность выбора [math]k[/math] центроидов [math]O(1)[/math]
      
  2. Шаг классификации
      
       Для каждого из [math]n[/math]объектов требуется выполнить [math]k*dim[/math] операций умножения и [math]k*(k - 1)[/math] операций сложения. То есть сложность вычисления расстояний на каждой итерации [math]O(n*k*(dim + k - 1)[/math].
       
       После этого нужно найти кластер, расстояние до которого минимально. Сложность такого поиска [math]O(n*k)[/math]
       
       Суммарная сложность шага [math]O(n*k*(dim + k - 1)[/math].
      
  3. Шаг перерасчета центроидов
      
      Для вычисления центра масс каждого из кластеров требуется совершить [math](n - 1)*dim[/math] операцию сложения и [math]k*dim[/math] операций деления. Сложность шага [math]O((n + k - 1)*dim)[/math]
      
  3.а Обновление центроидов потребует [math]k*dim[/math] операций вычитания, сложность шага [math]O(k*dim)[/math]

1.9 Входные и выходные данные алгоритма

Входные данные: Количество кластеров [math]k[/math], [math]m[/math]кластеризуемых элементов Дополнительные ограничения:

• [math]k[/math] — положительное число, т. е. [math]k \gt 0[/math].
• Для кластеризуемых элементов определена метрика (расстояние между объектами)

Объём входных данных: [math]n\cdot dim + 1[/math] (кластеризуемые объекты в виде векторов и число [math]k[/math])

Выходные данные: Массив, в который записаны принадлежности каждого элемента кластеру (допустим вывод в другой эквивалентной более удобной структуре).

Объём выходных данных: Размер массива равен [math]2\cdot n[/math].

1.10 Свойства алгоритма

Вычислительная мощность алгоритма на каждом шаге равна [math]k\cdot n[/math] (расстояние между элементом и центроидом [math]k\cdot n[/math] раз)

3 Литература

[1] Нейский И.М. Классификация и сравнение методов кластеризации http://it-claim.ru/Persons/Neyskiy/Article2_Neiskiy.pdf

[2] https://ru.wikipedia.org/wiki/K-means