Задание №88382. Учёный решил провести кластеризацию некоторого множества звёзд

Задание №88382 ЕГЭ Информатике

Условие задания #88382

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

Истинный центр кластера, или центроид,  — это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками A(x₁, y₁) и B(x₂, y₂) на плоскости, которое вычисляется по формуле:

$d (A, B) = \sqrt{({(x_{2} - x_{1})}^{2} + {(y_{2} - y_{1})}^{2})}$

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

В файле Б хранятся данные о звёздах трёх кластеров, где H  =  3, W  =  3 для каждого кластера. Известно, что количество звёзд не превышает 10 000.

Структура хранения информации о звездах в файле Б аналогична файлу А.

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

В ответе запишите четыре числа: в первой строке сначала целую часть произведения P_x × 10 000 , затем целую часть произведения P_y × 10 000 для файла А, во второй строке  — аналогичные данные для файла Б.

27-11a.txt 27-11b.txt

Ответ

Ответ:

29778 45839 33242 39939

Решение

Файл A

K = 2 # количество кластеров

def findClusterNo( x, y ):
return 0 if y < 2*x-1 else 1

#------------------------------------------------

clusters = [ [] for i in range(K) ]

for s in open("27-11a.txt"):
x, y = s.replace(',','.').split()
x, y = float(x), float(y)
clusterNo = findClusterNo( x, y )
clusters[clusterNo].append( (x, y) )

import math
def dist( p1, p2 ):
#return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
return math.hypot( p1[0] - p2[0], p1[1] - p2[1] )

centers = []
for k in range(K):
minSumDist = float('inf')
for pCenter in clusters[k]:
sumDist = sum( dist(pCenter,p)
for p in clusters[k] )
if sumDist < minSumDist:
minSumDist = sumDist
center = pCenter
centers.append( center )

print( "Центроиды:\n", centers )

sumX, sumY = 0, 0
for k in range(K):
sumX += centers[k][0]
sumY += centers[k][1]

print( int(sumX/K*10000), int(sumY/K*10000) )

#------------------------------------------------
# Метод k-средних
#------------------------------------------------

def findNearest( p0, data ):
return sorted( (dist(p0, p), p) for p in data )[0][1]

from random import random
centers = [ (x+random()*2, y+random()*2) for x, y in centers ]
centers = [ findNearest(centers[k], clusters[k]) for k in range(K) ]
for _ in range(20):
allData = sum( (x for x in clusters), [] )
clusters = [ [] for _ in range(K) ]
for p in allData:
pCenter = findNearest(p, centers)
clusters[centers.index(pCenter)].append( p )
for k in range(K):
lenK = len(clusters[k])
centers[k] = sum( x for x, y in clusters[k] ) / lenK, \
sum( y for x, y in clusters[k] ) / lenK
centers[k] = findNearest(centers[k], clusters[k])

sumX, sumY = 0, 0
for k in range(K):
sumX += centers[k][0]
sumY += centers[k][1]

print( "\nМетод k-средних дает НЕВЕРНЫЙ ответ" )
print( "Центроиды:\n", centers )

print( int(sumX/K*10000), int(sumY/K*10000) )

Файл B

K = 3 # количество кластеров

def findClusterNo( x, y ):
return 0 if y > 5 else \
1 if y > -x+5.5 else \
2

#------------------------------------------------

clusters = [ [] for i in range(K) ]

for s in open("11/27-11b.txt"): x, y = s.replace(',','.').split()
x, y = float(x), float(y)
clusterNo = findClusterNo( x, y )
clusters[clusterNo].append( (x, y) )

import math
def dist( p1, p2 ):
#return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
return math.hypot( p1[0] - p2[0], p1[1] - p2[1] )

print( "Центроиды:\n", centers )

sumX, sumY = 0, 0
for k in range(K):
sumX += centers[k][0]
sumY += centers[k][1]

print( int(sumX/K*10000), int(sumY/K*10000) )

#------------------------------------------------
# Метод k-средних
#------------------------------------------------

def findNearest( p0, data ):
return sorted( (dist(p0, p), p) for p in data )[0][1]

sumX, sumY = 0, 0
for k in range(K):
sumX += centers[k][0]
sumY += centers[k][1]

print( "\nМетод k-средних дает НЕВЕРНЫЙ ответ" )
print( "Центроиды:\n", centers )

print( int(sumX/K*10000), int(sumY/K*10000) )

Понятно ли решение?

Авторизуйся, чтобы посмотреть решение

Активируй TG-бот через QR-код или по кнопке
Введи код авторизации из TG-бота

Активировать TG-бот

Решения от учеников

Задание №88376 Задание №88377 Задание №88378 Задание №88379 Задание №88380 Задание №88381 Задание №88382 Задание №88383 Задание №88384 Задание №88385 Задание №88386 Задание №88387 Задание №88388 Задание №88389 Задание №88374

Бесплатно

Скачивай наш Тренажер ЕГЭ на iPhone или Android и тренируйся в любое время и в любом месте!