Участник:Илья Егоров/Алгоритм 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.4 Макроструктура алгоритма

Алгоритм k-средних базируется на алгоритме вычисления расстояния между векторами, расстояние на каждом шаге высчитывается [math]k\cdot n[/math] раз.

Помимо этого, в конце каждого шага вычисляется центр масс объектов кластера, для всех объектов потребуется [math]n-1[/math] суммирование и [math]k[/math] делений.

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

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

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

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

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

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

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

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

Входные данные: Количество кластеров [math]k[/math], [math]m[/math]кластеризуемых элементов Дополнительные ограничения:

• [math]k[/math] – положительное число, т. е. [math]k \gt 0[/math].
• Для кластеризуемых элементов определена метрика (расстояние между объектами)

Объём входных данных: [math]m*n + 1[/math] (кластеризуемые объекты в виде векторов и число [math]k[/math])

Выходные данные: Массив, в который записаны принадлежности каждого элемента кластеру (допустим вывод в другой эквивалентной более удобной структуре).

Объём выходных данных: Размер массива равен [math]2*m[/math].

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

Вычислительная мощность алгоритма на каждом шаге равна [math]k\cdot n[/math] (расстояние между элементом и центроидом [math]k\cdot n[/math] раз)

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.