Участник:S02200423

2023-10-30T17:30:31Z

S02200423: Создана пустая страница

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

2023-10-30T17:25:22Z

S02200423: Новая страница: «Основные авторы описания: [[Участник:S02200423|Г.Д.Кучерин] == Свойства и структура алгоритмо...»

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

== Свойства и структура алгоритмов ==
=== Свойства и структура алгоритмов ===
Алгоритм k средних<ref>"https://algowiki-project.org/ru/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_k_%D1%81%D1%80%D0%B5%D0%B4%D0%BD%D0%B8%D1%85_(k-means)"</ref> (англ. k-means) - один из алгоритмов, позволяющий выполнять кластеризацию наблюдений. В частности, его цель заключается в разделении <math>n</math> наблюдений на <math>k</math> кластеров. При этом каждому наблюдению присваивается кластер таким образом, чтобы каждое наблюдение принадлежало ровно одному кластеру, расположенному на наименьшем расстоянии от наблюдения. В начале работы данного алгоритма выполняется этап, называемый инициализацией кластеров - он предполагает выбор произвольного множества точек <math>\mu_i, \ i=1,...,k,</math>, которые рассматриваются как начальные центры кластеров. При этом данный алгоритм является чувствительным к начальным условиям, то есть его результат зависит от выбора начальных центров кластеров. Чтобы ликвидировать данный недостаток, был придуман улучшенный алгоритм k средних<ref>"https://ru.wikipedia.org/wiki/K-means%2B%2B"</ref>. В отличие от классического аналога, улучшенный алгоритм определяет порядок нахождения начальных значений центров кластеров, таким образом, устраняя вышеуказанный недостаток. В частности, первый центр кластеров определяется случайным образом, а последующие центры выбираются так, чтобы вероятность выбора была пропорциональна квадрату расстояния до ближайшего уже выбранного центра кластера. После осуществления данной процедуры инициализации выполняется основной алгоритм k средних.
=== Математическое описание алгоритма ===
Пусть дан набор из <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 средних: распределение векторов по кластерам, пересчет центров кластеров, проверка условия останова.
== Программная реализация алгоритма ==
== Литература ==
<references />

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

Участник:S02200423

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