Алгоритм решения задания 27 ЕГЭ по информатике. Часть 1

Навигация по странице

О задании

В ЕГЭ по информатике 2025 года задание 27 было кардинально изменено. Если ранее оно было самым трудным во всем экзамене и подразумевало применение методов олимпиадного программирования, то в настоящее время с ним может справиться любой экзаменуемый, просто выучив один из трёх алгоритмов.

Задания 27 теперь нацелены на кластеризацию данных и вычисление параметров кластеров. В данном задании вам даются два файла, которые содержат в каждой строке абсциссу и ординату точки. Эти точки следует разделить на кластеры и вычислить для каждого кластера заданное в условие значение. Обычно в качестве ответа требуется дать среднее арифметическое абсцисс и ординат медоид кластеров (в условии задания они называются «центрами»).

Таким образом, все решение этого задания заключается в трёх шагах:

Прочитать и обработать данные из файла (привести к нужному типу, заменить запятые на точки при необходимости)
Провести кластеризацию данных, то есть разделить все данные на группы по схожим признакам
В получившихся кластерах найти медоиды и вычислить среднее арифметическое по их координатам

Ко всему прочему, если ранее в 27 заданиях были файлы A и Б такие, что решение второго файла необходимо было существенно переделывать и оптимизировать, то в новых заданиях данные в файлах практически ничем не отличаются.

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

Вернёмся к описанным выше шагам. С первым шагом все и так понятно – с файлами мы уже умеем работать. Медоиды всегда ищутся по одному и тому же алгоритму, который описан в условии задания, здесь ничего необычного мы не сможем привнести. Но с алгоритмами кластеризации все куда интереснее.

В 27 заданиях можно применять один из трёх алгоритмов для кластеризации:

Кластеризация через уравнения прямых
Кластеризация методом k-средних
Кластеризация методом DBSCAN

Первый алгоритм самый простой, но не практичный. Он заключается в том, что мы «очерчиваем» каждый кластер прямыми линиями и выводим уравнения этих линий. Тогда в коде проверяем, как по отношению к этим прямым лежит точка на плоскости: ниже или выше, левее или правее. То есть так же, как мы это делали в заданиях 6, когда искали количество точек внутри сложной фигуры (треугольник, шестиугольник и т.д.).

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

Недостатком этого метода является то, что он, как и первый, не может работать с выбросами и кластерами сложной формы, например, серповидными.

Третий метод самый практичный, но вместе с тем и сложный в реализации. Он основан на алгоритме DBSCAN, то есть группирует точки на основе плотности их распределения. Для работы этого алгоритма от вас потребуется только определить минимальный радиус между соседними точками (eps, «эпсилон»). Обычно он подбирается из точечной диаграммы.

Главным преимуществом алгоритма DBSCAN является то, что его можно применять к кластерам любой формы, в том числе имеющим выбросы.

Каждому из этих трёх алгоритмов будет посвящена отдельная часть этой статьи. В данной же части мы подробно рассмотрим метод кластеризации данных через уравнения прямых.

Но перед началом настоятельно рекомендуем вам ознакомиться с прошлыми статьями, где разбирались все основные термины, связанные с кластеризацией и основными методами кластеризации:

Кластеризация через уравнения прямых

Давайте разберём этот алгоритм на примере одного из 27 заданий ЕГЭ.

Задание 2702

«Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x1,y1) и B(x2,y2) вычисляется по формуле:

$d(A, B) = \sqrt{(x_2-x_1)^2 +(y_2-y_1)^2}$

В файле A хранятся данные о звёздах двух кластеров, где H=3, W=3 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 100.

В файле B хранятся данные о звёздах трёх кластеров, где H=3, W=3 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле B аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px – среднее арифметическое абсцисс центров кластеров, и Py – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа: в первой строке сначала абсолютное значение целой части произведения Px ×10 000, затем абсолютное значение целой части произведения Py ×10 000 для файла А, во второй строке – аналогичные данные для файла B»

Сначала разберёмся с новыми для нас терминами. Про кластеры мы уже говорили ранее в этой статье. Теперь поговорим про предложение «будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна».

Под этой фразой скрывается термин из области кластерного анализа – медоида. Медоида — это точка (объект) из исходного набора данных, которая наиболее типична или центральна для данного набора (или кластера).

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

В более математической формулировке, медоида – это элемент множества, который минимизирует сумму расстояний до всех остальных точек этого множества. Иными словами, это точка, суммарное расстояние от которой до всех других точек минимально. Именно такая интерпретация этого термина и приводится в условии задания.

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

Можно сказать, что по этой формуле мы находим длину гипотенузы прямоугольного треугольника, катеты которого параллельны осям абсцисс и ординат, соответственно.

