Участник:Parkhomenko/Алгоритм k средних: различия между версиями
| Строка 60: | Строка 60: | ||
# Инициализируются центры масс <math>\mu_1^{(1)}, ..., \mu_k^{(1)}</math> | # Инициализируются центры масс <math>\mu_1^{(1)}, ..., \mu_k^{(1)}</math> | ||
# <math>t := 1</math> | # <math>t := 1</math> | ||
# Для каждого вектора <math>x_i, i = 1, 2, ..., n</math> вычисляется <br/><math>m = \underset{j \in \{1, 2, ..., k\}} {\operatorname{arg\,min}} \big \| x_i - \mu^{(t)}_j \big \|^2</math>, <br/>вектор <math>x_i</math> распределяется в кластер <math> | # Для каждого вектора <math>x_i, i = 1, 2, ..., n</math> вычисляется <br/><math>m = \underset{j \in \{1, 2, ..., k\}} {\operatorname{arg\,min}} \big \| x_i - \mu^{(t)}_j \big \|^2</math>, <br/>вектор <math>x_i</math> распределяется в кластер <math>S^{(t)}_m</math> | ||
# Для каждого <math>j = 1, 2, ..., k</math> вычисляется <br/><math>\mu^{(t+1)}_j = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math> | # Для каждого <math>j = 1, 2, ..., k</math> вычисляется <br/><math>\mu^{(t+1)}_j = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math> | ||
# Если <math>\mu^{(t)}_j = \mu^{(t+1)}_j, j = 1, 2, ..., k</math>, завершить выполнение алгоритма, иначе <math>t := t + 1</math>, переход на шаг 3. | # Если <math>\mu^{(t)}_j = \mu^{(t+1)}_j, j = 1, 2, ..., k</math>, завершить выполнение алгоритма, иначе <math>t := t + 1</math>, переход на шаг 3. | ||
Версия от 10:34, 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{ \mu_1^{(1)}, ..., \mu_k^{(1)} }[/math], которая может быть реализована двумя возможными способами:
- случайный выбор центров масс среди исходных наблюдений [math]\displaystyle{ x_1, x_2, ..., x_n }[/math];
- все наблюдения случайным образом распределяются по кластерам [math]\displaystyle{ S_1, S_2, ..., S_k }[/math], а затем для каждого кластера выполняется операция обновления центра масс.
На шаге распределения векторов по кластерам производится операция нахождения квадратов расстояний между векторами кластера и центром масс кластера:
- [math]\displaystyle{ \rho = \big \| x_p - \mu^{(t)}_i \big \|^2 }[/math]
На шаге обновления центров масс производится операция суммирования векторов кластера:
- [math]\displaystyle{ \mu^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j }[/math]
Схема реализации последовательного алгоритма
Последовательность исполнения метода следующая:
- Инициализируются центры масс [math]\displaystyle{ \mu_1^{(1)}, ..., \mu_k^{(1)} }[/math]
- [math]\displaystyle{ t := 1 }[/math]
- Для каждого вектора [math]\displaystyle{ x_i, i = 1, 2, ..., n }[/math] вычисляется
[math]\displaystyle{ m = \underset{j \in \{1, 2, ..., k\}} {\operatorname{arg\,min}} \big \| x_i - \mu^{(t)}_j \big \|^2 }[/math],
вектор [math]\displaystyle{ x_i }[/math] распределяется в кластер [math]\displaystyle{ S^{(t)}_m }[/math] - Для каждого [math]\displaystyle{ j = 1, 2, ..., k }[/math] вычисляется
[math]\displaystyle{ \mu^{(t+1)}_j = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j }[/math] - Если [math]\displaystyle{ \mu^{(t)}_j = \mu^{(t+1)}_j, j = 1, 2, ..., k }[/math], завершить выполнение алгоритма, иначе [math]\displaystyle{ t := t + 1 }[/math], переход на шаг 3.
Последовательная сложность алгоритма
Для вычисления центра массы кластера, содержащего [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.