Algoritmo de agrupamiento OPTICS

Ordenar puntos para identificar la estructura de agrupamiento ( OPTICS ) es un algoritmo para encontrar [1] agrupamientos en datos espaciales basados en la densidad . El algoritmo fue presentado por Michael Ankerst, Markus M. Breunig, Hans-Peter Kriegel y Jörg Sander [2] . La idea básica del algoritmo es similar a DBSCAN [3] , pero el algoritmo está diseñado para deshacerse de una de las principales debilidades del algoritmo DBSCAN: el problema de detectar grupos significativos en datos que tienen diferentes densidades. Para hacer esto, los puntos de la base de datos se ordenan (linealmente) de modo que los puntos espacialmente cercanos se conviertan en vecinos en el ordenamiento. Además, se almacena una distancia especial para cada punto, que representa la densidad que se debe asumir para el clúster para que los puntos pertenezcan al mismo clúster. Esto se representa como un dendrograma .

Idea principal

Al igual que DBSCAN , el algoritmo OPTICS requiere dos parámetros: el parámetro ε describe la distancia máxima (radio) que se tiene en cuenta y el parámetro MinPts describe la cantidad de puntos necesarios para formar un grupo. Un punto p es un punto central si al menos MinPts de puntos están en su vecindario ε . A diferencia de DBSCAN , el algoritmo 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 básica , que describe la distancia al punto más cercano de MinPts : ${\ Displaystyle N_ {\ varepsilon} (p)}$

{\text{core-dist}}_{\mathit {\varepsilon ,MinPts}}={\begin{cases}{\text{INDEFINED}}&|N_{\varepsilon }(p)|<{ \mathit {MinPts}}\\{\mathit {MinPts}}{\text{-th}}N_{\varepsilon }(p)&|N_{\varepsilon }(p)|\geqslant {\mathit {MinPts} }\end{casos}}

Aquí core-dist = distancia del núcleo, = -th en orden ascendente de distancia a . ${\mathit {MinPts}}{\text{-th}}N_{\varepsilon}(p)$ ${\mathit {MinPts))$ ${\ Displaystyle N_ {\ varepsilon} (p)}$

La distancia alcanzable del punto o desde el punto p es la distancia entre o y p , o la distancia básica del punto p , la que sea mayor:

{\text{dist-accesibilidad}}_{\mathit {\varepsilon ,MinPts}}(o,p)={\begin{cases}{\text{INDEFINED}}&|N_{\varepsilon }( p)|<{\mathit {MinPts}}\\\max({\text{core-dist}}_{\mathit {\varepsilon ,MinPts}}(p),{\text{dist}}(p, o))&|N_{\varepsilon }(p)|\geqslant {\mathit {MinPts}}\end{casos}}

Aquí reachability-dist = distancia alcanzable.

Si p y o son los vecinos más cercanos y , podemos suponer que p y o pertenecen al mismo grupo. ${\ estilo de visualización \ varepsilon '<\ varepsilon}$

Tanto las distancias básicas como las alcanzables no están definidas a menos que haya un grupo suficientemente denso (como se aplica a ε ). Dado un ε lo suficientemente grande , esto nunca sucederá, pero luego cualquier consulta de ε -vecindario devolverá la base de datos completa, lo que resultará en tiempo de ejecución . El parámetro ε es necesario para cortar grupos sueltos que ya no son interesantes y, por lo tanto, acelerar el algoritmo. $O(n^{2})$

El parámetro ε es, estrictamente hablando, opcional. Simplemente se puede establecer en el valor máximo posible. Sin embargo, cuando un índice espacial está disponible, afecta la complejidad computacional. OPTICS difiere de DBSCAN en que este parámetro no se tiene en cuenta, si ε puede influir, solo configurando el valor máximo.

Pseudocódigo

El enfoque básico del algoritmo OPTICS es el mismo que DBSCAN , pero en lugar de admitir muchos miembros de clúster conocidos pero aún no procesados, se utiliza una cola de prioridad (es decir, un montón indexado ).

ÓPTICA (DB, eps, MinPts) para cada punto p de DB p.reachable_distance=indefinido para cada punto bruto p de DB N=obtenerVecinos (p, eps) marcar p como procesado poner p en una lista ordenada if (base_distance(p, eps, Minpts) != indefinido) Semillas = cola de prioridad vacía actualizar (N, p, Semillas, eps, Minpts) para cada siguiente q de Seeds N'=obtenerVecinos(q, eps) marcar q como procesado poner q en una lista ordenada if (distancia_básica(q, eps, Minpts) != indefinido) actualización (N', q, Semillas, eps, Minpts)

