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