Как решать задание 27 ЕГЭ по информатике — кластерный анализ и программирование

О чём задание

Задание 27 — самое сложное в ЕГЭ по информатике (2 первичных балла, как и задание 26). Тебе дают файлы с координатами точек на плоскости (в файле А — до 1000, в файле Б — до 10 000). Нужно:

1. Разбить точки на кластеры (группы близких точек)
2. Найти центр каждого кластера — точку из набора, от которой сумма расстояний до всех остальных точек кластера минимальна
3. Вычислить ответ по формуле из условия

Задание идёт с двумя файлами: файл А (обычно 2 кластера, до 1000 точек — проще) и файл Б (обычно 3 кластера, до 10 000 точек — сложнее).

Что такое кластер в реальных данных

Кластерный анализ — это не абстрактная штука из ЕГЭ, а рабочий инструмент из анализа данных и машинного обучения. На практике он используется везде, где нужно найти группы похожих объектов:

• Маркетинг — разбить клиентов на сегменты по поведению (активные/пассивные, лояльные/случайные) и делать разные рассылки
• Биология — объединять гены со схожими паттернами экспрессии, находить виды по морфологическим признакам
• Медицина — разделять пациентов по реакции на лечение, находить подтипы заболеваний
• Поисковики и рекомендательные системы — группировать похожие новости, товары, фильмы
• Компьютерное зрение — сегментация изображений по цветам и текстурам

В ЕГЭ тебе дают упрощённый вариант: 2D-точки и хорошо разделённые кластеры. В реальных задачах кластеров могут быть сотни в десятках измерений — но принцип тот же.

Что нужно знать

Расстояние между точками

Евклидово расстояние: d = sqrt((x2-x1)² + (y2-y1)²)

Центр кластера (медоид)

В условиях ЕГЭ центр кластера — это точка из набора данных, для которой сумма расстояний до всех остальных точек кластера минимальна. В математике такая точка называется медоид. Это не среднее арифметическое координат (центроид), хотя среднее — хорошее начальное приближение для поиска медоида.

Кластер

Группа точек, расположенных «близко» друг к другу. В задачах обычно кластеры хорошо разделены визуально — между ними большой пробел.

Разобранный мини-пример

Пусть дано 8 точек и нужно разбить их на 2 кластера:

A(1, 1)  B(1, 2)  C(2, 1)  D(2, 2)
E(8, 8)  F(8, 9)  G(9, 8)  H(9, 9)

Шаг 1: Разбиение. Сортируем по X: 1, 1, 2, 2, 8, 8, 9, 9. Между 2 и 8 — разрыв 6 (а все остальные — по 1 или 0). Граница найдена. Кластер 1: A, B, C, D. Кластер 2: E, F, G, H.

Шаг 2: Поиск медоида в первом кластере. Для каждой точки считаем сумму расстояний до остальных трёх. Все 4 точки расположены в углах квадрата 1×1 — по симметрии суммы одинаковые, медоидом становится любая из них (в таких случаях берут точку с наименьшими координатами — A).

Шаг 3: Поиск медоида во втором кластере. То же самое — симметричный квадрат, медоид E(8, 8).

Шаг 4: Ответ. Если формула из условия — сумма X-координат медоидов, то ответ: 1 + 8 = 9. Если int((Px1 + Px2) * 10000) — то 90 000.

Таков общий шаблон: разделить → найти медоид каждого кластера → подставить в формулу.

Алгоритм решения

Шаг 1: Визуализация (опционально, но полезно)

Открой файл в Excel или Google Sheets, построй точечную диаграмму. Ты сразу увидишь кластеры.

Шаг 2: Разделение на кластеры

Простой подход: если кластеры хорошо разделены — отсортируй по X (или Y), найди большие разрывы между соседними значениями. Разрыв = граница кластера.

Программный подход на Python:

# Чтение данных
with open('data.txt') as f:
    points = []
    for line in f:
        x, y = map(float, line.split())
        points.append((x, y))

# Сортировка и визуальный поиск разрывов
points.sort()
for i in range(1, len(points)):
    dx = points[i][0] - points[i-1][0]
    if dx > 1:  # порог зависит от данных
        print(f"Разрыв между {i-1} и {i}: dx={dx}")

Шаг 3: Поиск центра кластера (медоида)

Для каждого кластера найди точку с минимальной суммой расстояний:

import math

def find_medoid(cluster):
    min_dist = float('inf')
    medoid = None
    for p in cluster:
        total = sum(
            math.sqrt((p[0]-q[0])**2 + (p[1]-q[1])**2)
            for q in cluster
        )
        if total < min_dist:
            min_dist = total
            medoid = p
    return medoid

Шаг 4: Вычисление ответа

Подставь координаты центров кластеров в формулу из условия. Обычно ответ — это int(Px * 10000) и int(Py * 10000) для каждого файла.

Разные методы разделения на кластеры

Выбор метода зависит от того, как расположены точки в конкретной задаче:

• Сортировка по X — работает, когда кластеры разделены по горизонтали. Самый частый случай в ЕГЭ
• Сортировка по Y — то же самое, но для вертикального разделения
• Сортировка по сумме X+Y или расстоянию от начала координат — если кластеры лежат «по диагонали»
• Разделение по расстоянию до общего среднего — посчитать среднюю точку всего набора, отсортировать по расстоянию до неё. Дальние точки образуют «внешние» кластеры, близкие — центральный
• k-means (упрощённый) — выбрать k случайных точек как начальные центры, каждый раз относить каждую точку к ближайшему центру и пересчитывать центры. Повторять до стабилизации. Нужен редко, но полезно знать принцип

На ЕГЭ в 99% случаев хватает сортировки по X или Y и поиска самых больших разрывов.

