Участник:Бротиковская Данута/Алгоритм k-means: различия между версиями

Версия 12:42, 14 октября 2016

Алгоритм k средних (k means)
Последовательный алгоритм
Последовательная сложность	[math]O(\Taukn*d)[/math]
Объём входных данных	[math] n*d [/math]
Объём выходных данных	[math] n [/math]

Авторы страницы Данута Бротиковская и Денис Зобнин

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Алгоритм k средних (k means) -- наиболее популярный метод кластеризации. Был изобретен в 1950-х годах математиком Гуго Штейнгаузом^[1] и почти одновременно Стюартом Ллойдом^[2]. Особую популярность приобрел после публикации работы МакКуина^[3] в 1967. Цель алгоритма заключается в разделении [math]n[/math] наблюдений на [math]k[/math] кластеров таким образом, чтобы каждое наблюдение придележало ровно одному кластеру, расположенному на наименьшем расстоянии от наблюдения.

1.2 Математическое описание алгоритма

Дан набор из [math]n[/math] d-мерных векторов [math]X=\{\mathbf{x}_1, \mathbf{x}_2, ..., \mathbf{x}_n\}[/math]. Алгоритм k means разбивает набор [math]X[/math] на [math]k, k\lt =n[/math] наборов [math]S=\{S_1, S_2, ..., S_k\}, S_i \cap S_j= \varnothing, i \ne j, [/math] таким образом, чтобы минимизировать сумму квадратов расстояний от каждой точки кластера до его центра. Другими словами:

[math]\arg\min_{S} \sum\limits_{i=1}^k \sum\limits_{x \in S_i} \lVert \mathbf{x}- \mathbf{\mu}_i \rVert^2,[/math]

[math](1)[/math]

где [math]\mathbf{\mu}_i[/math] – центры кластеров, [math]i=\overline{1,k}[/math]

Шаги алгоритма:

Начальный шаг: инициализация кластеров
Выбирается произвольное множество точек [math]\mu_i, i=\overline{1,k}[/math], рассматриваемых как начальные центры кластеров.
Распределение векторов по кластерам
[math]\forall \mathbf{x}_i \in X, i=\overline{1,n}: \mathbf{x}_i \in S_j \iff j=\arg\min_{k}||\mathbf{x}_i-\mathbf{\mu}_k||^2[/math]
Пересчет центров кластеров
[math] \forall i=\overline{1,k}: \widetilde{\mu_i} = \cfrac{1}{|S_i|}\sum_{x\in S_i}x[/math]

Проверка условия останова:

   if [math]\exist i\in \overline{1,k}: \mu_i \ne \widetilde{\mu_i}[/math] then
       goto 2;
   else
       stop

1.3 Вычислительное ядро алгоритма

Вычислительным ядром являются шаги 2 и 3 приведенного выше алгоритма: распределение векторов по кластерам и пересчет центров кластеров.

Распределение векторов по кластерам предполагает вычисление расстояний между каждым вектором [math]\mathbf{x}_i \in X, i= \overline{1,n}[/math] и центрами кластера [math]\mathbf{\mu}_j, j= \overline{1,k}[/math]. Таким образом, данный шаг предполагает [math]k*n[/math] вычислений расстояний между d-мерными векторами.

Пересчет центров кластеров предполагает [math]k[/math] вычислений центров масс [math]\mathbf{\mu}_i[/math] множеств [math]S_i, i=\overline{1,k}[/math] представленных выражением в шаге 3 представленного выше алгоритма.

1.4 Макроструктура алгоритма

Инициализация центров масс [math]\mu_1, ..., \mu_k[/math].

Наиболее распространенными являются следующие стратегии:

Метод Forgy
В качестве начальных значений [math]\mu_1, ..., \mu_k[/math] берутся случайно выбранные векторы.
Метод случайно разделения (Random Partitioning)
Для каждого вектора [math]x_i \in X, i=\overline{1, n}[/math] выбирается случайным образом кластер [math]S_1, ..., S_k[/math], после чего для каждого полученного кластера вычисляются значения [math]\mu_1, ..., \mu_k[/math].

Распределение векторов по кластерам

Для этого шага алгоритма между векторами [math]x_i \in X, i=\overline{1, n}[/math] и центрами кластеров [math]\mu_1, ..., \mu_k[/math] вычисляется расстояние по формуле:

[math]\rho(\mathbf{v_1}, \mathbf{v_2}) = \lVert \mathbf{v_1}- \mathbf{v_2} \rVert^2[/math]

[math](2)[/math]

Пересчет центров кластеров

Для этого шага алгоритма производится пересчет центров кластера по формуле:

[math] \mu = \cfrac{1}{|S|}\sum_{x\in S}x[/math]

[math](3)[/math]

