Главная функция: DBSCAN
Что она делает? Проходит по всем точкам и решает: это кластер или шум.
Шаг за шагом:
1. Подготовка
clusters = [] # Список всех найденных кластеров
visited = set() # Какие точки мы уже проверили
noise = set() # Точки-одиночки (шум)
2. Главный цикл — проверяем каждую точку:
for point in points:
if point in visited:
continue # Если уже смотрели — пропускаем
Аналогия: Как в игре "найди пару" — если карточку уже открывали, не трогаем её снова.
3. Ищем соседей
neighbors = find_neighbors(point, eps)
Рисуем круг радиусом eps вокруг точки. Все точки внутри круга — её соседи.
4. Принимаем решение:
Функция расширения: expand_cluster
Когда нашли ядровую точку, нужно собрать вокруг неё ВСЕ связанные точки.
Как работает:
1. Начинаем кластер
cluster = {point} # Добавляем первую точку
queue = list(neighbors) # Очередь: кого ещё проверить
2. Обрабатываем очередь (алгоритм BFS — поиск в ширину):
while queue:
current = queue.pop(0) # Берём следующего соседа
Аналогия: Как волна расходится по воде — от центра к краям.
3. Проверяем каждого соседа:
-
Если ещё не проверяли — смотрим его соседей:
if current not in visited:
visited.add(current)
current_neighbors = find_neighbors(current, eps)
-
Если у него тоже много соседей — он тоже ядровый!
if len(current_neighbors) >= minPts:
queue.extend(current_neighbors) # Добавляем его соседей в очередь
-
Всегда добавляем в кластер:
cluster.add(current)
4. Возвращаем готовый кластер:
return cluster