K-means

Материал из MachineLearning.

Версия от 10:39, 27 июня 2026; Eva Vallistu (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Статья написана с использованием LLM GPT-5.5 Thinking и проверена участником Eva Vallistu 27 июня 2026 (MSD) Промпт приводится полностью в Обсуждение:Алгоритм кластеризации k-means

K-means или метод k-средних — алгоритм кластеризации, разбивающий множество объектов на заранее заданное число $k$ кластеров так, чтобы объекты внутри одного кластера были близки друг к другу по выбранной метрике. Алгоритм относится к методам обучения без учителя и широко используется как базовый метод разбиения данных на группы.

В классической постановке k-means применяется к объектам, представленным векторами в евклидовом пространстве. Каждый кластер описывается своим центром — средним вектором объектов, отнесённых к этому кластеру. Алгоритм минимизирует сумму квадратов расстояний от объектов до центров соответствующих кластеров.

В отличие от DBSCAN, k-means требует заранее задать число кластеров и обычно предполагает, что кластеры имеют компактную, близкую к сферической форму. В отличие от иерархической кластеризации, алгоритм не строит дерево вложенных разбиений, а сразу ищет одно разбиение на $k$ групп.

Основные понятия и определения

Пусть задано множество объектов

$X={x_1,\ldots,x_n},\quad x_i\in\mathbb{R}^d.$

Требуется разбить $X$ на $k$ непересекающихся кластеров

$S_1,\ldots,S_k,$

таких что

$S_i\cap S_j=\varnothing,\quad i\neq j,$

$\bigcup_{j=1}^{k}S_j=X.$

Каждому кластеру $S_j$ соответствует центр

$\mu_j\in\mathbb{R}^d.$

В стандартном варианте k-means центр кластера определяется как среднее арифметическое объектов, входящих в этот кластер:

$\mu_j=\frac{1}{|S_j|}\sum_{x_i\in S_j}x_i.$

Целевая функция k-means имеет вид

$J(S_1,\ldots,S_k,\mu_1,\ldots,\mu_k)=\sum_{j=1}^{k}\sum_{x_i\in S_j}|x_i-\mu_j|^2.$

Задача k-means состоит в нахождении такого разбиения и таких центров, при которых значение $J$ минимально:

$\min_{S_1,\ldots,S_k}\sum_{j=1}^{k}\sum_{x_i\in S_j}|x_i-\mu_j|^2.$

Здесь $|\cdot|$ обычно обозначает евклидову норму. Поэтому классический k-means естественно связан именно с евклидовым расстоянием и суммой квадратов отклонений.

Для каждого объекта можно также ввести метку кластера

$c_i\in{1,\ldots,k},$

где $c_i=j$ означает, что объект $x_i$ отнесён к кластеру $j$ . Тогда целевая функция может быть записана как

$J(c,\mu)=\sum_{i=1}^{n}|x_i-\mu_{c_i}|^2.$

Алгоритм

Наиболее распространённая реализация k-means основана на алгоритме Ллойда. Алгоритм чередует два шага:

назначение объектов ближайшим центрам;
пересчёт центров как средних значений объектов внутри кластеров.

Пусть на некоторой итерации заданы центры $\mu_1,\ldots,\mu_k$ . Тогда каждый объект относится к ближайшему центру:

$c_i=\arg\min_{1\leq j\leq k}|x_i-\mu_j|^2.$

После этого центры пересчитываются по текущим кластерам:

$\mu_j=\frac{1}{|{i:c_i=j}|}\sum_{i:c_i=j}x_i.$

Если некоторый кластер оказался пустым, то его центр обычно переинициализируют, например случайным объектом выборки или объектом с наибольшей ошибкой относительно текущего ближайшего центра.

Типичная схема алгоритма:

задаётся число кластеров $k$ ;
выбираются начальные центры $\mu_1,\ldots,\mu_k$ ;
каждый объект относится к ближайшему центру;
центры пересчитываются как средние объектов внутри кластеров;
шаги назначения и пересчёта повторяются до стабилизации меток, центров или значения целевой функции.

В псевдокоде алгоритм можно записать следующим образом:

$\operatorname{KMeans}(X,k)$

выбрать начальные центры $\mu_1,\ldots,\mu_k$ ;
пока критерий остановки не выполнен:
- для каждого объекта найти ближайший центр:
  - $c_i\leftarrow \arg\min_j|x_i-\mu_j|^2$ ;
- для каждого кластера пересчитать центр:
  - $\mu_j\leftarrow \frac{1}{|{i:c_i=j}|}\sum_{i:c_i=j}x_i$ ;
вернуть метки $c_1,\ldots,c_n$ и центры $\mu_1,\ldots,\mu_k$ .

Каждая итерация алгоритма не увеличивает значение целевой функции. На шаге назначения при фиксированных центрах каждый объект выбирает лучший для себя кластер. На шаге пересчёта при фиксированном разбиении среднее арифметическое минимизирует сумму квадратов расстояний внутри кластера. Поэтому значение $J$ монотонно невозрастает.

Так как число возможных разбиений конечной выборки на $k$ кластеров конечно, алгоритм за конечное число шагов приходит к стационарному разбиению. Однако полученный результат не обязан быть глобальным минимумом целевой функции: k-means обычно сходится к локальному минимуму, зависящему от начальной инициализации.

Инициализация центров

Качество результата k-means существенно зависит от выбора начальных центров.

Простейший способ инициализации состоит в случайном выборе $k$ объектов из выборки. Такой подход прост, но может приводить к неустойчивым результатам: разные запуски алгоритма могут давать разные разбиения.

Более устойчивым вариантом является k-means++. Идея метода состоит в том, чтобы выбирать начальные центры не слишком близко друг к другу. Первый центр выбирается случайно. Каждый следующий центр выбирается с вероятностью, пропорциональной квадрату расстояния от объекта до ближайшего уже выбранного центра:

$P(x_i)=\frac{D(x_i)^2}{\sum_{\ell=1}^{n}D(x_\ell)^2},$

где $D(x_i)$ — расстояние от $x_i$ до ближайшего из уже выбранных центров.

Такая инициализация часто улучшает качество кластеризации и уменьшает разброс результатов между разными запусками. На практике k-means обычно запускают несколько раз с разными начальными центрами, после чего выбирают решение с минимальным значением целевой функции.

Выбор числа кластеров

В отличие от плотностных алгоритмов, k-means требует заранее задать число кластеров $k$ . Выбор этого параметра является отдельной задачей и обычно зависит от предметной области.

Один из распространённых эвристических способов — метод локтя. Для разных значений $k$ вычисляют значение внутрикластерной суммы квадратов:

$W_k=\sum_{j=1}^{k}\sum_{x_i\in S_j}|x_i-\mu_j|^2.$

При увеличении $k$ величина $W_k$ не возрастает, поскольку большее число кластеров позволяет точнее описывать данные. Значение $k$ выбирают в области, где дальнейшее увеличение числа кластеров даёт лишь небольшое уменьшение $W_k$ . Такая область визуально соответствует «локтю» на графике зависимости $W_k$ от $k$ .

Другой распространённый подход — использование коэффициента силуэта. Для объекта $x_i$ пусть $a_i$ — среднее расстояние до объектов своего кластера, а $b_i$ — минимальное среднее расстояние до объектов другого кластера. Тогда силуэт объекта определяется как

$s_i=\frac{b_i-a_i}{\max(a_i,b_i)}.$

Значения $s_i$ лежат в диапазоне от $-1$ до $1$ . Чем ближе средний силуэт к $1$ , тем лучше объекты отделены от соседних кластеров. Однако этот критерий также является эвристическим и может быть неустойчивым для данных сложной формы или высокой размерности.

Перед применением k-means признаки обычно нормируют, поскольку алгоритм чувствителен к масштабу координат. Для вещественных признаков часто используется стандартизация:

$x'*{ij}=\frac{x*{ij}-\mu_j}{\sigma_j},$

где $\mu_j$ и $\sigma_j$ — среднее и стандартное отклонение $j$ -го признака.

Если признаки имеют разные единицы измерения и не нормированы, координаты с большим масштабом могут непропорционально сильно влиять на расстояния и, следовательно, на результат кластеризации.

Свойства

K-means обладает следующими преимуществами:

простота реализации и интерпретации;
высокая скорость работы на больших выборках;
хорошая применимость к компактным кластерам в евклидовом пространстве;
возможность использовать центры кластеров как прототипы или сжатое описание данных;
удобство применения как базового метода кластеризации и предварительной обработки данных.

Основные ограничения алгоритма:

необходимость заранее задавать число кластеров $k$ ;
чувствительность к начальной инициализации центров;
сходимость только к локальному минимуму;
чувствительность к выбросам;
слабая применимость к кластерам несферической или сильно вытянутой формы;
зависимость результата от масштабирования признаков;
трудности при кластерах разной плотности и существенно разного размера;
ограниченность классической постановки числовыми признаками и евклидовым расстоянием.

K-means минимизирует сумму квадратов расстояний, поэтому отдельные выбросы могут заметно смещать центры кластеров. В задачах с большим числом выбросов часто используют предварительную очистку данных или альтернативные методы, например DBSCAN либо варианты робастной кластеризации.

Граница между кластерами в k-means задаётся диаграммой Вороного по центрам кластеров. Каждый объект относится к той области пространства, центр которой ближе всего. Поэтому алгоритм естественно порождает выпуклые области принадлежности и плохо описывает кластеры сложной нелинейной формы.

Временная сложность одной итерации алгоритма Ллойда составляет

$O(nkd),$

где $n$ — число объектов, $k$ — число кластеров, $d$ — размерность пространства. Если алгоритм выполняет $T$ итераций, общая сложность составляет

$O(Tnkd).$

Память требуется для хранения данных, центров кластеров и меток объектов. Без хранения полной матрицы расстояний объём памяти составляет

$O(nd+kd+n).$

Связь с вероятностными моделями

K-means можно рассматривать как предельный случай кластеризации с помощью смеси гауссовских распределений при некоторых дополнительных предположениях. Если компоненты смеси имеют одинаковые сферические ковариационные матрицы, а дисперсия стремится к нулю, то задача максимизации правдоподобия приводит к жёсткому назначению объектов ближайшим центрам.

В этом смысле k-means близок к алгоритму EM для смеси гауссовских распределений, но отличается тем, что использует жёсткие метки кластеров вместо вероятностных принадлежностей. Поэтому k-means можно интерпретировать как метод жёсткой кластеризации, тогда как смеси распределений дают мягкую кластеризацию.

Реализация

Ниже приведён пример применения k-means на языке Python с использованием библиотеки scikit-learn.

import numpy as np
from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
 
X = np.array([
[0.0, 0.1],
[0.1, 0.0],
[0.2, 0.1],
[5.0, 5.1],
[5.1, 5.0],
[5.2, 5.1],
[10.0, 10.0]
])
 
X_scaled = StandardScaler().fit_transform(X)
 
model = KMeans(
n_clusters=2,
init="k-means++",
n_init=10,
random_state=42
)
 
labels = model.fit_predict(X_scaled)
centers = model.cluster_centers_
 
print(labels)
print(centers)

В scikit-learn параметр n_clusters соответствует числу кластеров $k$ , параметр init задаёт способ инициализации центров, а n_init определяет число запусков алгоритма с разными начальными центрами.

Пример простой учебной реализации алгоритма Ллойда:

import numpy as np
 
def initialize_centers(X, k, random_state=None):
rng = np.random.default_rng(random_state)
indices = rng.choice(len(X), size=k, replace=False)
return X[indices].copy()
 
def assign_clusters(X, centers):
distances = np.linalg.norm(X[:, None, :] - centers[None, :, :], axis=2)
return np.argmin(distances, axis=1)
 
def update_centers(X, labels, k, old_centers):
centers = old_centers.copy()
 
```
for j in range(k):
    cluster_points = X[labels == j]
 
    if len(cluster_points) > 0:
        centers[j] = cluster_points.mean(axis=0)
 
return centers
```
 
def kmeans(X, k, max_iter=100, tol=1e-4, random_state=None):
centers = initialize_centers(X, k, random_state=random_state)
 
```
for _ in range(max_iter):
    labels = assign_clusters(X, centers)
    new_centers = update_centers(X, labels, k, centers)
 
    shift = np.linalg.norm(new_centers - centers)
 
    centers = new_centers
 
    if shift < tol:
        break
 
labels = assign_clusters(X, centers)
return labels, centers
```
 
X = np.array([
[0.0, 0.1],
[0.1, 0.0],
[0.2, 0.1],
[5.0, 5.1],
[5.1, 5.0],
[5.2, 5.1],
[10.0, 10.0]
])
 
labels, centers = kmeans(X, k=2, random_state=42)
 
print(labels)
print(centers)

Данная реализация предназначена только для иллюстрации. В практических задачах используют оптимизированные реализации, поддерживающие несколько запусков, k-means++, мини-батчи и эффективные операции над матрицами.

Варианты и обобщения

Существует несколько распространённых вариантов и обобщений k-means.

Mini-batch k-means использует на каждой итерации не всю выборку, а случайную мини-выборку объектов. Это снижает вычислительные затраты и позволяет применять алгоритм к большим наборам данных.

K-medoids вместо среднего вектора использует в качестве центра кластера один из объектов выборки. Такой подход может быть устойчивее к выбросам и допускает использование более общих матриц расстояний.

Kernel k-means применяет идею k-means в пространстве признаков, задаваемом ядром. Это позволяет строить нелинейные границы между кластерами, однако требует работы с матрицей ядра.

Fuzzy c-means является методом мягкой кластеризации: объект может принадлежать нескольким кластерам с разными степенями принадлежности.

См. также

Литература

MacQueen J. Some Methods for Classification and Analysis of Multivariate Observations // Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability. — 1967. — С. 281—297.

Lloyd S. Least Squares Quantization in PCM // IEEE Transactions on Information Theory. — 1982. — Т. 28. — № 2. — С. 129—137.

Forgy E. W. Cluster Analysis of Multivariate Data: Efficiency versus Interpretability of Classifications // Biometrics. — 1965. — Т. 21. — С. 768—769.

Arthur D.; Vassilvitskii S. k-means++: The Advantages of Careful Seeding // Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. — 2007. — С. 1027—1035.

Hastie T.; Tibshirani R.; Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. — 2. — Springer, 2009.

Bishop C. M. Pattern Recognition and Machine Learning. — Springer, 2006.

Источник — «http://www.recognition.su/wiki/index.php?title=K-means»

Категории: Кластеризация | Обучение без учителя | Алгоритмы машинного обучения