Участник:S02200423/Улучшенный алгоритм k средних

Основные авторы описания: [[Участник:S02200423|Г.Д.Кучерин]

1 Свойства и структура алгоритмов

1.1 Свойства и структура алгоритмов

Алгоритм k средних (англ. k-means) - один из алгоритмов, позволяющий выполнять кластеризацию наблюдений. В частности, его цель заключается в разделении $n$ наблюдений на $k$ кластеров. При этом каждому наблюдению присваивается кластер таким образом, чтобы каждое наблюдение принадлежало ровно одному кластеру, расположенному на наименьшем расстоянии от наблюдения. В начале работы данного алгоритма выполняется этап, называемый инициализацией кластеров - он предполагает выбор произвольного множества точек $\mu_i, \ i=1,...,k,$, которые рассматриваются как начальные центры кластеров. При этом данный алгоритм является чувствительным к начальным условиям, то есть его результат зависит от выбора начальных центров кластеров. Чтобы ликвидировать данный недостаток, был придуман улучшенный алгоритм k средних. В отличие от классического аналога, улучшенный алгоритм определяет порядок нахождения начальных значений центров кластеров, таким образом, устраняя вышеуказанный недостаток. В частности, первый центр кластеров определяется случайным образом, а последующие центры выбираются так, чтобы вероятность выбора была пропорциональна квадрату расстояния до ближайшего уже выбранного центра кластера. После осуществления данной процедуры инициализации выполняется основной алгоритм k средних.

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

Пусть дан набор из $n$ наблюдений $X=\{\mathbf{x}_1, \mathbf{x}_2, ..., \mathbf{x}_n\}, \mathbf{x}_i \in \mathbb{R}^d, \ i=1,...,n$, и нужно разделить его на $k$ ($k \in \mathbb{N}, \ k \leq n$) кластеров. Для выполнения улучшенного алгоритма k средних выполняются следующие шаги:

1. Выбирается случайное число $r$, $r \in \mathbb{N}, \ r \leq n$. Наблюдение $x_{r}$ выбирается в качестве первого по счету центра кластеров и обозначается $c_0$.

2. Каждый последующий центр кластеров $c_i$, $2 \leq i \leq k$ выбирается из множества $X$, при этом наблюдение $x'$ из данного множества может стать центром с вероятностью $\frac{D(x')^2}{\sum\limits_{x \in X} D(x)^2}$, где $D(x)$ - расстояние от наблюдения $x$до ближайшего уже выбранного центра.

3. Выполняются последующие шаги классического алгоритма k средних: распределение векторов по кластерам, пересчет центров кластеров, проверка условия останова.