Соседи, другие центры и статистика

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

Соединить точки, которые ближе порога ε, и считать одной группой всё, что связано цепочками таких шагов. Две точки — соседи, если d(A, B) ≤ ε. Возьмём A = (0; 0), B = (0,8; 0), C = (1,6; 0) и ε = 0,9.

Тогда d(A, B) = 0,8 ≤ 0,9 и d(B, C) = 0,8 ≤ 0,9, но d(A, C) = 1,6 > 0,9. Тем не менее все три точки образуют одну связную группу: от A до C можно пройти через B, причём каждый шаг достаточно короткий.

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

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

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

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

Группу растят от любой точки: ищут соседей у каждой добавленной точки, пока новых не останется. Алгоритм построения одной группы:

1. Взять любую ещё не распределённую точку.
2. Найти её нераспределённых соседей.
3. Добавить их в текущую группу.
4. Найти соседей у добавленных точек.
5. Продолжать, пока все точки текущей группы не будут обработаны.

После этого берём следующую нераспределённую точку и начинаем новую группу.

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

from math import dist  def split_clusters(points, eps):    remaining = points.copy()    clusters = []    while remaining:        cluster = [remaining.pop()]        pos = 0        while pos < len(cluster):            point = cluster[pos]            rest = []            for other in remaining:                if dist(point, other) <= eps:                    cluster.append(other)                else:                    rest.append(other)            remaining = rest            pos += 1        clusters.append(cluster)    return clusters

Разберём устройство кода.

• remaining содержит точки, которые ещё не отнесены ни к одной группе. Метод copy() создаёт отдельный список: сам исходный список points мы не будем опустошать.
• while remaining: — цикл продолжается, пока список не пуст.
• cluster = [remaining.pop()]: pop() извлекает последний элемент списка и удаляет его из списка. Эта точка становится первой точкой новой группы.
• pos — номер точки текущей группы, соседей которой мы сейчас будем искать.
• while pos < len(cluster): — размер cluster может увеличиваться по мере работы. Поэтому цикл обработает и исходную точку, и всех добавленных соседей.
• В rest соберём точки, которые пока остались нераспределёнными. Если точка близка к обрабатываемой — cluster.append(other), если нет — rest.append(other).
• После прохода remaining = rest: точки, присоединённые к кластеру, исчезают из списка нераспределённых.
• pos += 1 — переходим к следующей точке растущей группы.

Пройдём алгоритм по шагам на точках A, B, C и ещё двух точках D = (3,5; 0), E = (4,2; 0,4) с порогом 0,9:

Как выбрать порог ε?

Порог должен быть не меньше шагов внутри кластеров и меньше промежутков между кластерами; проверяют несколько значений и смотрят на размеры групп. В файле example27.txt у каждой группы точки связаны шагами √2 < 1,5, а между группами близких пар нет. Функции read_points и center_sum — из основных подтем:

points = read_points("example27.txt", has_header=True)clusters = split_clusters(points, eps=1.5)print("Количество групп:", len(clusters))for cluster in clusters:    print(len(cluster), center_sum(cluster))

Центры те же, что при границе x = 5. Первой получилась правая группа: pop() начал с последней точки файла. Требования к порогу:

1. Внутри каждого требуемого кластера точки соединяются цепочками шагов длиной не больше ε.
2. Между разными требуемыми кластерами нет ни одной пары точек на расстоянии не больше ε.

Обрати внимание: первое требование относится к цепочкам, а не к наибольшему расстоянию между любыми двумя точками внутри кластера. Вытянутый кластер может иметь длину 20 единиц, но состоять из точек с промежутками по 0,2. Для его связности вовсе не нужен порог 20.

Если порог слишком маленький, одна настоящая группа может распасться на несколько. Если слишком большой, отдельные группы могут соединиться.

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

После автоматического разделения полезно вывести размеры и проверить несколько близких значений порога. В файле 27-6.txt две дуги вложены одна в другую: вертикальная или горизонтальная граница здесь не помогает, а цепочки — помогают:

