Ordenar puntos para identificar la estructura de agrupación ( OPTICS ) es un algoritmo para encontrar agrupaciones basadas en densidad [1] en datos espaciales. Fue presentado 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 grupos significativos en datos de densidad variable. Para ello, los puntos de la base de datos se ordenan (linealmente) de modo que los puntos espacialmente más cercanos se conviertan en vecinos en el orden. Además, para cada punto se almacena una distancia especial que representa la densidad que se debe aceptar para un cluster para que ambos puntos pertenezcan al mismo cluster. Esto se representa como un dendograma .
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 grupo. Un punto p es un punto central si se encuentran al menos puntos MinPts dentro de su ε -vecindad (incluido el propio punto p ). A diferencia de DBSCAN , OPTICS también considera puntos que son 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 más cercano de MinPts :
La distancia de accesibilidad de otro punto o desde un punto p es la distancia entre o y p , o la distancia central de p , lo que sea mayor:
Si p y o son vecinos más cercanos, debemos suponer que p y o pertenecen al mismo grupo.
Tanto la distancia central como la distancia de accesibilidad no están definidas si no hay un grupo suficientemente denso (wrt ε ) disponible. Dado un ε suficientemente grande , esto nunca sucede, pero luego cada consulta de ε -vecindario devuelve la base de datos completa, lo que resulta en tiempo de ejecución. Por lo tanto, se requiere el parámetro ε para cortar la densidad de grupos que ya no son interesantes y acelerar el algoritmo.
El parámetro ε , estrictamente hablando, no es necesario. Simplemente se puede establecer al valor máximo posible. Sin embargo, cuando un índice espacial está disponible, juega un papel práctico con respecto a la complejidad. OPTICS se abstrae de DBSCAN eliminando este parámetro, al menos hasta el punto de tener que dar solo el valor máximo.
El enfoque básico de OPTICS es similar a DBSCAN , pero en lugar de mantener miembros del clúster conocidos, pero hasta ahora sin procesar, en un conjunto, se mantienen en una cola de prioridad (por ejemplo, usando un montón indexado ).
La función OPTICS(DB, ε, MinPts) es para cada punto p de DB . p.distancia-alcancebilidad = INDEFINIDO para cada punto p sin procesar de DB hacer N = obtenerVecinos(p, ε) marcar p como procesado salida p a la lista ordenada si distancia central (p, ε, MinPts)! = INDEFINIDO entonces Semillas = cola de prioridad vacía actualizar(N, p, Semillas, ε, MinPts) para cada siguiente q en Seeds hazlo N' = obtenerVecinos(q, ε) marcar q como procesado salida q a la lista ordenada si distancia central (q, ε, MinPts)! = INDEFINIDO hacer actualizar(N', q, Semillas, ε, MinPts)
En update(), la cola de prioridad Seeds se actualiza con el vecindario de y , respectivamente:
actualización de función (N, p, Seeds, ε, MinPts) es coredist = distancia-núcleo(p, ε, MinPts) para cada o en N si o no se procesa entonces nuevo-alcance-dist = max(coredist, dist(p,o)) si o.reachability-distance == UNDEFINED entonces // o no está en Seeds o.distancia-alcance = nueva-distancia-alcance Seeds.insert(o, nuevo-alcance-dist) else // o en Seeds, verifique si hay mejoras si new-reach-dist < o.reachability-distance entonces o.distancia-alcance = nueva-distancia-alcance Seeds.move-up(o, nuevo-alcance-dist)
Por lo tanto, OPTICS genera los puntos en un orden particular, anotado con su distancia de alcance más pequeña (en el algoritmo original, la distancia central también se exporta, pero esto no es necesario para un procesamiento posterior).
Utilizando un gráfico de accesibilidad (un tipo especial de dendrograma ), la estructura jerárquica de los grupos se puede obtener fácilmente. Es un gráfico 2D, con el orden de los puntos procesados por OPTICS en el eje x y la distancia de alcanzabilidad en el eje y. Dado que los puntos que pertenecen a un grupo tienen una distancia de accesibilidad baja con respecto a su vecino más cercano, los grupos aparecen como valles en el gráfico de accesibilidad. Cuanto más profundo es el valle, más denso es el grupo.
La imagen de arriba ilustra este concepto. En su área superior izquierda, se muestra un conjunto de datos de ejemplo sintético. La parte superior derecha visualiza el árbol de expansión producido por OPTICS y la parte inferior muestra el gráfico de accesibilidad calculado por OPTICS. Los colores en este gráfico son etiquetas y el algoritmo no los calcula; pero es bien visible cómo los valles en el gráfico corresponden a los grupos en el 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 accesibilidad. Por lo general, no se asignan a grupos, excepto al omnipresente grupo "todos los datos" en un resultado jerárquico.
La extracción de grupos de este gráfico se puede realizar manualmente seleccionando rangos en el eje x después de la inspección visual, seleccionando un umbral en el eje y (el resultado es similar al resultado de agrupamiento de DBSCAN con los mismos parámetros y minPts; aquí un un valor de 0,1 puede dar buenos resultados), o mediante diferentes algoritmos que intentan detectar los valles mediante inclinación, detección de rodillas o máximos locales. Un tramo de la parcela que comienza con un fuerte descenso y termina con un fuerte ascenso se considera un valle, y corresponde a un área contigua de alta densidad. Se debe tener especial cuidado en los últimos puntos de un valle para asignarlos al grupo interior o exterior; esto se puede lograr considerando el predecesor. [4] Las agrupaciones obtenidas de esta manera generalmente son jerárquicas y no se pueden lograr mediante una sola ejecución de DBSCAN.
Al igual que DBSCAN , OPTICS procesa cada punto una vez y realiza una consulta de vecindario durante este procesamiento. Dado un índice espacial que concede una consulta de vecindad en tiempo de ejecución, se obtiene un tiempo de ejecución general de . Sin embargo, el peor de los casos es , como ocurre con DBSCAN. Los autores del artículo original de OPTICS informan de un factor de desaceleración constante real de 1,6 en comparación con DBSCAN. Tenga en cuenta que el valor de podría influir en gran medida en el costo del algoritmo, ya que un valor demasiado grande podría elevar el costo de una consulta de vecindad a una complejidad lineal.
En particular, es posible elegir (una distancia mayor que la distancia máxima en el conjunto de datos), pero conduce a una complejidad cuadrática, ya que cada consulta de vecindad devuelve el conjunto de datos completo. Incluso cuando no hay ningún índice espacial disponible, esto supone un coste adicional en la gestión del montón. Por lo tanto, se debe elegir la adecuada para el conjunto de datos.
OPTICS-OF [5] es un algoritmo de detección de valores atípicos basado en OPTICS. El uso principal es la extracción de valores atípicos de una ejecución existente de OPTICS a bajo costo en comparación con el uso de un método de detección de valores atípicos diferente. La versión más conocida LOF se basa en los mismos conceptos.
DeLi-Clu, [6] Density-Link-Clustering combina ideas de agrupación de enlace único y OPTICS, eliminando el parámetro y ofreciendo mejoras de rendimiento sobre OPTICS.
HiSC [7] es un método de agrupación subespacial jerárquica (ejes paralelos) 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 fronterizos de los grupos y, por lo tanto, siguiendo más estrictamente la definición básica de niveles de densidad de Hartigan. [12]
Las implementaciones 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 índice para varias funciones de distancia y con extracción automática de clústeres utilizando el método de extracción ξ). Otras implementaciones de Java incluyen la extensión Weka (sin soporte para la extracción de ξ cluster).
El paquete R "dbscan" incluye una implementación C++ de OPTICS (con extracción tradicional tipo dbscan y de clúster ξ) utilizando un árbol kd para aceleración de índice solo para distancia euclidiana.
Las implementaciones Python de OPTICS están disponibles en la biblioteca PyClustering y en scikit-learn . HDBSCAN* está disponible en la biblioteca hdbscan.
