Алгоритм решения задания 27 ЕГЭ по информатике. Часть 3

Навигация по странице

Алгоритм DBSCAN

Это заключительная – третья – часть статьи, в которой мы разбираем решение 27 заданий ЕГЭ разными методами. В этот раз уделим внимание кластеризации данных методом DBSCAN.

Как вы уже могли заметить по прошлым частям, в заданиях ЕГЭ используются сильно упрощённые версии оригинальных алгоритмов кластеризации. С алгоритмом DBSCAN исключений делать не будем. Ранее мы уже писали собственную реализацию этого алгоритма на языке Python. Она вышла довольно обширной, писать столько кода во время экзамена – непозволительная роскошь.

Так что здесь мы оптимизируем и максимально сократим код выведенного ранее алгоритма, при этом сохранив весь необходимый для решения задания функционал. В нашей реализации мы вовсе избавимся от одного из двух задаваемых параметров DBSCAN – maxPts, то есть количество точек нам не придётся задавать вовсе.

Но от второго параметра – eps (минимальный радиус «соседства» точек) – нам никуда не деться. Его мы научимся определять по точечной диаграмме в редакторе электронных таблиц.

Также стоит отметить, что алгоритм DBSCAN – универсальный. То есть с его помощью можно работать с кластерами практически любой формы, а также грамотно определять и отфильтровывать выбросы (аномалии).

Далее в статье мы рассмотрим базовую формулировку 27 задания с самыми обычными кластерами, на основе которой и выведем наш алгоритм. После этого перейдём к более сложным кластерам: серповидным и кластерам с выбросами.

Кластеризация методом DBSCAN

Начнём со следующей формулировки:

Задание 2705

«Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x1, y1) и B(x2, y2) вычисляется по формуле:

$d(A, B) = \sqrt{(x_2-x_1)^2 +(y_2-y_1)^2}$

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

В файле B хранятся данные о звёздах трёх кластеров, где H=13, W=13 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле B аналогична файлу А.

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

В ответе запишите четыре числа: в первой строке сначала абсолютное значение целой части произведения Px × 10 000, затем абсолютное значение целой части произведения Py × 10 000 для файла А, во второй строке – аналогичные данные для файла B»

Сразу перейдём к составлению программы. Большую часть кода мы выводили ранее в прошлых частях этой статьи, так что сейчас подробно остановимся только на главной функции, которую будем использовать в этом подходе – функции dbscan().

Функция принимает на вход список точек (data), который мы предварительно прочитали из текстового файла. Вторым же аргументом будем передавать в функцию значение eps – минимального радиуса соседства точек из одного кластера.

Эта функция берёт список точек и делит его на несколько кластеров по простому правилу:

если точки находятся близко друг к другу (расстояние меньше заданного радиуса eps), то они объединяются в один кластер.
точки, которые находятся далеко от других точек, образуют отдельные кластеры

Сначала объявляем функцию и инициализируем список, в который мы будем добавлять сформированные кластеры:

def dbscan(data, eps=2):
    clusters = []

Далее идёт основной цикл while, который будет работать до тех пор, пока у нас останутся необработанные точки в списке data.

while data:

В этом цикле мы берём методом pop() последнюю точку из data, попутно удаляя её из этого списка. Эта точка становится первой в новом кластере.

Затем создаётся новый кластер, который изначально содержит только эту точку. Её же мы помещаем в уже другой список – queue (очередь). В этой очереди мы будем хранить точки, которые ещё нужно проверить на наличие соседей.

point = data.pop()
cluster = [point]
queue = [point]

Теперь запускаем второй цикл while. Если первый работал, пока в data есть точки, то второй будет работать до тех пор, пока очередь queue не станет пустой. Это значит, что мы проверили всех соседей и кластер больше нельзя расширить.

while queue:

Внутри этого внутреннего цикла мы берём первую точку из очереди методом pop(0), удаляем её из этой очереди и ищем всех её соседей.

current = queue.pop(0)

Как найти всех соседей точки в заданном радиусе? Все очень просто:

мы перебираем все точки, оставшиеся в списке данных (data)
проверяем расстояние (dist) от текущей точки (current) до каждой точки (p)
если расстояние меньше заданного радиуса eps, значит, точка p — это сосед текущей точки. Все такие точки собираем в список neighbors

