Алговики - Вклад [ru]

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

2016-10-15T20:57:40Z

Богомазов Евгений: /* Математическое описание алгоритма */

{{algorithm
| name = Алгоритм k-средних (k-means)
| serial_complexity = <math>O(n*k*d)</math>
| input_data = <math>n*d</math>
| output_data = <math>n</math>
}}

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

= ЧАСТЬ. Свойства и структура алгоритмов =
== Общее описание алгоритма ==

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

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

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

== Математическое описание алгоритма ==
'''Исходные данные:'''
* Совокупность 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}\tilde{\mu_i} = \underset{y}{argmin } \sum_{x \in S_i} ||x-y||^2_E \\ \Mu = \underset{\tilde{\Mu}}{argmin } \sum_{i \in k} \sum_{x \in S_i} ||x-\tilde{\mu_i}||^2_E \end{cases} </math>

'''Алгоритм:'''

1) <math> \mu_{i} = random </math>

2) <math> S_i = \{x \in S~|~\underset{j}{argmin } ||x-\mu_j||_E = 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)

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

Вычислительным ядром алгоритма является второй этап, а точнее нахождение матрицы расстояний между <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)''' На шаге инициализации центроидов в общем случае (случайный выбор элементов) макроопераций не производится. Но так как правило определения количества кластеров '''k''' неоднозначно, то для некоторых вариантов макрооперации могут понадобиться. К примеру, существует класс стратегий поиска '''k''', которые базируются на определении центра масс всех объектов, и для которых будут дополнительно выполняться макрооперации '''"Суммирование векторов"''' и '''"Деление вектора на скаляр"'''.

'''2a)''' При составлении матрицы расстояний ''' k <math> \cdot </math> n''' раз производится макрооперация '''"Вычисление расстояния между векторами"'''.

'''2b)''' При нахождение вектора распределения объектов по кластерам '''n''' раз производится макрооперация '''"Поиск минимума в векторе"'''.

'''3)''' При пересчете центроидов '''n - k''' раз производится макрооперация '''"Суммирование векторов"''' и '''k''' раз - '''"Деление вектора на скаляр"'''.

'''4)''' Для проверки критерия останова требуется '''k''' раз произвести макрооперацию '''"Сравнение векторов"''' для сопоставления обновленных значений центроидов с уже имеющимися.

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

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

'''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_{jl})^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 S_i} \dfrac{x_{lj}}{|S_i|} </math>, где <math>S_i = \{l~|~l \in 1\dots n, index_l = i\} </math>

'''4) Проверка критерия останова:'''

'''Если''' <math> \exists i: \tilde{\mu_i} \neq \mu_i</math>, <math> iter < maxiter </math>,

'''то''' <math> inc(iter), \Mu=\tilde{\Mu},</math> '''GOTO 2.а.'''

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

'''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> операций деления

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

Рассмотрим вычислительные этапы алгоритма k-means. Это распределение объектов по кластерам и перерасчет центроидов.

Распределение объектов по кластерам состоит из нахождения матрицы расстояний между <math>X</math> и <math>\Mu</math> (этапа '''2a)''') и нахождения индекса минимального элемента в каждой строке (этап '''2b)'''). Ниже приведен информационный граф данного этапа.

[[Файл:EgorovBogomazovInf.png |800px|thumb|center|Нахождение вектора индексов распределения по кластерам]]

Рассмотрим этап вычисления ячейки <math> dist_{ij} </math> матрицы более подробно. Он представляет из себя скалярное произведение d-мерных векторов <math> x_i </math> и <math> \mu_j </math>. Ниже приведена граф для данной операции.

[[Файл:EgorovBogomazovDist.png|600px|thumb|center|Операция вычисления расстояния]]

На этапе '''3)''' происходит суммирование всех <math> x_l </math> с одинаковым значением индекса в промежуточные суммы. Одновременно происходит подсчет количество элементов с фиксированным индексом. Затем происходит деление промежуточных сумм на соответствующее количество элементов в новом кластере, благодаря чему удается получить обновленные центроиды <math> \tilde{\mu}</math>

[[Файл:EgorovBogomazovNewCluster.png|800px|thumb|center|Обновление центроидов]]

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

Для получения общей картины достаточно определить, в том числе и с помощью информационного графа, каким ресурсом параллелизма обладает каждый из этапов алгоритма:

'''2a)''' Нахождение каждой ячейки матрицы <math> dist </math> может происходить полностью независимо, так как они находятся на одном ярусе. При рассмотрении операции вычисления значения конкретной ячейки <math> dist_{ij} </math> можно заметить, что все операции умножения также независимы между собой, поэтому понадобится всего одно умножение. Конечный результат получается в результате суммирования всех слагаемых и достигается параллельно за <math> \log(d) </math> бинарных операций сложения при помощи стандартного метода ''reduction''.

'''2b)''' Нахождение вектора распределений заключается в нахождении минимального элемента в каждой строке матрицы <math> dist </math>. При использовании ''reduction'' эту операцию можно выполнить за <math> \log(k) </math> бинарных операций сравнения.

'''3)''' В случае, если существует методология быстрого разделения '''n''' объектов на '''k''' множеств при помощи вектора индексации (косвенной адресации), все <math> \tilde{S_i} </math> могут быть обработаны параллельно. В рамках каждого отдельного <math> \tilde{S_i} </math> можно проводить распараллеливание дальше, так как <math> x_{lj} </math> также не зависят друг от друга. Таким образом, вычисление всех слагаемых для всех <math> \tilde{\mu_{ij}} </math> может быть выполнено за одно параллельное деление, а нахождение суммы всех этих слагаемых для каждого <math> \tilde{\mu_{ij}} </math> может быть выполнено за <math> O(log(n)) </math> в худшем случае (при вхождении почти всех объектов в один кластер).

Если же такой методологии не существует, то узким местом становится процесс распределения на множества согласно вектору <math>index</math>, который можно выполнить за <math> n </math> операций косвенных адресаций.

'''4)''' Все сравнения для критерия останова также независимы между собой и могут быть выполнены за одну операцию сравнения, а финальный результат может быть получен за одну операцию сложения при работе над общей памятью (к примеру, прибавление единицы при несовпадении в общую память и сравнение ее с 0 по завершению) или за <math>\log(k*d)</math> сложений иначе.

Так как количество итераций ограничено константой, то на сложность оно не влияет. В итоге, параллельная сложность алгоритма k-means такова:
* <math> O(\log(n*d)) </math> операций сложения
* <math> O(\log(k)) </math> операций сравнения
* <math> O(1) </math> операций умножения и деления

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

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

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

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

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

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

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

'''Ограничения алгоритма'''

Алгоритм эффективно работает только на небольших объемах данных.

'''Преимущества алгоритма'''
* Простота использования
* Быстрота использования
* Понятность и прозрачность описания
* Обладает вычислительной устойчивостью
* Предрасположенность к распараллеливанию
* Достаточно популярный, поэтому имеет множество реализаций и вариаций

'''Недостатки алгоритма'''

* Нет проверки корректности выбора числа кластеров
* Алгоритм чувствителен к количеству кластеров
* Алгоритм чувствителен к выбору начальных элементов в качестве центроидов
* Алгоритм крайне чувствителен к выбросам по данным
* Медленная работа на больших объемах данных

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

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

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

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

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

* [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]
* ...

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

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

[[en:Description of algorithm properties and structure]]

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

2016-10-15T20:56:15Z

Богомазов Евгений: /* Информационный граф */

{{algorithm
| name = Алгоритм k-средних (k-means)
| serial_complexity = <math>O(n*k*d)</math>
| input_data = <math>n*d</math>
| output_data = <math>n</math>
}}

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

= ЧАСТЬ. Свойства и структура алгоритмов =
== Общее описание алгоритма ==

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

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

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

== Математическое описание алгоритма ==
'''Исходные данные:'''
* Совокупность 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}\tilde{\mu_i} = \underset{y}{argmin } \sum_{x \in S_i} ||x-y||^2_E \\ \Mu = \underset{\tilde{\Mu}}{argmin } \sum_{i \in k} \sum_{x \in S_i} ||x-\tilde{\mu_i}||^2_E \end{cases} </math>

'''Алгоритм:'''

1) <math> \mu_{i} = random </math>

2) <math> S_i = \{x \in S | \underset{j}{argmin } ||x-\mu_j||_E = 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)

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

Вычислительным ядром алгоритма является второй этап, а точнее нахождение матрицы расстояний между <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)''' На шаге инициализации центроидов в общем случае (случайный выбор элементов) макроопераций не производится. Но так как правило определения количества кластеров '''k''' неоднозначно, то для некоторых вариантов макрооперации могут понадобиться. К примеру, существует класс стратегий поиска '''k''', которые базируются на определении центра масс всех объектов, и для которых будут дополнительно выполняться макрооперации '''"Суммирование векторов"''' и '''"Деление вектора на скаляр"'''.

'''2a)''' При составлении матрицы расстояний ''' k <math> \cdot </math> n''' раз производится макрооперация '''"Вычисление расстояния между векторами"'''.

'''2b)''' При нахождение вектора распределения объектов по кластерам '''n''' раз производится макрооперация '''"Поиск минимума в векторе"'''.

