Участник:Parkhomenko/Алгоритм k средних: различия между версиями
| Строка 21: | Строка 21: | ||
В результате работы алгоритма исходное множество векторов <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>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> | Под <math>\mu_i</math> здесь подразумевается центр масс векторов из множества <math>S_i</math>. | ||
Первоначальные значения центров масс <math>\mu_1^{(1)}, ..., \mu_k^{(1)}</math> определяются в начале работы алгоритма случайным образом среди векторов множества <math>X</math>. | Первоначальные значения центров масс <math>\mu_1^{(1)}, ..., \mu_k^{(1)}</math> определяются в начале работы алгоритма случайным образом среди векторов множества <math>X</math>. | ||
Версия от 07:37, 5 октября 2016
| Алгоритм 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-алгоритма. Основная идея работы алгоритма заключается в проведении некоторого количества итераций, на каждой из которых происходит пересчет центра масс для каждого кластера, полученного на предыдущей итерации. После этого векторы перераспределяются по кластерам: вектор относится к тому кластеру, расстояние до центра масс которого минимально. Алгоритм завершает работу в том случае, если на очередной итерации центры масс кластеров не изменились.
Математическое описание алгоритма
Исходные данные: множество d-мерных векторов (наблюдений) [math]\displaystyle{ X }[/math] = [math]\displaystyle{ \{x_1, x_2, ..., x_n\} }[/math], число кластеров [math]\displaystyle{ k \in \mathbb{N} }[/math]
В результате работы алгоритма исходное множество векторов [math]\displaystyle{ X }[/math] разбивается на [math]\displaystyle{ k }[/math] непересекающихся множеств (кластеров) [math]\displaystyle{ S_1, S_2, ..., S_k }[/math], таких что [math]\displaystyle{ X = {\bigcup \limits _{i = 1}^k S_i} }[/math] и значение [math]\displaystyle{ \sum_{i=1}^{k} \sum_{\mathbf x \in S_i} \left\| \mathbf x - \mu_i \right\|^2 }[/math] — минимально для всех возможных наборов [math]\displaystyle{ S_1, S_2, ..., S_k }[/math]. Под [math]\displaystyle{ \mu_i }[/math] здесь подразумевается центр масс векторов из множества [math]\displaystyle{ S_i }[/math].
Первоначальные значения центров масс [math]\displaystyle{ \mu_1^{(1)}, ..., \mu_k^{(1)} }[/math] определяются в начале работы алгоритма случайным образом среди векторов множества [math]\displaystyle{ X }[/math].
Алгоритм заключается в попеременном применении двух шагов: распределения векторов по кластерам и обновления центров масс каждого кластера
Распределение векторов по кластерам: на данном шаге каждый вектор распределяется в один из кластеров [math]\displaystyle{ S_i^{(t)} }[/math]:
- [math]\displaystyle{ 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]\displaystyle{ \mu^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j }[/math]
Алгоритм завершается, когда на очередном шаге не происходит изменения центров масс кластеров.
Вычислительное ядро алгоритма
Вычислительное ядро последовательного алгоритма 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.