Анализ данных: кластеризация

Представь точки на листе бумаги. У каждой есть два числа: положение по горизонтали x и по вертикали y. Пара (2, 3) означает: вправо на 2, вверх на 3. Точки могут образовывать заметные группы. Прежде чем искать их, нужно понять, какие свойства точки даны в файле и какое именно свойство определяет группу.

Одна строка файла называется записью: её числа относятся к одному объекту и должны оставаться вместе. В старых задачах № 27 строка часто содержала только координаты. В проекте демоверсии 2027 года запись о частице длиннее: координаты, горизонтальная и вертикальная составляющие скорости, массу и обозначение типа. Группу определяют по вычисленной энергии, а координаты понадобятся позже для другого вопроса. Проект демоверсии ещё может измениться; здесь мы учимся читать правило конкретного условия, а не угадывать будущий вариант.

В файле могут быть десятичные запятые. Python ожидает в записи дробного числа точку, поэтому replace(",", ".") заменяет запятую перед float(...). Функция float превращает текст в число с дробной частью. split() разделяет строку по пробелам или табуляции. В отличие от примера с заголовком в уроке о задаче 26, здесь количество записей не стоит в первой строке: формат каждого файла всегда нужно читать заново. Открытие и чтение файлов подробно разобраны в уроке «Файлы».

1with open("points.txt", encoding="utf-8") as source:2    points = []3    for line in source:4        parts = line.split()5        x = float(parts[0].replace(",", "."))6        y = float(parts[1].replace(",", "."))7        points.append((x, y))8 9print(points)  # [(0.0, 0.0), (2.0, 0.0), (8.0, 1.0)]

Для запуска создай рядом с программой файл из трёх строк: 0,0 0,0, 2,0 0,0 и 8,0 1,0. Метод append добавляет пару в список. Каждая пара хранится целиком: если отдельно переставить только x, связь с её y потеряется. Списки и их позиции подробнее разобраны в уроке «Списки».

Кластер — группа точек, объединённых правилом из условия. На рисунке две кучки можно увидеть глазами, но программе нужна точная граница. Например, пусть точки с x < 5 относятся к левой группе, а остальные — к правой. Точка с x = 5 попадёт вправо. Прямоугольники, окружности и другие области требуют других проверок; одного универсального теста «точки рядом» нет.

1points = [(0, 0), (2, 0), (5, 0), (8, 1)]2left = []3right = []4for point in points:5    if point[0] < 5:6        left.append(point)7    else:8        right.append(point)9 10print(left)   # [(0, 0), (2, 0)]11print(right)  # [(5, 0), (8, 1)]

Иногда задача просит найти «центр» кластера. Нельзя автоматически подставлять среднее координат: условие может требовать выбрать одну из исходных точек. Представим три точки на прямой: (0, 0), (2, 0), (5, 0). Суммы расстояний от них до всей тройки равны 7, 5 и 8. Лучший кандидат — (2, 0), а не среднее координат (7/3, 0), которого вообще нет среди точек.

Расстояние между точками (x₁, y₁) и (x₂, y₂) на плоскости равно квадратному корню из суммы квадратов разностей координат. Такое расстояние называют евклидовым. В коде ** 0.5 берёт квадратный корень. Ниже мы намеренно проверяем каждого кандидата: на трёх точках такой прямой способ легко сверить вручную. В других условиях может использоваться иная мера близости; правило центра нужно читать буквально.

1points = [(0, 0), (2, 0), (5, 0)]2for candidate in points:3    total = 04    for other in points:5        dx = candidate[0] - other[0]6        dy = candidate[1] - other[1]7        total += (dx * dx + dy * dy) ** 0.58    print(candidate, total)9# (0, 0) 7.010# (2, 0) 5.011# (5, 0) 8.0

В проекте демоверсии 2027 года близость частиц определяется не расстоянием на рисунке. Сначала для каждой частицы вычисляют кинетическую энергию по массе и двум составляющим скорости: E = m × (Vx² + Vy²) / 2. Здесь масса m, а Vx и Vy показывают скорость в двух направлениях. Если m = 2, Vx = 1 и Vy = 0, энергия равна 1. Координаты при этом не участвуют в вычислении энергии.

В каждой строке ниже шесть полей: x, y, Vx, Vy, m и обозначение типа. Текстовый тип оставляем строкой. Числовые поля переводим через float после замены десятичной запятой. Полученную энергию кладём рядом с остальными полями той же частицы; при сортировке запись переместится целиком. Сортировка записей по полю подробно разобрана в уроке «Сортировка и поиск».

