Método de agrupación basada en densidad Agrupación basada en densidad
La agrupación en clústeres tiene una amplia gama de aplicaciones. Por ejemplo, en aplicaciones empresariales, la agrupación en clústeres puede ayudar a los especialistas en marketing a estratificar a los clientes según sus atributos y descubrir diferentes grupos de clientes y sus tendencias de compra (como se muestra a continuación) (como se muestra en la figura). , que clasifica a los clientes según sus preferencias de color). De esta manera, las empresas pueden identificar mercados potenciales y desarrollar productos y servicios de manera más eficiente. En el análisis de texto, la agrupación puede ayudar a los periodistas a clasificar los últimos tweets en función de la similitud de temas y derivar rápidamente noticias candentes y grupos de atención. En biomedicina, la agrupación se puede utilizar para comprender la función de genes desconocidos basándose en la agrupación de genes con perfiles de expresión similares.
Dado que la agrupación en clústeres es un método de aprendizaje no supervisado, los diferentes métodos de agrupación se basan en diferentes suposiciones y tipos de datos. No existe un algoritmo de agrupamiento universal que sirva para todos, y cada algoritmo de agrupamiento tiene sus limitaciones y sesgos porque los datos a menudo se pueden clasificar de diferentes maneras. Es decir, un determinado algoritmo de agrupamiento puede ser muy eficaz con los datos de mercado, pero no con los datos genéticos.
Existen muchos algoritmos de agrupamiento, incluidos algoritmos de agrupamiento basados en particiones (como k-means), algoritmos de agrupamiento jerárquico (como BIRCH), algoritmos de agrupamiento basados en densidad (como DBSCAN), algoritmos de agrupamiento basados en red algoritmos de agrupamiento Algoritmos de agrupamiento de celosía (como STING), etc. Este artículo presentará uno de los métodos de agrupación más utilizados: la agrupación basada en densidad.
En comparación con otros métodos de agrupación, la agrupación basada en densidad puede encontrar grupos de diversas formas y tamaños en datos ruidosos. DBSCAN (Ester, 1996) es uno de los algoritmos más representativos de este tipo (DBSCAN ganó el premio SIGKDD Test of Time 2014). La idea central es descubrir primero puntos de alta densidad y luego conectar gradualmente todos los puntos de alta densidad similares para generar varios grupos. La implementación del algoritmo es dibujar un círculo con cada punto de datos como centro y eps como radio (llamado vecindario eps-vecindario), y luego contar cuántos puntos hay en el círculo. Este número es el valor de densidad del círculo. agujas. Luego podemos elegir un umbral de densidad MinPts. Por ejemplo, el centro del círculo con un número de puntos en el círculo menor que MinPts es un punto de baja densidad y el centro del círculo con un número de puntos mayor o igual. a MinPts es un punto de alta densidad (llamado punto central). Si hay un punto de alta densidad en el círculo de otro punto de alta densidad, conectamos los dos puntos para poder encadenar tantos puntos seguidos. Después de eso, si hay un punto de baja densidad dentro del círculo de un punto de alta densidad, lo conectamos al punto de alta densidad más cercano y lo llamamos punto límite. De esta manera, todos los puntos que se pueden conectar forman un grupo, y los puntos de baja densidad que no están dentro de ningún círculo de puntos de alta densidad son valores atípicos. El siguiente diagrama muestra cómo funciona DBSCAN.
Dado que DBSCAN descubre grupos conectando continuamente puntos de alta densidad en un vecindario, puede descubrir grupos de diferentes formas y tamaños simplemente definiendo el tamaño del vecindario y los umbrales de densidad. La siguiente figura muestra los resultados de agrupación de DBSCAN en dos dimensiones.
El pseudocódigo del algoritmo DBSCAN se expresa de la siguiente manera:
Dado que DBSCAN utiliza el umbral de densidad global MinPts, solo puede encontrar grupos compuestos por puntos con una densidad no menor que MinPts. es decir, es difícil encontrar agrupaciones de diferente densidad.
Ejemplos de sus éxitos y fracasos son los siguientes:
Para resolver el problema de descubrir conglomerados de diferentes densidades, se han inventado muchos métodos nuevos, como la ÓPTICA (Ordenar puntos para identificar estructuras de conglomerados), que empareja pares adyacentes. Clústeres basados en la densidad Los puntos se clasifican y luego se descubren grupos de diferentes densidades utilizando métodos de visualización. OPTICS debe funcionar a través de otros algoritmos para encontrar "valles" en el gráfico de visualización para descubrir grupos, por lo que su rendimiento está directamente limitado por estos algoritmos.
Además, SNN (vecino más cercano compartido) mejora DBSCAN mediante el uso del método de similitud basado en KNN (vecino más cercano). La similitud entre dos puntos es calcular cuántos k puntos vecinos más cercanos tienen estos dos puntos. Si dos puntos no son ****, o ninguno de los puntos es el k vecino más cercano del otro, la similitud entre los dos puntos es 0. Luego reemplazamos la fórmula de distancia en DBSCAN con similitud SNN, recalculamos la vecindad y la densidad de cada punto y encontramos grupos con diferentes densidades. El núcleo de SNN es que reemplazamos el cálculo de densidad original con un cálculo de densidad basado en el rango de vecindad de cada par de puntos y el rango de vecindad de cada par de puntos. La desventaja de SNN es que se debe definir el número de vecinos k y su rendimiento es sensible al tamaño de k. La siguiente figura ilustra cómo SNN calcula la densidad de los clústeres. La siguiente figura muestra cómo SNN calcula la similitud.
En 2014, la revista Science publicó un algoritmo basado en picos de densidad DP (Clustering by Fast Search and Find Density Peaks), que también utiliza la visualización para ayudar a encontrar grupos de diferentes densidades. La idea es que cada grupo tiene un punto de densidad máxima como centro del grupo que atrae y conecta puntos circundantes de baja densidad, y los diferentes centros del grupo están relativamente alejados. Para hacer esto, primero calcula la densidad de cada punto (también calcula cuántos puntos hay en el vecindario eps-vecindario) y luego calcula la distancia de cada punto al punto más cercano con una densidad mayor que él. Por lo tanto, para cada punto, tenemos dos valores de atributo, uno es su propio valor de densidad y el otro es su valor de distancia al punto más cercano con una densidad mayor que él. Para estos dos atributos, podemos generar un diagrama bidimensional (diagrama de decisión) tal que el punto superior derecho represente el centro de diferentes clusters, es decir, el punto con mayor densidad y más alejado de otros centros de clusters. Luego, podemos conectar gradualmente otros puntos al punto más cercano con una densidad mayor que él, hasta que finalmente los conectemos a un determinado punto central del grupo. De esta forma, todos los puntos que disfrutan del centro del clúster pertenecen a un clúster, mientras que aquellos puntos que están lejos de otros puntos y tienen una densidad muy baja pertenecen a valores atípicos. Dado que este método conecta puntos según la distancia relativa y la densidad relativa, se pueden encontrar grupos de diferentes densidades. La desventaja de DP es que cada grupo debe tener un punto de densidad máxima como centro del grupo. Si la densidad de un grupo se distribuye uniformemente, o un grupo tiene múltiples puntos de alta densidad, algunos grupos se dividirán en varios subgrupos. racimos. Además, DP también requiere que el usuario especifique cuántos grupos hay, lo que requiere ajustes constantes de prueba y error en la práctica. La siguiente figura muestra el diagrama de decisión generado por DP.
Además de esto, la estimación del índice de densidad también se puede utilizar para superar la incapacidad de DBSCAN para descubrir grupos de diferentes densidades. La idea central de la relación de densidad es que para cada punto, se calcula la relación entre su densidad y la densidad de su vecindario y luego se utiliza el cálculo de la relación de densidad para reemplazar el cálculo de densidad de DBSCAN para encontrar el punto central, mientras que otros procesos y DBSCAN permanecen sin cambios. De esta manera, cada punto local de alta densidad se selecciona como un punto central, descubriendo así grupos de diferentes densidades. Con base en esta idea, también podemos normalizar (ReScale) los datos originales de acuerdo con su distribución de densidad, es decir, expandir las áreas de alta densidad y continuar reduciendo las áreas de baja densidad. De esta manera, los grupos con diferentes densidades se pueden transformar en grupos con densidades similares y luego podemos ejecutar DBSCAN directamente en los datos normalizados. Este método requiere que el usuario establezca el rango de vecindad para calcular la relación de densidad. La siguiente figura es una comparación de la distribución de datos antes y después de la normalización.
La agrupación basada en densidad es un método de agrupación muy intuitivo. Las áreas adyacentes de alta densidad forman agrupaciones a través de la práctica. Este método puede encontrar grupos de varios tamaños y formas y tiene ciertas propiedades antirruido. En aplicaciones cotidianas, la estimación de la densidad se puede acelerar mediante diferentes métodos de indexación o métodos basados en cuadrículas, aumentando así la velocidad de agrupación.
La agrupación basada en densidad también se puede utilizar para transmisión y datos distribuidos; consulte (Aggarwal 2013) para aplicaciones en otras direcciones.
DP: ?/matlabcentral/fileexchange/53922-densityclust
DBSCAN, SNN, OPTICS y Density-ratio: /projects/density-ratio/
Aggarwal , C. C., & Reddy, C. C., & Aggarwal, C. C. & Reddy, C. K. (Eds. (2013). Agrupación de datos: algoritmos y aplicaciones.
Ankerst, M., Breunig, M. M. , Kriegel, H. P., & Sander, J. (1999, junio). Registro ACM Sigmod (Vol. 28, No. 2, págs. 49-60). ACM.
Ertöz, L., Steinbach , M. y Kumar, V. (2003, mayo). Búsqueda de grupos de diferentes tamaños, formas y densidades en datos ruidosos de alta dimensión. En Actas de la Conferencia Internacional SIAM de 2003 sobre Minería de Datos (págs. 47-58).
Ester, M., Kriegel, H. P., Sander, J. y Xu, X. (agosto de 1996) .SIGKDD (Vol. 96, No. 34, pp. 226-231).
Han, J., Pei, J., & Kamber, M. (2011). Minería de datos: conceptos y técnicas .
Rodriguez, A., & Laio, A. (2014).
Zhu, Y., Ting, K. M., & Carman, M. J. (2016). La agrupación encuentra grupos de diferentes densidades. Reconocimiento de patrones", Volumen 60, 2016, Páginas 983-997, ISSN 0031-3203..