Задача 27 ЕГЭ по информатике в 2025 г.: кластеризация

Хотите готовиться со мной к ЕГЭ?
Пишите: ydkras@mail.ru
Немного обо мне

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

Приведем условие задачи (в кратком пересказе по существу).

Есть некоторый набор точек на плоскости (якобы координат звезд), заданных их декартовыми координатами. Требуется разбить эти точки на группы (т.н. кластеры). Кластер - это "местное сгущение", в котором точки находятся близко друг от друга. Между кластерами - промежутки, где точек нет.

Затем нужно найти в каждом кластере так называемй центроид: точку, сумма расстояний от которой до всех остальных точек кластера минимальна. Оставшаяся часть задачи элементарна: найти средние арифметические абсцисс и ординат центроидов и напечать эти средние, умноженные на 10000 (точнее, целые части).

К задаче прилагаются два файла: один (файл A) содержит два кластера и около 1000 точек, другой (файл B) - три кластера и около 10000.

Разобьем эту задачу на этапы и рассмотрим каждый этап.

Этап 0: ввод исходных данных

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

f=open('27.txt')
f.readline()
stars=[list(map(float,s.replace(',','.').split())) for s in f]

Первая строчка в файле с данными может содержать символы X и Y - заголовки столбцов. Строка f.readline() читает эту пер вую строку из файла и не обрабатывает её. Можно также удалить первую строку из файла текстовым редактором. Тогда строка f.readline() в программе будет не нужна.

Этап 1: кластеризация

Полученный список необходимо разбить на несколько списков - по числу кластеров.

Вообще задача кластеризации - достаточно сложная, чисто программными средствами её вряд ли нужно решать. Куда проще "посмотреть на карту" и определить границы кластеров. Для этого нужно открыть файл с координатами точек в экселе и построить диаграмму XY.

Вот как выглядят на диаграммах файлы к демо-варианту задачи 27:

Задача 27A

Задача 27B

По этим картинкам просто определить границы областей, в которых находятся кластеры.

Для файла A это следуюшие интервалы:

-2<x<1, -1<y<3
1<x<5, 3<y<7

А для файла B:

-1<x<3, 0<y<3
2<x<5, 7<y<11
5<x<8, 4<y<7

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

Будем задавать границы кластеров списком, каждый элемент которого - список из четырех чисел: [xmin, xmax, ymin, ymax].

borders=[[-2,1,-1,3],[1,5,3,7]] # для файла A

либо

borders=[[-1,3,0,3],[2,5,7,11],[5,8,4,7]] # для файла B

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

clusters=[[] for _ in range(len(borders))] # список из len(borders) пустых подсписков

for s in stars:

tf=[b[0]<s[0]<b[1] and b[2]<s[1]<b[3] for b in borders]

if sum(tf)!=1: print('Ошибка кластеризации', s, tf)

clusters[tf.index(True)].append(s)

Вначале создаётся список из пустых подсписков в количестве элементов списка borders. Затем для каждой точки из списка stars проверяется её попадание в тот или иной диапазон координат. На всякий случай проверяется, что точка попала только в один диапазон (выражение sum(tf) - это количество значений True в списке tf), если это не так - печатается сообщение об ошибке. Координаты точки добавляются в соответствующий подсписок.

Этап 2: нахождение центроида

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

Метод достаточно медленный, но для количества точек около 3300 (треть точек в файле B) время расчета приемлемое, несколько секунд.

Вначале для каждой точки строится сумма расстояний до всех остальных точек кластера. Определяется минимальное число в списке сумм. Результат функции = координаты точки, для которой сумма расстояний минимальна.

def centroid(cluster):

sd=[sum([((c1[0]-c2[0])**2+(c1[1]-c2[1])**2)**0.5 for c1 in cluster]) for c2 in cluster]

return cluster[sd.index(min(sd))]

Этап 3: получение результатов

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

Ниже приведен полный текст программы. Она работает как для файла A, так и для файла B. Единственное отличие - это строка, где задается значение переменной borders.

def centroid(cluster):
    sd=[sum([((c1[0]-c2[0])**2+(c1[1]-c2[1])**2)**0.5 for c1 in cluster]) for c2 in cluster]
    return cluster[sd.index(min(sd))]

f=open('27.txt')
f.readline()
stars=[list(map(float,s.replace(',','.').split())) for s in f]
# borders=[[-2,1,-1,3],[1,5,3,7]] # для файла A
borders=[[-1,3,0,3],[2,5,7,11],[5,8,4,7]] # для файла B
clusters=[[] for _ in range(len(borders))] # список из len(borders) пустых подсписков
for s in stars:
    tf=[b[0]<s[0]<b[1] and b[2]<s[1]<b[3] for b in borders]
    if sum(tf)!=1: print('Ошибка кластеризации', s, tf)
    clusters[tf.index(True)].append(s)
centers=[centroid(c) for c in clusters]
answer=[int(sum([c[i] for c in centers])/len(centers)*10000) for i in range(2)]
print(*answer)

В файлах демо-варианта первая строка содержит заголовки столбцов. Чтобы их пропустить, в программе после открытия файла добавлена строка f.readline().

Различные варианты кластеризации

После опубликования демо-варианта 2025 г. различные авторы преисполнились энтузиазма и принялись выдумывать свои варианты задачи 27. Во многих из них кластеры имеют такую форму, что наш метод диапазонов по X и Y применить невозможно. Рассмотрим некоторые из таких задач.

Выпуклые многоугольники