points = read_points("27-6.txt") for eps in [0.3, 0.5, 1.0, 2.0]:    clusters = split_clusters(points, eps)     sizes = []     for cluster in clusters:        sizes.append(len(cluster))     print(eps, len(sizes), sorted(sizes, reverse=True)[:3])

При пороге 0,3 одна дуга распалась на куски; от 0,5 до 2 разделение одно и то же — две дуги из 140 и 120 точек.

Если в некотором диапазоне порогов сохраняется одно и то же разумное разделение, это полезный признак устойчивости. Но он не заменяет проверку геометрии и требований условия.

Секторы файла 27-5.txt показывают обе ошибки порога. У вершины C точки разных секторов сходятся, а на дальнем краю сектора точки редкие:

points = read_points("27-5.txt") for eps in [1.2, 3, 5]:    clusters = split_clusters(points, eps)    print(eps, sorted([len(c) for c in clusters], reverse=True))

При 1,2 третий сектор из 69 точек распался на куски 63, 3 и 3; при 5 все секторы слились через вершину; при 3 разделение верное. Угол направления из подтемы 2 разделяет эти точки без подбора порога.

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

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

# Нельзя считать это универсальным правилом!if len(cluster) > 10:    ...

Как найти центр, если в условии — наименьшее расстояние до самой далёкой точки?

Для каждого кандидата найти самое большое расстояние до точек кластера и выбрать кандидата с наименьшим таким максимумом. Такой принцип называют минимаксом: минимум среди максимумов. Сравним его с суммой расстояний на точках (0; 0), (1; 0), (2; 0), (5; 0) и (10; 0).

По сумме расстояний центр — (2, 0). По минимальному максимальному расстоянию — (5, 0). Это разные задачи с разными ответами.

from math import dist  def center_minimax(cluster):    best_point = cluster[0]    best_radius = float("inf")    for candidate in cluster:        radius = 0.0        for point in cluster:            d = dist(candidate, point)            if d > radius:                radius = d        if radius < best_radius:            best_radius = radius            best_point = candidate    return best_point, best_radius

line = [(0, 0), (1, 0), (2, 0), (5, 0), (10, 0)] center, radius = center_minimax(line)print(center, radius)print(center_sum(line))

Функция возвращает два значения: center — выбранную точку, radius — расстояние от неё до самой далёкой точки. Такое определение встречается в задачах подборки, где кластеры — круги, а ответ — средний радиус.

Если центр по условию обязан быть точкой кластера, нельзя свободно поставить его между точками. Например, для двух точек (0, 0) и (10, 0) геометрическая середина (5, 0) покрывает их кругом радиуса 5. Но если разрешено выбирать центр только из этих двух точек, минимальное максимальное расстояние равно 10. Ограничение на допустимые центры принципиально меняет задачу.

Что значат в условии «антицентр» и «антипод»?

То, что написано в определении: по одному слову алгоритм не угадать. Переведи определение в два ответа — что считаем для кандидата и как выбираем. Выбери определение:

минимум суммы расстояний

сумму расстояний до точек кластеранаименьшую сумму

максимум суммы расстояний

ту же суммунаибольшую сумму

минимум максимального расстояния

самое большое расстояние до точки кластеранаименьший максимум

самая далёкая точка от уже найденного центра

одно расстояние до этого центранаибольшее расстояние

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

Если «антицентр» определён как точка с максимальной суммой расстояний, в функции center_sum меняются начальное значение best_sum = -float("inf") и сравнение if total > best_sum:. Всё остальное устройство сохраняется. В подборках так ищут антицентры самых крупных кластеров: сначала sorted(clusters, key=len), затем антицентр каждого из нужных.

Но найти точку с максимальной суммой расстояний и найти точку, самую далёкую от центра, — это не одно и то же вычисление. Для самой далёкой от уже известного центра:

center = (2, 0)farthest_point = line[0]max_distance = -1.0 for point in line:    d = dist(center, point)     if d > max_distance:        max_distance = d        farthest_point = point print(farthest_point, max_distance)

Здесь нет суммирования: каждой точке соответствует только одно расстояние.

