Участник:Бротиковская Данута/Алгоритм k-means: различия между версиями
Нет описания правки |
Нет описания правки |
||
| Строка 19: | Строка 19: | ||
Дан набор из <math>n</math> d-мерных векторов <math>X</math> = <math>\{x_1, x_2, ..., x_n\}</math>. Алгоритм k средних разбивает набор <math>X</math> на <math>k, k<=n</math> наборов <math>S=\{S_1, S_2, ..., S_k\}</math> таким образом, чтобы минимизировать сумму квадратов расстояний от каждой точки кластера до его центра. Другими словами: | Дан набор из <math>n</math> d-мерных векторов <math>X</math> = <math>\{x_1, x_2, ..., x_n\}</math>. Алгоритм k средних разбивает набор <math>X</math> на <math>k, k<=n</math> наборов <math>S=\{S_1, S_2, ..., S_k\}</math> таким образом, чтобы минимизировать сумму квадратов расстояний от каждой точки кластера до его центра. Другими словами: | ||
<math>\arg\min_{S} \sum\limits_{i=1}^k \sum\limits_{x \in S_i} \lVert x-\mu_i \rVert^2</math> | <math>\arg\min_{S} \sum\limits_{i=1}^k \sum\limits_{x \in S_i} \lVert \mathbf{x}- \mathbf{\mu_i} \rVert^2</math> | ||
Версия от 15:35, 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 кластеров таким образом, чтобы каждое наблюдение придележало ровно одному кластеру, расположенному на наименьшем расстоянии от наблюдения.
Математическое описание алгоритма
Дан набор из [math]\displaystyle{ n }[/math] d-мерных векторов [math]\displaystyle{ X }[/math] = [math]\displaystyle{ \{x_1, x_2, ..., x_n\} }[/math]. Алгоритм k средних разбивает набор [math]\displaystyle{ X }[/math] на [math]\displaystyle{ k, k\lt =n }[/math] наборов [math]\displaystyle{ S=\{S_1, S_2, ..., S_k\} }[/math] таким образом, чтобы минимизировать сумму квадратов расстояний от каждой точки кластера до его центра. Другими словами:
[math]\displaystyle{ \arg\min_{S} \sum\limits_{i=1}^k \sum\limits_{x \in S_i} \lVert \mathbf{x}- \mathbf{\mu_i} \rVert^2 }[/math]
Шаги алгоритма:
Начальный шаг: Инициализация кластеров. Выбирается произвольное множество k точек, рассматриваемых как начальные центры кластеров.