В некоторых задачах границы кластеров не удается задать прямоугольниками, однако можно вписать эти кластеры в какие-то выпуклые многоугольники (треугольники, параллелограммы и т.п.). В таком случае можно проверять, находится ли точка внутри многоугольника или вне его.

Опишем алгоритм такой проверки. Будем брать две соседние вершины, обходя многоугольник по часовой стрелке. Если во всех случаях наша точка окажется "справа по курсу", то она лежит внутри многоугольника.

Чтобы определить, лежит ли точка справа от линии, можно воспользоваться векторным произведением. Допустим, мы движемся от точки A к точке B и нам надо знать, находится ли точка C слева или справа от линии AB. Построим векторы AB и AC и найдём их векторное произведение. Если оно положительно, то точка слева от линии, если отрицательно - то справа.

Вот функция для вычисления векторного произведения векторов AB и AC:

def vpr(a,b,c):

ab=[b[i]-a[i] for i in range(2)]

ac=[c[i]-a[i] for i in range(2)]

return ab[0]*ac[1]-ab[1]*ac[0]

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

def inside(p,contour):

toright=[vpr(contour[i-1],contour[i],p)<0 for i in range(len(contour))]

return all(toright)

Здесь использована особенность индексации в питоне: индекс [-1] обозначает последний элемент списка. Таким образом, при i, равном 0, мы имеем вектор от последней точки контура к первой.

Приведем программу для решения задачи из демо-варианта 2025 г. с использованием контуров.

Вершины контуров задаются так:

contours=[[(-2,-1),(-2,3),(1,3),(1,-1)],[(1,3),(1,7),(5,7),(5,3)]] # Для файла A
contours=[[(-1,0),(-1,3),(3,3),(3,0)],[(2,7)(2,11)(5,11)(5,7)],[(5,4),(5,7),(8,7),(8,4)]] # Для файла B

Вот полный текст программы:

def vpr(a,b,c):
    ab=[b[i]-a[i] for i in range(2)]
    ac=[c[i]-a[i] for i in range(2)]
    return ab[0]*ac[1]-ab[1]*ac[0]

def inside(p,contour):
    toright=[vpr(contour[i-1],contour[i],p)<0 for i in range(len(contour))]
    return all(toright)

def centroid(cluster):
    sd=[sum([((c1[0]-c2[0])**2+(c1[1]-c2[1])**2)**0.5 for c1 in cluster]) for c2 in cluster]
    return cluster[sd.index(min(sd))]

f=open('27.txt')
f.readline()
stars=[list(map(float,s.replace(',','.').split())) for s in f]
# contours=[[(-2,-1),(-2,3),(1,3),(1,-1)],[(1,3),(1,7),(5,7),(5,3)]] # Для файла A
contours=[[(-1,0),(-1,3),(3,3),(3,0)],[(2,7),(2,11),(5,11),(5,7)],[(5,4),(5,7),(8,7),(8,4)]] # Для файла B
clusters=[[] for _ in range(len(contours))] # список из len(contouts) пустых подсписков
for s in stars:
    tf=[inside(s,c) for c in contours]
    if sum(tf)!=1: print('Ошибка кластеризации', s, tf)
    clusters[tf.index(True)].append(s)
centers=[centroid(c) for c in clusters]
answer=[int(sum([c[i] for c in centers])/len(centers)*10000) for i in range(2)]
print(*answer)

Точки в списках contours - это вершины прямоугольников, которые являются границами кластеров в предыдущем решении. Но границей области может быть любой выпуклый многоугольник. Напомню, что вершины в списке должны быть в порядке, соответствующем обходу по часовой стрелке.

Полярные координаты

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

В Excel/LibreOffice Calc можно преобразовать декартовы координаты в полярные и построить диаграмму для определения границ областей с кластерами.

Предполагается, что мы открыли файл с исходными данными и в столбцах A и B находятся координаты точек (соответственно X и Y).

В ячейку C1 нужно занести формулу =КОРЕНЬ(A1^2+B1^2), а в ячейку D1 - формулу =ATAN2(A1;B1)*180/ПИ(). Первая формула вычисляет радиус точки, а вторая - угол в градусах в диапазоне (-180; +180).

После этого следует размножить эти формулы вниз и построить по содержимому столбцов C и D диаграмму X-Y, По этой диаграмме можно определить границы кластеров в полярных координатах.

Приведем функцию на питоне для преобразования декартовых координат в полярные.

def d2p(p):

return (math.sqrt(p[0]**2+p[1]**2),math.degrees(math.atan2(p[1],p[0])))

Необходимо импортировать модуль math.

Входной параметр - список или кортеж из координат X и Y. Функция возвращает кортеж из радиуса и угла точки (угол в градусах в диапазоне от -180 до +180).

Заметьте, что в функции ATAN2 в Excel/LibreOffice Calc первый параметр - координата X, а второй - координата Y. В функции atan2 в питоне всё наоборот: первый параметр - Y, а второй - X.

Невыпуклые многоугольники

Невыпуклые многоугольники - случай достаточно сложный. Опишем идею алгоритма.

Будем переходить последовательно от одной вершины многоугольника к другой и вычислять угол поворота прямой, соединяющей нашу точку с вершинами. Если при обходе всех вершин угол равен нулю (с точностью до ошибок вычислений), то точка находится вне многоугольника, если 360 (или -360) градусов - то внутри.

Позже я, возможно, приведу соответствующую функцию. А пока выражу надежду, что столь мерзкий случай вряд ли попадётся вам на экзамене.

Поиск по этому блогу

Информатика, ЕГЭ, Питон и т.п.