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 agrupaciones significativas en datos de densidad variable. Para hacerlo, los puntos de la base de datos se ordenan (linealmente) de modo que los puntos más cercanos espacialmente se conviertan en vecinos en el orden. Adicionalmente, se almacena una distancia especial para cada punto que representa la densidad que se debe aceptar para un cluster para que ambos puntos pertenezcan al mismo cluster. 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 el número de puntos necesarios para formar un grupo. Un punto p es un punto central si al menos los puntos MinPts se encuentran dentro de su vecindario ε(incluido el propio punto p ). 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 más cercano del MinPts :
La distancia de accesibilidad de otro punto o desde un punto p es la distancia entre o y p , o la distancia del núcleo de p , la que sea mayor:
Si P y O son los vecinos más cercanos, este es eltenemos que asumir para tener p y o pertenecen al mismo grupo.
Tanto la distancia del núcleo como la distancia de accesibilidad no están definidas si no hay disponible un grupo suficientemente denso (wrt ε ). Dado un ε suficientemente grande , esto nunca sucede, pero luego cada ε -consulta de vecindario devuelve la base de datos completa, lo que resulta entiempo de ejecución. Por lo tanto, se requiere el parámetro ε para cortar la densidad de los grupos que ya no son interesantes y para acelerar el algoritmo.
El parámetro ε , estrictamente hablando, no es necesario. Simplemente se puede establecer en el valor máximo posible. Cuando un índice espacial está disponible, sin embargo, juega un papel práctico con respecto a la complejidad. OPTICS se abstrae de DBSCAN eliminando este parámetro, al menos en la medida en que solo tenga que dar el valor máximo.
Pseudocódigo
El enfoque básico de OPTICS es similar a DBSCAN , pero en lugar de mantener miembros de clúster conocidos, pero hasta ahora no procesados, en un conjunto, se mantienen en una cola de prioridad (por ejemplo, usando un montón indexado ).
La función OPTICS (DB, eps, MinPts) es para cada punto p de DB do p.reachability-distance = UNDEFINED para cada punto p no procesado de DB, haga N = obtener vecinos (p, eps) marcar p como procesado salida p a la lista ordenada if core-distance (p, eps, MinPts)! = UNDEFINED entonces Semillas = cola de prioridad vacía actualizar (N, p, Seeds, eps, MinPts) para cada siguiente q en Seeds hacemos N '= obtener vecinos (q, eps) marcar q como procesado salida q a la lista ordenada if core-distance (q, eps, MinPts)! = UNDEFINED hacer actualizar (N ', q, Seeds, eps, MinPts)
En update (), la cola de prioridad Semillas se actualiza con el -barrio de y , respectivamente:
La actualización de la función (N, p, Seeds, eps, MinPts) es coredista = distancia del núcleo (p, eps, MinPts) para cada o en N si o no se procesa, entonces nuevo-alcance-dist = max (coredista, dist (p, o)) si o.reachability-distance == UNDEFINED entonces // o no está en Seeds o.reachability-distance = new-reach-dist Seeds.insert (o, nuevo-alcance-dist) else // o en Seeds, verifique la mejora si new-reach-distentonces o.reachability-distance = new-reach-dist 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 del núcleo también se exporta, pero esto no es necesario para un procesamiento posterior).
Extrayendo los clústeres
Utilizando un diagrama de accesibilidad (un tipo especial de dendrograma ), se puede obtener fácilmente la estructura jerárquica de los conglomerados. Es una gráfica 2D, con el orden de los puntos procesados por OPTICS en el eje xy la distancia de alcance 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 se muestran como valles en la gráfica 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 de este gráfico son etiquetas y no los calcula el algoritmo; 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 el grupo omnipresente de "todos los datos" en un resultado jerárquico.
La extracción de grupos de este gráfico se puede hacer manualmente seleccionando un rango en el eje x después de la inspección visual, seleccionando un umbral en el eje y (el resultado es similar a un resultado de agrupamiento DBSCAN con el mismo 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. Las agrupaciones obtenidas de esta manera suelen ser jerárquicas y no se pueden lograr con una sola ejecución de DBSCAN.
Complejidad
Como DBSCAN , OPTICS procesa cada punto una vez y realiza uno-consulta de vecindario durante este procesamiento. Dado un índice espacial que otorga una consulta de vecindario en tiempo de ejecución, un tiempo de ejecución general de es obtenido. Los autores del artículo OPTICS original informan 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, eligiendo (mayor que la distancia máxima en el conjunto de datos) es posible, pero conduce a 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 tiene un costo adicional en la administración del montón. Por lo tanto, debe elegirse adecuadamente para el conjunto de datos.
Extensiones
OPTICS-OF [4] 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 LOF más conocida se basa en los mismos conceptos.
DeLi-Clu, [5] Density-Link-Clustering combina ideas de clustering de enlace único y OPTICS, eliminando la parámetro y ofreciendo mejoras de rendimiento sobre OPTICS.
HiSC [6] es un método de agrupamiento subespacial jerárquico (eje paralelo) basado en OPTICS.
HiCO [7] es un algoritmo de agrupamiento de correlación jerárquica basado en OPTICS.
DiSH [8] es una mejora sobre HiSC que puede encontrar jerarquías más complejas.
FOPTICS [9] es una implementación más rápida que utiliza proyecciones aleatorias.
HDBSCAN * [10] se basa en un refinamiento de DBSCAN, excluyendo los puntos fronterizos de los conglomerados y, por tanto, siguiendo más estrictamente la definición básica de niveles de densidad de Hartigan. [11]
Disponibilidad
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 mediante el método de extracción ξ). Otras implementaciones de Java incluyen la extensión Weka (sin soporte para extraction extracción de clústeres).
El paquete R "dbscan" incluye una implementación C ++ de OPTICS (con extracción de clúster ξ y similar a dbscan tradicional) usando un árbol kd para la aceleración del índice solo para la distancia euclidiana.
Las implementaciones de Python de OPTICS 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). "Agrupación basada en densidad" . Revisiones interdisciplinarias de Wiley: minería de datos y descubrimiento de conocimientos . 1 (3): 231–240. doi : 10.1002 / widm.30 .
- ^ Mihael Ankerst; Markus M. Breunig; Hans-Peter Kriegel ; Jörg Sander (1999). ÓPTICA: Ordenar puntos para identificar la estructura de agrupamiento . Conferencia internacional ACM SIGMOD sobre Gestión de datos. Prensa ACM . 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.
- ^ Markus M. Breunig; Hans-Peter Kriegel ; Raymond T. Ng; Jörg Sander (1999). "ÓPTICA-DE: Identificación de valores atípicos locales" . Principios de minería de datos y descubrimiento de conocimientos . Apuntes de conferencias en Ciencias de la Computación. 1704 . Springer-Verlag . págs. 262-270. doi : 10.1007 / b72280 . ISBN 978-3-540-66490-1.
- ^ Achtert, E .; Böhm, C .; Kröger, P. (2006). DeLi-Clu: Impulsar la robustez, la integridad, la usabilidad y la eficiencia de la agrupación jerárquica por un ranking de par más cercano . LNCS: avances en el descubrimiento de conocimientos y minería de datos . Apuntes de conferencias en Ciencias de la Computación. 3918 . págs. 119-128. doi : 10.1007 / 11731139_16 . ISBN 978-3-540-33206-0.
- ^ Achtert, E .; Böhm, C .; Kriegel, HP ; Kröger, P .; Müller-Gorman, I .; Zimek, A. (2006). Encontrar jerarquías de clústeres subespaciales . LNCS: Descubrimiento de conocimiento en bases de datos: PKDD 2006 . Apuntes de conferencias en Ciencias de la Computación. 4213 . págs. 446–453. CiteSeerX 10.1.1.705.2956 . doi : 10.1007 / 11871637_42 . ISBN 978-3-540-45374-1.
- ^ Achtert, E .; Böhm, C .; Kröger, P .; Zimek, A. (2006). Jerarquías mineras de clústeres de correlación . Proc. 18a Conferencia Internacional sobre Gestión de Bases de Datos Científicas y Estadísticas (SSDBM) . págs. 119-128. CiteSeerX 10.1.1.707.7872 . doi : 10.1109 / SSDBM.2006.35 . ISBN 978-0-7695-2590-7.
- ^ Achtert, E .; Böhm, C .; Kriegel, HP ; Kröger, P .; Müller-Gorman, I .; Zimek, A. (2007). Detección y visualización de jerarquías de clústeres subespaciales . LNCS: Avances en Bases de Datos: Conceptos, Sistemas y Aplicaciones . Apuntes de conferencias en Ciencias de la Computación. 4443 . págs. 152-163. CiteSeerX 10.1.1.70.7843 . doi : 10.1007 / 978-3-540-71703-4_15 . ISBN 978-3-540-71702-7.
- ^ Schneider, Johannes; Vlachos, Michail (2013). "Agrupación rápida basada en densidad sin parámetros a través de proyecciones aleatorias". 22ª Conferencia Internacional 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 la agrupación de datos, visualización y detección de valores atípicos". Transacciones de ACM sobre el descubrimiento de conocimientos a partir de datos . 10 (1): 1–51. doi : 10.1145 / 2733381 .
- ^ JA Hartigan (1975). Algoritmos de agrupamiento . John Wiley e hijos.