1lines = [2    "0,0 0,0 1,0 0,0 2,0 II",3    "1,0 0,0 1,0 0,0 3,0 V",4    "8,0 1,0 1,0 0,0 10,0 II",5]6particles = []7for line in lines:8    parts = line.split()9    x = float(parts[0].replace(",", "."))10    y = float(parts[1].replace(",", "."))11    vx = float(parts[2].replace(",", "."))12    vy = float(parts[3].replace(",", "."))13    mass = float(parts[4].replace(",", "."))14    kind = parts[5]15    energy = mass * (vx * vx + vy * vy) / 216    particles.append((energy, x, y, kind))17 18energies = []19for record in particles:20    energies.append(record[0])21print(energies)  # [1.0, 1.5, 5.0]

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

Теперь сформулируем правило группы. Пусть R = 2: разность наибольшей и наименьшей энергий всей группы должна быть не больше 2. После сортировки достаточно сравнивать очередную энергию с первой энергией текущей группы. Только сравнение с соседней не годится: у 1, 2,5 и 4 соседние разности равны 1,5, но между крайними разница 3. Все три в одну группу при R = 2 не входят.

1energies = [15.5, 1.5, 10.0, 6.0, 2.0, 16.0,2            5.0, 11.0, 1.0, 5.5, 10.5, 15.0]3limit = 2.04clusters = []5for energy in sorted(energies):6    if len(clusters) == 0 or energy - clusters[-1][0] > limit:7        clusters.append([energy])8    else:9        clusters[-1].append(energy)10 11print(clusters)12# [[1.0, 1.5, 2.0], [5.0, 5.5, 6.0],13#  [10.0, 10.5, 11.0], [15.0, 15.5, 16.0]]

clusters[-1] — последняя созданная группа, а [0] — её первая, то есть наименьшая энергия. Пустой список проверяем отдельно, чтобы не обращаться к несуществующей группе. При разности ровно 2 частица остаётся в группе: новая начинается только при > limit. В данном примере между группами есть явные разрывы, а число групп совпадает с условием. В задаче, где допустимы несколько разбиений, такой короткий проход сам по себе не доказывает, что найдено требуемое: нужно использовать дополнительные правила.

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

После выделения групп нужно ещё раз прочитать определение центра. Для частиц, сгруппированных по энергии, центр — одна из частиц группы, у которой сумма расстояний по энергии до остальных минимальна. Расстояние по энергии здесь означает abs(E1 - E2): функция abs убирает знак разности. Это не то же расстояние, что между точками на плоскости.

Возьмём энергии 1,0; 1,5; 2,0. Для первой сумма разностей 0 + 0,5 + 1,0 = 1,5. Для средней — 0,5 + 0 + 0,5 = 1,0. Для последней — снова 1,5. Центр — частица с энергией 1,5. Если упорядоченных значений пять, выгоднее всего третье: при движении кандидата к нему число точек справа больше числа точек слева, поэтому общая сумма убывает; после него — растёт. Это среднее по положению в упорядоченном списке значение называют медианой. Оно не обязано равняться арифметическому среднему.

Индексы списка начинаются с нуля. Для трёх энергий середина имеет индекс 3 // 2 = 1; знак // берёт целую часть результата деления. В проекте демоверсии гарантирован единственный центр каждого кластера. Без такой гарантии у группы из чётного числа частиц две средние частицы могут давать одинаковую минимальную сумму. Равенство бывает и при нечётном числе частиц: для энергий 1, 1, 2 суммы разностей равны 1, 1 и 2. Обе частицы с энергией 1 делят минимум. Если условие не обещает единственный центр, нельзя произвольно выбрать одну частицу: нужно искать правило разрешения равенства.

