ML | Accesibilidad y conectividad de DBSCAN

Requisito previo: agrupación en clústeres de DBSCAN en ML

El algoritmo de agrupamiento basado en la densidad ha jugado un papel vital en la búsqueda de estructuras de formas no lineales basadas en la densidad. El agrupamiento espacial de aplicaciones con ruido basado en la densidad (DBSCAN) es el algoritmo basado en la densidad más utilizado. Utiliza el concepto de accesibilidad de densidad y conectividad de densidad.

Considere un conjunto de puntos en algún espacio para ser agrupados usando el agrupamiento DBSCAN. Sea ε el radio de una vecindad con respecto a algún punto y los objetos centrales son los objetos cuya vecindad ε contiene al menos un número MinPts de objetos.

Accesibilidad –

• Densidad directamente alcanzable:
  un objeto (o instancia) q es densidad directamente alcanzable desde el objeto p si q está dentro de la vecindad ε de p y p es un objeto central.
  

  Aquí directamente la accesibilidad de la densidad no es simétrica. El objeto p no es directamente alcanzable por densidad desde el objeto q, ya que q no es un objeto central.

• Densidad alcanzable:
  Un objeto q es densidad-alcanzable desde p wrt ε y MinPts si hay una string de objetos q ₁ , q ₂ …, q _n , con q ₁ =p, q _n =q tal que q _i+1 es densidad directamente accesible desde q _i wrt ε y MinPts para todo 1 <= i <= n
  

Aquí la accesibilidad de la densidad no es simétrica. Como q no es un punto central, q _n-1 no es directamente alcanzable por densidad desde q, por lo que el objeto p no es alcanzable por densidad desde el objeto q.

Conectividad –

• Conectividad de densidad: el objeto q está conectado por densidad al objeto p wrt ε y MinPts si hay un objeto o tal que tanto p como q son accesibles por densidad desde o wrt ε y MinPts .
  
  Aquí la conectividad de densidad es simétrica. Si el objeto q está conectado por densidad con el objeto p, entonces el objeto p también está conectado por densidad con el objeto q.

 
Con base en los dos conceptos anteriores, accesibilidad y conectividad , podemos definir el clúster y los puntos de ruido .

Clúster:
un clúster C wrt ε y MinPts es un subconjunto no vacío de D (el conjunto completo de objetos o instancias) que satisface:

• Maximalidad: para todos los objetos p, q si p ε C y si q es alcanzable por densidad desde p wrt ε y MinPts , entonces q ε C.
• Conectividad: para todos los objetos p, q ε C, p está conectado por densidad a q y viceversa con ε y MinPts .

Ruido:
Los objetos que no son directamente alcanzables por densidad desde al menos un objeto central se conocen como puntos de ruido .