Кластеризация: считаем характеристики

Два файла — два кластера. Учимся считать четыре величины: дальний и средний карлик, сближение и дальний гигант

У нас есть две группы точек (два кластера), и они лежат в двух отдельных файлах: cluster1.txt и cluster2.txt. В каждой строке файла — одна звезда: координата x, координата y и её характеристика (например L3II). Координаты — в условных единицах.

Нам нужно найти четыре величины. Две — про синие карлики в одном кластере, две — про белые мега-гиганты в обоих кластерах. Разберём каждую по шагам.

Первые две (карлики) считаются внутри одного кластера. Две другие (гиганты) связывают оба кластера.

Заметь общий каркас у всех четырёх: «какое расстояние (max / среднее / min) от чего до каких звёзд в каком кластере». Соберём пять кубиков и из них — любой ответ.

Каждую звезду удобно хранить как набор из четырёх значений: x, y, цвет и размер (если понадобиться светимость, то можно ее добавить ch[1]). Цвет и размер сразу вытащим из характеристики (как — в кубике 3). Читаем каждый файл по очереди в свой список.

чтениеdef read(name):
    pts = []
    for line in open(name):
        x, y, ch = line.replace(',', '.').split()    # запятая → точка
        pts.append((float(x), float(y), ch[0], ch[2:]))   # (x, y, цвет, размер)
    return pts

cl1 = read('cluster1.txt')    # точки первого кластера
cl2 = read('cluster2.txt')    # точки второго кластера

Теперь cl1 и cl2 — списки точек, каждая точка s — кортеж: s[0] = x, s[1] = y, s[2] = цвет, s[3] = размер.

Расстояние между двумя точками на плоскости — это длина отрезка между ними, по теореме Пифагора:

В Python уже есть готовая функция dist. Завернём её в короткую d(p, q), чтобы брать координаты из наших кортежей:

кубик 1from math import dist

def d(p, q):
    return dist((p[0], p[1]), (q[0], q[1]))    # расстояние между точками p и q

Центром кластера называют такую его точку, сумма расстояний от которой до всех остальных точек кластера наименьшая (самая «центральная» точка). Найдём её перебором: для каждой точки считаем сумму расстояний до всех и запоминаем точку с минимальной суммой. Начинаем с float('inf') — «бесконечности», чтобы первая же сумма оказалась меньше.

кубик 2def center(cl):
    best = cl[0]
    best_sum = float('inf')        # «бесконечность»: любая реальная сумма меньше
    for p in cl:                 # пробуем каждую точку как центр
        s = 0
        for q in cl:
            s += d(p, q)            # сумма расстояний до всех остальных
        if s < best_sum:           # нашли точку «центрее»
            best_sum = s
            best = p
    return best

Тип, который просят (LII, GV) — это цвет + размер. В характеристике: первая буква — цвет, потом цифра светимости (нам не нужна), затем размер.

разборch = 'L3II'
ch[0]   # 'L'  — цвет (синий)
ch[1]   # '3'  — светимость (не нужна)
ch[2:]  # 'II' — размер (карлик)   → значит это LII

Полная расшифровка букв и размеров (это условие — справочные таблицы задачи). Характеристика записана слитно: буква цвета, цифра светимости, затем размер римскими. Например, L3II = синий (L) + светимость 3 + карлик (II) = синий карлик; G5V = белый (G) + 5 + мега-гигант (V) = белый мега-гигант.

Нам в расчётах нужны LII (синий карлик) и GV (белый мега-гигант) — берём только цвет (ch[0]) и размер (ch[2:]), светимость не используется.

Чтобы отобрать из кластера звёзды нужного типа, проходим по нему и собираем подходящие в список:

кубик 3def of_type(cl, color, size):
    res = []
    for s in cl:
        if s[2] == color and s[3] == size:    # цвет и размер совпали
            res.append(s)
    return res

lii = of_type(cl1, 'L', 'II')   # синие карлики кластера cl1

Покрути фильтр: какие звёзды попадают в LII, GV, NII.

Иногда нужно взять не любой, а определённый кластер: «больший по числу точек» (для карликов) или «где звёзд нужного типа больше» (для гигантов). Сравниваем два кластера через if:

кубик 4# больший по числу точек (для карликов):
if len(cl1) >= len(cl2):
    big = cl1
else:
    big = cl2

# где больше GV (для дальнего гиганта):
gv1 = of_type(cl1, 'G', 'V')
gv2 = of_type(cl2, 'G', 'V')
if len(gv1) >= len(gv2):
    best, gv_best = cl1, gv1
else:
    best, gv_best = cl2, gv2

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

кубик 5ds = []
for s in pts:
    ds.append(d(c, s))      # расстояния от точки c до каждой звезды pts

max(ds)               # самое большое   → дальний карлик / гигант
sum(ds) / len(ds)     # среднее         → средний разброс
min(ds)               # самое маленькое → сближение, вариации

