Задание 27 ЕГЭ по информатике: кластеризация данных

Задания 26 и 27 — единственные два из 27, где кроме «всё верно / всё неверно» есть промежуточный результат в 1 балл. Вот дословная формулировка спецификации:

«Если в ответе на задания 26, 27 верные числа в ячейках таблицы перепутаны местами ИЛИ в ячейках таблицы на верном месте присутствует только одно верное число (второе неверно или отсутствует), ставится 1 балл. В остальных случаях – 0 баллов.» (демоверсия ЕГЭ-2027 по информатике, «Система оценивания»)

С 2027 года правило у заданий 26 и 27 одно и то же: оба ответа — строка из двух чисел, и оба оцениваются по числам, а не по строкам. Прежнее правило 27 говорило про «пары» (строка таблицы = два числа одного файла) и не давало балла за одно верное число из двух; теперь такого различия нет.

Отсюда практический вывод: даже если вы уверены только в одном из двух чисел, второе всё равно стоит записать — правильно поставленное первое число само по себе даёт 1 балл. Пустая ячейка ответа не наказывается сильнее неверной.

• Кластер — непустое подмножество точек, которое целиком помещается внутрь прямоугольника заданных размеров H × W. Прямоугольники разных кластеров между собой не пересекаются, и их стороны не обязательно параллельны осям координат — прямоугольник может быть повёрнут.
• Условие гарантирует, что разбиение на N кластеров существует и единственно — можно не сомневаться, что «правильная» кластеризация только одна, и искать её алгоритмом, а не подбирать руками.
• Центр кластера — это не среднее арифметическое координат (центроид), а одна из точек самого кластера с минимальной суммой расстояний до всех остальных его точек. Формально: среди точек кластера {p_1, ..., p_k} центром считается точка p_i, для которой сумма Σ d(p_i, p_j) по всем j ≠ i минимальна.
• Расстояние между точками — обычное евклидово: d(A, B) = √((x2 − x1)² + (y2 − y1)²).
• Условие отдельно гарантирует единственность центра для каждого кластера — при вычислениях с плавающей точкой это избавляет от необходимости обрабатывать «ничью» между двумя точками с одинаковой суммой расстояний.

Раз кластеры не пересекаются и каждый умещается в прямоугольник H × W, то расстояние между двумя точками внутри одного кластера ограничено сверху (не больше диагонали прямоугольника), а между точками из разных кластеров — заметно больше, потому что прямоугольники физически разнесены. Это ровно та структура данных, для которой работает классический приём — кластеризация через минимальное остовное дерево (MST, minimum spanning tree).

Идея по шагам

1. Постройте MST по всем точкам файла: дерево, соединяющее все точки рёбрами так, что сумма длин рёбер минимальна. Для плотного графа это делает алгоритм Прима за O(n²).
2. Отсортируйте рёбра MST по убыванию длины. Самые длинные рёбра — это как раз те, что «случайно» соединили разные кластеры или зацепили аномалию, потому что дерево обязано быть связным и достанет даже до одинокой дальней точки.
3. Удалите K − 1 самых длинных рёбер, где K — общее число кусков, на которое нужно разбить точки (число кластеров плюс число аномалий, если они есть). Дерево распадётся ровно на K компонент связности.
4. Компоненты с наибольшим числом точек — это настоящие кластеры (их ровно N, это число дано в условии). Мелкие компоненты (в демоверсии — из одной точки) — аномалии.

Этот метод называют иерархической кластеризацией методом одиночной связи (single linkage). Он не требует заранее знать форму кластера и хорошо ведёт себя на вытянутых прямоугольниках — в отличие, например, от метода k-средних, который «тянет» центры к сферическим формам и может ошибиться на кластере, вытянутом по диагонали.

Это и есть «очистка и оценка качества данных» из формулировки умения — этап, без которого расчёт центров даст неверный результат. В демоверсии файл Б содержит ровно три аномальные точки, о чём прямо сказано в условии: «эти три точки не относятся ни к одному из кластеров, их учитывать не нужно».

На практике аномалии — это одиночные точки, отстоящие от любого кластера дальше, чем размеры прямоугольника H × W. При построении MST они дают самые длинные рёбра дерева (ведь ближайший сосед аномалии — далёкий кластер), поэтому шаг «отрезать самые длинные рёбра» из предыдущего блока автоматически изолирует их в отдельные маленькие компоненты.

Частая ошибка — включить аномалию в ближайший кластер «за компанию». Даже одна лишняя точка сдвигает центр кластера (ведь сумма расстояний пересчитывается по новому, большему набору точек) и меняет ответ во всех связанных ячейках таблицы.

Ниже — полный код на Python: чтение файла, построение MST, разбиение на кластеры и аномалии, поиск центра кластера и финальное округление по правилу «целая часть произведения на 10 000».

