Algoritmo ÓPTICO

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 por Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel y Jörg Sander ^[2] . Su idea básica es similar a la de 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 forma 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 de forma que ambos puntos pertenezcan al mismo clúster. Esto se representa como un dendrograma .

Idea básica

Al igual que DBSCAN , OPTICS requiere dos parámetros: $ε$ , que describe la distancia máxima (radio) a considerar, y $MinPts$ , que describe la cantidad de puntos necesarios para formar un grupo. Un punto $p$ es un punto central si se encuentran al menos $MinPts$ puntos dentro de su vecindad $ε$ (incluido el propio punto $p$ ). A diferencia de DBSCAN , OPTICS también considera 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: $N_{\varepsilon }(p)$

{\text{core-dist}}_{\mathit {\varepsilon ,MinPts}}(p)={\begin{cases}{\text{UNDEFINED}}&{\text{if }}|N_{\varepsilon }(p)|<{\mathit {MinPts}}\\{\mathit {MinPts}}{\text{-th smallest distance in }}N_{\varepsilon }(p)&{\text{otherwise}}\end{cases}}

La distancia de alcance 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:

{\text{reachability-dist}}_{\mathit {\varepsilon ,MinPts}}(o,p)={\begin{cases}{\text{UNDEFINED}}&{\text{if }}|N_{\varepsilon }(p)|<{\mathit {MinPts}}\\\max({\text{core-dist}}_{\mathit {\varepsilon ,MinPts}}(p),{\text{dist}}(p,o))&{\text{otherwise}}\end{cases}}

Si $p$ y $o$ son vecinos más cercanos, debemos asumir que $p$ y $o$ pertenecen al mismo grupo. $\varepsilon '<\varepsilon$

Tanto la distancia del núcleo como la distancia de accesibilidad no están definidas si no hay disponible un clúster lo suficientemente denso (con respecto a $ε ). Dado un$ $ε$ suficientemente grande , esto nunca sucede, pero entonces cada consulta de vecindad $ε$ devuelve la base de datos completa, lo que genera tiempo de ejecución. Por lo tanto, se requiere el parámetro $ε$ para eliminar la densidad de clústeres que ya no son interesantes y para acelerar el algoritmo. $O(n^{2})$

El parámetro $ε$ no es estrictamente necesario. Se puede fijar simplemente en el valor máximo posible. Sin embargo, cuando se dispone de un índice espacial, éste desempeña un papel práctico en lo que respecta a la complejidad. OPTICS se abstrae de DBSCAN eliminando este parámetro, al menos hasta el punto de tener que indicar únicamente el valor máximo.

Pseudocódigo

El enfoque básico de OPTICS es similar a DBSCAN , pero en lugar de mantener miembros del clúster conocidos, pero hasta ahora 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 p.distancia-de-alcance = INDEFINIDA para cada punto p no procesado de DB hacer N = obtenerVecinos(p, ε) Marcar p como procesado salida p a la lista ordenada si distancia-núcleo(p, ε, MinPts) != INDEFINIDO entonces Semillas = cola de prioridad vacía update(N, p, Semillas, ε, MinPts) para cada siguiente q en Semillas hacer N' = obtenerVecinos(q, ε) Marcar q como procesado salida q a la lista ordenada si distancia-núcleo(q, ε, MinPts) != INDEFINIDO hacer update(N', q, Semillas, ε, MinPts)

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

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-de-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.insert(o, new-reach-dist) de lo contrario // o en Semillas, verificar si hay mejoras si new-reach-dist < o.reachability-distance entonces o.distancia-de-alcance = nueva-distancia-de-alcance Semillas.move-up(o, nueva-distancia-alcance)

De este modo, OPTICS genera los puntos en un orden particular, anotados con su distancia de alcance más pequeña (en el algoritmo original, también se exporta la distancia principal, pero esto no es necesario para el procesamiento posterior).

Extrayendo los clusters

Utilizando un gráfico de accesibilidad (un tipo especial de dendrograma ), se puede obtener fácilmente la estructura jerárquica de los grupos. Es un gráfico 2D, con el orden de los puntos procesados por OPTICS en el eje x y la distancia de accesibilidad en el eje y. Dado que los puntos que pertenecen a un grupo tienen una distancia de accesibilidad baja 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 no son calculados por el algoritmo; pero es claramente visible cómo los valles en el gráfico corresponden a los clústeres 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 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 la inspección visual, seleccionando un umbral en el eje y (el resultado es entonces similar a un resultado de agrupamiento DBSCAN con los mismos parámetros y minPts; aquí un valor de 0,1 puede producir buenos resultados), o mediante diferentes algoritmos que intentan detectar los valles por inclinación, detección de codo 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 especial cuidado con los últimos puntos de un valle para asignarlos al clúster interno o externo, esto se puede lograr considerando el predecesor. ^[4] Los agrupamientos obtenidos de esta manera generalmente son jerárquicos y no se pueden lograr con una sola ejecución de DBSCAN. $\varepsilon$

Complejidad

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

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

Extensiones

OPTICS-OF ^[5] es un algoritmo de detección de valores atípicos basado en OPTICS. Su principal uso es la extracción de valores atípicos de una serie existente de OPTICS a un bajo coste 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 agrupamiento de enlace único y OPTICS, eliminando el parámetro y ofreciendo mejoras de rendimiento con respecto a OPTICS. $\varepsilon$

HiSC ^[7] es un método de agrupamiento de subespacios jerárquicos (eje-paralelo) basado en OPTICS.

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

DiSH ^[9] es una mejora sobre 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 límite de los clústeres y, por lo tanto, siguiendo más estrictamente la definición básica de niveles de densidad de Hartigan. ^[12]