'''3)''' При пересчете центроидов '''n - k''' раз производится макрооперация '''"Суммирование векторов"''' и '''k''' раз - '''"Деление вектора на скаляр"'''.

'''4)''' Для проверки критерия останова требуется '''k''' раз произвести макрооперацию '''"Сравнение векторов"''' для сопоставления обновленных значений центроидов с уже имеющимися.

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

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

'''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_{jl})^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 S_i} \dfrac{x_{lj}}{|S_i|} </math>, где <math>S_i = \{l~|~l \in 1\dots n, index_l = i\} </math>

'''4) Проверка критерия останова:'''

'''Если''' <math> \exists i: \tilde{\mu_i} \neq \mu_i</math>, <math> iter < maxiter </math>,

'''то''' <math> inc(iter), \Mu=\tilde{\Mu},</math> '''GOTO 2.а.'''

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

'''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> операций деления

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

Рассмотрим вычислительные этапы алгоритма k-means. Это распределение объектов по кластерам и перерасчет центроидов.

Распределение объектов по кластерам состоит из нахождения матрицы расстояний между <math>X</math> и <math>\Mu</math> (этапа '''2a)''') и нахождения индекса минимального элемента в каждой строке (этап '''2b)'''). Ниже приведен информационный граф данного этапа.

[[Файл:EgorovBogomazovInf.png |800px|thumb|center|Нахождение вектора индексов распределения по кластерам]]

Рассмотрим этап вычисления ячейки <math> dist_{ij} </math> матрицы более подробно. Он представляет из себя скалярное произведение d-мерных векторов <math> x_i </math> и <math> \mu_j </math>. Ниже приведена граф для данной операции.

[[Файл:EgorovBogomazovDist.png|600px|thumb|center|Операция вычисления расстояния]]

На этапе '''3)''' происходит суммирование всех <math> x_l </math> с одинаковым значением индекса в промежуточные суммы. Одновременно происходит подсчет количество элементов с фиксированным индексом. Затем происходит деление промежуточных сумм на соответствующее количество элементов в новом кластере, благодаря чему удается получить обновленные центроиды <math> \tilde{\mu}</math>

[[Файл:EgorovBogomazovNewCluster.png|800px|thumb|center|Обновление центроидов]]

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

Для получения общей картины достаточно определить, в том числе и с помощью информационного графа, каким ресурсом параллелизма обладает каждый из этапов алгоритма:

'''2a)''' Нахождение каждой ячейки матрицы <math> dist </math> может происходить полностью независимо, так как они находятся на одном ярусе. При рассмотрении операции вычисления значения конкретной ячейки <math> dist_{ij} </math> можно заметить, что все операции умножения также независимы между собой, поэтому понадобится всего одно умножение. Конечный результат получается в результате суммирования всех слагаемых и достигается параллельно за <math> \log(d) </math> бинарных операций сложения при помощи стандартного метода ''reduction''.

'''2b)''' Нахождение вектора распределений заключается в нахождении минимального элемента в каждой строке матрицы <math> dist </math>. При использовании ''reduction'' эту операцию можно выполнить за <math> \log(k) </math> бинарных операций сравнения.

'''3)''' В случае, если существует методология быстрого разделения '''n''' объектов на '''k''' множеств при помощи вектора индексации (косвенной адресации), все <math> \tilde{S_i} </math> могут быть обработаны параллельно. В рамках каждого отдельного <math> \tilde{S_i} </math> можно проводить распараллеливание дальше, так как <math> x_{lj} </math> также не зависят друг от друга. Таким образом, вычисление всех слагаемых для всех <math> \tilde{\mu_{ij}} </math> может быть выполнено за одно параллельное деление, а нахождение суммы всех этих слагаемых для каждого <math> \tilde{\mu_{ij}} </math> может быть выполнено за <math> O(log(n)) </math> в худшем случае (при вхождении почти всех объектов в один кластер).

Если же такой методологии не существует, то узким местом становится процесс распределения на множества согласно вектору <math>index</math>, который можно выполнить за <math> n </math> операций косвенных адресаций.

'''4)''' Все сравнения для критерия останова также независимы между собой и могут быть выполнены за одну операцию сравнения, а финальный результат может быть получен за одну операцию сложения при работе над общей памятью (к примеру, прибавление единицы при несовпадении в общую память и сравнение ее с 0 по завершению) или за <math>\log(k*d)</math> сложений иначе.

Так как количество итераций ограничено константой, то на сложность оно не влияет. В итоге, параллельная сложность алгоритма k-means такова:
* <math> O(\log(n*d)) </math> операций сложения
* <math> O(\log(k)) </math> операций сравнения
* <math> O(1) </math> операций умножения и деления

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

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

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

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

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

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

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

'''Ограничения алгоритма'''

Алгоритм эффективно работает только на небольших объемах данных.

'''Преимущества алгоритма'''
* Простота использования
* Быстрота использования
* Понятность и прозрачность описания
* Обладает вычислительной устойчивостью
* Предрасположенность к распараллеливанию
* Достаточно популярный, поэтому имеет множество реализаций и вариаций

'''Недостатки алгоритма'''

* Нет проверки корректности выбора числа кластеров
* Алгоритм чувствителен к количеству кластеров
* Алгоритм чувствителен к выбору начальных элементов в качестве центроидов
* Алгоритм крайне чувствителен к выбросам по данным
* Медленная работа на больших объемах данных

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

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

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

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

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

* [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]
* ...

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

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

[[en:Description of algorithm properties and structure]]

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

2016-10-15T20:54:13Z

Богомазов Евгений: /* Информационный граф */

{{algorithm
| name = Алгоритм k-средних (k-means)
| serial_complexity = <math>O(n*k*d)</math>
| input_data = <math>n*d</math>
| output_data = <math>n</math>
}}

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

= ЧАСТЬ. Свойства и структура алгоритмов =
== Общее описание алгоритма ==

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

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

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

== Математическое описание алгоритма ==
'''Исходные данные:'''
* Совокупность 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}\tilde{\mu_i} = \underset{y}{argmin } \sum_{x \in S_i} ||x-y||^2_E \\ \Mu = \underset{\tilde{\Mu}}{argmin } \sum_{i \in k} \sum_{x \in S_i} ||x-\tilde{\mu_i}||^2_E \end{cases} </math>

'''Алгоритм:'''

1) <math> \mu_{i} = random </math>

2) <math> S_i = \{x \in S | \underset{j}{argmin } ||x-\mu_j||_E = 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)

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

Вычислительным ядром алгоритма является второй этап, а точнее нахождение матрицы расстояний между <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)''' На шаге инициализации центроидов в общем случае (случайный выбор элементов) макроопераций не производится. Но так как правило определения количества кластеров '''k''' неоднозначно, то для некоторых вариантов макрооперации могут понадобиться. К примеру, существует класс стратегий поиска '''k''', которые базируются на определении центра масс всех объектов, и для которых будут дополнительно выполняться макрооперации '''"Суммирование векторов"''' и '''"Деление вектора на скаляр"'''.

'''2a)''' При составлении матрицы расстояний ''' k <math> \cdot </math> n''' раз производится макрооперация '''"Вычисление расстояния между векторами"'''.

'''2b)''' При нахождение вектора распределения объектов по кластерам '''n''' раз производится макрооперация '''"Поиск минимума в векторе"'''.

'''3)''' При пересчете центроидов '''n - k''' раз производится макрооперация '''"Суммирование векторов"''' и '''k''' раз - '''"Деление вектора на скаляр"'''.

'''4)''' Для проверки критерия останова требуется '''k''' раз произвести макрооперацию '''"Сравнение векторов"''' для сопоставления обновленных значений центроидов с уже имеющимися.

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

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

'''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_{jl})^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 S_i} \dfrac{x_{lj}}{|S_i|} </math>, где <math>S_i = \{l~|~l \in 1\dots n, index_l = i\} </math>

'''4) Проверка критерия останова:'''

'''Если''' <math> \exists i: \tilde{\mu_i} \neq \mu_i</math>, <math> iter < maxiter </math>,

'''то''' <math> inc(iter), \Mu=\tilde{\Mu},</math> '''GOTO 2.а.'''

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

