Участник: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.3 Вычислительное ядро алгоритма

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

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

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

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

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 \>