Участник:Бротиковская Данута/Алгоритм 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\}, S_i \cap S_j= \varnothing, i \ne j, </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\}, S_i \cap S_j= \varnothing, i \ne j, </math> таким образом, чтобы минимизировать сумму квадратов расстояний от каждой точки кластера до его центра. Другими словами: | ||
| − | <div style="text-align: center;"><math>\arg\min_{S} \sum\limits_{i=1}^k \sum\limits_{x \in S_i} \lVert \mathbf{x}- \mathbf{\mu_i} \rVert^2</math>, где <math>\mu_i</math>- центры кластеров, <math>\overline{ | + | <div style="text-align: center;"><math>\arg\min_{S} \sum\limits_{i=1}^k \sum\limits_{x \in S_i} \lVert \mathbf{x}- \mathbf{\mu_i} \rVert^2</math>, где <math>\mu_i</math>- центры кластеров, <math>i=\overline{1,k}</math> </div> |
<b><u>Шаги алгоритма: </u></b> | <b><u>Шаги алгоритма: </u></b> | ||
| − | <b>1. Начальный шаг. Инициализация кластеров: </b> Выбирается произвольное множество точек <math>\mu_i, \overline{ | + | <b>1. Начальный шаг. Инициализация кластеров: </b> Выбирается произвольное множество точек <math>\mu_i, i=\overline{1,k}</math>, рассматриваемых как начальные центры кластеров |
| − | <b> 2. Распределение векторов по кластерам: </b> <math>\forall \mathbf{x_i} \in \mathbf{X}, \overline{ | + | <b> 2. Распределение векторов по кластерам: </b> <math>\forall \mathbf{x_i} \in \mathbf{X}, i=\overline{1,N}: \mathbf{x_i} \in S_j \iff j=\arg\min_{k}|x_i-\mu_k| </math> |
<b> 3. Пересчет центров кластеров:</b> <math> \forall i=\overline{i=1,k}: \widetilde{\mu_i} = \cfrac{1}{||S_i||}\sum_{x\in S_i}x</math> | <b> 3. Пересчет центров кластеров:</b> <math> \forall i=\overline{i=1,k}: \widetilde{\mu_i} = \cfrac{1}{||S_i||}\sum_{x\in S_i}x</math> | ||
| Строка 32: | Строка 32: | ||
<b> 4. Проверка условия останова:</b> | <b> 4. Проверка условия останова:</b> | ||
<math>if \exist i\in \overline{i=1,k}: \mu_i != \widetilde{\mu_i} => goto 2; else FINISH</math> | <math>if \exist i\in \overline{i=1,k}: \mu_i != \widetilde{\mu_i} => goto 2; else FINISH</math> | ||
| + | |||
| + | |||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
| − | Вычислительным ядром алгоритма являются шаги 2 и 3 приведенного выше алгоритма: | + | Вычислительным ядром алгоритма являются шаги 2 и 3 приведенного выше алгоритма: распределение векторов по кластерам и пересчет центров кластеров. |
| + | |||
| + | Распределение векторов по кластерам предполагает вычисление расстояний между каждым вектором <math>x_i \in X, i= \overline{1,N},</math> и центрами кластера <math>\mu_j, j= \overline{1,k}</math> | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
Версия 23:12, 8 октября 2016
| Алгоритм k средних (k means) | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]O(n^3)[/math] |
| Объём входных данных | [math]\frac{n (n + 1)}{2}[/math] |
| Объём выходных данных | [math]\frac{n (n + 1)}{2}[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]O(n)[/math] |
| Ширина ярусно-параллельной формы | [math]O(n^2)[/math] |
Авторы страницы Данута Бротиковская и Денис Зобнин
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Алгоритм k средних (k means) -- наиболее популярный метод кластеризации. Был изобретен в 1950-х годах математиком Гуго Штейнгаузом и почти одновременно Стюартом Ллойдом. Особую популярность приобрел после публикации работы МакКуина в 1967. Цель алгоритма заключается в разделении N наблюдений на K кластеров таким образом, чтобы каждое наблюдение придележало ровно одному кластеру, расположенному на наименьшем расстоянии от наблюдения.
1.2 Математическое описание алгоритма
Дан набор из [math]n[/math] d-мерных векторов [math]X[/math] = [math]\{x_1, x_2, ..., x_n\}[/math]. Алгоритм k средних разбивает набор [math]X[/math] на [math]k, k\lt =n[/math] наборов [math]S=\{S_1, S_2, ..., S_k\}, S_i \cap S_j= \varnothing, i \ne j, [/math] таким образом, чтобы минимизировать сумму квадратов расстояний от каждой точки кластера до его центра. Другими словами:
Шаги алгоритма:
1. Начальный шаг. Инициализация кластеров: Выбирается произвольное множество точек [math]\mu_i, i=\overline{1,k}[/math], рассматриваемых как начальные центры кластеров
2. Распределение векторов по кластерам: [math]\forall \mathbf{x_i} \in \mathbf{X}, i=\overline{1,N}: \mathbf{x_i} \in S_j \iff j=\arg\min_{k}|x_i-\mu_k| [/math]
3. Пересчет центров кластеров: [math] \forall i=\overline{i=1,k}: \widetilde{\mu_i} = \cfrac{1}{||S_i||}\sum_{x\in S_i}x[/math]
4. Проверка условия останова: [math]if \exist i\in \overline{i=1,k}: \mu_i != \widetilde{\mu_i} =\gt goto 2; else FINISH[/math]
1.3 Вычислительное ядро алгоритма
Вычислительным ядром алгоритма являются шаги 2 и 3 приведенного выше алгоритма: распределение векторов по кластерам и пересчет центров кластеров.
Распределение векторов по кластерам предполагает вычисление расстояний между каждым вектором [math]x_i \in X, i= \overline{1,N},[/math] и центрами кластера [math]\mu_j, j= \overline{1,k}[/math]