neighbors = [p for p in data if dist(current, p) < eps]

Соседи найдены, значит расширяем список cluster всеми найденными точками. Теперь все они входят в один кластер. Попутно мы пополняем очередь queue этими же соседями, чтобы в следующей итерации внутреннего цикла while проверить уже их соседей. Так кластер будет постепенно расширяться.

cluster.extend(neighbors)
queue.extend(neighbors)

Добавленные в кластер точки уже проверены. Мы точно определили их как точки одного кластера, больше на них смотреть смысла нет. Значит, нам нужно удалить их из общего списка данных (data), чтобы эти точки повторно не обрабатывались. Это можно сделать таким списковым включением:

data[:] = [p for p in data if p not in neighbors]

Когда очередь queue станет пустой, это значит, что кластер больше расширить невозможно. Мы переходим к следующему шагу: готовый кластер (cluster) добавляем в список кластеров (clusters).

clusters.append(cluster)

Осталось лишь вернуть список clusters из функции. Полный код этой функции представлен ниже:

def dbscan(data, eps):
    clusters = []

    while data:
        point = data.pop()
        cluster = [point]
        queue = [point]

        while queue:
            current = queue.pop(0)
            neighbors = [p for p in data if dist(current, p) < eps]
            cluster.extend(neighbors)
            queue.extend(neighbors)
            data[:] = [p for p in data if p not in neighbors]

        clusters.append(cluster)

    return clusters

Алгоритм, который мы написали, работает по принципу постепенного (рекурсивного) расширения кластеров:

Мы берём произвольную точку из наших данных и начинаем с неё новый кластер. Затем вокруг этой точки «мысленно» рисуем окружность с радиусом eps.
Находим всех соседей, которые попадают внутрь этой окружности, и добавляем их в текущий кластер.
Затем повторяем то же самое для каждой из найденных точек-соседей:
- для каждого соседа снова ищем уже его собственных соседей,
- расширяем текущий кластер за счёт вновь найденных точек.
Этот процесс повторяется рекурсивно (точка → соседи точки → соседи соседей и т.д.), пока в текущем кластере не останется ни одной точки, которую мы не проверили бы на наличие её соседей.
После того, как текущий кластер полностью сформирован и больше расширить его уже нельзя, переходим к следующей необработанной точке и создаём новый кластер аналогичным способом.

Таким образом, точки постепенно объединяются в плотные группы, при этом алгоритм самостоятельно проходит через всех соседей и соседей этих соседей, расширяя кластер в глубину до тех пор, пока не найдёт все точки, расположенные близко друг к другу.

На этом всё, мы оптимизировали и сократили алгоритм DBSCAN и теперь его можно спокойно использовать для решения 27 заданий. А все остальные шаги в решении мы уже рассматривали ранее. Давайте пробежимся по ним и заострим внимание только на вызове функции dbscan(), ведь с этим могут возникнуть трудности.

Импортируем функцию dist() из модуля math, считываем данные из файла и пишем функцию для поиска медоиды.

from math import dist

with open('2705_A.txt') as f:
    next(f)
    data = [tuple(map(float, line.split())) for line in f]


def get_medoid(cluster):
    return min(cluster,
               key=lambda p: sum(dist(p, q) for q in cluster))


def dbscan(data, eps):
    clusters = []

    while data:
        point = data.pop()
        cluster = [point]
        queue = [point]

        while queue:
            current = queue.pop(0)
            neighbors = [p for p in data if
                         dist(current, p) < eps]
            cluster.extend(neighbors)
            queue.extend(neighbors)
            data[:] = [p for p in data if
                       p not in neighbors]

        clusters.append(cluster)

Теперь нужно вызвать функцию dbscan(). Но у вас может возникнуть вопрос: «какое значение передать в качестве второго аргумента eps?».

Для этого нам стоит визуализировать данные из файла A. Точечную диаграмму, как и всегда в этих заданиях, строим в любом редакторе электронных таблиц.

Итак, как правильно подобрать параметр eps? Про правильный и общепринятый способ мы уже знаем из прошлой статьи. Но нам нужно что-то упрощённое и быстрое.

