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

Последнее задание экзамена — задача анализа данных. В файле записаны координаты точек на плоскости (например, звёзд на снимке или датчиков на карте). Точки образуют несколько кластеров — групп близко расположенных точек, далеко отстоящих от других групп. Для каждого кластера нужно найти центр, а затем по центрам вычислить ответ. Обычно даны два файла: в файле A точек немного и кластеров два, в файле B точек значительно больше и кластеров три или больше; за каждый файл начисляется свой первичный балл. Задание считается самым сложным в варианте, но его вполне можно решить, если заранее подготовить шаблон программы.

Что проверяет задание

• чтение числовых данных из файла (координаты — дробные числа, иногда с запятой вместо точки);
• умение разбить множество точек на кластеры по расстоянию;
• вычисление евклидова расстояния между точками: корень из суммы квадратов разностей координат;
• поиск центра кластера по определению из условия и аккуратное вычисление ответа (среднее, умножение на 10 000, целая часть).

Типичные формулировки

1. «Центр кластера — точка этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Найдите Px — среднее арифметическое абсцисс центров кластеров и Py — среднее арифметическое их ординат. В ответе запишите целые части произведений Px × 10 000 и Py × 10 000».
2. Вариант с аномалиями: в файле есть отдельные точки, не входящие ни в один кластер; их нужно отбросить.
3. Вариант, где центр выбирается по другому правилу: точка, для которой максимальное расстояние до остальных точек кластера минимально.
4. Вместо средних просят координаты центра самого большого кластера или расстояние между центрами.

Главное — дословно применить определение центра из условия: центр всегда одна из точек кластера, а не среднее координат.

Пошаговый метод

1. Прочитайте точки в список пар (x, y); при необходимости замените запятые на точки.
2. Посмотрите на данные. Удобно построить точечную диаграмму в электронной таблице: кластеры видны сразу, и становится понятно, на каком расстоянии они друг от друга.
3. Разбейте на кластеры. Надёжный способ — обход: берём непосещённую точку, добавляем к её кластеру все точки ближе порога R, затем все точки, близкие к добавленным, и так далее. Порог выбирают меньше расстояния между кластерами и больше расстояния между соседними точками внутри кластера. Если кластеры хорошо разделены прямыми, можно просто распределить точки по условиям на координаты.
4. Найдите центр каждого кластера перебором: для каждой точки посчитайте сумму расстояний до остальных точек кластера и выберите точку с минимальной суммой.
5. Посчитайте ответ по формуле из условия и возьмите целую часть функцией int.

Разбор примера

Дан «файл» из 11 точек (на экзамене точек будут сотни и тысячи):

Точки, находящиеся на расстоянии меньше 1 друг от друга, относятся к одному кластеру. Центр кластера — точка с минимальной суммой расстояний до остальных точек кластера. Найдите целые части чисел Px × 10 000 и Py × 10 000, где Px и Py — средние значения абсцисс и ординат центров.

Шаг 1. Кластеры. Получаются две группы: пять точек около (1,1; 1,3) и шесть точек около (6,2; 4,2). Внутри групп соседние точки ближе 1, а между группами расстояние больше 4.

Шаг 2. Центр первого кластера. Суммы расстояний (округлённо): для (0,5; 1,2) — 3,594; для (1,1; 0,8) — 3,139; для (1,4; 1,5) — 2,889; для (0,9; 1,9) — 3,705; для (1,6; 1,0) — 3,335. Минимум у точки (1,4; 1,5).

Шаг 3. Центр второго кластера. Суммы: (5,6; 4,1) — 4,526; (6,3; 3,7) — 4,126; (6,0; 4,6) — 4,171; (6,8; 4,2) — 4,707; (5,9; 3,5) — 4,886; (6,5; 4,9) — 5,289. Минимум у точки (6,3; 3,7). Обратите внимание, что две суммы отличаются меньше чем на 0,05: вручную легко ошибиться, поэтому центр всегда ищут программой.

Шаг 4. Ответ. Px = (1,4 + 6,3) / 2 = 3,85, Py = (1,5 + 3,7) / 2 = 2,6. Целые части: 38 500 и 26 000.

Ответ: 38500 26000.

Код на Python

Шаблон работает для любого числа кластеров. Функция dist из модуля math считает евклидово расстояние.

from math import dist

pts = []
for line in open('27A.txt'):
    x, y = map(float, line.replace(',', '.').split())
    pts.append((x, y))

R = 1.0                                 # порог: подберите по диаграмме
clusters, seen = [], set()
for i in range(len(pts)):
    if i in seen:
        continue
    seen.add(i)
    stack, cl = [i], []
    while stack:                        # обход: собираем всех «соседей соседей»
        j = stack.pop()
        cl.append(pts[j])
        for k in range(len(pts)):
            if k not in seen and dist(pts[j], pts[k]) < R:
                seen.add(k)
                stack.append(k)
    clusters.append(cl)

centres = [min(cl, key=lambda p: sum(dist(p, q) for q in cl)) for cl in clusters]
px = sum(p[0] for p in centres) / len(centres)
py = sum(p[1] for p in centres) / len(centres)
print(int(px * 10000), int(py * 10000))   # 38500 26000 для данных примера

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

Частые ошибки

• Берут в качестве центра среднее координат. По условию центр — одна из точек кластера.
• Слишком большой порог R склеивает кластеры, слишком маленький — дробит один кластер на несколько. Проверяйте количество и размеры кластеров.
• Округляют вместо целой части. Нужна именно целая часть: int(3.84999 * 10000) даёт 38499, а округление даст 38500.
• Забывают про запятые в дробных числах — float('1,5') вызывает ошибку.
• Путают абсциссы и ординаты в ответе: сначала Px, затем Py.
• Не учитывают аномалии в файле B: точки-выбросы не должны влиять на центры.

Потренируйтесь

Решите задания № 27 в банке и задачи с проверкой кода: подготовленный заранее шаблон кластеризации экономит на экзамене 20–30 минут. Вернуться к началу экзамена можно с разбора задания 1: таблица и граф.