Разделение на кластеры

Как понять, на какие группы делятся точки и где проходят границы?

Построй диаграмму рассеяния — каждая запись файла становится точкой на плоскости — и посмотри на неё. Функцию read_points из подтемы 1 считаем определённой выше в программе.

В табличном редакторе выдели два столбца координат и построй точечную диаграмму. Не линейный график: он соединит точки в порядке строк файла, а порядок строк ничего не говорит о том, какие точки рядом.

В Python можно использовать matplotlib, если эта библиотека доступна в твоей среде:

import matplotlib.pyplot as plt xs = []ys = [] for x, y in points:    xs.append(x)    ys.append(y) plt.scatter(xs, ys, s=3)plt.axis("equal")plt.grid()plt.show()

Здесь scatter рисует отдельные точки, s=3 задаёт небольшой размер маркеров, axis("equal") устанавливает одинаковый масштаб по обеим осям, grid() добавляет сетку, show() показывает рисунок. Одинаковый масштаб важен: иначе круг может выглядеть вытянутым эллипсом, а расстояния по горизонтали и вертикали будут восприниматься неправильно.

Строй рисунок по самому файлу. Картинка в условии может быть только иллюстрацией и не соответствовать данным задания — такое предупреждение прямо встречается в условиях подборки.

После построения рисунка спроси себя:

• Сколько отчётливых групп видно?
• Есть ли между ними пустые полосы?
• Можно ли провести разделяющую прямую?
• Есть ли отдельно стоящие точки?
• Похожи ли группы на компактные облака, дуги, кольца или вытянутые цепочки?

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

Как записать правило, если на рисунке группы разделяет пустая полоса?

Провести по полосе границу и сравнивать с ней координату точки. В файле example27.txt все точки одной группы левее x = 5, а другой — правее:

points = read_points("example27.txt", has_header=True) clusters = [[], []] for point in points:    x, y = point     if x < 5:        clusters[0].append(point)    else:        clusters[1].append(point) print(len(clusters[0]), len(clusters[1]))print(clusters[1])

На диаграмме рассеяния граница видна сразу:

Почему это работает? Мы нашли правило, которое однозначно определяет принадлежность каждой точки: x < 5 — первый кластер, x ≥ 5 — второй.

Число 5 здесь — граница для конкретных данных, а не универсальная константа задания 27. Если группы разделены горизонтально, используется координата y: if y < 8:.

Как разделить три группы, если одной границы мало?

Условия комбинируют цепочкой if / elif / else: выполняется первая истинная проверка, поэтому порядок проверок важен. elif означает «иначе, если». Например:

1. Сначала выделяется нижняя группа: y < 3.
2. Среди оставшихся точек выделяется левая: x < 5.
3. Всё остальное попадает в третью.

Запусти цепочку по шагам на трёх точках и посмотри, какую ветвь проходит каждая:

clusters = [[], [], []] for x, y in [(2, 1), (3, 6), (8, 7)]:    if y < 3:        clusters[0].append((x, y))    elif x < 5:        clusters[1].append((x, y))    else:        clusters[2].append((x, y)) print(clusters)

Для (2, 1) проверка в строке 4 истинна, и до строки 6 дело не доходит. Числа 3 и 5 — границы для этих точек: в другом файле их снова находят по рисунку.

Почему часто удобнее if / elif / else, а не несколько независимых if? При независимых проверках точка может удовлетворить сразу двум условиям:

if x < 5:    clusters[0].append(point) if y < 3:    clusters[1].append(point)

Если у точки одновременно x < 5 и y < 3, она попадёт в оба списка. Цепочка if / elif / else выполняет только одну ветвь. Правильные границы она за тебя не выберет, но гарантирует, что каждая точка попадёт ровно в одну группу.

Что делать с точками, которые не входят ни в один кластер?

Задать области кластеров явно, а всё, что в них не попало, отложить в отдельный список аномалий. Аномалия — запись, которая не относится ни к одному из кластеров. Например, в демоверсии 2026 года сказано, что в файле Б три лишние точки и их нужно исключить.

Привычное последнее else здесь опасно: оно отправит в последний кластер всё, что не подошло раньше, — и аномалии тоже. Поэтому каждую область задают прямоугольником из двух условий через and, а в else остаются только аномалии. Так устроен наш файл 27-2.txt: три кластера и три аномалии.

points = read_points("27-2.txt") clusters = [[], [], []]noise = [] for point in points:    x, y = point     if -8 < x < 0 and 2 < y < 10:        clusters[0].append(point)    elif 1 < x < 10 and 2 < y < 10:        clusters[1].append(point)    elif -2 < x < 5 and -7 < y < 1:        clusters[2].append(point)    else:        noise.append(point) for cluster in clusters:    print("Размер:", len(cluster)) print("Аномалий:", len(noise))print(sum(len(c) for c in clusters) + len(noise), len(points))

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

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

Как разделить группы, если пустая полоса между ними идёт наискосок?

Провести наклонную прямую и сравнить y точки с высотой прямой при том же x. Пусть группы разделяет прямая y = 2x + 1. Точки выше неё удовлетворяют условию y > 2x + 1, а ниже — y < 2x + 1:

if y < 2 * x + 1:    clusters[0].append(point)else:    clusters[1].append(point)

Чтобы понять проверку, возьми конкретное x. Выражение 2*x + 1 вычисляет высоту прямой при этом x. Затем программа сравнивает с ней высоту точки.

Как разделить точки, если кластеры лежат в треугольниках, которые образуют две наклонные прямые и оси координат?