'''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> операций деления

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

Рассмотрим вычислительные этапы алгоритма k-means. Это распределение объектов по кластерам и перерасчет центроидов.

Распределение объектов по кластерам состоит из нахождения матрицы расстояний между <math>X</math> и <math>\Mu</math> (этапа 2a) и нахождения индекса минимального элемента в каждой строке (этап 2b). Ниже приведен информационный граф данного этапа.

[[Файл:EgorovBogomazovInf.png |800px|thumb|center|Нахождение вектора индексов распределения по кластерам]]

Рассмотрим этап вычисления ячейки <math> dist_{ij} </math> матрицы более подробно. Он представляет из себя скалярное произведение d-мерных векторов <math> x_i </math> и <math> \mu_j </math>. Ниже приведена граф для данной операции.

[[Файл:EgorovBogomazovDist.png|600px|thumb|center|Операция вычисления расстояния]]

На этапе 3) происходит суммирование всех <math> x_l </math> с одинаковым значением индекса в промежуточные суммы. Одновременно происходит подсчет количество элементов с фиксированным индексом. Затем происходит деление промежуточных сумм на соответствующее количество элементов в новом кластере, благодаря чему удается получить обновленные центроиды <math> \tilde{\mu}</math>

[[Файл:EgorovBogomazovNewCluster.png|800px|thumb|center|Обновление центроидов]]

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

Для получения общей картины достаточно определить, в том числе и с помощью информационного графа, каким ресурсом параллелизма обладает каждый из этапов алгоритма:

'''2a)''' Нахождение каждой ячейки матрицы <math> dist </math> может происходить полностью независимо, так как они находятся на одном ярусе. При рассмотрении операции вычисления значения конкретной ячейки <math> dist_{ij} </math> можно заметить, что все операции умножения также независимы между собой, поэтому понадобится всего одно умножение. Конечный результат получается в результате суммирования всех слагаемых и достигается параллельно за <math> \log(d) </math> бинарных операций сложения при помощи стандартного метода ''reduction''.

'''2b)''' Нахождение вектора распределений заключается в нахождении минимального элемента в каждой строке матрицы <math> dist </math>. При использовании ''reduction'' эту операцию можно выполнить за <math> \log(k) </math> бинарных операций сравнения.

'''3)''' В случае, если существует методология быстрого разделения '''n''' объектов на '''k''' множеств при помощи вектора индексации (косвенной адресации), все <math> \tilde{S_i} </math> могут быть обработаны параллельно. В рамках каждого отдельного <math> \tilde{S_i} </math> можно проводить распараллеливание дальше, так как <math> x_{lj} </math> также не зависят друг от друга. Таким образом, вычисление всех слагаемых для всех <math> \tilde{\mu_{ij}} </math> может быть выполнено за одно параллельное деление, а нахождение суммы всех этих слагаемых для каждого <math> \tilde{\mu_{ij}} </math> может быть выполнено за <math> O(log(n)) </math> в худшем случае (при вхождении почти всех объектов в один кластер).

Если же такой методологии не существует, то узким местом становится процесс распределения на множества согласно вектору <math>index</math>, который можно выполнить за <math> n </math> операций косвенных адресаций.

'''4)''' Все сравнения для критерия останова также независимы между собой и могут быть выполнены за одну операцию сравнения, а финальный результат может быть получен за одну операцию сложения при работе над общей памятью (к примеру, прибавление единицы при несовпадении в общую память и сравнение ее с 0 по завершению) или за <math>\log(k*d)</math> сложений иначе.

Так как количество итераций ограничено константой, то на сложность оно не влияет. В итоге, параллельная сложность алгоритма k-means такова:
* <math> O(\log(n*d)) </math> операций сложения
* <math> O(\log(k)) </math> операций сравнения
* <math> O(1) </math> операций умножения и деления

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

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

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

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

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

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

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

'''Ограничения алгоритма'''

Алгоритм эффективно работает только на небольших объемах данных.

'''Преимущества алгоритма'''
* Простота использования
* Быстрота использования
* Понятность и прозрачность описания
* Обладает вычислительной устойчивостью
* Предрасположенность к распараллеливанию
* Достаточно популярный, поэтому имеет множество реализаций и вариаций

'''Недостатки алгоритма'''

* Нет проверки корректности выбора числа кластеров
* Алгоритм чувствителен к количеству кластеров
* Алгоритм чувствителен к выбору начальных элементов в качестве центроидов
* Алгоритм крайне чувствителен к выбросам по данным
* Медленная работа на больших объемах данных

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

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

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

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

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

* [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]
* ...

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

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

[[en:Description of algorithm properties and structure]]

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

2016-10-15T20:46:21Z

Богомазов Евгений: /* Схема реализации последовательного алгоритма */

{{algorithm
| name = Алгоритм k-средних (k-means)
| serial_complexity = <math>O(n*k*d)</math>
| input_data = <math>n*d</math>
| output_data = <math>n</math>
}}

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

= ЧАСТЬ. Свойства и структура алгоритмов =
== Общее описание алгоритма ==

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

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

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

== Математическое описание алгоритма ==
'''Исходные данные:'''
* Совокупность 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}\tilde{\mu_i} = \underset{y}{argmin } \sum_{x \in S_i} ||x-y||^2_E \\ \Mu = \underset{\tilde{\Mu}}{argmin } \sum_{i \in k} \sum_{x \in S_i} ||x-\tilde{\mu_i}||^2_E \end{cases} </math>

'''Алгоритм:'''

1) <math> \mu_{i} = random </math>

2) <math> S_i = \{x \in S | \underset{j}{argmin } ||x-\mu_j||_E = 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)

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

Вычислительным ядром алгоритма является второй этап, а точнее нахождение матрицы расстояний между <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)''' На шаге инициализации центроидов в общем случае (случайный выбор элементов) макроопераций не производится. Но так как правило определения количества кластеров '''k''' неоднозначно, то для некоторых вариантов макрооперации могут понадобиться. К примеру, существует класс стратегий поиска '''k''', которые базируются на определении центра масс всех объектов, и для которых будут дополнительно выполняться макрооперации '''"Суммирование векторов"''' и '''"Деление вектора на скаляр"'''.

'''2a)''' При составлении матрицы расстояний ''' k <math> \cdot </math> n''' раз производится макрооперация '''"Вычисление расстояния между векторами"'''.

'''2b)''' При нахождение вектора распределения объектов по кластерам '''n''' раз производится макрооперация '''"Поиск минимума в векторе"'''.

'''3)''' При пересчете центроидов '''n - k''' раз производится макрооперация '''"Суммирование векторов"''' и '''k''' раз - '''"Деление вектора на скаляр"'''.

'''4)''' Для проверки критерия останова требуется '''k''' раз произвести макрооперацию '''"Сравнение векторов"''' для сопоставления обновленных значений центроидов с уже имеющимися.

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

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

'''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_{jl})^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 S_i} \dfrac{x_{lj}}{|S_i|} </math>, где <math>S_i = \{l~|~l \in 1\dots n, index_l = i\} </math>

'''4) Проверка критерия останова:'''

'''Если''' <math> \exists i: \tilde{\mu_i} \neq \mu_i</math>, <math> iter < maxiter </math>,

'''то''' <math> inc(iter), \Mu=\tilde{\Mu},</math> '''GOTO 2.а.'''

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

'''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> операций деления

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

Рассмотрим вычислительные этапы алгоритма k-means. Это распределение объектов по кластерам и перерасчет центроидов.

Распределение объектов по кластерам состоит из нахождения матрицы расстояний между <math>X</math> и <math>\Mu</math> (этапа 2a) и нахождения индекса минимального элемента в каждой строке (этап 2b). Ниже приведен информационный граф данного этапа.

'''Picture_1.png'''

Рассмотрим этап вычисления ячейки <math> dist_{ij} </math> матрицы более подробно. Он представляет из себя скалярное произведение d-мерных векторов <math> x_i </math> и <math> \mu_j </math>. Ниже приведена граф для данной операции.

'''Picture_2.png'''

На этапе 3) происходит суммирование всех <math> x_l </math> с одинаковым значением индекса в промежуточные суммы. Одновременно происходит подсчет количество элементов с фиксированным индексом. Затем происходит деление промежуточных сумм на соответствующее количество элементов в новом кластере, благодаря чему удается получить обновленные центроиды <math> \tilde{\mu}</math>

'''Picture_3.png'''

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

Для получения общей картины достаточно определить, в том числе и с помощью информационного графа, каким ресурсом параллелизма обладает каждый из этапов алгоритма:

'''2a)''' Нахождение каждой ячейки матрицы <math> dist </math> может происходить полностью независимо, так как они находятся на одном ярусе. При рассмотрении операции вычисления значения конкретной ячейки <math> dist_{ij} </math> можно заметить, что все операции умножения также независимы между собой, поэтому понадобится всего одно умножение. Конечный результат получается в результате суммирования всех слагаемых и достигается параллельно за <math> \log(d) </math> бинарных операций сложения при помощи стандартного метода ''reduction''.

'''2b)''' Нахождение вектора распределений заключается в нахождении минимального элемента в каждой строке матрицы <math> dist </math>. При использовании ''reduction'' эту операцию можно выполнить за <math> \log(k) </math> бинарных операций сравнения.

'''3)''' В случае, если существует методология быстрого разделения '''n''' объектов на '''k''' множеств при помощи вектора индексации (косвенной адресации), все <math> \tilde{S_i} </math> могут быть обработаны параллельно. В рамках каждого отдельного <math> \tilde{S_i} </math> можно проводить распараллеливание дальше, так как <math> x_{lj} </math> также не зависят друг от друга. Таким образом, вычисление всех слагаемых для всех <math> \tilde{\mu_{ij}} </math> может быть выполнено за одно параллельное деление, а нахождение суммы всех этих слагаемых для каждого <math> \tilde{\mu_{ij}} </math> может быть выполнено за <math> O(log(n)) </math> в худшем случае (при вхождении почти всех объектов в один кластер).

Если же такой методологии не существует, то узким местом становится процесс распределения на множества согласно вектору <math>index</math>, который можно выполнить за <math> n </math> операций косвенных адресаций.

