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

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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 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>
  
 
=== Информационный граф ===
 
=== Информационный граф ===

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


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


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

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 Литература

<references \>

  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.