Algoritmo de ÓPTICA

El algoritmo OPTICS ( Ordering points to identify the clustering structure ) es un algoritmo para encontrar clústeres basados ​​en la densidad ^{[ 1 ]} en datos espaciales. Fue presentado en 1999 por Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel y Jörg Sander . ^{[ 2 ]} Su idea básica es similar a DBSCAN , ^{[ 3 ]} pero aborda una de las principales debilidades de DBSCAN: el problema de detectar clústeres significativos en datos de densidad variable. Para ello, los puntos de la base de datos se ordenan (linealmente) de manera que los puntos espacialmente más cercanos se conviertan en vecinos en el ordenamiento. Además, se almacena una distancia especial para cada punto que representa la densidad que debe aceptarse para un clúster para que ambos puntos pertenezcan al mismo clúster. Esto se representa como un dendrograma .

Al igual que DBSCAN , OPTICS requiere dos parámetros: ε , que describe la distancia máxima (radio) a considerar, y MinPts , que describe el número de puntos necesarios para formar un clúster. Un punto p es un punto central si se encuentran al menos MinPts puntos dentro de su vecindario ε.${\ Displaystyle N _ {\ varepsilon} (p)}$(incluido el punto p en sí). A diferencia de DBSCAN , OPTICS también considera los puntos que forman parte de un grupo más denso, por lo que a cada punto se le asigna una distancia central que describe la distancia al punto MinPts más cercano:

${\displaystyle {\text{core-dist}}_{\mathit {\varepsilon ,MinPts}}(p)={\begin{cases}{\text{UNDEFINED}}&{\text{si }}|N_{\varepsilon }(p)|<{\mathit {MinPts}}\\{\mathit {MinPts}}{\text{-ésima distancia más pequeña en }}N_{\varepsilon }(p)&{\text{en otro caso}}\end{cases}}}$

La distancia de alcanzabilidad de otro punto o desde un punto p es la distancia entre o y p , o la distancia central de p , la que sea mayor:

${\displaystyle {\text{reachability-dist}}_{\mathit {\varepsilon ,MinPts}}(o,p)={\begin{cases}{\text{UNDEFINED}}&{\text{si }}|N_{\varepsilon }(p)|<{\mathit {MinPts}}\\\max({\text{core-dist}}_{\mathit {\varepsilon ,MinPts}}(p),{\text{dist}}(p,o))&{\text{en otro caso}}\end{cases}}}$

Si p y o son vecinos más cercanos, esta es la${\displaystyle \varepsilon '<\varepsilon }$Debemos suponer que p y o pertenecen al mismo clúster.

Tanto la distancia central como la distancia de accesibilidad no están definidas si no hay un clúster suficientemente denso (con respecto a ε ) disponible. Dado un ε suficientemente grande , esto nunca sucede, pero entonces cada consulta de vecindario ε devuelve toda la base de datos, lo que resulta en${\displaystyle O(n^{2})}$tiempo de ejecución. Por lo tanto, el parámetro ε es necesario para recortar la densidad de clústeres que ya no son interesantes y para acelerar el algoritmo.

El parámetro ε , en rigor, no es necesario. Simplemente se le puede asignar el valor máximo posible. Sin embargo, cuando se dispone de un índice espacial, sí influye en la complejidad práctica. OPTICS simplifica DBSCAN eliminando este parámetro, al menos hasta el punto de requerir únicamente el valor máximo.

El enfoque básico de OPTICS es similar al de DBSCAN , pero en lugar de mantener los miembros del clúster conocidos, pero aún no procesados, en un conjunto, se mantienen en una cola de prioridad (por ejemplo, utilizando un montón indexado ).

La función OPTICS(DB, ε, MinPts) es para cada punto p de DB hacer p.distancia de accesibilidad = INDEFINIDO para cada punto no procesado p de DB hacer N = obtenerVecinos(p, ε) marcar p como procesado Salida p a la lista ordenada Si core-distance(p, ε, MinPts) != UNDEFINED entonces Semillas = cola de prioridad vacía actualizar(N, p, Semillas, ε, PuntosMínimos) para cada siguiente q en Seeds hacer N' = obtenerVecinos(q, ε) marcar q como procesado Salida q a la lista ordenada Si core-distance(q, ε, MinPts) != UNDEFINED , actualiza(N', q, Seeds, ε, MinPts).

En update(), la cola de prioridad Seeds se actualiza con el${\displaystyle \varepsilon }$-vecindario de${\displaystyle p}$y${\displaystyle q}$, respectivamente:

La función update(N, p, Seeds, ε, MinPts) es coredist = distancia-núcleo(p, ε, MinPts) para cada o en N si o no se procesa entonces nueva-distancia-alcance = max(coredist, dist(p,o)) Si o.reachability-distance == UNDEFINED entonces // o no está en Seeds o.distancia-de-alcance = nueva-distancia-de-alcance Semillas.insertar(o, new-reach-dist) else // o en Seeds, comprobar si hay mejora si new-reach-dist < o.reachability-distance entonces o.distancia-de-alcance = nueva-distancia-de-alcance Semillas.mover-arriba(o, nueva-distancia-alcance)

Por lo tanto, OPTICS genera los puntos en un orden determinado, anotados con su distancia de alcanzabilidad más pequeña (en el algoritmo original, también se exporta la distancia del núcleo, pero esto no es necesario para el procesamiento posterior).

Mediante un diagrama de alcanzabilidad (un tipo especial de dendrograma ), se puede obtener fácilmente la estructura jerárquica de los clústeres. Se trata de un diagrama bidimensional, donde el eje x representa el orden de los puntos procesados ​​por OPTICS y el eje y la distancia de alcanzabilidad. Dado que los puntos que pertenecen a un clúster tienen una baja distancia de alcanzabilidad a su vecino más cercano, los clústeres aparecen como valles en el diagrama de alcanzabilidad. Cuanto más profundo sea el valle, más denso será el clúster.

