K-Means Clustering

Кластеризация k-средних — это алгоритм обучения без учителя, который разбивает данные на k групп, представленных центроидами — средними значениями точек, отнесённых к каждой группе. Он ищет такое разбиение, при котором сумма квадратов расстояний внутри кластеров минимальна. Эта величина называется инерцией; она показывает, насколько близко точки кластера расположены к его центроиду. Стандартная процедура — алгоритм Ллойда, который Стюарт Ллойд разработал в Bell Labs в 1957 году для квантования сигналов; название «k-средних» появилось в статье Джеймса Маккуина 1967 года. Благодаря простоте, высокой скорости и способности масштабироваться до миллионов точек k-средние — стандартный инструмент для интеллектуального анализа данных, сжатия и исследования структуры неразмеченных данных.

Как работает алгоритм#

Выбрав начальные центроиды, алгоритм Ллойда попеременно выполняет этап назначения и этап обновления, пока кластеры не перестанут изменяться:

1. Инициализация: Выбери k начальных центроидов. Метод k-means++, используемый по умолчанию в Scikit-learn, случайным образом выбирает первый центроид, а для каждого следующего использует вероятность, пропорциональную квадрату расстояния до ближайшего уже выбранного центроида. Благодаря этому начальные точки располагаются на расстоянии друг от друга.
2. Назначение: Отнеси каждую точку к ближайшему центроиду, обычно используя евклидово расстояние.
3. Обновление: Перемести каждый центроид в среднее положение точек, которые теперь к нему относятся.
4. Повторение: Возвращайся к этапу назначения, пока ни одна точка не сменит кластер или центроиды не сместятся меньше заданного допуска.

Ни один из двух этапов не может увеличить инерцию, поэтому алгоритм всегда сходится, но лишь к локальному минимуму, который зависит от начальных центроидов. Найти глобальный оптимум — NP-трудная задача, поэтому реализации запускают несколько инициализаций и выбирают ту, у которой инерция минимальна. В KMeans из scikit-learn параметр n_init="auto" по умолчанию запускает алгоритм один раз при инициализации k-means++ и 10 раз при случайной инициализации.

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

Для работы k-средних нужно заранее задать k. Инерция всегда уменьшается с ростом k, поскольку центроиды располагаются ближе к точкам. Поэтому метод локтя строит график зависимости инерции от k и ищет точку, где снижение замедляется. Коэффициент силуэта сравнивает для каждой точки среднее расстояние до своего кластера со средним расстоянием до ближайшего другого кластера. Его значения лежат в диапазоне от -1 до 1; более высокие значения соответствуют компактным, хорошо разделённым кластерам. В этом примере оцениваются значения k от 2 до 6 для данных, сформированных вокруг четырёх центров:

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score

# 600 unlabeled points drawn around 4 hidden centers
X, _ = make_blobs(n_samples=600, centers=4, cluster_std=1.0, random_state=7)

# Fit k-means for several k and score each partition
for k in range(2, 7):
    kmeans = KMeans(n_clusters=k, n_init="auto", random_state=0)
    labels = kmeans.fit_predict(X)
    print(f"k={k}  inertia={kmeans.inertia_:8.0f}  silhouette={silhouette_score(X, labels):.3f}")

Инерция снижается с 18 363 при k=2 до 5 241 при k=3 и 1 127 при k=4, а затем — лишь до 1 039 при k=5 и 922 при k=6, поэтому точка локтя находится при k=4. Коэффициент силуэта подтверждает этот результат: он достигает максимума 0.811 при k=4 и снижается до 0.687 при k=5, помогая восстановить четыре центра, вокруг которых были сформированы данные.

Предположения и варианты#

K-средние лучше всего работает, когда кластеры примерно сферические, сопоставимы по размеру и отделены друг от друга в евклидовом пространстве. Признаки с большим масштабом сильнее влияют на расстояние, поэтому данные обычно сначала стандартизируют. Каждая точка попадает в какой-либо кластер, а несколько крайних выбросов могут сместить центроид в сторону от своей группы. Некоторые варианты ослабляют эти ограничения:

• Мини-пакетные k-средние: Обновляют центроиды на небольших случайных пакетах, немного жертвуя точностью ради гораздо более быстрого обучения на больших наборах данных.
• K-медоиды: Используют в качестве центров кластеров реальные точки данных, что повышает устойчивость к выбросам и позволяет использовать любую меру расстояния.
• Нечёткие c-средние: Назначают каждой точке степень принадлежности к каждому кластеру в духе нечёткой логики, а не жёстко относят её к одному кластеру.
• Модели гауссовых смесей: Подбирают распределение вероятностей для каждого кластера, что позволяет описывать эллиптические кластеры разных размеров и возвращать мягкие вероятностные назначения.

Применение в ИИ и компьютерном зрении#

• Квантование цветов: кластеризация цветов пикселей изображения и замена каждого пикселя центроидом сокращают палитру фотографии с тысячами цветов до k цветов. Это сжимает изображение и одновременно обеспечивает быстрый, приблизительный вариант сегментации изображений.
• Кодовые книги и векторное квантование: центроиды образуют кодовую книгу, а каждый вектор хранится как индекс ближайшего центроида. Классический поиск изображений методом «мешка визуальных слов» строил словари таким способом на основе локальных дескрипторов изображений.
• Проектирование анкерных блоков: YOLOv2 применял k-средних к ширине и высоте обучающих рамок, используя 1 минус IoU в качестве расстояния, чтобы выбрать анкерные блоки.
• Палитризация весов: при экспорте YOLO26 в Core ML с помощью quantize=8 значения каждого большого тензора весов кластеризуются методом k-средних в 256 центроидов, поэтому экспортированная модель хранит для каждого веса 8-битный индекс и небольшую таблицу поиска.
• Сегментация клиентов: розничные продавцы группируют клиентов по частоте покупок, размеру корзины и давности последней покупки, чтобы подбирать предложения для каждого сегмента.

K-средних и родственные алгоритмы#

• Метод k ближайших соседей (KNN): общая буква «k» может сбивать с толку. KNN — это алгоритм обучения с учителем, который присваивает новой точке метку на основе k ближайших размеченных примеров, а k-средних — алгоритм без учителя, где k обозначает число создаваемых кластеров.
• DBSCAN: группирует точки по плотности, самостоятельно определяет число кластеров, находит кластеры любой формы и помечает разреженные точки как шум, а не принудительно включает их в кластер.
• Иерархическая кластеризация: строит дерево вложенных кластеров, многократно объединяя ближайшие группы. Поэтому k можно выбрать позже, разрезав дерево на любом уровне, но вычислительные затраты растут как минимум квадратично с числом точек.