Как найти центр по наименьшей сумме квадратов расстояний?

Это точка кластера, ближайшая к средней точке: сумма квадратов растёт с удалением от средней точки, как парабола. На точках 0, 1, 2, 3, 100 сумму квадратов выиграл кандидат 3 — ближайший к средней точке 21,2 (подтема 3). Нарисуем сумму квадратов T(x) для любого x на прямой:

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

def center_squared(cluster):    sum_x = 0.0    sum_y = 0.0    for x, y in cluster:        sum_x += x        sum_y += y    mean_x = sum_x / len(cluster)    mean_y = sum_y / len(cluster)    best_point = cluster[0]    best_value = float("inf")    for point in cluster:        x, y = point        value = (x - mean_x) ** 2 + (y - mean_y) ** 2        if value < best_value:            best_value = value            best_point = point    return best_point

cluster = [(0, 0), (1, 0), (2, 0), (3, 0), (100, 0)]print(center_squared(cluster), center_sum(cluster))

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

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

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

Это тот же перебор кандидатов, только для кандидата считают не сумму, а количество, и правил выбора два. Оба правила укладываются в один ключ:

from math import dist stars = [(1, 1), (2, 1), (2, 2), (5, 4), (6.2, 4.4), (5.6, 5.6)]R = 1.5  def visible(c):    return sum(dist(c, s) < R for s in stars) - 1  aim = min(stars, key=lambda c: (-visible(c), dist(c, (0, 0))))print([visible(c) for c in stars])print(aim)

• sum(dist(c, s) < R for s in stars) складывает истинные сравнения как единицы. Сама звезда тоже попадает в счёт — расстояние 0 — поэтому вычитаем 1. Так звёзды с одинаковыми координатами посчитаются верно.
• Ключ — пара: сначала -visible(c) (чем больше видно, тем меньше ключ), при равенстве — расстояние до начала координат. min сравнивает пары по порядку.

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

Посчитать коэффициент корреляции Пирсона r: он лежит от −1 до 1, и чем ближе |r| к 1, тем точнее точки ложатся на прямую. r около 0 — облако без наклона, r < 0 — один параметр растёт, а другой убывает. В подборках связь называют сильной, если |r| ≥ 0,9.

r = Σ(xᵢ − x̄)(yᵢ − ȳ) / √(Σ(xᵢ − x̄)² · Σ(yᵢ − ȳ)²), где x̄ и ȳ — средние. Для точек (1; 2), (2; 3), (3; 5), (4; 4), (5; 6): x̄ = 3, ȳ = 4, отклонения x — −2, −1, 0, 1, 2, отклонения y — −2, −1, 1, 0, 2. Сумма произведений 4 + 1 + 0 + 0 + 4 = 9, суммы квадратов 10 и 10, r = 9 / √100 = 0,9:

def pearson(points):    n = len(points)    mx = sum(p[0] for p in points) / n    my = sum(p[1] for p in points) / n    sxy = sum((p[0] - mx) * (p[1] - my) for p in points)    sxx = sum((p[0] - mx) ** 2 for p in points)    syy = sum((p[1] - my) ** 2 for p in points)    return sxy / (sxx * syy) ** 0.5  print(pearson([(1, 2), (2, 3), (3, 5), (4, 4), (5, 6)]))

В файле 27-9.txt записаны результаты трёх экспериментов вперемешку. На рисунке они разделены пустыми полосами — делим границами и считаем r для каждого:

points = read_points("27-9.txt")groups = [[], [], []]for x, y in points:    if x < 15:        groups[0].append((x, y))    elif x < 35:        groups[1].append((x, y))    else:        groups[2].append((x, y))for g in groups:    print(len(g), round(pearson(g), 3))

Сильная связь — у первого и третьего экспериментов: в них 60 + 70 = 130 измерений. В Python 3.10 и новее то же число считает statistics.correlation(xs, ys). В подборке эксперименты разделяют цепочками соседей с порогом из условия — функцией split_clusters из начала урока.

