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

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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 37: Строка 37:
 
Вычислительным ядром алгоритма являются шаги 2 и 3 приведенного выше алгоритма: <b><i>распределение векторов по кластерам</i></b> и <b><i>пересчет центров кластеров</i></b>.  
 
Вычислительным ядром алгоритма являются шаги 2 и 3 приведенного выше алгоритма: <b><i>распределение векторов по кластерам</i></b> и <b><i>пересчет центров кластеров</i></b>.  
  
<b><i>Распределение векторов</i></b> по кластерам предполагает вычисление расстояний между каждым вектором <math>x_i \in X, i= \overline{1,N},</math> и центрами кластера <math>\mu_j, j= \overline{1,k}</math>. Таким образом, данный шаг предполагает kN вычислений расстояний между d-мерными векторами.
+
<b><i>Распределение векторов</i></b> по кластерам предполагает вычисление расстояний между каждым вектором <math>x_i \in X, i= \overline{1,N},</math> и центрами кластера <math>\mu_j, j= \overline{1,k}</math>. Таким образом, данный шаг предполагает kN вычислений расстояний между d-мерными векторами. В качестве <b><i>метрики расстояния</i></b> как правило рассматривается Евклидово расстояние.
 
 
В качестве <b><i>метрики расстояния</i></b> как правило рассматривается Евклидово расстояние.
 
  
 
<b><i>Пересчет центров кластеров</i></b> предполагает k вычислений центров масс <math>\mu_i</math> множеств <math>S_i, i=\overline{1, k}</math>, представленных выражением шага 3.
 
<b><i>Пересчет центров кластеров</i></b> предполагает k вычислений центров масс <math>\mu_i</math> множеств <math>S_i, i=\overline{1, k}</math>, представленных выражением шага 3.

Версия 23:21, 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 Общее описание алгоритма

Алгоритм 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] таким образом, чтобы минимизировать сумму квадратов расстояний от каждой точки кластера до его центра. Другими словами:

[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]


Шаги алгоритма:

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{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]. Таким образом, данный шаг предполагает kN вычислений расстояний между d-мерными векторами. В качестве метрики расстояния как правило рассматривается Евклидово расстояние.

Пересчет центров кластеров предполагает k вычислений центров масс [math]\mu_i[/math] множеств [math]S_i, i=\overline{1, k}[/math], представленных выражением шага 3.

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

1.10 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.2.1 Локальность реализации алгоритма

2.2.1.1 Структура обращений в память и качественная оценка локальности
2.2.1.2 Количественная оценка локальности

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.4.1 Масштабируемость алгоритма

2.4.2 Масштабируемость реализации алгоритма

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература