Участник:Илья Егоров/Алгоритм k-средних: различия между версиями
| Строка 11: | Строка 11: | ||
Исходные данные: <math>\{a_i\}, i = 1 \dots n</math>--множество объектов, подлежащих кластеризации, k -- предполагаемое количество кластеров | Исходные данные: <math>\{a_i\}, i = 1 \dots n</math> -- множество объектов, подлежащих кластеризации, <math>k</math> -- предполагаемое количество кластеров | ||
Вычисляемые данные: центр предполагаемого кластера -- центр масс элементов кластера. | Вычисляемые данные: центр предполагаемого кластера -- центр масс элементов кластера. | ||
Версия от 14:34, 2 октября 2016
Здесь будет описание алгоритма k-средних
Страница создана группой "Илья Егоров -- Евгений Богомазов"
ЧАСТЬ. Свойства и структура алгоритмов
Общее описание алгоритма
Алгоритм кластеризации k-средних был предложен в 1950-х годах математиками Гуго Штейнгаузом и Стюартом Ллойдом независимо друг от друга, а наибольшую популярность получил после работы Маккуина. Алгоритм позволяет при заданном числе k построить k кластеров, расположенных на максимальном расстоянии друг от друга. Таким образом, наибольшей точности алгоритм достигает при полной осведомленности о характере кластеризуемых объектов и, как следствие, при обладании максимально корректной информации о числе кластеров. В общем случае выбор числа k может базироваться на любых значимых факторах, в том числе на результатах предшествующих исследований, теоретических соображениях или интуиции.
Математическое описание алгоритма
Исходные данные: [math]\displaystyle{ \{a_i\}, i = 1 \dots n }[/math] -- множество объектов, подлежащих кластеризации, [math]\displaystyle{ k }[/math] -- предполагаемое количество кластеров
Вычисляемые данные: центр предполагаемого кластера -- центр масс элементов кластера.
[math]\displaystyle{ \sum^n_{i=1} }[/math]
Вычислительное ядро алгоритма
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Информационный граф
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Свойства алгоритма
ЧАСТЬ. Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
Литература
[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.