Рассмотрим две точки на плоскости: точку А с координатами (1, 0) и B с координатами (5, 3). Найдём расстояние между этими точками.

Подставляем координаты точек в формулу евклидова расстояния:

$d(A, B) = \sqrt{(5-1)^2 +(3-0)^2} = \sqrt{16+9} = 5$

Таким образом, расстояние между нашими точками A и B равно 5 единицам.

Аналогичные действия можем проделать с помощью Python:

point_A = (1, 0)
point_B = (5, 3)

def euclidean_distance(a, b):
    return ((b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2) ** 0.5

print(euclidean_distance(point_A, point_B))

>>>5.0

Но на экзамене, в целях экономии времени рекомендуем вам пользоваться функцией dist() из встроенного модуля math. Работает она точно так же, как и наша самописная функция:

from math import dist

point_A = (1, 0)
point_B = (5, 3)

print(dist(point_A, point_B))

>>>5.0

Поскольку мы теперь умеем находить расстояние между точками, давайте напишем функцию для поиска медоиды кластера. Назовём функцию get_medoid() и создадим в ней две переменные: min_distance_sum для хранения минимальной суммы расстояний и medoid_point для хранения нужной нам точки-медоиды.

def get_medoid(cluster):
    min_distance_sum = float('inf')
    medoid_point = None

Далее проходимся по каждой точке кластера и вычисляем общую сумму расстояния от этой точки до всех остальных:

for p in cluster:
    total_distance = 0
    for q in cluster:
        total_distance += dist(p, q)

Если эта сумма total_distance будет меньше предыдущей минимальной, то будем обновлять медоиду:

if total_distance < min_distance_sum:
    min_distance_sum = total_distance
    medoid_point = p

После завершения работы цикла будем возвращать значение medoid_point. Вся функция выглядит так:

def get_medoid(cluster):
    min_distance_sum = float('inf')
    medoid_point = None
    for p in cluster:
        total_distance = 0
        for q in cluster:
            total_distance += dist(p, q)
        if total_distance < min_distance_sum:
            min_distance_sum = total_distance
            medoid_point = p

    return medoid_point

Давайте проверим её работу на абстрактном кластере из четырёх точек:

from math import dist

cluster = [(1, 2), (3, 4), (5, 6), (7, 8)]


def get_medoid(cluster):
    min_distance_sum = float('inf')
    medoid_point = None
    for p in cluster:
        total_distance = 0
        for q in cluster:
            total_distance += dist(p, q)
        if total_distance < min_distance_sum:
            min_distance_sum = total_distance
            medoid_point = p

    return medoid_point


print(get_medoid(cluster))

>>>(3, 4)

В результате получаем медоиду нашего кластера – точку с координатами (3, 4). Но не спешите запоминать эту функцию. Её можно написать гораздо более компактно и эффективно – всего в одну строчку.

def get_medoid(cluster):
    return min(cluster, key=lambda p: sum(dist(p, q) for q in cluster))

Дело в том, что функция min() в Python умеет не только находить минимальное значение в списке, но и искать минимальный элемент по какому-то правилу. Здесь это правило задаётся с помощью лямбда-функции: мы также считаем расстояния между точками p и q в кластере, последовательно перебирая каждую.

Точка p перебирается внутри самой функции min(), точка q перебирается в цикле for внутри генераторного выражения sum(dist(p, q) for q in cluster). Это генераторное выражение возвращает сумму расстояний между точками p и q, что аналогично такой записи:

total_distance = 0
        for q in cluster:
            total_distance += dist(p, q)

В итоге мы вместо 10 строчек написали всего одну, полностью сохранив весь функционал. Давайте проверим эту функцию на все тех же данных.

from math import dist

cluster = [(1, 2), (3, 4), (5, 6), (7, 8)]


def get_medoid(cluster):
    return min(cluster, key=lambda p: sum(dist(p, q) for q in cluster))


print(get_medoid(cluster))

Получаем все ту же точку с координатами (3, 4).

Теперь можем смело переходить к кластеризации данных. Для начала нам необходимо визуализировать все точки на диаграмме. Для этого проще всего будет воспользоваться редактором электронных таблиц.

Открываем пустую таблицу и копируем данные из прикреплённых файлов в неё. Начинаем с файла A. Получим такую диаграмму:

Теперь нам надо очертить границы для каждой группы точек. Для левой группы будут такие границы:

Слева: x = -1.9
Справа: x = 1
Снизу: y = 0
Сверху: y = 8

Для правой, соответственно, такие границы:

Слева: x = 1,3
Справа: x = 4,2
Снизу: y = 3,2
Сверху: y = 6,2

Отметим их на изображении.

Конечно, нам такая точность в определении границ не нужна. Более того, чаще всего мы будем поступать куда проще. Например, здесь можно заметить, что кластеры разделяются всего одной прямой x = 1. Точки одного кластера лежат слева от неё, другого – справа.

Это значит, что точки первого кластера будут иметь абсциссу меньше 1, а точки второго – больше 1.

На этом завершим наш короткий анализ данных и приступим к решению задания. Сначала импортируем функцию dist() и напишем функцию для поиска медоиды.

from math import dist


def get_medoid(cluster):
    return min(cluster, key=lambda p: sum(dist(p, q) for q in cluster))

Теперь открываем файл А и пропускаем первую строку функцией next(). Это делаем только в тех файлах, в которых первая строка содержит буквы «X Y», а не численные данные.

with open('2702_A.txt') as file:
    next(file)

Далее создаём списки под каждый кластер и в цикле for построчно считываем файл.

cluster_1 = []
cluster_2 = []
for line in file:

Разделяем числа каждой строки по пробельному символу и приводим к типу float (вещественные числа).

x, y = map(float, line.split())

Если значение переменной x меньше 1, то сохраняем обе координаты в виде кортежа в первый кластер. В противном случае – во второй.

if x < 1:
    cluster_1.append((x, y))
else:
    cluster_2.append((x, y))

Весь код для считывания данных и кластеризации их выглядит так:

with open('2702_A.txt') as file:
    next(file)
    cluster_1 = []
    cluster_2 = []
    for line in file:
        x, y = map(float, line.split())
        if x < 1:
            cluster_1.append((x, y))
        else:
            cluster_2.append((x, y))

Данные мы успешно считали и разделили все точки по кластерам. Теперь переходим к поиску медоиды каждого кластера. Для этого вызываем написанную ранее функцию get_medoid().

medoid_1 = get_medoid(cluster_1)
medoid_2 = get_medoid(cluster_2)

Осталось лишь сформировать ответ. Для этого нам нужно найти среднее арифметическое абсцисс и ординат обоих медоид. На экран будем выводить абсолютное значение полученных чисел, умножая каждое на 10 000.

px = (medoid_1[0] + medoid_2[0]) / 2
py = (medoid_1[1] + medoid_2[1]) / 2
print(abs(int(px * 10_000)), abs(int(py * 10_000)))

Весь код для решения файла А этого задания будет таким:

from math import dist


def get_medoid(cluster):
    return min(cluster, key=lambda p: sum(dist(p, q) for q in cluster))


with open('2702_A.txt') as file:
    next(file)
    cluster_1 = []
    cluster_2 = []
    for line in file:
        x, y = map(float, line.split())
        if x < 1:
            cluster_1.append((x, y))
        else:
            cluster_2.append((x, y))

medoid_1 = get_medoid(cluster_1)
medoid_2 = get_medoid(cluster_2)

px = (medoid_1[0] + medoid_2[0]) / 2
py = (medoid_1[1] + medoid_2[1]) / 2
print(abs(int(px * 10_000)), abs(int(py * 10_000)))

В результате получаем один из двух ответов: 10738 30730.

Осталось адаптировать своё решение для файла Б. Для начала давайте построим точечную диаграмму на основе данных этого файла.

Здесь кластеры отлично разделяются прямыми, параллельными оси абсцисс. Так, точки первого кластера лежат ниже прямой y = 3, точки второго кластера – выше прямой y = 7. Третий кластер (самый правый) можем определить как тот, точки которого лежат между прямыми y = 3 и y = 7. Или просто все оставшиеся точки, не вошедшие в первые два кластера, будем относить к третьему.

В коде это будет реализовано так:

if y < 3:
    cluster_1.append((x, y))
elif y > 7:
    cluster_2.append((x, y))
else:
    cluster_3.append((x, y))

Осталось лишь добавить строку кода для вычисления третьей медоиды и поправить вычисление среднего арифметического. Полный код для решения файла Б будет таким:

from math import dist


def get_medoid(cluster):
    return min(cluster, key=lambda p: sum(dist(p, q) for q in cluster))


with open('2702_B.txt') as file:
    next(file)
    cluster_1 = []
    cluster_2 = []
    cluster_3 = []
    for line in file:
        x, y = map(float, line.split())
        if y < 3:
            cluster_1.append((x, y))
        elif y > 7:
            cluster_2.append((x, y))
        else:
            cluster_3.append((x, y))

medoid_1 = get_medoid(cluster_1)
medoid_2 = get_medoid(cluster_2)
medoid_3 = get_medoid(cluster_3)

px = (medoid_1[0] + medoid_2[0] + medoid_3[0]) / 3
py = (medoid_1[1] + medoid_2[1] + medoid_3[1]) / 3
print(abs(int(px * 10_000)), abs(int(py * 10_000)))

И мы получили второй ответ к данному заданию: 37522 51277.

Пример

Решим еще одно задание этим методом. Формулировка будет такой:

Задание 2701

$d(A, B) = \sqrt{(x_2-x_1)^2 +(y_2-y_1)^2}$

В файле A хранятся данные о звёздах двух кластеров, где H=11, W=11 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 100.

В файле B хранятся данные о звёздах трёх кластеров, где H=13, W=13 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле B аналогична файлу А.

В ответе запишите четыре числа: в первой строке сначала абсолютное значение целой части произведения Px × 10 000, затем абсолютное значение целой части произведения Py × 10 000 для файла А, во второй строке – аналогичные данные для файла B»

Начнём все так же с визуализации данных из файла А.

Здесь кластеры можем разделить прямой y = 0. В таком случае те точки, ордината которых меньше 0 будут отходить первому кластеру, а в противном случае – ко второму.

Код можем использовать тот же самый, что был в прошлом задании. Но давайте немного оптимизируем его. Согласитесь, довольно неудобно писать по несколько строчек для поиска медоиды каждого кластера? Лучше реализуем поиск медоид через списочное вложение, например, так:

medoids = [get_medoid(cluster) for cluster in clusters]

Тогда перед чтением данных из файла создаём список из двух пустых списков, по количеству кластеров (для файла Б будет три пустых списка).

clusters = [[], []]

Далее считываем данные как обычно и в каждый из вложенных списков добавляем соответствующие точки:

with open('2701_A.txt') as file:
    next(file)
    for line in file:
        x, y = map(float, line.split())
        if y < 0:
            clusters[0].append((x, y))
        else:
            clusters[1].append((x, y))

Находим медоиды списочным выражением, написанным выше, а затем через функцию sum() складываем сначала абсциссы, затем ординаты медоид и делим на количество медоид, получая тем самым среднее арифметическое:

px = sum(x for x, y in medoids) / len(medoids)
py = sum(y for x, y in medoids) / len(medoids)

Такая запись более прозрачна, легче читается и убережёт вас от ошибок: не забудете добавить еще одну медоиду для файла Б и не ошибётесь в индексах.

А весь код для решения файла А будет выглядеть так:

from math import dist


def get_medoid(cluster):
    return min(cluster, key=lambda p: sum(dist(p, q) for q in cluster))


clusters = [[], []]
with open('2701_A.txt') as file:
    next(file)
    for line in file:
        x, y = map(float, line.split())
        if y < 0:
            clusters[0].append((x, y))
        else:
            clusters[1].append((x, y))

medoids = [get_medoid(cluster) for cluster in clusters]

px = sum(x for x, y in medoids) / len(medoids)
py = sum(y for x, y in medoids) / len(medoids)
print(abs(int(px * 10_000)), abs(int(py * 10_000)))

На выходе получаем пару чисел: 26216 24182.

Переходим к файлу Б. Также визуализируем точки из него.

Здесь кластеры прекрасно разделяются прямыми x = 10 и x = 20.

Переходим к решению кодом. Не забываем добавить еще один пустой список в clusters:

clusters = [[], [], []]

Считываем данные и распределяем каждую точку в свой список.

with open('2701_B.txt') as file:
    next(file)
    for line in file:
        x, y = map(float, line.split())
        if x < 10:
            clusters[0].append((x, y))
        elif x > 20:
            clusters[1].append((x, y))
        else:
            clusters[2].append((x, y))

На этом все отличия от прошлого кода закончились. Полный код будет выглядеть так:

from math import dist


def get_medoid(cluster):
    return min(cluster, key=lambda p: sum(dist(p, q) for q in cluster))


clusters = [[], [], []]
with open('2701_B.txt') as file:
    next(file)
    for line in file:
        x, y = map(float, line.split())
        if x < 10:
            clusters[0].append((x, y))
        elif x > 20:
            clusters[1].append((x, y))
        else:
            clusters[2].append((x, y))

medoids = [get_medoid(cluster) for cluster in clusters]

px = sum(x for x, y in medoids) / len(medoids)
py = sum(y for x, y in medoids) / len(medoids)
print(abs(int(px * 10_000)), abs(int(py * 10_000)))

После завершения работы программы получаем вторую пару чисел, которую и запишем в ответ к этому заданию: 150891 63754.

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

<<< Последняя часть

Следующая часть >>>