Disponibilidad

Las implementaciones de 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 con extracción automática de clústeres mediante el método de extracción ξ). Otras implementaciones de 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úster ξ y estilo dbscan tradicional) utilizando un árbol kd para aceleración de índice solo para 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.

Referencias

^ Kriegel, Hans-Peter; Kröger, Peer; Sander, Jörg; Zimek, Arthur (mayo de 2011). "Agrupamiento basado en la densidad". Wiley Interdisciplinary Reviews: Minería de datos y descubrimiento de conocimiento . 1 (3): 231–240. doi :10.1002/widm.30. S2CID 36920706.
^ Mihael Ankerst; Markus M. Breunig; Hans-Peter Kriegel ; Jörg Sander (1999). ÓPTICA: Ordenación de puntos para identificar la estructura de agrupamiento . Conferencia internacional ACM SIGMOD sobre gestión de datos. ACM Press . págs. 49–60. CiteSeerX 10.1.1.129.6542 .
^ Martin Ester ; Hans-Peter Kriegel ; Jörg Sander; Xiaowei Xu (1996). Evangelos Simoudis; Jiawei Han; Usama M. Fayyad (eds.). Un algoritmo basado en densidad para descubrir clústeres en grandes bases de datos espaciales con ruido . Actas de la Segunda Conferencia Internacional sobre Descubrimiento de Conocimiento y Minería de Datos (KDD-96). AAAI Press . págs. 226–231. CiteSeerX 10.1.1.71.1980 . ISBN 1-57735-004-9.
^ Schubert, Erich; Gertz, Michael (22 de agosto de 2018). Mejora de la estructura del clúster extraída de gráficos OPTICS (PDF) . Lernen, Wissen, Daten, Analysen (LWDA 2018). vol. CEUR-WS 2191. págs. 318–329 - vía CEUR-WS.
^ Markus M. Breunig; Hans-Peter Kriegel ; Raymond T. Ng; Jörg Sander (1999). "OPTICS-OF: Identificación de valores atípicos locales". Principios de minería de datos y descubrimiento de conocimiento. Apuntes de clase en informática. Vol. 1704. Springer-Verlag . págs. 262–270. doi :10.1007/b72280. ISBN. 978-3-540-66490-1. Número de identificación del sujeto 27352458.
^ Achtert, Elke; Böhm, Christian; Kröger, Peer (2006). "DeLi-Clu: Impulsando la robustez, la completitud, la usabilidad y la eficiencia de la agrupación jerárquica mediante una clasificación de pares más cercanos". En Ng, Wee Keong; Kitsuregawa, Masaru; Li, Jianzhong; Chang, Kuiyu (eds.). Avances en el descubrimiento de conocimientos y la minería de datos, 10.ª Conferencia Pacífico-Asia, PAKDD 2006, Singapur, 9-12 de abril de 2006, Actas . Apuntes de clase en informática. Vol. 3918. Springer. págs. 119–128. doi :10.1007/11731139_16.
^ Achtert, Elke; Böhm, Christian; Kriegel, Hans-Peter; Kröger, Peer; Müller-Gorman, Ina; Zimek, Arthur (2006). "Encontrar jerarquías de agrupaciones de subespacios". En Fürnkranz, Johannes; Scheffer, Tobias; Spiliopoulou, Myra (eds.). Descubrimiento de conocimiento en bases de datos: PKDD 2006, 10.ª Conferencia europea sobre principios y práctica del descubrimiento de conocimiento en bases de datos, Berlín, Alemania, 18-22 de septiembre de 2006, Actas . Apuntes de clase en informática. Vol. 4213. Springer. págs. 446–453. doi : 10.1007/11871637_42 .
^ Achtert, E.; Böhm, C.; Kröger, P.; Zimek, A. (2006). "Extracción de jerarquías de clústeres de correlación". 18.ª Conferencia internacional sobre gestión de bases de datos científicas y estadísticas (SSDBM'06) . pp. 119–128. CiteSeerX 10.1.1.707.7872 . doi :10.1109/SSDBM.2006.35. ISBN . 978-0-7695-2590-7. Número de identificación del sujeto 2679909.
^ Achtert, Elke; Böhm, Christian; Kriegel, Hans-Peter; Kröger, Peer; Müller-Gorman, Ina; Zimek, Arthur (2007). "Detección y visualización de jerarquías de clústeres de subespacios". En Ramamohanarao, Kotagiri; Krishna, P. Radha; Mohania, Mukesh K.; Nantajeewarawat, Ekawit (eds.). Avances en bases de datos: conceptos, sistemas y aplicaciones, 12.ª Conferencia internacional sobre sistemas de bases de datos para aplicaciones avanzadas, DASFAA 2007, Bangkok, Tailandia, 9-12 de abril de 2007, Actas . Apuntes de clase en informática. Vol. 4443. Springer. págs. 152–163. doi :10.1007/978-3-540-71703-4_15.
^ Schneider, Johannes; Vlachos, Michail (2013). "Agrupamiento rápido sin parámetros basado en densidad mediante proyecciones aleatorias". 22.ª Conferencia internacional de la ACM sobre gestión de la información y el conocimiento (CIKM) .
^ Campello, Ricardo JGB; Moulavi, Davoud; Zimek, Arthur; Sander, Jörg (22 de julio de 2015). "Estimaciones de densidad jerárquica para agrupamiento de datos, visualización y detección de valores atípicos". ACM Transactions on Knowledge Discovery from Data . 10 (1): 1–51. doi :10.1145/2733381. S2CID 2887636.
^ JA Hartigan (1975). Algoritmos de agrupamiento . John Wiley & Sons.