Уровень алгоритма

Участник:Илья Егоров/Алгоритм k-средних: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 121: Строка 121:
  
 
== Существующие реализации алгоритма ==
 
== Существующие реализации алгоритма ==
 +
 +
=== Бесплатный доступ ===
 +
 +
'''Десктопные программы'''
 +
 +
* [http://www.cs.waikato.ac.nz/ml/weka/ Weka]
 +
* [http://docs.orange.biolab.si/2/reference/rst/Orange.clustering.kmeans.html Orange]
 +
 +
'''Фреймворки для языков'''
 +
 +
* '''Python:'''
 +
** [http://scikit-learn.org/ scikit-learn]
 +
** [https://www.scipy.org/ SciPy]
 +
* '''C++:'''
 +
** [http://mlpack.org/ MLPACK]
 +
** [http://docs.opencv.org/3.0-beta/doc/py_tutorials/py_ml/py_kmeans/py_kmeans_opencv/py_kmeans_opencv.html OpenCV]
 +
** [https://www.gnu.org/software/octave/ Octave]
 +
* '''C#:''' 
 +
** [http://accord-framework.net/docs/html/T_Accord_MachineLearning_KMeans.htm Accord.NET]
 +
* '''Java:'''
 +
** [http://elki.dbs.ifi.lmu.de ELKI]
 +
** [https://mahout.apache.org Mahout]
 +
* '''Lua'''
 +
** [http://torch.ch Torch]
 +
 +
Языки [https://www.r-bloggers.com/k-means-clustering-in-r/ R] и [http://juliastats.github.io Julia] содержат алгоритм k-means в базовой реализации.
 +
 +
=== Платный доступ/лицензия  ===
 +
 +
Существует целый перечень мощных статистических и математических пакетов для разных ОС:
 +
* [http://www.mathworks.com/help/stats/kmeans.html?requestedDomain=www.mathworks.com MATLAB]
 +
* [http://mathworld.wolfram.com/K-MeansClusteringAlgorithm.html Mathematica]
 +
* [http://www.stata.com/features/cluster-analysis/ Stata]
 +
* [https://support.sas.com/rnd/app/stat/procedures/fastclus.html SAS]
 +
* [https://blogs.sap.com/2013/03/28/sap-hana-pal-k-means-algorithm-or-how-to-do-customer-segmentation-for-the-telecommunications-industry/ SAP HANA]
 +
* [http://docs.rapidminer.com/studio/operators/modeling/segmentation/k_means.html RapidMiner]
 +
* ...
  
 
= Литература =
 
= Литература =

Версия 21:34, 14 октября 2016


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


Страница создана группой "Илья Егоров — Евгений Богомазов"


1 ЧАСТЬ. Свойства и структура алгоритмов

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

Алгоритм кластеризации k-средних впервые был предложен в 1950-х годах математиками Гуго Штейнгаузом и Стюартом Ллойдом независимо друг от друга. Наибольшую популярность он получил после работы Маккуина.

Алгоритм позволяет при заданном числе [math]k[/math] построить [math]k[/math] кластеров, расположенных на максимальном расстоянии друг от друга. Таким образом, наибольшей точности результат выполнения алгоритма достигает при полной осведомленности Пользователя о характере кластеризуемых объектов и, как следствие, при обладании максимально корректной информацией о числе кластеров.

В общем случае выбор числа [math]k[/math] может базироваться на любых значимых факторах, в том числе на результатах предшествующих исследований, теоретических соображениях или интуиции.

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

Исходные данные:

  • Совокупность n d-мерных векторов [math] X = \{x_1 \dots x_n\} , [/math] где [math] x_i = \{x_{i1} \dots x_{id}\} [/math]
  • Предполагаемое количество кластеров k

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

  • Разбиение X на множество [math] S = \{S_1 \dots S_k \}, \bigcup S_i = X, S_i \cap S_j = \emptyset, i \neq j [/math]
  • k центров кластеров [math] \Mu = \{\mu_1 \dots \mu_k \} [/math], где [math] \mu_i = \{\mu_{i1} \dots \mu_{id} \} [/math] такие, что

[math] \begin{cases}\mu_i = argmin_y \sum_{x \in S_i} ||x-y||^2_E \\ \mu_i = argmin_\Mu \sum_{i \in k} \sum_{x \in S_i} ||x-\mu_i||^2_E \end{cases} [/math]

Алгоритм:

1) [math] \mu_{ij} = random [/math]

2) [math] S_i = \{x| argmin_j ||x-\mu_j|| = i\} i = 1 \dots k [/math]

3) [math] \tilde{\mu_{i}} = E_{x \in S_i}(x) [/math]

4) Если для [math] \forall i: \mu_i = \tilde{\mu_i} [/math] то алгоритм завершен, иначе [math] \mu_i = \tilde{\mu_i} [/math] и перейти на пункт 2)

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

Вычислительным ядром алгоритма является второй этап, а точнее нахождение матрицы расстояний между [math]X[/math] и [math]\Mu[/math]. Для d-мерного вектора [math]a:[/math]

[math]||a||=\sqrt{\sum_{i=1\dots d} a_i^2}[/math], поэтому заполнение одной ячейки такой матрицы потребует [math]d[/math] операций умножения, [math]d-1[/math] операций сложения и одну операция вычисления квадратного корня. Но так как эти расстояния используются только для сравнения, а sqrt является монотонно возрастающей функцией, то ее можно не вычислять. Поэтому нахождения матрицы расстояний потребует всего [math]n*k*d[/math] операций умножений и [math]n*k*(d-1)[/math] операций сложений.

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

Алгоритм k-средних базируется на алгоритме вычисления расстояния между векторами, расстояние на каждом шаге высчитывается [math]k\cdot n[/math] раз.

Помимо этого, в конце каждого шага вычисляется центр масс объектов кластера, для всех объектов потребуется [math]n-1[/math] суммирование и [math]k[/math] делений.

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

Последовательность шагов алгоритма следующая:

   1. Инициализация центроидов [math]\Mu[/math], [math] iter = 1 [/math], задание максимального количество итераций [math]maxiter[/math]
       
   2a. Нахождение матрицы расстояний [math]dist:[/math]
   
       [math]dist_{ij} = \sum_{l = 1\dots d} (x_{il}-\mu_{il})^2[/math]
       
   2b. Нахождение вектора распределения объектов по кластерам [math]index: [/math]
   
       [math]index_{i} =   \underset{j}{argmin }~dist_{ij} [/math]
   
   3. Пересчет центроидов [math]\tilde{\Mu}:[/math]
   
       [math]\tilde{\mu_{ij}} = \sum_{l \in T_i} \dfrac{x_{lj}}{|T_i|} [/math], где [math]T_i = \{l~|~l \in 1\dots n, index_l = i\}  [/math]
   
   4. Проверка критерия останова:
   
       Если [math] \exists i: \tilde{\mu_i} \neq \mu_i[/math], [math] iter \lt  maxiter [/math],
   
       то [math] inc(iter), \Mu=\tilde{\Mu},[/math] GOTO 2.а.

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

   1) Сложность инициализации в общем случае зависит от применяемого метода генерации/получения случайных чисел, но ей можно пренебречь
   
   2a) Вычисление матрицы расстояний требует [math] n*k*d [/math] операций умножений и [math] n*k*(d-1) [/math] операций сложений
   
   2b) Нахождение вектора распределения требует [math] n*(k-1) [/math] операций сравнений
   
   3) Для вычисления [math] \tilde{\Mu} [/math] требуется [math] (n - k + 1) * d [/math] операций сложений и [math] k * d [/math] операций деления
   
   4) Для критерия останова требуется [math] n*d [/math] сравнений

Итого: так как максимальное количество итераций задается в алгоритме заранее и не зависит от входных данных, то количество итераций ограничено константой. Тогда сложность алгоритма:

  • [math] O(n*k*d)[/math] операций сложений/вычитаний
  • [math] O(n*k*d)[/math] операций умножений, [math] O(k*d) [/math] операций делений

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

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

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

Входные данные: Количество кластеров k, n кластеризуемых элементов

Дополнительные ограничения:

  • k — положительное число, т. е. k > 0.
  • Для кластеризуемых элементов определена метрика (расстояние между объектами)

Объём входных данных: n [math]\cdot[/math] d + 1 (кластеризуемые объекты в виде векторов и число k)

Выходные данные: Массив, в который записаны принадлежности каждого элемента кластеру (допустим вывод в другой эквивалентной более удобной структуре).

Объём выходных данных: Размер массива равен 2 [math]\cdot[/math] n.

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

Вычислительная мощность алгоритма на каждом шаге равна [math]k\cdot n[/math] (расстояние между элементом и центроидом [math]k\cdot n[/math] раз)

2 ЧАСТЬ. Программная реализация алгоритма

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

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

2.2.1 Бесплатный доступ

Десктопные программы

Фреймворки для языков

Языки R и Julia содержат алгоритм k-means в базовой реализации.

2.2.2 Платный доступ/лицензия

Существует целый перечень мощных статистических и математических пакетов для разных ОС:

3 Литература

[1] Нейский И.М. Классификация и сравнение методов кластеризации http://it-claim.ru/Persons/Neyskiy/Article2_Neiskiy.pdf

[2] https://ru.wikipedia.org/wiki/K-means