'''4)''' Все сравнения для критерия останова также независимы между собой и могут быть выполнены за одну операцию сравнения, а финальный результат может быть получен за одну операцию сложения при работе над общей памятью (к примеру, прибавление единицы при несовпадении в общую память и сравнение ее с 0 по завершению) или за <math>\log(k*d)</math> сложений иначе.

Так как количество итераций ограничено константой, то на сложность оно не влияет. В итоге, параллельная сложность алгоритма k-means такова:
* <math> O(\log(n*d)) </math> операций сложения
* <math> O(\log(k)) </math> операций сравнения
* <math> O(1) </math> операций умножения и деления

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

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

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

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

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

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

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

'''Ограничения алгоритма'''

Алгоритм эффективно работает только на небольших объемах данных.

'''Преимущества алгоритма'''
* Простота использования
* Быстрота использования
* Понятность и прозрачность описания
* Обладает вычислительной устойчивостью
* Предрасположенность к распараллеливанию
* Достаточно популярный, поэтому имеет множество реализаций и вариаций

'''Недостатки алгоритма'''

* Нет проверки корректности выбора числа кластеров
* Алгоритм чувствителен к количеству кластеров
* Алгоритм чувствителен к выбору начальных элементов в качестве центроидов
* Алгоритм крайне чувствителен к выбросам по данным
* Медленная работа на больших объемах данных

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

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

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

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

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

* [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]
* ...

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

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

[[en:Description of algorithm properties and structure]]

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

2016-10-15T20:42:18Z

Богомазов Евгений: /* Информационный граф */

{{algorithm
| name = Алгоритм k-средних (k-means)
| serial_complexity = <math>O(n*k*d)</math>
| input_data = <math>n*d</math>
| output_data = <math>n</math>
}}

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

= ЧАСТЬ. Свойства и структура алгоритмов =
== Общее описание алгоритма ==

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

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

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

== Математическое описание алгоритма ==
'''Исходные данные:'''
* Совокупность 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}\tilde{\mu_i} = \underset{y}{argmin } \sum_{x \in S_i} ||x-y||^2_E \\ \Mu = \underset{\tilde{\Mu}}{argmin } \sum_{i \in k} \sum_{x \in S_i} ||x-\tilde{\mu_i}||^2_E \end{cases} </math>

'''Алгоритм:'''

1) <math> \mu_{i} = random </math>

2) <math> S_i = \{x \in S | \underset{j}{argmin } ||x-\mu_j||_E = 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)

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

Вычислительным ядром алгоритма является второй этап, а точнее нахождение матрицы расстояний между <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)''' На шаге инициализации центроидов в общем случае (случайный выбор элементов) макроопераций не производится. Но так как правило определения количества кластеров '''k''' неоднозначно, то для некоторых вариантов макрооперации могут понадобиться. К примеру, существует класс стратегий поиска '''k''', которые базируются на определении центра масс всех объектов, и для которых будут дополнительно выполняться макрооперации '''"Суммирование векторов"''' и '''"Деление вектора на скаляр"'''.

'''2a)''' При составлении матрицы расстояний ''' k <math> \cdot </math> n''' раз производится макрооперация '''"Вычисление расстояния между векторами"'''.

'''2b)''' При нахождение вектора распределения объектов по кластерам '''n''' раз производится макрооперация '''"Поиск минимума в векторе"'''.

'''3)''' При пересчете центроидов '''n - k''' раз производится макрооперация '''"Суммирование векторов"''' и '''k''' раз - '''"Деление вектора на скаляр"'''.

'''4)''' Для проверки критерия останова требуется '''k''' раз произвести макрооперацию '''"Сравнение векторов"''' для сопоставления обновленных значений центроидов с уже имеющимися.

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

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

'''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_{jl})^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 \tilde{S_i}} \dfrac{x_{lj}}{|\tilde{S_i}|} </math>, где <math>\tilde{S_i} = \{l~|~l \in 1\dots n, index_l = i\} </math>

'''4) Проверка критерия останова:'''

'''Если''' <math> \exists i: \tilde{\mu_i} \neq \mu_i</math>, <math> iter < maxiter </math>,

'''то''' <math> inc(iter), \Mu=\tilde{\Mu},</math> '''GOTO 2.а.'''

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

'''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> операций деления

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

Рассмотрим вычислительные этапы алгоритма k-means. Это распределение объектов по кластерам и перерасчет центроидов.

Распределение объектов по кластерам состоит из нахождения матрицы расстояний между <math>X</math> и <math>\Mu</math> (этапа 2a) и нахождения индекса минимального элемента в каждой строке (этап 2b). Ниже приведен информационный граф данного этапа.

'''Picture_1.png'''

Рассмотрим этап вычисления ячейки <math> dist_{ij} </math> матрицы более подробно. Он представляет из себя скалярное произведение d-мерных векторов <math> x_i </math> и <math> \mu_j </math>. Ниже приведена граф для данной операции.

'''Picture_2.png'''

На этапе 3) происходит суммирование всех <math> x_l </math> с одинаковым значением индекса в промежуточные суммы. Одновременно происходит подсчет количество элементов с фиксированным индексом. Затем происходит деление промежуточных сумм на соответствующее количество элементов в новом кластере, благодаря чему удается получить обновленные центроиды <math> \tilde{\mu}</math>

'''Picture_3.png'''

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

Для получения общей картины достаточно определить, в том числе и с помощью информационного графа, каким ресурсом параллелизма обладает каждый из этапов алгоритма:

'''2a)''' Нахождение каждой ячейки матрицы <math> dist </math> может происходить полностью независимо, так как они находятся на одном ярусе. При рассмотрении операции вычисления значения конкретной ячейки <math> dist_{ij} </math> можно заметить, что все операции умножения также независимы между собой, поэтому понадобится всего одно умножение. Конечный результат получается в результате суммирования всех слагаемых и достигается параллельно за <math> \log(d) </math> бинарных операций сложения при помощи стандартного метода ''reduction''.

'''2b)''' Нахождение вектора распределений заключается в нахождении минимального элемента в каждой строке матрицы <math> dist </math>. При использовании ''reduction'' эту операцию можно выполнить за <math> \log(k) </math> бинарных операций сравнения.

'''3)''' В случае, если существует методология быстрого разделения '''n''' объектов на '''k''' множеств при помощи вектора индексации (косвенной адресации), все <math> \tilde{S_i} </math> могут быть обработаны параллельно. В рамках каждого отдельного <math> \tilde{S_i} </math> можно проводить распараллеливание дальше, так как <math> x_{lj} </math> также не зависят друг от друга. Таким образом, вычисление всех слагаемых для всех <math> \tilde{\mu_{ij}} </math> может быть выполнено за одно параллельное деление, а нахождение суммы всех этих слагаемых для каждого <math> \tilde{\mu_{ij}} </math> может быть выполнено за <math> O(log(n)) </math> в худшем случае (при вхождении почти всех объектов в один кластер).

Если же такой методологии не существует, то узким местом становится процесс распределения на множества согласно вектору <math>index</math>, который можно выполнить за <math> n </math> операций косвенных адресаций.

'''4)''' Все сравнения для критерия останова также независимы между собой и могут быть выполнены за одну операцию сравнения, а финальный результат может быть получен за одну операцию сложения при работе над общей памятью (к примеру, прибавление единицы при несовпадении в общую память и сравнение ее с 0 по завершению) или за <math>\log(k*d)</math> сложений иначе.

Так как количество итераций ограничено константой, то на сложность оно не влияет. В итоге, параллельная сложность алгоритма k-means такова:
* <math> O(\log(n*d)) </math> операций сложения
* <math> O(\log(k)) </math> операций сравнения
* <math> O(1) </math> операций умножения и деления

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

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

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

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

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

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

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

'''Ограничения алгоритма'''

Алгоритм эффективно работает только на небольших объемах данных.

'''Преимущества алгоритма'''
* Простота использования
* Быстрота использования
* Понятность и прозрачность описания
* Обладает вычислительной устойчивостью
* Предрасположенность к распараллеливанию
* Достаточно популярный, поэтому имеет множество реализаций и вариаций

'''Недостатки алгоритма'''

* Нет проверки корректности выбора числа кластеров
* Алгоритм чувствителен к количеству кластеров
* Алгоритм чувствителен к выбору начальных элементов в качестве центроидов
* Алгоритм крайне чувствителен к выбросам по данным
* Медленная работа на больших объемах данных

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

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

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

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

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

* [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]
* ...

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

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

[[en:Description of algorithm properties and structure]]

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

2016-10-15T16:03:18Z

Богомазов Евгений: /* Математическое описание алгоритма */

{{algorithm
| name = Алгоритм k-средних (k-means)
| serial_complexity = <math>O(n*k*d)</math>
| input_data = <math>n*d</math>
| output_data = <math>n</math>
}}

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

= ЧАСТЬ. Свойства и структура алгоритмов =
== Общее описание алгоритма ==

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

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

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

== Математическое описание алгоритма ==
'''Исходные данные:'''
* Совокупность 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}\tilde{\mu_i} = \underset{y}{argmin } \sum_{x \in S_i} ||x-y||^2_E \\ \Mu = \underset{\tilde{\Mu}}{argmin } \sum_{i \in k} \sum_{x \in S_i} ||x-\tilde{\mu_i}||^2_E \end{cases} </math>

'''Алгоритм:'''

1) <math> \mu_{i} = random </math>

2) <math> S_i = \{x \in S | \underset{j}{argmin } ||x-\mu_j||_E = 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)

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

Вычислительным ядром алгоритма является второй этап, а точнее нахождение матрицы расстояний между <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> операций сложений.

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

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

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

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

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

'''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_{jl})^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 \tilde{S_i}} \dfrac{x_{lj}}{|\tilde{S_i}|} </math>, где <math>\tilde{S_i} = \{l~|~l \in 1\dots n, index_l = i\} </math>

