Участник:Parkhomenko/Алгоритм k средних

Алгоритм k средних
Последовательный алгоритм
Последовательная сложность	[math]O(m*n*k*d)[/math]
Объём входных данных	[math]n * d[/math]
Объём выходных данных	[math]n[/math]

Основные авторы описания: П.А.Пархоменко, И.Д.Машонский

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

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

Алгоритм k средних (англ. k-means) - один из алгоритмов машинного обучения, решающий задачу кластеризации. Он был изобретен в середине 1950-х математиком Гуго Штейнгаузом и Стюартом Ллойдом. Алгоритм стал особо популярным после публикации Маккуина, в которой впервые был использован термин “k-means”.

Задача алгоритма кластеризации заключается в разбиении N объектов (d-мерных векторов) на K групп (кластеров). Каждый вектор может принадлежать только одному кластеру. Количество кластеров K фиксировано, оно задается в качестве параметра.

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

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

Исходные данные: множество d-мерных векторов (наблюдений) [math]X[/math] = [math]\{x_1, x_2, ..., x_n\}[/math], число кластеров [math]k \in \mathbb{N}[/math]

В результате работы алгоритма исходное множество векторов [math]X[/math] разбивается на [math]k[/math] непересекающихся множеств (кластеров) [math]S_1, S_2, ..., S_k[/math], таких что [math]X = {\bigcup \limits _{i = 1}^k S_i} [/math] и значение [math]\sum_{i=1}^{k} \sum_{\mathbf x \in S_i} \left\| \mathbf x - \mu_i \right\|^2 [/math] — минимально для всех возможных наборов [math]S_1, S_2, ..., S_k[/math]. Под [math]\mu_i[/math] здесь подразумевается центр масс векторов из множества [math]S_i[/math].

Первоначальные значения центров масс [math]\mu_1^{(1)}, ..., \mu_k^{(1)}[/math] определяются в начале работы алгоритма случайным образом среди векторов множества [math]X[/math].

Алгоритм заключается в попеременном применении двух шагов: распределения векторов по кластерам и обновления центров масс каждого кластера

Распределение векторов по кластерам: на данном шаге каждый вектор распределяется в один из кластеров [math]S_i^{(t)}[/math]:

[math]S_i^{(t)} = \big \{ x_p : \big \| x_p - \mu^{(t)}_i \big \|^2 \le \big \| x_p - \mu^{(t)}_j \big \|^2 \ \forall j, 1 \le j \le k \big\},[/math]

Обновление центров масс: на данном шаге вычисляются новые центры масс для кластеров, полученных на предыдущем шаге.

[math]\mu^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j [/math]

Алгоритм завершается, когда на очередном шаге не происходит изменения центров масс кластеров.

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

Вычислительное ядро последовательного алгоритма k-means состоит из двух операций, повторяющихся на каждой итерации алгоритма:

• пересчета центров масс кластеров;
• соотнесения каждого вектора к одному из кластеров.

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

Для соотнесения вектора к одному из кластеров, необходимо для каждого из N вектора посчитать расстояние до центров масс всех K кластеров. Для нахождения расстояния между двумя d-мерными векторами p и q используется Евклидова метрика: [math]\sqrt{\sum_{k=1}^d (p_k-q_k)^2}[/math]

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

В начале алгоритма осуществляется инициализация центров масс [math]\mu_1^{(1)}, ..., \mu_k^{(1)}[/math], которая может быть реализована двумя возможными способами:

• случайный выбор центров масс среди исходных наблюдений [math]x_1, x_2, ..., x_n[/math];
• все наблюдения случайным образом распределяются по кластерам [math]S_1, S_2, ..., S_k[/math], а затем для каждого кластера выполняется операция обновления центра масс.

На шаге распределения векторов по кластерам производится операция нахождения квадратов расстояний между векторами кластера и центром масс кластера:

[math]\rho = \big \| x_p - \mu^{(t)}_i \big \|^2[/math]

На шаге обновления центров масс производится операция суммирования векторов кластера:

[math]\mu^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j [/math]

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

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

1. Инициализируются центры масс [math]\mu_1^{(1)}, ..., \mu_k^{(1)}[/math]
2. [math]t := 1[/math]
3. Для каждого вектора [math]x_i, i = 1, 2, ..., n[/math] вычисляется
   [math]m = \underset{j \in \{1, 2, ..., k\}} {\operatorname{arg\,min}} \big \| x_i - \mu^{(t)}_j \big \|^2[/math],
   вектор [math]x_i[/math] распределяется в кластер [math]S^{(t)}_m[/math]
4. Для каждого [math]j = 1, 2, ..., k[/math] вычисляется
   [math]\mu^{(t+1)}_j = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j [/math]
5. Если [math]\mu^{(t)}_j = \mu^{(t+1)}_j, j = 1, 2, ..., k[/math], завершить выполнение алгоритма, иначе [math]t := t + 1[/math], переход на шаг 3.

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

Для вычисления центра массы кластера, содержащего [math]n_i[/math] d-мерных векторов, необходимо:

• [math]n_i * (d - 1)[/math] операций сложения
• [math]d[/math] операций деления

Для определения центров масс всех k кластеров требуется:

• [math]n * (d - 1)[/math] операций сложения
• [math]k * d[/math] операций деления

Для определения расстояния между двумя d-мерными векторами, требуется:

• [math]d[/math] операций вычитания
• [math]d[/math] операций умножения
• [math]d - 1[/math] операций сложения

Для определения кластера для n d-мерного векторов, необходимо:

• [math]n * k * d[/math] операций вычитания
• [math]n * k * d[/math] операций умножения
• [math]n * k * (d - 1)[/math] операций сложения

Таким образом, общая сложность одной итерации:

• [math]O(n * k * d)[/math] операций сложения/вычитания
• [math]O(n * k * d)[/math] операций умножения/деления

Сложность всего алгоритма, состоящего из m итераций: [math]O(m * n * k * d)[/math]

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

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

• целое неотрицательное число [math]k[/math] - количество кластеров;
• матрица координат векторов [math]A[/math] размерностью [math]n * d[/math].

Объем входных данных:

• [math]n * d[/math] вещественных чисел (если координаты вещественные числа), [math]1[/math] целое неотрицательное число.

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

• вектор длины [math]n[/math] - для каждого вектора указан номер кластера.

Объем выходных данных:

• [math]n[/math] целых неотрицательных чисел.

3 Литература

<references \>