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

Версия 17:35, 29 сентября 2016

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

Основные авторы описания: П.А.Пархоменко, И.Д.Машонский

Содержание

1 ЧАСТЬ. Свойства и структура алгоритмов
2 ЧАСТЬ. Программная реализация алгоритма
3 Литература

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

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

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

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

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

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

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

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

пересчета центров масс кластеров;
соотнесения каждого вектора к одному из кластеров.

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

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

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

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

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

Для вычисления центра массы кластера, содержащего [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]

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

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

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

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

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

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

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

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

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

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

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

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

3 Литература

↑ Steinhaus H. (1956). Sur la division des corps materiels en parties. Bull. Acad. Polon. Sci., C1. III vol IV: 801—804.
↑ Lloyd S. (1957). Least square quantization in PCM’s. Bell Telephone Laboratories Paper.
↑ 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.

[1] Steinhaus H. (1956). Sur la division des corps materiels en parties. Bull. Acad. Polon. Sci., C1. III vol IV: 801—804.

[2] Lloyd S. (1957). Least square quantization in PCM’s. Bell Telephone Laboratories Paper.

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

[1]

[2]

[3]

@@ Строка 32: / Строка 32: @@
 === Последовательная сложность алгоритма ===
+Для вычисления центра массы кластера, содержащего <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>
 === Информационный граф ===