Участник:Бротиковская Данута/Алгоритм k-means: различия между версиями
Перейти к навигации
Перейти к поиску
Нет описания правки |
Нет описания правки |
||
| Строка 13: | Строка 13: | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
Алгоритм <b>k средних</b> (<b>k means</b>) -- наиболее популярный метод кластеризации. Был изобретен в 1950-х годах математиком <i>Гуго Штейнгаузом</i> и почти одновременно Стюартом Ллойдом. Особую популярность приобрел после публикации работы МакКуина в 1967. Цель алгоритма заключается в разделении N наблюдений на K кластеров таким образом, | Алгоритм <b>k средних</b> (<b>k means</b>) -- наиболее популярный метод кластеризации. Был изобретен в 1950-х годах математиком <i>Гуго Штейнгаузом</i> и почти одновременно Стюартом Ллойдом. Особую популярность приобрел после публикации работы МакКуина в 1967. | ||
Цель алгоритма заключается в разделении N наблюдений на K кластеров таким образом, чтобы каждое наблюдение придележало ровно одному кластеру, расположенному на наименьшем расстоянии от наблюдения. | |||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
Версия от 14:59, 8 октября 2016
| Алгоритм k средних (k means) | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ O(n^3) }[/math] |
| Объём входных данных | [math]\displaystyle{ \frac{n (n + 1)}{2} }[/math] |
| Объём выходных данных | [math]\displaystyle{ \frac{n (n + 1)}{2} }[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]\displaystyle{ O(n) }[/math] |
| Ширина ярусно-параллельной формы | [math]\displaystyle{ O(n^2) }[/math] |
Авторы страницы Данута Бротиковская и Денис Зобнин
Свойства и структура алгоритма
Общее описание алгоритма
Алгоритм k средних (k means) -- наиболее популярный метод кластеризации. Был изобретен в 1950-х годах математиком Гуго Штейнгаузом и почти одновременно Стюартом Ллойдом. Особую популярность приобрел после публикации работы МакКуина в 1967. Цель алгоритма заключается в разделении N наблюдений на K кластеров таким образом, чтобы каждое наблюдение придележало ровно одному кластеру, расположенному на наименьшем расстоянии от наблюдения.