'''4) Проверка критерия останова:'''

'''Если''' <math> \exists i: \tilde{\mu_i} \neq \mu_i</math>, <math> iter < maxiter </math>,

'''то''' <math> inc(iter), \Mu=\tilde{\Mu},</math> '''GOTO 2.а.'''

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

'''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> операций делений

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

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

Для получения общей картины достаточно определить, в том числе и с помощью информационного графа, каким ресурсом параллелизма обладает каждый из этапов алгоритма:

'''2a)''' Нахождение каждой ячейки матрицы <math> dist </math> может происходить полностью независимо, так как они находятся на одном ярусе. При рассмотрении операции вычисления значения конкретной ячейки <math> dist_{ij} </math> можно заметить, что все операции умножения также независимы между собой, поэтому понадобится всего одно умножение. Конечный результат получается в результате суммирования всех слагаемых и достигается параллельно за <math> \log(d) </math> бинарных операций сложения при помощи стандартного метода ''reduction''.

'''2b)''' Нахождение вектора распределений заключается в нахождении минимального элемента в каждой строке матрицы <math> dist </math>. При использовании ''reduction'' эту операцию можно выполнить за <math> \log(k) </math> бинарных операций сравнения.

'''3)''' В случае, если существует методология быстрого разделения '''n''' объектов на '''k''' множеств при помощи вектора индексации (косвенной адресации), все <math> \tilde{S_i} </math> могут быть обработаны параллельно. В рамках каждого отдельного <math> \tilde{S_i} </math> можно проводить распараллеливание дальше, так как <math> x_{lj} </math> также не зависят друг от друга. Таким образом, вычисление всех слагаемых для всех <math> \tilde{\mu_{ij}} </math> может быть выполнено за одно параллельное деление, а нахождение суммы всех этих слагаемых для каждого <math> \tilde{\mu_{ij}} </math> может быть выполнено за <math> O(log(n)) </math> в худшем случае (при вхождении почти всех объектов в один кластер).

Если же такой методологии не существует, то узким местом становится процесс распределения на множества согласно вектору <math>index</math>, который можно выполнить за <math> n </math> операций косвенных адресаций.

'''4)''' Все сравнения для критерия останова также независимы между собой и могут быть выполнены за одну операцию сравнения, а финальный результат может быть получен за одну операцию сложения при работе над общей памятью (к примеру, прибавление единицы при несовпадении в общую память и сравнение ее с 0 по завершению) или за <math>\log(k*d)</math> сложений иначе.

Так как количество итераций ограничено константой, то на сложность оно не влияет. В итоге, параллельная сложность алгоритма k-means такова:
* <math> O(\log(n*d)) </math> операций сложения
* <math> O(\log(k)) </math> операций сравнения
* <math> O(1) </math> операций умножения и деления

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

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

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

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

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

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

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

'''Ограничения алгоритма'''

Алгоритм эффективно работает только на небольших объемах данных.

'''Преимущества алгоритма'''
* Простота использования
* Быстрота использования
* Понятность и прозрачность описания
* Обладает вычислительной устойчивостью
* Предрасположенность к распараллеливанию
* Достаточно популярный, поэтому имеет множество реализаций и вариаций

'''Недостатки алгоритма'''

* Нет проверки корректности выбора числа кластеров
* Алгоритм чувствителен к количеству кластеров
* Алгоритм чувствителен к выбору начальных элементов в качестве центроидов
* Алгоритм крайне чувствителен к выбросам по данным
* Медленная работа на больших объемах данных

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

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

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

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

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

* [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]
* ...

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

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

[[en:Description of algorithm properties and structure]]

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

2016-10-15T16:00:25Z

Богомазов Евгений: /* Ресурс параллелизма алгоритма */

{{algorithm
| name = Алгоритм k-средних (k-means)
| serial_complexity = <math>O(n*k*d)</math>
| input_data = <math>n*d</math>
| output_data = <math>n</math>
}}

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

= ЧАСТЬ. Свойства и структура алгоритмов =
== Общее описание алгоритма ==

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

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

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

== Математическое описание алгоритма ==
'''Исходные данные:'''
* Совокупность 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}\tilde{\mu_i} = \underset{y}{argmin } \sum_{x \in S_i} ||x-y||^2_E \\ \Mu = \underset{\tilde{\Mu}}{argmin } \sum_{i \in k} \sum_{x \in S_i} ||x-\tilde{\mu_i}||^2_E \end{cases} </math>

'''Алгоритм:'''

1) <math> \mu_{ij} = random </math>

2) <math> S_i = \{x \in S | \underset{j}{argmin } ||x-\mu_j||_E = 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)

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

Вычислительным ядром алгоритма является второй этап, а точнее нахождение матрицы расстояний между <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> операций сложений.

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

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

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

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

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

'''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_{jl})^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 \tilde{S_i}} \dfrac{x_{lj}}{|\tilde{S_i}|} </math>, где <math>\tilde{S_i} = \{l~|~l \in 1\dots n, index_l = i\} </math>

'''4) Проверка критерия останова:'''

'''Если''' <math> \exists i: \tilde{\mu_i} \neq \mu_i</math>, <math> iter < maxiter </math>,

'''то''' <math> inc(iter), \Mu=\tilde{\Mu},</math> '''GOTO 2.а.'''

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

'''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> операций делений

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

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

Для получения общей картины достаточно определить, в том числе и с помощью информационного графа, каким ресурсом параллелизма обладает каждый из этапов алгоритма:

'''2a)''' Нахождение каждой ячейки матрицы <math> dist </math> может происходить полностью независимо, так как они находятся на одном ярусе. При рассмотрении операции вычисления значения конкретной ячейки <math> dist_{ij} </math> можно заметить, что все операции умножения также независимы между собой, поэтому понадобится всего одно умножение. Конечный результат получается в результате суммирования всех слагаемых и достигается параллельно за <math> \log(d) </math> бинарных операций сложения при помощи стандартного метода ''reduction''.

'''2b)''' Нахождение вектора распределений заключается в нахождении минимального элемента в каждой строке матрицы <math> dist </math>. При использовании ''reduction'' эту операцию можно выполнить за <math> \log(k) </math> бинарных операций сравнения.

'''3)''' В случае, если существует методология быстрого разделения '''n''' объектов на '''k''' множеств при помощи вектора индексации (косвенной адресации), все <math> \tilde{S_i} </math> могут быть обработаны параллельно. В рамках каждого отдельного <math> \tilde{S_i} </math> можно проводить распараллеливание дальше, так как <math> x_{lj} </math> также не зависят друг от друга. Таким образом, вычисление всех слагаемых для всех <math> \tilde{\mu_{ij}} </math> может быть выполнено за одно параллельное деление, а нахождение суммы всех этих слагаемых для каждого <math> \tilde{\mu_{ij}} </math> может быть выполнено за <math> O(log(n)) </math> в худшем случае (при вхождении почти всех объектов в один кластер).

Если же такой методологии не существует, то узким местом становится процесс распределения на множества согласно вектору <math>index</math>, который можно выполнить за <math> n </math> операций косвенных адресаций.

'''4)''' Все сравнения для критерия останова также независимы между собой и могут быть выполнены за одну операцию сравнения, а финальный результат может быть получен за одну операцию сложения при работе над общей памятью (к примеру, прибавление единицы при несовпадении в общую память и сравнение ее с 0 по завершению) или за <math>\log(k*d)</math> сложений иначе.

Так как количество итераций ограничено константой, то на сложность оно не влияет. В итоге, параллельная сложность алгоритма k-means такова:
* <math> O(\log(n*d)) </math> операций сложения
* <math> O(\log(k)) </math> операций сравнения
* <math> O(1) </math> операций умножения и деления

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

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

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

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

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

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

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

'''Ограничения алгоритма'''

Алгоритм эффективно работает только на небольших объемах данных.

'''Преимущества алгоритма'''
* Простота использования
* Быстрота использования
* Понятность и прозрачность описания
* Обладает вычислительной устойчивостью
* Предрасположенность к распараллеливанию
* Достаточно популярный, поэтому имеет множество реализаций и вариаций

'''Недостатки алгоритма'''

* Нет проверки корректности выбора числа кластеров
* Алгоритм чувствителен к количеству кластеров
* Алгоритм чувствителен к выбору начальных элементов в качестве центроидов
* Алгоритм крайне чувствителен к выбросам по данным
* Медленная работа на больших объемах данных

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

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

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

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

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

* [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]
* ...

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

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

[[en:Description of algorithm properties and structure]]

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

2016-10-15T15:12:14Z

Богомазов Евгений:

{{algorithm
| name = Алгоритм k-средних (k-means)
| serial_complexity = <math>O(n*k*d)</math>
| input_data = <math>n*d</math>
| output_data = <math>n</math>
}}

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

= ЧАСТЬ. Свойства и структура алгоритмов =
== Общее описание алгоритма ==

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

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

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

== Математическое описание алгоритма ==
'''Исходные данные:'''
* Совокупность 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}\tilde{\mu_i} = \underset{y}{argmin } \sum_{x \in S_i} ||x-y||^2_E \\ \Mu = \underset{\tilde{\Mu}}{argmin } \sum_{i \in k} \sum_{x \in S_i} ||x-\tilde{\mu_i}||^2_E \end{cases} </math>

'''Алгоритм:'''

1) <math> \mu_{ij} = random </math>

2) <math> S_i = \{x \in S | \underset{j}{argmin } ||x-\mu_j||_E = 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)

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

Вычислительным ядром алгоритма является второй этап, а точнее нахождение матрицы расстояний между <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> операций сложений.

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

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

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

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

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

'''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_{jl})^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 \tilde{S_i}} \dfrac{x_{lj}}{|\tilde{S_i}|} </math>, где <math>\tilde{S_i} = \{l~|~l \in 1\dots n, index_l = i\} </math>

