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

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

Алгоритм k-средних

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

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

Для решения заданий ЕГЭ нам предстоит несколько модернизировать алгоритм, написанный нами ранее. Суть в том, что в оригинальном k-средних используются центроиды, а в 27 заданиях нам чаще всего предстоит работать с медоидами кластеров.

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

Как обычно, далее мы рассмотрим одну из формулировок задания 27 и на примере решения этого задания будем выводить наш алгоритм. А для закрепления решим еще одно задание этим же способом. Также мы научимся визуализировать результаты кластеризации с помощью встроенного в Python модуля turtle.

Кластеризация методом k-средних

Начнём с такой формулировки:

Задание 2703

«Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на 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=6, W=6 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 100.

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

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

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

В 27 задании без визуализации никуда. Открываем редактор электронных таблиц, переносим данные из файла А и строим точечную диаграмму.

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

Да, звучит слегка запутанно, но на деле суть проста: в оригинальном k-средних мы случайным образом выбираем центроиды и сдвигаем их в центр кластера, в заданиях ЕГЭ мы сами подбираем такие точки, которые потом «сдвинутся» в точку-медоиду кластера.

Зачем их подбирать? Чтобы не возникло ситуации, когда обе точки окажутся в неудачных координатах и неправильно разобьют данные на кластеры. Об этом мы как раз говорили в статье про алгоритм k-средних.

Так что в 27 заданиях ЕГЭ мы специально выбираем точки, максимально удалённые друг от друга и вместе с тем максимально близкие к предполагаемому медоиду своего кластера.

Переходим от слов к делу. Логично предположить, что для первого (левого нижнего) кластера можно взять точку с координатами (-9, -2), назовём её А. Для второго – (-1, 15), её назовём B. Отметим их на диаграмме.

Теперь мы будем уверены, что алгоритм k-средних с такими начальными точками правильно кластеризует наши данные.

Переходим к написанию кода. За основу мы возьмём уже написанный ранее код с нашей ручной реализацией этого алгоритма в Python.

Сначала импортируем функцию dist() из модуля math, чтобы не писать свою функцию вычисления евклидова расстояния. Далее считываем данные из файла А и формируем из них список data.

from math import dist

with open('2703_A.txt') as file:
    next(file)
    data = [list(map(float, line.split())) for line in file]

В функции assign_clusters() мы назначали точки ближайшему кластеру. Её мы оставляем без изменений, разве что вторую и третью строчку цикла объединим в одну.

def assign_clusters(data, centers):
    labels = []
    for p in data:
        distances = [dist(p, center) for center in centers]
        labels.append(distances.index(min(distances)))
    return labels

Следующая функция у нас называлась update_centers() и отвечала за поиск нового места для центроида. Её нам предстоит немного поправить: теперь нам нужно искать не какую-то абстрактную «центральную» точку, а среди реальных точек найти ту, сумма расстояний от которой до всех остальных точек кластера минимальна.

Начало функции оставим прежним:

def update_centers(data, labels, k):
    new_centers = []
    for cluster_label in range(k):
        cluster = [point for point, label in zip(data, labels) if labels == cluster_label]

Дальше идёт вычисление медоиды для текущего кластера. Выражение для вычисления медоиды мы уже знаем с прошлой части, выглядит оно так:

medoid = min(cluster, key=lambda p: sum(dist(p, q) for q in cluster))

Осталось лишь добавить все медоиды в список new_centers и вернуть этот список из функции. Полный код функции update_centers() будет таким:

def update_centers(data, labels, k):
    new_centers = []
    for cluster_label in range(k):
        cluster = [point for point, label in zip(data, labels) if labels == cluster_label]
        medoid = min(cluster, key=lambda p: sum(dist(p, q) for q in cluster))
        new_centers.append(medoid)
    return new_centers

Теперь реализуем последнюю функцию – k_means(). В ней мы должны создать список с начальными точками, которые выбрали ранее.