Можем условиться, что наш eps должен быть таким, что:

Хотя бы один сосед самой дальней (навскидку) точки кластера должен входить в окружность радиуса eps
Ни одна точка другого кластера не должна входить в эту окружность

Давайте выберем eps, равный 2. Начертим окружность с таким радиусом вокруг самой правой верхней точки левого нижнего кластера.

Как видно на изображении – сосед этой точки попадает в окружность, а ни одна точка второго кластера не попадает. Значит, можем воспользоваться таким eps.

На деле eps тут должен быть больше 1,9 и меньше 31. При значениях, меньших 1,9 не все точки попадают в кластер и становятся выбросами. Например, у рассмотренной выше точки в радиусе 1,9 не будет ни одного соседа – она станет выбросом.

При значениях, больших 31 в эпсилон-окружность (окружность радиуса eps) граничной точки одного кластера будут попадать точки другого и на выходе здесь получится всего один цельный кластер.

Таким образом, вы можете выбрать любое значение от 1,9 до 31. Мы же остановимся на значении 2. Теперь смело вызываем функцию dbscan() с этим значением и сохраняем результат вызова в переменную clusters.

clusters = dbscan(data, 2)

Давайте удостоверимся, что данные разделились правильно. Для этого можем вывести на экран длину каждого элемента списка cluster. То есть мы получим количество точек в каждом кластере.

print([len(cluster) for cluster in clusters])
>>>[48, 52]

В итоге у нас получились два кластера по 48 и 52 точки в каждом, то есть кластеризация прошла успешно. Теперь ищем медоиды, вычисляем среднее арифметическое по абсциссам и ординатам и выводим на экран ответ к файлу А. Весь код выглядит следующим образом:

from math import dist

with open('2705_A.txt') as f:
    next(f)
    data = [tuple(map(float, line.split())) for line in f]


def get_medoid(cluster):
    return min(cluster,
               key=lambda p: sum(dist(p, q) for q in cluster))


def dbscan(data, eps):
    clusters = []

    while data:
        point = data.pop()
        cluster = [point]
        queue = [point]

        while queue:
            current = queue.pop(0)
            neighbors = [p for p in data if
                         dist(current, p) < eps]
            cluster.extend(neighbors)
            queue.extend(neighbors)
            data[:] = [p for p in data if
                       p not in neighbors]

        clusters.append(cluster)

    return clusters


clusters = dbscan(data, 2)
print([len(cluster) for cluster in clusters])

medoids = [get_medoid(cluster) for cluster in clusters]

px = sum(x for x, y in medoids) / len(medoids)
py = sum(y for x, y in medoids) / len(medoids)

print(abs(int(px * 10_000)), abs(int(py * 10_000)))

Получаем пару чисел 167990 и 73043. Переходим к файлу Б. Поскольку программа у нас уже написана, нам осталось лишь убедиться в выборе параметра eps. Для этого снова построим точечную диаграмму.

Кластеры по-прежнему довольно плотные и находятся на достаточно большом расстоянии друг от друга. Но при значении eps=2 есть риск, что граничные точки не войдут в свои кластеры. Давайте выберем значение побольше, например, 5.

Выглядит наш код теперь следующим образом:

from math import dist

with open('2705_B.txt') as f:
    next(f)
    data = [tuple(map(float, line.split())) for line in f]


def get_medoid(cluster):
    return min(cluster,
               key=lambda p: sum(dist(p, q) for q in cluster))


def dbscan(data, eps):
    clusters = []

    while data:
        point = data.pop()
        cluster = [point]
        queue = [point]

        while queue:
            current = queue.pop(0)
            neighbors = [p for p in data if
                         dist(current, p) < eps]
            cluster.extend(neighbors)
            queue.extend(neighbors)
            data[:] = [p for p in data if
                       p not in neighbors]

        clusters.append(cluster)

    return clusters


clusters = dbscan(data, 5)
print([len(cluster) for cluster in clusters])

medoids = [get_medoid(cluster) for cluster in clusters]

px = sum(x for x, y in medoids) / len(medoids)
py = sum(y for x, y in medoids) / len(medoids)

