Статья Автор: Лебедев Дмитрий

Решение заданий модели m597

Доктор Браун допустил ошибку при выставлении даты на машине времени и Марти МайФлай оказался 2520 году.
Марти, для возвращения назад, должен по карте определить столицы двух больших районов Калифорнии.

Район (кластер) – это группа домов, координаты которых находятся внутри прямоугольника высотой H и шириной W.
Каждый дом обязательно принадлежит только одному району.
Столица района (или центроид) – это такой дом, сумма манхэттенских расстояний от которого до всех других домов района (кластера) минимальна.
Манхэттенское расстояние между двумя точками A(x1,y1) и B(x2,y2) вычисляется по формуле: d(A,B)=∣x2−x1∣+∣y2−y1∣

В файле A хранятся данные о двух районах Хипл-Вэллии, а в файле Б данные о трех районах Лос-Анджелеса.
Структура файлов с данными одинаковая:

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

Для каждого файла определите

координаты столицы (центра) каждого района (кластера),
затем вычислите два числа:
- Px – среднее арифметическое абсцисс центров кластеров,
- Py – среднее арифметическое ординат центров кластеров.
В ответе запишите четыре числа:
- в первой строке сначала целую часть произведения Px×10000,
  затем целую часть произведения Py×10000 для файла А,
- во второй строке – аналогичные данные для файла Б.

Действие 1 - Считываем точки и рисуем "точечную диаграмму" с помощью MATPLOTLIB
Для удобства, нужный файл выбирается по номеру (по умолчанию выбирается файл А из демоварианта)
Введите номер файла и посмотрите на результат

import matplotlib.pyplot as plt
fnames = {'A1':'27A_m597A.txt', 'B1': '27B_m597A.txt'}
fnames['A2'] = '27A_m597B.txt'; fnames['B2'] ='27B_m597B.txt'
fnames['9A1'] = '27A_m599A.txt'; fnames['9B1'] ='27B_m599A.txt'
krej = input()
if (krej in fnames) == False :
    krej = list(fnames)[0]
fname = fnames[krej]
# считывание данных 
XX, YY = [], []
for s in open(fname):
  s = s.replace(',','.')
  x, y = map(float, s.split())
  XX.append(x)
  YY.append(y)
print(fname,len(XX))
# Построение точечного графика с настройками
plt.scatter(XX, YY, color='blue', marker='.')
plt.show()
dots_all = {'A1': ((-8,0), (1,5)),'B1': ((-5,-8),(-1,-7),(-4,0)) }
dots_all ['A2'] = ((3.5,5), (5,25)); dots_all['B2'] = ((-4,-6),(-2,6),(4,6))
dots_all ['9A1'] = ((-5,6), (-3,2)); dots_all['9B1'] = ((-8,-2),(-5,2),(-2,2))

Рисуем разноцветные кластеры

import matplotlib.pyplot as plt
def next_dot (pos,dt): # подпрограмма выбирает ближайшую из набора
  # отбор по квадрату расстояния до точки
  ans, r = dt[0][2], (pos[0]-dt[0][0])**2+(pos[1]-dt[0][1])**2
  for i in range(1,len(dt)):
    ri = (pos[0]-dt[i][0])**2+(pos[1]-dt[i][1])**2
    if ri < r :
      ans, r = dt[i][2], ri
  return ans

# описание для всех заданий модели
fnames = {'A1':'27A_m597A.txt', 'B1': '27B_m597A.txt'}
fnames['A2'] = '27A_m597B.txt'; fnames['B2'] ='27B_m597B.txt'
fnames['9A1'] = '27A_m599A.txt'; fnames['9B1'] ='27B_m599A.txt'
dots_all = {'A1': ((-8,0,0), (1,5,1)),'B1': ((-5,-8,0),(-1,-7,1),(-4,0,2)) }
dots_all ['A2'] = ((3.5,5,0), (5,25,1)); dots_all['B2'] = ((-4,-6,0),(-2,6,1),(4,6,2))
dots_all ['9A1'] = ((-5,6,0), (-3,2,1)); 
dots_all['9B1'] = ((-8,0,0),(-7,-3,0),(-5,2,1),(-4,4,1),(-2,2,2),(-1,3,2))
krej = input()
if (krej in fnames) == False :
    krej = list(fnames)[0]
fname, dots = fnames[krej], dots_all[krej]  
DDD = dict() # словарь кластеров 
for i in range(len(dots)) :
  if dots[i][2] in DDD : continue
  DDD[dots[i][2]] = [] # инициализация значений
for s in open(fname): # считывание точек
  s = s.replace(',','.')
  x, y = map(float, s.split()) 
  i = next_dot((x,y),dots) # выбор кластера
  DDD[i].append((x,y)) # добавление в кластер
print([(i,len(DDD[i])) for i in DDD]) # печать размеров кластеров


# вывод раскраски кластеров
colors = [ 'red','blue','green','brown','black']
for i in DDD :
  X = [ xy[0] for xy in DDD[i]]
  Y = [ xy[1] for xy in DDD[i]]
  plt.scatter(X, Y, color=colors[i%5], marker='.')
