Зачем это в ЕГЭ. Задание 27 (высокий уровень сложности, 2 первичных балла) проверяет умение разрабатывать эффективные алгоритмы обработки данных. Встречается в 80% реальных вариантов, часто требует применения методов кластеризации для анализа наборов точек.
Главная идея. Кластеризация — это группировка данных по схожести. В ЕГЭ обычно нужно реализовать алгоритм k-средних или иерархическую кластеризацию. Ключ — правильно определить метрику расстояния и критерий остановки.
Алгоритм (чеклист).
1. Загрузи данные (координаты точек из файла или списка).
2. Выбери количество кластеров k (часто дано в условии).
3. Инициализируй центроиды (случайно или по правилу).
4. Назначь точки ближайшим центроидам (евклидово расстояние).
5. Пересчитай центроиды как среднее точек кластера.
6. Повторяй шаги 4-5, пока центроиды не стабилизируются.
Опоры (кратко).
- Формула евклидова расстояния:
- Критерий остановки:
- Метод локтя для определения k (минимум суммы квадратов расстояний).
Пример 1 (k-средних).
Шаг 1. Даны точки: [(1,2), (1,4), (10,5), (11,4)], k=2.
Шаг 2. Инициализируем центроиды: (1,2) и (10,5).
Шаг 3. Кластер 1: [(1,2), (1,4)], кластер 2: [(10,5), (11,4)].
Шаг 4. Новые центроиды: (1,3) и (10.5,4.5).
Шаг 5. Кластеры не изменились — остановка.
Пример 2 (иерархическая).
Шаг 1. Даны точки: [(1,1), (1,2), (5,5), (6,6)], порог расстояния=3.
Шаг 2. Объединяем (1,1) и (1,2) в кластер (среднее (1,1.5)).
Шаг 3. Объединяем (5,5) и (6,6) в кластер (5.5,5.5).
Шаг 4. Расстояние между кластерами >3 — остановка.
Типичные ошибки.
1. Неправильная инициализация центроидов — выбирай точки максимально далёкие.
2. Игнорирование условия остановки — добавляй счётчик итераций.
3. Пустые кластеры — проверяй len(cluster) перед пересчётом центроида.
4. Неправильная метрика — для географических данных используй haversine.
Дальше. Разбери реализацию DBSCAN для задач с шумами.