Полный шаблон решения на Python

Вот рабочий код, который решает типовое задание 27 — два файла, по 2-3 кластера, медоид каждого:

import math

def solve(filename, n_clusters):
    # 1. Читаем точки
    with open(filename) as f:
        points = []
        for line in f:
            x, y = map(float, line.split())
            points.append((x, y))

    # 2. Сортируем по X, находим разрывы
    points.sort()
    gaps = []
    for i in range(1, len(points)):
        dx = points[i][0] - points[i-1][0]
        gaps.append((dx, i))
    # Берём n_clusters-1 самых больших разрывов
    gaps.sort(reverse=True)
    splits = sorted(g[1] for g in gaps[:n_clusters-1])

    # 3. Разрезаем список на кластеры
    clusters = []
    prev = 0
    for s in splits:
        clusters.append(points[prev:s])
        prev = s
    clusters.append(points[prev:])

    # 4. Для каждого кластера — медоид
    medoids = []
    for cluster in clusters:
        # Приближение: среднее
        mx = sum(p[0] for p in cluster) / len(cluster)
        my = sum(p[1] for p in cluster) / len(cluster)
        # Ищем ближайшие 200 точек к среднему
        cluster.sort(key=lambda p: (p[0]-mx)**2 + (p[1]-my)**2)
        candidates = cluster[:200]
        # Среди них — настоящий медоид
        best = None
        best_sum = float('inf')
        for p in candidates:
            s = sum(math.hypot(p[0]-q[0], p[1]-q[1]) for q in cluster)
            if s < best_sum:
                best_sum = s
                best = p
        medoids.append(best)

    return medoids

medoids_A = solve('27_A.txt', 2)
medoids_B = solve('27_B.txt', 3)

# Дальше — формула из условия, например:
# answer = sum(int(m[0] * 10000) for m in medoids_A)

Этот шаблон закрывает примерно 90% вариантов задания 27. Остаются нюансы вроде «медоид с чётным индексом» или «сумма квадратов координат» — это правится в последних строках.

Оптимизация для 10000 точек

Перебор всех пар точек — O(n²). Для 10 000 точек это 100 миллионов операций — в чистом Python может занять 30+ секунд. Основные техники:

1. Предварительная сортировка. points.sort() — O(n log n) вместо сравнения пар. Это уже разделение на кластеры почти бесплатно
2. Среднее как приближение. Вычисли среднее X и Y кластера, затем ищи медоид среди 100-200 точек, ближайших к среднему. Сложность падает с O(n²) до O(n) на поиск + O(k·n) на итоговую проверку
3. math.hypot(dx, dy) быстрее, чем math.sqrt(dx**2 + dy**2) на 20-30%
4. Убрать квадратный корень. Если надо только сравнивать расстояния — работай с квадратами расстояний. Сравнение a² < b² эквивалентно a < b для положительных чисел
5. numpy — если разрешено использовать. np.linalg.norm(points - p, axis=1) считает все расстояния одним махом и работает в 50-100 раз быстрее

Профилируй своё решение на файле Б перед экзаменом — если оно отрабатывает за 5 секунд дома, на компьютере в аудитории будет не сильно хуже.

Типичные ошибки

Ошибка 1: Центр кластера ≠ среднее. Среднее арифметическое координат — это центроид (геометрический центр). Центр кластера из условия ЕГЭ — это медоид, реальная точка из набора с минимальной суммой расстояний. Обычно они близки, но не совпадают.

Ошибка 2: Неправильное разделение на кластеры. Если кластеры пересекаются по одной из координат — сортировка только по X не поможет. Используй визуализацию.

Ошибка 3: Точность вычислений. Работай с float, не округляй промежуточные результаты. Округляй только финальный ответ.

Ошибка 4: Забыл про файл Б. Задание требует ответы для обоих файлов. Файл Б сложнее — там больше кластеров и может потребоваться другой порог разделения.

Типичные ловушки в формулировке

Задание 27 любит «ловушки» в самой формуле ответа. Читай условие медленно:

• Сумма координат vs произведение — можно не туда подставить
• int() vs round() — int(3.99) даёт 3, а round(3.99) даёт 4. В ЕГЭ обычно нужно именно int() после умножения на 10000
• Сумма по всем кластерам или только по конкретному — иногда нужен медоид только «среднего» кластера
• X или Y координаты — путают под стрессом, особенно если в условии несколько формул
• Размерность множителя — 10000 или 100000, каждый год может быть разный

Сколько времени тратить

Задание 27 стоит 2 первичных балла (как и задание 26). По рекомендациям ФИПИ на него стоит выделять не менее 40 минут. Если файл А решился быстро, а файл Б не поддаётся — сдай хотя бы ответ для А (можно получить 1 балл из 2). Эта стратегия «отдать половину» может оказаться решающей для итогового балла — подробный разбор стратегии экзамена в материале Как набрать 90+ баллов, а проходные пороги под конкретные вузы — в статье про баллы.

Как тренироваться

• Начни с 8-10 точек вручную. Нарисуй на бумаге, раздели глазами, посчитай медоид перебором. Это ставит понимание
• Потом — 50-100 точек в Excel. Построй диаграмму, убедись, что видишь кластеры
• Затем — Python на 1000 точек (аналог файла А). Научись писать шаблон за 15 минут без подглядывания
• В финале — 10 000 точек (аналог файла Б). Здесь появляются оптимизации и контроль времени выполнения

Задание 27 требует навыков программирования и работы с данными. Начни с простых задач на кластеризацию и постепенно увеличивай сложность. В TuteMe есть задачи разного уровня с автоматической проверкой.

Попробовать бесплатно →