Обе величины живут внутри одного кластера — большего по числу точек. Берём его центр и его синие карлики (LII), считаем расстояния, и берём максимум (дальний карлик) и среднее (средний разброс).

карликиif len(cl1) >= len(cl2):       # кубик 4: больший кластер
    big = cl1
else:
    big = cl2

c   = center(big)               # кубик 2: центр
lii = of_type(big, 'L', 'II')   # кубик 3: синие карлики

ds = []                         # кубик 5: расстояния
for s in lii:
    ds.append(d(c, s))

far_dwarf = max(ds)             # дальний карлик
avg_dwarf = sum(ds) / len(ds)   # средний разброс карликов
print(int(abs(far_dwarf * 10000)), int(abs(avg_dwarf * 10000)))

На плоскости: точки одного кластера, его центр (золотой ромб) и синие карлики (LII, синие). Линии — расстояния от центра до LII; самая длинная (дальний карлик) золотая, среднее всех — средний разброс.

Здесь работают оба кластера. Сначала отберём белых мега-гигантов (GV) в каждом: gv1 и gv2.

Сближение гигантов — минимальное расстояние между GV из разных кластеров. Перебираем все пары «GV из cl1 — GV из cl2» и копим минимум (старт — float('inf')). Пары внутри одного кластера не считаются.

сближениеgv1 = of_type(cl1, 'G', 'V')
gv2 = of_type(cl2, 'G', 'V')

near_giants = float('inf')        # «бесконечность»: первое же расстояние меньше
for p in gv1:          # GV из первого кластера
    for q in gv2:      # GV из второго кластера
        r = d(p, q)
        if r < near_giants:
            near_giants = r

Дальний гигант — берём кластер, где GV больше, его центр, и максимальное расстояние от центра до его GV.

дальний гигантif len(gv1) >= len(gv2):    # кластер, где GV больше
    best, gv_best = cl1, gv1
else:
    best, gv_best = cl2, gv2

c = center(best)
far_giant = 0
for s in gv_best:
    far_giant = max(far_giant, d(c, s))

print(int(abs(near_giants * 10000)), int(abs(far_giant * 10000)))

На плоскости: два кластера, белые мега-гиганты (GV) выделены белым. Красный отрезок — сближение гигантов (ближайшая пара GV из разных кластеров), золотой — дальний гигант (от центра кластера, где GV больше, до самого далёкого его GV).

Меняя три вещи — тип звезды, какой кластер и агрегатор (max / среднее / min) — получаешь любой похожий вопрос. Несколько примеров:

целикомfrom math import dist

def d(p, q):
    return dist((p[0], p[1]), (q[0], q[1]))

def center(cl):
    best = cl[0]; best_sum = float('inf')
    for p in cl:
        s = 0
        for q in cl:
            s += d(p, q)
        if s < best_sum:
            best_sum = s; best = p
    return best

def of_type(cl, color, size):
    res = []
    for s in cl:
        if s[2] == color and s[3] == size:
            res.append(s)
    return res

def read(name):
    pts = []
    for line in open(name):
        x, y, ch = line.replace(',', '.').split()
        pts.append((float(x), float(y), ch[0], ch[2:]))
    return pts

cl1 = read('cluster1.txt')
cl2 = read('cluster2.txt')

# ---- карлики: больший кластер, его синие карлики (LII) ----
if len(cl1) >= len(cl2):
    big = cl1
else:
    big = cl2
c = center(big)
lii = of_type(big, 'L', 'II')
ds = []
for s in lii:
    ds.append(d(c, s))
far_dwarf = max(ds)
avg_dwarf = sum(ds) / len(ds)
print(int(abs(far_dwarf * 10000)), int(abs(avg_dwarf * 10000)))

# ---- гиганты: белые мега-гиганты (GV) обоих кластеров ----
gv1 = of_type(cl1, 'G', 'V')
gv2 = of_type(cl2, 'G', 'V')

near_giants = float('inf')          # min между GV разных кластеров
for p in gv1:
    for q in gv2:
        r = d(p, q)
        if r < near_giants:
            near_giants = r

if len(gv1) >= len(gv2):         # кластер, где GV больше
    best, gv_best = cl1, gv1
else:
    best, gv_best = cl2, gv2
c = center(best)
far_giant = 0
for s in gv_best:
    far_giant = max(far_giant, d(c, s))

print(int(abs(near_giants * 10000)), int(abs(far_giant * 10000)))

В каждом вопросе — кусок кода (реализация функции или расчёт). Прочитай его и выбери, что он вычисляет. Переменные в коде (cl1, gv1, big, c, lii…) — те же, что в разделах выше; в первой строке сниппета есть подсказка, что они означают. Вопросы построены на вариациях наших величин: меняются тип звезды, выбор кластера и агрегатор (max / среднее / min).