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