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

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

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

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|a_i - s_P\right| \rightarrow \min_P[/math]

1.3 Вычислительное ядро алгоритма

Основное время работы алгоритма приходится на вычисление расстояний от каждого объекта до каждого из центроидов. Эту операцию придется повторять до тех пор, пока центроиды смещаются.

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

Последовательность шагов алгоритма следующая:

1. Выбираем [math]k[/math] объектов для кластеризации, объявляем их центроидами

2. Классифицируем каждый объект на предмет принадлежности к кластеру согласно формуле в разделе "Математическое описание алгоритма".

3. Вычисляем центр масс каждого из кластеров.

3.а Если для какого-либо кластера его центр масс отличается от центроида, то переносим центроид этого кластера во вновь образованный центр масс, проделываем эту операцию для всех других кластеров и переходим к п.2

3.б Если для каждого кластера его центр масс совпадает с центроидом -- Выход из алгоритма, объекты классифицированы.

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.