import math

def read_points(path):
    points = []
    with open(path) as f:
        for line in f:
            parts = line.split()
            if len(parts) == 2:
                points.append((float(parts[0]), float(parts[1])))
    return points

def dist(a, b):
    return math.hypot(a[0] - b[0], a[1] - b[1])

def build_mst(points):
    n = len(points)
    in_tree = [False] * n
    min_edge = [math.inf] * n
    nearest = [-1] * n
    min_edge[0] = 0
    edges = []
    for _ in range(n):
        u = -1
        for j in range(n):
            if not in_tree[j] and (u == -1 or min_edge[j] < min_edge[u]):
                u = j
        in_tree[u] = True
        if nearest[u] != -1:
            edges.append((min_edge[u], u, nearest[u]))
        for j in range(n):
            if not in_tree[j]:
                d = dist(points[u], points[j])
                if d < min_edge[j]:
                    min_edge[j] = d
                    nearest[j] = u
    return edges

def find(parent, x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

def union(parent, a, b):
    ra, rb = find(parent, a), find(parent, b)
    if ra != rb:
        parent[ra] = rb

def cluster_points(points, k_clusters, n_anomalies=0):
    n = len(points)
    edges = build_mst(points)
    edges.sort(key=lambda e: -e[0])
    cuts = k_clusters + n_anomalies - 1
    parent = list(range(n))
    for _, a, b in edges[cuts:]:
        union(parent, a, b)
    groups = {}
    for i in range(n):
        root = find(parent, i)
        groups.setdefault(root, []).append(points[i])
    by_size = sorted(groups.values(), key=len, reverse=True)
    clusters = by_size[:k_clusters]
    anomalies = [p for g in by_size[k_clusters:] for p in g]
    return clusters, anomalies

def cluster_center(cluster):
    best_point, best_sum = None, math.inf
    for p in cluster:
        s = sum(dist(p, q) for q in cluster)
        if s < best_sum:
            best_sum, best_point = s, p
    return best_point

def scaled_int(value):
    return int(abs(value) * 10000)

Функция build_mst — алгоритм Прима за O(n²): для файла с несколькими сотнями точек он отрабатывает мгновенно; для файлов на тысячи точек (как файл Б в демоверсии, до 10 000 точек по условию) время растёт до нескольких секунд на чистом Python — этого достаточно, ведь отдельного лимита времени на задание 27, кроме общих 3 часов 55 минут на весь экзамен, нет.

До 2025 года задание 27 проверяло другое умение — «создавать собственные программы (20–40 строк) для анализа числовых последовательностей». Условие тоже приходило с двумя файлами (A и Б), но ответом были не четыре числа в таблице, а два числа одной строкой, и задача обычно сводилась к поиску оптимума (минимума или максимума) на большом массиве чисел, где перебор всех вариантов на файле Б заведомо не укладывался во время. Многие сборники и тренажёры, изданные до обновления, до сих пор используют этот тип — на реальном экзамене 2026–2027 годов он не встретится, но техника линейного прохода по массиву с накоплением нужных величин полезна и пригождается в заданиях 24 и 26.

День 1–2: разберитесь с определением центра кластера на маленьких наборах точек (5–10 штук) — считайте суммы расстояний руками и сверяйте с кодом из этой статьи. Обязательно решите пример, где центроид (среднее координат) и правильный центр кластера не совпадают — так вы перестанете путать эти два понятия. День 3–5: напишите и запустите функции dist и cluster_center самостоятельно, не подглядывая в готовый код. День 6–7: потренируйтесь читать формат входного файла — две координаты в строке через пробел.

День 1–3: реализуйте построение минимального остовного дерева (алгоритм Прима) и убедитесь, что оно верно работает на наборе из 10–15 точек с двумя явно разделёнными группами. День 4–5: добавьте отсечение самых длинных рёбер и разделение на кластеры и аномалии — проверьте на наборе с одной-двумя нарочно удалёнными «одинокими» точками. День 6–7: соберите весь конвейер целиком — от чтения файла до таблицы 2×2 — и прогоните на собственных тестовых наборах, для которых заранее известен правильный ответ.

День 1–2: отработайте округление по формуле «целая часть абсолютной величины произведения на 10 000» — на отрицательных координатах и на числах, где эта разница особенно заметна. День 3–4: потренируйтесь безошибочно расставлять четыре числа по ячейкам таблицы — строка 1 всегда файл A, строка 2 всегда файл Б. День 5–7: решайте задание 27 на время (уложитесь в 40 минут, как рекомендует ФИПИ), а также повторите старый тип задания в разделе выше — не для тренировки, а для того, чтобы уверенно отличать его от актуального, если он попадётся в старом сборнике. Проверьте себя в тренажёре на заданиях из банка ФИПИ.