Разбивает объекты на k кластеров, минимизируя суммарное расстояние до центроидов.
- квадрат расстояния от объекта до центра его кластера
- минимизируется суммарный внутрикластерный разброс (инерция). Отсюда требование сферических кластеров
Ключевые тезисы
- Алгоритм Ллойда чередует назначение точек и пересчёт центров до сходимости.
- Предполагает сферические кластеры сопоставимого размера.
- Число k выбирают по методу локтя, силуэту или доменной логике; ++ улучшает инициализацию.
Какую задачу решает
разбивает объекты на групп так, чтобы внутри группы они были похожи, а между группами — различались. Формально минимизируется сумма квадратов расстояний до центров кластеров; алгоритм чередует два шага: приписать каждый объект ближайшему центру, затем пересчитать центры как средние.
Метод остаётся самым используемым в не потому, что он лучший, а потому, что он быстрый, понятный и предсказуемый. Его ограничения — сферические кластеры сопоставимого размера и необходимость задать заранее — надо знать до применения, иначе результат будет выглядеть осмысленным, будучи бессмысленным.
Классический контрпример — два концентрических кольца. Человек видит два кластера; видит центр общий для обоих и разрежет картинку пополам по диаметру, потому что он умеет строить только области вокруг центров. То же произойдёт с двумя вытянутыми параллельными полосами. Проверка занимает минуту: постройте PCA-проекцию с раскраской по кластерам — если границы выглядят как произвольные прямые поперёк видимой структуры, форма кластеров методу не подходит.
Подробный разбор
- среднее значение
- параметр C: цена нарушения зазора. Большое C — почти не прощаем ошибок
- объект: вектор признаков
- номер или количество: индекс шага, число соседей, кластеров или позиций
- суммирование по всем перечисленным элементам
- норма — длина вектора
- Инициализировать центры (лучше ++, а не случайно).
- Отнести каждый объект к ближайшему центру.
- Пересчитать центры как средние своих объектов.
- Повторять шаги 2–3, пока назначения меняются.
- Метод локтя: строим WCSS от и ищем точку, где падение резко замедляется.
- Силуэт: максимизируем среднюю величину , где — среднее расстояние внутри кластера, — до ближайшего чужого.
- Доменная логика: часто задаётся бизнесом (три сегмента клиентов, пять тарифов), и это лучший критерий.
предполагает сферические кластеры сопоставимого размера и плотности. Для вытянутых или вложенных структур результат будет бессмысленным — там нужны GMM, или спектральная .
Где применяется
- клиентовГруппировка по поведению и профилю для разной коммуникации.
- Сжатие и цветов изображения, кодовые книги для векторного поиска.
- ПредобработкаНомер кластера как новый для модели с учителем.
- Разведочный анализПервый взгляд на то, есть ли в данных группы вообще.
Плюсы, минусы и альтернативы
Плюсы
- Очень быстрый: линейная сложность по числу объектов.
- Простой и предсказуемый, легко объяснить нетехническому заказчику.
- Масштабируется до миллионов объектов (mini-batch вариант).
- Центроиды интерпретируемы — это «типичный представитель» группы.
- Легко применяется к новым объектам: ближайший центр.
Минусы
- нужно задать заранее, а объективного способа его выбрать нет.
- Предполагает сферические кластеры примерно одного размера и плотности.
- Чувствителен к выбросам: один далёкий объект утягивает центр.
- Результат зависит от инициализации (частично лечится ++).
- Обязательна .
- Всегда выдаёт кластеров, даже если структуры в данных нет вовсе.
Брать, если
- Кластеров ожидается примерно круглая форма и сопоставимый размер.
- Объектов много и нужна скорость.
- Число групп продиктовано задачей (например, нужно ровно 5 сегментов).
Не брать, если
- Кластеры вытянутые, вложенные или разной плотности — берите или GMM.
- Число кластеров неизвестно и подсказки от задачи нет.
- В данных много , и убрать их нельзя.
Чем заменяют
Связанные темы
Метрические и ядровые методы · Кластеризация и её оценка
DBSCAN75%
DBSCAN · Классическое машинное обучениеПлотностная кластеризация: кластеры — это связные области высокой плотности, остальное объявляется шумом.
GMM75%
Смесь гауссиан · Классическое машинное обучениеВероятностная модель: данные порождаются смесью нормальных распределений, параметры оцениваются EM-алгоритмом.
Clustering75%
Кластеризация · Обучение без учителяРазбиение объектов на группы похожих без заранее известных меток.
Density Estimation75%
Оценка плотности · Обучение без учителяВосстановление распределения данных: где объекты встречаются часто, а где почти никогда.
Association Rules75%
Ассоциативные правила · Обучение без учителяПоиск закономерностей вида «если A, то B» в транзакционных данных.
Silhouette Score75%
Силуэт · МетрикиСравнивает среднее расстояние объекта до своего кластера и до ближайшего чужого.
Davies–Bouldin75%
Индекс Дэвиса — Болдина · МетрикиОтношение внутрикластерного разброса к расстоянию между кластерами; чем меньше, тем лучше.
Calinski–Harabasz75%
Индекс Калинского — Харабаша · МетрикиОтношение межкластерной дисперсии к внутрикластерной; чем больше, тем лучше разделение.
Mapper75%
Алгоритм Mapper · Топологический анализ данныхСтроит граф-скелет данных: проекция фильтрующей функцией, покрытие интервалами, локальная кластеризация и склейка.
k-NN65%
Метод k ближайших соседей · Классическое машинное обучениеЛенивый алгоритм: предсказание — это голосование k ближайших объектов обучающей выборки.
SVM65%
Метод опорных векторов · Классическое машинное обучениеИщет гиперплоскость с максимальным зазором между классами; ядровой трюк добавляет нелинейность без явного перехода в новое пространство.
Distance65%
Расстояние · Математический справочникМера непохожести объектов — основа кластеризации, k-NN и поиска.
Norm65%
Норма · Математический справочникМера длины вектора; выбор нормы определяет геометрию задачи.
Normalization & Standardization65%
Нормализация и стандартизация · ДанныеПриведение признаков к сопоставимым масштабам, без которого расстояния, градиенты и регуляризация работают некорректно.
Metric spaces65%
Метрические пространства · Топологический анализ данныхМножество с функцией расстояния. Любой TDA-пайплайн начинается с выбора метрики.
Всё, что названо в описании, разобрано здесь же или в соседней теме — переходы под каждым определением.
Центроид
Среднее объектов кластера. Именно из-за усреднения метод чувствителен к выбросам.
Разбор ниже: Алгоритм ЛлойдаИнерция (WCSS)
Сумма квадратов расстояний до своих центров — то, что минимизируется. С ростом монотонно падает.
Разбор ниже: Выбор числа кластеровk-means++
Умная инициализация центров: разносит их подальше друг от друга и заметно улучшает результат.
Разбор ниже: Алгоритм ЛлойдаМетод локтя
Излом на графике инерции от . Часто размыт — поэтому рядом смотрят силуэт.
Разбор ниже: Выбор числа кластеровСилуэт
Насколько объект ближе к своему кластеру, чем к соседнему. Работает как оценка качества разбиения.
Отдельная тема: Silhouette Score — СилуэтУсиливает профиль: Data Scientist.
Спрашивают на собеседовании: Магнит — Ассортимент и спрос.
Глава «Классическое машинное обучение» последний раз правилась . Нашли ошибку — напишите.