Участник:S02200423/Улучшенный алгоритм k средних
Основные авторы описания: [[Участник:S02200423|Г.Д.Кучерин]
Содержание
1 Свойства и структура алгоритмов
1.1 Свойства и структура алгоритмов
Алгоритм k средних[1] (англ. k-means) - один из алгоритмов, позволяющий выполнять кластеризацию наблюдений. В частности, его цель заключается в разделении [math]n[/math] наблюдений на [math]k[/math] кластеров. При этом каждому наблюдению присваивается кластер таким образом, чтобы каждое наблюдение принадлежало ровно одному кластеру, расположенному на наименьшем расстоянии от наблюдения. В начале работы данного алгоритма выполняется этап, называемый инициализацией кластеров - он предполагает выбор произвольного множества точек [math]\mu_i, \ i=1,...,k,[/math], которые рассматриваются как начальные центры кластеров. При этом данный алгоритм является чувствительным к начальным условиям, то есть его результат зависит от выбора начальных центров кластеров. Чтобы ликвидировать данный недостаток, был придуман улучшенный алгоритм k средних[2]. В отличие от классического аналога, улучшенный алгоритм определяет порядок нахождения начальных значений центров кластеров, таким образом, устраняя вышеуказанный недостаток. В частности, первый центр кластеров определяется случайным образом, а последующие центры выбираются так, чтобы вероятность выбора была пропорциональна квадрату расстояния до ближайшего уже выбранного центра кластера. После осуществления данной процедуры инициализации выполняется основной алгоритм k средних.
1.2 Математическое описание алгоритма
Пусть дан набор из [math]n[/math] наблюдений [math]X=\{\mathbf{x}_1, \mathbf{x}_2, ..., \mathbf{x}_n\}, \mathbf{x}_i \in \mathbb{R}^d, \ i=1,...,n[/math], и нужно разделить его на [math]k[/math] ([math]k \in \mathbb{N}, \ k \leq n[/math]) кластеров. Для выполнения улучшенного алгоритма k средних выполняются следующие шаги:
1. Выбирается случайное число [math]r[/math], [math]r \in \mathbb{N}, \ r \leq n[/math]. Наблюдение [math]x_{r}[/math] выбирается в качестве первого по счету центра кластеров и обозначается [math]c_0[/math].
2. Каждый последующий центр кластеров [math]c_i[/math], [math] 2 \leq i \leq k[/math] выбирается из множества [math]X[/math], при этом наблюдение [math]x'[/math] из данного множества может стать центром с вероятностью [math]\frac{D(x')^2}{\sum\limits_{x \in X} D(x)^2}[/math], где [math]D(x)[/math] - расстояние от наблюдения [math]x[/math]до ближайшего уже выбранного центра.
3. Выполняются последующие шаги классического алгоритма k средних: распределение векторов по кластерам, пересчет центров кластеров, проверка условия останова.
