Skip to content
Назад к результатам поиска

Кластеризация методом k-средних

Автор метода
MacQueen, J. B.; Lloyd, S. P.
Год
1967 (formalized 1982)
Тип
Partitional clustering
Семейство
Machine learning

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

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

Это один из наиболее широко используемых разведочных инструментов в машинном обучении и анализе данных.

Интуиция метода

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

История

Идея k-средних была независимо представлена Мак-Куином в 1967 году, который придумал термин, и формализована как эффективный итеративный алгоритм Стюартом Ллойдом в Bell Labs в 1950-х годах (опубликовано в 1982 году). Улучшение инициализации k-means++ Артуром и Вассильвицким в 2007 году решило проблему чувствительности к локальным минимумам. Сегодня k-means остается краеугольным камнем неконтролируемого обучения, преподаваемым практически в каждом учебном плане по науке о данных.

Когда применять

k-means подходит для разведочной кластеризации больших, чисто числовых наборов данных, когда вам нужно быстрое, масштабируемое разбиение, и вы готовы заранее указать K или искать его с помощью метода локтя или силуэта. Он хорошо работает для сегментации клиентов, сжатия изображений, группировки тем документов и предварительной обработки перед обучением с учителем. Избегайте его, когда кластеры не являются сферическими, имеют сильно различающиеся размеры или плотности, когда признаки категориальные или порядковые (используйте k-modes или k-prototypes вместо этого), когда количество кластеров полностью неизвестно, а эксперименты с различными K невозможны, или когда данные содержат много выбросов (используйте DBSCAN или робастные варианты вместо этого).

Ограничения и замечания

  • Требует предварительного задания K; неправильный выбор K приводит к бессмысленным кластерам.
  • Предполагает сферические кластеры одинакового размера; вытянутые, неправильные или кластеры с разным масштабом разделяются или объединяются некорректно.
  • Чувствителен к выбросам: одна экстремальная точка может сильно сместить центроид от основной массы кластера.
  • Работает только с непрерывными числовыми признаками; категориальные данные требуют другого алгоритма (k-modes).
  • Сходится к локальному минимуму; результаты могут различаться при разных запусках с разными случайными зернами, если не используются k-means++ или множественные перезапуски.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Быстрый и масштабируемый: O(nKdi) за итерацию, практичен на миллионах наблюдений с умеренными K и размерностями.
  • Прост в реализации, широко доступен в каждом основном фреймворке машинного обучения и легко объясним нетехнической аудитории.
  • Хорошо работает на больших, хорошо разделенных, примерно сферических кластерах одинакового размера.
  • Инициализация k-means++ существенно снижает чувствительность к начальным условиям по сравнению со случайной инициализацией.
  • Детерминирован при фиксированном случайном зерне, что делает результаты воспроизводимыми.

Применение

  • Сегментация клиентов для маркетинга и персонализации на основе поведенческих или демографических признаков.
  • Сжатие изображений путем квантования цветов пикселей до K репрезентативных значений (квантование цвета).
  • Кластеризация документов и текстов как этап в конвейерах тематического моделирования после векторизации.
  • Предварительная обработка для обнаружения аномалий: точки, далекие от любого центроида, являются кандидатами в выбросы.
  • Этап инициализации для более сложных алгоритмов, таких как гауссовы смеси или иерархическая кластеризация.
  • Анализ экспрессии генов для группировки генов или образцов со схожими профилями экспрессии.

Как это работает

Как это работает

1

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

2

Каждое наблюдение назначается кластеру, центроид которого является ближайшим согласно евклидову расстоянию. Это жесткое назначение создает K непересекающихся разбиений данных. Формально, каждая точка x_i назначается кластеру c_i = argmin_k ||x_i - mu_k||^2.

Формула
c_i = \arg\min_k \|x_i - \mu_k\|^2
3

Каждый центроид пересчитывается как среднее арифметическое всех точек, в настоящее время назначенных этому кластеру: mu_k = (1/|C_k|) * сумма всех x_i в C_k. Этот шаг гарантирует, что новый центроид минимизирует WCSS в каждом кластере при текущем назначении.

Формула
\mu_k = \frac{1}{|C_k|} \sum_{x_i \in C_k} x_i
4

Шаги назначения и обновления чередуются до тех пор, пока положения центроидов не перестанут изменяться (или изменятся менее чем на пороговое значение) или не будет достигнуто максимальное количество итераций. Алгоритм гарантированно сходится к локальному минимуму WCSS, но не обязательно к глобальному минимуму.

5

Качество решения оценивается по общей WCSS (инерции) J = сумма по кластерам суммы по назначенным точкам ||x_i - mu_k||^2. Выбор K является отдельной проблемой, решаемой методом локтя, силуэтными оценками или разрывной статистикой, поскольку сам алгоритм требует предварительного задания K.

Формула
J = \sum_{k=1}^{K} \sum_{x_i \in C_k} \|x_i - \mu_k\|^2

Частые ошибки

  • Забывание стандартизировать признаки перед кластеризацией — переменные с большими масштабами будут доминировать в расчетах расстояний.
  • Выбор K путем рассмотрения только WCSS в выборке без графика локтя или силуэтной валидации, что приводит к тривиально малому или большому K.
  • Запуск только одной инициализации и принятие первого результата без множественных перезапусков для защиты от плохих локальных минимумов.
  • Включение категориальных или порядковых переменных в матрицу признаков без соответствующего кодирования или перехода на k-modes.
  • Рассмотрение меток кластеров как значимых идентификаторов групп без внешней валидации, особенно когда кластеры нечетко разделены.

Часто задаваемые вопросы

Как выбрать правильное количество кластеров K?

Запустите k-means для диапазона значений K, постройте график суммы квадратов внутри кластера в зависимости от K и найдите 'локоть', где скорость уменьшения резко замедляется. Дополните это силуэтными оценками, которые измеряют, насколько каждая точка похожа на свой собственный кластер по сравнению с соседними кластерами; более высокий средний силуэт указывает на лучше определенные кластеры.

Почему я получаю разные результаты при каждом запуске?

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

Работает ли k-means с категориальными данными?

Нет. k-means полагается на евклидово расстояние и средние значения центроидов, которые не определены для категориальных переменных. Для чисто категориальных данных используйте k-modes; для смешанных числовых и категориальных данных используйте k-prototypes.

Когда мне следует предпочесть DBSCAN или GMM вместо k-means?

Используйте DBSCAN, когда кластеры имеют неправильную форму или вам нужно автоматическое обнаружение выбросов без указания K. Используйте модели гауссовых смесей (GMM), когда вам нужны мягкие (вероятностные) назначения кластеров или кластеры разных размеров и ориентаций, ценой более высокой вычислительной сложности.

Нужно ли мне масштабировать мои признаки?

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

Похожие методы

Источники

  1. Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129–137.

    Открыть ссылку DOI
    Скопировано.
  2. MacQueen, J. B. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, 1, 281–297.

    Открыть ссылку на публикацию
    Скопировано.