def k_means(data, k):
    centers = [[-9, -2], [-1, 15]]

Далее создаём пустой список new_centres, в котором впоследствии и будут находиться наши медоиды. Затем запускаем цикл while с условием неравенства значений new_centers и centers. То есть будем выполнять какие-либо действия, пока значения этих переменных не совпадут.

new_centers = []
while new_centers != centers:

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

labels = assign_clusters(data, centers)
new_centers = update_centers(data, labels, k)
centers = new_centers

Из функции будем возвращать значения labels и centers. Для решения задачи нужны будут только значения из centers. Данные из labels мы будем использовать для визуализации точек на диаграмме с помощью Черепахи.

Полный код функции k_means() будет таким:

def k_means(data, k):
    centers = [[-9, -2], [-1, 15]]
    new_centers = []
    while new_centers != centers:
        labels = assign_clusters(data, centers)
        new_centers = update_centers(data, labels, k)
        centers = new_centers
    return labels, centers

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

labels, centers = k_means(data, 2)

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

Для этого импортируем модуль turtle и создаём функцию draw_scatter(). Подробно разбирать её не будем, в ней Черепаха просто телепортируется к каждой точке из набора данных и отмечает её цветом соответствующего кластера. Выглядит эта функция так:

def draw_scatter(data, labels):
    turtle.screensize(2000, 2000)
    turtle.tracer(0)
    scale = 50
    colors = ["#F76D47", "#A7D380", "#79CFD4"]
    for point, label in zip(data, labels):
        turtle.teleport(point[0] * scale, point[1] * scale)
        turtle.dot(16, colors[label])
    turtle.update()
    turtle.done()

Вызываем её и видим на экране такую точечную диаграмму.

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

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

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

from math import dist
import turtle

with open('2703_A.txt') as file:
    next(file)
    data = [list(map(float, line.split())) for line in file]

def assign_clusters(data, centers):
    labels = []
    for p in data:
        distances = [dist(p, center) for center in centers]
        labels.append(distances.index(min(distances)))
    return labels


def update_centers(data, labels, k):
    new_centers = []
    for cluster_label in range(k):
        cluster = [p for p, l in zip(data, labels)
                   if l == cluster_label]
        medoid = min(cluster, key=lambda p:
        sum(dist(p, q) for q in cluster))
        new_centers.append(medoid)
    return new_centers


def k_means(data, k):
    centers = [[-9, -2], [-1, 15]]
    new_centers = []
    while new_centers != centers:
        labels = assign_clusters(data, centers)
        new_centers = update_centers(data, labels, k)
        centers = new_centers
    return labels, centers


labels, centers = k_means(data, 2)


def draw_scatter(data, labels):
    turtle.screensize(2000, 2000)
    turtle.tracer(0)
    scale = 50
    colors = ["#F76D47", "#A7D380", "#79CFD4"]
    for point, label in zip(data, labels):
        turtle.teleport(point[0] * scale, point[1] * scale)
        turtle.dot(16, colors[label])
    turtle.update()
    turtle.done()


draw_scatter(data, labels)

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

print(abs(int(px * 10_000)), abs(int(py * 10_000)))

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

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

Начальные точки выберем такими:

Точка с координатами (-4, 1)
Точка с координатами (4, 4)
Точка с координатами (5, 10)

Единственные отличия в решении этого файла от прошлого коснутся функции k_means():

Обновим значения списка centers: centers = [[-4, 1], [4, 4], [5, 10]]
При вызове функции укажем k=3 (три кластера): labels, centers = k_means(data, 3)

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

from math import dist
import turtle

with open('2703_B.txt') as file:
    next(file)
    data = [list(map(float, line.split())) for line in file]

def assign_clusters(data, centers):
    labels = []
    for p in data:
        distances = [dist(p, center) for center in centers]
        labels.append(distances.index(min(distances)))
    return labels


