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

Задание 27 — высокий уровень, максимум 2 балла. По спецификации это последовательность шагов анализа данных: собрать данные, оценить качество, выбрать модель, преобразовать, при необходимости увидеть структуру, интерпретировать. В актуальных вариантах это кластеры точек на плоскости, часто «звёзды».

Файл 2026 — `.txt`. Обычно два файла: A — маленький, для отладки, B — большой, с тем же правилом и большим числом кластеров. Формат строки читайте в условии: иногда только x и y, иногда после координат есть классы светимости и лишние поля.

Оценка:

• 2 балла — обе строки ответа верны, пары чисел в правильном порядке;
• 1 балл — верна только одна пара, либо обе пары верны, но строки переставлены;
• 0 — иначе.

В бланк вводят числа, не программу.

Что такое центр

Не подставляйте среднее арифметическое координат, пока не прочитаете определение. В нынешних формулировках центр кластера часто одна из точек этого кластера: та, у которой сумма расстояний до остальных точек кластера минимальна. Её обещают единственной.

Иногда после нахождения центров просят не координаты, а расстояние между центрами, число точек в полуплоскости, среднее центров, целую часть от координаты, умноженной на 10 000. Пишите ровно ту формулу, которая в условии. int(x * 10000) отбрасывает дробную часть и не округляет. Если x отрицательный, в Python int отбрасывает к нулю, а в условии может быть «целая часть» как округление к минус бесконечности. Для положительных координат это совпадает. Не округляйте через round.

Расстояние — обычное евклидово, если не сказано «по оси абсцисс». Расстояние по оси абсцисс — модуль разности x, без квадратного корня по двум координатам.

Конспект

1. Разберите строку так, как она устроена. Два первых числа — координаты. Дальше могут идти пометки. Пропуск строки-мусора лучше сделать явно, чем поймать ошибку на середине файла B.

2. Файл A визуально кластеризуется даже без графика: напечатайте минимум и максимум x и y, посмотрите группы. На экзамене matplotlib может не быть, на него не опирайтесь.

3. Кластеры в этих задачах разделены пространством. Достаточно порога: две точки в одном кластере, если между ними расстояние меньше порога, и дальше по цепочке. Порог возьмите меньше зазора между облаками и больше диаметра облака. На файле A подберите его за минуту, глядя на разброс.

4. Число кластеров должно совпасть с условием. Если получилось больше или меньше, порог неверный, файл B не запускайте.

5. Для каждого кластера найдите центр по определению из условия. Для «точка с минимальной суммой расстояний» переберите точки кластера. Кластеры на файле B бывают по несколько тысяч точек, квадрат по кластеру допустим, квадрат по всему файлу — уже тяжело, поэтому сначала режьте на кластеры.

6. Аномалии. Если условие говорит отбросить выбросы или точки вне полос, сделайте это до центра. Иначе центр уедет.

7. Посчитайте две величины для файла A, сверьте с ручной оценкой, затем тот же код — на файле B. Не меняйте формулу между файлами, меняется только число кластеров и данные.

Альтернатива порогу: если кластеры явно разделены по x, отсортируйте по x и режьте в больших зазорах. Это быстрее, но ломается, если облака стоят друг над другом. Порог по полному расстоянию универсальнее.

Старый тип задания 27 — числовая последовательность и два указателя — всё ещё встречается в открытом банке. Если в условии не точки, а последовательность и «подпоследовательность с суммой», не применяйте кластеры. Сначала определите модель.

Шаблон на Python

def read_points(path):
    pts = []
    for line in open(path, encoding="utf-8"):
        parts = line.replace(",", ".").split()
        if len(parts) < 2:
            continue
        try:
            pts.append((float(parts[0]), float(parts[1])))
        except ValueError:
            continue
    return pts

def clusters(pts, eps):
    n = len(pts)
    used = [False] * n
    groups = []
    for i in range(n):
        if used[i]:
            continue
        stack = [i]
        used[i] = True
        group = []
        while stack:
            v = stack.pop()
            group.append(pts[v])
            x1, y1 = pts[v]
            for u in range(n):
                if used[u]:
                    continue
                x2, y2 = pts[u]
                if (x1 - x2) ** 2 + (y1 - y2) ** 2 <= eps * eps:
                    used[u] = True
                    stack.append(u)
        groups.append(group)
    return groups

def center(group):
    best = None
    best_sum = None
    for x1, y1 in group:
        s = 0.0
        for x2, y2 in group:
            s += ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
        if best_sum is None or s < best_sum:
            best_sum = s
            best = (x1, y1)
    return best

pts = read_points("27_A.txt")
groups = clusters(pts, eps=1.0)
print("кластеров:", len(groups), "размеры:", [len(g) for g in groups])
centers = [center(g) for g in groups]
print(centers)
# дальше — формула из условия, например целая часть среднего x * 10000
# px = sum(c[0] for c in centers) / len(centers)
# print(int(px * 10000))

Порог eps подберите на файле A. Если кластеров больше, чем обещано, увеличьте порог. Если один кластер поглотил два облака, уменьшите.

Когда центр определён как среднее, замените функцию center: среднее x и среднее y, это уже не точка из файла. Не смешивайте два определения в одной сдаче.

Производительность: поиск соседей в шаблоне квадратичный. Для файла A это незаметно. Для файла B при десятках тысяч точек может быть тесно по времени. Тогда группируйте сеткой: в список соседей попадают только точки близких ячеек. Пока файл до нескольких тысяч, прямой порог достаточен.

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

• Центр заменён на среднее, хотя нужна точка кластера с минимальной суммой расстояний.
• В кластер попали выбросы, центр сместился.
• Для файла B остался порог, который на A случайно дал 2 кластера, а на B склеивает области.
• В ответ попали координаты, хотя просили расстояние между центрами.
• Целая часть заменена округлением.
• Строки A и B переставлены. Это может оставить 1 балл, если обе пары сами по себе верны.