En el procedimiento de actualización (), la cola de prioridad de semillas se actualiza por vecinos de los puntos y, en consecuencia: $\varepsilon$ $pags$ $q$

actualización (N, p, Semillas, eps, Minpts) coredist=distancia_base(p, eps, MinPts) para cada o en N si (o no procesado) new_dist_dist=max(corredista, dist(p,o)) if (o.reachable_distance == indefinido) // el punto o no está en Seeds o.reach_distance=nueva_distancia_de_alcance Seeds.insert(o, new_delivery_dist) de lo contrario // punto o en Seeds, compruebe si hay mejoras if (nueva_distancia_de_alcance < o. distancia_de_alcance) o.reach_distance=nueva_distancia_de_alcance Seeds.move_up(o, new_advance_growth)

OPTICS coloca los puntos en un cierto orden, marcándolos con la distancia más pequeña posible (en el algoritmo original, también se recuerda la distancia principal, pero esto no es necesario para el procesamiento posterior).

Extracción de clústeres

Usando un gráfico de accesibilidad (un tipo especial de diagrama de árbol ), es fácil obtener una estructura jerárquica de grupos. Esta es una gráfica 2D donde los puntos se trazan en el eje x en el orden en que son procesados por el algoritmo OPTICS, y la distancia alcanzable se traza en el eje y. Debido a que los puntos que pertenecen a un clúster tienen una pequeña distancia alcanzable a su vecino más cercano, los clústeres parecen valles en un gráfico de accesibilidad. Cuanto más profundo es el valle, más denso es el racimo.

La figura anterior ilustra este concepto. El área superior izquierda de la figura muestra el conjunto de datos simulados. El área superior derecha de la figura visualiza el árbol de expansión obtenido por el algoritmo OPTICS, y la parte inferior de la figura muestra el diagrama de alcanzabilidad obtenido por OPTICS. Los colores de este gráfico son etiquetas y no los calcula el algoritmo. Sin embargo, se ve claramente cómo los valles en el gráfico corresponden a los grupos del conjunto de datos dado. Los puntos amarillos de esta imagen se consideran ruido y no corresponden a ningún valle. Por lo general, no se asignan a ningún clúster, excepto al clúster general "todos los datos" en el resultado jerárquico.

La extracción de grupos de dicho gráfico se puede hacer manualmente seleccionando intervalos en el eje x después de ver el gráfico, eligiendo un umbral en el eje y (entonces el resultado es similar al agrupamiento DBSCAN con los mismos valores y minPts, en nuestro caso un valor de 0.1 puede dar buenos resultados), o usando varios algoritmos que intentan determinar los valles por la inclinación del gráfico, por la curvatura o por máximos locales. Los agrupamientos obtenidos de esta manera suelen ser jerárquicos y no se pueden obtener en una sola ejecución del algoritmo DBSCAN. $\varepsilon$

Dificultad

Al igual que DBSCAN , el algoritmo procesa cada punto solo una vez y realiza una consulta de un vecino durante este procesamiento. Dado un índice espacial que asegura que la consulta de vecindad se ejecuta a tiempo , obtenemos el tiempo total de ejecución . Los autores del artículo original en OPTICS informan una desaceleración constante de 1,6 veces en comparación con DBSCAN. Tenga en cuenta que el valor puede afectar en gran medida el costo del algoritmo, ya que un valor demasiado grande puede aumentar la complejidad de la consulta de vecindad a una lineal. $O(\log n)$ $O(n\cdot\log n)$ $\varepsilon$

En particular, es posible una selección (mayor que la distancia máxima en el conjunto de datos), pero obviamente conduce a una complejidad cuadrática, ya que una consulta de lista de vecinos devuelve el conjunto de datos completo. Incluso si no hay ningún índice espacial disponible, esto da como resultado una sobrecarga adicional en el mantenimiento del almacenamiento dinámico. Por lo tanto, se debe elegir adecuadamente para el conjunto de datos. $\varepsilon >\max _{x,y}d(x,y)$ $\varepsilon$

Extensiones