print(abs(int(px * 10_000)), abs(int(py * 10_000)))

Запускаем его и получаем вторую пару чисел, которую будем писать в ответ: 122627 и 29105.

Пример 1

Следующим рассмотрим задание с такой формулировкой:

Задание 2706

Гарантируется, что такое разбиение существует и единственно для заданных размеров секторов.

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра.

Расстояние между двумя точками на плоскости A(x1, y1) и B(x2, y2) вычисляется по формуле:

$d(A, B) = \sqrt{(x_2-x_1)^2 +(y_2-y_1)^2}$

В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата X, затем координата Y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах трёх кластеров. Известно, что количество звёзд не превышает 9 000. Структура хранения информации о звездах в файле B аналогична файлу А.

Как мы видим, теперь условие отличается от всех рассмотренных ранее. Это неспроста, здесь нам предстоит работать с кластерами серповидной формы. Визуализируем данные из первого файла.

Вот такие необычные данные содержит файл А. Здесь, конечно, можно пойти через уравнения прямых и отделить один кластер от другого тремя прямыми линиями. Например, так:

Но мы поступим проще, ведь алгоритм DBSCAN прекрасно справится с кластерами такой формы. Главное – подобрать верное значение для параметра eps.

Рассмотрим поближе самую удалённую, на первый взгляд, точку «верхнего» кластера.

Можно заметить, что при значениях радиуса, меньших 0,1, ни один её сосед не попадёт в эту окружность, следовательно, эта точка будет считаться выбросом, что нас не устраивает.

Также стоит рассмотреть максимально близкие граничные точки обоих кластеров.

Здесь видно, что при значениях радиуса, больших 0,4, кластеры «слипнутся» в один из-за того, что граничная точка одного кластера станет соседом граничной точки другого.

Следовательно, мы можем выбрать любое значение eps в диапазоне от 0,1 до 0,4. Остановимся на значении 0,3. В таком случае код для решения файла А будет такой:

from math import dist

with open('2706_A.txt') as f:
    next(f)
    data = [tuple(map(float, line.split())) for line in f]


def get_medoid(cluster):
    return min(cluster,
               key=lambda p: sum(dist(p, q) for q in cluster))


def dbscan(data, eps):
    clusters = []

    while data:
        point = data.pop()
        cluster = [point]
        queue = [point]

        while queue:
            current = queue.pop(0)
            neighbors = [p for p in data if
                         dist(current, p) < eps]
            cluster.extend(neighbors)
            queue.extend(neighbors)
            data[:] = [p for p in data if
                       p not in neighbors]

        clusters.append(cluster)

    return clusters


clusters = dbscan(data, 0.3)
print([len(cluster) for cluster in clusters])

medoids = [get_medoid(cluster) for cluster in clusters]

px = sum(x for x, y in medoids) / len(medoids)
py = sum(y for x, y in medoids) / len(medoids)

print(abs(int(px * 10_000)), abs(int(py * 10_000)))

После запуска программы видим на экране первую пару ответов: 6267 и 15179.

Теперь визуализируем данные из второго файла.

Здесь кластеры достаточно плотные, можем не переживать, что выберем слишком маленькое значение для eps. Минимальное расстояние между соседними кластерами чуть больше 0,1. Давайте возьмем в качестве значения для eps как раз число 0,1. Получим такой код.

from math import dist

with open('2706_B.txt') as f:
    next(f)
    data = [tuple(map(float, line.split())) for line in f]


def get_medoid(cluster):
    return min(cluster,
               key=lambda p: sum(dist(p, q) for q in cluster))


def dbscan(data, eps):
    clusters = []

    while data:
        point = data.pop()
        cluster = [point]
        queue = [point]

        while queue:
            current = queue.pop(0)
            neighbors = [p for p in data if
                         dist(current, p) < eps]
            cluster.extend(neighbors)
            queue.extend(neighbors)
            data[:] = [p for p in data if
                       p not in neighbors]

        clusters.append(cluster)

    return clusters


clusters = dbscan(data, 0.1)
print([len(cluster) for cluster in clusters])

medoids = [get_medoid(cluster) for cluster in clusters]

