Задание 27 · Анализ данных
Практика и итог
Вся тема на одной странице: как решилась задача темы, главное из подтем, порядок решения и частые ошибки.
Одна задача — вся тема
Задача темы — частицы из файла 27-4.txt: Q₁ по парам с признаком II и Q₂ по центрам — собиралась из функций всех пяти основных подтем. Пролистай версии: точками отмечены строки, которых не было в предыдущей.
- Подтема 1, «Точки и файл»: частица — запись, энергия — функция. Точками отмечены новые строки.
- Подтема 2, «Разделение на кластеры»: границы в пустых промежутках.
- Подтема 3, «Центр кластера»: центр — перебор кандидатов.
- Подтема 4, «Ответ по центрам»: ответ из центров по условию.
- Подтема 5, «Расстояния и пары»: пары — внутри каждого кластера. Ответ задачи темы — 772010 125026.
Четыре шага одни и те же в любом задании 27: прочитать записи, разделить на кластеры, найти центры по определению из условия и собрать ответ. Дополнительный урок добавляет соседей, другие определения центра и статистику.
Карта темы
Каждая подтема дала один шаг решения, и любое решение собирается из них. Сверху — путь от файла к ответу, ниже — по блоку на подтему. Заголовок блока ведёт на подтему.
- Записипрочитать файл и построить рисунок
- Кластерыкаждая точка — ровно в одну группу
- Ответцентры и величины из условия
1Точки, расстояния и файл
dist(a, b)√(Δx² + Δy²); с порогом — квадратыreplace(",", ".").split()запятая, пробелы и табуляция- x = r · cos φугол — через radians
2Разделение на кластеры
if / elif / elseодна группа на точку, порядок важенnoiseаномалии — отдельно, не в последний кластер- границыв пустых промежутках: по координате, углу, энергии
3Центр кластера
total = 0.0внутри цикла: новая сумма для каждого кандидата- средняя точкане центр: центр — одна из точек
center_sum(g, energy_gap)своя формула расстояния из условия
4Ответ по центрам
- Pₓ, P_yсредние координат центров
- × 10000, intцелая часть, а не round
5Расстояния и пары точек
- пары i < jкаждая пара один раз
- внутри кластерасписок отобранных — заново в каждом
6Соседи, другие центры и статистикадополнительный урок
- другой центрминимакс, сумма квадратов, точка наведения
Как решать
Любое задание 27 решается одним порядком из пяти шагов. Каждому шагу ты уже учился — под ним номера подтем:
Проверочный рисунок: кластеры разными маркерами и центры поверх. Каждая граница должна проходить по пустому месту, а центр — лежать в своём кластере:
Частые ошибки
Восемь ошибок встречаются чаще других, и каждую ловит один вопрос к себе. Выбери ошибку — увидишь, как её исправить, и вопрос, который её ловит:
- запятая
float('1,5')→float('1,5'.replace(',', '.')). Спроси себя: какой разделитель дробной части в файле?подтема 1- градусы
cos(phi)→cos(radians(phi)). Спроси себя: получится ли из (90; 2) точка (0; 2)?подтема 1- последний else
- аномалии попали в последний кластер → явные области и отдельный noise. Спроси себя: сколько точек в noise по условию?подтема 2
- сумма кандидата
- total = 0.0 стоит до внешнего цикла → новая сумма для каждого кандидата. Спроси себя: на пяти точках прямой центр — средняя?подтема 3
- среднее
- средняя точка принята за центр → центр — одна из точек кластера. Спроси себя: есть ли такая точка в файле?подтема 3
- формула
- центр по dist, а в условии разность энергий → center_sum(g, energy_gap). Спроси себя: какое «расстояние» в определении центра?подтема 3
- модуль и round
round(q * 10000)→int(q * 10000). Спроси себя: просят целую часть или округление?подтема 4- пары вне кластера
- пары собраны по всему файлу → список отобранных — заново в каждом кластере. Спроси себя: могут ли точки пары быть из разных кластеров?подтема 5
Итог
Тема пройдена: задача темы решена от чтения файла до ответа 772010 125026. Вот что взять с собой.
- ПорядокЗаписи, кластеры, центры, ответ, проверка.
- КластерыКаждая точка — в одну группу, аномалии отдельно.
- ЦентрПеребор точек по формуле из условия.
- ОтветПары — внутри кластера, int, а не round.
- Задача темыQ₁ · 10000 = 772010, Q₂ · 10000 = 125026.
Проверьте себя
Ответь сначала сам, потом открой ответ.
Почему центр кластера ищут перебором точек, а не берут среднее координат?
ОтветСкрыть ответ
По определению центр — одна из точек кластера с наименьшей суммой расстояний. Средняя точка в файле может и не встретиться.
Сумма размеров кластеров и аномалий совпала с числом точек. Значит, разделение верно?
ОтветСкрыть ответ
Не обязательно: одну точку можно потерять, а другую учесть дважды. Нужен проверочный рисунок.
Как в задаче темы частица попадает в свою группу?
ОтветСкрыть ответ
Номер группы — сколько границ 3.5, 7, 10.5 её энергия превысила: sum(energy(p) > b for b in bounds).
Получилось Q₁ = 3.14159. Что записать в ответ при «целая часть произведения на 10 000»?
ОтветСкрыть ответ
31415: int(3.14159 * 10000) — дробную часть отбрасывают, а не округляют.
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Расстояние между центрами
В файле 27-1.txt записаны точки двух кластеров. Найди расстояние между центрами кластеров. В ответе запиши целую часть произведения найденного расстояния на 10 000.
Введите число.
Подсказка
Граница x = 6, центры по сумме расстояний.
Решение
65667.
Решение программой
from math import dist def read_points(filename): points = [] with open(filename, encoding='utf-8-sig') as f: for line in f: parts = line.replace(',', '.').split() points.append((float(parts[0]), float(parts[1]))) return points def center_sum(cluster): best_point = cluster[0] best_sum = float('inf') for candidate in cluster: total = 0.0 for point in cluster: total += dist(candidate, point) if total < best_sum: best_sum = total best_point = candidate return best_point left, right = [], []for p in read_points('27-1.txt'): if p[0] < 6: left.append(p) else: right.append(p) d = dist(center_sum(left), center_sum(right))print(int(d * 10000))Ответ: 65667
Точки чужого кластера
В файле 27-2.txt записаны точки трёх кластеров и ровно три аномалии. Найди наибольшее расстояние от центра кластера с наименьшим количеством точек до точки кластера с наибольшим количеством точек. В ответе запиши целую часть произведения найденного расстояния на 10 000.
Введите число.
Подсказка
Центр маленького кластера, а точки — из самого большого.
Решение
126711.
Решение программой
from math import dist def read_points(filename): points = [] with open(filename, encoding='utf-8-sig') as f: for line in f: parts = line.replace(',', '.').split() points.append((float(parts[0]), float(parts[1]))) return points def center_sum(cluster): best_point = cluster[0] best_sum = float('inf') for candidate in cluster: total = 0.0 for point in cluster: total += dist(candidate, point) if total < best_sum: best_sum = total best_point = candidate return best_point clusters = [[], [], []]for x, y in read_points('27-2.txt'): if -8 < x < 0 and 2 < y < 10: clusters[0].append((x, y)) elif 1 < x < 10 and 2 < y < 10: clusters[1].append((x, y)) elif -2 < x < 5 and -7 < y < 1: clusters[2].append((x, y))clusters.sort(key=len)centers = [center_sum(c) for c in clusters] far = max(dist(centers[0], p) for p in clusters[-1])print(int(far * 10000))Ответ: 126711
Белые карлики большого кластера
В файле 27-3.txt записаны звёзды трёх кластеров. Определи количество белых карликов (класс светимости VII) в кластере с наибольшим количеством звёзд.
Введите число.
Подсказка
Сначала самый большой кластер, затем коды VII.
Решение
20.
Решение программой
from math import dist def center_sum(cluster): best_point = cluster[0] best_sum = float('inf') for candidate in cluster: total = 0.0 for point in cluster: total += dist(candidate, point) if total < best_sum: best_sum = total best_point = candidate return best_point stars = []with open('27-3.txt', encoding='utf-8-sig') as f: for line in f: sx, sy, code = line.replace(',', '.').split() stars.append((float(sx), float(sy), code)) clusters = [[], [], []]for s in stars: if s[1] < 5: clusters[0].append(s) elif s[0] < 10: clusters[1].append(s) else: clusters[2].append(s) def is_kind(code, cls, lum): return code[0] == cls and code[2:] == lum big = max(clusters, key=len)print(sum(s[2] == 'VII' for s in big))Ответ: 20
Кластеры в секторах
В файле 27-5.txt записаны точки трёх кластеров; каждый лежит внутри сектора радиуса 15 с центральным углом 20° и вершиной в точке C (2; −1). Найди Pₓ и P_y — средние арифметические абсцисс и ординат центров кластеров. В ответе запиши целые части произведений |Pₓ| · 10 000 и |P_y| · 10 000.
Введите два целых числа через пробел.
Подсказка
Угол направления из вершины C (2; −1); сектор начинается с угла start и имеет ширину 20°.
Решение
22208 11252.
Решение программой
from math import dist def read_points(filename): points = [] with open(filename, encoding='utf-8-sig') as f: for line in f: parts = line.replace(',', '.').split() points.append((float(parts[0]), float(parts[1]))) return points def center_sum(cluster): best_point = cluster[0] best_sum = float('inf') for candidate in cluster: total = 0.0 for point in cluster: total += dist(candidate, point) if total < best_sum: best_sum = total best_point = candidate return best_point from math import atan2, degrees clusters = [[], [], []]for p in read_points('27-5.txt'): a = degrees(atan2(p[1] + 1, p[0] - 2)) % 360 for k, start in enumerate([350, 110, 230]): if (a - start) % 360 <= 20: clusters[k].append(p)centers = [center_sum(c) for c in clusters]px = abs(sum(c[0] for c in centers) / 3)py = abs(sum(c[1] for c in centers) / 3)print(int(px * 10000), int(py * 10000))Ответ: 22208 11252
Центры звёзд в полярных координатах
В файле 27-7.txt записаны звёзды двух кластеров в полярных координатах: в каждой строке — полярный угол φ в градусах и полярный радиус r. Кластеры лежат в разных секторах круга с центром в начале координат. Центр кластера — его звезда с наименьшей суммой расстояний до остальных звёзд кластера; расстояния считай на обычной плоскости. Найди Pₓ и P_y — средние арифметические абсцисс и ординат центров кластеров. В ответе запиши целые части произведений Pₓ · 10 000 и P_y · 10 000.
Введите два числа через пробел в том порядке, в каком их спрашивают.
Подсказка
Переведи точки в x и y; кластеры удобно разделить по углу φ ещё до перевода.
Решение
Секторы — около 15–35° и 100–125°: граница φ = 60 проходит по пустому месту.
Решение программой
from math import cos, sin, radians, dist clusters = [[], []]with open('27-7.txt') as f: for line in f: phi, r = map(float, line.replace(',', '.').split()) a = radians(phi) k = 0 if phi < 60 else 1 clusters[k].append((r * cos(a), r * sin(a))) def center(cl): return min(cl, key=lambda c: sum(dist(c, p) for p in cl)) cs = [center(c) for c in clusters]px = sum(c[0] for c in cs) / 2py = sum(c[1] for c in cs) / 2print(int(px * 10000), int(py * 10000))Ответ: 25246 35917