Треугольник между прямыми — это несколько условий «по какую сторону прямой лежит точка», соединённых через and. В файле 27-8.txt прямые y = x и y = 10 − x вместе с осями ограничивают два треугольника — это кластеры. Точки вне треугольников — аномалии:

Обе области лежат правее оси y, выше оси x и ниже прямой y = 10 − x. Внутри этого большого треугольника их делит прямая y = x:

points = read_points("27-8.txt")clusters = [[], []]noise = [] for x, y in points:    if x > 0 and y > 0 and y < 10 - x:        if y < x:            clusters[0].append((x, y))        else:            clusters[1].append((x, y))    else:        noise.append((x, y)) print(len(clusters[0]), len(clusters[1]), len(noise))

Проверим на точке (6; 2): 6 > 0, 2 > 0 и 2 < 10 − 6 = 4 — она внутри большого треугольника, а 2 < 6 — значит, в нижнем. Точка (7; 5) не проходит третью проверку: 5 < 3 — ложь, это аномалия.

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

Вычислить по координатам другую величину — расстояние до точки или угол направления — и делить по ней.

Например, группы могут располагаться в разных кольцевых областях вокруг известной точки C = (x₀; y₀). Тогда вычисляем расстояние до неё, r = √((x − x₀)² + (y − y₀)²), и разделяем точки по диапазонам r:

r = dist(point, (x0, y0)) if r < 3:    ...elif r < 7:    ...else:    ...

Границы опять выбираются по конкретным данным. Здесь точка C, относительно которой расположены кольца, не обязана быть тем «центром кластера», который затем требуется найти по сумме расстояний. У этих точек разное назначение.

Если группы лежат в разных секторах, разделяющим признаком может быть направление от известной точки C. Сектор можно представить как кусок круга между двумя лучами. Для точки, не совпадающей с C, угол направления вычисляется так:

from math import atan2, degrees angle = degrees(atan2(y - y0, x - x0))angle = angle % 360

Здесь atan2 определяет угол направления с учётом обеих координат; degrees переводит его из радиан в градусы; % 360 приводит угол к диапазону от 0 включительно до 360 не включительно. Направление вправо соответствует 0°, вверх — 90°, влево — 180°.

Почему лучше не использовать обычное деление (y-y0)/(x-x0)? У противоположных направлений оно одинаковое: точки (1; 1) и (−1; −1) от начала координат дают одно и то же отношение 1. А на вертикальном луче получается деление на ноль.

Есть тонкость: направления 359° и 1° очень близки. Их нельзя считать далёкими только потому, что одно число почти 360, а другое почти 0. Чтобы проверить сектор, начинающийся с угла start и имеющий ширину width, удобно написать:

relative_angle = (angle - start) % 360 if relative_angle <= width:    ...

Так выглядит сектор, который переходит через направление 0°:

Не дели угол на ширину сектора автоматически. Из того, что ширина равна 20°, не следует, что границы проходят именно по 0°, 20°, 40° и так далее. Положение секторов тоже нужно установить. В файле 27-5.txt три сектора по 20° вокруг C = (2; −1):

По рисунку и углам крайних точек начала секторов — 350°, 110° и 230°:

from math import atan2, degrees points = read_points("27-5.txt")x0, y0 = 2, -1starts = [350, 110, 230]clusters = [[], [], []] for x, y in points:    angle = degrees(atan2(y - y0, x - x0)) % 360     for k in range(3):        if (angle - starts[k]) % 360 <= 20:            clusters[k].append((x, y)) print([len(c) for c in clusters], len(points))

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

Как разделить частицы из задачи темы, если их координаты тут ни при чём?

Делить по величине, вычисленной по нескольким столбцам строки, — по кинетической энергии. По условию модуль разности энергий любых двух частиц одного кластера не больше R = 2. Посчитаем энергию каждой частицы файла 27-4.txt функцией energy из подтемы 1 и посмотрим на неё так же, как на точки, — только на одной оси:

Без рисунка большие промежутки находит программа: отсортируем энергии и выведем соседние значения, между которыми больше 0,5. Затем делим по границам из этих промежутков. Номер группы частицы — сколько границ её энергия уже превысила:

def energy_groups(particles, bounds):    groups = [[] for _ in range(len(bounds) + 1)]     for p in particles:        k = 0        while k < len(bounds) and energy(p) > bounds[k]:            k += 1        groups[k].append(p)     return groups

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

particles = read_particles("27-4.txt")es = sorted(energy(p) for p in particles) for a, b in zip(es, es[1:]):    if b - a > 0.5:        print(round(a, 3), round(b, 3)) groups = energy_groups(particles, [3.5, 7, 10.5]) for g in groups:    e = [energy(p) for p in g]    print(len(g), round(max(e) - min(e), 3))

zip(es, es[1:]) даёт пары соседних значений отсортированного списка, а включение [[] for _ in …] создаёт нужное число пустых групп (имя _ пишут для переменной, которая не нужна). Ширина каждой группы меньше 2, значит, разбиение подходит под условие.

• Рисунокпо самому файлу, одинаковый масштаб по осям
• Границыцепочка if / elif / else: каждая точка — ровно в одну группу
• Аномалииявные области, остальное — в noise; сверь количество с условием
• Наклонная прямаяподставь x в уравнение и сравни с y
• Угол и расстояниеatan2 и (angle − start) % 360; dist до точки
• Энергиясортировка и большие промежутки; ширина группы ≤ R