OPTICS-OF [4] es un algoritmo de detección de anomalías basado en OPTICS. Se utiliza principalmente para extraer valores atípicos de una ejecución existente del algoritmo OPTICS a un bajo costo en comparación con otros métodos de extracción de valores atípicos. La versión más conocida del algoritmo de detección de valores atípicos locales se basa en los mismos conceptos.

DeLi-Clu [5] , ( Density-Link-Clustering ) combina ideas del método de agrupamiento único y el algoritmo OPTICS, eliminando el parámetro y agregando mejoras de eficiencia sobre OPTICS. $\varepsilon$

HiSC [6] es un método de agrupamiento subespacial jerárquico (paralelo a los ejes) basado en OPTICS.

HiCO [7] es un algoritmo de agrupamiento de correlación jerárquica basado en OPTICS.

DiSH [8] es una mejora del algoritmo HiSC que puede encontrar jerarquías más complejas.

FOPTICS [9] es una implementación rápida que utiliza proyecciones aleatorias.

HDBSCAN* [10] se basa en una mejora del algoritmo DBSCAN mediante la exclusión de los puntos límite de los grupos y, por lo tanto, una definición más rigurosa de los niveles de densidad (según Hartigan) [11] .

Disponibilidad

Las implementaciones Java de OPTICS, OPTICS-OF, DeLi-Clu, HiSC, HiCO y DiSH están disponibles en el sistema de minería de datos ELKI (con índice acelerado para algunas funciones de distancia y con agrupamiento automático usando el método ξ). Otra implementación de Java incluye una extensión del kit de herramientas de Weka (sin soporte para la agrupación en clústeres con ξ). El paquete de lenguaje R "dbscan" incluye una implementación en C++ del algoritmo OPTICS (con agrupamiento tradicional como dbscan y ξ) que utiliza un árbol de dimensiones K para acelerar el índice de la distancia euclidiana.

El lenguaje Python tiene las siguientes implementaciones. OPTICS está disponible en la biblioteca PyClustering . HDBSCAN está disponible en la biblioteca hdbscan , que se basa en scikit learn .

Notas

↑ Kriegel, Kröger, Sander, Zimek, 2011 , pág. 231–240.
↑ Ankerst, Breunig, Kriegel, Sander, 1999 , pág. 49–60.
↑ Ester, Kriegel, Sander, Xu, 1996 , pág. 226–231.
↑ Breunig, Kriegel, Ng, Sander, 1999 , pág. 262–270.
↑ Achtert, Böhm, Kröger, 2006 , pág. 119–128.
↑ Achtert, Böhm, Kriegel, Kröger, Müller-Gorman, Zimek, 2006 , pág. 446–453.
↑ Achtert, Böhm, Kröger, Zimek, 2006 , pág. 119–128.
↑ Achtert, Böhm, Kriegel, Kröger, Müller-Gorman, Zimek, 2007 , pág. 152–163.
↑ Schneider, Vlachos, 2013 .
↑ Campello, Moulavi, Zimek, Sander, 2015 , p. 1–51.
↑ Hartigan, 1975 .

Literatura

