Задача к ЕГЭ по информатике на тему «Анализ данных (звезды)» №5

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

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

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

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

∘ -------------------- d(A, B) = (x2 − x1)2 + (y2 − y1)2

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

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

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

В ответе запишите четыре числа через пробел: сначала целую часть произведения $Px ⋅1000$ для файла А и $Py ⋅1000$ для файла А, далее целую часть деления $Px ⋅1000$ для файла Б и $Py ⋅1000$ для файла Б.

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

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

Для начала визуально оценим данные в условии кластеры. Для этого откроем предложенные файлы в $Excel$ , перейдем в раздел «Вставка $→$ Диаграммы $→$ Точечная».

Диаграмма для файла А имеет вид:

Просто разделить кластеры с помощью прямых не получится. Воспользуемся методом DBSCAN:

Код программы для файла А:

from math import dist

f = open(’2_A.txt’)
s = f.readline()
# Сохраняем массив данных
st = [list(map(float, i.replace(’,’, ’.’).split())) for i in f]

# Массив с кластерами
# Вначале находим по одной точке в файле, принадлежащей каждому кластеру -- это будет начальная точка для алгоритма DBSCAN.
# Отобрать их можно либо анализом первых точек в Excel файле, либо программным способом
a = [[[st[0][0], st[0][1]]], [[st[1][0], st[1][1]]], [[st[10][0], st[10][1]]]]
st.pop(10), st.pop(1), st.pop(0)

# Реализация метода DBSCAN
for k in range(3):
    for star in a[k]:  # Перебираем звёзды среди звёзд кластера
        for i in range(len(st)):  # Перебираем необработанные звёзды
            if st[i] != ’*’:
                # При dist >= 0.3 два кластера попадают друг в друга
                if dist(st[i], star) < 0.2:
                    a[k].append(st[i])
                    st[i] = ’*’

sum_x = sum_y = 0  # Переменные для суммы абсцисс и ординат центров
for i in a:
    tx = ty = 0  # Координаты текущего центра кластера
    mn = 100000050000  # Минимальное расстояние
    for j in i:  # Перебор предполагаемого центроида
        sm = 0  # Суммарное расстояние
        for k in i:  # Перебор остальных звёзд для вычисления расстояний
            sm += dist(k, j)
        if sm < mn:
            mn = sm
            tx, ty = j
    sum_x += tx
    sum_y += ty

print(int(sum_x / 3 * 1000))
print(int(sum_y / 3 * 1000))

Диаграмма для файла Б имеет вид:

Просто разделить кластеры с помощью прямых не получится. Воспользуемся методом DBSCAN:

Код программы для файла Б:

from math import dist

f = open(’2_B.txt’)
s = f.readline()
# Сохраняем массив данных
st = [list(map(float, i.replace(’,’, ’.’).split())) for i in f]

# Массив с кластерами
# Вначале находим по одной точке в файле, принадлежащей каждому кластеру -- это будет начальная точка для алгоритма DBSCAN.
# Отобрать их можно либо анализом первых точек в Excel файле, либо программным способом
a = [
    [[st[0][0], st[0][1]]],
    [[st[1][0], st[1][1]]],
    [[st[2][0], st[2][1]]],
    [[st[3][0], st[3][1]]],
    [[st[4][0], st[4][1]]],
    [[st[6][0], st[6][1]]]
]
st.pop(6), st.pop(4), st.pop(3), st.pop(2), st.pop(1), st.pop(0)

# Реализация метода DBSCAN
for k in range(6):
    for star in a[k]:  # Перебираем звёзды среди звёзд кластера
        for i in range(len(st)):  # Перебираем необработанные звёзды
            if st[i] != ’*’:
                # При dist >= 0.3 два кластера попадают друг в друга
                if dist(st[i], star) < 0.2:
                    a[k].append(st[i])
                    st[i] = ’*’

sum_x = sum_y = 0  # Переменные для суммы абсцисс и ординат центров
for i in a:
    tx = ty = 0  # Координаты текущего центра кластера
    mn = 100000050000  # Минимальное расстояние
    for j in i:  # Перебор предполагаемого центроида
        sm = 0  # Суммарное расстояние
        for k in i:  # Перебор остальных звёзд для вычисления расстояний
            sm += dist(k, j)
        if sm < mn:
            mn = sm
            tx, ty = j
    sum_x += tx






































































































































































































    sum_y += ty

print(int(sum_x / 6 * 1000))
print(int(sum_y / 6 * 1000))

Ответ: 1042 -1688 -280 200