Версия 19:19, 6 октября 2016

Здесь будет описание алгоритма k-средних

Страница создана группой "Илья Егоров -- Евгений Богомазов"

Содержание

1 ЧАСТЬ. Свойства и структура алгоритмов
2 ЧАСТЬ. Программная реализация алгоритма
3 Литература

1 ЧАСТЬ. Свойства и структура алгоритмов

1.1 Общее описание алгоритма

Алгоритм кластеризации k-средних впервые был предложен в 1950-х годах математиками Гуго Штейнгаузом и Стюартом Ллойдом независимо друг от друга. Наибольшую популярность он получил после работы Маккуина.

Алгоритм позволяет при заданном числе [math]k[/math] построить [math]k[/math] кластеров, расположенных на максимальном расстоянии друг от друга. Таким образом, наибольшей точности результат выполнения алгоритма достигает при полной осведомленности Пользователя о характере кластеризуемых объектов и, как следствие, при обладании максимально корректной информацией о числе кластеров.

В общем случае выбор числа [math]k[/math] может базироваться на любых значимых факторах, в том числе на результатах предшествующих исследований, теоретических соображениях или интуиции.

1.2 Математическое описание алгоритма

Исходные данные: [math]\{a_i\}, i = 1 \dots m[/math] -- множество из [math]m[/math]объектов, подлежащих кластеризации и определяющихся вектором длины [math]n[/math], [math]k[/math] -- предполагаемое количество кластеров.

Вычисляемые данные: центр предполагаемого кластера (центроид) -- на первом шаге объявляется равным случайному объекту, затем сдвигается в центр масс элементов кластера.

Если [math]\{s_1 \dots s_k\}[/math] -- центроиды, где [math]1 \dots k [/math] -- номера кластеров, то объект [math]a[/math] относится к кластеру [math]P[/math], если суммарное квадратичное отклонение точек кластеров от центров этих кластеров минимально:

[math]a_i \in P \Leftrightarrow \left(\vec{a_i} - \vec{s_P}\right)^2 \rightarrow \min[/math]

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] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

[2] Воеводин В.В., Воеводин Вад.В. Спасительная локальность суперкомпьютеров //Открытые системы. - 2013. - № 9. - С. 12-15.

[3] Воеводин Вад.В., Швец П. Метод покрытий для оценки локальности использования данных в программах // Вестник УГАТУ. — 2014. — Т. 18, № 1(62). — С. 224–229.

[4] Антонов А.С., Теплов А.М. О практической сложности понятия масштабируемости параллельных программ// Высокопроизводительные параллельные вычисления на кластерных системах (HPC 2014): Материалы XIV Международной конференции -Пермь: Издательство ПНИПУ, 2014. С. 20-27.

[5] Никитенко Д.А. Комплексный анализ производительности суперкомпьютерных систем, основанный на данных системного мониторинга // Вычислительные методы и программирование. 2014. 15. 85–97.

@@ Строка 19: / Строка 19: @@
 Вычисляемые данные: центр предполагаемого кластера (центроид) -- на первом шаге объявляется равным случайному объекту, затем сдвигается в центр масс элементов кластера.
-Если <math>\{s_1 \dots s_k\}</math> -- центроиды, где <math>1 \dots k </math> -- номера кластеров, то объект <math>a</math> относится к кластеру <math>p</math>, если суммарное квадратичное отклонение точек кластеров от центров этих кластеров минимально:
+Если <math>\{s_1 \dots s_k\}</math> -- центроиды, где <math>1 \dots k </math> -- номера кластеров, то объект <math>a</math> относится к кластеру <math>P</math>, если суммарное квадратичное отклонение точек кластеров от центров этих кластеров минимально:
-<math>\left(\vec{a_i} - \vec{s_p}\right)^2 \Rightarrow \min</math>
+<math>a_i \in P \Leftrightarrow \left(\vec{a_i} - \vec{s_P}\right)^2 \rightarrow \min</math>
 == Вычислительное ядро алгоритма ==

Участник:Илья Егоров/Алгоритм k-средних: различия между версиями