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

Администратор

1 год назад

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

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

Под расстоянием понимается расстояние Евклида между двумя точками A(x1,y1) и B(x2,y2) на плоскости, которое вычисляется по формуле:

Аномалиями назовём звёзды, находящиеся на расстоянии более одной условной единицы от звёзд кластеров. При расчётах аномалии учитывать не нужно.

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

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

Для каждого файла определите координаты края каждого кластера, затем вычислите два числа: Tx – среднее арифметическое абсцисс краев кластеров, и Ty – среднее арифметическое ординат краев кластеров.

В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения Tx×10000, затем целую часть абсолютного значения произведения Ty×10000 для файла А, во второй строке – аналогичные данные для файла B.

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

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.

Для выполнения задания используйте данные из прилагаемого файла.

ege-inf-zad27-7A.txt ege-inf-zad27-7A.xlsx

ege-inf-zad27-7B.txt ege-inf-zad27-7B.xlsx

Ответ:

для файла А

Tx × 10000

Ty × 10000

для файла Б

Tx × 10000

Ty × 10000

kompege.ru № 19566 (М. Попков) – задание №27

Показать решение...

Решение:

Visualizing DBSCAN Clustering

https://www.naftaliharris.com/blog/visualizing-dbscan-clustering/

Решение: Кабанов Алексей

для файла А

from math import dist
from turtle import*
from random import*
f = open('ege-inf-zad27-7A.txt')
data = []
for s in f:
    x,y = [float(d) for d in s.split()]
    data.append([x,y])
clusters = []
while data:
    cl = [data.pop()]
    for p in cl:
        sosed = [p1 for p1 in data if dist(p,p1) < 1]
        for p1 in sosed:
            cl.append(p1)
            data.remove(p1)
    clusters.append(cl)

clusters = [cl for cl in clusters if len(cl) > 20]
print([len(cl) for cl in clusters])

#
# tracer(0)
# up()
# for cl in clusters:
#     color = random(),random(),random()
#     for x,y in cl:
#         goto(x*30, y*30)
#         dot(2, color)
# mainloop()

def clusterEdge(cl):
    m = []
    for p in cl:
        s = 0
        for p1 in cl:
            s += dist(p,p1)
        m.append([s,p])
    return max(m)[1]

cen = [clusterEdge(cl) for cl in clusters]
tx = sum(x for x,y in cen)/len(cen)
ty = sum(y for x,y in cen)/len(cen)
print(abs(int(tx*10000)), abs(int(ty*10000)))

from math import dist

from turtle import*

from random import*

f = open('ege-inf-zad27-7A.txt')

data = []

for s in f:

x,y = [float(d) for d in s.split()]

data.append([x,y])

clusters = []

while data:

cl = [data.pop()]

for p in cl:

sosed = [p1 for p1 in data if dist(p,p1) < 1]

for p1 in sosed:

cl.append(p1)

data.remove(p1)

clusters.append(cl)

clusters = [cl for cl in clusters if len(cl) > 20]

print([len(cl) for cl in clusters])

# tracer(0)

# up()

# for cl in clusters:

# color = random(),random(),random()

# for x,y in cl:

# goto(x*30, y*30)

# dot(2, color)

# mainloop()

def clusterEdge(cl):

m = []

for p in cl:

s = 0

for p1 in cl:

s += dist(p,p1)

m.append([s,p])

return max(m)[1]

cen = [clusterEdge(cl) for cl in clusters]

tx = sum(x for x,y in cen)/len(cen)

ty = sum(y for x,y in cen)/len(cen)

print(abs(int(tx*10000)), abs(int(ty*10000)))

[243, 241]
14803 51534

для файла Б

from math import dist
from turtle import*
from random import*
f = open('ege-inf-zad27-7B.txt')
data = []
for s in f:
    x,y = [float(d) for d in s.split()]
    data.append([x,y])
clusters = []
while data:
    cl = [data.pop()]
    for p in cl:
        sosed = [p1 for p1 in data if dist(p,p1) < 1]
        for p1 in sosed:
            cl.append(p1)
            data.remove(p1)
    clusters.append(cl)

clusters = [cl for cl in clusters if len(cl) > 20]
print([len(cl) for cl in clusters])

#
# tracer(0)
# up()
# for cl in clusters:
#     color = random(),random(),random()
#     for x,y in cl:
#         goto(x*30, y*30)
#         dot(2, color)
# mainloop()

def clusterEdge(cl):
    m = []
    for p in cl:
        s = 0
        for p1 in cl:
            s += dist(p,p1)
        m.append([s,p])
    return max(m)[1]

cen = [clusterEdge(cl) for cl in clusters]
tx = sum(x for x,y in cen)/len(cen)
ty = sum(y for x,y in cen)/len(cen)
print(abs(int(tx*10000)), abs(int(ty*10000)))

from math import dist

from turtle import*

from random import*

f = open('ege-inf-zad27-7B.txt')

data = []

for s in f:

x,y = [float(d) for d in s.split()]

data.append([x,y])

clusters = []

while data:

cl = [data.pop()]

for p in cl:

sosed = [p1 for p1 in data if dist(p,p1) < 1]

for p1 in sosed:

cl.append(p1)

data.remove(p1)

clusters.append(cl)

clusters = [cl for cl in clusters if len(cl) > 20]

print([len(cl) for cl in clusters])

# tracer(0)

# up()

# for cl in clusters:

# color = random(),random(),random()

# for x,y in cl:

# goto(x*30, y*30)

# dot(2, color)

# mainloop()

def clusterEdge(cl):

m = []

for p in cl:

s = 0

for p1 in cl:

s += dist(p,p1)

m.append([s,p])

return max(m)[1]

cen = [clusterEdge(cl) for cl in clusters]

tx = sum(x for x,y in cen)/len(cen)

ty = sum(y for x,y in cen)/len(cen)

print(abs(int(tx*10000)), abs(int(ty*10000)))

[2496, 2512, 2473, 2499]
216297 43456

Ответ:

14803 51534
216297 43456