27.03 Кластеры нестандартной формы
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Учёный Галлей, увлечённый астрономией, решил исследовать звёздное небо и провести кластеризацию звёзд по их расположению на карте. Каждая звезда представлена точкой на графике, а кластер звёзд – это набор точек, лежащих внутри прямоугольника. Каждая звезда обязательно принадлежит только одному из кластеров.
Центр звёздного скопления – это одна из звёзд, сумма расстояний от которой до всех остальных звёзд в кластере минимальна. Галлей считает, что эта звезда является ключевой для понимания структуры скопления.
Под расстоянием понимается расстояние Евклида между двумя точками 
и 
на плоскости, которое
вычисляется по формуле:
Аномалиями назовём точки, находящиеся на расстоянии не менее R условных единиц от точек кластеров. При расчётах аномалии учитывать не нужно. Координатная четверть, в которой лежит больше всего центров звёздных скоплений, считается зоной повышенной чувствительности. Кластеры, центры которых расположенные в данной зоне, считаются ложными, и не используются учёным в дальнейших расчётах.
В файле А хранятся данные о четырех кластерах звёзд, где 
для каждого кластера. В каждой строке
записана информация о расположении одной звезды: сначала координата 
, затем координата 
. Значения даны в
условных единицах, которые представлены вещественными числами. Известно, что количество звёзд не превышает
1000.
В файле Б хранятся данные о шести кластерах звёзд, где 
для каждого кластера. Известно, что
количество звёзд не превышает 10000. Структура хранения информации о звёздах в файле Б аналогична файлу
А.
Для каждого файла определите координаты центра звёздного скопления каждого кластера, затем вычислите два числа:
– среднее арифметическое абсцисс центров звёздных скоплений, и 
– среднее арифметическое ординат центров
звёздных скоплений. Если в каждой четверти лежит одинаковое количество центров звёздных скоплений, считать 
и
равными 0.
В ответе запишите четыре числа через пробел: сначала целую часть произведений 
и 
для файла А,
далее целую часть произведения 
и 
для файла Б.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемого файла.
Для начала визуально оценим данные в условии кластеры. Для этого откроем предложенные файлы в 
, перейдем в
раздел «Вставка 
Диаграммы 
Точечная».
Диаграмма для файла А имеет вид:
Разделить все кластеры с помощью прямых не получится. Воспользуемся методом DBSCAN:
Код программы для файла А:
from math import *
f = open(’3A.txt’)
s = f.readline()
a = [list(map(float, i.replace(’,’, ’.’).split())) for i in f]
# Вначале находим по одной точке в файле, принадлежащей каждому кластеру - это будет начальная точка для кластера
# Отобрать их можно либо анализом первых точек в Excel файле, либо программным способом
# Также нужно учесть, что кластер может принадлежать синусоиде
cl = [[[a[0][0], a[0][1]]], [[a[7][0], a[7][1]]], [[a[2][0], a[2][1]]], [[a[9][0], a[9][1]]]]
a.pop(9), a.pop(7), a.pop(2), a.pop(0)
for k in range(4):
for j in cl[k]:
for i in range(len(a)):
if a[i] != ’*’:
p = [a[i][0], a[i][1]]
if dist(p, j) < 0.45:
cl[k].append(p)
a[i] = ’*’
s_xy = []
for i in cl:
tx = ty = 0 # Координаты текущего центра кластера
mn = 100000050000 # Минимальное расстояние
for j in i:
x1, y1 = j
sm = 0 # Суммарное расстояние
for k in i:
x2, y2 = k
sm += ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
if sm < mn:
mn = sm
tx, ty = x1, y1
s_xy.append([tx, ty, 0])
coords = [0, 0, 0, 0]
for i in s_xy:
if i[0] > 0 and i[1] > 0:
coords[0] += 1
i[2] = 1
elif i[0] > 0 and i[1] < 0:
coords[3] += 1
i[2] = 4
elif i[0] < 0 and i[1] > 0:
coords[1] += 1
i[2] = 2
elif i[0] < 0 and i[1] < 0:
coords[2] += 1
i[2] = 3
if coords.count(coords[0]) == 4: # Если количество центров кластеров одинаково во всех координатных плоскостях
print(0, 0) # Ответом будет 0, 0
else: # В противном случае, рассматриваем центры кластеров
mx = coords.index(max(coords)) + 1 # Координатная четверть, в которой лежит максимальное количество центров кластеров
s_ost = [i for i in s_xy if i[2] != mx]
sum_x = sum(i[0] for i in s_ost)
sum_y = sum(i[1] for i in s_ost)
print(int(sum_x * 100 / len(s_ost)), int(sum_y * 100 / len(s_ost)))
Диаграмма для файла Б имеет вид:
Разделить все кластеры с помощью прямых не получится. Воспользуемся методом DBSCAN:
Код программы для файла Б:
from math import *
f = open(’3B.txt’)
s = f.readline()
a = [list(map(float, i.replace(’,’, ’.’).split())) for i in f]
# Вначале находим по одной точке в файле, принадлежащей каждому кластеру - это будет начальная точка для кластера
# Отобрать их можно либо анализом первых точек в Excel файле, либо программным способом
# Также нужно учесть, что кластер может принадлежать синусоиде
cl = [[[a[40][0], a[40][1]]], [[a[19][0], a[19][1]]], [[a[15][0], a[15][1]]], [[a[16][0], a[16][1]]], [[a[18][0], a[18][1]]], [[a[25][0], a[25][1]]]]
a.pop(40), a.pop(25), a.pop(19), a.pop(18), a.pop(16), a.pop(15)
for k in range(6):
for j in cl[k]:
for i in range(len(a)):
if a[i] != ’*’:
p = [a[i][0], a[i][1]]
if dist(p, j) < 0.4:
cl[k].append(p)
a[i] = ’*’
s_xy = []
for i in cl:
tx = ty = 0 # Координаты текущего центра кластера
mn = 100000050000 # Минимальное расстояние
for j in i:
x1, y1 = j
sm = 0 # Суммарное расстояние
for k in i:
x2, y2 = k
sm += ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
if sm < mn:
mn = sm
tx, ty = x1, y1
s_xy.append([tx, ty, 0])
coords = [0, 0, 0, 0]
for i in s_xy:
if i[0] > 0 and i[1] > 0:
coords[0] += 1
i[2] = 1
elif i[0] > 0 and i[1] < 0:
coords[3] += 1
i[2] = 4
elif i[0] < 0 and i[1] > 0:
coords[1] += 1
i[2] = 2
elif i[0] < 0 and i[1] < 0:
coords[2] += 1
i[2] = 3
if coords.count(coords[0]) == 4: # Если количество центров кластеров одинаково во всех координатных плоскостях
print(0, 0) # Ответом будет 0, 0
else: # В противном случае, рассматриваем центры кластеров
mx = coords.index(max(coords)) + 1 # Координатная четверть, в которой лежит максимальное количество центров кластеров
s_ost = [i for i in s_xy if i[2] != mx]
sum_x = sum(i[0] for i in s_ost)
sum_y = sum(i[1] for i in s_ost)
print(int(abs(sum_x) * 1000 / len(s_ost)), int(abs(sum_y) * 1000 / len(s_ost)))
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
