Почему разные старты дают разные кластеры?

Ллойд монотонно уменьшает целевую функцию, но лишь до локального минимума невыпуклой задачи. Разные начальные центроиды попадают в разные «ловушки» — поэтому часто делают несколько перезапусков или умную инициализацию (k-means++).

Гарантируется ли глобально оптимальное разбиение?

Нет: даже на плоскости точная глобальная оптимизация k-средних в худшем случае NP-трудна. Итерации Ллойда — быстрый эвристический метод, который на «гладких» облаках обычно работает хорошо.

Что делать, если кластер опустел?

В рабочем коде часто переинициализируют центроид (например, в самую далёкую точку). Здесь пустой кластер оставляет старый центроид, чтобы не терять метку посреди шага; на следующем назначении состав может измениться.

Метод k-средних (алгоритм Ллойда)

Точки на плоскости, число кластеров k и стартовые центроиды. Шаг Ллойда: назначение к ближайшему центру и перенос центроида в центр масс. Демо — смесь гауссиан; внутрикластерная сумма квадратов.

Кластеры

k (число кластеров)4

Seed инициализации / R1

Итерации Ллойда

Тонкие линии точка → центроид

Данные

Размер демо-смеси56

Seed демо42

Пустой кластер на шаге средних сохраняет прежний центроид (учебная упрощённая политика).

Горячие клавиши

Щёлчок по полю — добавить точку (до 90)
Перетаскивание — сдвинуть точку
Shift+щелчок — удалить ближайшую
Пробел — один шаг Ллойда
R — новый seed и заново k центроидов из точек

Измеренные величины

Точек56

Число кластеров k4

Шагов Ллойда (всего)0

SSE внутри кластеров102.47

О модели

Метод k-средних разбивает конечное множество точек на k групп, минимизируя сумму квадратов евклидовых расстояний до центроидов. Здесь — классический алгоритм Ллойда: при фиксированных k центрах чередуются шаг назначения (каждая точка → ближайший центроид, ячейки Вороного) и шаг обновления (центроид ← среднее своих точек). На полном шаге внутрикластерная сумма квадратов не возрастает: назначение оптимально при фиксированных центрах, среднее — оптимум при фиксированных метках. Стартовые центроиды — k различных точек данных, выбранных перемешиванием с управляемым зерном; демо даёт смесь гауссиан. Пустой кластер сохраняет прежний центроид — учебный приём без полной логики k-means++.

Для кого: Анализ данных: обучение без учителя, диаграмма Вороного, чередующаяся минимизация.

Ключевые понятия

метод k-средних
алгоритм Ллойда
центроид
ячейка Вороного
внутрикластерная сумма квадратов
смесь гауссиан
локальный минимум
пустой кластер

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

Алгоритм Ллойда: шаг назначения — каждая точка к ближайшему из k центроидов; шаг обновления — центроид в центр масс своих точек. Старт — k случайных точек данных; демо — смесь гауссиан. Внутрикластерная сумма квадратов на полном шаге не растёт.

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

Почему разные старты дают разные кластеры?: Ллойд монотонно уменьшает целевую функцию, но лишь до локального минимума невыпуклой задачи. Разные начальные центроиды попадают в разные «ловушки» — поэтому часто делают несколько перезапусков или умную инициализацию (k-means++).
Гарантируется ли глобально оптимальное разбиение?: Нет: даже на плоскости точная глобальная оптимизация k-средних в худшем случае NP-трудна. Итерации Ллойда — быстрый эвристический метод, который на «гладких» облаках обычно работает хорошо.
Что делать, если кластер опустел?: В рабочем коде часто переинициализируют центроид (например, в самую далёкую точку). Здесь пустой кластер оставляет старый центроид, чтобы не терять метку посреди шага; на следующем назначении состав может измениться.

Продолжите с близкими темами в этой категории — или все 85 в «Визуализация математики».

Вся категория →

НовоеШкольные

Линейная регрессия: МНК, гребень, лассо и R²

Запустить симулятор

Точки на плоскости и модель y = β₀ + β₁x: обычный МНК, гребень (штраф L₂ по наклону) или лассо (штраф L₁). Сдвиг Δy у точки с наибольшим |x| — выброс с сильным рычагом; сравниваются SSE и R².

НовоеШкольные

Выпуклая оболочка (Грэм и QuickHull)

Запустить симулятор

Точки на плоскости: обход Грэма с пошаговой анимацией или QuickHull; сравнение множеств вершин.

НовоеШкольные

DBSCAN: плотностная кластеризация

Запустить симулятор

Радиус ε и порог minPts: ядро, граница и шум. Кластеры произвольной формы без заданного k; вокруг ядер можно показать окружности ε.

НовоеШкольные

Триангуляция Делоне и диаграмма Вороного

Запустить симулятор

Триангуляция Бойера–Уотсона и двойственная диаграмма Вороного: клик добавляет сайты, перетаскивание двигает.

НовоеШкольные

Метод наименьших квадратов

Запустить симулятор

Зашумлённые точки и прямая y = ax + b, которая минимизирует сумму квадратов вертикальных остатков. Меняйте наклон, сдвиг и шум — видны остатки и сумма квадратов ошибок.

НовоеУниверситет / научные

Адаптивный фильтр LMS / NLMS

Запустить симулятор

Первичный канал p = s + v, где v — неизвестная КИХ от опорного белого шума x[n]. L-отводный адаптивный КИХ по LMS или NLMS: ошибка e = p − wᵀx стремится к полезному сигналу s.

Метод k-средних (алгоритм Ллойда)

О модели

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

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

Похожие симуляторы

Линейная регрессия: МНК, гребень, лассо и R²

Выпуклая оболочка (Грэм и QuickHull)

DBSCAN: плотностная кластеризация

Триангуляция Делоне и диаграмма Вороного

Метод наименьших квадратов

Адаптивный фильтр LMS / NLMS

Метод k-средних (алгоритм Ллойда)

О модели

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

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