'''4. Проверка критерия останова:'''

'''Если''' <math> \exists i: \tilde{\mu_i} \neq \mu_i</math>, <math> iter < maxiter </math>,

'''то''' <math> inc(iter), \Mu=\tilde{\Mu},</math> '''GOTO 2.а.'''

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

'''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> операций делений

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

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

'''Подправь стилистику!!!'''

Для получения общей картины достаточно посмотреть, каким ресурсом параллелизма обладает каждый из этапов алгоритма с оглядкой на информационный граф:

2a) Нахождение каждой ячейки матрицы <math> dist </math> может происходить полностью независимо в виду нахождения их на одном ярусе. Рассмотрев вычисление конкретной ячейки <math> dist_{ij} </math> можно заметить,
что все операции умножения также независимы между собой (поэтому понадобится всего одно умножение), а конечный результат получается в результате суммирования всех слагаемых. При помощи стандартной методологии reduction ее можно выполнить параллельно за <math> \log(d) </math> бинарных операций сложения

2b) Нахождение вектора распределений заключается в нахождение минимального элемента в каждой строке матрицы <math> dist </math>. Снова при помощи reduction ее можно выполнить за <math> \log(k) </math> бинарных операций сравнения

3) При условии существовании методологии быстрого распределения n объектов на k множеств при помощи вектора индексации (косвенной адресации), то все <math> \tilde{S_i} </math> могут быть обработаны параллельно. В рамках каждого отдельного <math> \tilde{S_i} </math> можно проводить распараллеливание дальше, так как <math> x_{lj} </math> также не зависят друг от друга, поэтому вычисление всех слагаемых для всех <math> \tilde{\mu_{ij}} </math> может быть выполнено за одно параллельное деление, а нахождение суммы всех этих слагаемых для каждого <math> \tilde{\mu_{ij}} </math> может быть выполнено за <math> O(log(n)) </math> в худшем случае (при вхождение почти всех объектов в один кластер)

Если же такой методологии не существуют, то узким местом становится распределения на множества согласно вектору <math>index</math>, которое можно выполнить за <math> n </math> операций косвенных адресаций.

4) Все сравнения для критерия останова также независимы между собой и могут быть выполнены за одну операцию сравнения, финальный результат может быть получен за одну операцию сложения при работе над общей памятью('''нужно ли объяснять как?''', например прибавление единицы при несовпадении в общую память и сравнение ее с 0 по завершению (при этом пофиг на конфликты)) или за <math>\log(k*d)</math> сложений иначе

Так как количество итераций ограничено константой, то на сложность оно не влияет. Итого параллельная сложность алгоритма:
* <math> O(\log(n*d)) </math> операций сложения
* <math> O(\log(k)) </math> операций сравнения
* <math> O(1) </math> операций умножений и делений

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

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

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

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

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

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

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

'''Ограничения алгоритма'''

Алгоритм эффективно работает только на небольших объемах данных.

'''Преимущества алгоритма'''
* Простота использования
* Быстрота использования
* Понятность и прозрачность описания
* Обладает вычислительной устойчивостью
* Предрасположенность к распараллеливанию
* Достаточно популярный, поэтому имеет множество реализаций и вариаций

'''Недостатки алгоритма'''

* Нет проверки корректности выбора числа кластеров
* Алгоритм чувствителен к количеству кластеров
* Алгоритм чувствителен к выбору начальных элементов в качестве центроидов
* Алгоритм крайне чувствителен к выбросам по данным
* Медленная работа на больших объемах данных

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

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

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

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

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

* [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]
* ...

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

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

[[en:Description of algorithm properties and structure]]

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

2016-10-15T14:20:48Z

Богомазов Евгений: /* Схема реализации последовательного алгоритма */

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

2016-10-15T14:14:27Z

Богомазов Евгений: /* Схема реализации последовательного алгоритма */

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

2016-10-14T20:35:44Z

Богомазов Евгений:

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

2016-10-14T20:32:56Z

Богомазов Евгений:

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

2016-10-14T20:17:23Z

Богомазов Евгений: /* Свойства алгоритма */

{{algorithm
| name = Алгоритм k-средних (k-means)
| serial_complexity = <math>O()</math>
| input_data = <math>\frac{()}{}</math>
| output_data = <math>\frac{ ()}{}</math>
}}

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

= ЧАСТЬ. Свойства и структура алгоритмов =
== Общее описание алгоритма ==

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

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

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

== Математическое описание алгоритма ==
'''Исходные данные:'''
* Совокупность 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}\tilde{\mu_i} = \underset{y}{argmin } \sum_{x \in S_i} ||x-y||^2_E \\ \Mu = \underset{\tilde{\Mu}}{argmin } \sum_{i \in k} \sum_{x \in S_i} ||x-\tilde{\mu_i}||^2_E \end{cases} </math>

'''Алгоритм:'''

1) <math> \mu_{ij} = random </math>

2) <math> S_i = \{x| \underset{j}{argmin } ||x-\mu_j||_E = 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)

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

Вычислительным ядром алгоритма является второй этап, а точнее нахождение матрицы расстояний между <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> операций сложений.

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

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

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

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

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

'''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 < maxiter </math>,

'''то''' <math> inc(iter), \Mu=\tilde{\Mu},</math> '''GOTO 2.а.'''

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

'''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> операций делений

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

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

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

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

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

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

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

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

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

'''Ограничения алгоритма'''

Алгоритм эффективно работает только на небольших объемах данных.

'''Преимущества алгоритма'''
* Простота использования
* Быстрота использования
* Понятность и прозрачность описания
* Обладает вычислительной устойчивостью
* Предрасположенность к распараллеливанию
* Достаточно популярный, поэтому имеет множество реализаций и вариаций

'''Недостатки алгоритма'''

* Нет проверки корректности выбора числа кластеров
* Алгоритм чувствителен к количеству кластеров
* Алгоритм чувствителен к выбору начальных элементов в качестве центроидов
* Алгоритм крайне чувствителен к выбросам по данным
* Медленная работа на больших объемах данных

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

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

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

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

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

* [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]
* ...

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

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

[[en:Description of algorithm properties and structure]]

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

2016-10-14T20:15:50Z

Богомазов Евгений: /* Математическое описание алгоритма */

{{algorithm
| name = Алгоритм k-средних (k-means)
| serial_complexity = <math>O()</math>
| input_data = <math>\frac{()}{}</math>
| output_data = <math>\frac{ ()}{}</math>
}}

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

= ЧАСТЬ. Свойства и структура алгоритмов =
== Общее описание алгоритма ==

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

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

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

== Математическое описание алгоритма ==
'''Исходные данные:'''
* Совокупность 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}\tilde{\mu_i} = \underset{y}{argmin } \sum_{x \in S_i} ||x-y||^2_E \\ \Mu = \underset{\tilde{\Mu}}{argmin } \sum_{i \in k} \sum_{x \in S_i} ||x-\tilde{\mu_i}||^2_E \end{cases} </math>

'''Алгоритм:'''

1) <math> \mu_{ij} = random </math>

2) <math> S_i = \{x| \underset{j}{argmin } ||x-\mu_j||_E = 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)

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

Вычислительным ядром алгоритма является второй этап, а точнее нахождение матрицы расстояний между <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> операций сложений.

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

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

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

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

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

'''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 < maxiter </math>,

'''то''' <math> inc(iter), \Mu=\tilde{\Mu},</math> '''GOTO 2.а.'''

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

