Статья Автор: Прохоров Михаил

Я решаю 27 Прохоров

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри сектора круга. Каждая звезда обязательно принадлежит только одному из кластеров.

Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна.

Под расстоянием понимается расстояние Евклида между двумя точками
В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата, затем координата. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах четырёх кластеров. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле B аналогична файлу А.

×10000 для файла А, во второй строке – аналогичные данные для файла B.

Возможные данные одного из файлов иллюстрированы графиком.

Полный шаблон для такого типа задач с аномалиями:

#перед этим меняем запятые на точки и убираем первую строчку, если она не нужна

#---введение (константы, которые можно подставлять)
limit_dist = 0.8#расстояние поиска ближайших точек
limit_anom = 10#граница количества для аномалий
size = 40#масштаб (условные единицы черепашки)
index = 10000#насколько домножать ответ

#---берем данные
data = []
for s in open('27.11.B_20206.txt', 'r'):
    data.append(tuple(map(float, s.split())))

print(len(data))#для проверки

#---функция расстояния
def dist(d1, d2):
    x1, y1, x2, y2 = *d1, *d2
    return ((x2- x1) ** 2 + (y2 - y1) ** 2) ** 0.5
#или from math import dist -> только если такая метрика

#---функция нахождения класстера по точке
def getCluster(d0):
    cluster = [d for d in data if dist(d, d0) < limit_dist]
    if cluster:
        for d in cluster: data.remove(d)
        cluster += sum([getCluster(d) for d in cluster], [])
        #de facto выполняем параллельно, а не последовательно
    return cluster

#---определение кластеров и аномалий
clusters, anomalies = [], []
while data:
    d = data.pop()
    cl = getCluster(d) + [d]#не забывать d
    print(len(cl))#для проверки
    if len(cl) < limit_anom:
        anomalies += cl
    else:
        clusters.append(cl)

#---отрисовка кластеров и аномалий
colors = ['red', 'green', 'blue', 'purple', 'pink', 'yellow']
#если ты такой же ценитель колористики, тогда смотри
# https://barzunov.ru/python/turtle/color/colors-list/
from turtle import *
up()
tracer(0)

for cl, color in zip(clusters, colors):
    for x, y in cl:
        goto(x * size, y * size)
        dot(2, color)

for x, y in anomalies:
        goto(x * size, y * size)
        dot(3, 'black')

#---функция нахождения центроида
def center(cl):
    return min((sum(dist(d1, d) for d1 in cl), d) for d in cl)[1]

#---нахождение центроидов
centres = [center(i) for i in clusters]
print(centres)#для проверки

#---подготовка к ответу
count = len(centres)#помнить
px = sum(x for x, y in centres)
py = sum(y for x, y in centres)
print(int(px / count * index), int(py / count * index))
#может ещё быть в вопросе abs()

Шаблон для достаточно быстрого решения такой именно задачи:

from math import dist

limit = 1
size = 15
index = 10000

data = [tuple(map(float, s.split()))  for s in open('27.11.B_20206.txt', 'r')]

def getCluster(d0):
    cluster = [d for d in data if dist(d, d0) < limit]
    if cluster:
        for d in cluster: data.remove(d)
        cluster += sum([getCluster(d) for d in cluster], [])
    return cluster

clusters = []
while data:
    d = data.pop()
    clusters.append(getCluster(d) + [d])

colors = ['red', 'green', 'blue']
from turtle import *
up()
tracer(0)
for cl, color in zip(clusters, colors):
    for x, y in cl:
        goto(x * size, y * size)
        dot(2, color)

def center(cl):
    return min((sum(dist(d1, d) for d1 in cl), d) for d in cl)[1]

centres = [center(i) for i in clusters]

px = sum(x for x, y in centres) / len(centres)
py = sum(y for x, y in centres) / len(centres)
print(int(px * index), int(py * index))

Если мы решаем через точки.
Тогда сначала откроем EXCEL и узнаем центры класстеров

Полный шаблон для решения:

#убираем первую строчку, если не нужна
size = 10#масштаб (условные единицы)
index = 10000#насколько домножать ответ

#---берем данные
m = [tuple(map(float, s.replace(',', '.').split())) for s in open('27.11.B_20206.txt', 'r')]

p = [(8, 3, 0), (12, -7, 0), (15, 3, 1), (22, 2, 1), (10, 7, 2),(11, 10, 2), (13, 18, 2), (12, 10, 3), (15, 15, 3)]#центройды (выбираем визуально)

#---функция расстояния
def dist(d1, d2):
    x1, y1, x2, y2 = *d1, *d2
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
#если такая метрика можно использовать from math import dist. Может быть и abs(x2 - x1) + abs(y2 - y1)

#---функция определения класстера по точке
def findCluster(d, p):
    return min([(dist((x0, y0), d), cl) for x0, y0, cl in p])[1]

#---разделяем на класстеры
clusters = {}
for d in m:
    cl = findCluster(d, p)
    if cl in clusters:
        clusters[cl] += [d]
    else:
        clusters[cl] = [d]

print(len(clusters), *[len(cl) for cl in clusters.values()])
#выводим размеры класстеров для проверки

#---отрисовка кластеров
colors = ['red', 'blue', 'green', 'pink', 'yellow', 'cyan', 'light blue', 'purple', 'orange']
from turtle import *
tracer(0)
up()

for cl, color in zip(clusters.values(), colors):
    for x, y in cl:
        goto(x * size, y * size)
        dot(3, color)

#---функция нахождения центроида
def center(cl):
    return min([(sum(dist(d1, d) for d1 in cl), d) for d in cl])[1]

#---нахождение центроидов
centers = [center(cl) for cl in clusters.values()]
print(centers)#выводим центройды для проверки

#---подготовка к ответу
px = sum(x for x, y in centers) / len(centers)
py = sum(y for x, y in centers) / len(centers)
print(int(index * px), int(index * py))
#иногда просят абсолютное значение => abs()

Прикрепленные файлы
27.11.A_20206.txt
27.11.B_20206.txt

Чтобы оставить комментарий нужна авторизация

Печать