Метод K-средних (K-Means)

<h2>Идея метода</h2> <p>K-Means — это алгоритм разбиения, который заранее получает число кластеров \(K\) и описывает каждый кластер центроидом. Центроид — это не обязательно реальная точка из выборки, а среднее положение объектов внутри группы.</p> <p>Метод старается сделать кластеры компактными: каждая точка должна быть близка к центроиду своего кластера. Поэтому целевая функция записывается как сумма квадратов расстояний от точек до назначенных центроидов:</p> <p>$$Q = \sum_{i=1}^{\ell} \|x_i - \mu_{a_i}\|^2 \rightarrow \min.$$</p> <p>Здесь \(x_i\) — объект, \(a_i\) — номер его кластера, \(\mu_{a_i}\) — центроид этого кластера.</p> <h2>Два чередующихся шага</h2> <ol> <li><strong>Назначение точек.</strong> Для каждой точки выбирается ближайший центроид: $$a_i = \arg\min_k \|x_i - \mu_k\|^2.$$</li> <li><strong>Пересчет центроидов.</strong> Для каждого кластера считается среднее его точек: $$\mu_k = \frac{1}{|C_k|}\sum_{x_i \in C_k} x_i.$$</li> </ol> <p>Эти шаги повторяются, пока назначения почти не меняются или пока не достигнут лимит итераций. На каждой итерации значение \(Q\) не увеличивается, поэтому алгоритм обычно быстро стабилизируется.</p> <h2>Что важно понимать</h2> <p>K-Means не перебирает все возможные разбиения. Он улучшает текущее решение, поэтому результат зависит от начальных центроидов и может оказаться локальным оптимумом. На практике алгоритм запускают несколько раз с разными инициализациями и выбирают разбиение с меньшей суммой квадратов.</p>