px = sum(x for x, y in medoids) / len(medoids)
py = sum(y for x, y in medoids) / len(medoids)

print(abs(int(px * 10_000)), abs(int(py * 10_000)))

В результате на экран выводится следующая пара ответов: 4927 и 819.

Пример 2

Теперь научимся решать задания, в которых кластеры содержат выбросы. Формулировка будет такая:

Задание 2710

Гарантируется, что такое разбиение существует и единственно для заданных размеров секторов.

Расстояние между двумя точками на плоскости A(x1, y1) и B(x2, y2) вычисляется по формуле:

$d(A, B) = \sqrt{(x_2-x_1)^2 +(y_2-y_1)^2}$

Выбросами будем называть те звёзды, которые имеют менее 5 соседних звёзд в радиусе единичной окружности. В дальнейших расчётах выбросы не учитываются.

В файле B хранятся данные о звёздах трёх кластеров. Известно, что количество звёзд не превышает 1 000. Структура хранения информации о звездах в файле B аналогична файлу А.

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

В ответе запишите четыре числа: в первой строке сначала абсолютное значение целой части произведения Px × 10 000, затем абсолютное значение целой части произведения Py × 10 000 для файла А, во второй строке – аналогичные данные для файла B»

Давайте убедимся, что выбросы действительно есть, и визуализируем данные из файла А.

И опять же, это задание запросто решается через уравнения прямых. В таком случае мы просто располагаем прямые так, чтобы они отделяли не только соседние кластеры, но и выбросы от кластеров.

А мы же снова пойдём через алгоритм DBSCAN, который определит выбросы в отдельные кластеры. В таком случае мы можем отфильтровать «лишние» кластеры с выбросами по количеству точек в них: если точек меньше какого-то значения, то такой кластер будет выбросом.

Здесь мы видим, что в выбросах ровно по две точки. Но какие-то из них мы могли не заметить, так что лучше всего будет взять число немного больше, чем количество точек в кластере-выбросе. Допустим, будем считать выбросом тот кластер, в котором меньше 5 точек.

Тогда для удаления таких кластеров из общего списка будем использовать такое списковое включение:

clusters = [cluster for cluster in clusters if len(cluster) > 5]

Со значением для параметра eps мудрить не будем: выберем для него значение 1.

Получим такой код:

from math import dist

with open('2710_A.txt') as f:
    next(f)
    data = [tuple(map(float, line.split())) for line in f]


def get_medoid(cluster):
    return min(cluster,
               key=lambda p: sum(dist(p, q) for q in cluster))


def dbscan(data, eps):
    clusters = []

    while data:
        point = data.pop()
        cluster = [point]
        queue = [point]

        while queue:
            current = queue.pop(0)
            neighbors = [p for p in data if
                         dist(current, p) < eps]
            cluster.extend(neighbors)
            queue.extend(neighbors)
            data[:] = [p for p in data if
                       p not in neighbors]

        clusters.append(cluster)

    return clusters


clusters = dbscan(data, 1)
print(f'До фильтрации: {[len(cluster) for cluster in clusters]}')

clusters = [cluster for cluster in clusters if len(cluster) > 5]
print(f'После фильтрации: {[len(cluster) for cluster in clusters]}')

medoids = [get_medoid(cluster) for cluster in clusters]

px = sum(x for x, y in medoids) / len(medoids)
py = sum(y for x, y in medoids) / len(medoids)

print(abs(int(px * 10_000)), abs(int(py * 10_000)))

Обратите внимание на отладочные выводы, они помогают убедиться, что наш код действительно нашел и отфильтровал все выбросы. Так, до фильтрации будет выведен такой список с размерами кластеров: [2, 2, 48, 48]. А после фильтрации у нас останутся только два кластера по 48 точек в каждом.

А в качестве ответа получим пару чисел: 5949 и 27762.

Переходим к файлу Б и визуализируем данные из него.

Кластеры плотные и расположены достаточно далеко как друг от друга, так и от выбросов. Оставим параметр eps, равный 1.

Проверим, сколько точек будет в каждом кластере:

from math import dist

with open('2710_B.txt') as f:
    next(f)
    data = [tuple(map(float, line.split())) for line in f]


