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

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

Алгоритм k средних
Последовательный алгоритм
Последовательная сложность	[math]O(mnk*d)[/math]
Объём входных данных	[math]n * d[/math]
Объём выходных данных	[math]n[/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 Входные и выходные данные алгоритма

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

целое неотрицательное число [math]k[/math] - количество кластеров;
матрица координат векторов [math]A[/math] размерностью [math]n * d[/math].

Объем входных данных:

[math]n * d[/math] вещественных чисел (если координаты вещественные числа), [math]1[/math] целое неотрицательное число.

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

вектор длины [math]n[/math] - для каждого вектора указан номер кластера.

Объем выходных данных:

[math]n[/math] целых неотрицательных чисел.

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]

@@ Строка 2: / Строка 2: @@
 | name              = Алгоритм k средних
 | serial_complexity = <math>O(m*n*k*d)</math>
-| input_data        = <math></math>
+| input_data        = <math>n * d</math>
-| output_data       = <math></math>
+| output_data       = <math>n</math>
 }}