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

Участник:Parkhomenko/Алгоритм k средних

2016-12-15T11:24:01Z

Parkhomenko: /* Масштабируемость алгоритма и его реализации */

{{Assignment|Zhum}}
{{algorithm
| name = Алгоритм k средних
| serial_complexity = <math>O(tnkd)</math>
| input_data = <math>nd</math>
| output_data = <math>n</math>
| pf_height = <math>O(t \cdot \log nkd)</math>
| pf_width = <math>O(nkd)</math>
}}

Основные авторы описания: [[Участник:Parkhomenko|П.А.Пархоменко]] ([[#Общее описание алгоритма|1.1]], [[#Вычислительное ядро алгоритма|1.3]], [[#Последовательная сложность алгоритма|1.6]], [[#Ресурс параллелизма алгоритма|1.8]], [[#Входные и выходные данные алгоритма|1.9]], [[#Свойства алгоритма|1.10]], [[#Масштабируемость алгоритма и его реализации|2.4]]), [[Участник:Ivan.mashonskiy|И.Д.Машонский]] ([[#Математическое описание алгоритма|1.2]], [[#Макроструктура алгоритма|1.4]], [[#Схема реализации последовательного алгоритма|1.5]], [[#Информационный граф|1.7]], [[#Ресурс параллелизма алгоритма|1.8]], [[#Свойства алгоритма|1.10]], [[#Существующие реализации алгоритма|2.7]])
== Свойства и структура алгоритмов ==

=== Общее описание алгоритма ===
Алгоритм k средних (англ. k-means) - один из алгоритмов машинного обучения, решающий задачу кластеризации. Он был изобретен в середине 1950-х математиком Гуго Штейнгаузом<ref>Steinhaus H. (1956). Sur la division des corps materiels en parties. Bull. Acad. Polon. Sci., C1. III vol IV: 801—804.</ref> и Стюартом Ллойдом<ref>Lloyd S. (1957). Least square quantization in PCM’s. Bell Telephone Laboratories Paper.</ref>. Алгоритм стал особо популярным после публикации Маккуина<ref>MacQueen J. (1967). Some methods for classification and analysis of multivariate observations. In Proc. 5th Berkeley Symp. on Math. Statistics and Probability, pages 281—297.</ref>, в которой впервые был использован термин “k-means”.

Задача алгоритма кластеризации заключается в разбиении N объектов (d-мерных векторов) на K групп (кластеров). Каждый вектор может принадлежать только одному кластеру. Количество кластеров K фиксировано, оно задается в качестве параметра.

K-means является итерационным алгоритмом, разновидностью EM-алгоритма. Основная идея работы алгоритма заключается в проведении некоторого количества итераций, на каждой из которых происходит пересчет центра масс для каждого кластера, полученного на предыдущей итерации. После этого векторы перераспределяются по кластерам: вектор относится к тому кластеру, расстояние до центра масс которого минимально. Алгоритм завершает работу в том случае, если на очередной итерации центры масс кластеров не изменились.

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

Исходные данные: множество d-мерных векторов (наблюдений) <math>X</math> = <math>\{x_1, x_2, ..., x_n\}</math>, число кластеров <math>k \in \mathbb{N}</math>

В результате работы алгоритма исходное множество векторов <math>X</math> разбивается на <math>k</math> непересекающихся множеств (кластеров) <math>S_1, S_2, ..., S_k</math>, таких что <math>X = {\bigcup \limits _{i = 1}^k S_i} </math> и значение <math>\sum_{i=1}^{k} \sum_{\mathbf x \in S_i} \left\| \mathbf x - \mu_i \right\|^2 </math> — минимально для всех возможных наборов <math>S_1, S_2, ..., S_k</math>.
Под <math>\mu_i</math> здесь подразумевается центр масс векторов из множества <math>S_i</math>.

Первоначальные значения центров масс <math>\mu_1^{(1)}, ..., \mu_k^{(1)}</math> определяются в начале работы алгоритма случайным образом среди векторов множества <math>X</math>.

Алгоритм заключается в попеременном применении двух шагов <ref>MacKay, David (2003). "Chapter 20. An Example Inference Task: Clustering" (PDF). Information Theory, Inference and Learning Algorithms. Cambridge University Press. pp. 284–292.</ref>: '''распределения''' векторов по кластерам и '''обновления''' центров масс каждого кластера

'''Распределение векторов по кластерам''': на данном шаге каждый вектор распределяется в один из кластеров <math>S_i^{(t)}</math>:
::<math>S_i^{(t)} = \big \{ x_p : \big \| x_p - \mu^{(t)}_i \big \|^2 \le \big \| x_p - \mu^{(t)}_j \big \|^2 \ \forall j, 1 \le j \le k \big\},</math>
'''Обновление центров масс''': на данном шаге вычисляются новые центры масс для кластеров, полученных на предыдущем шаге.
::<math>\mu^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math>

Алгоритм завершается, когда на очередном шаге не происходит изменения центров масс кластеров.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро последовательного алгоритма k-means состоит из двух операций, повторяющихся на каждой итерации алгоритма:
* пересчета центров масс кластеров;
* соотнесения каждого вектора к одному из кластеров.

Пересчет центра масс кластера заключается в нахождении d-мерного вектора, являющегося средним арифметическим d-мерных векторов, принадлежащих кластеру. Эту операцию необходимо выполнять для каждого из K кластеров.

Для соотнесения вектора к одному из кластеров, необходимо для каждого из N вектора посчитать расстояние до центров масс всех K кластеров. Для нахождения расстояния между двумя d-мерными векторами p и q используется Евклидова метрика: <math>\sqrt{\sum_{k=1}^d (p_k-q_k)^2}</math>

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

Инициализация центров масс кластеров

В начале алгоритма осуществляется инициализация центров масс <math>\mu_1^{(1)}, ..., \mu_k^{(1)}</math>, которая может быть реализована двумя возможными способами <ref>Hamerly, G.; Elkan, C. (2002). "Alternatives to the k-means algorithm that find better clusterings" (PDF). Proceedings of the eleventh international conference on Information and knowledge management (CIKM).</ref>:
* случайный выбор центров масс среди исходных наблюдений <math>x_1, x_2, ..., x_n</math>;
* все наблюдения случайным образом распределяются по кластерам <math>S_1, S_2, ..., S_k</math>, а затем для каждого кластера выполняется операция обновления центра масс.

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

На шаге распределения векторов по кластерам производится операция нахождения квадратов расстояний между векторами кластера и центром масс кластера:
::<math>\rho = \big \| x_p - \mu^{(t)}_i \big \|^2</math>

Обновление центров масс кластеров

На шаге обновления центров масс производится операция суммирования векторов кластера:
::<math>\mu^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math>

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

Последовательность исполнения метода следующая:
# Инициализируются центры масс <math>\mu_1^{(1)}, ..., \mu_k^{(1)}</math>
# <math>t := 1</math>
# Для каждого вектора <math>x_i, i = 1, 2, ..., n</math> вычисляется <math>m = \underset{j \in \{1, 2, ..., k\}} {\operatorname{arg\,min}} \big \| x_i - \mu^{(t)}_j \big \|^2</math>, вектор <math>x_i</math> распределяется в кластер <math>S^{(t)}_m</math>
# Для каждого <math>j = 1, 2, ..., k</math> вычисляется <math>\mu^{(t+1)}_j = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math>
# Если <math>\mu^{(t)}_j = \mu^{(t+1)}_j, j = 1, 2, ..., k</math>, завершить выполнение алгоритма, иначе <math>t := t + 1</math>, переход на шаг 3.

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

Для вычисления центра массы кластера, содержащего <math>n_i</math> d-мерных векторов, необходимо:
* <math>n_i \cdot (d - 1)</math> операций сложения
* <math>d</math> операций деления

Для определения центров масс всех k кластеров требуется:
* <math>n \cdot (d - 1)</math> операций сложения
* <math>k \cdot d</math> операций деления

Для определения расстояния между двумя d-мерными векторами, требуется:
* <math>d</math> операций вычитания
* <math>d</math> операций умножения
* <math>d - 1</math> операций сложения

Для определения кластера для n d-мерного векторов, необходимо:
* <math>n \cdot k \cdot d</math> операций вычитания
* <math>n \cdot k \cdot d</math> операций умножения
* <math>n \cdot k \cdot (d - 1)</math> операций сложения

Таким образом, общая сложность одной итерации:
* <math>O(n k d)</math> операций сложения/вычитания
* <math>O(n k d)</math> операций умножения/деления

Сложность всего алгоритма, состоящего из <math>t</math> итераций: <math>O(t n k d)</math>

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

В данном разделе описывается информационный граф алгоритма k-средних при <math>n = 3, k = 2</math>

На рисунке 1 показана общая структура алгоритма: в качестве входных данных выступает матрица, строками которой являются входные векторы <math>x_1, x_2, x_3</math>, на выходе получается массив из <math>n</math> чисел, где элемент с номером <math>i = 1, 2, 3</math> обозначает номер кластера, которому принадлежит вектор <math>x_i</math>. На шаге <math>init</math> происходит инициализация значений центров масс кластеров, после этого осуществляется итеративное повторение этапов распределения векторов по кластерам (<math>as</math>) и обновления значений центров масс кластеров (<math>up</math>). Когда на очередном шаге обновления центров масс кластеров значения центров масс не изменяются, алгоритм завершает работу, и в качестве выходных данных выступают номера кластеров для каждого из входных векторов.
[[file:k_means_main.png|thumb|center|400px|Рисунок 1. Общая схема работы алгоритма k-средних]]

'''Распределение векторов по кластерам.''' На рисунке 2 изображен информационный граф для этапа распределения векторов по кластерам. В качестве входных данных выступают строки входной матрицы (входные векторы) <math>x_1, x_2, x_3</math> и текущие значения центров масс кластеров <math>\mu_1, \mu_2</math> (вычисленные на этапе инициализации или предшествующего этапа обновления центров масс кластеров). В качестве выходных данных выступают числа <math>m_1, m_2, m_3</math>, где <math>m_i, i = 1, 2, 3</math> - номер кластера, содержащего вектор <math>x_i</math>. Вершинами с пометкой <math>sub</math> обозначены операции векторной разности, вершинами <math>sn</math> - операция вычисления квадрата нормы вектора, вершинами <math>am</math> - операция <math>\underset{i \in \{1, 2\}} {\operatorname{arg\,min}} p_i</math>.
[[file:k_means_info_graph_as.png|thumb|center|400px|Рисунок 2. Граф алгоритма для этапа распределения векторов по кластерам]]
'''Обновление центров масс кластеров.''' На рисунке 3 представлен информационный граф для этапа обновления центров масс кластеров. В качестве входных данных выступают строки входной матрицы (входные векторы) <math>x_1, x_2, x_3</math> с соответствующими номерами кластеров <math>m_1, m_2, m_3</math>, содержащих эти векторы. В качестве выходных данных здесь выступают обновленные значения центров масс кластеров: <math>\mu_1, \mu_2</math>. Вершинами с пометками <math>s_i, i = 1, 2</math> обозначены операции суммирования векторов, принадлежащих кластеру <math>i</math>. Вершинами с пометками <math>cs_i, i = 1, 2</math> обозначены операции вычисления выражения <math>1 / |S_i|</math>, где за <math>S_i</math> обозначен кластер с номером <math>i</math>. Вершинами с пометкой <math>p</math> обозначена операция произведения.
[[file:k_means_info_graph_up.png|thumb|center|400px|Рисунок 3. Граф алгоритма для этапа обновления центров масс кластеров]]

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

Алгоритм кластеризации k средних имеет место массовый параллелизм: в основе каждого из основных этапов алгоритма (распределения векторов по кластерам и обновления центров масс кластеров) лежат циклы, итерации которых являются информационно независимыми.
Учитывая данный факт можно оценить параллельную сложность алгоритма в предположении доступности неограниченного числа необходимых процессоров.

В силу особенностей алгоритма k средних порядок выполнения основных этапов существенен, что не позволяет выполнять их параллельно. Таким образом, итоговая сложность параллельного алгоритма будет определяться, исходя из формулы <math>T = t \cdot (T_{as} + T_{up})</math>, где <math>T_{as}</math> - параллельная сложность этапа распределения векторов по кластерам, <math>T_{up}</math> - параллельная сложность этапа обновления центров масс кластеров, <math>t</math> - общее число итераций алгоритма.

Параллельная сложность этапа распределения векторов по кластерам с учетом доступности неограниченного числа процессоров вычисляется следующим образом: так как вычисление значений <math>\big \| x_i - \mu^{(t)}_j \big \|^2</math> для каждой пары векторов <math>x_i, i = 1, 2, ..., n</math> и <math>\mu^{(t)}_j, j = 1, 2, ..., k</math> можно выполнять независимо и для вычисления этого выражения требуется <math>O(\log d)</math> операций в соответствии с [[Нахождение_частных_сумм_элементов_массива_сдваиванием | параллельной реализацией нахождения сумм элементов массива сдваиванием]]. Параллельная сложность реализации операции нахождения минимума из <math>k</math> элементов определяется как <math>O(\log k)</math>. Таким образом, сложность этапа распределения векторов по кластерам <math>O(\log kd)</math>.

Параллельная сложность этапа обновления центров масс кластеров вычисляется следующим образом: так как обновление значений каждого из центров масс кластеров можно выполнять независимо, параллельная сложность определяется сложностью обновления центра масс самого большого кластера. В худшем случае для нахождения значения выражения <math>\mu^{(t+1)}_j = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math> требуется <math>O(\log n)</math> операций.

С учетом вышесказанного, итоговая параллельная сложность алгоритма k средних определяется выражением <math>O(t \cdot \log nkd)</math>.

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

'''Входные данные''':
* целое неотрицательное число <math>k</math> - количество кластеров;
* матрица координат векторов <math>A</math> размерностью <math>n * d</math>.

'''Объем входных данных''':
* <math>n * d</math> вещественных чисел (если координаты вещественные числа), <math>1</math> целое неотрицательное число.

'''Выходные данные''':
* вектор длины <math>n</math> - для каждого вектора указан номер кластера.

'''Объем выходных данных''':
* <math>n</math> целых неотрицательных чисел.

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

Соотношение последовательной и параллельной сложности алгоритма равно <math>\frac{O(tnkd)}{O(t \cdot \log nkd)}</math>.

Число операций алгоритма k средних оценивается как <math>O(tnkd)</math>, суммарный объем входных и выходных данных равен <math>n(d+1)</math>. Следовательно, вычислительная мощность алгоритма линейна по <math>k</math> и линейна по <math>t</math>.

Стоит отметить следующие ключевые особенности алгоритма k средних:
* Алгоритм прост в реализации и имеет высокую скорость работы по сравнению с другими алгоритмами кластеризации (при удачном выборе начальных значений центров масс кластеров)
* В качестве метрики используется евклидово расстояние, а в качестве меры разброса кластера используется дисперсия
* Количество кластеров k является входным параметром алгоритма, поэтому неправильный выбор этого параметра может негативно повлиять на качество кластеризации
* Сходимость алгоритма к локальному минимуму может породить некорректный конечный результат работы
* Алгоритм очень чувствителен к выбору начальных центров масс кластеров: классический вариант подразумевает случайный их выбор, что может являться источником погрешности. Из этого и предыдущего свойства следует то, что алгоритм не является устойчивым.

Как и любой другой алгоритм кластеризации, результат работы алгоритма k средних зависит от того, удовлетворяет ли входной набор данных предположениям, на которые опираются алгоритмы кластеризации. Таким образом, на одних наборах данных алгоритм может показывать хорошие результаты, но на других выдавать некорректные результаты.

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

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

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

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

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

=== Масштабируемость алгоритма и его реализации ===
Исследование масштабируемости алгоритма k-means в зависимости от количества используемых процессов было проведено в статье Кумара<ref>Kumar, J., Mills, R. T., Hoffman, F. M., & Hargrove, W. W. (2011). Parallel k-means clustering for quantitative ecoregion delineation using large data sets. Procedia Computer Science, 4, 1602-1611.</ref>. Исследование происходило на суперкомпьютере Jaguar - Cray XT5<ref>https://www.top500.org/system/176029</ref>. На момент экспериментов данный суперкомпьютер имел следующую конфигурацию: 18,688 вычислительных узлов с двумя шестнадцатиядерными процессорами AMD Opteron 2435 (Istanbul) 2.6 GHz, 16 GB of DDR2-800 оперативной памяти, и SeaStar 2+ роутер. Всего он состоял из 224,256 вычислительных ядер, 300 TB памяти, и пиковой производительностью 2.3 petaflops.

Реализация алгоритма была выполнена на языке программирования C с использованием MPI.

Объем данных составлял 84 гигабайта, количество объектов (d-мерных векторов) n равнялось 1,024,767,667, размерность векторов d равнялась 22, количество кластеров k равнялось 1000.

На рисунке 4 показана зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров. Можно отметить, что время, затраченное на чтение данных и запись результатов кластеризации, практически не изменяется с увеличением количества задействованных процессоров. Время же работы самого алгоритма кластеризации уменьшается с увеличением количества процессоров.
[[Файл:k-means-proc-scalability.png|thumb|center|700px|Рисунок 4. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров.]]

Также было произведено самостоятельное исследование масштабируемости алгоритма. Исследование производилось на суперкомпьютере "Blue Gene/P"<ref>http://hpc.cmc.msu.ru/bgp</ref>.

Набор и границы значений изменяемых параметров запуска реализации алгоритма:

* число процессоров [1, 2, 4, 8, 16, 32, 64, 128, 256, 512];
* количество объектов [5000, 10000, 25000, 50000].

Был использован набор данных ''Dataset for Sensorless Drive Diagnosis Data Set''<ref>PASCHKE, Fabian ; BAYER, Christian ; BATOR, Martyna ; MÃ–NKS, Uwe ; DICKS, Alexander ; ENGE-ROSENBLATT, Olaf ; LOHWEG, Volker: Sensorlose ZustandsÃ¼berwachung an Synchronmotoren, Bd. 46. In: HOFFMANN, Frank; HÃœLLERMEIER, Eyke (Hrsg.): Proceedings 23. Workshop Computational Intelligence. Karlsruhe : KIT Scientific Publishing, 2013 (Schriftenreihe des Instituts fÃ¼r Angewandte Informatik - Automatisierungstechnik am Karlsruher Institut fÃ¼r Technologie, 46), S. 211-225</ref> из репозитория ''Machine learning repository''<ref>https://archive.ics.uci.edu/ml/datasets/Dataset+for+Sensorless+Drive+Diagnosis</ref>.

Исследуемый набор данных содержит векторы, размерность которых равна 49. Компоненты векторов являются вещественными числами. Количество кластеров равно 11. Пропущенные значения отсутствуют.

Для исследования масштабируемости алгоритма была использована реализация на языке C с использованием MPI<ref>http://users.eecs.northwestern.edu/~wkliao/Kmeans/index.html</ref>. Код можно найти здесь: https://github.com/serban/kmeans. Данная реализация предоставляет возможность распараллеливать решение задачи с помощью технологий MPI, OpenMP И CUDA. Для запуска MPI-версии программы использовалась цель "mpi_main" Makefile.

На рисунке 5 показана зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров (использовались логарифмические оси). Разными цветами помечены запуски, соответствующие разным количествам объектам, участвующих в кластеризации. Можно видеть близкое к линейному увеличение времени работы программы в зависимости от количества процессоров. Также можно видеть увеличение времени работы алгоритма при увеличении количества объектов.
[[Файл:Plot_1.png|thumb|center|900px|Рисунок 5. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров.]]

На рисунке 6 показана эта же зависимость, только в трехмерном пространстве. Аналогично с рисунком 5, были использованы логарифмические оси. Как и в случае двумерного рисунка, можно видеть близкое к линейному увеличение времени работы программы.
[[Файл:Kmeans-3d.png|thumb|center|900px|Рисунок 6. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров.]]

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

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

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

Существуют следующие реализации алгоритма k-средних:
* [http://scikit-learn.org/ scikit-learn] библиотека машинного обучения для языка Python.
* [https://www.scipy.org/ SciPy] библиотека на языке Python, содержащая большое число реализаций различных алгоритмов, в том числе ''k''-средних.
* [http://elki.dbs.ifi.lmu.de ELKI] библиотека для анализа данных на языке программирования Java, содержит различные алгоритмы кластеризации, в том числе ''k''-средних.
* [http://mlpack.org MLPACK] библиотека машинного обучения для C++, содержит реализацию алгоритма ''k''-средних.
* [https://github.com/JuliaStats/Clustering.jl Julia k-means] реализация алгоритма ''k''-средних на языке программирования Julia.
* [http://opencv.org/ OpenCV] библиотека содержит реализацию ''k''-средних.
* [http://mahout.apache.org Apache Mahout] содержит реализацию алгоритма ''k''-средних на базе MapReduce.
* [http://www.cs.waikato.ac.nz/~ml/weka Weka] библиотека и инструмент для анализа данных на языке Java.
* [http://torch.ch/ Torch] библиотека машинного обучения на базе языка программирования Lua.
* [https://spark.apache.org/ Apache Spark MLlib] содержит распределенную реализацию алгоритма ''k''-средних.
* [http://www.accord-framework.net/ Accord.NET] содержит несколько различных реализаций ''k''-средних на языке C#.
* [https://www.r-bloggers.com/k-means-clustering-in-r/ R k-means] реализация ''k''-средних на языке R.

== Литература ==
<references \>

Файл:Kmeans-3d.png

2016-12-15T11:18:47Z

Parkhomenko:

Участник:Parkhomenko/Алгоритм k средних

2016-12-09T21:37:13Z

Parkhomenko: /* Масштабируемость алгоритма и его реализации */

{{Assignment|Zhum}}
{{algorithm
| name = Алгоритм k средних
| serial_complexity = <math>O(tnkd)</math>
| input_data = <math>nd</math>
| output_data = <math>n</math>
| pf_height = <math>O(t \cdot \log nkd)</math>
| pf_width = <math>O(nkd)</math>
}}

Основные авторы описания: [[Участник:Parkhomenko|П.А.Пархоменко]] ([[#Общее описание алгоритма|1.1]], [[#Вычислительное ядро алгоритма|1.3]], [[#Последовательная сложность алгоритма|1.6]], [[#Ресурс параллелизма алгоритма|1.8]], [[#Входные и выходные данные алгоритма|1.9]], [[#Свойства алгоритма|1.10]], [[#Масштабируемость алгоритма и его реализации|2.4]]), [[Участник:Ivan.mashonskiy|И.Д.Машонский]] ([[#Математическое описание алгоритма|1.2]], [[#Макроструктура алгоритма|1.4]], [[#Схема реализации последовательного алгоритма|1.5]], [[#Информационный граф|1.7]], [[#Ресурс параллелизма алгоритма|1.8]], [[#Свойства алгоритма|1.10]], [[#Существующие реализации алгоритма|2.7]])
== Свойства и структура алгоритмов ==

=== Общее описание алгоритма ===
Алгоритм k средних (англ. k-means) - один из алгоритмов машинного обучения, решающий задачу кластеризации. Он был изобретен в середине 1950-х математиком Гуго Штейнгаузом<ref>Steinhaus H. (1956). Sur la division des corps materiels en parties. Bull. Acad. Polon. Sci., C1. III vol IV: 801—804.</ref> и Стюартом Ллойдом<ref>Lloyd S. (1957). Least square quantization in PCM’s. Bell Telephone Laboratories Paper.</ref>. Алгоритм стал особо популярным после публикации Маккуина<ref>MacQueen J. (1967). Some methods for classification and analysis of multivariate observations. In Proc. 5th Berkeley Symp. on Math. Statistics and Probability, pages 281—297.</ref>, в которой впервые был использован термин “k-means”.

Задача алгоритма кластеризации заключается в разбиении N объектов (d-мерных векторов) на K групп (кластеров). Каждый вектор может принадлежать только одному кластеру. Количество кластеров K фиксировано, оно задается в качестве параметра.

K-means является итерационным алгоритмом, разновидностью EM-алгоритма. Основная идея работы алгоритма заключается в проведении некоторого количества итераций, на каждой из которых происходит пересчет центра масс для каждого кластера, полученного на предыдущей итерации. После этого векторы перераспределяются по кластерам: вектор относится к тому кластеру, расстояние до центра масс которого минимально. Алгоритм завершает работу в том случае, если на очередной итерации центры масс кластеров не изменились.

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

Исходные данные: множество d-мерных векторов (наблюдений) <math>X</math> = <math>\{x_1, x_2, ..., x_n\}</math>, число кластеров <math>k \in \mathbb{N}</math>

В результате работы алгоритма исходное множество векторов <math>X</math> разбивается на <math>k</math> непересекающихся множеств (кластеров) <math>S_1, S_2, ..., S_k</math>, таких что <math>X = {\bigcup \limits _{i = 1}^k S_i} </math> и значение <math>\sum_{i=1}^{k} \sum_{\mathbf x \in S_i} \left\| \mathbf x - \mu_i \right\|^2 </math> — минимально для всех возможных наборов <math>S_1, S_2, ..., S_k</math>.
Под <math>\mu_i</math> здесь подразумевается центр масс векторов из множества <math>S_i</math>.

Первоначальные значения центров масс <math>\mu_1^{(1)}, ..., \mu_k^{(1)}</math> определяются в начале работы алгоритма случайным образом среди векторов множества <math>X</math>.

Алгоритм заключается в попеременном применении двух шагов <ref>MacKay, David (2003). "Chapter 20. An Example Inference Task: Clustering" (PDF). Information Theory, Inference and Learning Algorithms. Cambridge University Press. pp. 284–292.</ref>: '''распределения''' векторов по кластерам и '''обновления''' центров масс каждого кластера

'''Распределение векторов по кластерам''': на данном шаге каждый вектор распределяется в один из кластеров <math>S_i^{(t)}</math>:
::<math>S_i^{(t)} = \big \{ x_p : \big \| x_p - \mu^{(t)}_i \big \|^2 \le \big \| x_p - \mu^{(t)}_j \big \|^2 \ \forall j, 1 \le j \le k \big\},</math>
'''Обновление центров масс''': на данном шаге вычисляются новые центры масс для кластеров, полученных на предыдущем шаге.
::<math>\mu^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math>

Алгоритм завершается, когда на очередном шаге не происходит изменения центров масс кластеров.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро последовательного алгоритма k-means состоит из двух операций, повторяющихся на каждой итерации алгоритма:
* пересчета центров масс кластеров;
* соотнесения каждого вектора к одному из кластеров.

Пересчет центра масс кластера заключается в нахождении d-мерного вектора, являющегося средним арифметическим d-мерных векторов, принадлежащих кластеру. Эту операцию необходимо выполнять для каждого из K кластеров.

Для соотнесения вектора к одному из кластеров, необходимо для каждого из N вектора посчитать расстояние до центров масс всех K кластеров. Для нахождения расстояния между двумя d-мерными векторами p и q используется Евклидова метрика: <math>\sqrt{\sum_{k=1}^d (p_k-q_k)^2}</math>

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

Инициализация центров масс кластеров

В начале алгоритма осуществляется инициализация центров масс <math>\mu_1^{(1)}, ..., \mu_k^{(1)}</math>, которая может быть реализована двумя возможными способами <ref>Hamerly, G.; Elkan, C. (2002). "Alternatives to the k-means algorithm that find better clusterings" (PDF). Proceedings of the eleventh international conference on Information and knowledge management (CIKM).</ref>:
* случайный выбор центров масс среди исходных наблюдений <math>x_1, x_2, ..., x_n</math>;
* все наблюдения случайным образом распределяются по кластерам <math>S_1, S_2, ..., S_k</math>, а затем для каждого кластера выполняется операция обновления центра масс.

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

На шаге распределения векторов по кластерам производится операция нахождения квадратов расстояний между векторами кластера и центром масс кластера:
::<math>\rho = \big \| x_p - \mu^{(t)}_i \big \|^2</math>

Обновление центров масс кластеров

На шаге обновления центров масс производится операция суммирования векторов кластера:
::<math>\mu^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math>

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

Последовательность исполнения метода следующая:
# Инициализируются центры масс <math>\mu_1^{(1)}, ..., \mu_k^{(1)}</math>
# <math>t := 1</math>
# Для каждого вектора <math>x_i, i = 1, 2, ..., n</math> вычисляется <math>m = \underset{j \in \{1, 2, ..., k\}} {\operatorname{arg\,min}} \big \| x_i - \mu^{(t)}_j \big \|^2</math>, вектор <math>x_i</math> распределяется в кластер <math>S^{(t)}_m</math>
# Для каждого <math>j = 1, 2, ..., k</math> вычисляется <math>\mu^{(t+1)}_j = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math>
# Если <math>\mu^{(t)}_j = \mu^{(t+1)}_j, j = 1, 2, ..., k</math>, завершить выполнение алгоритма, иначе <math>t := t + 1</math>, переход на шаг 3.

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

Для вычисления центра массы кластера, содержащего <math>n_i</math> d-мерных векторов, необходимо:
* <math>n_i \cdot (d - 1)</math> операций сложения
* <math>d</math> операций деления

Для определения центров масс всех k кластеров требуется:
* <math>n \cdot (d - 1)</math> операций сложения
* <math>k \cdot d</math> операций деления

Для определения расстояния между двумя d-мерными векторами, требуется:
* <math>d</math> операций вычитания
* <math>d</math> операций умножения
* <math>d - 1</math> операций сложения

Для определения кластера для n d-мерного векторов, необходимо:
* <math>n \cdot k \cdot d</math> операций вычитания
* <math>n \cdot k \cdot d</math> операций умножения
* <math>n \cdot k \cdot (d - 1)</math> операций сложения

Таким образом, общая сложность одной итерации:
* <math>O(n k d)</math> операций сложения/вычитания
* <math>O(n k d)</math> операций умножения/деления

Сложность всего алгоритма, состоящего из <math>t</math> итераций: <math>O(t n k d)</math>

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

В данном разделе описывается информационный граф алгоритма k-средних при <math>n = 3, k = 2</math>

На рисунке 1 показана общая структура алгоритма: в качестве входных данных выступает матрица, строками которой являются входные векторы <math>x_1, x_2, x_3</math>, на выходе получается массив из <math>n</math> чисел, где элемент с номером <math>i = 1, 2, 3</math> обозначает номер кластера, которому принадлежит вектор <math>x_i</math>. На шаге <math>init</math> происходит инициализация значений центров масс кластеров, после этого осуществляется итеративное повторение этапов распределения векторов по кластерам (<math>as</math>) и обновления значений центров масс кластеров (<math>up</math>). Когда на очередном шаге обновления центров масс кластеров значения центров масс не изменяются, алгоритм завершает работу, и в качестве выходных данных выступают номера кластеров для каждого из входных векторов.
[[file:k_means_main.png|thumb|center|400px|Рисунок 1. Общая схема работы алгоритма k-средних]]

'''Распределение векторов по кластерам.''' На рисунке 2 изображен информационный граф для этапа распределения векторов по кластерам. В качестве входных данных выступают строки входной матрицы (входные векторы) <math>x_1, x_2, x_3</math> и текущие значения центров масс кластеров <math>\mu_1, \mu_2</math> (вычисленные на этапе инициализации или предшествующего этапа обновления центров масс кластеров). В качестве выходных данных выступают числа <math>m_1, m_2, m_3</math>, где <math>m_i, i = 1, 2, 3</math> - номер кластера, содержащего вектор <math>x_i</math>. Вершинами с пометкой <math>sub</math> обозначены операции векторной разности, вершинами <math>sn</math> - операция вычисления квадрата нормы вектора, вершинами <math>am</math> - операция <math>\underset{i \in \{1, 2\}} {\operatorname{arg\,min}} p_i</math>.
[[file:k_means_info_graph_as.png|thumb|center|400px|Рисунок 2. Граф алгоритма для этапа распределения векторов по кластерам]]
'''Обновление центров масс кластеров.''' На рисунке 3 представлен информационный граф для этапа обновления центров масс кластеров. В качестве входных данных выступают строки входной матрицы (входные векторы) <math>x_1, x_2, x_3</math> с соответствующими номерами кластеров <math>m_1, m_2, m_3</math>, содержащих эти векторы. В качестве выходных данных здесь выступают обновленные значения центров масс кластеров: <math>\mu_1, \mu_2</math>. Вершинами с пометками <math>s_i, i = 1, 2</math> обозначены операции суммирования векторов, принадлежащих кластеру <math>i</math>. Вершинами с пометками <math>cs_i, i = 1, 2</math> обозначены операции вычисления выражения <math>1 / |S_i|</math>, где за <math>S_i</math> обозначен кластер с номером <math>i</math>. Вершинами с пометкой <math>p</math> обозначена операция произведения.
[[file:k_means_info_graph_up.png|thumb|center|400px|Рисунок 3. Граф алгоритма для этапа обновления центров масс кластеров]]

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

Алгоритм кластеризации k средних имеет место массовый параллелизм: в основе каждого из основных этапов алгоритма (распределения векторов по кластерам и обновления центров масс кластеров) лежат циклы, итерации которых являются информационно независимыми.
Учитывая данный факт можно оценить параллельную сложность алгоритма в предположении доступности неограниченного числа необходимых процессоров.

В силу особенностей алгоритма k средних порядок выполнения основных этапов существенен, что не позволяет выполнять их параллельно. Таким образом, итоговая сложность параллельного алгоритма будет определяться, исходя из формулы <math>T = t \cdot (T_{as} + T_{up})</math>, где <math>T_{as}</math> - параллельная сложность этапа распределения векторов по кластерам, <math>T_{up}</math> - параллельная сложность этапа обновления центров масс кластеров, <math>t</math> - общее число итераций алгоритма.

Параллельная сложность этапа распределения векторов по кластерам с учетом доступности неограниченного числа процессоров вычисляется следующим образом: так как вычисление значений <math>\big \| x_i - \mu^{(t)}_j \big \|^2</math> для каждой пары векторов <math>x_i, i = 1, 2, ..., n</math> и <math>\mu^{(t)}_j, j = 1, 2, ..., k</math> можно выполнять независимо и для вычисления этого выражения требуется <math>O(\log d)</math> операций в соответствии с [[Нахождение_частных_сумм_элементов_массива_сдваиванием | параллельной реализацией нахождения сумм элементов массива сдваиванием]]. Параллельная сложность реализации операции нахождения минимума из <math>k</math> элементов определяется как <math>O(\log k)</math>. Таким образом, сложность этапа распределения векторов по кластерам <math>O(\log kd)</math>.

Параллельная сложность этапа обновления центров масс кластеров вычисляется следующим образом: так как обновление значений каждого из центров масс кластеров можно выполнять независимо, параллельная сложность определяется сложностью обновления центра масс самого большого кластера. В худшем случае для нахождения значения выражения <math>\mu^{(t+1)}_j = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math> требуется <math>O(\log n)</math> операций.

С учетом вышесказанного, итоговая параллельная сложность алгоритма k средних определяется выражением <math>O(t \cdot \log nkd)</math>.

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

'''Входные данные''':
* целое неотрицательное число <math>k</math> - количество кластеров;
* матрица координат векторов <math>A</math> размерностью <math>n * d</math>.

'''Объем входных данных''':
* <math>n * d</math> вещественных чисел (если координаты вещественные числа), <math>1</math> целое неотрицательное число.

'''Выходные данные''':
* вектор длины <math>n</math> - для каждого вектора указан номер кластера.

'''Объем выходных данных''':
* <math>n</math> целых неотрицательных чисел.

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

Соотношение последовательной и параллельной сложности алгоритма равно <math>\frac{O(tnkd)}{O(t \cdot \log nkd)}</math>.

Число операций алгоритма k средних оценивается как <math>O(tnkd)</math>, суммарный объем входных и выходных данных равен <math>n(d+1)</math>. Следовательно, вычислительная мощность алгоритма линейна по <math>k</math> и линейна по <math>t</math>.

Стоит отметить следующие ключевые особенности алгоритма k средних:
* Алгоритм прост в реализации и имеет высокую скорость работы по сравнению с другими алгоритмами кластеризации (при удачном выборе начальных значений центров масс кластеров)
* В качестве метрики используется евклидово расстояние, а в качестве меры разброса кластера используется дисперсия
* Количество кластеров k является входным параметром алгоритма, поэтому неправильный выбор этого параметра может негативно повлиять на качество кластеризации
* Сходимость алгоритма к локальному минимуму может породить некорректный конечный результат работы
* Алгоритм очень чувствителен к выбору начальных центров масс кластеров: классический вариант подразумевает случайный их выбор, что может являться источником погрешности. Из этого и предыдущего свойства следует то, что алгоритм не является устойчивым.

Как и любой другой алгоритм кластеризации, результат работы алгоритма k средних зависит от того, удовлетворяет ли входной набор данных предположениям, на которые опираются алгоритмы кластеризации. Таким образом, на одних наборах данных алгоритм может показывать хорошие результаты, но на других выдавать некорректные результаты.

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

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

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

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

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

=== Масштабируемость алгоритма и его реализации ===
Исследование масштабируемости алгоритма k-means в зависимости от количества используемых процессов было проведено в статье Кумара<ref>Kumar, J., Mills, R. T., Hoffman, F. M., & Hargrove, W. W. (2011). Parallel k-means clustering for quantitative ecoregion delineation using large data sets. Procedia Computer Science, 4, 1602-1611.</ref>. Исследование происходило на суперкомпьютере Jaguar - Cray XT5<ref>https://www.top500.org/system/176029</ref>. На момент экспериментов данный суперкомпьютер имел следующую конфигурацию: 18,688 вычислительных узлов с двумя шестнадцатиядерными процессорами AMD Opteron 2435 (Istanbul) 2.6 GHz, 16 GB of DDR2-800 оперативной памяти, и SeaStar 2+ роутер. Всего он состоял из 224,256 вычислительных ядер, 300 TB памяти, и пиковой производительностью 2.3 petaflops.

Реализация алгоритма была выполнена на языке программирования C с использованием MPI.

Объем данных составлял 84 гигабайта, количество объектов (d-мерных векторов) n равнялось 1,024,767,667, размерность векторов d равнялась 22, количество кластеров k равнялось 1000.

На рисунке 4 показана зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров. Можно отметить, что время, затраченное на чтение данных и запись результатов кластеризации, практически не изменяется с увеличением количества задействованных процессоров. Время же работы самого алгоритма кластеризации уменьшается с увеличением количества процессоров.
[[Файл:k-means-proc-scalability.png|thumb|center|700px|Рисунок 4. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров.]]

Также было произведено самостоятельное исследование масштабируемости алгоритма. Исследование производилось на суперкомпьютере "Blue Gene/P"<ref>http://hpc.cmc.msu.ru/bgp</ref>.

Набор и границы значений изменяемых параметров запуска реализации алгоритма:

* число процессоров [1, 2, 4, 8, 16, 32, 64, 128, 256, 512];
* количество объектов [5000, 10000, 25000, 50000].

Был использован набор данных ''Dataset for Sensorless Drive Diagnosis Data Set''<ref>PASCHKE, Fabian ; BAYER, Christian ; BATOR, Martyna ; MÃ–NKS, Uwe ; DICKS, Alexander ; ENGE-ROSENBLATT, Olaf ; LOHWEG, Volker: Sensorlose ZustandsÃ¼berwachung an Synchronmotoren, Bd. 46. In: HOFFMANN, Frank; HÃœLLERMEIER, Eyke (Hrsg.): Proceedings 23. Workshop Computational Intelligence. Karlsruhe : KIT Scientific Publishing, 2013 (Schriftenreihe des Instituts fÃ¼r Angewandte Informatik - Automatisierungstechnik am Karlsruher Institut fÃ¼r Technologie, 46), S. 211-225</ref> из репозитория ''Machine learning repository''<ref>https://archive.ics.uci.edu/ml/datasets/Dataset+for+Sensorless+Drive+Diagnosis</ref>.

Исследуемый набор данных содержит векторы, размерность которых равна 49. Компоненты векторов являются вещественными числами. Количество кластеров равно 11. Пропущенные значения отсутствуют.

Для исследования масштабируемости алгоритма была использована реализация на языке C с использованием MPI<ref>http://users.eecs.northwestern.edu/~wkliao/Kmeans/index.html</ref>. Код можно найти здесь: https://github.com/serban/kmeans. Данная реализация предоставляет возможность распараллеливать решение задачи с помощью технологий MPI, OpenMP И CUDA. Для запуска MPI-версии программы использовалась цель "mpi_main" Makefile.

На рисунке 5 показана зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров (использовались логарифмические оси). Разными цветами помечены запуски, соответствующие разным количествам объектам, участвующих в кластеризации. Можно видеть близкое к линейному увеличение времени работы программы в зависимости от количества процессоров. Также можно видеть увеличение времени работы алгоритма при увеличении количества объектов.
[[Файл:Plot_1.png|thumb|center|900px|Рисунок 5. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров.]]

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

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

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

Существуют следующие реализации алгоритма k-средних:
* [http://scikit-learn.org/ scikit-learn] библиотека машинного обучения для языка Python.
* [https://www.scipy.org/ SciPy] библиотека на языке Python, содержащая большое число реализаций различных алгоритмов, в том числе ''k''-средних.
* [http://elki.dbs.ifi.lmu.de ELKI] библиотека для анализа данных на языке программирования Java, содержит различные алгоритмы кластеризации, в том числе ''k''-средних.
* [http://mlpack.org MLPACK] библиотека машинного обучения для C++, содержит реализацию алгоритма ''k''-средних.
* [https://github.com/JuliaStats/Clustering.jl Julia k-means] реализация алгоритма ''k''-средних на языке программирования Julia.
* [http://opencv.org/ OpenCV] библиотека содержит реализацию ''k''-средних.
* [http://mahout.apache.org Apache Mahout] содержит реализацию алгоритма ''k''-средних на базе MapReduce.
* [http://www.cs.waikato.ac.nz/~ml/weka Weka] библиотека и инструмент для анализа данных на языке Java.
* [http://torch.ch/ Torch] библиотека машинного обучения на базе языка программирования Lua.
* [https://spark.apache.org/ Apache Spark MLlib] содержит распределенную реализацию алгоритма ''k''-средних.
* [http://www.accord-framework.net/ Accord.NET] содержит несколько различных реализаций ''k''-средних на языке C#.
* [https://www.r-bloggers.com/k-means-clustering-in-r/ R k-means] реализация ''k''-средних на языке R.

== Литература ==
<references \>

Файл:Plot 1.png

2016-12-09T21:20:35Z

Parkhomenko:

Участник:Parkhomenko/Алгоритм k средних

2016-11-17T22:02:36Z

Parkhomenko:

{{Assignment}}

{{algorithm
| name = Алгоритм k средних
| serial_complexity = <math>O(tnkd)</math>
| input_data = <math>nd</math>
| output_data = <math>n</math>
| pf_height = <math>O(t * \log kdn)</math>
| pf_width = <math>O(kdn)</math>
}}

Основные авторы описания: [[Участник:Parkhomenko|П.А.Пархоменко]] ([[#Общее описание алгоритма|1.1]], [[#Вычислительное ядро алгоритма|1.3]], [[#Последовательная сложность алгоритма|1.6]], [[#Ресурс параллелизма алгоритма|1.8]], [[#Входные и выходные данные алгоритма|1.9]], [[#Свойства алгоритма|1.10]], [[#Масштабируемость алгоритма и его реализации|2.4]]), [[Участник:Ivan.mashonskiy|И.Д.Машонский]] ([[#Математическое описание алгоритма|1.2]], [[#Макроструктура алгоритма|1.4]], [[#Схема реализации последовательного алгоритма|1.5]], [[#Информационный граф|1.7]], [[#Ресурс параллелизма алгоритма|1.8]], [[#Свойства алгоритма|1.10]], [[#Существующие реализации алгоритма|2.7]])
== Свойства и структура алгоритмов ==

=== Общее описание алгоритма ===
Алгоритм k средних (англ. k-means) - один из алгоритмов машинного обучения, решающий задачу кластеризации. Он был изобретен в середине 1950-х математиком Гуго Штейнгаузом<ref>Steinhaus H. (1956). Sur la division des corps materiels en parties. Bull. Acad. Polon. Sci., C1. III vol IV: 801—804.</ref> и Стюартом Ллойдом<ref>Lloyd S. (1957). Least square quantization in PCM’s. Bell Telephone Laboratories Paper.</ref>. Алгоритм стал особо популярным после публикации Маккуина<ref>MacQueen J. (1967). Some methods for classification and analysis of multivariate observations. In Proc. 5th Berkeley Symp. on Math. Statistics and Probability, pages 281—297.</ref>, в которой впервые был использован термин “k-means”.

Задача алгоритма кластеризации заключается в разбиении N объектов (d-мерных векторов) на K групп (кластеров). Каждый вектор может принадлежать только одному кластеру. Количество кластеров K фиксировано, оно задается в качестве параметра.

K-means является итерационным алгоритмом, разновидностью EM-алгоритма. Основная идея работы алгоритма заключается в проведении некоторого количества итераций, на каждой из которых происходит пересчет центра масс для каждого кластера, полученного на предыдущей итерации. После этого векторы перераспределяются по кластерам: вектор относится к тому кластеру, расстояние до центра масс которого минимально. Алгоритм завершает работу в том случае, если на очередной итерации центры масс кластеров не изменились.

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

Исходные данные: множество d-мерных векторов (наблюдений) <math>X</math> = <math>\{x_1, x_2, ..., x_n\}</math>, число кластеров <math>k \in \mathbb{N}</math>

В результате работы алгоритма исходное множество векторов <math>X</math> разбивается на <math>k</math> непересекающихся множеств (кластеров) <math>S_1, S_2, ..., S_k</math>, таких что <math>X = {\bigcup \limits _{i = 1}^k S_i} </math> и значение <math>\sum_{i=1}^{k} \sum_{\mathbf x \in S_i} \left\| \mathbf x - \mu_i \right\|^2 </math> — минимально для всех возможных наборов <math>S_1, S_2, ..., S_k</math>.
Под <math>\mu_i</math> здесь подразумевается центр масс векторов из множества <math>S_i</math>.

Первоначальные значения центров масс <math>\mu_1^{(1)}, ..., \mu_k^{(1)}</math> определяются в начале работы алгоритма случайным образом среди векторов множества <math>X</math>.

Алгоритм заключается в попеременном применении двух шагов <ref>MacKay, David (2003). "Chapter 20. An Example Inference Task: Clustering" (PDF). Information Theory, Inference and Learning Algorithms. Cambridge University Press. pp. 284–292.</ref>: '''распределения''' векторов по кластерам и '''обновления''' центров масс каждого кластера

'''Распределение векторов по кластерам''': на данном шаге каждый вектор распределяется в один из кластеров <math>S_i^{(t)}</math>:
::<math>S_i^{(t)} = \big \{ x_p : \big \| x_p - \mu^{(t)}_i \big \|^2 \le \big \| x_p - \mu^{(t)}_j \big \|^2 \ \forall j, 1 \le j \le k \big\},</math>
'''Обновление центров масс''': на данном шаге вычисляются новые центры масс для кластеров, полученных на предыдущем шаге.
::<math>\mu^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math>

Алгоритм завершается, когда на очередном шаге не происходит изменения центров масс кластеров.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро последовательного алгоритма k-means состоит из двух операций, повторяющихся на каждой итерации алгоритма:
* пересчета центров масс кластеров;
* соотнесения каждого вектора к одному из кластеров.

Пересчет центра масс кластера заключается в нахождении d-мерного вектора, являющегося средним арифметическим d-мерных векторов, принадлежащих кластеру. Эту операцию необходимо выполнять для каждого из K кластеров.

Для соотнесения вектора к одному из кластеров, необходимо для каждого из N вектора посчитать расстояние до центров масс всех K кластеров. Для нахождения расстояния между двумя d-мерными векторами p и q используется Евклидова метрика: <math>\sqrt{\sum_{k=1}^d (p_k-q_k)^2}</math>

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

Инициализация центров масс кластеров

В начале алгоритма осуществляется инициализация центров масс <math>\mu_1^{(1)}, ..., \mu_k^{(1)}</math>, которая может быть реализована двумя возможными способами <ref>Hamerly, G.; Elkan, C. (2002). "Alternatives to the k-means algorithm that find better clusterings" (PDF). Proceedings of the eleventh international conference on Information and knowledge management (CIKM).</ref>:
* случайный выбор центров масс среди исходных наблюдений <math>x_1, x_2, ..., x_n</math>;
* все наблюдения случайным образом распределяются по кластерам <math>S_1, S_2, ..., S_k</math>, а затем для каждого кластера выполняется операция обновления центра масс.

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

На шаге распределения векторов по кластерам производится операция нахождения квадратов расстояний между векторами кластера и центром масс кластера:
::<math>\rho = \big \| x_p - \mu^{(t)}_i \big \|^2</math>

Обновление центров масс кластеров

На шаге обновления центров масс производится операция суммирования векторов кластера:
::<math>\mu^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math>

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

Последовательность исполнения метода следующая:
# Инициализируются центры масс <math>\mu_1^{(1)}, ..., \mu_k^{(1)}</math>
# <math>t := 1</math>
# Для каждого вектора <math>x_i, i = 1, 2, ..., n</math> вычисляется <math>m = \underset{j \in \{1, 2, ..., k\}} {\operatorname{arg\,min}} \big \| x_i - \mu^{(t)}_j \big \|^2</math>, вектор <math>x_i</math> распределяется в кластер <math>S^{(t)}_m</math>
# Для каждого <math>j = 1, 2, ..., k</math> вычисляется <math>\mu^{(t+1)}_j = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math>
# Если <math>\mu^{(t)}_j = \mu^{(t+1)}_j, j = 1, 2, ..., k</math>, завершить выполнение алгоритма, иначе <math>t := t + 1</math>, переход на шаг 3.

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

Для вычисления центра массы кластера, содержащего <math>n_i</math> d-мерных векторов, необходимо:
* <math>n_i * (d - 1)</math> операций сложения
* <math>d</math> операций деления

Для определения центров масс всех k кластеров требуется:
* <math>n * (d - 1)</math> операций сложения
* <math>k * d</math> операций деления

Для определения расстояния между двумя d-мерными векторами, требуется:
* <math>d</math> операций вычитания
* <math>d</math> операций умножения
* <math>d - 1</math> операций сложения

Для определения кластера для n d-мерного векторов, необходимо:
* <math>n * k * d</math> операций вычитания
* <math>n * k * d</math> операций умножения
* <math>n * k * (d - 1)</math> операций сложения

Таким образом, общая сложность одной итерации:
* <math>O(n * k * d)</math> операций сложения/вычитания
* <math>O(n * k * d)</math> операций умножения/деления

Сложность всего алгоритма, состоящего из <math>t</math> итераций: <math>O(t * n * k * d)</math>

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

В данном разделе описывается информационный граф алгоритма k-средних при <math>n = 3, k = 2</math>

На рисунке 1 показана общая структура алгоритма: в качестве входных данных выступает матрица, строками которой являются входные векторы <math>x_1, x_2, x_3</math>, на выходе получается массив из <math>n</math> чисел, где элемент с номером <math>i = 1, 2, 3</math> обозначает номер кластера, которому принадлежит вектор <math>x_i</math>. На шаге <math>init</math> происходит инициализация значений центров масс кластеров, после этого осуществляется итеративное повторение этапов распределения векторов по кластерам (<math>as</math>) и обновления значений центров масс кластеров (<math>up</math>). Когда на очередном шаге обновления центров масс кластеров значения центров масс не изменяются, алгоритм завершает работу, и в качестве выходных данных выступают номера кластеров для каждого из входных векторов.
[[file:k_means_main.png|thumb|center|400px|Рисунок 1. Общая схема работы алгоритма k-средних]]

'''Распределение векторов по кластерам.''' На рисунке 2 изображен информационный граф для этапа распределения векторов по кластерам. В качестве входных данных выступают строки входной матрицы (входные векторы) <math>x_1, x_2, x_3</math> и текущие значения центров масс кластеров <math>\mu_1, \mu_2</math> (вычисленные на этапе инициализации или предшествующего этапа обновления центров масс кластеров). В качестве выходных данных выступают числа <math>m_1, m_2, m_3</math>, где <math>m_i, i = 1, 2, 3</math> - номер кластера, содержащего вектор <math>x_i</math>. Вершинами с пометкой <math>sub</math> обозначены операции векторной разности, вершинами <math>sn</math> - операция вычисления квадрата нормы вектора, вершинами <math>am</math> - операция <math>\underset{i \in \{1, 2\}} {\operatorname{arg\,min}} p_i</math>.
[[file:k_means_info_graph_as.png|thumb|center|400px|Рисунок 2. Граф алгоритма для этапа распределения векторов по кластерам]]
'''Обновление центров масс кластеров.''' На рисунке 3 представлен информационный граф для этапа обновления центров масс кластеров. В качестве входных данных выступают строки входной матрицы (входные векторы) <math>x_1, x_2, x_3</math> с соответствующими номерами кластеров <math>m_1, m_2, m_3</math>, содержащих эти векторы. В качестве выходных данных здесь выступают обновленные значения центров масс кластеров: <math>\mu_1, \mu_2</math>. Вершинами с пометками <math>s_i, i = 1, 2</math> обозначены операции суммирования векторов, принадлежащих кластеру <math>i</math>. Вершинами с пометками <math>cs_i, i = 1, 2</math> обозначены операции вычисления выражения <math>1 / |S_i|</math>, где за <math>S_i</math> обозначен кластер с номером <math>i</math>. Вершинами с пометкой <math>p</math> обозначена операция произведения.
[[file:k_means_info_graph_up.png|thumb|center|400px|Рисунок 3. Граф алгоритма для этапа обновления центров масс кластеров]]

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

Алгоритм кластеризации k средних имеет место массовый параллелизм: в основе каждого из основных этапов алгоритма (распределения векторов по кластерам и обновления центров масс кластеров) лежат циклы, итерации которых являются информационно независимыми.
Учитывая данный факт можно оценить параллельную сложность алгоритма в предположении доступности неограниченного числа необходимых процессоров.

В силу особенностей алгоритма k средних порядок выполнения основных этапов существенен, что не позволяет выполнять их параллельно. Таким образом, итоговая сложность параллельного алгоритма будет определяться, исходя из формулы <math>T = t * (T_{as} + T_{up})</math>, где <math>T_{as}</math> - параллельная сложность этапа распределения векторов по кластерам, <math>T_{up}</math> - параллельная сложность этапа обновления центров масс кластеров, <math>t</math> - общее число итераций алгоритма.

Параллельная сложность этапа распределения векторов по кластерам с учетом доступности неограниченного числа процессоров вычисляется следующим образом: так как вычисление значений <math>\big \| x_i - \mu^{(t)}_j \big \|^2</math> для каждой пары векторов <math>x_i, i = 1, 2, ..., n</math> и <math>\mu^{(t)}_j, j = 1, 2, ..., k</math> можно выполнять независимо и для вычисления этого выражения требуется <math>O(\log d)</math> операций в соответствии с [[Нахождение_частных_сумм_элементов_массива_сдваиванием | параллельной реализацией нахождения сумм элементов массива сдваиванием]]. Параллельная сложность реализации операции нахождения минимума из <math>k</math> элементов определяется как <math>O(\log k)</math>. Таким образом, сложность этапа распределения векторов по кластерам <math>O(\log kd)</math>.

Параллельная сложность этапа обновления центров масс кластеров вычисляется следующим образом: так как обновление значений каждого из центров масс кластеров можно выполнять независимо, параллельная сложность определяется сложностью обновления центра масс самого большого кластера. В худшем случае для нахождения значения выражения <math>\mu^{(t+1)}_j = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math> требуется <math>O(\log n)</math> операций.

С учетом вышесказанного, итоговая параллельная сложность алгоритма k средних определяется выражением <math>O(t * \log kdn)</math>.

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

'''Входные данные''':
* целое неотрицательное число <math>k</math> - количество кластеров;
* матрица координат векторов <math>A</math> размерностью <math>n * d</math>.

'''Объем входных данных''':
* <math>n * d</math> вещественных чисел (если координаты вещественные числа), <math>1</math> целое неотрицательное число.

'''Выходные данные''':
* вектор длины <math>n</math> - для каждого вектора указан номер кластера.

'''Объем выходных данных''':
* <math>n</math> целых неотрицательных чисел.

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

Соотношение последовательной и параллельной сложности алгоритма равно <math>\frac{O(tnkd)}{O(t * \log kdn)}</math>.

Число операций алгоритма k средних оценивается как <math>O(tnkd)</math>, суммарный объем входных и выходных данных равен <math>n(d+1)</math>. Следовательно, вычислительная мощность алгоритма линейна по <math>k</math> и линейна по <math>t</math>.

Стоит отметить следующие ключевые особенности алгоритма k средних:
* Алгоритм прост в реализации и имеет высокую скорость работы по сравнению с другими алгоритмами кластеризации (при удачном выборе начальных значений центров масс кластеров)
* В качестве метрики используется евклидово расстояние, а в качестве меры разброса кластера используется дисперсия
* Количество кластеров k является входным параметром алгоритма, поэтому неправильный выбор этого параметра может негативно повлиять на качество кластеризации
* Сходимость алгоритма к локальному минимуму может породить некорректный конечный результат работы
* Алгоритм очень чувствителен к выбору начальных центров масс кластеров: классический вариант подразумевает случайный их выбор, что может являться источником погрешности. Из этого и предыдущего свойства следует то, что алгоритм не является устойчивым.

Как и любой другой алгоритм кластеризации, результат работы алгоритма k средних зависит от того, удовлетворяет ли входной набор данных предположениям, на которые опираются алгоритмы кластеризации. Таким образом, на одних наборах данных алгоритм может показывать хорошие результаты, но на других выдавать некорректные результаты.

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

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

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

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

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

=== Масштабируемость алгоритма и его реализации ===
Исследование масштабируемости алгоритма k-means в зависимости от количества используемых процессов было проведено в статье Кумара<ref>Kumar, J., Mills, R. T., Hoffman, F. M., & Hargrove, W. W. (2011). Parallel k-means clustering for quantitative ecoregion delineation using large data sets. Procedia Computer Science, 4, 1602-1611.</ref>. Исследование происходило на суперкомпьютере Jaguar - Cray XT5<ref>https://www.top500.org/system/176029</ref>. На момент экспериментов данный суперкомпьютер имел следующую конфигурацию: 18,688 вычислительных узлов с двумя шестнадцатиядерными процессорами AMD Opteron 2435 (Istanbul) 2.6 GHz, 16 GB of DDR2-800 оперативной памяти, и SeaStar 2+ роутер. Всего он состоял из 224,256 вычислительных ядер, 300 TB памяти, и пиковой производительностью 2.3 petaflops.

Реализация алгоритма была выполнена на языке программирования C с использованием MPI.

Объем данных составлял 84 гигабайта, количество объектов (d-мерных векторов) n равнялось 1,024,767,667, размерность векторов d равнялась 22, количество кластеров k равнялось 1000.

На рисунке 4 показана зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров. Можно отметить, что время, затраченное на чтение данных и запись результатов кластеризации, практически не изменяется с увеличением количества задействованных процессоров. Время же работы самого алгоритма кластеризации уменьшается с увеличением количества процессоров.
[[Файл:k-means-proc-scalability.png|thumb|center|700px|Рисунок 4. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров.]]

Также было произведено самостоятельное исследование масштабируемости алгоритма. Исследование производилось на суперкомпьютере "Blue Gene/P"<ref>http://hpc.cmc.msu.ru/bgp</ref>.

Набор и границы значений изменяемых параметров запуска реализации алгоритма:

* число процессоров [1, 2, 4, 8, 16, 32, 64, 128, 256, 512];
* количество объектов [5000, 10000, 25000, 50000].

Был использован набор данных ''Dataset for Sensorless Drive Diagnosis Data Set''<ref>PASCHKE, Fabian ; BAYER, Christian ; BATOR, Martyna ; MÃ–NKS, Uwe ; DICKS, Alexander ; ENGE-ROSENBLATT, Olaf ; LOHWEG, Volker: Sensorlose ZustandsÃ¼berwachung an Synchronmotoren, Bd. 46. In: HOFFMANN, Frank; HÃœLLERMEIER, Eyke (Hrsg.): Proceedings 23. Workshop Computational Intelligence. Karlsruhe : KIT Scientific Publishing, 2013 (Schriftenreihe des Instituts fÃ¼r Angewandte Informatik - Automatisierungstechnik am Karlsruher Institut fÃ¼r Technologie, 46), S. 211-225</ref> из репозитория ''Machine learning repository''<ref>https://archive.ics.uci.edu/ml/datasets/Dataset+for+Sensorless+Drive+Diagnosis</ref>.

Исследуемый набор данных содержит векторы, размерность которых равна 49. Компоненты векторов являются вещественными числами. Количество кластеров равно 11. Пропущенные значения отсутствуют.

Для исследования масштабируемости алгоритма была использована реализация на языке C с использованием MPI<ref>http://users.eecs.northwestern.edu/~wkliao/Kmeans/index.html</ref>. Код можно найти здесь: https://github.com/serban/kmeans.

На рисунке 5 показана зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров. Можно видеть, что при увеличении количества процессоров в N раз, время работы алгоритма уменьшается примерно в N раз (при условии, что количество объектов остается неизменным). Также можно отметить, что при фиксированном количестве процессоров, зависимость времени работы алгоритма от количества объектов также близка к линейной.
[[Файл:Heatmap_kmeans.png|thumb|center|900px|Рисунок 5. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров.]]

На рисунке 6 показана зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров (при фиксированном количестве объектов, равном 50000). При визуализации была использована логарифмическая шкала. Можно отметить, что при заданном наборе данных можно наблюдать линейную зависимость времени работы алгоритма от количества используемых процессоров, что согласуется с теоретической оценкой сложности последовательной версии алгоритма.
[[Файл:50000kmeans.png|thumb|center|900px|Рисунок 6. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров (количество объектов равно 50000).]]

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

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

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

Существуют следующие реализации алгоритма k-средних:
* [http://scikit-learn.org/ scikit-learn] библиотека машинного обучения для языка Python.
* [https://www.scipy.org/ SciPy] библиотека на языке Python, содержащая большое число реализаций различных алгоритмов, в том числе ''k''-средних.
* [http://elki.dbs.ifi.lmu.de ELKI] библиотека для анализа данных на языке программирования Java, содержит различные алгоритмы кластеризации, в том числе ''k''-средних.
* [http://mlpack.org MLPACK] библиотека машинного обучения для C++, содержит реализацию алгоритма ''k''-средних.
* [https://github.com/JuliaStats/Clustering.jl Julia k-means] реализация алгоритма ''k''-средних на языке программирования Julia.
* [http://opencv.org/ OpenCV] библиотека содержит реализацию ''k''-средних.
* [http://mahout.apache.org Apache Mahout] содержит реализацию алгоритма ''k''-средних на базе MapReduce.
* [http://www.cs.waikato.ac.nz/~ml/weka Weka] библиотека и инструмент для анализа данных на языке Java.
* [http://torch.ch/ Torch] библиотека машинного обучения на базе языка программирования Lua.
* [https://spark.apache.org/ Apache Spark MLlib] содержит распределенную реализацию алгоритма ''k''-средних.
* [http://www.accord-framework.net/ Accord.NET] содержит несколько различных реализаций ''k''-средних на языке C#.
* [https://www.r-bloggers.com/k-means-clustering-in-r/ R k-means] реализация ''k''-средних на языке R.

== Литература ==
<references \>

Участник:Parkhomenko/Алгоритм k средних

2016-11-17T21:57:52Z

Parkhomenko: /* Масштабируемость алгоритма и его реализации */

{{algorithm
| name = Алгоритм k средних
| serial_complexity = <math>O(tnkd)</math>
| input_data = <math>nd</math>
| output_data = <math>n</math>
| pf_height = <math>O(t * \log kdn)</math>
| pf_width = <math>O(kdn)</math>
}}

Основные авторы описания: [[Участник:Parkhomenko|П.А.Пархоменко]] ([[#Общее описание алгоритма|1.1]], [[#Вычислительное ядро алгоритма|1.3]], [[#Последовательная сложность алгоритма|1.6]], [[#Ресурс параллелизма алгоритма|1.8]], [[#Входные и выходные данные алгоритма|1.9]], [[#Свойства алгоритма|1.10]], [[#Масштабируемость алгоритма и его реализации|2.4]]), [[Участник:Ivan.mashonskiy|И.Д.Машонский]] ([[#Математическое описание алгоритма|1.2]], [[#Макроструктура алгоритма|1.4]], [[#Схема реализации последовательного алгоритма|1.5]], [[#Информационный граф|1.7]], [[#Ресурс параллелизма алгоритма|1.8]], [[#Свойства алгоритма|1.10]], [[#Существующие реализации алгоритма|2.7]])
== Свойства и структура алгоритмов ==

=== Общее описание алгоритма ===
Алгоритм k средних (англ. k-means) - один из алгоритмов машинного обучения, решающий задачу кластеризации. Он был изобретен в середине 1950-х математиком Гуго Штейнгаузом<ref>Steinhaus H. (1956). Sur la division des corps materiels en parties. Bull. Acad. Polon. Sci., C1. III vol IV: 801—804.</ref> и Стюартом Ллойдом<ref>Lloyd S. (1957). Least square quantization in PCM’s. Bell Telephone Laboratories Paper.</ref>. Алгоритм стал особо популярным после публикации Маккуина<ref>MacQueen J. (1967). Some methods for classification and analysis of multivariate observations. In Proc. 5th Berkeley Symp. on Math. Statistics and Probability, pages 281—297.</ref>, в которой впервые был использован термин “k-means”.

Задача алгоритма кластеризации заключается в разбиении N объектов (d-мерных векторов) на K групп (кластеров). Каждый вектор может принадлежать только одному кластеру. Количество кластеров K фиксировано, оно задается в качестве параметра.

K-means является итерационным алгоритмом, разновидностью EM-алгоритма. Основная идея работы алгоритма заключается в проведении некоторого количества итераций, на каждой из которых происходит пересчет центра масс для каждого кластера, полученного на предыдущей итерации. После этого векторы перераспределяются по кластерам: вектор относится к тому кластеру, расстояние до центра масс которого минимально. Алгоритм завершает работу в том случае, если на очередной итерации центры масс кластеров не изменились.

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

Исходные данные: множество d-мерных векторов (наблюдений) <math>X</math> = <math>\{x_1, x_2, ..., x_n\}</math>, число кластеров <math>k \in \mathbb{N}</math>

В результате работы алгоритма исходное множество векторов <math>X</math> разбивается на <math>k</math> непересекающихся множеств (кластеров) <math>S_1, S_2, ..., S_k</math>, таких что <math>X = {\bigcup \limits _{i = 1}^k S_i} </math> и значение <math>\sum_{i=1}^{k} \sum_{\mathbf x \in S_i} \left\| \mathbf x - \mu_i \right\|^2 </math> — минимально для всех возможных наборов <math>S_1, S_2, ..., S_k</math>.
Под <math>\mu_i</math> здесь подразумевается центр масс векторов из множества <math>S_i</math>.

Первоначальные значения центров масс <math>\mu_1^{(1)}, ..., \mu_k^{(1)}</math> определяются в начале работы алгоритма случайным образом среди векторов множества <math>X</math>.

Алгоритм заключается в попеременном применении двух шагов <ref>MacKay, David (2003). "Chapter 20. An Example Inference Task: Clustering" (PDF). Information Theory, Inference and Learning Algorithms. Cambridge University Press. pp. 284–292.</ref>: '''распределения''' векторов по кластерам и '''обновления''' центров масс каждого кластера

'''Распределение векторов по кластерам''': на данном шаге каждый вектор распределяется в один из кластеров <math>S_i^{(t)}</math>:
::<math>S_i^{(t)} = \big \{ x_p : \big \| x_p - \mu^{(t)}_i \big \|^2 \le \big \| x_p - \mu^{(t)}_j \big \|^2 \ \forall j, 1 \le j \le k \big\},</math>
'''Обновление центров масс''': на данном шаге вычисляются новые центры масс для кластеров, полученных на предыдущем шаге.
::<math>\mu^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math>

Алгоритм завершается, когда на очередном шаге не происходит изменения центров масс кластеров.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро последовательного алгоритма k-means состоит из двух операций, повторяющихся на каждой итерации алгоритма:
* пересчета центров масс кластеров;
* соотнесения каждого вектора к одному из кластеров.

Пересчет центра масс кластера заключается в нахождении d-мерного вектора, являющегося средним арифметическим d-мерных векторов, принадлежащих кластеру. Эту операцию необходимо выполнять для каждого из K кластеров.

Для соотнесения вектора к одному из кластеров, необходимо для каждого из N вектора посчитать расстояние до центров масс всех K кластеров. Для нахождения расстояния между двумя d-мерными векторами p и q используется Евклидова метрика: <math>\sqrt{\sum_{k=1}^d (p_k-q_k)^2}</math>

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

Инициализация центров масс кластеров

В начале алгоритма осуществляется инициализация центров масс <math>\mu_1^{(1)}, ..., \mu_k^{(1)}</math>, которая может быть реализована двумя возможными способами <ref>Hamerly, G.; Elkan, C. (2002). "Alternatives to the k-means algorithm that find better clusterings" (PDF). Proceedings of the eleventh international conference on Information and knowledge management (CIKM).</ref>:
* случайный выбор центров масс среди исходных наблюдений <math>x_1, x_2, ..., x_n</math>;
* все наблюдения случайным образом распределяются по кластерам <math>S_1, S_2, ..., S_k</math>, а затем для каждого кластера выполняется операция обновления центра масс.

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

На шаге распределения векторов по кластерам производится операция нахождения квадратов расстояний между векторами кластера и центром масс кластера:
::<math>\rho = \big \| x_p - \mu^{(t)}_i \big \|^2</math>

Обновление центров масс кластеров

На шаге обновления центров масс производится операция суммирования векторов кластера:
::<math>\mu^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math>

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

Последовательность исполнения метода следующая:
# Инициализируются центры масс <math>\mu_1^{(1)}, ..., \mu_k^{(1)}</math>
# <math>t := 1</math>
# Для каждого вектора <math>x_i, i = 1, 2, ..., n</math> вычисляется <math>m = \underset{j \in \{1, 2, ..., k\}} {\operatorname{arg\,min}} \big \| x_i - \mu^{(t)}_j \big \|^2</math>, вектор <math>x_i</math> распределяется в кластер <math>S^{(t)}_m</math>
# Для каждого <math>j = 1, 2, ..., k</math> вычисляется <math>\mu^{(t+1)}_j = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math>
# Если <math>\mu^{(t)}_j = \mu^{(t+1)}_j, j = 1, 2, ..., k</math>, завершить выполнение алгоритма, иначе <math>t := t + 1</math>, переход на шаг 3.

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

Для вычисления центра массы кластера, содержащего <math>n_i</math> d-мерных векторов, необходимо:
* <math>n_i * (d - 1)</math> операций сложения
* <math>d</math> операций деления

Для определения центров масс всех k кластеров требуется:
* <math>n * (d - 1)</math> операций сложения
* <math>k * d</math> операций деления

Для определения расстояния между двумя d-мерными векторами, требуется:
* <math>d</math> операций вычитания
* <math>d</math> операций умножения
* <math>d - 1</math> операций сложения

Для определения кластера для n d-мерного векторов, необходимо:
* <math>n * k * d</math> операций вычитания
* <math>n * k * d</math> операций умножения
* <math>n * k * (d - 1)</math> операций сложения

Таким образом, общая сложность одной итерации:
* <math>O(n * k * d)</math> операций сложения/вычитания
* <math>O(n * k * d)</math> операций умножения/деления

Сложность всего алгоритма, состоящего из <math>t</math> итераций: <math>O(t * n * k * d)</math>

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

В данном разделе описывается информационный граф алгоритма k-средних при <math>n = 3, k = 2</math>

На рисунке 1 показана общая структура алгоритма: в качестве входных данных выступает матрица, строками которой являются входные векторы <math>x_1, x_2, x_3</math>, на выходе получается массив из <math>n</math> чисел, где элемент с номером <math>i = 1, 2, 3</math> обозначает номер кластера, которому принадлежит вектор <math>x_i</math>. На шаге <math>init</math> происходит инициализация значений центров масс кластеров, после этого осуществляется итеративное повторение этапов распределения векторов по кластерам (<math>as</math>) и обновления значений центров масс кластеров (<math>up</math>). Когда на очередном шаге обновления центров масс кластеров значения центров масс не изменяются, алгоритм завершает работу, и в качестве выходных данных выступают номера кластеров для каждого из входных векторов.
[[file:k_means_main.png|thumb|center|400px|Рисунок 1. Общая схема работы алгоритма k-средних]]

'''Распределение векторов по кластерам.''' На рисунке 2 изображен информационный граф для этапа распределения векторов по кластерам. В качестве входных данных выступают строки входной матрицы (входные векторы) <math>x_1, x_2, x_3</math> и текущие значения центров масс кластеров <math>\mu_1, \mu_2</math> (вычисленные на этапе инициализации или предшествующего этапа обновления центров масс кластеров). В качестве выходных данных выступают числа <math>m_1, m_2, m_3</math>, где <math>m_i, i = 1, 2, 3</math> - номер кластера, содержащего вектор <math>x_i</math>. Вершинами с пометкой <math>sub</math> обозначены операции векторной разности, вершинами <math>sn</math> - операция вычисления квадрата нормы вектора, вершинами <math>am</math> - операция <math>\underset{i \in \{1, 2\}} {\operatorname{arg\,min}} p_i</math>.
[[file:k_means_info_graph_as.png|thumb|center|400px|Рисунок 2. Граф алгоритма для этапа распределения векторов по кластерам]]
'''Обновление центров масс кластеров.''' На рисунке 3 представлен информационный граф для этапа обновления центров масс кластеров. В качестве входных данных выступают строки входной матрицы (входные векторы) <math>x_1, x_2, x_3</math> с соответствующими номерами кластеров <math>m_1, m_2, m_3</math>, содержащих эти векторы. В качестве выходных данных здесь выступают обновленные значения центров масс кластеров: <math>\mu_1, \mu_2</math>. Вершинами с пометками <math>s_i, i = 1, 2</math> обозначены операции суммирования векторов, принадлежащих кластеру <math>i</math>. Вершинами с пометками <math>cs_i, i = 1, 2</math> обозначены операции вычисления выражения <math>1 / |S_i|</math>, где за <math>S_i</math> обозначен кластер с номером <math>i</math>. Вершинами с пометкой <math>p</math> обозначена операция произведения.
[[file:k_means_info_graph_up.png|thumb|center|400px|Рисунок 3. Граф алгоритма для этапа обновления центров масс кластеров]]

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

Алгоритм кластеризации k средних имеет место массовый параллелизм: в основе каждого из основных этапов алгоритма (распределения векторов по кластерам и обновления центров масс кластеров) лежат циклы, итерации которых являются информационно независимыми.
Учитывая данный факт можно оценить параллельную сложность алгоритма в предположении доступности неограниченного числа необходимых процессоров.

В силу особенностей алгоритма k средних порядок выполнения основных этапов существенен, что не позволяет выполнять их параллельно. Таким образом, итоговая сложность параллельного алгоритма будет определяться, исходя из формулы <math>T = t * (T_{as} + T_{up})</math>, где <math>T_{as}</math> - параллельная сложность этапа распределения векторов по кластерам, <math>T_{up}</math> - параллельная сложность этапа обновления центров масс кластеров, <math>t</math> - общее число итераций алгоритма.

Параллельная сложность этапа распределения векторов по кластерам с учетом доступности неограниченного числа процессоров вычисляется следующим образом: так как вычисление значений <math>\big \| x_i - \mu^{(t)}_j \big \|^2</math> для каждой пары векторов <math>x_i, i = 1, 2, ..., n</math> и <math>\mu^{(t)}_j, j = 1, 2, ..., k</math> можно выполнять независимо и для вычисления этого выражения требуется <math>O(\log d)</math> операций в соответствии с [[Нахождение_частных_сумм_элементов_массива_сдваиванием | параллельной реализацией нахождения сумм элементов массива сдваиванием]]. Параллельная сложность реализации операции нахождения минимума из <math>k</math> элементов определяется как <math>O(\log k)</math>. Таким образом, сложность этапа распределения векторов по кластерам <math>O(\log kd)</math>.

Параллельная сложность этапа обновления центров масс кластеров вычисляется следующим образом: так как обновление значений каждого из центров масс кластеров можно выполнять независимо, параллельная сложность определяется сложностью обновления центра масс самого большого кластера. В худшем случае для нахождения значения выражения <math>\mu^{(t+1)}_j = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math> требуется <math>O(\log n)</math> операций.

С учетом вышесказанного, итоговая параллельная сложность алгоритма k средних определяется выражением <math>O(t * \log kdn)</math>.

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

'''Входные данные''':
* целое неотрицательное число <math>k</math> - количество кластеров;
* матрица координат векторов <math>A</math> размерностью <math>n * d</math>.

'''Объем входных данных''':
* <math>n * d</math> вещественных чисел (если координаты вещественные числа), <math>1</math> целое неотрицательное число.

'''Выходные данные''':
* вектор длины <math>n</math> - для каждого вектора указан номер кластера.

'''Объем выходных данных''':
* <math>n</math> целых неотрицательных чисел.

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

Соотношение последовательной и параллельной сложности алгоритма равно <math>\frac{O(tnkd)}{O(t * \log kdn)}</math>.

Число операций алгоритма k средних оценивается как <math>O(tnkd)</math>, суммарный объем входных и выходных данных равен <math>n(d+1)</math>. Следовательно, вычислительная мощность алгоритма линейна по <math>k</math> и линейна по <math>t</math>.

Стоит отметить следующие ключевые особенности алгоритма k средних:
* Алгоритм прост в реализации и имеет высокую скорость работы по сравнению с другими алгоритмами кластеризации (при удачном выборе начальных значений центров масс кластеров)
* В качестве метрики используется евклидово расстояние, а в качестве меры разброса кластера используется дисперсия
* Количество кластеров k является входным параметром алгоритма, поэтому неправильный выбор этого параметра может негативно повлиять на качество кластеризации
* Сходимость алгоритма к локальному минимуму может породить некорректный конечный результат работы
* Алгоритм очень чувствителен к выбору начальных центров масс кластеров: классический вариант подразумевает случайный их выбор, что может являться источником погрешности. Из этого и предыдущего свойства следует то, что алгоритм не является устойчивым.

Как и любой другой алгоритм кластеризации, результат работы алгоритма k средних зависит от того, удовлетворяет ли входной набор данных предположениям, на которые опираются алгоритмы кластеризации. Таким образом, на одних наборах данных алгоритм может показывать хорошие результаты, но на других выдавать некорректные результаты.

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

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

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

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

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

=== Масштабируемость алгоритма и его реализации ===
Исследование масштабируемости алгоритма k-means в зависимости от количества используемых процессов было проведено в статье Кумара<ref>Kumar, J., Mills, R. T., Hoffman, F. M., & Hargrove, W. W. (2011). Parallel k-means clustering for quantitative ecoregion delineation using large data sets. Procedia Computer Science, 4, 1602-1611.</ref>. Исследование происходило на суперкомпьютере Jaguar - Cray XT5<ref>https://www.top500.org/system/176029</ref>. На момент экспериментов данный суперкомпьютер имел следующую конфигурацию: 18,688 вычислительных узлов с двумя шестнадцатиядерными процессорами AMD Opteron 2435 (Istanbul) 2.6 GHz, 16 GB of DDR2-800 оперативной памяти, и SeaStar 2+ роутер. Всего он состоял из 224,256 вычислительных ядер, 300 TB памяти, и пиковой производительностью 2.3 petaflops.

Реализация алгоритма была выполнена на языке программирования C с использованием MPI.

Объем данных составлял 84 гигабайта, количество объектов (d-мерных векторов) n равнялось 1,024,767,667, размерность векторов d равнялась 22, количество кластеров k равнялось 1000.

На рисунке 4 показана зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров. Можно отметить, что время, затраченное на чтение данных и запись результатов кластеризации, практически не изменяется с увеличением количества задействованных процессоров. Время же работы самого алгоритма кластеризации уменьшается с увеличением количества процессоров.
[[Файл:k-means-proc-scalability.png|thumb|center|700px|Рисунок 4. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров.]]

Также было произведено самостоятельное исследование масштабируемости алгоритма. Исследование производилось на суперкомпьютере "Blue Gene/P"<ref>http://hpc.cmc.msu.ru/bgp</ref>.

Набор и границы значений изменяемых параметров запуска реализации алгоритма:

* число процессоров [1, 2, 4, 8, 16, 32, 64, 128, 256, 512];
* количество объектов [5000, 10000, 25000, 50000].

Был использован набор данных ''Dataset for Sensorless Drive Diagnosis Data Set''<ref>PASCHKE, Fabian ; BAYER, Christian ; BATOR, Martyna ; MÃ–NKS, Uwe ; DICKS, Alexander ; ENGE-ROSENBLATT, Olaf ; LOHWEG, Volker: Sensorlose ZustandsÃ¼berwachung an Synchronmotoren, Bd. 46. In: HOFFMANN, Frank; HÃœLLERMEIER, Eyke (Hrsg.): Proceedings 23. Workshop Computational Intelligence. Karlsruhe : KIT Scientific Publishing, 2013 (Schriftenreihe des Instituts fÃ¼r Angewandte Informatik - Automatisierungstechnik am Karlsruher Institut fÃ¼r Technologie, 46), S. 211-225</ref> из репозитория ''Machine learning repository''<ref>https://archive.ics.uci.edu/ml/datasets/Dataset+for+Sensorless+Drive+Diagnosis</ref>.

Исследуемый набор данных содержит векторы, размерность которых равна 49. Компоненты векторов являются вещественными числами. Количество кластеров равно 11. Пропущенные значения отсутствуют.

Для исследования масштабируемости алгоритма была использована реализация на языке C с использованием MPI<ref>http://users.eecs.northwestern.edu/~wkliao/Kmeans/index.html</ref>. Код можно найти здесь: https://github.com/serban/kmeans.

На рисунке 5 показана зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров. Можно видеть, что при увеличении количества процессоров в N раз, время работы алгоритма уменьшается примерно в N раз (при условии, что количество объектов остается неизменным). Также можно отметить, что при фиксированном количестве процессоров, зависимость времени работы алгоритма от количества объектов также близка к линейной.
[[Файл:Heatmap_kmeans.png|thumb|center|900px|Рисунок 5. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров.]]

На рисунке 6 показана зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров (при фиксированном количестве объектов, равном 50000). При визуализации была использована логарифмическая шкала. Можно отметить, что при заданном наборе данных можно наблюдать линейную зависимость времени работы алгоритма от количества используемых процессоров, что согласуется с теоретической оценкой сложности последовательной версии алгоритма.
[[Файл:50000kmeans.png|thumb|center|900px|Рисунок 6. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров (количество объектов равно 50000).]]

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

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

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

Существуют следующие реализации алгоритма k-средних:
* [http://scikit-learn.org/ scikit-learn] библиотека машинного обучения для языка Python.
* [https://www.scipy.org/ SciPy] библиотека на языке Python, содержащая большое число реализаций различных алгоритмов, в том числе ''k''-средних.
* [http://elki.dbs.ifi.lmu.de ELKI] библиотека для анализа данных на языке программирования Java, содержит различные алгоритмы кластеризации, в том числе ''k''-средних.
* [http://mlpack.org MLPACK] библиотека машинного обучения для C++, содержит реализацию алгоритма ''k''-средних.
* [https://github.com/JuliaStats/Clustering.jl Julia k-means] реализация алгоритма ''k''-средних на языке программирования Julia.
* [http://opencv.org/ OpenCV] библиотека содержит реализацию ''k''-средних.
* [http://mahout.apache.org Apache Mahout] содержит реализацию алгоритма ''k''-средних на базе MapReduce.
* [http://www.cs.waikato.ac.nz/~ml/weka Weka] библиотека и инструмент для анализа данных на языке Java.
* [http://torch.ch/ Torch] библиотека машинного обучения на базе языка программирования Lua.
* [https://spark.apache.org/ Apache Spark MLlib] содержит распределенную реализацию алгоритма ''k''-средних.
* [http://www.accord-framework.net/ Accord.NET] содержит несколько различных реализаций ''k''-средних на языке C#.
* [https://www.r-bloggers.com/k-means-clustering-in-r/ R k-means] реализация ''k''-средних на языке R.

== Литература ==
<references \>

Файл:Heatmap kmeans.png

2016-11-17T21:45:27Z

Parkhomenko:

Файл:50000kmeans.png

2016-11-17T21:45:01Z

Parkhomenko:

Участник:Parkhomenko/Алгоритм k средних

2016-10-12T09:48:11Z

Parkhomenko: /* Масштабируемость алгоритма и его реализации */

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

Основные авторы описания: [[Участник:Parkhomenko|П.А.Пархоменко]], [[Участник:Ivan.mashonskiy|И.Д.Машонский]]
== Свойства и структура алгоритмов ==

=== Общее описание алгоритма ===
Алгоритм k средних (англ. k-means) - один из алгоритмов машинного обучения, решающий задачу кластеризации. Он был изобретен в середине 1950-х математиком Гуго Штейнгаузом<ref>Steinhaus H. (1956). Sur la division des corps materiels en parties. Bull. Acad. Polon. Sci., C1. III vol IV: 801—804.</ref> и Стюартом Ллойдом<ref>Lloyd S. (1957). Least square quantization in PCM’s. Bell Telephone Laboratories Paper.</ref>. Алгоритм стал особо популярным после публикации Маккуина<ref>MacQueen J. (1967). Some methods for classification and analysis of multivariate observations. In Proc. 5th Berkeley Symp. on Math. Statistics and Probability, pages 281—297.</ref>, в которой впервые был использован термин “k-means”.

Задача алгоритма кластеризации заключается в разбиении N объектов (d-мерных векторов) на K групп (кластеров). Каждый вектор может принадлежать только одному кластеру. Количество кластеров K фиксировано, оно задается в качестве параметра.

K-means является итерационным алгоритмом, разновидностью EM-алгоритма. Основная идея работы алгоритма заключается в проведении некоторого количества итераций, на каждой из которых происходит пересчет центра масс для каждого кластера, полученного на предыдущей итерации. После этого векторы перераспределяются по кластерам: вектор относится к тому кластеру, расстояние до центра масс которого минимально. Алгоритм завершает работу в том случае, если на очередной итерации центры масс кластеров не изменились.

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

Исходные данные: множество d-мерных векторов (наблюдений) <math>X</math> = <math>\{x_1, x_2, ..., x_n\}</math>, число кластеров <math>k \in \mathbb{N}</math>

В результате работы алгоритма исходное множество векторов <math>X</math> разбивается на <math>k</math> непересекающихся множеств (кластеров) <math>S_1, S_2, ..., S_k</math>, таких что <math>X = {\bigcup \limits _{i = 1}^k S_i} </math> и значение <math>\sum_{i=1}^{k} \sum_{\mathbf x \in S_i} \left\| \mathbf x - \mu_i \right\|^2 </math> — минимально для всех возможных наборов <math>S_1, S_2, ..., S_k</math>.
Под <math>\mu_i</math> здесь подразумевается центр масс векторов из множества <math>S_i</math>.

Первоначальные значения центров масс <math>\mu_1^{(1)}, ..., \mu_k^{(1)}</math> определяются в начале работы алгоритма случайным образом среди векторов множества <math>X</math>.

Алгоритм заключается в попеременном применении двух шагов: '''распределения''' векторов по кластерам и '''обновления''' центров масс каждого кластера

'''Распределение векторов по кластерам''': на данном шаге каждый вектор распределяется в один из кластеров <math>S_i^{(t)}</math>:
::<math>S_i^{(t)} = \big \{ x_p : \big \| x_p - \mu^{(t)}_i \big \|^2 \le \big \| x_p - \mu^{(t)}_j \big \|^2 \ \forall j, 1 \le j \le k \big\},</math>
'''Обновление центров масс''': на данном шаге вычисляются новые центры масс для кластеров, полученных на предыдущем шаге.
::<math>\mu^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math>

Алгоритм завершается, когда на очередном шаге не происходит изменения центров масс кластеров.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро последовательного алгоритма k-means состоит из двух операций, повторяющихся на каждой итерации алгоритма:
* пересчета центров масс кластеров;
* соотнесения каждого вектора к одному из кластеров.

Пересчет центра масс кластера заключается в нахождении d-мерного вектора, являющегося средним арифметическим d-мерных векторов, принадлежащих кластеру. Эту операцию необходимо выполнять для каждого из K кластеров.

Для соотнесения вектора к одному из кластеров, необходимо для каждого из N вектора посчитать расстояние до центров масс всех K кластеров. Для нахождения расстояния между двумя d-мерными векторами p и q используется Евклидова метрика: <math>\sqrt{\sum_{k=1}^d (p_k-q_k)^2}</math>

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

В начале алгоритма осуществляется инициализация центров масс <math>\mu_1^{(1)}, ..., \mu_k^{(1)}</math>, которая может быть реализована двумя возможными способами:
* случайный выбор центров масс среди исходных наблюдений <math>x_1, x_2, ..., x_n</math>;
* все наблюдения случайным образом распределяются по кластерам <math>S_1, S_2, ..., S_k</math>, а затем для каждого кластера выполняется операция обновления центра масс.

На шаге распределения векторов по кластерам производится операция нахождения квадратов расстояний между векторами кластера и центром масс кластера:
::<math>\rho = \big \| x_p - \mu^{(t)}_i \big \|^2</math>

На шаге обновления центров масс производится операция суммирования векторов кластера:
::<math>\mu^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math>

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

Последовательность исполнения метода следующая:
# Инициализируются центры масс <math>\mu_1^{(1)}, ..., \mu_k^{(1)}</math>
# <math>t := 1</math>
# Для каждого вектора <math>x_i, i = 1, 2, ..., n</math> вычисляется <math>m = \underset{j \in \{1, 2, ..., k\}} {\operatorname{arg\,min}} \big \| x_i - \mu^{(t)}_j \big \|^2</math>, вектор <math>x_i</math> распределяется в кластер <math>S^{(t)}_m</math>
# Для каждого <math>j = 1, 2, ..., k</math> вычисляется <math>\mu^{(t+1)}_j = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math>
# Если <math>\mu^{(t)}_j = \mu^{(t+1)}_j, j = 1, 2, ..., k</math>, завершить выполнение алгоритма, иначе <math>t := t + 1</math>, переход на шаг 3.

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

Для вычисления центра массы кластера, содержащего <math>n_i</math> d-мерных векторов, необходимо:
* <math>n_i * (d - 1)</math> операций сложения
* <math>d</math> операций деления

Для определения центров масс всех k кластеров требуется:
* <math>n * (d - 1)</math> операций сложения
* <math>k * d</math> операций деления

Для определения расстояния между двумя d-мерными векторами, требуется:
* <math>d</math> операций вычитания
* <math>d</math> операций умножения
* <math>d - 1</math> операций сложения

Для определения кластера для n d-мерного векторов, необходимо:
* <math>n * k * d</math> операций вычитания
* <math>n * k * d</math> операций умножения
* <math>n * k * (d - 1)</math> операций сложения

Таким образом, общая сложность одной итерации:
* <math>O(n * k * d)</math> операций сложения/вычитания
* <math>O(n * k * d)</math> операций умножения/деления

Сложность всего алгоритма, состоящего из m итераций: <math>O(m * n * k * d)</math>

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

В данном разделе описывается информационный граф алгоритма k-средних при <math>n = 3, k = 2</math>

На рисунке 1 показана общая структура алгоритма: в качестве входных данных выступает матрица, строками которой являются входные векторы <math>x_1, x_2, x_3</math>, на выходе получается массив из <math>n</math> чисел, где элемент с номером <math>i = 1, 2, 3</math> обозначает номер кластера, которому принадлежит вектор <math>x_i</math>. На шаге <math>init</math> происходит инициализация значений центров масс кластеров, после этого осуществляется итеративное повторение этапов распределения векторов по кластерам (<math>as</math>) и обновления значений центров масс кластеров (<math>up</math>).
[[file:k_means_schema.svg|thumb|center||Рисунок 1. Общая схема работы алгоритма k-средних]]

'''Распределение векторов по кластерам.''' На рисунке 2 изображен информационный граф для этапа распределения векторов по кластерам. В качестве входных данных выступают строки входной матрицы (входные векторы) <math>x_1, x_2, x_3</math> и текущие значения центров масс кластеров <math>\mu_1, \mu_2</math> (вычисленные на этапе инициализации или предшествующего этапа обновления центров масс кластеров). В качестве выходных данных выступают числа <math>m_1, m_2, m_3</math>, где <math>m_i, i = 1, 2, 3</math> - номер кластера, содержащего вектор <math>x_i</math>. Вершинами с пометкой <math>sub</math> обозначены операции векторной разности, врешинами <math>sn</math> - операция вычисления квадрата нормы вектора, вершинами <math>am</math> - операция <math>\underset{i \in \{1, 2\}} {\operatorname{arg\,min}} p_i</math>.
[[file:k_means_info_graph_as.svg|thumb|center||Рисунок 2. Граф алгоритма для этапа распределения векторов по кластерам]]
'''Обновление центро масс кластеров.''' На рисунке 3 представлен информационный граф для этапа обновления центров масс кластеров. В качестве входных данных выступают строки входной матрицы (входные векторы) <math>x_1, x_2, x_3</math> с соответствующими номерами кластеров <math>m_1, m_2, m_3</math>, содержащих эти векторы. В качестве выходных данных здесь выступают обновленные значения центров масс кластеров: <math>\mu_1, \mu_2</math>. Вершинами с пометками <math>s_i, i = 1, 2</math> обозначены операции суммирования векторов, принадлежащих кластеру <math>i</math>. Вершинами с пометками <math>cs_i, i = 1, 2</math> обозначены операции вычисления выражения <math>1 / |S_i|</math>, где за <math>S_i</math> обозначен кластер с номером <math>i</math>. Вершинами с пометкой <math>p</math> обозначена операция произведения.
[[file:k_means_info_graph_up.svg|thumb|center||Рисунок 3. Граф алгоритма для этапа обновления центров масс кластеров]]

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

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

'''Входные данные''':
* целое неотрицательное число <math>k</math> - количество кластеров;
* матрица координат векторов <math>A</math> размерностью <math>n * d</math>.

'''Объем входных данных''':
* <math>n * d</math> вещественных чисел (если координаты вещественные числа), <math>1</math> целое неотрицательное число.

'''Выходные данные''':
* вектор длины <math>n</math> - для каждого вектора указан номер кластера.

'''Объем выходных данных''':
* <math>n</math> целых неотрицательных чисел.

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

Стоит отметить следующие ключевые особенности алгоритма k средних:
* Алгоритм прост в реализации и имеет высокую скорость работы по сравнению с другими алгоритмами кластеризации (при удачном выборе начальных значений центров масс кластеров)
* В качестве метрики используется евклидово расстояние, а в качестве меры разброса кластера используется дисперсия
* Количество кластеров k является входным параметром алгоритма, поэтому неправильный выбор этого параметра может негативно повлиять на качество кластеризации
* Сходимость алгоритма к локальному минимуму может породить некорректный конечный результат работы
* Алгоритм очень чувствителен к выбору начальных центров масс кластеров: классический вариант подразумевает случайный их выбор, что может являться источником погрешности. Из этого и предыдущего свойства следует то, что алгоритм не является устойчивым.

Как и любой другой алгоритм кластеризации, результат работы алгоритма k средних зависит от того, удовлетворяет ли входной набор данных предположениям, на которые опираются алгоритмы кластеризации. Таким образом, на одних наборах данных алгоритм может показывать хорошие результаты, но на других выдавать некорректные результаты.

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

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

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

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

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

=== Масштабируемость алгоритма и его реализации ===
Исследование масштабируемости алгоритма k-means в зависимости от количества используемых процессов было проведено в статье Кумара<ref>Kumar J. et al. Parallel k-means clustering for quantitative ecoregion delineation using large data sets //Procedia Computer Science. – 2011. – Т. 4. – С. 1602-1611.</ref>. Исследование происходило на суперкомпьютере Jaguar - Cray XT5<ref>https://www.top500.org/system/176029</ref>. На момент экспериментов данный суперкомпьютер имел следующую конфигурацию: 18,688 вычислительных узлов с двумя шестнадцатиядерными процессорами AMD Opteron 2435 (Istanbul) 2.6 GHz, 16 GB of DDR2-800 оперативной памяти, и SeaStar 2+ роутер. Всего он состоял из 224,256 вычислительных ядер, 300 TB памяти, и пиковой производительностью 2.3 petaflops.

Реализация алгоритма была выполнена на языке программирования C с использованием MPI.

Объем данных составлял 84 гигабайта, количество объектов (m-мерных векторов) n равнялось 1,024,767,667, размерность векторов m равнялось 22, количество кластеров k равнялось 1000.

На рисунке 4 показана зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров. Можно отметить, что время, затраченное на чтение данных и запись результатов кластеризации, практически не изменяется с увеличением количества задействованных процессоров. Время же работы самого алгоритма кластеризации уменьшается с увеличением количества процессоров.
[[Файл:k-means-proc-scalability.png|thumb|center|700px|Рисунок 4. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров.]]

Ниже представлены результаты исследования времени работы алгоритма k-means в зависимости от количества кластеров k и количества векторов n. Для исследования использовалась реализация k-means на языке программирования C (с использованием OpenMP). Тестирование происходило на 8 процессорах. Затраченное время считалось как среднее арифметическое 5 запусков алгоритма.

На рисунке 5 показана зависимость времени работы алгоритма от количества кластеров k. Количество векторов n равно 100000.
[[Файл:K-means-k.png|thumb|center|700px|Рисунок 5. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества кластеров k.]]

На рисунке 6 показана зависимость времени работы алгоритма от количества векторов n. Количество кластеров k равно 160.
[[Файл:K-means-n.png|thumb|center|700px|Рисунок 6. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества векторов n.]]

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

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

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

Существуют следующие реализации алгоритма k-средних:
* [http://scikit-learn.org/ scikit-learn] библиотека машинного обучения для языка Python.
* [https://www.scipy.org/ SciPy] библиотека на языке Python, содержащая большое число реализаций различных алгоритмов, в том числе ''k''-средних.
* [http://elki.dbs.ifi.lmu.de ELKI] библиотека для анализа данных на языке программирования Java, содержит различные алгоритмы кластеризации, в том числе ''k''-средних.
* [http://mlpack.org MLPACK] библиотека машинного обучения для C++, содержит реализацию алгоритма ''k''-средних.
* [https://github.com/JuliaStats/Clustering.jl Julia k-means] реализация алгоритма ''k''-средних на языке программирования Julia.
* [http://opencv.org/ OpenCV] библиотека содержит реализацию ''k''-средних.
* [http://mahout.apache.org Apache Mahout] содержит реализацию алгоритма ''k''-средних на базе MapReduce.
* [http://www.cs.waikato.ac.nz/~ml/weka Weka] библиотека и инструмент для анализа данных на языке Java.
* [http://torch.ch/ Torch] библиотека машинного обучения на базе языка программирования Lua.
* [https://spark.apache.org/ Apache Spark MLlib] содержит распределенную реализацию алгоритма ''k''-средних.
* [http://www.accord-framework.net/ Accord.NET] содержит несколько различных реализаций ''k''-средних на языке C#.
* [https://www.r-bloggers.com/k-means-clustering-in-r/ R k-means] реализация ''k''-средних на языке R.

== Литература ==
<references \>

Участник:Parkhomenko/Алгоритм k средних

2016-10-12T09:45:29Z

Parkhomenko: /* Масштабируемость алгоритма и его реализации */

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

Основные авторы описания: [[Участник:Parkhomenko|П.А.Пархоменко]], [[Участник:Ivan.mashonskiy|И.Д.Машонский]]
== Свойства и структура алгоритмов ==

=== Общее описание алгоритма ===
Алгоритм k средних (англ. k-means) - один из алгоритмов машинного обучения, решающий задачу кластеризации. Он был изобретен в середине 1950-х математиком Гуго Штейнгаузом<ref>Steinhaus H. (1956). Sur la division des corps materiels en parties. Bull. Acad. Polon. Sci., C1. III vol IV: 801—804.</ref> и Стюартом Ллойдом<ref>Lloyd S. (1957). Least square quantization in PCM’s. Bell Telephone Laboratories Paper.</ref>. Алгоритм стал особо популярным после публикации Маккуина<ref>MacQueen J. (1967). Some methods for classification and analysis of multivariate observations. In Proc. 5th Berkeley Symp. on Math. Statistics and Probability, pages 281—297.</ref>, в которой впервые был использован термин “k-means”.

Задача алгоритма кластеризации заключается в разбиении N объектов (d-мерных векторов) на K групп (кластеров). Каждый вектор может принадлежать только одному кластеру. Количество кластеров K фиксировано, оно задается в качестве параметра.

K-means является итерационным алгоритмом, разновидностью EM-алгоритма. Основная идея работы алгоритма заключается в проведении некоторого количества итераций, на каждой из которых происходит пересчет центра масс для каждого кластера, полученного на предыдущей итерации. После этого векторы перераспределяются по кластерам: вектор относится к тому кластеру, расстояние до центра масс которого минимально. Алгоритм завершает работу в том случае, если на очередной итерации центры масс кластеров не изменились.

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

Исходные данные: множество d-мерных векторов (наблюдений) <math>X</math> = <math>\{x_1, x_2, ..., x_n\}</math>, число кластеров <math>k \in \mathbb{N}</math>

В результате работы алгоритма исходное множество векторов <math>X</math> разбивается на <math>k</math> непересекающихся множеств (кластеров) <math>S_1, S_2, ..., S_k</math>, таких что <math>X = {\bigcup \limits _{i = 1}^k S_i} </math> и значение <math>\sum_{i=1}^{k} \sum_{\mathbf x \in S_i} \left\| \mathbf x - \mu_i \right\|^2 </math> — минимально для всех возможных наборов <math>S_1, S_2, ..., S_k</math>.
Под <math>\mu_i</math> здесь подразумевается центр масс векторов из множества <math>S_i</math>.

Первоначальные значения центров масс <math>\mu_1^{(1)}, ..., \mu_k^{(1)}</math> определяются в начале работы алгоритма случайным образом среди векторов множества <math>X</math>.

Алгоритм заключается в попеременном применении двух шагов: '''распределения''' векторов по кластерам и '''обновления''' центров масс каждого кластера

'''Распределение векторов по кластерам''': на данном шаге каждый вектор распределяется в один из кластеров <math>S_i^{(t)}</math>:
::<math>S_i^{(t)} = \big \{ x_p : \big \| x_p - \mu^{(t)}_i \big \|^2 \le \big \| x_p - \mu^{(t)}_j \big \|^2 \ \forall j, 1 \le j \le k \big\},</math>
'''Обновление центров масс''': на данном шаге вычисляются новые центры масс для кластеров, полученных на предыдущем шаге.
::<math>\mu^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math>

Алгоритм завершается, когда на очередном шаге не происходит изменения центров масс кластеров.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро последовательного алгоритма k-means состоит из двух операций, повторяющихся на каждой итерации алгоритма:
* пересчета центров масс кластеров;
* соотнесения каждого вектора к одному из кластеров.

Пересчет центра масс кластера заключается в нахождении d-мерного вектора, являющегося средним арифметическим d-мерных векторов, принадлежащих кластеру. Эту операцию необходимо выполнять для каждого из K кластеров.

Для соотнесения вектора к одному из кластеров, необходимо для каждого из N вектора посчитать расстояние до центров масс всех K кластеров. Для нахождения расстояния между двумя d-мерными векторами p и q используется Евклидова метрика: <math>\sqrt{\sum_{k=1}^d (p_k-q_k)^2}</math>

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

В начале алгоритма осуществляется инициализация центров масс <math>\mu_1^{(1)}, ..., \mu_k^{(1)}</math>, которая может быть реализована двумя возможными способами:
* случайный выбор центров масс среди исходных наблюдений <math>x_1, x_2, ..., x_n</math>;
* все наблюдения случайным образом распределяются по кластерам <math>S_1, S_2, ..., S_k</math>, а затем для каждого кластера выполняется операция обновления центра масс.

На шаге распределения векторов по кластерам производится операция нахождения квадратов расстояний между векторами кластера и центром масс кластера:
::<math>\rho = \big \| x_p - \mu^{(t)}_i \big \|^2</math>

На шаге обновления центров масс производится операция суммирования векторов кластера:
::<math>\mu^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math>

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

Последовательность исполнения метода следующая:
# Инициализируются центры масс <math>\mu_1^{(1)}, ..., \mu_k^{(1)}</math>
# <math>t := 1</math>
# Для каждого вектора <math>x_i, i = 1, 2, ..., n</math> вычисляется <math>m = \underset{j \in \{1, 2, ..., k\}} {\operatorname{arg\,min}} \big \| x_i - \mu^{(t)}_j \big \|^2</math>, вектор <math>x_i</math> распределяется в кластер <math>S^{(t)}_m</math>
# Для каждого <math>j = 1, 2, ..., k</math> вычисляется <math>\mu^{(t+1)}_j = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math>
# Если <math>\mu^{(t)}_j = \mu^{(t+1)}_j, j = 1, 2, ..., k</math>, завершить выполнение алгоритма, иначе <math>t := t + 1</math>, переход на шаг 3.

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

Для вычисления центра массы кластера, содержащего <math>n_i</math> d-мерных векторов, необходимо:
* <math>n_i * (d - 1)</math> операций сложения
* <math>d</math> операций деления

Для определения центров масс всех k кластеров требуется:
* <math>n * (d - 1)</math> операций сложения
* <math>k * d</math> операций деления

Для определения расстояния между двумя d-мерными векторами, требуется:
* <math>d</math> операций вычитания
* <math>d</math> операций умножения
* <math>d - 1</math> операций сложения

Для определения кластера для n d-мерного векторов, необходимо:
* <math>n * k * d</math> операций вычитания
* <math>n * k * d</math> операций умножения
* <math>n * k * (d - 1)</math> операций сложения

Таким образом, общая сложность одной итерации:
* <math>O(n * k * d)</math> операций сложения/вычитания
* <math>O(n * k * d)</math> операций умножения/деления

Сложность всего алгоритма, состоящего из m итераций: <math>O(m * n * k * d)</math>

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

В данном разделе описывается информационный граф алгоритма k-средних при <math>n = 3, k = 2</math>

На рисунке 1 показана общая структура алгоритма: в качестве входных данных выступает матрица, строками которой являются входные векторы <math>x_1, x_2, x_3</math>, на выходе получается массив из <math>n</math> чисел, где элемент с номером <math>i = 1, 2, 3</math> обозначает номер кластера, которому принадлежит вектор <math>x_i</math>. На шаге <math>init</math> происходит инициализация значений центров масс кластеров, после этого осуществляется итеративное повторение этапов распределения векторов по кластерам (<math>as</math>) и обновления значений центров масс кластеров (<math>up</math>).
[[file:k_means_schema.svg|thumb|center||Рисунок 1. Общая схема работы алгоритма k-средних]]

'''Распределение векторов по кластерам.''' На рисунке 2 изображен информационный граф для этапа распределения векторов по кластерам. В качестве входных данных выступают строки входной матрицы (входные векторы) <math>x_1, x_2, x_3</math> и текущие значения центров масс кластеров <math>\mu_1, \mu_2</math> (вычисленные на этапе инициализации или предшествующего этапа обновления центров масс кластеров). В качестве выходных данных выступают числа <math>m_1, m_2, m_3</math>, где <math>m_i, i = 1, 2, 3</math> - номер кластера, содержащего вектор <math>x_i</math>. Вершинами с пометкой <math>sub</math> обозначены операции векторной разности, врешинами <math>sn</math> - операция вычисления квадрата нормы вектора, вершинами <math>am</math> - операция <math>\underset{i \in \{1, 2\}} {\operatorname{arg\,min}} p_i</math>.
[[file:k_means_info_graph_as.svg|thumb|center||Рисунок 2. Граф алгоритма для этапа распределения векторов по кластерам]]
'''Обновление центро масс кластеров.''' На рисунке 3 представлен информационный граф для этапа обновления центров масс кластеров. В качестве входных данных выступают строки входной матрицы (входные векторы) <math>x_1, x_2, x_3</math> с соответствующими номерами кластеров <math>m_1, m_2, m_3</math>, содержащих эти векторы. В качестве выходных данных здесь выступают обновленные значения центров масс кластеров: <math>\mu_1, \mu_2</math>. Вершинами с пометками <math>s_i, i = 1, 2</math> обозначены операции суммирования векторов, принадлежащих кластеру <math>i</math>. Вершинами с пометками <math>cs_i, i = 1, 2</math> обозначены операции вычисления выражения <math>1 / |S_i|</math>, где за <math>S_i</math> обозначен кластер с номером <math>i</math>. Вершинами с пометкой <math>p</math> обозначена операция произведения.
[[file:k_means_info_graph_up.svg|thumb|center||Рисунок 3. Граф алгоритма для этапа обновления центров масс кластеров]]

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

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

'''Входные данные''':
* целое неотрицательное число <math>k</math> - количество кластеров;
* матрица координат векторов <math>A</math> размерностью <math>n * d</math>.

'''Объем входных данных''':
* <math>n * d</math> вещественных чисел (если координаты вещественные числа), <math>1</math> целое неотрицательное число.

'''Выходные данные''':
* вектор длины <math>n</math> - для каждого вектора указан номер кластера.

'''Объем выходных данных''':
* <math>n</math> целых неотрицательных чисел.

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

Стоит отметить следующие ключевые особенности алгоритма k средних:
* Алгоритм прост в реализации и имеет высокую скорость работы по сравнению с другими алгоритмами кластеризации (при удачном выборе начальных значений центров масс кластеров)
* В качестве метрики используется евклидово расстояние, а в качестве меры разброса кластера используется дисперсия
* Количество кластеров k является входным параметром алгоритма, поэтому неправильный выбор этого параметра может негативно повлиять на качество кластеризации
* Сходимость алгоритма к локальному минимуму может породить некорректный конечный результат работы
* Алгоритм очень чувствителен к выбору начальных центров масс кластеров: классический вариант подразумевает случайный их выбор, что может являться источником погрешности. Из этого и предыдущего свойства следует то, что алгоритм не является устойчивым.

Как и любой другой алгоритм кластеризации, результат работы алгоритма k средних зависит от того, удовлетворяет ли входной набор данных предположениям, на которые опираются алгоритмы кластеризации. Таким образом, на одних наборах данных алгоритм может показывать хорошие результаты, но на других выдавать некорректные результаты.

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

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

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

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

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

=== Масштабируемость алгоритма и его реализации ===
Исследование масштабируемости алгоритма k-means в зависимости от количества используемых процессов было проведено в статье Кумара<ref>Kumar J. et al. Parallel k-means clustering for quantitative ecoregion delineation using large data sets //Procedia Computer Science. – 2011. – Т. 4. – С. 1602-1611.</ref>. Исследование происходило на суперкомпьютере Jaguar - Cray XT5<ref>https://www.top500.org/system/176029</ref>. На момент экспериментов данный суперкомпьютер имел следующую конфигурацию: 18,688 вычислительных узлов с двумя шестнадцатиядерными процессорами AMD Opteron 2435 (Istanbul) 2.6 GHz, 16 GB of DDR2-800 оперативной памяти, и SeaStar 2+ роутер. Всего он состоял из 224,256 вычислительных ядер, 300 TB памяти, и пиковой производительностью 2.3 petaflops.

Реализация алгоритма была выполнена на языке программирования C с использованием MPI.

Объем данных составлял 84 гигабайта, количество объектов (m-мерных векторов) n равнялось 1,024,767,667, размерность векторов m равнялось 22, количество кластеров k равнялось 1000.

На рисунке 4 показана зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров. Можно отметить, что время, затраченное на чтение данных и запись результатов кластеризации, практически не изменяется с увеличением количества задействованных процессоров. Время же работы самого алгоритма кластеризации уменьшается с увеличением количества процессоров.
[[Файл:k-means-proc-scalability.png|thumb|center|700px|Рисунок 4. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров.]]

Ниже представлены результаты исследования времени работы алгоритма k-means в зависимости от количества кластеров k и количества векторов n. Для исследования использовалась реализация k-means на языке программирования C (с использованием OpenMP). Тестирование происходило на 8 процессорах. Затраченное время считалось как среднее арифметическое 5 запусков алгоритма.

На рисунке 5 показана зависимость времени работы алгоритма от количества кластеров k. Количество векторов n равно 100000.
[[Файл:k-means-k.png|thumb|center|700px|Рисунок 5. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества кластеров k.]]

На рисунке 6 показана зависимость времени работы алгоритма от количества векторов n. Количество кластеров k равно 160.
[[Файл:k-means-n.png|thumb|center|700px|Рисунок 6. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества векторов n.]]

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

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

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

Существуют следующие реализации алгоритма k-средних:
* [http://scikit-learn.org/ scikit-learn] библиотека машинного обучения для языка Python.
* [https://www.scipy.org/ SciPy] библиотека на языке Python, содержащая большое число реализаций различных алгоритмов, в том числе ''k''-средних.
* [http://elki.dbs.ifi.lmu.de ELKI] библиотека для анализа данных на языке программирования Java, содержит различные алгоритмы кластеризации, в том числе ''k''-средних.
* [http://mlpack.org MLPACK] библиотека машинного обучения для C++, содержит реализацию алгоритма ''k''-средних.
* [https://github.com/JuliaStats/Clustering.jl Julia k-means] реализация алгоритма ''k''-средних на языке программирования Julia.
* [http://opencv.org/ OpenCV] библиотека содержит реализацию ''k''-средних.
* [http://mahout.apache.org Apache Mahout] содержит реализацию алгоритма ''k''-средних на базе MapReduce.
* [http://www.cs.waikato.ac.nz/~ml/weka Weka] библиотека и инструмент для анализа данных на языке Java.
* [http://torch.ch/ Torch] библиотека машинного обучения на базе языка программирования Lua.
* [https://spark.apache.org/ Apache Spark MLlib] содержит распределенную реализацию алгоритма ''k''-средних.
* [http://www.accord-framework.net/ Accord.NET] содержит несколько различных реализаций ''k''-средних на языке C#.
* [https://www.r-bloggers.com/k-means-clustering-in-r/ R k-means] реализация ''k''-средних на языке R.

== Литература ==
<references \>

Обсуждение участника:Lineprinter

2016-10-12T09:19:14Z

Parkhomenko:

== Перенос ==

Статья:[[Алгоритм_Ланцоша_с_полной_переортогонализацией]];
Выполняет:[[Участник:Sfedotov| Федотов С.А.]]

Статья:[[Алгоритм_k-средних]]
Выполняют: Богомазов Евгений, [[Участник:Илья_Егоров|Егоров Илья]]

Статья: algowiki-project.org/ru/Решение_задачи_Коши_для_системы_ОДУ_методом_Рунге-Кутты_4_порядка;
Выполняют: Алимов Дамир и Антон Лесничий

Статья: Алгоритм кластеризации, основанный на минимальном остовном дереве;
Выполняет: Стандрик Антон Сергеевич (Astandrik)

Статья: [[Нахождение_собственных_чисел_квадратной_матрицы_методом_QR_разложения_(3)|Нахождение собственных чисел квадратной матрицы методом QR разложения (3)]];
Выполняют: [[Участник:Смирнова_Александра|Смирнова А.С.]], [[Участник:Александра_Киямова|Киямова А.]]

Статья: [[Метод_Якоби_вычисления_сингулярных_чисел_и_векторов]];
Выполняют: [[Участница:Почернина_Елена| Почернина Елена]] и [[Участница:Светлана|Костюкова Светлана]]

Статья: [[Метод_Ньютона_для_решения_систем_нелинейных_уравнений(2)]];
Выполняют: [[Участник:Oleggium|Гирняк О.Р.]], [[Участник:Dimx19|Васильков Д.А.]]

Статья: [[Алгоритм_кластеризации_с_использованием_представлений]];
Выполняют: [[Участник:Cookie|Шатков С.А.]], [[Антохина Ю.А.]]

Статья: [[Быстрое_преобразование_Фурье_(FFT)|Быстрое преобразование Фурье (FFT)]];
Выполняют: [[Участник:Victoria_Stepanischeva|Степанищева Виктория]] и [[Участник:Igor_Munkin|Мунькин Игорь]]

Статья: [[Быстрое_дискретное_преобразование_Фурье|Быстрое_дискретное_преобразование_Фурье]];
Выполняют: [[Участник:ivanov.kir.m | К.М.Иванов]], [[Участник:Pumpkin | А.C.Сапин]]

Статья:[[Алгоритм_k_средних]]
Выполняют: [[Участник:Parkhomenko|Пархоменко Павел]], [[Участник:ivan.mashonskiy|Машонский Иван]]

Участник:Parkhomenko/Алгоритм k средних

2016-10-12T08:29:48Z

Parkhomenko: /* Масштабируемость алгоритма и его реализации */

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

Основные авторы описания: [[Участник:Parkhomenko|П.А.Пархоменко]], [[Участник:Ivan.mashonskiy|И.Д.Машонский]]
== Свойства и структура алгоритмов ==

=== Общее описание алгоритма ===
Алгоритм k средних (англ. k-means) - один из алгоритмов машинного обучения, решающий задачу кластеризации. Он был изобретен в середине 1950-х математиком Гуго Штейнгаузом<ref>Steinhaus H. (1956). Sur la division des corps materiels en parties. Bull. Acad. Polon. Sci., C1. III vol IV: 801—804.</ref> и Стюартом Ллойдом<ref>Lloyd S. (1957). Least square quantization in PCM’s. Bell Telephone Laboratories Paper.</ref>. Алгоритм стал особо популярным после публикации Маккуина<ref>MacQueen J. (1967). Some methods for classification and analysis of multivariate observations. In Proc. 5th Berkeley Symp. on Math. Statistics and Probability, pages 281—297.</ref>, в которой впервые был использован термин “k-means”.

Задача алгоритма кластеризации заключается в разбиении N объектов (d-мерных векторов) на K групп (кластеров). Каждый вектор может принадлежать только одному кластеру. Количество кластеров K фиксировано, оно задается в качестве параметра.

K-means является итерационным алгоритмом, разновидностью EM-алгоритма. Основная идея работы алгоритма заключается в проведении некоторого количества итераций, на каждой из которых происходит пересчет центра масс для каждого кластера, полученного на предыдущей итерации. После этого векторы перераспределяются по кластерам: вектор относится к тому кластеру, расстояние до центра масс которого минимально. Алгоритм завершает работу в том случае, если на очередной итерации центры масс кластеров не изменились.

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

Исходные данные: множество d-мерных векторов (наблюдений) <math>X</math> = <math>\{x_1, x_2, ..., x_n\}</math>, число кластеров <math>k \in \mathbb{N}</math>

В результате работы алгоритма исходное множество векторов <math>X</math> разбивается на <math>k</math> непересекающихся множеств (кластеров) <math>S_1, S_2, ..., S_k</math>, таких что <math>X = {\bigcup \limits _{i = 1}^k S_i} </math> и значение <math>\sum_{i=1}^{k} \sum_{\mathbf x \in S_i} \left\| \mathbf x - \mu_i \right\|^2 </math> — минимально для всех возможных наборов <math>S_1, S_2, ..., S_k</math>.
Под <math>\mu_i</math> здесь подразумевается центр масс векторов из множества <math>S_i</math>.

Первоначальные значения центров масс <math>\mu_1^{(1)}, ..., \mu_k^{(1)}</math> определяются в начале работы алгоритма случайным образом среди векторов множества <math>X</math>.

Алгоритм заключается в попеременном применении двух шагов: '''распределения''' векторов по кластерам и '''обновления''' центров масс каждого кластера

'''Распределение векторов по кластерам''': на данном шаге каждый вектор распределяется в один из кластеров <math>S_i^{(t)}</math>:
::<math>S_i^{(t)} = \big \{ x_p : \big \| x_p - \mu^{(t)}_i \big \|^2 \le \big \| x_p - \mu^{(t)}_j \big \|^2 \ \forall j, 1 \le j \le k \big\},</math>
'''Обновление центров масс''': на данном шаге вычисляются новые центры масс для кластеров, полученных на предыдущем шаге.
::<math>\mu^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math>

Алгоритм завершается, когда на очередном шаге не происходит изменения центров масс кластеров.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро последовательного алгоритма k-means состоит из двух операций, повторяющихся на каждой итерации алгоритма:
* пересчета центров масс кластеров;
* соотнесения каждого вектора к одному из кластеров.

Пересчет центра масс кластера заключается в нахождении d-мерного вектора, являющегося средним арифметическим d-мерных векторов, принадлежащих кластеру. Эту операцию необходимо выполнять для каждого из K кластеров.

Для соотнесения вектора к одному из кластеров, необходимо для каждого из N вектора посчитать расстояние до центров масс всех K кластеров. Для нахождения расстояния между двумя d-мерными векторами p и q используется Евклидова метрика: <math>\sqrt{\sum_{k=1}^d (p_k-q_k)^2}</math>

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

В начале алгоритма осуществляется инициализация центров масс <math>\mu_1^{(1)}, ..., \mu_k^{(1)}</math>, которая может быть реализована двумя возможными способами:
* случайный выбор центров масс среди исходных наблюдений <math>x_1, x_2, ..., x_n</math>;
* все наблюдения случайным образом распределяются по кластерам <math>S_1, S_2, ..., S_k</math>, а затем для каждого кластера выполняется операция обновления центра масс.

На шаге распределения векторов по кластерам производится операция нахождения квадратов расстояний между векторами кластера и центром масс кластера:
::<math>\rho = \big \| x_p - \mu^{(t)}_i \big \|^2</math>

На шаге обновления центров масс производится операция суммирования векторов кластера:
::<math>\mu^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math>

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

Последовательность исполнения метода следующая:
# Инициализируются центры масс <math>\mu_1^{(1)}, ..., \mu_k^{(1)}</math>
# <math>t := 1</math>
# Для каждого вектора <math>x_i, i = 1, 2, ..., n</math> вычисляется <math>m = \underset{j \in \{1, 2, ..., k\}} {\operatorname{arg\,min}} \big \| x_i - \mu^{(t)}_j \big \|^2</math>, вектор <math>x_i</math> распределяется в кластер <math>S^{(t)}_m</math>
# Для каждого <math>j = 1, 2, ..., k</math> вычисляется <math>\mu^{(t+1)}_j = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math>
# Если <math>\mu^{(t)}_j = \mu^{(t+1)}_j, j = 1, 2, ..., k</math>, завершить выполнение алгоритма, иначе <math>t := t + 1</math>, переход на шаг 3.

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

Для вычисления центра массы кластера, содержащего <math>n_i</math> d-мерных векторов, необходимо:
* <math>n_i * (d - 1)</math> операций сложения
* <math>d</math> операций деления

Для определения центров масс всех k кластеров требуется:
* <math>n * (d - 1)</math> операций сложения
* <math>k * d</math> операций деления

Для определения расстояния между двумя d-мерными векторами, требуется:
* <math>d</math> операций вычитания
* <math>d</math> операций умножения
* <math>d - 1</math> операций сложения

Для определения кластера для n d-мерного векторов, необходимо:
* <math>n * k * d</math> операций вычитания
* <math>n * k * d</math> операций умножения
* <math>n * k * (d - 1)</math> операций сложения

Таким образом, общая сложность одной итерации:
* <math>O(n * k * d)</math> операций сложения/вычитания
* <math>O(n * k * d)</math> операций умножения/деления

Сложность всего алгоритма, состоящего из m итераций: <math>O(m * n * k * d)</math>

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

В данном разделе описывается информационный граф алгоритма k-средних при <math>n = 3, k = 2</math>

На рисунке 1 показана общая структура алгоритма: в качестве входных данных выступает матрица, строками которой являются входные векторы <math>x_1, x_2, x_3</math>, на выходе получается массив из <math>n</math> чисел, где элемент с номером <math>i</math> обозначает номер кластера, которому принадлежит вектор <math>x_i</math>. На шаге init происходит инициализация значений центров масс кластеров, после этого осуществляется итеративное повторение этапов распределения векторов по кластерам (as) и обновления значений центров масс кластеров (up).

[[file:k_means_info_graph_as.svg|thumb|center||Рисунок 2. Граф алгоритма для этапа распределения векторов по кластерам]]
[[file:k_means_info_graph_up.svg|thumb|center||Рисунок 3. Граф алгоритма для этапа обновления центров масс кластеров]]

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

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

'''Входные данные''':
* целое неотрицательное число <math>k</math> - количество кластеров;
* матрица координат векторов <math>A</math> размерностью <math>n * d</math>.

'''Объем входных данных''':
* <math>n * d</math> вещественных чисел (если координаты вещественные числа), <math>1</math> целое неотрицательное число.

'''Выходные данные''':
* вектор длины <math>n</math> - для каждого вектора указан номер кластера.

'''Объем выходных данных''':
* <math>n</math> целых неотрицательных чисел.

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

Стоит отметить следующие ключевые особенности алгоритма k средних:
* Алгоритм прост в реализации и имеет высокую скорость работы по сравнению с другими алгоритмами кластеризации (при удачном выборе начальных значений центров масс кластеров)
* В качестве метрики используется евклидово расстояние, а в качестве меры разброса кластера используется дисперсия
* Количество кластеров k является входным параметром алгоритма, поэтому неправильный выбор этого параметра может негативно повлиять на качество кластеризации
* Сходимость алгоритма к локальному минимуму может породить некорректный конечный результат работы
* Алгоритм очень чувствителен к выбору начальных центров масс кластеров: классический вариант подразумевает случайный их выбор, что может являться источником погрешности. Из этого и предыдущего свойства следует то, что алгоритм не является устойчивым.

Как и любой другой алгоритм кластеризации, результат работы алгоритма k средних зависит от того, удовлетворяет ли входной набор данных предположениям, на которые опираются алгоритмы кластеризации. Таким образом, на одних наборах данных алгоритм может показывать хорошие результаты, но на других выдавать некорректные результаты.

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

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

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

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

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

=== Масштабируемость алгоритма и его реализации ===
Исследование масштабируемости алгоритма k-means в зависимости от количества используемых процессов было проведено в статье Кумара<ref>Kumar J. et al. Parallel k-means clustering for quantitative ecoregion delineation using large data sets //Procedia Computer Science. – 2011. – Т. 4. – С. 1602-1611.</ref>. Исследование происходило на суперкомпьютере Jaguar - Cray XT5<ref>https://www.top500.org/system/176029</ref>. На момент экспериментов данный суперкомпьютер имел следующую конфигурацию: 18,688 вычислительных узлов с двумя шестнадцатиядерными процессорами AMD Opteron 2435 (Istanbul) 2.6 GHz, 16 GB of DDR2-800 оперативной памяти, и SeaStar 2+ роутер. Всего он состоял из 224,256 вычислительных ядер, 300 TB памяти, и пиковой производительностью 2.3 petaflops.

Реализация алгоритма была выполнена на языке программирования C с использованием MPI.

Объем данных составлял 84 гигабайта, количество объектов (m-мерных векторов) n равнялось 1,024,767,667, размерность векторов m равнялось 22, количество кластеров k равнялось 1000.

На рисунке 4 показана зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров. Можно отметить, что время, затраченное на чтение данных и запись результатов кластеризации, практически не изменяется с увеличением количества задействованных процессоров. Время же работы самого алгоритма кластеризации уменьшается с увеличением количества процессоров.
[[Файл:k-means-proc-scalability.png|thumb|center|700px|Рисунок 4. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров.]]

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

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

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

Существуют следующие реализации алгоритма k-средних:
* [http://scikit-learn.org/ scikit-learn] библиотека машинного обучения для языка Python.
* [https://www.scipy.org/ SciPy] библиотека на языке Python, содержащая большое число реализаций различных алгоритмов, в том числе ''k''-средних.
* [http://elki.dbs.ifi.lmu.de ELKI] библиотека для анализа данных на языке программирования Java, содержит различные алгоритмы кластеризации, в том числе ''k''-средних.
* [http://mlpack.org MLPACK] библиотека машинного обучения для C++, содержит реализацию алгоритма ''k''-средних.
* [https://github.com/JuliaStats/Clustering.jl Julia k-means] реализация алгоритма ''k''-средних на языке программирования Julia.
* [http://opencv.org/ OpenCV] библиотека содержит реализацию ''k''-средних.
* [http://mahout.apache.org Apache Mahout] содержит реализацию алгоритма ''k''-средних на базе MapReduce.
* [http://www.cs.waikato.ac.nz/~ml/weka Weka] библиотека и инструмент для анализа данных на языке Java.
* [http://torch.ch/ Torch] библиотека машинного обучения на базе языка программирования Lua.
* [https://spark.apache.org/ Apache Spark MLlib] содержит распределенную реализацию алгоритма ''k''-средних.
* [http://www.accord-framework.net/ Accord.NET] содержит несколько различных реализаций ''k''-средних на языке C#.
* [https://www.r-bloggers.com/k-means-clustering-in-r/ R k-means] реализация ''k''-средних на языке R.

== Литература ==
<references \>

Участник:Parkhomenko/Алгоритм k средних

2016-09-29T14:42:09Z

Parkhomenko:

Участник:Parkhomenko/Алгоритм k средних

2016-09-29T14:41:21Z

Parkhomenko: /* Входные и выходные данные алгоритма */

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

Основные авторы описания: [[Участник:Parkhomenko|П.А.Пархоменко]], [[Участник:Ivan.mashonskiy|И.Д.Машонский]]
== ЧАСТЬ. Свойства и структура алгоритмов ==

=== Общее описание алгоритма ===
Алгоритм k средних (англ. k-means) - один из алгоритмов машинного обучения, решающий задачу кластеризации. Он был изобретен в середине 1950-х математиком Гуго Штейнгаузом<ref>Steinhaus H. (1956). Sur la division des corps materiels en parties. Bull. Acad. Polon. Sci., C1. III vol IV: 801—804.</ref> и Стюартом Ллойдом<ref>Lloyd S. (1957). Least square quantization in PCM’s. Bell Telephone Laboratories Paper.</ref>. Алгоритм стал особо популярным после публикации Маккуина<ref>MacQueen J. (1967). Some methods for classification and analysis of multivariate observations. In Proc. 5th Berkeley Symp. on Math. Statistics and Probability, pages 281—297.</ref>, в которой впервые был использован термин “k-means”.

Задача алгоритма кластеризации заключается в разбиении N объектов (d-мерных векторов) на K групп (кластеров). Каждый вектор может принадлежать только одному кластеру. Количество кластеров K фиксировано, оно задается в качестве параметра.

K-means является итерационным алгоритмом, разновидностью EM-алгоритма. Основная идея работы алгоритма заключается в проведении некоторого количества итераций, на каждой из которых происходит пересчет центра масс для каждого кластера, полученного на предыдущей итерации. После этого векторы перераспределяются по кластерам: вектор относится к тому кластеру, расстояние до центра масс которого минимально. Алгоритм завершает работу в том случае, если на очередной итерации центры масс кластеров не изменились.

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

=== Вычислительное ядро алгоритма ===
Вычислительное ядро последовательного алгоритма k-means состоит из двух операций, повторяющихся на каждой итерации алгоритма:
* пересчета центров масс кластеров;
* соотнесения каждого вектора к одному из кластеров.

Пересчет центра масс кластера заключается в нахождении d-мерного вектора, являющегося средним арифметическим d-мерных векторов, принадлежащих кластеру. Эту операцию необходимо выполнять для каждого из K кластеров.

Для соотнесения вектора к одному из кластеров, необходимо для каждого из N вектора посчитать расстояние до центров масс всех K кластеров. Для нахождения расстояния между двумя d-мерными векторами p и q используется Евклидова метрика: <math>\sqrt{\sum_{k=1}^d (p_k-q_k)^2}</math>

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

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

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

Для вычисления центра массы кластера, содержащего <math>n_i</math> d-мерных векторов, необходимо:
* <math>n_i * (d - 1)</math> операций сложения
* <math>d</math> операций деления

Для определения центров масс всех k кластеров требуется:
* <math>n * (d - 1)</math> операций сложения
* <math>k * d</math> операций деления

Для определения расстояния между двумя d-мерными векторами, требуется:
* <math>d</math> операций вычитания
* <math>d</math> операций умножения
* <math>d - 1</math> операций сложения

Для определения кластера для n d-мерного векторов, необходимо:
* <math>n * k * d</math> операций вычитания
* <math>n * k * d</math> операций умножения
* <math>n * k * (d - 1)</math> операций сложения

Таким образом, общая сложность одной итерации:
* <math>O(n * k * d)</math> операций сложения/вычитания
* <math>O(n * k * d)</math> операций умножения/деления

Сложность всего алгоритма, состоящего из m итераций: <math>O(m * n * k * d)</math>

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

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

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

'''Входные данные''':
* целое неотрицательное число <math>k</math> - количество кластеров;
* матрица координат векторов <math>A</math> размерностью <math>n * d</math>.

'''Объем входных данных''':
* <math>n * d</math> вещественных чисел (если координаты вещественные числа), <math>1</math> целое неотрицательное число.

'''Выходные данные''':
* вектор длины <math>n</math> - для каждого вектора указан номер кластера.

'''Объем выходных данных''':
* <math>n</math> целых неотрицательных чисел.

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

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

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

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

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

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

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

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

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

== Литература ==
<references \>

Участник:Parkhomenko/Алгоритм k средних

2016-09-29T14:35:59Z

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

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

Основные авторы описания: [[Участник:Parkhomenko|П.А.Пархоменко]], [[Участник:Ivan.mashonskiy|И.Д.Машонский]]
== ЧАСТЬ. Свойства и структура алгоритмов ==

=== Общее описание алгоритма ===
Алгоритм k средних (англ. k-means) - один из алгоритмов машинного обучения, решающий задачу кластеризации. Он был изобретен в середине 1950-х математиком Гуго Штейнгаузом<ref>Steinhaus H. (1956). Sur la division des corps materiels en parties. Bull. Acad. Polon. Sci., C1. III vol IV: 801—804.</ref> и Стюартом Ллойдом<ref>Lloyd S. (1957). Least square quantization in PCM’s. Bell Telephone Laboratories Paper.</ref>. Алгоритм стал особо популярным после публикации Маккуина<ref>MacQueen J. (1967). Some methods for classification and analysis of multivariate observations. In Proc. 5th Berkeley Symp. on Math. Statistics and Probability, pages 281—297.</ref>, в которой впервые был использован термин “k-means”.

Задача алгоритма кластеризации заключается в разбиении N объектов (d-мерных векторов) на K групп (кластеров). Каждый вектор может принадлежать только одному кластеру. Количество кластеров K фиксировано, оно задается в качестве параметра.

K-means является итерационным алгоритмом, разновидностью EM-алгоритма. Основная идея работы алгоритма заключается в проведении некоторого количества итераций, на каждой из которых происходит пересчет центра масс для каждого кластера, полученного на предыдущей итерации. После этого векторы перераспределяются по кластерам: вектор относится к тому кластеру, расстояние до центра масс которого минимально. Алгоритм завершает работу в том случае, если на очередной итерации центры масс кластеров не изменились.

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

=== Вычислительное ядро алгоритма ===
Вычислительное ядро последовательного алгоритма k-means состоит из двух операций, повторяющихся на каждой итерации алгоритма:
* пересчета центров масс кластеров;
* соотнесения каждого вектора к одному из кластеров.

Пересчет центра масс кластера заключается в нахождении d-мерного вектора, являющегося средним арифметическим d-мерных векторов, принадлежащих кластеру. Эту операцию необходимо выполнять для каждого из K кластеров.

Для соотнесения вектора к одному из кластеров, необходимо для каждого из N вектора посчитать расстояние до центров масс всех K кластеров. Для нахождения расстояния между двумя d-мерными векторами p и q используется Евклидова метрика: <math>\sqrt{\sum_{k=1}^d (p_k-q_k)^2}</math>

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

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

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

Для вычисления центра массы кластера, содержащего <math>n_i</math> d-мерных векторов, необходимо:
* <math>n_i * (d - 1)</math> операций сложения
* <math>d</math> операций деления

Для определения центров масс всех k кластеров требуется:
* <math>n * (d - 1)</math> операций сложения
* <math>k * d</math> операций деления

Для определения расстояния между двумя d-мерными векторами, требуется:
* <math>d</math> операций вычитания
* <math>d</math> операций умножения
* <math>d - 1</math> операций сложения

Для определения кластера для n d-мерного векторов, необходимо:
* <math>n * k * d</math> операций вычитания
* <math>n * k * d</math> операций умножения
* <math>n * k * (d - 1)</math> операций сложения

Таким образом, общая сложность одной итерации:
* <math>O(n * k * d)</math> операций сложения/вычитания
* <math>O(n * k * d)</math> операций умножения/деления

Сложность всего алгоритма, состоящего из m итераций: <math>O(m * n * k * d)</math>

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

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

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

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

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

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

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

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

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

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

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

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

== Литература ==
<references \>

Участник:Parkhomenko/Алгоритм k средних

2016-09-29T14:10:35Z

Parkhomenko: /* Вычислительное ядро алгоритма */

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

Основные авторы описания: [[Участник:Parkhomenko|П.А.Пархоменко]], [[Участник:Ivan.mashonskiy|И.Д.Машонский]]
== ЧАСТЬ. Свойства и структура алгоритмов ==

=== Общее описание алгоритма ===
Алгоритм k средних (англ. k-means) - один из алгоритмов машинного обучения, решающий задачу кластеризации. Он был изобретен в середине 1950-х математиком Гуго Штейнгаузом<ref>Steinhaus H. (1956). Sur la division des corps materiels en parties. Bull. Acad. Polon. Sci., C1. III vol IV: 801—804.</ref> и Стюартом Ллойдом<ref>Lloyd S. (1957). Least square quantization in PCM’s. Bell Telephone Laboratories Paper.</ref>. Алгоритм стал особо популярным после публикации Маккуина<ref>MacQueen J. (1967). Some methods for classification and analysis of multivariate observations. In Proc. 5th Berkeley Symp. on Math. Statistics and Probability, pages 281—297.</ref>, в которой впервые был использован термин “k-means”.

Задача алгоритма кластеризации заключается в разбиении N объектов (d-мерных векторов) на K групп (кластеров). Каждый вектор может принадлежать только одному кластеру. Количество кластеров K фиксировано, оно задается в качестве параметра.

K-means является итерационным алгоритмом, разновидностью EM-алгоритма. Основная идея работы алгоритма заключается в проведении некоторого количества итераций, на каждой из которых происходит пересчет центра масс для каждого кластера, полученного на предыдущей итерации. После этого векторы перераспределяются по кластерам: вектор относится к тому кластеру, расстояние до центра масс которого минимально. Алгоритм завершает работу в том случае, если на очередной итерации центры масс кластеров не изменились.

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

=== Вычислительное ядро алгоритма ===
Вычислительное ядро последовательного алгоритма k-means состоит из двух операций, повторяющихся на каждой итерации алгоритма:
* пересчета центров масс кластеров;
* соотнесения каждого вектора к одному из кластеров.

Пересчет центра масс кластера заключается в нахождении d-мерного вектора, являющегося средним арифметическим d-мерных векторов, принадлежащих кластеру. Эту операцию необходимо выполнять для каждого из K кластеров.

Для соотнесения вектора к одному из кластеров, необходимо для каждого из N вектора посчитать расстояние до центров масс всех K кластеров. Для нахождения расстояния между двумя d-мерными векторами p и q используется Евклидова метрика: <math>\sqrt{\sum_{k=1}^d (p_k-q_k)^2}</math>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

== Литература ==
<references \>

Участник:Parkhomenko/Алгоритм k средних

2016-09-29T13:34:20Z

Parkhomenko: /* Общее описание алгоритма */

Участник:Parkhomenko/Алгоритм k средних

2016-09-29T13:23:29Z

Parkhomenko: Новая страница: «{{algorithm | name = Алгоритм k средних | serial_complexity = <math>O(m*n*k*d)</math> | input_data = <math></math> | output_dat…»

Участник:Parkhomenko

2016-09-29T12:56:59Z

Parkhomenko: Новая страница: «Пархоменко Павел Андреевич, СП ВМК МГУ, 628 группа»

Пархоменко Павел Андреевич, СП ВМК МГУ, 628 группа