Задание 27
Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри прямоугольника высотой H и шириной W. Каждая звезда обязательно принадлежит только одному из
кластеров.
Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками A(x1, y1) и B(x2, y2) на плоскости, которое вычисляется по формуле:
В файле A хранятся данные о звёздах двух кластеров, где H=3, W=3 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле Б хранятся данные о звёздах трёх кластеров, где H=3, W=3 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле Б аналогична файлу А.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px – среднее арифметическое абсцисс центров кластеров, и Py – среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть произведения Px × 10 000 , затем целую часть произведения Py × 10 000 для файла А, во второй строке – аналогичные данные для файла Б.
Возможные данные одного из файлов иллюстрированы графиком.
Теория
В задании 27 проверяется умение выполнять последовательность решения задач анализа данных: сбор первичных данных, очистка и оценка качества данных, выбор и построение модели, преобразование данных, визуализация данных, интерпретация результатов - взято из спецификации демонстрационного варианта. Задача творческая и требует комплексного решения: анализ исходных данных, их графическое представление, преобразование и реализация алгоритма обработки.
Решение
Для решения задачи А - откройте файл А.xlsx и проанализируйте его. Далее выделите все данные и постройте точечную диаграмму, время на оформление диаграммы не тратьте.
Видно, что кластеры разделяются по x=1 и y=3 - достаточно в программе использовать одно из этих значений. Открываем теперь текстовый файл с данными - первая строка заголовки, а все данные указаны через запятую (разделитель целой и дробной части чисел). Считываем заголовок, а потом все числа в два массива А и B, заменив в числах запятую на точку. Чисел немного, поэтому используем простой алгоритм перебора всех точек с подсчетом суммы расстояний до других точек, с определением минимального - эта точка и будет центром кластера. Выполняем сначала для кластера А, потом для B. Рекомендуется использовать промежуточный вывод для отладки и контроля.
Результат работы программы
Визуализируйте данные файл Б.xlsx. По вертикальной оси измените цену делений на 1. Видно, что кластеры разделяются по y=4 и y=7.
Аналогично, не меняя алгоритма создайте аналогичную задаче А программу, только с тремя массивами. Чисел больше и программа работает намного дольше, поэтому используйте промежуточный вывод для отладки и контроля. При нахождении среднего не забудьте разделить на 3.
Результат работы программы
Ответ
(Время не более 45 минут)
| 10738 | 30730 |
| 37522 | 51277 |