Hans-Peter Kriegel, Peer Kröger, Jörg Sander, Arthur Zimek. Agrupación basada en densidad // Revisiones interdisciplinarias de Wiley: minería de datos y descubrimiento de conocimiento. - 2011. - mayo ( vol. 1 , número 3 ). — S. 231–240 . -doi : 10.1002/ widm.30 .
Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, Jörg Sander. ÓPTICA: Puntos de Ordenación para Identificar la Estructura de Clustering // =ACM Congreso internacional SIGMOD sobre Gestión de datos . - Prensa ACM , 1999. - S. 49-60.
Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu. 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) / Evangelos Simoudis, Jiawei Han, Usama M. Fayyad. - Prensa AAAI , 1996. - S. 226-231. — ISBN 1-57735-004-9 .
Markus M. Breunig, Hans-Peter Kriegel, Raymond T. Ng, Jörg Sander. OPTICS-OF: Identificación de valores atípicos locales // Principios de minería de datos y descubrimiento de conocimiento . - Springer-Verlag , 1999. - S. 262 -270. - ISBN 978-3-540-66490-1 . -doi : 10.1007/ b72280 .
Achtert E., Böhm C., Kröger P. DeLi-Clu: Aumento de la robustez, integridad, usabilidad y eficiencia de la agrupación jerárquica mediante una clasificación de pares más cercanos. - 2006. - T. 3918. - S. 119-128. — (Apuntes de clase en informática). - ISBN 978-3-540-33206-0 . -doi : 10.1007/ 11731139_16 .
Achtert E., Böhm C., Kriegel HP, Kröger P., Müller-Gorman I., Zimek A. Búsqueda de jerarquías de clústeres subespaciales // LNCS: Descubrimiento de conocimiento en bases de datos: PKDD 2006. - 2006. - V. 4213 . — S. 446–453 . - ISBN 978-3-540-45374-1 . -doi : 10.1007/ 11871637_42 .
Achtert E., Böhm C., Kröger P., Zimek A. Minería de jerarquías de clústeres de correlación // Proc. 18ª Conferencia Internacional sobre Gestión de Bases de Datos Científicas y Estadísticas (SSDBM). - 2006. - S. 119-128. — ISBN 0-7695-2590-3 . -doi : 10.1109/ SSDBM.2006.35 .
Achtert E., Böhm C., Kriegel HP, Kröger P., Müller-Gorman I., Zimek A. Detección y visualización de jerarquías de clústeres subespaciales // LNCS: avances en bases de datos: conceptos, sistemas y aplicaciones. - 2007. - T. 4443 . — S. 152–163 . - ISBN 978-3-540-71702-7 . -doi : 10.1007 / 978-3-540-71703-4_15 .
Johannes Schneider, Michail Vlachos. Agrupación rápida sin parámetros basada en la densidad a través de proyecciones aleatorias // 22ª Conferencia Internacional ACM sobre Gestión de la Información y el Conocimiento (CIKM). — ACM, 2013.
Campello RJGB, Davoud Moulavi, Arthur Zimek, Jörg Sander. Estimaciones de densidad jerárquica para agrupación de datos, visualización y detección de valores atípicos // Transacciones de ACM en el descubrimiento de conocimiento a partir de datos. - 2015. - T. 10 , núm. 1 . — S. 1–51 . -doi : 10.1145/ 2733381 .
Juan Hartigan algoritmos de agrupamiento. - John Wiley & Sons, 1975. - (Series de Wiley en probabilidad y estadística matemática). — ISBN 0-471-35645-X .

Aprendizaje automático y minería de datos
Tareas	Problema de clasificación Aprender sin un maestro Aprendizaje asistido por profesores Análisis de regresión AutoML reglas de asociación Extracción de características entrenamiento de rasgos Entrenamiento de clasificación Derivación gramatical Aprender en línea
Aprendiendo con un maestro	método del k-vecino más cercano Clasificador bayesiano ingenuo árbol de decisión Máquinas de vectores soporte Regresión lineal Regresión logística perceptrón conjuntos de modelos Harpillera impulsar bosque aleatorio Método de vector relevante
análisis de conglomerados	método k-medias método de agrupamiento difuso Agrupación jerárquica algoritmo EM ABEDUL CURAR DBSCAN ÓPTICA Desplazamiento medio
Reducción de dimensionalidad	Análisis factorial Método de componentes principales CCA ICA LDA Expansión de matriz no negativa t-SNE
Pronóstico estructural	Graficar modelo probabilístico red bayesiana Modelo oculto de Markov FRC
Detección de anomalías	método del k-vecino más cercano Nivel de emisión local
Graficar modelos probabilísticos	red bayesiana Red de Markov Modelo oculto de Markov
Redes neuronales	Máquina Boltzmann limitada mapa autoorganizado Función de activación Sigmoideo softmax Funcion de base radial Método de propagación hacia atrás Aprendizaje profundo perceptrón multicapa Red neuronal recurrente memoria a corto plazo Bloque recurrente controlado Red neuronal convolucional U-red Codificador automático
Aprendizaje reforzado	proceso de Markov Ecuación de Bellman Algoritmo codicioso Q-aprendizaje SARAS Diferencia temporal (DT)
Teoría	Teoría de Vapnik-Chervonenkis Dilema de dispersión de sesgo Teoría del aprendizaje computacional Minimización empírica del riesgo El aprendizaje de Occam aprendizaje PAC Teoría del aprendizaje estadístico
revistas y congresos	NeurIPS ICML ML JMLR ArXiv:cs.LG