Участник:Parkhomenko/Алгоритм k средних
| Алгоритм k средних | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ O(m*n*k*d) }[/math] |
| Объём входных данных | [math]\displaystyle{ n * d }[/math] |
| Объём выходных данных | [math]\displaystyle{ n }[/math] |
Основные авторы описания: П.А.Пархоменко, И.Д.Машонский
ЧАСТЬ. Свойства и структура алгоритмов
Общее описание алгоритма
Алгоритм k средних (англ. k-means) - один из алгоритмов машинного обучения, решающий задачу кластеризации. Он был изобретен в середине 1950-х математиком Гуго Штейнгаузом[1] и Стюартом Ллойдом[2]. Алгоритм стал особо популярным после публикации Маккуина[3], в которой впервые был использован термин “k-means”.
Задача алгоритма кластеризации заключается в разбиении N объектов (d-мерных векторов) на K групп (кластеров). Каждый вектор может принадлежать только одному кластеру. Количество кластеров K фиксировано, оно задается в качестве параметра.
K-means является итерационным алгоритмом, разновидностью EM-алгоритма. Основная идея работы алгоритма заключается в проведении некоторого количества итераций, на каждой из которых происходит пересчет центра масс для каждого кластера, полученного на предыдущей итерации. После этого векторы перераспределяются по кластерам: вектор относится к тому кластеру, расстояние до центра масс которого минимально. Алгоритм завершает работу в том случае, если на очередной итерации центры масс кластеров не изменились.
Математическое описание алгоритма
Вычислительное ядро алгоритма
Вычислительное ядро последовательного алгоритма k-means состоит из двух операций, повторяющихся на каждой итерации алгоритма:
- пересчета центров масс кластеров;
- соотнесения каждого вектора к одному из кластеров.
Пересчет центра масс кластера заключается в нахождении d-мерного вектора, являющегося средним арифметическим d-мерных векторов, принадлежащих кластеру. Эту операцию необходимо выполнять для каждого из K кластеров.
Для соотнесения вектора к одному из кластеров, необходимо для каждого из N вектора посчитать расстояние до центров масс всех K кластеров. Для нахождения расстояния между двумя d-мерными векторами p и q используется Евклидова метрика: [math]\displaystyle{ \sqrt{\sum_{k=1}^d (p_k-q_k)^2} }[/math]
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Для вычисления центра массы кластера, содержащего [math]\displaystyle{ n_i }[/math] d-мерных векторов, необходимо:
- [math]\displaystyle{ n_i * (d - 1) }[/math] операций сложения
- [math]\displaystyle{ d }[/math] операций деления
Для определения центров масс всех k кластеров требуется:
- [math]\displaystyle{ n * (d - 1) }[/math] операций сложения
- [math]\displaystyle{ k * d }[/math] операций деления
Для определения расстояния между двумя d-мерными векторами, требуется:
- [math]\displaystyle{ d }[/math] операций вычитания
- [math]\displaystyle{ d }[/math] операций умножения
- [math]\displaystyle{ d - 1 }[/math] операций сложения
Для определения кластера для n d-мерного векторов, необходимо:
- [math]\displaystyle{ n * k * d }[/math] операций вычитания
- [math]\displaystyle{ n * k * d }[/math] операций умножения
- [math]\displaystyle{ n * k * (d - 1) }[/math] операций сложения
Таким образом, общая сложность одной итерации:
- [math]\displaystyle{ O(n * k * d) }[/math] операций сложения/вычитания
- [math]\displaystyle{ O(n * k * d) }[/math] операций умножения/деления
Сложность всего алгоритма, состоящего из m итераций: [math]\displaystyle{ O(m * n * k * d) }[/math]
Информационный граф
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Входные данные:
- целое неотрицательное число [math]\displaystyle{ k }[/math] - количество кластеров;
- матрица координат векторов [math]\displaystyle{ A }[/math] размерностью [math]\displaystyle{ n * d }[/math].
Объем входных данных:
- [math]\displaystyle{ n * d }[/math] вещественных чисел (если координаты вещественные числа), [math]\displaystyle{ 1 }[/math] целое неотрицательное число.
Выходные данные:
- вектор длины [math]\displaystyle{ n }[/math] - для каждого вектора указан номер кластера.
Объем выходных данных:
- [math]\displaystyle{ n }[/math] целых неотрицательных чисел.
Свойства алгоритма
ЧАСТЬ. Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
Литература
<references \>
- ↑ Steinhaus H. (1956). Sur la division des corps materiels en parties. Bull. Acad. Polon. Sci., C1. III vol IV: 801—804.
- ↑ Lloyd S. (1957). Least square quantization in PCM’s. Bell Telephone Laboratories Paper.
- ↑ MacQueen J. (1967). Some methods for classification and analysis of multivariate observations. In Proc. 5th Berkeley Symp. on Math. Statistics and Probability, pages 281—297.