'''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> операций делений

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

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

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

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

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

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

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

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

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

'''Ограничения алгоритма'''

Алгоритм эффективно работает только на небольших объемах данных.

'''Преимущества алгоритма'''
* Простота использования
* Быстрота использования
* Понятность и прозрачность описания
* Обладает вычислительной устойчивостью
* Предрасположенность к распараллеливанию
* Достаточно популярный, поэтому имеет множество реализаций и вариаций

'''Недостатки алгоритма'''

* Нет проверки корректности выбора числа кластеров
* Алгоритм чувствителен к количеству кластеров
* Алгоритм чувствителен к выбору начальных элементов в качестве центроидов и на одном наборе данных в теории может демонстрировать разные результаты
* Алгоритм крайне чувствителен к выбросам по данным
* Медленная работа на больших объемах данных

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

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

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

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

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

* [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]
* ...

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

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

[[en:Description of algorithm properties and structure]]

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

2016-10-14T20:05:53Z

Богомазов Евгений: /* Свойства алгоритма */

{{algorithm
| name = Алгоритм k-средних (k-means)
| serial_complexity = <math>O()</math>
| input_data = <math>\frac{()}{}</math>
| output_data = <math>\frac{ ()}{}</math>
}}

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

= ЧАСТЬ. Свойства и структура алгоритмов =
== Общее описание алгоритма ==

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

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

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

== Математическое описание алгоритма ==
'''Исходные данные:'''
* Совокупность 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)

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

Вычислительным ядром алгоритма является второй этап, а точнее нахождение матрицы расстояний между <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> операций сложений.

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

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

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

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

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

'''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 < maxiter </math>,

'''то''' <math> inc(iter), \Mu=\tilde{\Mu},</math> '''GOTO 2.а.'''

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