1.5 Схема реализации последовательного алгоритма

algorithm k-means is
    1. Инициализировать центры кластеров [math]\mathbf{\mu}_i^{(1)}, i=\overline{1,k}[/math]
    2. [math]t \leftarrow 1[/math]
    3. Распределение по кластерам

       [math]S_i^{(t)}=\{\mathbf{x}_p: \lVert\mathbf{x}_p-\mathbf{\mu}_i^{(t)}\rVert^2 \leq \lVert\mathbf{x}_p-\mathbf{\mu}_j^{(t)}\rVert^2 \quad \forall j=\overline{1,k}\},[/math]

       где каждый вектор [math]\mathbf{x}_p[/math] соотносится единственному кластеру [math]S^{(t)}[/math]
    4. Обновление центров кластеров

       [math]\mathbf{\mu}_i^{(t+1)} = \frac{1}{|S^{(t)}_i|} \sum_{\mathbf{x}_j \in S^{(t)}_i} \mathbf{x}_j [/math]

    5. if [math]\exist i \in \overline{1,k}: \mathbf{\mu}_i^{(t)} \ne \mathbf{\mu}_i^{(t+1)}[/math] then
           goto 3;
       else
           stop

1.6 Последовательная сложность алгоритма

Обозначим [math]\Theta_{centroid}^{d, m}[/math] временную сложность вычисления центорида кластера, число элементов которого равна [math]m[/math], в d-мерном пространстве.

Аналогично [math]\Theta_{distance}^d[/math] – временная сложность вычисления расстояния между двумя d-мерными векторами.

Сложность шага инициализации [math]k[/math] кластеров мощности [math]m[/math] в d-мерном пространстве – [math]\Theta_{init}^{k, d, m}[/math]

Стратерия Forgy: вычисления не требуются, [math]\Theta_{init}^{k, d, m} = 0[/math]
Стратегия случайного разбиения: вычисление центров k кластеров, [math]\Theta_{init}^{k, d, m} = k*\Theta_{centroid}^{d, m}, m \le n[/math]

Cложность шага распределения d мерных векторов по k кластерам – [math]\Theta_{distribute}^{k, d}[/math]

На этом шаге для каждого вектора [math]x_i \in X, i=\overline{1, n}[/math] вычисляется k расстояний до центров кластеров [math]\mu_1, ...\mu_k[/math]

[math]\Theta_{distribute}^{k, d} = n*k*\Theta_{distance}^d[/math]

Сложность шага пересчета центров [math]k[/math] кластеров размера [math]m[/math] в d-мерном пространстве – [math]\Theta_{recenter}^{k, d, m}[/math]

На этом шаге вычисляется [math]k[/math] центров кластеров [math]\mu_1, ...\mu_k[/math]

[math]\Theta_{recenter}^{k, d, m} = k*\Theta_{centroid}^{d, m}[/math]

Рассчитаем [math]\Theta_{centroid}^{d, m}[/math] для кластера, число элементов которого равно [math]m[/math]

[math]\Theta_{centroid}^{d, m}[/math] = [math]m * d[/math] сложений + [math]d[/math] делений

Рассчитаем [math]\Theta_{distance}^d[/math] в соответствие с формулой [math](2)[/math]

[math]\Theta_{distance}^d[/math] = [math]d[/math] вычитаний + [math]d[/math] умножений + [math](d-1)[/math] сложение

Предположим, что алгоритм сошелся за [math]\Tau[/math] итераций, тогда временная сложность алгоритма [math]\Theta_{k-means}^{d, n}[/math]

[math]\Theta_{k-means}^{d, n} \le \Theta_{init}^{k, d, n} + \Tau*(\Theta_{distribute}^{k, d} + \Theta_{recenter}^{k, d, n})[/math]

Операции сложения/вычитания:

[math]\Theta_{k-means}^{d, n} \le k*n*d+ \Tau*(k*n*(2d-1) + k*n*d) = k*n*d+ \Tau*(k*n*(3d-1)) \thicksim O(\Tau*k*d*n)[/math]

Операции умножения/деления:

[math]\Theta_{k-means}^{d, n} \le k*d + \Tau*(k*n*d + k*d) = k*d + \Tau * k*d*(n+1) \thicksim O(\Tau*k*d*n) [/math]

Получаем, что временная сложность алгоритма k-means кластеризации [math]n[/math] d-мерных векторов на [math]k[/math] кластеров за [math]\Tau[/math] итераций:

[math] \Theta_{k-means}^{d, n} \thicksim O(\Tau*k*d*n) [/math]

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

Входные данные

Целое положительное число [math]k[/math] – количество кластеров.
Матрица из [math]n*d[/math] элементов – координат векторов (наблюдений).

