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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 73: Строка 73:
 
  9      <b>stop</b>;
 
  9      <b>stop</b>;
 
  10 };
 
  10 };
 +
 +
Существующие способы оптимизации алгоритма <ref>[http://link.springer.com/chapter/10.1007/3-540-45643-0_13  Phillips S. J. Acceleration of k-means and related clustering algorithms //Workshop on Algorithm Engineering and Experimentation. – Springer Berlin Heidelberg, 2002. – С. 166-177.]</ref> <ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.187.3017&rep=rep1&type=pdf  Hamerly G. Making k-means Even Faster //SDM. – 2010. – С. 130-140.]</ref> <ref>[http://cseweb.ucsd.edu/~elkan/kmeansicml03.pdf  Elkan C. Using the triangle inequality to accelerate k-means //ICML. – 2003. – Т. 3. – С. 147-153.]</ref>
  
 
=== Последовательная сложность алгоритма ===
 
=== Последовательная сложность алгоритма ===

Версия 20:07, 14 октября 2016

Авторы страницы: Валуйская Я.А., Глотов Е.С.

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],


Алгоритм состоит из следующих шагов:

  1. Инициализация центров масс
    На данном шаге задаются начальные значения центров масс [math] \mu_1^1, ..., \mu_k^1[/math]. Существует несколько способов их выбора. Они будут рассмотрены ниже.
  2. t-ый шаг итерации:
    • Распределение векторов по кластерам
      На данном шаге каждый вектор [math]x \in X[/math] распределяется в свой кластер [math]S_i^t[/math] так, что:
      [math]l_i^t = \arg \min_{j} (d(x, \mu_j^t))^2 , j = 1, ..., k[/math]
    • Пересчет центров масс кластеров
      На данном шаге происходит пересчет центров масс кластеров, полученных на предыдущем этапе:
      [math]\mu_i^{t+1} = \frac{1}{|S_i^t|} \sum_{x \in S_i^t} x[/math]
  3. Критерий останова
    [math]\mu_i^t = \mu_i^{t+1},[/math] для всех [math]i = 1, ..., k[/math]


Способы инициализации начальных данных:

  1. Метод Forgy
    Случайным образом выбираются [math]k[/math] векторов из множества наблюдений [math]X[/math]. Эти вектора используются в качестве центров масс кластеров [math]\mu_1, ..., \mu_k[/math]
  2. Метод случайного разбиения (Random Partition) [4]
    Каждый вектор [math]x_i, i = 1, .., n[/math] случайным образом распределяется в кластер [math]S_j, j = 1, .., k[/math], затем для каждого кластера вычисляется его центр масс [math]\mu_j[/math].

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

Вычислительном ядром алгоритма является шаг 2, состоящий из следующих этапов:

  1. распределение векторов по кластерам;
  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 Макроструктура алгоритма

  1. Макрооперация "Расстояние между векторами"
    В данном алгоритме используется Евклидова метрика:
    [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];
  2. Макрооперация "Пересчет центра масс кластера"
    [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 Последовательная сложность алгоритма

Подсчитаем количество операций для каждого шага алгоритма.

  1. Инициализация:
    • Метод Forgy: [math]N_{init} = 0[/math]
    • Метод случайного разбиения:
      • Количество операций деления: [math]N^{/}_{init} = k * d[/math];
      • Количество операций сложения: [math]N^{+}_{init} = d * (n - k)[/math].
  2. Распределение [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].
  3. Пересчет центра масс [math]\mu_i \in R^d[/math] для [math]k[/math] кластеров на одной итерации:
    • Количество операций деления: [math]N^{/}_{centr} = k * d[/math];
    • Количество операций сложения: [math]N^{+}_{centr} = d * (n - k)[/math].

Следовательно, в случае если алгоритм сошелся за [math]i[/math] итераций, получаем:

  • Операций сложения/вычитания: [math]N^{+,-}_{k-means} = N^{+}_{init} + i*(N^{+}_{distr} + N^{-}_{distr} + N^{+}_{centr}) = 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^{/}_{centr}) = 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 Информационный граф

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

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 Свойства алгоритма

Достоинства
  1. Алгоритм прозрачный и понятный, за счет чего очень прост в реализации;
  2. Алгоритм имеет высокую скорость работы в случае выбора оптимальных начальных значений центров масс кластеров.
Недостатки
  1. Число кластеров является входным аргументом алгоритма. Таким образом, некорректный выбор данного параметра может привести к плохим результатам работы алгоритма, поэтому очень важно проводить диагностические прогоны для подбора оптимального количества кластеров;
  2. Алгоритм может сойтись к локальному минимуму (достижение глобального минимума не гарантируется);
  3. Результат сильно зависит от выбора начальных значений центров масс кластеров. Существует улучшенная версия алгоритма - 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 Литература