'''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> операций делений

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

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

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

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

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

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

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

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

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

'''Ограничения алгоритма'''

Алгоритм эффективно работает только на небольших объемах данных.

'''Преимущества алгоритма'''
* Простота использования
* Быстрота использования
* Понятность и прозрачность описания
* Обладает вычислительной устойчивостью
* Предрасположенность к распараллеливанию
* Достаточно популярный, поэтому имеет множество реализаций и вариаций

'''Недостатки алгоритма'''

* Нет проверки корректности выбора числа кластеров
* Алгоритм чувствителен к количеству кластеров
* Алгоритм чувствителен к выбору начальных элементов в качестве центроидов и на одном наборе данных в теории может демонстрировать разные результаты
* Алгоритм крайне чувствителен к выбросам по данным
* Медленная работа на больших объемах данных

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

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

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

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

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

* [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]
* ...

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

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

[[en:Description of algorithm properties and structure]]

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

2016-10-14T17:45:07Z

Богомазов Евгений: /* Последовательная сложность алгоритма */

{{algorithm
| name = Алгоритм k-средних (k-means)
| serial_complexity = <math>O()</math>
| input_data = <math>\frac{()}{}</math>
| output_data = <math>\frac{ ()}{}</math>
}}

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

= ЧАСТЬ. Свойства и структура алгоритмов =
== Общее описание алгоритма ==

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

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

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

== Математическое описание алгоритма ==
'''Исходные данные:'''
* Совокупность 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)

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

Вычислительным ядром алгоритма является второй этап, а точнее нахождение матрицы расстояний между <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> операций сложений.

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

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

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

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

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

'''1. Шаг инициализации'''
По какому-либо правилу выбираем <math>k</math> объектов для кластеризации, объявляем их центроидами

'''2. Шаг классификации'''
Классифицируем каждый объект на предмет принадлежности к кластеру:

<math>a_i \in P \Leftrightarrow \left|a_i - s_P\right| \rightarrow \min_P</math>

'''3. Шаг перерасчета центроидов'''
Вычисляем центр масс каждого из кластеров.

'''3.а''' Если для какого-либо кластера его центр масс '''отличается''' от центроида, то
* переносим центроид этого кластера во вновь образованный центр масс,
* проделываем эту операцию для всех других кластеров
* переходим к '''Шагу 2'''

'''3.б''' Если для каждого кластера его центр масс '''совпадает''' с центроидом, то
'''Выход из алгоритма''', объекты классифицированы.

'''Альтернатива'''

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

1) Инициализация центроидов <math>\Mu</math>, <math> iter = 1 </math>, задание максимального количество итераций <math>maxiter</math>
2a) Нахождение матрицы расстояний <math>dist: dist_{ij} = \sum_{l = 1\dots d} (x_{il}-\mu_{il})^2</math>
2b) Нахождение вектора распределения объектов по кластерам <math>index: index_{i} = argmin_{j} dist_{ij} </math>
3) Пересчет центроидов <math>\tilde{\Mu}: \tilde{\mu_{ij}} = \sum_{l \in T_i} 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 < maxiter </math>, то <math> inc(iter), \Mu=\tilde{\Mu}</math>, goto 2a

'''Альтернатива альтернативы'''

'''1. Инициализация центроидов'''

<math>\Mu</math>, <math> iter = 1 </math>, задание максимального количество итераций <math>maxiter</math>

'''2.а. Нахождение матрицы расстояний'''

<math>dist: dist_{ij} = \sum_{l = 1\dots d} (x_{il}-\mu_{il})^2</math>

'''2.б. Нахождение вектора распределения объектов по кластерам'''

<math>index: index_{i} = \underset{j}{argmin } dist_{ij} </math>

'''3. Пересчет центроидов'''

<math>\tilde{\Mu}: \tilde{\mu_{ij}} = \sum_{l \in T_i} 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 < maxiter </math>,

'''то''' <math> inc(iter), \Mu=\tilde{\Mu},</math> '''GOTO 2.а.'''

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

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> операций делений

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[[en:Description of algorithm properties and structure]]

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

2016-10-14T15:50:14Z

Богомазов Евгений: /* Схема реализации последовательного алгоритма */

{{algorithm
| name = Алгоритм k-средних (k-means)
| serial_complexity = <math>O()</math>
| input_data = <math>\frac{()}{}</math>
| output_data = <math>\frac{ ()}{}</math>
}}

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

= ЧАСТЬ. Свойства и структура алгоритмов =
== Общее описание алгоритма ==

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

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

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

== Математическое описание алгоритма ==
'''Исходные данные:'''
* Совокупность 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)

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

Вычислительным ядром алгоритма является второй этап, а точнее нахождение матрицы расстояний между <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> операций сложений.

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

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

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

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

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

'''1. Шаг инициализации'''
По какому-либо правилу выбираем <math>k</math> объектов для кластеризации, объявляем их центроидами

'''2. Шаг классификации'''
Классифицируем каждый объект на предмет принадлежности к кластеру:

<math>a_i \in P \Leftrightarrow \left|a_i - s_P\right| \rightarrow \min_P</math>

'''3. Шаг перерасчета центроидов'''
Вычисляем центр масс каждого из кластеров.

'''3.а''' Если для какого-либо кластера его центр масс '''отличается''' от центроида, то
* переносим центроид этого кластера во вновь образованный центр масс,
* проделываем эту операцию для всех других кластеров
* переходим к '''Шагу 2'''

'''3.б''' Если для каждого кластера его центр масс '''совпадает''' с центроидом, то
'''Выход из алгоритма''', объекты классифицированы.

'''Альтернатива'''

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

1) Инициализация центроидов <math>\Mu</math>, <math> iter = 1 </math>, задание максимального количество итераций <math>maxiter</math>
2a) Нахождение матрицы расстояний <math>dist: dist_{ij} = \sum_{l = 1\dots d} (x_{il}-\mu_{il})^2</math>
2b) Нахождение вектора распределения объектов по кластерам <math>index: index_{i} = argmin_{j} dist_{ij} </math>
3) Пересчет центроидов <math>\tilde{\Mu}: \tilde{\mu_{ij}} = \sum_{l \in T_i} 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 < maxiter </math>, то <math> inc(iter), \Mu=\tilde{\Mu}</math>, goto 2a

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

'''1. Шаг инициализации'''

Сложность выбора <math>k</math> центроидов <math>O(1)</math>

'''2. Шаг классификации'''

Для каждого из <math>n</math>объектов требуется выполнить <math>k*dim</math> операций умножения и <math>k*(k - 1)</math> операций сложения. То есть сложность вычисления расстояний на каждой итерации <math>O(n*k*(dim + k - 1)</math>.

После этого нужно найти кластер, расстояние до которого минимально. Сложность такого поиска <math>O(n*k)</math>

'''Суммарная сложность шага <math>O(n*k*(dim + k - 1)</math>.'''

'''3. Шаг перерасчета центроидов'''

Для вычисления центра масс каждого из кластеров требуется совершить <math>(n - 1)*dim</math> операцию сложения и <math>k*dim</math> операций деления. Сложность шага <math>O((n + k - 1)*dim)</math>

3.а Обновление центроидов потребует <math>k*dim</math> операций вычитания, сложность шага <math>O(k*dim)</math>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[[en:Description of algorithm properties and structure]]

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

2016-10-14T15:03:25Z

Богомазов Евгений: /* Вычислительное ядро алгоритма */

{{algorithm
| name = Алгоритм k-средних (k-means)
| serial_complexity = <math>O()</math>
| input_data = <math>\frac{()}{}</math>
| output_data = <math>\frac{ ()}{}</math>
}}

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

= ЧАСТЬ. Свойства и структура алгоритмов =
== Общее описание алгоритма ==

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

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

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

== Математическое описание алгоритма ==
'''Исходные данные:'''
* Совокупность 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)

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

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

'''Альтернатива'''

Вычислительным ядром алгоритма является второй этап, а точнее нахождение матрицы расстояний между <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> операций сложений.

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

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

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

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

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

'''1. Шаг инициализации'''
По какому-либо правилу выбираем <math>k</math> объектов для кластеризации, объявляем их центроидами

'''2. Шаг классификации'''
Классифицируем каждый объект на предмет принадлежности к кластеру:

<math>a_i \in P \Leftrightarrow \left|a_i - s_P\right| \rightarrow \min_P</math>

'''3. Шаг перерасчета центроидов'''
Вычисляем центр масс каждого из кластеров.

'''3.а''' Если для какого-либо кластера его центр масс '''отличается''' от центроида, то
* переносим центроид этого кластера во вновь образованный центр масс,
* проделываем эту операцию для всех других кластеров
* переходим к '''Шагу 2'''

'''3.б''' Если для каждого кластера его центр масс '''совпадает''' с центроидом, то
'''Выход из алгоритма''', объекты классифицированы.

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

'''1. Шаг инициализации'''

Сложность выбора <math>k</math> центроидов <math>O(1)</math>

'''2. Шаг классификации'''

Для каждого из <math>n</math>объектов требуется выполнить <math>k*dim</math> операций умножения и <math>k*(k - 1)</math> операций сложения. То есть сложность вычисления расстояний на каждой итерации <math>O(n*k*(dim + k - 1)</math>.

После этого нужно найти кластер, расстояние до которого минимально. Сложность такого поиска <math>O(n*k)</math>

'''Суммарная сложность шага <math>O(n*k*(dim + k - 1)</math>.'''

'''3. Шаг перерасчета центроидов'''

Для вычисления центра масс каждого из кластеров требуется совершить <math>(n - 1)*dim</math> операцию сложения и <math>k*dim</math> операций деления. Сложность шага <math>O((n + k - 1)*dim)</math>

3.а Обновление центроидов потребует <math>k*dim</math> операций вычитания, сложность шага <math>O(k*dim)</math>

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

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

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

'''Входные данные''': Количество кластеров <math>k</math>, <math>m</math>кластеризуемых элементов
Дополнительные ограничения:
* <math>k</math> — положительное число, т. е. <math>k > 0</math>.
* Для кластеризуемых элементов определена метрика (расстояние между объектами)

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

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

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

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

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

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

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

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

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

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

[[en:Description of algorithm properties and structure]]

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

2016-10-14T15:02:50Z

Богомазов Евгений: /* Вычислительное ядро алгоритма */

{{algorithm
| name = Алгоритм k-средних (k-means)
| serial_complexity = <math>O()</math>
| input_data = <math>\frac{()}{}</math>
| output_data = <math>\frac{ ()}{}</math>
}}

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

= ЧАСТЬ. Свойства и структура алгоритмов =
== Общее описание алгоритма ==

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

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

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

== Математическое описание алгоритма ==
'''Исходные данные:'''
* Совокупность 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)

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

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

'''Альтернатива'''

Вычислительным ядром алгоритма является второй этап, а точнее нахождение матрицы расстояний между <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>d*n*k</math> операций умножений и <math>n*k*(d-1)</math> операций сложений.

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

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

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

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

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

'''1. Шаг инициализации'''
По какому-либо правилу выбираем <math>k</math> объектов для кластеризации, объявляем их центроидами

'''2. Шаг классификации'''
Классифицируем каждый объект на предмет принадлежности к кластеру:

<math>a_i \in P \Leftrightarrow \left|a_i - s_P\right| \rightarrow \min_P</math>

'''3. Шаг перерасчета центроидов'''
Вычисляем центр масс каждого из кластеров.

'''3.а''' Если для какого-либо кластера его центр масс '''отличается''' от центроида, то
* переносим центроид этого кластера во вновь образованный центр масс,
* проделываем эту операцию для всех других кластеров
* переходим к '''Шагу 2'''

'''3.б''' Если для каждого кластера его центр масс '''совпадает''' с центроидом, то
'''Выход из алгоритма''', объекты классифицированы.

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

'''1. Шаг инициализации'''

Сложность выбора <math>k</math> центроидов <math>O(1)</math>

'''2. Шаг классификации'''

Для каждого из <math>n</math>объектов требуется выполнить <math>k*dim</math> операций умножения и <math>k*(k - 1)</math> операций сложения. То есть сложность вычисления расстояний на каждой итерации <math>O(n*k*(dim + k - 1)</math>.

После этого нужно найти кластер, расстояние до которого минимально. Сложность такого поиска <math>O(n*k)</math>

'''Суммарная сложность шага <math>O(n*k*(dim + k - 1)</math>.'''

'''3. Шаг перерасчета центроидов'''

Для вычисления центра масс каждого из кластеров требуется совершить <math>(n - 1)*dim</math> операцию сложения и <math>k*dim</math> операций деления. Сложность шага <math>O((n + k - 1)*dim)</math>

3.а Обновление центроидов потребует <math>k*dim</math> операций вычитания, сложность шага <math>O(k*dim)</math>

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

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

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

'''Входные данные''': Количество кластеров <math>k</math>, <math>m</math>кластеризуемых элементов
Дополнительные ограничения:
* <math>k</math> — положительное число, т. е. <math>k > 0</math>.
* Для кластеризуемых элементов определена метрика (расстояние между объектами)

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

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

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

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

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

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

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

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

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

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

[[en:Description of algorithm properties and structure]]

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

2016-10-14T13:29:34Z

Богомазов Евгений: /* Математическое описание алгоритма */

{{algorithm
| name = Алгоритм k-средних (k-means)
| serial_complexity = <math>O()</math>
| input_data = <math>\frac{()}{}</math>
| output_data = <math>\frac{ ()}{}</math>
}}

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

= ЧАСТЬ. Свойства и структура алгоритмов =
== Общее описание алгоритма ==

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

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

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

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

'''Исходные данные:'''
* <math>\{a_i\}, i = 1 \dots m</math> — множество из <math>n</math> объектов, подлежащих кластеризации и определяющихся вектором длины <math>dim</math>,
* <math>k</math> — предполагаемое количество кластеров.

'''Вычисляемые данные:'''
* Центр предполагаемого кластера (центроид) — на первом шаге объявляется равным случайному объекту, а затем сдвигается в центр масс элементов кластера.

Если <math>\{s_1 \dots s_k\}</math> — центроиды, где <math>1 \dots k</math> — номера кластеров, то объект <math>a</math> относится к кластеру <math>P</math>, если суммарное квадратичное отклонение точек кластеров от центров этих кластеров минимально:

<math>a_i \in P \Leftrightarrow \left|a_i - s_P\right| \rightarrow \min_P</math>

Альтернатива:

'''Исходные данные:'''
* Совокупность 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> \mu_i = argmin_y \sum_{x \in S_i} ||x-y||^2_E </math> и <math> argmin_\Mu \sum_{i \in k} \sum_{x \in S_i} ||x-\mu_i||^2_E </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)

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

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

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

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

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

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

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

'''1. Шаг инициализации'''
По какому-либо правилу выбираем <math>k</math> объектов для кластеризации, объявляем их центроидами

'''2. Шаг классификации'''
Классифицируем каждый объект на предмет принадлежности к кластеру:

<math>a_i \in P \Leftrightarrow \left|a_i - s_P\right| \rightarrow \min_P</math>

'''3. Шаг перерасчета центроидов'''
Вычисляем центр масс каждого из кластеров.

'''3.а''' Если для какого-либо кластера его центр масс '''отличается''' от центроида, то
* переносим центроид этого кластера во вновь образованный центр масс,
* проделываем эту операцию для всех других кластеров
* переходим к '''Шагу 2'''

'''3.б''' Если для каждого кластера его центр масс '''совпадает''' с центроидом, то
'''Выход из алгоритма''', объекты классифицированы.

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

'''1. Шаг инициализации'''

Сложность выбора <math>k</math> центроидов <math>O(1)</math>

'''2. Шаг классификации'''

Для каждого из <math>n</math>объектов требуется выполнить <math>k*dim</math> операций умножения и <math>k*(k - 1)</math> операций сложения. То есть сложность вычисления расстояний на каждой итерации <math>O(n*k*(dim + k - 1)</math>.

После этого нужно найти кластер, расстояние до которого минимально. Сложность такого поиска <math>O(n*k)</math>

'''Суммарная сложность шага <math>O(n*k*(dim + k - 1)</math>.'''

'''3. Шаг перерасчета центроидов'''

Для вычисления центра масс каждого из кластеров требуется совершить <math>(n - 1)*dim</math> операцию сложения и <math>k*dim</math> операций деления. Сложность шага <math>O((n + k - 1)*dim)</math>

3.а Обновление центроидов потребует <math>k*dim</math> операций вычитания, сложность шага <math>O(k*dim)</math>

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

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

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

'''Входные данные''': Количество кластеров <math>k</math>, <math>m</math>кластеризуемых элементов
Дополнительные ограничения:
* <math>k</math> — положительное число, т. е. <math>k > 0</math>.
* Для кластеризуемых элементов определена метрика (расстояние между объектами)

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

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

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

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

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

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

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

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

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

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

[[en:Description of algorithm properties and structure]]