Объем входных данных
1 целое число + [math]n*d[/math] вещественных чисел (при условии, что координаты – вещественные числа).

Выходные данные
Целые положительные числа – номера кластеров, соотвествующие каждому вектору (при условии, что нумерация кластеров начинается с 1).

Объем выходных данных
[math]n[/math] целых положительных чисел.

1.10 Свойства алгоритма

Сильные стороны алгоритма:

Сравнительно высокая эффективность при простоте реализации
Высокое качество кластеризации
Возможность распараллеливания
Существование множества модификаций

Недостатки алгоритма^[4]:

Количество кластеров является параметром алгоритма
Чувствительность к начальным условиям

Инициализация центров кластеров в значительной степени влияет на результат кластеризации.
Чувствительность к выбросам и шумам

Выбросы, далекие от центров настоящих кластеров, все равно учитываются при вычислении их центров.
Возможность сходимости к локальному оптимуму

Итеративный подход не дает гарантии сходимости к оптимальному решению.
Использование понятия "среднего"

Алгоритм неприменим к данным, для которых не определено понятие "среднего", например, категориальным данным.

Вычислительная мощность

Вычислительная мощностьВычислительная мощность алгоритма k-means равна [math]\frac{k*d*n*\Tau}{2*n*d} = \frac{k*\Tau}{2} [/math], где [math]k[/math] - число кластеров, [math]\Tau[/math] - число итераций алгоритма.

Детерминированность и устойчивость

Алгоритм k-means является итерационным. Количество итераций алгоритма в общем случае не фиксируется и зависит от начального расположения объектов в пространстве, параметра [math]k[/math], а также от начального приближения центров кластеров, [math]\mu_1, ..., \mu_k[/math]. В результате этого может варьироваться результат работы алгоритма. По этим причинам алгоритм не является ни детермирированным, ни устойчивым.

Сбалансированность

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.2.1 Локальность реализации алгоритма

2.2.1.1 Структура обращений в память и качественная оценка локальности

2.2.1.2 Количественная оценка локальности

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.4.1 Масштабируемость алгоритма

2.4.2 Масштабируемость реализации алгоритма

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

2.7.1 Открытое программное обеспечение

CrimeStat
Julia
Mahout
Octave
Spark
Torch
Weka
Accord.NET
OpenCV
MLPACK
SciPy
scikit-learn
R
ELKI

2.7.2 Проприетарное программное обеспечение

3 Литература

↑ Steinhaus, Hugo. "Sur la division des corp materiels en parties." Bull. Acad. Polon. Sci 1.804 (1956): 801.
↑ Lloyd, S. P. "Least square quantization in PCM. Bell Telephone Laboratories Paper. Published in journal much later: Lloyd, SP: Least squares quantization in PCM." IEEE Trans. Inform. Theor.(1957/1982).
↑ MacQueen, James. "Some methods for classification and analysis of multivariate observations." Proceedings of the fifth Berkeley symposium on mathematical statistics and probability. Vol. 1. No. 14. 1967.
↑ Ortega, Joaquín Pérez, Ma Del Rocío Boone Rojas, and María J. Somodevilla. "Research issues on K-means Algorithm: An Experimental Trial Using Matlab."

[1] Steinhaus, Hugo. "Sur la division des corp materiels en parties." Bull. Acad. Polon. Sci 1.804 (1956): 801.

[2] Lloyd, S. P. "Least square quantization in PCM. Bell Telephone Laboratories Paper. Published in journal much later: Lloyd, SP: Least squares quantization in PCM." IEEE Trans. Inform. Theor.(1957/1982).

[3] MacQueen, James. "Some methods for classification and analysis of multivariate observations." Proceedings of the fifth Berkeley symposium on mathematical statistics and probability. Vol. 1. No. 14. 1967.

[4] Ortega, Joaquín Pérez, Ma Del Rocío Boone Rojas, and María J. Somodevilla. "Research issues on K-means Algorithm: An Experimental Trial Using Matlab."

[1]

[2]

[3]

[4]

@@ Строка 214: / Строка 214: @@
 </ul>
 <p><b>Вычислительная мощность</b></p>
-Вычислительная мощность алгоритма k-means равна <math>\frac{k*d*n*\Tau}{2*n*d} = \frac{k*\Tau}{2} </math>, где <math>k</math> - число кластеров, <math>\Tau</math> - число итераций алгоритма.
+Вычислительная мощность[[глоссарий#Вычислительная мощность|''Вычислительная мощность'']] алгоритма k-means равна <math>\frac{k*d*n*\Tau}{2*n*d} = \frac{k*\Tau}{2} </math>, где <math>k</math> - число кластеров, <math>\Tau</math> - число итераций алгоритма.
 <p><b>Детерминированность и устойчивость </b></p>