ML | Explicación de agrupamiento de OPTICS

Requisitos previos: agrupación en clústeres de DBSCAN

OPTICS Clustering significa Puntos de pedido para identificar la estructura del clúster . Se inspira en el algoritmo de agrupamiento DBSCAN. Agrega dos términos más a los conceptos de agrupación en clústeres de DBSCAN. Están:-

1. Distancia al núcleo: Es el valor mínimo de radio requerido para clasificar un punto dado como punto central. Si el punto dado no es un punto central, entonces su distancia central no está definida.



2. Distancia de Alcanzabilidad: Se define con respecto a otro punto de datos q(Let). La distancia de accesibilidad entre un punto p y q es el máximo de la distancia central de p y la distancia euclidiana (o alguna otra métrica de distancia) entre p y q. Tenga en cuenta que la distancia de alcance no está definida si q no es un punto central.

Esta técnica de agrupación en clústeres es diferente de otras técnicas de agrupación en clústeres en el sentido de que esta técnica no segmenta explícitamente los datos en clústeres. En su lugar, produce una visualización de las distancias de Accesibilidad y utiliza esta visualización para agrupar los datos.

Pseudocódigo:

El siguiente Pseudocódigo ha sido referido desde la página de Wikipedia del algoritmo.

OPTICS(DB, eps, MinPts)

    #Repeating the process for all points in the database
    for each point pt of DB

       #Initializing the reachability distance of the selected point
       pt.reachable_dist = UNDEFINED
    for each unprocessed point pt of DB

       #Getting the neighbours of the selected point
       #according to the definitions of epsilon and
       #minPts in DBSCAN
       Nbrs = getNbrs(pt, eps)

       mark pt as processed
       output pt to the ordered list

       #Checking if the selected point is not noise
       if (core_dist(pt, eps, Minpts) != UNDEFINED)

          #Initializing a priority queue to get the closest data point
          #in terms of Reachability distance
          Seeds = empty priority queue

          #Calling the update function
          update(Nbrs, pt, Seeds, eps, Minpts)

          #Repeating the process for the next closest point
          for each next q in Seeds
             Nbrs' = getNbrs(q, eps)
             mark q as processed
             output q to the ordered list
             if (core_dist(q, eps, Minpts) != UNDEFINED)
                update(Nbrs', q, Seeds, eps, Minpts)

El pseudocódigo para la función de actualización se proporciona a continuación:

update(Nbrs, pt, Seeds, eps, MinPts)

    #Calculating the core distance for the given point
    coredist = core_dist(pt, eps, MinPts)

    #Updating the Reachability distance for each neighbour of p
    for each obj in Nbrs
       if (obj is not processed)
          new_reach_distance = max(coredist, dist(pt, obj))

          #Checking if the neighbour point is in seeds
          if (obj.reachable_dist == UNDEFINED)

              #Updation step
              obj.reachabled_dist = new_reach_distance
              Seeds.insert(obj, new_reach_distance)
          else               
              if (new_reach_distance < obj.reachable_dist)

                 #Updation step
                 o.reachable_dist = new_reach_distance
                 Seeds.move-up(obj, new_reach_distance)

Agrupación OPTICS v/s Agrupación DBSCAN:

1. Costo de memoria: la técnica de agrupamiento OPTICS requiere más memoria, ya que mantiene una cola de prioridad (Min Heap) para determinar el siguiente punto de datos que está más cerca del punto que se está procesando actualmente en términos de distancia de alcance. También requiere más poder de cómputo porque las consultas de vecinos más cercanos son más complicadas que las consultas de radio en DBSCAN.
2. Menos parámetros: la técnica de agrupamiento OPTICS no necesita mantener el parámetro épsilon y solo se proporciona en el pseudocódigo anterior para reducir el tiempo necesario. Esto conduce a la reducción del proceso analítico de ajuste de parámetros.
3. Esta técnica no segrega los datos dados en grupos. Simplemente produce un gráfico de distancia de alcance y depende de la interpretación del programador agrupar los puntos en consecuencia.