Участник:IanaV/Алгоритм k means: различия между версиями
IanaV (обсуждение | вклад) |
IanaV (обсуждение | вклад) |
||
| Строка 94: | Строка 94: | ||
#* Количество операций взятия минимума: <math>N^{min}_{distr} = n * (k - 1)</math>. | #* Количество операций взятия минимума: <math>N^{min}_{distr} = n * (k - 1)</math>. | ||
# Пересчет центра масс <math>\mu_i \in R^d</math> для <math>k</math> кластеров на одной итерации: | # Пересчет центра масс <math>\mu_i \in R^d</math> для <math>k</math> кластеров на одной итерации: | ||
| − | #* Количество операций деления: <math>N^{/}_{ | + | #* Количество операций деления: <math>N^{/}_{update} = k * d</math>; |
| − | #* Количество операций сложения: <math>N^{+}_{ | + | #* Количество операций сложения: <math>N^{+}_{update} = d * (n - k)</math>. |
Следовательно, в случае если алгоритм сошелся за <math>i</math> итераций, получаем: | Следовательно, в случае если алгоритм сошелся за <math>i</math> итераций, получаем: | ||
| − | * Операций сложения/вычитания: <math>N^{+,-}_{k-means} = N^{+}_{init} + i*(N^{+}_{distr} + N^{-}_{distr} + N^{+}_{ | + | * Операций сложения/вычитания: <math>N^{+,-}_{k-means} = N^{+}_{init} + i*(N^{+}_{distr} + N^{-}_{distr} + N^{+}_{update}) = d * (n - k) + i*(k*n*(d-1)+k*n*d+d*(n-k)) \thicksim O(i*k*n*d)</math> |
| − | * Операций умножения/деления: <math>N^{*,/}_{k-means} = N^{/}_{init} + i*(N^{*}_{distr} + N^{/}_{ | + | * Операций умножения/деления: <math>N^{*,/}_{k-means} = N^{/}_{init} + i*(N^{*}_{distr} + N^{/}_{update}) = k * d + i*(k*n*d+k*d) \thicksim O(i*k*n*d)</math> |
Таким образом, [[глоссарий#Последовательная сложность|''последовательная сложность'']] алгоритма k-means для <math>n</math> <math>d</math>-мерных векторов и <math>k</math> кластеров за <math>i</math> итераций, требуемых для сходимости алгоритма: <p align="center"><math>O(i * n * k * d)</math></p> | Таким образом, [[глоссарий#Последовательная сложность|''последовательная сложность'']] алгоритма k-means для <math>n</math> <math>d</math>-мерных векторов и <math>k</math> кластеров за <math>i</math> итераций, требуемых для сходимости алгоритма: <p align="center"><math>O(i * n * k * d)</math></p> | ||
Версия 19:04, 15 октября 2016
Авторы страницы: Валуйская Я.А., Глотов Е.С.
Вклад в основную часть работы (сбор и анализ данных) у авторов одинаков, четких разграничений по пунктам статьи сделать невозможно. Итоговое оформление статьи выполнила Валуйская Я.А.
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Алгоритм k-means (k средних) - один из наиболее популярных алгоритмов кластеризации. Наиболее простой, но в то же время достаточно неточный метод кластеризации в классической реализации.
Алгоритм был разработан в 1956 году математиком Гуго Штейнгаузом [1], и почти одновременно его изобрел Стюарт Ллойд [2]. Особую популярность алгоритм снискал после работы Джеймса Маккуина [3]
Алгоритм кластеризации k-means решает задачу распределения [math]N[/math] наблюдений (элементов векторного пространства) на заранее известное число кластеров [math]K[/math]. Действие алгоритма таково, что он стремится минимизировать среднеквадратичное отклонение на точках каждого кластера.
Основная идея алгоритма заключается в том, что на каждой итерации перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем векторы разбиваются на кластеры вновь в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике. Алгоритм завершается, когда на какой-то итерации не происходит изменения кластеров.
1.2 Математическое описание алгоритма
Исходные данные:
- множество наблюдений [math]X = \{x_1, x_2, ..., x_n\}[/math], где каждое наблюдение [math]x_i \in R^d, i = 1, ..., n[/math];
- количество кластеров [math]k \in N, k \leq n[/math]
Обозначения:
- [math]S = \{S_1, S_2, ..., S_k \} [/math] - множество кластеров, которые удовлетворяют следующим условиям:
- [math]S_i \bigcap S_j = \emptyset, i \neq j[/math];
- [math]X = {\bigcup \limits _{i = 1}^k S_i} [/math].
- [math]\mu_i \in R^d, i = 1, ..., k[/math] - центр масс кластера [math]S_i[/math]
- [math]d(u, v)[/math] - расстояние между векторами [math]u \in R^m, v \in R^m[/math]
Выходные данные:
- [math]L = (l_1, l_2, ..., l_n)[/math] - набор меток, где метка [math]l_i \in N_{[1, k]}[/math] - является порядковым номером кластера, к которому принадлежит вектор [math]x_i[/math]: [math] x_i \in S_{l_i}[/math]
Цель алгоритма k-means - распределить наблюдения из входного множества [math]X[/math] по [math]k[/math] кластерам [math]S = \{S_1, S_2, ..., S_k \} [/math] таким образом, чтобы сумма квадратов расстояний от каждой точки кластера до его центра масс по всем кластерам была минимальной:
[math]\arg\min_{S} \sum_{i=1}^{k} \sum_{x \in S_i} (d(x, \mu_i))^2 [/math],
Алгоритм состоит из следующих шагов:
- Инициализация центров масс
На данном шаге задаются начальные значения центров масс [math] \mu_1^1, ..., \mu_k^1[/math]. Существует несколько способов их выбора. Они будут рассмотрены ниже. - t-ый шаг итерации:
- Распределение векторов по кластерам
На данном шаге каждый вектор [math]x_i \in X[/math] распределяется в свой кластер [math]S_j^t[/math] так, что:
[math]l_i^t = \arg \min_{j} (d(x_i, \mu_j^t))^2 , j = 1, ..., k; i = 1, ..., n[/math] - Пересчет центров масс кластеров
На данном шаге происходит пересчет центров масс кластеров, полученных на предыдущем этапе:
[math]\mu_i^{t+1} = \frac{1}{|S_i^t|} \sum_{x \in S_i^t} x[/math]; [math]i = 1, ..., k[/math]
- Распределение векторов по кластерам
- Критерий останова
[math]\mu_i^t = \mu_i^{t+1},[/math] для всех [math]i = 1, ..., k[/math]
Способы инициализации начальных данных:
- Метод Forgy
Случайным образом выбираются [math]k[/math] векторов из множества наблюдений [math]X[/math]. Эти вектора используются в качестве центров масс кластеров [math]\mu_1, ..., \mu_k[/math] - Метод случайного разбиения (Random Partition) [4]
Каждый вектор [math]x_i, i = 1, .., n[/math] случайным образом распределяется в кластер [math]S_j, j = 1, .., k[/math], затем для каждого кластера вычисляется его центр масс [math]\mu_j[/math].
1.3 Вычислительное ядро алгоритма
Вычислительном ядром алгоритма является шаг 2, состоящий из следующих этапов:
- распределение векторов по кластерам;
- пересчет центров масс кластеров.
Распределение векторов по кластерам заключается в следующем: для каждого вектора [math]x_i \in X, i = 1, ..., n[/math] необходимо посчитать расстояние между этим вектором и центром масс кластера [math]\mu_j^t, j = 1, ..., k[/math]. Следовательно, на каждой итерации необходимо выполнить [math]n * k[/math] операций вычисления расстояния между векторами.
Пересчет центров масс кластеров заключается в следующем: для каждого кластера [math]S_i^t \in S, i = 1, ..., k[/math] необходимо пересчитать кластер по формуле, приведенной в пункте выше. Следовательно, на каждой итерации необходимо выполнить [math]k[/math] операций пересчета центров масс кластеров.
1.4 Макроструктура алгоритма
- Макрооперация "Расстояние между векторами"
В данном алгоритме используется Евклидова метрика:
[math]v \in R^m[/math] и [math]u \in R^m: d(v, u) = \sqrt{\sum_{j=1}^{m} (v_j - u_j)^2} [/math]; - Макрооперация "Пересчет центра масс кластера"
[math]\mu_i^{t+1} = \frac{1}{|S_i^t|} \sum_{x \in S_i^t} x[/math]
1.5 Схема реализации последовательного алгоритма
Псевдокод алгоритма:
Входные данные : Множество векторов [math]X[/math], количество кластеров [math]k[/math] Выходные данные : Набор меток [math]L[/math] принадлежности к кластеру 1 Инициализация центров масс [math]\mu_i^1, i = 1, ..., k[/math]; 2 t := 1; 3 Для каждого вектора [math]x_i \in X, i = 1, ..., n:[/math] [math]l_i^t = \arg \min_{j} (d(x_i,\mu_j^t))^2 , j = 1, ..., k[/math]; 4 Для каждого кластера [math]S_i^t, i = 1, ..., k[/math] выполняется макрооперация "Пересчет центра масс"; 5 if ([math]\exists i = 1, ..., k: \mu_i^t \neq \mu_i^{t+1}[/math]) { 6 t := t + 1; 7 goto 3; 8 } else { 9 stop; 10 };
Существующие способы оптимизации алгоритма [5] [6] [7]
1.6 Последовательная сложность алгоритма
Подсчитаем количество операций для каждого шага алгоритма.
- Инициализация:
- Метод Forgy: [math]N_{init} = 0[/math]
- Метод случайного разбиения:
- Количество операций деления: [math]N^{/}_{init} = k * d[/math];
- Количество операций сложения: [math]N^{+}_{init} = d * (n - k)[/math].
- Распределение [math]n[/math] векторов [math]x_i \in R^d[/math] по [math]k[/math] кластерам на одной итерации:
- Количество операций умножения: [math]N^{*}_{distr} = k * n * d[/math];
- Количество операций сложения: [math]N^{+}_{distr} = k * n * (d - 1)[/math];
- Количество операций вычитания: [math]N^{-}_{distr} = k * n * d[/math];
- Количество операций взятия минимума: [math]N^{min}_{distr} = n * (k - 1)[/math].
- Пересчет центра масс [math]\mu_i \in R^d[/math] для [math]k[/math] кластеров на одной итерации:
- Количество операций деления: [math]N^{/}_{update} = k * d[/math];
- Количество операций сложения: [math]N^{+}_{update} = d * (n - k)[/math].
Следовательно, в случае если алгоритм сошелся за [math]i[/math] итераций, получаем:
- Операций сложения/вычитания: [math]N^{+,-}_{k-means} = N^{+}_{init} + i*(N^{+}_{distr} + N^{-}_{distr} + N^{+}_{update}) = d * (n - k) + i*(k*n*(d-1)+k*n*d+d*(n-k)) \thicksim O(i*k*n*d)[/math]
- Операций умножения/деления: [math]N^{*,/}_{k-means} = N^{/}_{init} + i*(N^{*}_{distr} + N^{/}_{update}) = k * d + i*(k*n*d+k*d) \thicksim O(i*k*n*d)[/math]
Таким образом, последовательная сложность алгоритма k-means для [math]n[/math] [math]d[/math]-мерных векторов и [math]k[/math] кластеров за [math]i[/math] итераций, требуемых для сходимости алгоритма:
[math]O(i * n * k * d)[/math]
1.7 Информационный граф
Рассмотрим информационный граф алгоритма k-means. На рисунке 1 представлена общая схема алгоритма k-means, согласно разделу "Схема реализации последовательного алгоритма". Вершина Init - этап инициализации. Вершина Distribute - этап распределения векторов по кластерам. Вершина Update - этап пересчета центров масс кластеров.
На рисунке 2 представлен информационный граф этапа распределения векторов по кластерам. На вход данному этапу подают множество векторов [math]x_1, x_2, ..., x_n[/math] из входных данных и множество центров масс кластеров [math]\mu^t_1, ..., \mu^t_k[/math], полученных с шага инициализации или с предыдущей итерации. Для каждой пары векторов [math]x_i, \mu^t_j, i = 1, ..., n; j = 1,..., k[/math] считается расстояние между ними (вершина dist). Информационный граф вычисления расстояния между двумя векторами рассмотрен ниже. Затем выполняется операция нахождения минимума (вершина min), в результате которой каждому вектору [math]x_i, i = 1, ..., n[/math] приписывается метка [math]l^t_i[/math], равная порядковому номеру кластера [math]S^t_j, j = 1 ..., k[/math], которому принадлежит данный вектор: [math]x_i \in S^t_j[/math].
На рисунке 3 представлен информационный граф вычисления расстояния между двумя векторами [math]x_i = (x_{i1}, ..., x_{id}), i = 1, ..., n[/math] и [math]\mu^t_j = (\mu^t_{j1}, ..., \mu^t_{jd}) , j = 1, ..., k[/math]. Выполняется операция поэлементного вычитания двух векторов (вершины -), затем возведение в квадрат (вершины sqr), затем суммирование полученных результатов (вершина +). На выходе получаем квадрат расстояния между векторами.
На рисунке 4 представлен информационный граф этапа пересчета центров масс кластеров [math]\mu^t_1, \mu^t_2,..., \mu^t_k[/math]. Для каждого кластера [math]S^t_j, j = 1, ..., k[/math] выполняется операция суммирования (вершина [math]sum_j[/math]) векторов, которые принадлежат данному кластеру. Кроме того, для каждого кластера выполняется операция определения его размера (вершина [math]size_j[/math]). Затем выполняется операция деления (вершина /). На выходе получаем новые центры масс кластеров [math]\mu^{t+1}_1, \mu^{t+1}_2,..., \mu^{t+1}_k[/math].
1.8 Ресурс параллелизма алгоритма
Вычислительное ядро алгоритма имеет большие возможности для параллелизма:
- Распределение векторов по кластерам: вектора [math]x_i, x_j, i \neq j; i, j = 1, ..., n[/math] могут быть распределены по кластерам независимо друг от друга;
- Пересчет центров масс кластеров: центры масс кластеров [math]\mu_i, \mu_j, i \neq j; i, j = 1, ..., k[/math] могут быть пересчитаны независимо друг от друга.
Однако, этап пересчета центров масс кластеров зависит от этапа распределения векторов по кластерам, так что эти этапы должны выполняться строго последовательно. Таким образом, параллельная сложность алгоритма может быть вычислена следующим образом:
[math]N_{k-means} = N_{init} + i * (N_{distr} + N_{centr})[/math], где [math]N_{init}[/math] - сложность этапа инициализации, [math]i[/math] - количество итераций, необходимых для сходимости алгоритма, [math]N_{distr}[/math] - параллельная сложность этапа распределения векторов по кластерам, [math]N_{centr}[/math] - параллельная сложность этапа пересчета центров масс кластеров.
Рассчитаем параллельную сложность [math]N_{distr}[/math] этапа распределения векторов по кластерам в предположении наличия неограниченного числа процессоров для одной итерации. Для каждой пары векторов [math](x_i, \mu_j), i = 1,...,n; j = 1, ..., k[/math] операция вычисления расстояния выполняется независимо.
- Подсчет расстояния требует [math]O(log(d))[/math] операций согласно алгоритму нахождения частичной суммы элементов массива путем сдваивания;
- Для нахождения минимума среди [math]k[/math] элементов требуется [math]O(log(k))[/math] операций.
Таким образом, получаем, что [math]N_{distr} = log(k*d)[/math]
1.9 Входные и выходные данные алгоритма
Входные данные:
- [math]n[/math] векторов [math]x_i \in R^d, i = 1, ..., n[/math];
- число кластеров [math]k \in N_{[1,n]}[/math].
Объем входных данных: [math]n * d[/math] действительных чисел, 1 целое число
Выходные данные:
- вектор меток [math]L \in N^n[/math].
Объем выходных данных: [math]n[/math] целых чисел. [math]n \in [1,k][/math]
1.10 Свойства алгоритма
- Достоинства
- Алгоритм прозрачный и понятный, за счет чего очень прост в реализации;
- Алгоритм имеет высокую скорость работы в случае выбора оптимальных начальных значений центров масс кластеров.
- Недостатки
- Число кластеров является входным аргументом алгоритма. Таким образом, некорректный выбор данного параметра может привести к плохим результатам работы алгоритма, поэтому очень важно проводить диагностические прогоны для подбора оптимального количества кластеров;
- Алгоритм может сойтись к локальному минимуму (достижение глобального минимума не гарантируется);
- Результат сильно зависит от выбора начальных значений центров масс кластеров. Существует улучшенная версия алгоритма - k-means++ [8], которая предлагает свой способ нахождения начальных оптимальных значений центров масс кластеров;
- Чувствительность к выбросам и шумам, так как они учитываются при вычислении центров масс кластеров.
- Устойчивость
- Алгоритм является устойчивым к погрешностям во входных данных, так как при вычислении центров кластеров расстояния между объектами усредняются, что приводит к уменьшению ошибки. Алгоритм также является устойчивым к погрешностям, допускаемых при вычислениях, так как операция сложения на каждой новой итерации выполняется над входными данными.
- Сбалансированность
- todo
- Соотношение последовательной и параллельной сложности
- todo
- Вычислительная мощность
- [math]{O(n*d*k*i) \over n*d+n+1} \thicksim {O(d*k*i) \over d+1} \thicksim O(k*i)[/math], где [math]n[/math] - число входных векторов, [math]d[/math] - размерность векторов, [math]k[/math] - число кластеров, [math]i[/math] - число итераций, требуемое для сходимости
- Детерминированность
- Алгоритм является недетерминированным, так как результат зависит от выбора исходных центров кластеров, а их оптимальный выбор неизвестен.
2 Программная реализация алгоритма
2.1 Масштабируемость алгоритма и его реализации
2.2 Существующие реализации алгоритма
Существуют следующие Open Source реализации алгоритма:
- ELKI - содержит реализацию алгоритма k-means на языке Java (в том числе реализацию улучшенного алгоритма k-means++)
- Weka - содержит реализацию k-means на языке Java
- Apache Mahout - содержит реализацию k-means в парадигме MapReduce
- Spark Mllib - содержит распределенную реализацию k-means
- Accord.NET - содержит реализацию k-means на C# (в том числе реализацию улучшенного алгоритма k-means++)
- MLPACK - содержит реализацию k-means на языке C++
- OpenCV - содержит реализацию k-means на C++. А также есть обертки для языков Python и Java
- SciPy - содержит реализацию k-means на языке Python
- Scikit-learn - содержит реализацию k-means на языке Python
- Julia - содержит реализацию алгоритма k-means на языке Julia
- Octave - содержит реализацию k-means на языке Octave
- R - содержит реализацию k-means на языке R
- Torch - содержит реализацию k-means на языке Lua
3 Литература
- ↑ 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.
- ↑ Hamerly, G.; Elkan, C. (2002). "Alternatives to the k-means algorithm that find better clusterings". Proceedings of the eleventh international conference on Information and knowledge management (CIKM).
- ↑ Phillips S. J. Acceleration of k-means and related clustering algorithms //Workshop on Algorithm Engineering and Experimentation. – Springer Berlin Heidelberg, 2002. – С. 166-177.
- ↑ Hamerly G. Making k-means Even Faster //SDM. – 2010. – С. 130-140.
- ↑ Elkan C. Using the triangle inequality to accelerate k-means //ICML. – 2003. – Т. 3. – С. 147-153.
- ↑ Arthur, D.; Vassilvitskii, S. (2007). "k-means++: the advantages of careful seeding". Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics Philadelphia, PA, USA. pp. 1027–1035.