def get_medoid(cluster):
    return min(cluster,
               key=lambda p: sum(dist(p, q) for q in cluster))


def dbscan(data, eps):
    clusters = []

    while data:
        point = data.pop()
        cluster = [point]
        queue = [point]

        while queue:
            current = queue.pop(0)
            neighbors = [p for p in data if
                         dist(current, p) < eps]
            cluster.extend(neighbors)
            queue.extend(neighbors)
            data[:] = [p for p in data if
                       p not in neighbors]

        clusters.append(cluster)

    return clusters


clusters = dbscan(data, 1)
print(f'До фильтрации: {[len(cluster) for cluster in clusters]}')

Получаем такой список: [330, 330, 4, 330, 3, 3]. Следовательно, в выбросах от 3 до 4 точек. Значит, условие фильтрации оставляем прежнем: чтобы кластер не считался выбросом, в нём должно быть более 5 точек.

Весь код нашей программы будет такой:

from math import dist

with open('2710_B.txt') as f:
    next(f)
    data = [tuple(map(float, line.split())) for line in f]


def get_medoid(cluster):
    return min(cluster,
               key=lambda p: sum(dist(p, q) for q in cluster))


def dbscan(data, eps):
    clusters = []

    while data:
        point = data.pop()
        cluster = [point]
        queue = [point]

        while queue:
            current = queue.pop(0)
            neighbors = [p for p in data if
                         dist(current, p) < eps]
            cluster.extend(neighbors)
            queue.extend(neighbors)
            data[:] = [p for p in data if
                       p not in neighbors]

        clusters.append(cluster)

    return clusters


clusters = dbscan(data, 1)
print(f'До фильтрации: {[len(cluster) for cluster in clusters]}')

clusters = [cluster for cluster in clusters if len(cluster) > 5]
print(f'После фильтрации: {[len(cluster) for cluster in clusters]}')

medoids = [get_medoid(cluster) for cluster in clusters]

px = sum(x for x, y in medoids) / len(medoids)
py = sum(y for x, y in medoids) / len(medoids)

print(abs(int(px * 10_000)), abs(int(py * 10_000)))

И получаем вторую пару чисел: 7455 и 6872.

Итоги

Итак, в трёх частях этой статьи мы подробно разобрали решение нового формата задания 27 ЕГЭ по информатике 2025 года. Теперь, вместо сложных методов олимпиадного программирования, любой экзаменуемый может успешно справиться с заданием, освоив один из трёх предложенных нами алгоритмов кластеризации:

Кластеризация через уравнения прямых – самый простой и понятный способ. Он требует минимального количества кода и отлично подходит для кластеров, которые легко разделить одной или несколькими прямыми линиями. Главным недостатком этого метода является его непрактичность для сложных форм кластеров и невозможность работы с выбросами.
Алгоритм k-средних – промежуточный вариант, более сложный и эффективный, чем кластеризация через уравнения прямых. Этот алгоритм позволяет автоматически находить медоиды кластеров и довольно быстро сходится к решению. Однако для успешной работы алгоритма k-средних необходимо грамотно подбирать начальные точки-медоиды, чтобы избежать ошибки в кластеризации.
Алгоритм DBSCAN – самый мощный и универсальный из всех рассмотренных алгоритмов. Он отлично справляется с любыми формами кластеров и позволяет без проблем обрабатывать выбросы. Однако DBSCAN требует аккуратного подбора ключевого параметра – радиуса соседства (eps). Неправильный выбор параметра может привести либо к объединению нескольких кластеров в один, либо к появлению большого количества шумовых точек.

Мы подробно рассмотрели особенности каждого алгоритма, а также написали простые и понятные реализации на языке Python, максимально оптимизированные под условия реального экзамена.

Мы научились не только проводить саму кластеризацию, но и визуализировать её результаты, что существенно облегчает выбор параметров и проверку корректности решения.

Теперь у вас есть сразу три надёжных инструмента для решения задания 27. Вы можете выбрать тот алгоритм, который наиболее понятен и удобен именно вам, исходя из конкретного условия задания и особенностей предоставленных данных.

<<< Предыдущая часть

Первая часть >>>