Кластеризация

Что просят сделать

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

Простыми словами

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

Что дано

Два файла. В файле А обычно 2 кластера, в файле Б обычно 3. В каждой строке три значения: координата x, координата y и класс звезды.

4,924550 4,721530 O7V
3,111640 6,900950 G1V

В ответ идут 4 числа: два для файла А и два для файла Б. Часто просят умножить на 10000 и взять целую часть.

План из пяти шагов

1. Прочитать файл в список.
2. Разделить звёзды на кластеры.
3. Проверить, что кластеров столько, сколько в условии. Если нет, поменять порог.
4. Найти центр каждого кластера.
5. Посчитать то, что спрашивают.

Весь код в уроке запускается на маленьком учебном файле 27-demo.txt, в нём 36 звёзд и 3 кластера. Можешь менять код и смотреть, что произойдёт.

Шаг 1. Читаем файл

Читаем файл построчно и превращаем каждую строку в удобную запись.

from math import dist

data = []
for line in open('27-demo.txt'):
    x, y, h = line.replace(',', '.').split()
    data.append(([float(x), float(y)], h))

print(len(data))
print(data[0])

Разберём строку за строкой:

• line.replace(',', '.'): в файле дробные числа записаны через запятую, а Python понимает только точку.
• .split() разрезает строку по пробелам на три части: x, y, h.
• float(x) превращает текст в число.
• data.append(([x, y], h)) кладёт в список одну звезду: сначала координаты, потом класс.

Значит, у звезды p координаты лежат в p[0], а класс в p[1]. Это пригодится на всех следующих шагах.

Расстояние между звёздами считает dist из модуля math: dist(p[0], q[0]). Формулу писать самому не нужно.

Шаг 2. Делим на кластеры

Это главная часть. Идея такая: берём любую звезду и начинаем новую кучку. Находим всех её близких соседей и добавляем в кучку. Потом ищем соседей у соседей, пока новые не закончатся. Кучка готова, берём следующую свободную звезду.

from math import dist

data = []
for line in open('27-demo.txt'):
    x, y, h = line.replace(',', '.').split()
    data.append(([float(x), float(y)], h))

t = 1.5
clusters = []
while data:
    clusters.append([data.pop(0)])
    for p in clusters[-1]:
        sosedi = [p1 for p1 in data if dist(p[0], p1[0]) < t]
        clusters[-1].extend(sosedi)
        for p1 in sosedi:
            data.remove(p1)

for cl in clusters:
    print(len(cl))

Что делает каждая строка:

• while data: пока остались звёзды без кучки, продолжаем.
• clusters.append([data.pop(0)]): берём первую свободную звезду и начинаем с неё новую кучку. pop убирает её из data.
• for p in clusters[-1]: идём по текущей кучке. Важный момент: кучка растёт прямо во время цикла, поэтому до новых соседей цикл тоже дойдёт. Так и работает цепочка.
• sosedi = [...]: все свободные звёзды ближе порога t к звезде p.
• extend добавляет соседей в кучку, а remove убирает их из свободных, чтобы никого не посчитать дважды.

Запусти код. Он напечатает размер каждого кластера.

Шаг 3. Подбираем порог

Порог t в условии не дан, его подбираем сами. Вот что происходит с учебным файлом при разных порогах:

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

Как подбирать

1. Начни с t = 1 и посмотри на напечатанные размеры.
2. Кластеров больше, чем в условии, увеличь t.
3. Кластеров меньше, чем в условии, уменьшай t.
4. Число совпало и размеры выглядят как настоящие кучки, можно идти дальше.

На настоящих файлах это важно. В одном файле экзамена при t = 1 получается лишний кластер из одной точки, и нужно поднять порог. В другом при t = 1 два кластера склеиваются, и нужно опустить порог примерно до 0,6.

Прямоугольник H×W в условии описывает, какого размера кучки. Для нашего кода он нужен только как подсказка: порог обычно гораздо меньше этих размеров.

# пиши решение здесь

Шаг 4. Находим центры

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

Посчитаем на маленьком примере

Кластер из четырёх точек. Для каждой складываем расстояния до трёх других:

Наименьшая сумма у точки (1,5; 2), она и есть центр.

То же в коде

from math import dist

