Задание 27 | Урок №4 — Метод DBSCAN | Информатика ЕГЭ 2025

• Метод дебскан - это упрощенный алгоритм кластеризации для задач ЕГЭ по информатике.  

• Он автоматически разбивает данные по кластерам и обрабатывает аномалии.  

• Работает с кластерами различной формы, включая сложные.  

• Реализация метода занимает всего семь строк кода.  

• Напоминание о предыдущих уроках по методу Камин и обычной кластеризации.  

• Рекомендация посмотреть первые два урока, так как условия задач могут измениться.  

• Автор видео использовал метод дебскан с середины октября и сделал задачу на его применение.  

• Алексей Богданов предложил проверять правильность кластеризации с помощью визуализации.  

• Рекомендация ознакомиться с его реализацией алгоритма дебскан.  

• Автор предлагает свою реализацию метода для ЕГЭ по информатике.  

• Метод дебскан основан на плотности точек в пространстве.  

• Он группирует точки с близкими соседями и помечает аномалии.  

• Алгоритм автоматически определяет количество кластеров.  

• Дебскан рассматривает точки на расстоянии, определенном параметром эпсилон.  

• Точки, находящиеся в эпсилон-окрестности, считаются соседями.  

• Алгоритм проверяет точки одну за другой, пока не найдет все соседи.  

• Эпсилон определяется на глаз или с помощью диаграммы в Excel.  

• Если кластеризация прошла некорректно, параметр эпсилон корректируется.  

• Визуализация помогает проверить правильность кластеризации.  

• Рассматривается сайт для анализа данных.  

• Обсуждается минимальное количество соседей для кластеризации.  

• В ЕГЭ по информатике можно уменьшить минимальное количество соседей до одного.  

• Выбираются случайные точки и находятся соседи.  

• Рекурсивно вычисляется кластеризация для оставшегося набора данных.  

• Аномальные точки выделяются, если они не находят соседей.  

• Увеличение eps уменьшает количество аномальных точек.  

• eps влияет на радиус окрестности и распределение кластеров.  

• Добыскан работает со сложными формами, такими как кольца и улыбки.  

• Добыскан успешно выделяет кластеры, в отличие от Камина.  

• Камин может не справиться с кольцами и сложными формами.  

• Добыскан справляется с различными формами кластеров.  

• Таблица иллюстрирует работу Добыскана и Камина на разных формах кластеров.  

• Добыскан лучше справляется с волнистыми и сложными формами.  

• Камин может давать неверные результаты при близких точках.  

• Добыскан подходит для ЕГЭ по информатике, так как дает больше свободы.  

• Переход к реализации алгоритма и написанию псевдокода.  

• Создание списка кластеров для хранения точек.  

• Идем по всем точкам в наборе данных.  

• Список меняется в процессе прохода, поэтому используем выражение для проверки наличия элементов.  

• Создаем новый кластер из одной точки и добавляем его в список кластеров.  

• Удаляем последний элемент из списка.  

• Находим точки, близкие к текущей, в пределах эпсона.  

• Если расстояние между точками меньше эпсона, добавляем их в текущий кластер.  

• Используем функцию из модуля math для вычисления расстояния между точками.  

• Удаляем уже рассмотренные точки из списка.  

• Копируем список для предотвращения коллизий.  

• Алгоритм выполняет кластеризацию за квадратичное время.  

• Проверяем соседей соседей и так далее.  

• Размер списка меняется в процессе итерирования.  

• Используем списочное выражение для нахождения соседей.  

• Добавляем соседей в текущий кластер и удаляем их из основного списка.  

• Это ускоряет процесс на 20%.  

• Решаем задачу из ЕГЭ по информатике.  

• Используем метод для выделения кластеров.  

• Визуализируем результаты с помощью диаграммы в Excel.  

• Проверка наличия аномалий в данных.  

• Определение расстояния между точками на глаз.  

• Выполнение кластеризации с эпслоном равным двум.  

• Выделение двух кластеров.  

• Написание функции для визуализации данных.  

• Использование модуля черепашки для визуализации.  

• Поднятие хвоста и настройка цветов для кластеров.  

• Визуализация точек в кластерах с разными цветами.  

• Визуализация выделенных кластеров.  

• Проверка правильности выделения точек по цветам.  

• Демонстрация, что точки правильно отнесены к кластерам.  

• Влияние слишком большого и слишком маленького эпслона.  

• Пример с эпслоном 10 и 0.5.  

• Важность правильного выбора эпслона для корректной кластеризации.  

• Переписывание кода для использования метода экстенд.  

• Упрощение кода с помощью склеивания.  

• Демонстрация компактного и эффективного кода.  

• Написание функции для получения центроидов.  

• Добавление суммы расстояний и точек в список.  

• Нахождение минимального элемента для определения центроида.  

• Подсчет среднего арифметического для двух кластеров.  

• Умножение результата на 100000 и округление до целого числа.  

• Проверка правильности расчета.  

• Запускаем код и получаем правильные ответы для файла 455058449904.  

• Код короткий и читаемый, использует короткие имена переменных.  

• Визуализация используется для проверки правильности выбора.  

• Копируем данные из файла B и заменяем запятые на точки.  

• Делим данные на три кластера и запускаем алгоритм.  

• Визуализация помогает проверить распределение данных.  

• Визуализация показывает, что данные объединились в один кластер.  

• Уменьшаем эпслон и снова запускаем кластеризацию.  

• Визуализация показывает три кластера, что соответствует реальности.  

• Проверяем центроиды и убеждаемся в правильности результатов.  

• Алгоритм работает быстро и эффективно.  

• Подходим к решению задач с аномалиями.  

• Открываем новую задачу с аномалиями и кластерами.  

• Находим группы точек с менее чем 30 соседними точками как аномалии.  

• Преобразуем данные и читаем их в основной файл.  

• Читаем данные и создаем список кластеров.  

• Находим соседей для каждой точки и удаляем их из списка.  

• Находим центроиды кластеров и выводим ответ.  

• Отсеиваем кластеры с менее чем 30 точками как аномалии.  

• Строим диаграмму в Excel для проверки.  

• Визуализируем кластеры и аномалии для лучшего понимания.  

• Применяем алгоритм к большему набору данных.  

• Визуализируем результаты и проверяем правильность.  

• Делим данные на три кластера и запускаем кластеризацию.  

• Запускаем кластеризацию и получаем три кластера.  

• Проверяем данные в Excel и видим три группы аномалий.  

• Настраиваем параметр eps для корректного выделения кластеров.  

• Проверяем центроиды и получаем правильный ответ.  

• Визуализация помогает убедиться в правильности кластеризации.  

• На экзамене рекомендуется использовать визуализацию для проверки.  

• Код позволяет решать задачи с любым количеством кластеров.  

• Реализацию можно выбрать по вкусу, но показанная версия самая компактная и простая.  

• Альтернативный вариант кода также работает, но медленнее.  

• Задача 27 легко решается, что сравнимо с задачей 25.  

• Призываем ставить лайки и писать комментарии с идеями по оптимизации кода.  

• Усложнение задач 24 и 26 ожидается, поэтому важно практиковаться.  

• Рекомендация использовать курсы на Stepik для подготовки.  

• Курсы предоставляют разборы, видео, задачи и чат.  

• Промокод на скидку доступен в описании.  

• Призываем делиться видео для увеличения результатов на экзамене.  

• Желаем успешной подготовки и продуктивной работы.