plt.grid()
plt.show()

Построим решение задания. Будем придерживаться следующей схемы

Определяем "опроные точки" кластеров (с помощью MATPLOTLOB или EXCEL или TURTLES или ...
записаны в dots_all визуальным поиском
Разбиваем точки на кластеры методом "поиска ближайшей опроной точки".
Для храниния точек в кластере используем словарь,
Выводим размеры кластеров.
Для каждого кластера находим "среднюю точку" и сортируем по расстоянию до "средней точки"
Для каждого кластера находим "истинный центроид" методом перебора с отсевом по "порогу"
Для полученных значений "истинных центроидов" находим отве

Обработку кластера выделим в отдельную процедуру

def next_dot (pos,dt): # подпрограмма выбирает ближайшую из набора
  # отбор по квадрату расстояния до точки
  ans, r = dt[0][2], (pos[0]-dt[0][0])**2+(pos[1]-dt[0][1])**2
  for i in range(1,len(dt)):
    ri = (pos[0]-dt[i][0])**2+(pos[1]-dt[i][1])**2
    if ri < r :
      ans, r = dt[i][2], ri
  return ans
def sum_rast (dot,kl,porog = float('inf')): 
  # вычисление суммы евклидовых расстояний от dot до всех точек набора kl
  # необязательный парамерт порог вызывает прекращение вычислений при достижении porog
  ans = 0 # инициализация ответа
  for xy in kl :
    r = (dot[0]-xy[0])*(dot[0]-xy[0])+(dot[1]-xy[1])*(dot[1]-xy[1])
    ans += r ** 0.5
    #r = abs(dot[0]-xy[0])+abs(dot[1]-xy[1])
    #ans += r 
    if ans > porog : return float('inf')
  return ans  
def sred_dot (kl) : # получение "средней точки"
  m = len(kl)
  gxy = (sum([dot[0] for dot in kl]) / m, sum([dot[1] for dot in kl]) / m) 
  return gxy
def kin_dza_dza(kl): # обработка кластера
  gxy = sred_dot(kl) # получение "средней точки"
  # сортировка по расстоянию до средней точки
  kl.sort(key = lambda dot : (dot[0]-gxy[0])**2 + (dot[1]-gxy[1])**2 )
  # поиск "истинного центроида"
  sr_min, index = sum_rast(kl[0],kl), 0
  for i in range (1, len(kl)):
    sr = sum_rast(kl[i],kl,sr_min)
    if sr < sr_min : 
      sr_min, index = sr, i
  return kl[index]
# описание для всех заданий модели
fnames = {'A1':'27A_m597A.txt', 'B1': '27B_m597A.txt'}
fnames['A2'] = '27A_m597B.txt'; fnames['B2'] ='27B_m597B.txt'
fnames['9A1'] = '27A_m599A.txt'; fnames['9B1'] ='27B_m599A.txt'
dots_all = {'A1': ((-8,0), (1,5)),'B1': ((-5,-8),(-1,-7),(-4,0)) }
dots_all ['A2'] = ((3.5,5), (5,25)); dots_all['B2'] = ((-4,-6),(-2,6),(4,6))
dots_all ['9A1'] = ((-5,6,0), (-3,2,1)); 
dots_all['9B1'] = ((-8,0,0),(-7,-3,0),(-5,2,1),(-4,4,1),(-2,2,2),(-1,3,2))
krej = input()
if (krej in fnames) == False :
    krej = list(fnames)[0]
fname, dots = fnames[krej], dots_all[krej]  
DDD = dict() # словарь кластеров 
for i in range(len(dots)) :
  if dots[i][2] in DDD : continue
  DDD[dots[i][2]] = [] # инициализация значений
for s in open(fname): # считывание точек
  s = s.replace(',','.')
  x, y = map(float, s.split()) 
  i = next_dot((x,y),dots) # выбор кластера
  DDD[i].append((x,y)) # добавление в кластер
print([(i,len(DDD[i])) for i in DDD]) # печать размеров кластеров
ans = []  
for i in DDD :
  rez = kin_dza_dza(DDD[i])
  ans.append(rez)
rez = sred_dot(ans)  
print(ans)
print(int(rez[0]*100000),int(rez[1]*100000))  
#'''

# для тренировки

from math import dist

size = 10
index = 10000

m = [tuple(map(float, s.replace(',', '.').split())) for s in open('27B_m597B.txt', 'r')]
cl = ['red', 'blue', 'green']
p = [(-4, 2, cl[0]), (4, 5, cl[1]), (5, 11, cl[2])]


def findCluster(d, p):
    return min([(dist((x0, y0), d), cl) for x0, y0, cl in p])[1]

clusters = [(list(d for d in m if findCluster(d, p) == c), c) for c in cl]

from turtle import *
tracer(0)
up()

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

update()

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

centers = [center(cl) for cl, c in clusters]


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))

Прикрепленные файлы
27A_m597A.txt
27A_m597B.txt
27A_m599A.txt
27B_m597A.txt
27B_m597B.txt
27B_m599A.txt

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

Печать