data = []
for line in open('27-demo.txt'):
    x, y, h = line.replace(',', '.').split()
    data.append(([float(x), float(y)], h))

t = 1.5
clusters = []
while data:
    clusters.append([data.pop(0)])
    for p in clusters[-1]:
        sosedi = [p1 for p1 in data if dist(p[0], p1[0]) < t]
        clusters[-1].extend(sosedi)
        for p1 in sosedi:
            data.remove(p1)

def centroids(cl):
    m = []
    for p in cl:
        sm = sum(dist(p[0], p1[0]) for p1 in cl)
        m.append([sm, p])
    return min(m)[1]

centroid = [centroids(cl) for cl in clusters]

for c in centroid:
    print(c)

• Для каждой звезды p считаем сумму sm расстояний до всех звёзд кучки.
• В список m кладём пары «сумма, звезда».
• min(m) находит пару с наименьшей суммой, а [1] достаёт из неё звезду.

В итоге centroid[0] это центр кластера clusters[0], и так далее. Номера совпадают, и это удобно на следующем шаге.

# пиши решение здесь

# пиши решение здесь

Шаг 5. Отвечаем на вопрос

Самый творческий шаг, но вопросы повторяются. Сначала пойми, про кого спрашивают.

Как читать класс звезды

Класс записан так: буква цвета, цифра, потом светимость. Например, K4IV значит оранжевый субгигант.

Белые карлики записаны просто VII, без цвета и цифры.

Проверяем отдельно цвет и светимость: цвет это h[0], светимость это h[2:].

h[0] == 'K' and h[2:] == 'III'     # оранжевый гигант
h[0] == 'O' and h[2:] == 'VI'      # голубой субкарлик

Частые вопросы и готовый код

Полный разбор вопроса

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

from math import dist

data = []
for line in open('27-demo.txt'):
    x, y, h = line.replace(',', '.').split()
    data.append(([float(x), float(y)], h))

t = 1.5
clusters = []
while data:
    clusters.append([data.pop(0)])
    for p in clusters[-1]:
        sosedi = [p1 for p1 in data if dist(p[0], p1[0]) < t]
        clusters[-1].extend(sosedi)
        for p1 in sosedi:
            data.remove(p1)

def centroids(cl):
    m = []
    for p in cl:
        sm = sum(dist(p[0], p1[0]) for p1 in cl)
        m.append([sm, p])
    return min(m)[1]

centroid = [centroids(cl) for cl in clusters]

def is_dwarf(h):
    return h[0] in 'OBAFGKM' and h[2:] == 'V'

counts = [sum(1 for p in cl if is_dwarf(p[1])) for cl in clusters]
print(counts)
i = counts.index(min(counts))
c = centroid[i]
print(int(abs(c[0][0]) * 10000), int(abs(c[0][1]) * 10000))

counts хранит число карликов по кластерам, а counts.index(min(counts)) находит номер кластера с наименьшим числом. Номер i подходит и для clusters, и для centroid.

from math import dist
data = []
for line in open('27-demo.txt'):
    x, y, h = line.replace(',', '.').split()
    data.append(([float(x), float(y)], h))
# дальше твой код

from math import dist
data = []
for line in open('27-demo.txt'):
    x, y, h = line.replace(',', '.').split()
    data.append(([float(x), float(y)], h))
# дальше твой код

Весь порядок на экзамене

Собери всё вместе. Удобно держать один файл с кодом и менять в нём только имя файла, порог и последние строки.

1. Копируешь шаблон из шага 4 и пишешь имя файла А.
2. Запускаешь и смотришь размеры. Подбираешь порог, пока число кластеров не совпадёт с условием.
3. Читаешь вопрос для А и дописываешь последние строки, сверяясь с таблицей из шага 5.
4. Записываешь два числа.
5. Меняешь имя файла на Б и снова проверяешь порог: для него он может быть другим.
6. Дописываешь вопрос для Б. Он обычно другой, поэтому код для А не подойдёт.

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

Если кластеризуют не звёзды, а числа

Иногда кучки строятся не по расстоянию на плоскости, а по одному числу, например по энергии E = m(Vx² + Vy²) / 2. Код почти тот же: положи в начало записи список из одного числа, [E], а координаты и признак отдельно. dist прекрасно работает и со списками из одного числа. Порог снова подбираем по числу кластеров.

Ловушки