Участник:Error2407

2016-10-12T10:40:28Z

Error2407: Новая страница: «Богомазов Евгений, 619»

Богомазов Евгений, 619

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

2016-10-12T10:38:35Z

Error2407: /* ЧАСТЬ. Свойства и структура алгоритмов */

{{algorithm
| name = Алгоритм k-средних (k-means)
| serial_complexity = <math>O()</math>
| pf_height = <math>O()</math>
| pf_width = <math>O()</math>
| input_data = <math>\frac{()}{}</math>
| output_data = <math>\frac{ ()}{}</math>
}}

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

= ЧАСТЬ. Свойства и структура алгоритмов =
== Общее описание алгоритма ==

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

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

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

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

Исходные данные: <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>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

'''Входные данные''': Количество кластеров <math>k</math>, <math>m</math>кластеризуемых элементов
Дополнительные ограничения:
* <math>k</math> — положительное число, т. е. <math>k > 0</math>.
* Для кластеризуемых элементов определена метрика (расстояние между объектами)

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

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

'''Объём выходных данных''': Размер массива равен <math>2\cdot m</math>.

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

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

= ЧАСТЬ. Программная реализация алгоритма =

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

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

= Литература =
[1] Нейский И.М. Классификация и сравнение методов кластеризации http://it-claim.ru/Persons/Neyskiy/Article2_Neiskiy.pdf

[2] https://ru.wikipedia.org/wiki/K-means

[[en:Description of algorithm properties and structure]]

Алговики - Вклад [ru]

Участник:Error2407

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