Как найти выбросы — случайные ошибочные измерения, которые надо убрать перед расчётом?

Методом межквартильного размаха: найти квартили Q1 и Q3, размах IQR = Q3 − Q1 и считать выбросом всё, что дальше 1,5 · IQR от квартилей. Квартили считают так, как сказано в условии. В подборке: Q1 — медиана нижней половины упорядоченных значений, Q3 — медиана верхней; при нечётном количестве срединное значение не входит ни в одну половину.

Значения 3, 9, 10, 10, 11, 12, 12, 13, 14, 29: нижняя половина 3, 9, 10, 10, 11 — Q1 = 10, верхняя 12, 12, 13, 14, 29 — Q3 = 13. IQR = 3, границы 10 − 4,5 = 5,5 и 13 + 4,5 = 17,5:

def median(v):    n = len(v)    if n % 2:        return v[n // 2]    return (v[n // 2 - 1] + v[n // 2]) / 2  def quartiles(values):    v = sorted(values)    n = len(v)    return median(v[:n // 2]), median(v[(n + 1) // 2:])  data = [12, 3, 10, 14, 11, 29, 9, 12, 13, 10]q1, q3 = quartiles(data)iqr = q3 - q1lo, hi = q1 - 1.5 * iqr, q3 + 1.5 * iqrprint(q1, q3, lo, hi)print([v for v in data if v < lo or v > hi])

Срез v[:n // 2] — нижняя половина, v[(n + 1) // 2:] — верхняя: при нечётном n срединный элемент пропускается. Если точки двумерные, границы считают отдельно для x и для y, и точка — выброс, когда хотя бы одна её координата за границей.

Можно ли искать центр быстрее, не рискуя ответом?

Да: считать каждое расстояние один раз и прибавлять его сразу к двум суммам, а кандидата бросать, как только его сумма догнала лучшую. В основном переборе d(A, B) считается дважды — когда кандидат A и когда кандидат B. Но d(A, B) = d(B, A).

Для этого создаём отдельную сумму для каждой точки: totals = [0.0] * len(cluster). Если точек четыре, получится [0.0, 0.0, 0.0, 0.0]. Полная функция:

def center_sum_pairs(cluster):    n = len(cluster)    totals = [0.0] * n    for i in range(n):        for j in range(i + 1, n):            d = dist(cluster[i], cluster[j])            totals[i] += d            totals[j] += d    best_index = totals.index(min(totals))    return cluster[best_index]

range(n) создаёт последовательность номеров 0, 1, 2, …, n − 1. Внутренний цикл начинается с i + 1, поэтому перебираются только пары, в которых второй номер больше первого. Для четырёх точек это (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3).

Пара (1, 0) не нужна: она уже учтена как (0, 1). Расстояние от точки до самой себя тоже не вычисляется.

Число различных пар — m(m − 1) / 2, примерно вдвое меньше исходных m². После завершения циклов min(totals) находит наименьшую сумму, totals.index(...) — номер её первого появления, и по этому номеру возвращаем исходную точку cluster[best_index]:

print(center_sum_pairs(cluster), center_sum_pairs(line))

Порядок роста остаётся квадратичным, но вычислений расстояния становится меньше. Таблица всех попарных расстояний не нужна — хватает списка сумм длины m.

from math import dist  def center_sum_early(cluster):    best_point = cluster[0]    best_sum = float("inf")    for candidate in cluster:        total = 0.0        for point in cluster:            total += dist(candidate, point)            if total >= best_sum:                break        if total < best_sum:            best_sum = total            best_point = candidate    return best_point  print(center_sum_early([(0, 0), (5, 0)]))

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

• Цепочки соседейгруппа — всё, что связано шагами не длиннее ε
• Порогбольше шагов внутри, меньше промежутков между
• Другие центрыминимакс, антицентр, ближайшая к средней точке
• Точка наведенияключ (-видимых, до начала координат)
• Корреляцияr Пирсона; сильная связь — |r| ≥ 0,9
• Выбросыза пределами Q1 − 1,5 · IQR и Q3 + 1,5 · IQR