K-means: как машины группируют данные

🎯 Зачем это нужно?

Представь Instagram без рекомендаций 📱. Или Spotify, который не знает твой музыкальный вкус 🎵. А что если Netflix показывал бы всем одни и те же фильмы? 🎬

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

• 🛍️ E-commerce: “Люди как ты также покупали…”
• 🎮 Геймдев: Группировка игроков по скиллу в рейтинговых играх
• 📊 Маркетинг: Сегментация клиентов для таргетированной рекламы
• 🧬 Биоинформатика: Группировка генов по функциям

📚 История вопроса

K-means изобрел Стюарт Ллойд в Bell Labs в 1957 году для передачи сигналов! Но опубликовал только в 1982 - засекретили на 25 лет 🤫.

Параллельно тот же алгоритм переоткрыли в 1960-х для экономики и маркетинга. Сейчас его используют везде - от анализа космических снимков до рекомендательных систем.

💡 Интуиция

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

K-means работает точно так же:

1️⃣ Расставляем стулья (k центроидов) случайно по залу 2️⃣ Каждый подходит к ближайшему стулу (относим точки к ближайшему центроиду)
3️⃣ Двигаем стулья в центр своих групп (пересчитываем центроиды) 4️⃣ Повторяем, пока стулья не перестанут двигаться (до сходимости)

[МЕДИА: image_01] Описание: Анимация работы k-means алгоритма на примере группировки людей на дискотеке Промпт: “educational animation showing k-means clustering process, people at school disco gradually forming groups around chairs, colorful modern illustration, step-by-step visualization, friendly cartoon style”

📐 Формальное определение

K-means - это алгоритм разбиения n точек на k кластеров, минимизирующий внутрикластерную сумму квадратов (WCSS):

J = ∑ᵢ₌₁ᵏ ∑ₓ∈Cᵢ ||x - μᵢ||²

Где:

• k - количество кластеров (задаем заранее)
• Cᵢ - i-й кластер
• μᵢ - центроид i-го кластера
• ||x - μᵢ||² - квадрат евклидова расстояния

Алгоритм Ллойда:

1. Инициализируем k центроидов случайно
2. REPEAT:
   a) Присваиваем каждую точку ближайшему центроиду
   b) Пересчитываем центроиды как среднее своих точек
3. UNTIL центроиды не изменились

🔍 Примеры с разбором

Пример 1: Группировка клиентов интернет-магазина

Данные: возраст покупателей и сумма покупок в месяц

Хотим k=2 кластера

Шаг 1: Случайно выбираем центроиды

• μ₁ = (30, 20)
• μ₂ = (40, 30)

Шаг 2: Считаем расстояния и присваиваем кластеры

Для клиента A (25, 15):

• до μ₁: √((25-30)² + (15-20)²) = √(25+25) = 7.07
• до μ₂: √((25-40)² + (15-30)²) = √(225+225) = 21.21 → A идет в кластер 1

Аналогично для всех:

• Кластер 1: A, B, E (молодежь с небольшими тратами)
• Кластер 2: C, D, F (возрастные с большими тратами)

Шаг 3: Пересчитываем центроиды

• μ₁ = ((25+28+23)/3, (15+18+12)/3) = (25.3, 15.0)
• μ₂ = ((45+50+47)/3, (35+40+38)/3) = (47.3, 37.7)

[МЕДИА: image_02] Описание: Пошаговая визуализация k-means на данных клиентов Промпт: “step-by-step k-means clustering visualization, scatter plot with age vs spending, two distinct clusters forming, centroids moving, before and after comparison, professional data science style”

Пример 2: Оптимальное количество кластеров

Проблема: Как выбрать k?

Метод локтя (Elbow method): Строим график WCSS от k и ищем “локоть” - точку, где улучшение замедляется.

# Псевдокод для метода локтя
wcss = []
for k in range(1, 11):
    kmeans = KMeans(n_clusters=k)
    kmeans.fit(data)
    wcss.append(kmeans.inertia_)  # WCSS
    
plot(range(1,11), wcss)  # Ищем "локоть"

Практическое правило: Если график похож на руку, k находится в “локте” 💪

🎮 Практика

Базовый уровень 🟢

Задание 1: У тебя есть 4 точки: (1,1), (2,1), (5,5), (6,6). Выполни одну итерацию k-means с k=2 и начальными центроидами (2,2) и (5,5).

Задание 2: Объясни, почему k-means может дать разные результаты при повторном запуске.

Задание 3: Приведи пример данных, где k-means работает плохо.

Продвинутый уровень 🟡

Задание 4: Реализуй функцию расчета WCSS для заданного разбиения:

def calculate_wcss(points, clusters, centroids):
    # твой код
    pass

Задание 5: Пользователи игры характеризуются временем в сутки (0-24ч) и уровнем (1-100). Как бы ты сегментировал их для разных типов контента?

Задание 6: Почему в k-means используется именно евклидово расстояние? Когда это плохо?

Челлендж 🔴

Задание 7: Докажи, что алгоритм Ллойда всегда сходится (или объясни, почему это не всегда так).

Задание 8: Предложи модификацию k-means для работы с категориальными признаками (цвет глаз, любимый жанр музыки).

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

❌ Ошибка: “K-means найдет оптимальные кластеры автоматически” ✅ Правильно: Нужно задать k заранее и проверить разные значения 💡 Почему: Алгоритм минимизирует WCSS при фиксированном k, но не выбирает k

❌ Ошибка: Не нормализовать признаки с разными масштабами ✅ Правильно: Привести все признаки к одному масштабу (StandardScaler)
💡 Почему: Признак “зарплата” (тысячи) доминирует над “возраст” (десятки)

❌ Ошибка: Использовать k-means для кластеров произвольной формы ✅ Правильно: K-means для округлых, одинаковых по размеру кластеров 💡 Почему: Алгоритм предполагает сферические кластеры равной дисперсии

❌ Ошибка: Игнорировать локальные минимумы ✅ Правильно: Запускать алгоритм несколько раз с разной инициализацией 💡 Почему: Результат зависит от начальных центроидов

🎓 Главное запомнить

✅ K-means группирует данные в k сферических кластеров равного размера ✅ Ключевая формула: J = ∑ᵢ₌₁ᵏ ∑ₓ∈Cᵢ ||x - μᵢ||²
✅ Применение: Сегментация клиентов, рекомендации, сжатие изображений

🔗 Связь с другими темами

Откуда пришли: Евклидово расстояние (геометрия), среднее арифметическое (статистика) Куда ведет: Иерархическая кластеризация, DBSCAN, Gaussian Mixture Models Связано с: PCA (снижение размерности перед кластеризацией), кросс-валидация (выбор k)