Участник:Parkhomenko/Алгоритм k средних: различия между версиями
| Строка 19: | Строка 19: | ||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
Вычислительное ядро последовательного алгоритма k-means состоит из двух операций, повторяющихся на каждой итерации алгоритма: | |||
* пересчета центров масс кластеров; | |||
* соотнесения каждого вектора к одному из кластеров. | |||
Пересчет центра масс кластера заключается в нахождении d-мерного вектора, являющегося средним арифметическим d-мерных векторов, принадлежащих кластеру. Эту операцию необходимо выполнять для каждого из K кластеров. | |||
Для соотнесения вектора к одному из кластеров, необходимо для каждого из N вектора посчитать расстояние до центров масс всех K кластеров. Для нахождения расстояния между двумя d-мерными векторами p и q используется Евклидова метрика: <math>\sqrt{\sum_{k=1}^d (p_k-q_k)^2}</math> | |||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
Версия от 14:10, 29 сентября 2016
| Алгоритм k средних | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ O(m*n*k*d) }[/math] |
| Объём входных данных | [math]\displaystyle{ }[/math] |
| Объём выходных данных | [math]\displaystyle{ }[/math] |
Основные авторы описания: П.А.Пархоменко, И.Д.Машонский
ЧАСТЬ. Свойства и структура алгоритмов
Общее описание алгоритма
Алгоритм k средних (англ. k-means) - один из алгоритмов машинного обучения, решающий задачу кластеризации. Он был изобретен в середине 1950-х математиком Гуго Штейнгаузом[1] и Стюартом Ллойдом[2]. Алгоритм стал особо популярным после публикации Маккуина[3], в которой впервые был использован термин “k-means”.
Задача алгоритма кластеризации заключается в разбиении N объектов (d-мерных векторов) на K групп (кластеров). Каждый вектор может принадлежать только одному кластеру. Количество кластеров K фиксировано, оно задается в качестве параметра.
K-means является итерационным алгоритмом, разновидностью EM-алгоритма. Основная идея работы алгоритма заключается в проведении некоторого количества итераций, на каждой из которых происходит пересчет центра масс для каждого кластера, полученного на предыдущей итерации. После этого векторы перераспределяются по кластерам: вектор относится к тому кластеру, расстояние до центра масс которого минимально. Алгоритм завершает работу в том случае, если на очередной итерации центры масс кластеров не изменились.
Математическое описание алгоритма
Вычислительное ядро алгоритма
Вычислительное ядро последовательного алгоритма k-means состоит из двух операций, повторяющихся на каждой итерации алгоритма:
- пересчета центров масс кластеров;
- соотнесения каждого вектора к одному из кластеров.
Пересчет центра масс кластера заключается в нахождении d-мерного вектора, являющегося средним арифметическим d-мерных векторов, принадлежащих кластеру. Эту операцию необходимо выполнять для каждого из K кластеров.
Для соотнесения вектора к одному из кластеров, необходимо для каждого из N вектора посчитать расстояние до центров масс всех K кластеров. Для нахождения расстояния между двумя d-мерными векторами p и q используется Евклидова метрика: [math]\displaystyle{ \sqrt{\sum_{k=1}^d (p_k-q_k)^2} }[/math]
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Информационный граф
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Свойства алгоритма
ЧАСТЬ. Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
Литература
<references \>
- ↑ 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.