def update_centers(data, labels, k):
    new_centers = []
    for cluster_label in range(k):
        cluster = [p for p, l in zip(data, labels)
                   if l == cluster_label]
        medoid = min(cluster, key=lambda p:
        sum(dist(p, q) for q in cluster))
        new_centers.append(medoid)
    return new_centers


def k_means(data, k):
    centers = [[-4, 1], [4, 4], [5, 10]]
    new_centers = []
    while new_centers != centers:
        labels = assign_clusters(data, centers)
        new_centers = update_centers(data, labels, k)
        centers = new_centers
    return labels, centers


labels, centers = k_means(data, 3)


def draw_scatter(data, labels):
    turtle.screensize(2000, 2000)
    turtle.tracer(0)
    scale = 50
    colors = ["#F76D47", "#A7D380", "#79CFD4"]
    for point, label in zip(data, labels):
        turtle.teleport(point[0] * scale, point[1] * scale)
        turtle.dot(16, colors[label])
    turtle.update()
    turtle.done()


draw_scatter(data, labels)

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

print(abs(int(px * 10_000)), abs(int(py * 10_000)))

В результате получаем следующую визуализацию.

И вторую пару чисел для ответа на это задание: 14271 54727.

Пример

Разберем еще одно задание для закрепления. В этот раз обойдёмся без визуализации и подробно останавливаться на разборе кода не будем.

Задание 2704

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

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

Построим точечную диаграмму для данных из файла А.

В качестве начальных выберем точки с координатами (-5, -7) и (5, 7).

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

from math import dist

with open('2704_A.txt') as file:
    next(file)
    data = [list(map(float, line.split())) for line in file]

def assign_clusters(data, centers):
    labels = []
    for p in data:
        distances = [dist(p, center) for center in centers]
        labels.append(distances.index(min(distances)))
    return labels


def update_centers(data, labels, k):
    new_centers = []
    for cluster_label in range(k):
        cluster = [p for p, l in zip(data, labels)
                   if l == cluster_label]
        medoid = min(cluster, key=lambda p:
        sum(dist(p, q) for q in cluster))
        new_centers.append(medoid)
    return new_centers


def k_means(data, k):
    centers = [[-5, -7], [5, 7]]
    new_centers = []
    while new_centers != centers:
        labels = assign_clusters(data, centers)
        new_centers = update_centers(data, labels, k)
        centers = new_centers
    return labels, centers


labels, centers = k_means(data, 2)


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

print(abs(int(px * 10_000)), abs(int(py * 10_000)))

В результате получаем числа 10592 и 6300.

Теперь второй файл. Данные из него выглядят следующим образом.

В качестве начальных выберем точки со следующими координатами: (-11, -5), (3, -11) и (3, 3). А код будет выглядеть так:

from math import dist

with open('2704_B.txt') as file:
    next(file)
    data = [list(map(float, line.split())) for line in file]

def assign_clusters(data, centers):
    labels = []
    for p in data:
        distances = [dist(p, center) for center in centers]
        labels.append(distances.index(min(distances)))
    return labels


def update_centers(data, labels, k):
    new_centers = []
    for cluster_label in range(k):
        cluster = [p for p, l in zip(data, labels)
                   if l == cluster_label]
        medoid = min(cluster, key=lambda p:
        sum(dist(p, q) for q in cluster))
        new_centers.append(medoid)
    return new_centers


def k_means(data, k):
    centers = [[-11, -5], [3, -11], [3, 3]]
    new_centers = []
    while new_centers != centers:
        labels = assign_clusters(data, centers)
        new_centers = update_centers(data, labels, k)
        centers = new_centers
    return labels, centers


labels, centers = k_means(data, 3)


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

print(abs(int(px * 10_000)), abs(int(py * 10_000)))

И мы получили вторую пару ответов к этому заданию: 15981 37287.

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

<<< Предыдущая часть

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