La imagen superior ilustra este concepto. En la parte superior izquierda, se muestra un conjunto de datos sintéticos de ejemplo. La parte superior derecha visualiza el árbol de expansión generado por OPTICS, y la parte inferior muestra el gráfico de alcanzabilidad calculado por OPTICS. Los colores en este gráfico son etiquetas, no calculados por el algoritmo; sin embargo, se observa claramente cómo los valles en el gráfico corresponden a los clústeres del conjunto de datos anterior. Los puntos amarillos en esta imagen se consideran ruido, y no se encuentra ningún valle en su gráfico de alcanzabilidad. Por lo general, no se asignan a clústeres, excepto al omnipresente clúster "todos los datos" en un resultado jerárquico.

La extracción de clústeres de este gráfico se puede realizar manualmente seleccionando rangos en el eje x después de una inspección visual, seleccionando un umbral en el eje y (el resultado es entonces similar a un resultado de agrupamiento DBSCAN con el mismo${\displaystyle \varepsilon }$y parámetros minPts ; aquí un valor de 0.1 puede dar buenos resultados), o mediante diferentes algoritmos que intentan detectar los valles por pendiente, detección de rodilla o máximos locales. Un rango del gráfico que comienza con un descenso pronunciado y termina con un ascenso pronunciado se considera un valle, y corresponde a un área contigua de alta densidad. Se debe tener cuidado adicional con los últimos puntos en un valle para asignarlos al clúster interno o externo, esto se puede lograr considerando el predecesor. ^{[ 4 ]} Los agrupamientos obtenidos de esta manera suelen ser jerárquicos y no se pueden lograr con una sola ejecución de DBSCAN.

Al igual que DBSCAN , OPTICS procesa cada punto una vez y realiza una${\displaystyle \varepsilon }$-consulta de vecindario durante este procesamiento. Dado un índice espacial que otorga una consulta de vecindario en${\displaystyle O(\log n)}$tiempo de ejecución, un tiempo de ejecución general de${\displaystyle O(n\cdot \log n)}$se obtiene. Sin embargo, el peor caso es${\displaystyle O(n^{2})}$, al igual que con DBSCAN. Los autores del artículo original de OPTICS informan un factor de ralentización constante real de 1,6 en comparación con DBSCAN. Tenga en cuenta que el valor de${\displaystyle \varepsilon }$podría influir en gran medida en el coste del algoritmo, ya que un valor demasiado grande podría elevar el coste de una consulta de vecindario a una complejidad lineal.

En particular, elegir${\displaystyle \varepsilon >\max _ {x,y}d(x,y)}$(mayor que la distancia máxima en el conjunto de datos) es posible, pero conlleva una complejidad cuadrática, ya que cada consulta de vecindario devuelve el conjunto de datos completo. Incluso cuando no hay un índice espacial disponible, esto conlleva un costo adicional en la gestión del montón. Por lo tanto,${\displaystyle \varepsilon }$debe elegirse adecuadamente para el conjunto de datos.

OPTICS-OF ^{[ 5 ]} es un algoritmo de detección de valores atípicos basado en OPTICS. Su principal utilidad radica en la extracción de valores atípicos de una ejecución existente de OPTICS a un costo menor que el de otros métodos de detección. La versión más conocida, LOF, se basa en los mismos conceptos.

DeLi-Clu, ^{[ 6 ]} Density-Link-Clustering combina ideas de agrupamiento de enlace simple y OPTICS, eliminando el${\displaystyle \varepsilon }$parámetro y ofreciendo mejoras de rendimiento con respecto a OPTICS.

HiSC ^{[ 7 ]} es un método de agrupamiento de subespacios jerárquicos (paralelo a los ejes) basado en OPTICS.

HiCO ^{[ 8 ]} es un algoritmo de agrupamiento de correlación jerárquica basado en OPTICS.

DiSH ^{[ 9 ]} es una mejora con respecto a HiSC que puede encontrar jerarquías más complejas.

FOPTICS ^{[ 10 ]} es una implementación más rápida que utiliza proyecciones aleatorias.

HDBSCAN* ^{[ 11 ]} se basa en un refinamiento de DBSCAN, excluyendo los puntos de borde de los clústeres y siguiendo así más estrictamente la definición básica de niveles de densidad de Hartigan. ^{[ 12 ]}

La Cordillera OPTICS ^{[ 13 ]} es una medida descriptiva de Scagnostics que indica el grado de agrupamiento de un conjunto de datos. Utiliza OPTICS para crear un dendrograma y luego agrega la información del dendrograma para obtener una medida de agrupamiento que oscila entre 0 (sin agrupamiento) y 1 (máximo agrupamiento).

Las implementaciones en Java de OPTICS, OPTICS-OF, DeLi-Clu, HiSC, HiCO y DiSH están disponibles en el marco de minería de datos ELKI (con aceleración de índices para varias funciones de distancia y extracción automática de clústeres mediante el método de extracción ξ ). Otras implementaciones en Java incluyen la extensión Weka (sin soporte para la extracción de clústeres ξ ).

El paquete R "dbscan" incluye una implementación en C++ de OPTICS (con extracción de clústeres tanto tradicional tipo dbscan como ξ ) que utiliza un árbol kd para la aceleración de índices solo para la distancia euclidiana.

Las implementaciones de OPTICS en Python están disponibles en la biblioteca PyClustering y en scikit-learn . HDBSCAN* está disponible en la biblioteca hdbscan .