1clusters = [[1.0, 1.5, 2.0], [5.0, 5.5, 6.0]]2for cluster in clusters:3    centre = cluster[len(cluster) // 2]4    total = 05    for energy in cluster:6        total += abs(centre - energy)7    print(centre, total)8# 1.5 1.09# 5.5 1.0

Вторая часть задачи может спрашивать уже не об энергии. Например, найдём наибольшее расстояние между частицами типа II внутри одного кластера. Здесь одновременно действуют два фильтра: тип обеих частиц равен II и кластер у них общий. Координаты нужны только после группировки по энергии. Пара точек из разных кластеров не подходит, даже если расстояние между ними самое большое во всём файле.

Если файл уже указывает имя кластера в каждой строке, записи удобно собрать в словарь: имя служит ключом, а связанное с ним значение — список точек этой группы. Метод values() позволяет перебрать именно эти списки, не обращаясь к именам. Как устроены ключи и значения, подробно объясняет урок «Словари». В нашем примере группы уже собраны в списке, поэтому словарь не требуется.

Для точек с координатами (x₁, y₁) и (x₂, y₂) сначала найдём квадрат расстояния: (x1 - x2)² + (y1 - y2)². Чем больше этот квадрат, тем больше и само расстояние: квадратный корень не меняет порядок неотрицательных чисел. Поэтому внутри циклов достаточно сравнивать квадраты, а корень взять один раз в конце.

1clusters = [2    [(0, 0, "II"), (2, 3, "II"), (20, 20, "V")],3    [(0, 0, "II"), (1, 4, "II"), (30, 30, "III")],4]5best_square = 06for cluster in clusters:7    selected = []8    for point in cluster:9        if point[2] == "II":10            selected.append(point)11    for left in range(len(selected)):12        for right in range(left + 1, len(selected)):13            dx = selected[left][0] - selected[right][0]14            dy = selected[left][1] - selected[right][1]15            square = dx * dx + dy * dy16            if square > best_square:17                best_square = square18 19print(best_square)  # 1720print(int(best_square ** 0.5 * 10000))  # 41231

Внутренний цикл начинается с left + 1, чтобы не сравнивать точку с собой и не считать одну пару дважды. В первой группе квадрат расстояния равен 13, во второй — 17. Далёкие точки другого типа намеренно пропущены. int оставляет целую часть положительного результата после умножения на 10 000: для корня из 17 получается 41231. Это не округление до ближайшего целого.

Если в одной группе после отбора осталось m подходящих точек, цикл сравнит m × (m - 1) / 2 пар. Для 100 точек это 4 950, а для 10 000 — уже 49 995 000. Поэтому сначала отбирай нужный тип и оценивай число сравнений. Однократный корень убирает лишнюю дорогую операцию, но не сокращает число пар. Если после фильтрации их всё ещё слишком много, нужен отдельный более быстрый геометрический алгоритм; нельзя выдавать этот прямой перебор за быстрое решение любого файла.

Соединим шаги на собственном коротком наборе. В каждой записи ниже лежат x, y, Vx, Vy, m и тип. Для наглядности скорость всегда равна (1, 0), поэтому энергия равна половине массы; в файле с иной скоростью программа применит ту же полную формулу. Четыре группы разделены по энергиям при R = 2. В каждой три частицы с разными энергиями, поэтому средняя по энергии частица — единственный центр.

Первое число Q1 — наибольшее расстояние между двумя частицами II одного кластера. Второе Q2 — наибольшая энергия среди четырёх центров. Это независимые расчёты: центр не обязан быть типа II и не участвует автоматически в паре для Q1.

Чтобы получить второе число в программе, сохраним энергии центров в список centre_energies. Вызов max(centre_energies) выбирает из этого списка наибольшее число.

1particles = [2    (0, 0, 1, 0, 2, "II"), (0, 2, 1, 0, 3, "V"),3    (3, 0, 1, 0, 4, "II"),4    (0, 0, 1, 0, 10, "II"), (5, 5, 1, 0, 11, "V"),5    (2, 3, 1, 0, 12, "II"),6    (0, 0, 1, 0, 20, "II"), (20, 20, 1, 0, 21, "III"),7    (1, 4, 1, 0, 22, "II"),8    (0, 0, 1, 0, 30, "II"), (50, 50, 1, 0, 31, "V"),9    (2, 2, 1, 0, 32, "II"),10]11records = []12for x, y, vx, vy, mass, kind in particles:13    energy = mass * (vx * vx + vy * vy) / 214    records.append((energy, x, y, kind))15records = sorted(records, key=lambda record: record[0])16 17clusters = []18for record in records:19    if len(clusters) == 0 or record[0] - clusters[-1][0][0] > 2:20        clusters.append([record])21    else:22        clusters[-1].append(record)23 24centre_energies = []25best_square = 026for cluster in clusters:27    centre = cluster[len(cluster) // 2]28    centre_energies.append(centre[0])29    selected = []30    for record in cluster:31        if record[3] == "II":32            selected.append(record)33    for left in range(len(selected)):34        for right in range(left + 1, len(selected)):35            dx = selected[left][1] - selected[right][1]36            dy = selected[left][2] - selected[right][2]37            square = dx * dx + dy * dy38            if square > best_square:39                best_square = square40 41q1 = best_square ** 0.542q2 = max(centre_energies)43print(int(q1 * 10000), int(q2 * 10000))  # 41231 155000

Строка for x, y, vx, vy, mass, kind in particles раздаёт шесть полей записи шести именам слева по порядку. После добавления энергии запись становится четвёркой (энергия, x, y, тип), поэтому record[0] — энергия, а record[1] и record[2] — координаты. lambda record: record[0] сообщает sorted, по какому полю расположить целые записи; это тот же приём из урока о сортировке.

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

Разные варианты № 27 меняют определение кластера и центра. В предоставленной подборке встречаются и прежние задачи на суммы или произведения пар с ограничением по делимости. Там тоже важно не перебирать огромный файл вслепую, но группировка точек по энергии к ним не применяется. Этот урок подробно учит одному современному семейству и способу проверять условие; для другого семейства потребуется свой вывод алгоритма.

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