ML | Доступность и подключение DBSCAN

Предварительное условие: кластеризация DBSCAN в машинном обучении

Алгоритм кластеризации на основе плотности сыграл жизненно важную роль в поиске структуры нелинейных форм на основе плотности. Пространственная кластеризация приложений с шумом на основе плотности (DBSCAN) - это наиболее широко используемый алгоритм на основе плотности. Он использует концепцию плотности достижимости и плотности связи.

Рассмотрим набор точек в некотором пространстве для кластеризации с использованием кластеризации DBSCAN. Пусть ε - радиус окрестности относительно некоторой точки, а основные объекты - это объекты, ε-окрестность которых содержит не менее MinPts количества объектов.

Доступность -

• Непосредственно достижимая плотность:
  Объект (или экземпляр) q является непосредственно достижимой плотностью от объекта p, если q находится в пределах ε-окрестности p, а p является основным объектом.
  

  Здесь непосредственно плотность достижимости не является симметричной. Объект p не является напрямую достижимым по плотности из объекта q, поскольку q не является основным объектом.

• Достигаемая плотность:
  Объект q является достижимым по плотности из p относительно ε и MinPts, если существует цепочка объектов q ₁ , q ₂ …, q _n , с q ₁ = p, q _n = q, такая, что q _{i + 1} непосредственно является плотностью - достижимо из q _i относительно ε и MinPts для всех 1 <= i <= n
  

Здесь достижимость по плотности не симметрична. Поскольку q не является основной точкой, поэтому q _n-1 не является напрямую достижимым по плотности из q, поэтому объект p недостижим по плотности из объекта q.

Связь -

• Подключение Плотность: Объект д от плотности объекта соединен с р е WRT и MinPts , если существует объект О , такие , что оба р и д плотности достижима из O WRT ε и MinPts.
  
  Здесь плотность связности симметрична. Если объект q плотно связан с объектом p, то объект p также плотно связан с объектом q.

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

Кластер:
Кластер C относительно ε и MinPts - это непустое подмножество D (весь набор объектов или экземпляров), удовлетворяющее -

• Максимальность: Для всех объектов p, q, если p ε C и если q является плотно достижимым из p относительно ε и MinPts, то q ε C.
• Связность: для всех объектов p, q ε C, p плотно связан с q и наоборот относительно ε и MinPts.

Шум:
Объекты, которые напрямую не достижимы по плотности хотя бы из одного основного объекта, известны как точки шума .