Análisis de conglomerados

Grouping a set of objects by similarity

El resultado de un análisis de conglomerados se muestra como la coloración de los cuadrados en tres conglomerados.

El análisis de conglomerados o clustering es la tarea de agrupar un conjunto de objetos de tal manera que los objetos del mismo grupo (llamado cluster ) sean más similares (en algún sentido específico definido por el analista) entre sí que con los de otros grupos (clusters). Es una tarea principal del análisis exploratorio de datos , y una técnica común para el análisis estadístico de datos , utilizada en muchos campos, incluidos el reconocimiento de patrones , el análisis de imágenes , la recuperación de información , la bioinformática , la compresión de datos , los gráficos por computadora y el aprendizaje automático .

El análisis de conglomerados se refiere a una familia de algoritmos y tareas en lugar de un algoritmo específico . Se puede lograr mediante varios algoritmos que difieren significativamente en su comprensión de lo que constituye un conglomerado y cómo encontrarlos de manera eficiente. Las nociones populares de conglomerados incluyen grupos con pequeñas distancias entre los miembros del conglomerado, áreas densas del espacio de datos, intervalos o distribuciones estadísticas particulares . Por lo tanto, la agrupación en clústeres se puede formular como un problema de optimización multiobjetivo . El algoritmo de agrupación en clústeres apropiado y la configuración de parámetros (incluidos parámetros como la función de distancia a utilizar, un umbral de densidad o el número de conglomerados esperados) dependen del conjunto de datos individual y del uso previsto de los resultados. El análisis de clústeres como tal no es una tarea automática, sino un proceso iterativo de descubrimiento de conocimiento u optimización interactiva multiobjetivo que implica prueba y error. A menudo es necesario modificar el preprocesamiento de datos y los parámetros del modelo hasta que el resultado logre las propiedades deseadas.

Además del término clustering , hay una serie de términos con significados similares, incluyendo clasificación automática , taxonomía numérica , botriología (del griego βότρυς ' uva ' ) , análisis tipológico y detección de comunidades . Las diferencias sutiles a menudo están en el uso de los resultados: mientras que en la minería de datos, los grupos resultantes son el tema de interés, en la clasificación automática lo que interesa es el poder discriminativo resultante.

El análisis de conglomerados se originó en la antropología por Driver y Kroeber en 1932 ^[1] y fue introducido en psicología por Joseph Zubin en 1938 ^[2] y Robert Tryon en 1939 ^[3] y fue utilizado por Cattell a partir de 1943 ^[4] para la clasificación de la teoría de rasgos en psicología de la personalidad .

Definición

El concepto de "agrupamiento" no se puede definir con precisión, lo que constituye una de las razones por las que existen tantos algoritmos de agrupamiento. ^[5] Existe un denominador común: un grupo de objetos de datos. Sin embargo, distintos investigadores emplean distintos modelos de agrupamiento y, para cada uno de ellos, se pueden dar distintos algoritmos. El concepto de agrupamiento, tal como se encuentra en distintos algoritmos, varía significativamente en sus propiedades. Comprender estos "modelos de agrupamiento" es fundamental para comprender las diferencias entre los distintos algoritmos. Entre los modelos de agrupamiento típicos se incluyen:

• Modelos de conectividad : por ejemplo,la agrupación jerárquicacrea modelos basados ​​en la conectividad a distancia.
• Modelos de centroide : por ejemplo, elalgoritmo k-meansrepresenta cada grupo mediante un único vector de media.
• Modelos de distribución : los clústeres se modelan utilizando distribuciones estadísticas, comolas distribuciones normales multivariadasutilizadas por elalgoritmo de maximización de expectativas.
• Modelos de densidad : por ejemplo,DBSCANyOPTICSdefinen los clústeres como regiones densas conectadas en el espacio de datos.
• Modelos de subespacios : enel biclustering(también conocido como co-clustering o clustering de dos modos), los clusters se modelan con miembros del cluster y atributos relevantes.
• Modelos de grupo : algunos algoritmos no proporcionan un modelo refinado para sus resultados y solo proporcionan la información de agrupación.
• Modelos basados ​​en grafos : unacamarilla, es decir, un subconjunto de nodos en ungrafode modo que cada dos nodos en el subconjunto estén conectados por una arista, puede considerarse como una forma prototípica de clúster. Las relajaciones del requisito de conectividad completa (puede faltar una fracción de las aristas) se conocen como cuasi-camarillas, como en elalgoritmo de agrupamiento HCS.
• Modelos de grafos con signo : cada camino en un grafo con signo tiene un signo a partir del producto de los signos en las aristas. Bajo los supuestos de la teoría del equilibrio , las aristas pueden cambiar de signo y dar como resultado un grafo bifurcado. El "axioma de agrupación" más débil (ningún ciclo tiene exactamente una arista negativa) produce resultados con más de dos agrupaciones, o subgrafos con solo aristas positivas. ^[6]
• Modelos neuronales : la red neuronalno supervisada más conocidaes elmapa autoorganizadoy estos modelos generalmente se pueden caracterizar como similares a uno o más de los modelos anteriores, incluyendo modelos de subespacio cuando las redes neuronales implementan una forma deanálisis de componentes principalesoanálisis de componentes independientes.

Una "agrupación" es esencialmente un conjunto de tales grupos, que normalmente contienen todos los objetos del conjunto de datos. Además, puede especificar la relación de los grupos entre sí, por ejemplo, una jerarquía de grupos integrados entre sí. Las agrupaciones se pueden distinguir, a grandes rasgos, de la siguiente manera:

• Agrupamiento duro : cada objeto pertenece a un clúster o no
• Agrupamiento suave (también:Agrupamiento difuso ): cada objeto pertenece a cada grupo en un cierto grado (por ejemplo, una probabilidad de pertenecer al grupo)

También son posibles distinciones más finas, por ejemplo:

• Agrupamiento por partición estricta : cada objeto pertenece exactamente a un clúster
• Agrupamiento de particionamiento estricto con valores atípicos : los objetos también pueden no pertenecer a ningún grupo; en cuyo caso se consideranvalores atípicos.
• Agrupamiento superpuesto (también:agrupamiento alternativo,agrupamiento de múltiples vistas): los objetos pueden pertenecer a más de un clúster; generalmente implica clústeres duros
• Agrupamiento jerárquico : los objetos que pertenecen a un clúster secundario también pertenecen al clúster principal
• Agrupamiento de subespacios : durante un agrupamiento superpuesto, dentro de un subespacio definido de forma única, no se espera que los agrupamientos se superpongan.

Algoritmos

Como se mencionó anteriormente, los algoritmos de agrupamiento se pueden clasificar en función de su modelo de agrupamiento. La siguiente descripción general solo enumerará los ejemplos más destacados de algoritmos de agrupamiento, ya que es posible que haya más de 100 algoritmos de agrupamiento publicados. No todos proporcionan modelos para sus agrupamientos y, por lo tanto, no se pueden clasificar fácilmente. Se puede encontrar una descripción general de los algoritmos explicados en Wikipedia en la lista de algoritmos estadísticos .

No existe un algoritmo de agrupamiento objetivamente "correcto", pero como se ha señalado, "la agrupación depende del observador". ^[5] El algoritmo de agrupamiento más adecuado para un problema particular a menudo debe elegirse experimentalmente, a menos que exista una razón matemática para preferir un modelo de agrupamiento sobre otro. Un algoritmo diseñado para un tipo de modelo generalmente fallará en un conjunto de datos que contenga un tipo de modelo radicalmente diferente. ^[5] Por ejemplo, k-means no puede encontrar agrupamientos no convexos. ^[5] La mayoría de los métodos de agrupamiento tradicionales suponen que los agrupamientos presentan una forma esférica, elíptica o convexa. ^[7]

Agrupamiento basado en conectividad (agrupamiento jerárquico)

El agrupamiento basado en la conectividad, también conocido como agrupamiento jerárquico , se basa en la idea central de que los objetos están más relacionados con los objetos cercanos que con los objetos más alejados. Estos algoritmos conectan "objetos" para formar "agrupamientos" en función de su distancia. Un agrupamiento se puede describir en gran medida por la distancia máxima necesaria para conectar partes del agrupamiento. A diferentes distancias, se formarán diferentes agrupamientos, que se pueden representar mediante un dendrograma , lo que explica de dónde proviene el nombre común " agrupamiento jerárquico ": estos algoritmos no proporcionan una única partición del conjunto de datos, sino que proporcionan una extensa jerarquía de agrupamientos que se fusionan entre sí a ciertas distancias. En un dendrograma, el eje y marca la distancia a la que se fusionan los agrupamientos, mientras que los objetos se colocan a lo largo del eje x de modo que los agrupamientos no se mezclen.

La agrupación basada en la conectividad es una familia completa de métodos que difieren en la forma en que se calculan las distancias. Además de la elección habitual de las funciones de distancia , el usuario también debe decidir el criterio de vinculación (ya que una agrupación consta de varios objetos, hay varios candidatos para calcular la distancia) que se va a utilizar. Las opciones más populares se conocen como agrupación de vinculación simple (el mínimo de distancias entre objetos), agrupación de vinculación completa (el máximo de distancias entre objetos) y UPGMA o WPGMA ("Método de agrupación de pares ponderados o no ponderados con media aritmética", también conocido como agrupación de vinculación promedio). Además, la agrupación jerárquica puede ser aglomerativa (comenzando con elementos individuales y agregándolos en agrupaciones) o divisiva (comenzando con el conjunto de datos completo y dividiéndolo en particiones).

Estos métodos no producirán una partición única del conjunto de datos, sino una jerarquía de la cual el usuario aún necesita elegir los clústeres apropiados. No son muy robustos frente a los valores atípicos, que aparecerán como clústeres adicionales o incluso provocarán que otros clústeres se fusionen (conocido como "fenómeno de encadenamiento", en particular con el agrupamiento de enlace único ). En el caso general, la complejidad es para el agrupamiento aglomerativo y para el agrupamiento divisivo , ^[8] lo que los hace demasiado lentos para grandes conjuntos de datos. Para algunos casos especiales, se conocen métodos eficientes óptimos (de complejidad ): SLINK ^[9] para el enlace único y CLINK ^[10] para el agrupamiento de enlace completo. ${\displaystyle {\mathcal {O}}(n^{3})}$ ${\displaystyle {\mathcal {O}}(2^{n-1})}$ ${\displaystyle {\mathcal {O}}(n^{2})}$

• Ejemplos de agrupamiento por enlaces
• 
  Enlace único en datos gaussianos. En 35 grupos, el grupo más grande comienza a fragmentarse en partes más pequeñas, mientras que antes todavía estaba conectado al segundo más grande debido al efecto de enlace único.
• 
  Enlace simple en clústeres basados ​​en densidad. Se extrajeron 20 clústeres, la mayoría de los cuales contienen elementos únicos, ya que el agrupamiento por enlace no tiene una noción de "ruido".

Agrupamiento basado en centroides

En la agrupación basada en centroides, cada grupo está representado por un vector central, que no necesariamente es un miembro del conjunto de datos. Cuando el número de grupos se fija en k , la agrupación de k -medias proporciona una definición formal como un problema de optimización: encontrar los centros de los grupos k y asignar los objetos al centro del grupo más cercano, de modo que se minimicen las distancias al cuadrado desde el grupo.

Se sabe que el problema de optimización en sí es NP-hard y, por lo tanto, el enfoque común es buscar solo soluciones aproximadas. Un método aproximado particularmente conocido es el algoritmo de Lloyd , ^[11] a menudo denominado simplemente " algoritmo k-means " (aunque otro algoritmo introdujo este nombre ). Sin embargo, solo encuentra un óptimo local y comúnmente se ejecuta varias veces con diferentes inicializaciones aleatorias. Las variaciones de k -means a menudo incluyen optimizaciones tales como elegir la mejor de múltiples ejecuciones, pero también restringir los centroides a los miembros del conjunto de datos ( k -medoides ), elegir medianas ( agrupamiento k -medianas ), elegir los centros iniciales de manera menos aleatoria ( k -means++ ) o permitir una asignación de clúster difusa ( c-means difusa ).

La mayoría de los algoritmos de tipo k -means requieren que se especifique de antemano el número de clústeres ( k ), lo que se considera una de las mayores desventajas de estos algoritmos. Además, los algoritmos prefieren clústeres de tamaño aproximadamente similar, ya que siempre asignarán un objeto al centroide más cercano. Esto a menudo conduce a bordes de clústeres cortados incorrectamente (lo que no es sorprendente ya que el algoritmo optimiza los centros de los clústeres, no los bordes de los clústeres).

K-means tiene varias propiedades teóricas interesantes. En primer lugar, divide el espacio de datos en una estructura conocida como diagrama de Voronoi . En segundo lugar, conceptualmente es similar a la clasificación del vecino más próximo y, como tal, es popular en el aprendizaje automático . En tercer lugar, puede considerarse una variación de la agrupación basada en modelos y el algoritmo de Lloyd como una variación del algoritmo de maximización de expectativas para este modelo, que se analiza a continuación.

• Ejemplos de agrupamiento de k -medias
• 
  k -means separa los datos en celdas de Voronoi, lo que supone grupos de igual tamaño (no es adecuado aquí).
• 
  k -means no puede representar clústeres basados ​​en densidad.

Los problemas de agrupamiento basados ​​en centroides, como k -medias y k -medoides, son casos especiales del problema de ubicación de instalaciones métricas no capacitadas , un problema canónico en las comunidades de investigación de operaciones y geometría computacional. En un problema básico de ubicación de instalaciones (del cual existen numerosas variantes que modelan configuraciones más elaboradas), la tarea es encontrar las mejores ubicaciones de almacenes para brindar un servicio óptimo a un conjunto determinado de consumidores. Se pueden considerar los "almacenes" como centroides de agrupamiento y las "ubicaciones de los consumidores" como los datos que se deben agrupar. Esto hace posible aplicar las soluciones algorítmicas bien desarrolladas de la literatura sobre ubicación de instalaciones al problema de agrupamiento basado en centroides que se considera actualmente.

Agrupamiento basado en modelos

El marco de agrupamiento más estrechamente relacionado con las estadísticas es el agrupamiento basado en modelos , que se basa en modelos de distribución . Este enfoque modela los datos como si surgieran de una mezcla de distribuciones de probabilidad. Tiene la ventaja de proporcionar respuestas estadísticas basadas en principios a preguntas como cuántos conglomerados hay, qué método o modelo de agrupamiento utilizar y cómo detectar y tratar los valores atípicos.

Si bien la base teórica de estos métodos es excelente, sufren de sobreajuste a menos que se impongan restricciones a la complejidad del modelo. Un modelo más complejo normalmente podrá explicar mejor los datos, lo que hace que la elección de la complejidad del modelo adecuada sea inherentemente difícil. Los métodos de agrupamiento basados ​​en modelos estándar incluyen modelos más parsimoniosos basados ​​en la descomposición de valores propios de las matrices de covarianza, que proporcionan un equilibrio entre el sobreajuste y la fidelidad a los datos.

Un método destacado se conoce como modelos de mezcla gaussiana (que utilizan el algoritmo de maximización de expectativas ). En este caso, el conjunto de datos suele modelarse con un número fijo (para evitar el sobreajuste) de distribuciones gaussianas que se inicializan aleatoriamente y cuyos parámetros se optimizan iterativamente para ajustarse mejor al conjunto de datos. Esto convergerá a un óptimo local , por lo que varias ejecuciones pueden producir resultados diferentes. Para obtener una agrupación estricta, los objetos suelen asignarse a la distribución gaussiana a la que es más probable que pertenezcan; para las agrupaciones flexibles, esto no es necesario.

La agrupación basada en la distribución produce modelos complejos para los clústeres que pueden capturar la correlación y la dependencia entre atributos. Sin embargo, estos algoritmos suponen una carga adicional para el usuario: para muchos conjuntos de datos reales, puede que no exista un modelo matemático definido de manera concisa (por ejemplo, suponer que las distribuciones gaussianas son una suposición bastante sólida sobre los datos).

• Ejemplos de agrupamiento de modelos de mezcla gaussiana
• 
  En datos distribuidos gaussianamente, EM funciona bien, ya que utiliza gaussianas para modelar clústeres.
• 
  Los clústeres basados ​​en densidad no se pueden modelar utilizando distribuciones gaussianas.

Agrupamiento basado en densidad

En la agrupación basada en la densidad, ^[12] los clústeres se definen como áreas de mayor densidad que el resto del conjunto de datos. Los objetos en áreas dispersas (que son necesarias para separar los clústeres) suelen considerarse puntos de ruido y de frontera.

El método de agrupamiento basado en densidad más popular ^{[13] es} DBSCAN . ^[14] A diferencia de muchos métodos más nuevos, presenta un modelo de agrupamiento bien definido llamado "alcance por densidad". Similar al agrupamiento basado en enlaces, se basa en conectar puntos dentro de ciertos umbrales de distancia. Sin embargo, solo conecta puntos que satisfacen un criterio de densidad, en la variante original definido como un número mínimo de otros objetos dentro de este radio. Un agrupamiento consta de todos los objetos conectados por densidad (que pueden formar un agrupamiento de una forma arbitraria, a diferencia de muchos otros métodos) más todos los objetos que están dentro del rango de estos objetos. Otra propiedad interesante de DBSCAN es que su complejidad es bastante baja (requiere un número lineal de consultas de rango en la base de datos) y que descubrirá esencialmente los mismos resultados (es determinista para los puntos centrales y de ruido, pero no para los puntos de borde) en cada ejecución, por lo tanto, no hay necesidad de ejecutarlo varias veces. OPTICS ^[15] es una generalización de DBSCAN que elimina la necesidad de elegir un valor apropiado para el parámetro de rango y produce un resultado jerárquico relacionado con el del agrupamiento por ligamiento . DeLi-Clu, ^[16] Density-Link-Clustering combina ideas del agrupamiento por ligamiento único y OPTICS, eliminando el parámetro por completo y ofreciendo mejoras de rendimiento sobre OPTICS mediante el uso de un índice de árbol R. ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$

La principal desventaja de DBSCAN y OPTICS es que esperan algún tipo de caída de densidad para detectar los límites de los clústeres. En conjuntos de datos con, por ejemplo, distribuciones gaussianas superpuestas (un caso de uso común en datos artificiales), los límites de los clústeres producidos por estos algoritmos a menudo parecerán arbitrarios, porque la densidad de los clústeres disminuye continuamente. En un conjunto de datos que consiste en mezclas de gaussianas, estos algoritmos casi siempre son superados por métodos como el agrupamiento EM que pueden modelar con precisión este tipo de datos.

El cambio de media es un método de agrupamiento en el que cada objeto se mueve al área más densa en su vecindad, según la estimación de densidad de kernel . Finalmente, los objetos convergen a máximos locales de densidad. De manera similar al agrupamiento de k-medias, estos "atractores de densidad" pueden servir como representantes del conjunto de datos, pero el cambio de media puede detectar agrupaciones de forma arbitraria de manera similar a DBSCAN. Debido al costoso procedimiento iterativo y la estimación de densidad, el cambio de media suele ser más lento que DBSCAN o k-medias. Además de eso, la aplicabilidad del algoritmo de cambio de media a datos multidimensionales se ve obstaculizada por el comportamiento no uniforme de la estimación de densidad de kernel, que resulta en una fragmentación excesiva de las colas de los agrupamientos. ^[16]

• Ejemplos de agrupamiento basado en densidad
• 
  Agrupamiento basado en densidad con DBSCAN
• 
  DBSCAN asume grupos de densidad similar y puede tener problemas para separar grupos cercanos.
• 
  OPTICS es una variante de DBSCAN que mejora el manejo de clústeres de diferentes densidades.

Agrupamiento basado en cuadrícula

La técnica basada en cuadrícula se utiliza para un conjunto de datos multidimensionales . ^[17] En esta técnica, creamos una estructura de cuadrícula y la comparación se realiza en cuadrículas (también conocidas como celdas). La técnica basada en cuadrícula es rápida y tiene una baja complejidad computacional. Hay dos tipos de métodos de agrupamiento basados ​​en cuadrícula: STING y CLIQUE. Los pasos involucrados en el algoritmo de agrupamiento basado en cuadrícula son:

1. Dividir el espacio de datos en un número finito de celdas.
2. Seleccione aleatoriamente una celda 'c', donde c no debe ser atravesada de antemano.
3. Calcular la densidad de 'c'
4. Si la densidad de 'c' es mayor que la densidad umbral
   1. Marcar la celda 'c' como un nuevo clúster
   2. Calcular la densidad de todos los vecinos de 'c'
   3. Si la densidad de una celda vecina es mayor que la densidad umbral, agregue la celda al grupo y repita los pasos 4.2 y 4.3 hasta que no haya ninguna celda vecina con una densidad mayor que la densidad umbral.
5. Repita los pasos 2, 3 y 4 hasta que todas las celdas estén recorridas.
6. Detener.

Acontecimientos recientes

En los últimos años, se ha dedicado un esfuerzo considerable a mejorar el rendimiento de los algoritmos existentes. ^{[18] [19]} Entre ellos se encuentran CLARANS , ^[20] y BIRCH . ^[21] Con la reciente necesidad de procesar conjuntos de datos cada vez más grandes (también conocidos como big data ), ha aumentado la voluntad de intercambiar el significado semántico de los clústeres generados por el rendimiento. Esto llevó al desarrollo de métodos de preagrupamiento como el agrupamiento de dosel , que puede procesar grandes conjuntos de datos de manera eficiente, pero los "clústeres" resultantes son simplemente una prepartición aproximada del conjunto de datos para luego analizar las particiones con métodos existentes más lentos como el agrupamiento de k-medias .

En el caso de los datos de alta dimensión , muchos de los métodos existentes fallan debido a la maldición de la dimensionalidad , que hace que determinadas funciones de distancia resulten problemáticas en espacios de alta dimensión. Esto dio lugar a nuevos algoritmos de agrupamiento para datos de alta dimensión que se centran en el agrupamiento de subespacios (en los que solo se utilizan algunos atributos y los modelos de agrupamiento incluyen los atributos relevantes para el agrupamiento) y el agrupamiento por correlación , que también busca agrupamientos de subespacios rotados arbitrariamente ("correlacionados") que se puedan modelar proporcionando una correlación de sus atributos. ^[22] Algunos ejemplos de estos algoritmos de agrupamiento son CLIQUE ^[23] y SUBCLU . ^[24]

Las ideas de los métodos de agrupamiento basados ​​en densidad (en particular la familia de algoritmos DBSCAN / OPTICS ) se han adaptado al agrupamiento de subespacios (HiSC, ^[25] agrupamiento de subespacios jerárquicos y DiSH ^[26] ) y al agrupamiento de correlación (HiCO, ^[27] agrupamiento de correlación jerárquica, 4C ^[28] utilizando "conectividad de correlación" y ERiC ^[29] explorando agrupamientos de correlación jerárquicos basados ​​en densidad).

Se han propuesto varios sistemas de agrupamiento diferentes basados ​​en información mutua . Uno es la variación de la métrica de información de Marina Meilă; ^[30] otro proporciona agrupamiento jerárquico. ^[31] Utilizando algoritmos genéticos, se puede optimizar una amplia gama de diferentes funciones de ajuste, incluida la información mutua. ^[32] Además, la propagación de creencias , un desarrollo reciente en la ciencia informática y la física estadística , ha llevado a la creación de nuevos tipos de algoritmos de agrupamiento. ^[33]

Evaluación y valoración

La evaluación (o "validación") de los resultados de la agrupación es tan difícil como la agrupación misma. ^[34] Los enfoques populares incluyen la evaluación " interna ", donde la agrupación se resume en una única puntuación de calidad, la evaluación " externa ", donde la agrupación se compara con una clasificación de "verdad fundamental" existente, la evaluación " manual " por parte de un experto humano y la evaluación " indirecta " mediante la evaluación de la utilidad de la agrupación en su aplicación prevista. ^[35]

Las medidas de evaluación interna tienen el problema de que representan funciones que en sí mismas pueden considerarse como un objetivo de agrupamiento. Por ejemplo, se podría agrupar el conjunto de datos por el coeficiente de Silhouette; excepto que no se conoce ningún algoritmo eficiente para esto. Al utilizar una medida interna de este tipo para la evaluación, se compara más bien la similitud de los problemas de optimización ^[35] y no necesariamente la utilidad del agrupamiento.

La evaluación externa tiene problemas similares: si tenemos esas etiquetas de "verdad fundamental", entonces no necesitaríamos agrupar; y en aplicaciones prácticas normalmente no tenemos esas etiquetas. Por otra parte, las etiquetas sólo reflejan una posible partición del conjunto de datos, lo que no implica que no exista una agrupación diferente, y tal vez incluso mejor.

Por lo tanto, ninguno de estos enfoques puede juzgar en última instancia la calidad real de un agrupamiento, sino que esto requiere una evaluación humana, ^[35] que es altamente subjetiva. Sin embargo, estas estadísticas pueden ser bastante informativas para identificar agrupamientos deficientes, ^[36] pero no se debe descartar la evaluación humana subjetiva. ^[36]

Evaluación interna

Cuando se evalúa un resultado de agrupamiento en función de los datos que se agruparon en sí, esto se denomina evaluación interna. Estos métodos suelen asignar la mejor puntuación al algoritmo que produce agrupamientos con alta similitud dentro de un agrupamiento y baja similitud entre agrupamientos. Una desventaja de utilizar criterios internos en la evaluación de agrupamientos es que las puntuaciones altas en una medida interna no necesariamente dan como resultado aplicaciones de recuperación de información efectivas. ^[37] Además, esta evaluación está sesgada hacia los algoritmos que utilizan el mismo modelo de agrupamiento. Por ejemplo, el agrupamiento k-means optimiza naturalmente las distancias de los objetos, y un criterio interno basado en la distancia probablemente sobrestimará el agrupamiento resultante.

Por lo tanto, las medidas de evaluación interna son las más adecuadas para obtener una idea de las situaciones en las que un algoritmo funciona mejor que otro, pero esto no implica que un algoritmo produzca resultados más válidos que otro. ^[5] La validez medida por dicho índice depende de la afirmación de que este tipo de estructura existe en el conjunto de datos. Un algoritmo diseñado para algún tipo de modelos no tiene ninguna posibilidad si el conjunto de datos contiene un conjunto radicalmente diferente de modelos, o si la evaluación mide un criterio radicalmente diferente. ^[5] Por ejemplo, la agrupación de k-medias solo puede encontrar agrupaciones convexas, y muchos índices de evaluación suponen agrupaciones convexas. En un conjunto de datos con agrupaciones no convexas, ni el uso de k -medias, ni de un criterio de evaluación que suponga convexidad, es sólido.

Existen más de una docena de medidas de evaluación interna, generalmente basadas en la intuición de que los elementos del mismo grupo deberían ser más similares que los elementos de grupos diferentes. ^{[38] : 115–121} Por ejemplo, se pueden utilizar los siguientes métodos para evaluar la calidad de los algoritmos de agrupamiento basados ​​en criterios internos:

• Índice de Davies-Bouldin

El índice de Davies-Bouldin se puede calcular mediante la siguiente fórmula:

${\displaystyle DB={\frac {1}{n}}\sum _{i=1}^{n}\max _{j\neq i}\left({\frac {\sigma _{i}+\sigma _{j}}{d(c_{i},c_{j})}}\right)}$

donde n es el número de clústeres, es el centroide del clúster , es la distancia promedio de todos los elementos del clúster al centroide , y es la distancia entre los centroides y . Dado que los algoritmos que producen clústeres con distancias intra-clúster bajas (alta similitud intra-clúster) y distancias inter-clúster altas (baja similitud inter-clúster) tendrán un índice de Davies-Bouldin bajo, el algoritmo de agrupamiento que produce una colección de clústeres con el índice de Davies-Bouldin más pequeño se considera el mejor algoritmo basado en este criterio. ${\displaystyle c_{i}}$ ${\displaystyle i}$ ${\displaystyle \sigma _{i}}$ ${\displaystyle i}$ ${\displaystyle c_{i}}$ ${\displaystyle d(c_{i},c_{j})}$ ${\displaystyle c_{i}}$ ${\displaystyle c_{j}}$

• Índice de Dunn

El índice de Dunn tiene como objetivo identificar cúmulos densos y bien separados. Se define como la relación entre la distancia mínima entre cúmulos y la distancia máxima dentro de los cúmulos. Para cada partición de cúmulos, el índice de Dunn se puede calcular mediante la siguiente fórmula: ^[39]

${\displaystyle D={\frac {\min _{1\leq i<j\leq n}d(i,j)}{\max _{1\leq k\leq n}d^{\prime }(k)}}\,,}$

donde d ( i , j ) representa la distancia entre los conglomerados i y j , y d '( k ) mide la distancia intraconglomerado del conglomerado k . La distancia interconglomerado d ( i , j ) entre dos conglomerados puede ser cualquier número de medidas de distancia, como la distancia entre los centroides de los conglomerados. De manera similar, la distancia intraconglomerado d '( k ) puede medirse de diversas maneras, como la distancia máxima entre cualquier par de elementos en el conglomerado  k . Dado que el criterio interno busca conglomerados con alta similitud intraconglomerado y baja similitud interconglomerado, son más deseables los algoritmos que producen conglomerados con alto índice de Dunn.

• Coeficiente de silueta

El coeficiente de silueta contrasta la distancia promedio a los elementos del mismo grupo con la distancia promedio a los elementos de otros grupos. Los objetos con un valor de silueta alto se consideran bien agrupados, los objetos con un valor bajo pueden ser valores atípicos. Este índice funciona bien con el agrupamiento de k -medias y también se utiliza para determinar el número óptimo de grupos. ^[40]

Evaluación externa

En la evaluación externa, los resultados de la agrupación se evalúan en función de datos que no se utilizaron para la agrupación, como etiquetas de clase conocidas y puntos de referencia externos. Dichos puntos de referencia consisten en un conjunto de elementos preclasificados, y estos conjuntos a menudo son creados por humanos (expertos). Por lo tanto, los conjuntos de puntos de referencia pueden considerarse un estándar de oro para la evaluación. ^[34] Estos tipos de métodos de evaluación miden qué tan cerca está la agrupación de las clases de referencia predeterminadas. Sin embargo, recientemente se ha discutido si esto es adecuado para datos reales, o solo en conjuntos de datos sintéticos con una verdad fundamental fáctica, ya que las clases pueden contener una estructura interna, los atributos presentes pueden no permitir la separación de los grupos o las clases pueden contener anomalías . ^[41] Además, desde el punto de vista del descubrimiento de conocimiento , la reproducción del conocimiento conocido puede no ser necesariamente el resultado deseado. ^[41] En el escenario especial de agrupación restringida , donde la metainformación (como las etiquetas de clase) ya se utiliza en el proceso de agrupación, la retención de información para fines de evaluación no es trivial. ^[42]

Varias medidas se adaptan a partir de variantes utilizadas para evaluar tareas de clasificación. En lugar de contar la cantidad de veces que una clase se asignó correctamente a un único punto de datos (conocidos como verdaderos positivos ), estas métricas de conteo de pares evalúan si se predice que cada par de puntos de datos que realmente está en el mismo grupo estará en el mismo grupo. ^[34]

Al igual que ocurre con la evaluación interna, existen varias medidas de evaluación externa, ^{[38] : 125–129} por ejemplo:

• Pureza : La pureza es una medida del grado en que los clústeres contienen una sola clase. ^[37] Su cálculo puede considerarse de la siguiente manera: para cada clúster, cuente el número de puntos de datos de la clase más común en dicho clúster. Ahora tome la suma de todos los clústeres y divídala por el número total de puntos de datos. Formalmente, dado un conjunto de clústeres y un conjunto de clases , ambos dividiendo los puntos de datos, la pureza puede definirse como: ${\displaystyle M}$ ${\displaystyle D}$ ${\displaystyle N}$

${\displaystyle {\frac {1}{N}}\sum _{m\in M}\max _{d\in D}{|m\cap d|}}$

Esta medida no penaliza la existencia de muchos clústeres, y una mayor cantidad de clústeres facilitará la producción de una pureza alta. Siempre es posible obtener una puntuación de pureza de 1 si se coloca cada punto de datos en su propio clúster. Además, la pureza no funciona bien con datos desequilibrados, en los que incluso los algoritmos de agrupamiento con un rendimiento deficiente darán un valor de pureza alto. Por ejemplo, si un conjunto de datos de tamaño 1000 consta de dos clases, una que contiene 999 puntos y la otra que contiene 1 punto, entonces cada partición posible tendrá una pureza de al menos el 99,9 %.

• Índice Rand ^[43]

El índice Rand calcula la similitud de los clústeres (obtenidos mediante el algoritmo de agrupamiento) con las clasificaciones de referencia. Se puede calcular utilizando la siguiente fórmula:

${\displaystyle RI={\frac {TP+TN}{TP+FP+FN+TN}}}$

donde es el número de verdaderos positivos, es el número de verdaderos negativos , es el número de falsos positivos y es el número de falsos negativos . Las instancias que se cuentan aquí son el número de asignaciones por pares correctas . Es decir, es el número de pares de puntos que se agrupan en la partición predicha y en la partición de verdad fundamental, es el número de pares de puntos que se agrupan en la partición predicha pero no en la partición de verdad fundamental, etc. Si el conjunto de datos es de tamaño N, entonces . ${\displaystyle TP}$ ${\displaystyle TN}$ ${\displaystyle FP}$ ${\displaystyle FN}$ ${\displaystyle TP}$ ${\displaystyle FP}$ ${\displaystyle TP+TN+FP+FN={\binom {N}{2}}}$

Un problema con el índice Rand es que los falsos positivos y los falsos negativos tienen la misma ponderación. Esta puede ser una característica indeseable para algunas aplicaciones de agrupamiento. La medida F aborda esta inquietud, ^{[ cita requerida ] al igual que el} índice Rand ajustado con corrección de probabilidad .

• Medida F

La medida F se puede utilizar para equilibrar la contribución de los falsos negativos ponderando la recuperación a través de un parámetro . Definamos la precisión y la recuperación (ambas medidas de evaluación externa en sí mismas) de la siguiente manera: ${\displaystyle \beta \geq 0}$

${\displaystyle P={\frac {TP}{TP+FP}}}$

${\displaystyle R={\frac {TP}{TP+FN}}}$

donde es la tasa de precisión y es la tasa de recuperación . Podemos calcular la medida F utilizando la siguiente fórmula: ^[37] ${\displaystyle P}$ ${\displaystyle R}$

${\displaystyle F_{\beta }={\frac {(\beta ^{2}+1)\cdot P\cdot R}{\beta ^{2}\cdot P+R}}}$

Cuando , . En otras palabras, la recuperación no tiene impacto en la medida F cuando , y al aumentar se asigna una cantidad creciente de peso a la recuperación en la medida F final. ${\displaystyle \beta =0}$ ${\displaystyle F_{0}=P}$ ${\displaystyle \beta =0}$ ${\displaystyle \beta }$

Tampoco se tiene en cuenta y puede variar desde 0 hacia arriba sin límite. ${\displaystyle TN}$

• Índice de Jaccard

El índice de Jaccard se utiliza para cuantificar la similitud entre dos conjuntos de datos. El índice de Jaccard toma un valor entre 0 y 1. Un índice de 1 significa que los dos conjuntos de datos son idénticos y un índice de 0 indica que los conjuntos de datos no tienen elementos comunes. El índice de Jaccard se define mediante la siguiente fórmula:

${\displaystyle J(A,B)={\frac {|A\cap B|}{|A\cup B|}}={\frac {TP}{TP+FP+FN}}}$

Este es simplemente el número de elementos únicos comunes a ambos conjuntos dividido por el número total de elementos únicos en ambos conjuntos.

Tenga en cuenta que no se tiene en cuenta. ${\displaystyle TN}$

• Índice de dados

La medida simétrica de Dice duplica el peso mientras sigue ignorando : ${\displaystyle TP}$ ${\displaystyle TN}$

${\displaystyle DSC={\frac {2TP}{2TP+FP+FN}}}$

• Índice de Fowlkes-Mallows ^[44]

El índice de Fowlkes-Mallows calcula la similitud entre los clústeres obtenidos mediante el algoritmo de agrupamiento y las clasificaciones de referencia. Cuanto mayor sea el valor del índice de Fowlkes-Mallows, más similares serán los clústeres y las clasificaciones de referencia. Se puede calcular utilizando la siguiente fórmula:

${\displaystyle FM={\sqrt {{\frac {TP}{TP+FP}}\cdot {\frac {TP}{TP+FN}}}}}$

donde es el número de verdaderos positivos , es el número de falsos positivos y es el número de falsos negativos . El índice es la media geométrica de la precisión y la recuperación y , por lo tanto, también se conoce como la medida G , mientras que la medida F es su media armónica. ^{[45] [46]} Además, la precisión y la recuperación también se conocen como índices de Wallace y . ^[47] Las versiones normalizadas al azar de la recuperación, la precisión y la medida G corresponden a Informedness , Markedness y Matthews Correlation y se relacionan fuertemente con Kappa . ^[48] ${\displaystyle TP}$ ${\displaystyle FP}$ ${\displaystyle FN}$ ${\displaystyle FM}$ ${\displaystyle P}$ ${\displaystyle R}$ ${\displaystyle B^{I}}$ ${\displaystyle B^{II}}$

• El índice Chi ^[49] es un índice de validación externa que mide los resultados de la agrupación mediante la aplicación de la estadística chi-cuadrado . Este índice valora positivamente el hecho de que las etiquetas sean lo más dispersas posible entre los clústeres, es decir, que cada clúster tenga la menor cantidad posible de etiquetas diferentes. Cuanto mayor sea el valor del índice Chi, mayor será la relación entre los clústeres resultantes y la etiqueta utilizada.
• La información mutua es una medida teórica de la información que mide cuánta información se comparte entre una agrupación y una clasificación basada en la verdad fundamental, y que puede detectar una similitud no lineal entre dos agrupaciones. La información mutua normalizada es una familia de variantes de esta corregida por azar que tiene un sesgo reducido para la variación de los números de agrupaciones. ^[34]
• Matriz de confusión

Se puede utilizar una matriz de confusión para visualizar rápidamente los resultados de un algoritmo de clasificación (o agrupamiento). Muestra en qué medida un grupo se diferencia del grupo estándar.

Tendencia a la agrupación

Medir la tendencia de los clústeres es medir en qué medida existen clústeres en los datos que se van a agrupar, y puede realizarse como prueba inicial antes de intentar la agrupación. Una forma de hacerlo es comparar los datos con datos aleatorios. En promedio, los datos aleatorios no deberían tener clústeres.

• Estadísticas de Hopkins

Existen múltiples formulaciones de la estadística de Hopkins . ^[50] Una típica es la siguiente. ^[51] Sea el conjunto de puntos de datos en el espacio dimensional. Considere una muestra aleatoria (sin reemplazo) de puntos de datos con miembros . Genere también un conjunto de puntos de datos distribuidos aleatoriamente de manera uniforme. Ahora defina dos medidas de distancia, que sean la distancia de desde su vecino más cercano en X y la distancia de desde su vecino más cercano en X. Luego definimos la estadística de Hopkins como: ${\displaystyle X}$ ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle m\ll n}$ ${\displaystyle x_{i}}$ ${\displaystyle Y}$ ${\displaystyle m}$ ${\displaystyle u_{i}}$ ${\displaystyle y_{i}\in Y}$ ${\displaystyle w_{i}}$ ${\displaystyle x_{i}\in X}$

${\displaystyle H={\frac {\sum _{i=1}^{m}{u_{i}^{d}}}{\sum _{i=1}^{m}{u_{i}^{d}}+\sum _{i=1}^{m}{w_{i}^{d}}}}\,,}$

Con esta definición, los datos aleatorios uniformes deberían tender a tener valores cercanos a 0,5, y los datos agrupados deberían tender a tener valores más cercanos a 1.

Sin embargo, los datos que contienen sólo una gaussiana también tendrán una puntuación cercana a 1, ya que esta estadística mide la desviación de una distribución uniforme , no la multimodalidad , lo que hace que esta estadística sea en gran medida inútil en la aplicación (ya que los datos reales nunca son remotamente uniformes).

Aplicaciones

Biología, biología computacional y bioinformática

Ecología vegetal y animal

El análisis de conglomerados se utiliza para describir y hacer comparaciones espaciales y temporales de comunidades (conjuntos) de organismos en ambientes heterogéneos. También se utiliza en sistemática vegetal para generar filogenias artificiales o conglomerados de organismos (individuos) a nivel de especie, género o superior que comparten una serie de atributos.

Transcriptómica

La agrupación se utiliza para crear grupos de genes con patrones de expresión relacionados (también conocidos como genes coexpresados) como en el algoritmo de agrupación HCS . ^{[52] [53]} A menudo, estos grupos contienen proteínas funcionalmente relacionadas, como enzimas para una vía específica , o genes que están co-regulados. Los experimentos de alto rendimiento que utilizan etiquetas de secuencia expresada (EST) o microarreglos de ADN pueden ser una herramienta poderosa para la anotación del genoma  , un aspecto general de la genómica .

Análisis de secuencias

La agrupación de secuencias se utiliza para agrupar secuencias homólogas en familias de genes . ^[54] Este es un concepto muy importante en bioinformática y en biología evolutiva en general. Véase evolución por duplicación de genes .

Plataformas de genotipado de alto rendimiento

Los algoritmos de agrupamiento se utilizan para asignar genotipos automáticamente. ^[55]

Agrupamiento genético humano

La similitud de datos genéticos se utiliza en la agrupación para inferir estructuras de población.

Medicamento

Imágenes médicas

En las exploraciones PET , el análisis de conglomerados se puede utilizar para diferenciar entre diferentes tipos de tejido en una imagen tridimensional para muchos propósitos diferentes. ^[56]

Análisis de la actividad antimicrobiana

El análisis de conglomerados se puede utilizar para analizar patrones de resistencia a los antibióticos, para clasificar los compuestos antimicrobianos según su mecanismo de acción y para clasificar los antibióticos según su actividad antibacteriana.

Segmentación IMRT

La agrupación se puede utilizar para dividir un mapa de fluencia en regiones distintas para su conversión en campos entregables en radioterapia basada en MLC.

Negocios y marketing

Investigación de mercado

El análisis de conglomerados se utiliza ampliamente en la investigación de mercados cuando se trabaja con datos multivariados de encuestas y paneles de prueba. Los investigadores de mercado utilizan el análisis de conglomerados para dividir la población general de consumidores en segmentos de mercado y para comprender mejor las relaciones entre diferentes grupos de consumidores/ clientes potenciales , y para su uso en la segmentación de mercados , el posicionamiento de productos , el desarrollo de nuevos productos y la selección de mercados de prueba.

Agrupación de artículos de compra

La agrupación se puede utilizar para agrupar todos los artículos de compra disponibles en la web en un conjunto de productos únicos. Por ejemplo, todos los artículos de eBay se pueden agrupar en productos únicos (eBay no tiene el concepto de SKU ).

World Wide Web

Análisis de redes sociales

En el estudio de las redes sociales , la agrupación se puede utilizar para reconocer comunidades dentro de grandes grupos de personas.

Agrupación de resultados de búsqueda

En el proceso de agrupamiento inteligente de archivos y sitios web, la agrupación se puede utilizar para crear un conjunto de resultados de búsqueda más relevante en comparación con los motores de búsqueda normales como Google ^{[ cita requerida ]} . Actualmente, existen varias herramientas de agrupamiento basadas en la web, como Clusty . También se puede utilizar para devolver un conjunto de resultados más completo en los casos en que un término de búsqueda podría referirse a cosas muy diferentes. Cada uso distinto del término corresponde a un grupo único de resultados, lo que permite que un algoritmo de clasificación devuelva resultados completos al elegir el resultado principal de cada grupo. ^[57]

Optimización de mapas deslizantes

El mapa de fotos de Flickr y otros sitios de mapas utilizan la agrupación para reducir la cantidad de marcadores en un mapa. ^{[ cita requerida ]} Esto lo hace más rápido y reduce la cantidad de desorden visual.

Ciencias de la Computación

Evolución del software

La agrupación en clústeres es útil en la evolución del software, ya que ayuda a reducir las propiedades heredadas del código al reformar la funcionalidad que se ha dispersado. Es una forma de reestructuración y, por lo tanto, una forma de mantenimiento preventivo directo.

Segmentación de imágenes

La agrupación se puede utilizar para dividir una imagen digital en regiones distintas para la detección de bordes o el reconocimiento de objetos . ^[58]

Algoritmos evolutivos

La agrupación se puede utilizar para identificar diferentes nichos dentro de la población de un algoritmo evolutivo, de modo que la oportunidad reproductiva pueda distribuirse de manera más uniforme entre las especies o subespecies en evolución.

Sistemas de recomendación

Los sistemas de recomendación están diseñados para recomendar nuevos artículos en función de los gustos de los usuarios. A veces, utilizan algoritmos de agrupamiento para predecir las preferencias de un usuario en función de las preferencias de otros usuarios del grupo de usuarios.

Métodos de Monte Carlo de cadenas de Markov

La agrupación se utiliza a menudo para localizar y caracterizar los extremos en la distribución objetivo.

Detección de anomalías

Las anomalías o valores atípicos normalmente se definen (ya sea explícita o implícitamente) con respecto a la estructura de agrupamiento de los datos.

Procesamiento del lenguaje natural

La agrupación se puede utilizar para resolver la ambigüedad léxica . ^[57]

DevOps

La agrupación en clústeres se ha utilizado para analizar la eficacia de los equipos DevOps. ^[59]

Ciencia social

Análisis de secuencias en las ciencias sociales

El análisis de conglomerados se utiliza para identificar patrones de trayectorias de vida familiar, carreras profesionales y uso del tiempo diario o semanal, por ejemplo.

Análisis del delito

El análisis de conglomerados puede utilizarse para identificar áreas en las que hay una mayor incidencia de determinados tipos de delitos. Al identificar estas áreas específicas o "puntos calientes" en los que se ha producido un delito similar durante un período de tiempo, es posible gestionar los recursos de las fuerzas del orden de forma más eficaz.

Minería de datos educativos

El análisis de conglomerados se utiliza, por ejemplo, para identificar grupos de escuelas o estudiantes con propiedades similares.

Tipologías

A partir de datos de encuestas, proyectos como los realizados por el Pew Research Center utilizan el análisis de conglomerados para discernir tipologías de opiniones, hábitos y datos demográficos que pueden ser útiles en política y marketing.

Otros

Robótica de campo

Los algoritmos de agrupamiento se utilizan para el conocimiento situacional robótico para rastrear objetos y detectar valores atípicos en los datos de los sensores. ^[60]

Química matemática

Para encontrar similitud estructural, etc., por ejemplo, se agruparon 3000 compuestos químicos en el espacio de 90 índices topológicos . ^[61]

Climatología

Para encontrar regímenes climáticos o patrones atmosféricos preferidos de presión a nivel del mar. ^[62]

Finanzas

El análisis de conglomerados se ha utilizado para agrupar acciones en sectores. ^[63]

Geología del petróleo

El análisis de conglomerados se utiliza para reconstruir datos faltantes del núcleo del fondo del pozo o curvas de registro faltantes con el fin de evaluar las propiedades del yacimiento.

Geoquímica

La agrupación de propiedades químicas en diferentes ubicaciones de la muestra.

Véase también

Tipos especializados de análisis de conglomerados

• Algoritmos de agrupamiento automático
• Agrupamiento equilibrado
• Agrupamiento de datos de alta dimensión
• Agrupamiento conceptual
• Agrupamiento por consenso
• Agrupamiento restringido
• Detección de la comunidad
• Agrupamiento de flujos de datos
• Agrupamiento de HCS
• Agrupamiento de secuencias
• Agrupamiento espectral

Técnicas utilizadas en el análisis de conglomerados

• Red neuronal artificial (RNA)
• Búsqueda de vecino más cercano
• Análisis de los componentes del barrio
• Análisis de clases latentes
• Propagación por afinidad

Proyección y preprocesamiento de datos

• Reducción de dimensión
• Análisis de componentes principales
• Escalamiento multidimensional

Otro

• Modelado ponderado por grupos
• La maldición de la dimensionalidad
• Determinar el número de clústeres en un conjunto de datos
• Coordenadas paralelas
• Análisis de datos estructurados
• Separabilidad lineal

Referencias

1. Driver y Kroeber (1932). «Expresión cuantitativa de las relaciones culturales». Publicaciones de la Universidad de California en Arqueología y Etnología Estadounidenses . Expresión cuantitativa de las relaciones culturales. Berkeley, CA: University of California Press: 211–256. Archivado desde el original el 2020-12-06 . Consultado el 2019-02-18 .
2. Zubin, Joseph (1938). "Una técnica para medir la afinidad mental". Revista de psicología social y anormal . 33 (4): 508–516. doi :10.1037/h0055441. ISSN  0096-851X.
3. Tryon, Robert C. (1939). Análisis de conglomerados: perfil de correlación y análisis ortométrico (factorial) para el aislamiento de unidades en la mente y la personalidad . Edwards Brothers.
4. Cattell, RB (1943). "La descripción de la personalidad: rasgos básicos resueltos en grupos". Revista de psicología social y anormal . 38 (4): 476–506. doi :10.1037/h0054116.
5. Estivill-Castro, Vladimir (20 de junio de 2002). "Por qué tantos algoritmos de clusterización: un documento de posición". Boletín de exploraciones de ACM SIGKDD . 4 (1): 65–75. doi :10.1145/568574.568575. S2CID  7329935.
6. James A. Davis (mayo de 1967) "Agrupamiento y equilibrio estructural en gráficos", Human Relations 20:181–7
7. Gao, Caroline X.; Dwyer, Dominic; Zhu, Ye; Smith, Catherine L.; Du, Lan; Filia, Kate M.; Bayer, Johanna; Menssink, Jana M.; Wang, Teresa; Bergmeir, Christoph; Wood, Stephen; Cotton, Sue M. (1 de septiembre de 2023). "Una descripción general de los métodos de agrupamiento con pautas para su aplicación en la investigación en salud mental". Investigación en psiquiatría . 327 : 115265. doi : 10.1016/j.psychres.2023.115265 . hdl : 10481/84538 . ISSN  0165-1781.
8. Everitt, Brian (2011). Análisis de conglomerados . Chichester, West Sussex, Reino Unido: Wiley. ISBN 9780470749913.
9. Sibson, R. (1973). "SLINK: un algoritmo óptimamente eficiente para el método de clúster de enlace único" (PDF) . The Computer Journal . 16 (1). British Computer Society: 30–34. doi :10.1093/comjnl/16.1.30.
10. Defays, D. (1977). "Un algoritmo eficiente para un método de enlace completo". The Computer Journal . 20 (4). British Computer Society: 364–366. doi :10.1093/comjnl/20.4.364.
11. Lloyd, S. (1982). "Cuantización de mínimos cuadrados en PCM". IEEE Transactions on Information Theory . 28 (2): 129–137. doi :10.1109/TIT.1982.1056489. S2CID  10833328.
12. Kriegel, Hans-Peter ; Kröger, Peer; Sander, Jörg; Zimek, Arthur (2011). "Agrupamiento basado en la densidad". WIREs Data Mining and Knowledge Discovery . 1 (3): 231–240. doi :10.1002/widm.30. S2CID  36920706.
13. Microsoft Academic Search: artículos de minería de datos más citados Archivado el 21 de abril de 2010 en Wayback Machine : DBSCAN está en el puesto 24, cuando se accedió el: 18/4/2010
14. Ester, Martin; Kriegel, Hans-Peter ; Sander, Jörg; Xu, Xiaowei (1996). "Un algoritmo basado en la densidad para descubrir clústeres en grandes bases de datos espaciales con ruido". En Simoudis, Evangelos; Han, Jiawei; Fayyad, Usama M. (eds.). Actas de la Segunda Conferencia Internacional sobre Descubrimiento de Conocimiento y Minería de Datos (KDD-96) . AAAI Press . págs. 226–231. ISBN. 1-57735-004-9.
15. Ankerst, Mihael; Breunig, Markus M.; Kriegel, Hans-Peter ; Sander, Jörg (1999). "OPTICS: 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 . 
16. Achtert, E.; Böhm, C.; Kröger, P. (2006). "DeLi-Clu: Impulsando la robustez, la completitud, la usabilidad y la eficiencia de la agrupación jerárquica mediante una clasificación por pares más cercanos". Avances en el descubrimiento de conocimientos y la minería de datos . Apuntes de clase en informática. Vol. 3918. págs. 119–128. CiteSeerX 10.1.1.64.1161 . doi :10.1007/11731139_16. ISBN .  978-3-540-33206-0.
17. Aggarwal, Charu C.; Reddy, Chandan K. (eds.). Agrupamiento de datos: algoritmos y aplicaciones . ISBN 978-1-315-37351-5.OCLC 1110589522  .
18. Sculley, D. (2010). Agrupamiento de k-medias a escala web . Proc. 19.ª WWW.
19. Huang, Z. (1998). "Extensiones del algoritmo k -means para agrupar grandes conjuntos de datos con valores categóricos". Minería de datos y descubrimiento de conocimiento . 2 (3): 283–304. doi :10.1023/A:1009769707641. S2CID  11323096.
20. R. Ng y J. Han. "Método de agrupamiento eficiente y eficaz para la minería de datos espaciales". En: Actas de la 20ª Conferencia VLDB, páginas 144-155, Santiago, Chile, 1994.
21. Tian Zhang, Raghu Ramakrishnan, Miron Livny. "Un método de agrupamiento de datos eficiente para bases de datos muy grandes". En: Proc. Int'l Conf. on Management of Data, ACM SIGMOD, págs. 103-114.
22. Kriegel, Hans-Peter ; Kröger, Peer; Zimek, Arthur (julio de 2012). "Agrupamiento de subespacios". Wiley Interdisciplinary Reviews: Minería de datos y descubrimiento de conocimiento . 2 (4): 351–364. doi :10.1002/widm.1057. S2CID  7241355.
23. Agrawal, R.; Gehrke, J.; Gunopulos, D.; Raghavan, P. (2005). "Agrupamiento automático de subespacios de datos de alta dimensión". Minería de datos y descubrimiento de conocimiento . 11 : 5–33. CiteSeerX 10.1.1.131.5152 . doi :10.1007/s10618-005-1396-1. S2CID  9289572. 
24. Karin Kailing, Hans-Peter Kriegel y Peer Kröger. Agrupamiento de subespacios conectados por densidad para datos de alta dimensión . En: Proc. SIAM Int. Conf. on Data Mining (SDM'04) , págs. 246–257, 2004.
25. Achtert, E.; Böhm, C.; Kriegel, H.-P .; Kröger, P.; Müller-Gorman, I.; Zimek, A. (2006). "Encontrar jerarquías de clústeres de subespacios". Descubrimiento de conocimiento en bases de datos: PKDD 2006. Apuntes de clase en informática. Vol. 4213. págs. 446–453. CiteSeerX 10.1.1.705.2956 . doi :10.1007/11871637_42. ISBN.  978-3-540-45374-1.
26. 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 de subespacios". Avances en bases de datos: conceptos, sistemas y aplicaciones . Apuntes de clase en informática. Vol. 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.
27. 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) . págs. 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.
28. Böhm, C.; Kailing, K.; Kröger, P.; Zimek, A. (2004). "Computing Clusters of Correlation Connected Objects". Actas de la conferencia internacional ACM SIGMOD 2004 sobre gestión de datos - SIGMOD '04 . p. 455. CiteSeerX 10.1.1.5.1279 . doi :10.1145/1007568.1007620. ISBN  978-1581138597. Número de identificación del sujeto  6411037.
29. Achtert, E.; Bohm, C.; Kriegel, HP ; Kröger, P.; Zimek, A. (2007). "Sobre la exploración de relaciones complejas de clústeres de correlación". 19.ª Conferencia internacional sobre gestión de bases de datos científicas y estadísticas (SSDBM 2007) . pág. 7. CiteSeerX 10.1.1.71.5021 . doi :10.1109/SSDBM.2007.21. ISBN .  978-0-7695-2868-7.S2CID 1554722  .
30. Meilă, Marina (2003). "Comparación de agrupaciones por variación de información". Teoría del aprendizaje y máquinas de núcleo . Apuntes de clase en informática. Vol. 2777. págs. 173–187. doi :10.1007/978-3-540-45167-9_14. ISBN 978-3-540-40720-1.
31. Kraskov, Alexander; Stögbauer, Harald; Andrzejak, Ralph G.; Grassberger, Peter (1 de diciembre de 2003). "Agrupamiento jerárquico basado en información mutua". arXiv : q-bio/0311039 . Código Bibliográfico :2003q.bio....11039K. {{cite journal}}: Requiere citar revista |journal=( ayuda )
32. Auffarth, B. (18–23 de julio de 2010). "Agrupamiento mediante un algoritmo genético con operador de mutación sesgado". Wcci Cec . IEEE.
33. Frey, BJ; Dueck, D. (2007). "Agrupamiento mediante el paso de mensajes entre puntos de datos". Science . 315 (5814): 972–976. Bibcode :2007Sci...315..972F. CiteSeerX 10.1.1.121.3145 . doi :10.1126/science.1136800. PMID  17218491. S2CID  6502291. 
34. Pfitzner, Darius; Leibbrandt, Richard; Powers, David (2009). "Caracterización y evaluación de medidas de similitud para pares de agrupamientos". Conocimiento y sistemas de información . 19 (3). Springer: 361–394. doi :10.1007/s10115-008-0150-6. S2CID  6935380.
35. Feldman, Ronen; Sanger, James (1 de enero de 2007). Manual de minería de texto: enfoques avanzados para analizar datos no estructurados . Cambridge Univ. Press. ISBN 978-0521836579.OCLC 915286380  .
36. Weiss, Sholom M.; Indurkhya, Nitin; Zhang, Tong; Damerau, Fred J. (2005). Minería de texto: métodos predictivos para analizar información no estructurada . Springer. ISBN 978-0387954332.OCLC 803401334  .
37. Manning, Christopher D.; Raghavan, Prabhakar; Schütze, Hinrich (7 de julio de 2008). Introducción a la recuperación de información . Cambridge University Press. ISBN 978-0-521-86571-5.
38. Descubrimiento de conocimiento en bases de datos – Parte III – Agrupamiento (PDF) , Universidad de Heidelberg , 2017{{citation}}: CS1 maint: location missing publisher (link)
39. Dunn, J. (1974). "Clústeres bien separados y particiones difusas óptimas". Journal of Cybernetics . 4 : 95–104. doi :10.1080/01969727408546059.
40. Peter J. Rousseeuw (1987). "Siluetas: una ayuda gráfica para la interpretación y validación del análisis de conglomerados". Revista de Matemática Computacional y Aplicada . 20 : 53–65. doi :10.1016/0377-0427(87)90125-7.
41. Färber, Ines; Günnemann, Stephan; Kriegel, Hans-Peter ; Kröger, Peer; Müller, Emmanuel; Schubert, Erich; Seidl, Thomas; Zimek, Arthur (2010). "Sobre el uso de etiquetas de clase en la evaluación de agrupaciones" (PDF) . En Fern, Xiaoli Z.; Davidson, Ian; Dy, Jennifer (eds.). MultiClust: descubrimiento, resumen y uso de múltiples agrupaciones . ACM SIGKDD .
42. Pourrajabi, M.; Moulavi, D.; Campello, RJGB; Zimek, A .; Sander, J.; Goebel, R. (2014). "Selección de modelos para agrupamiento semisupervisado". Actas de la 17.ª Conferencia internacional sobre la extensión de la tecnología de bases de datos (EDBT) . págs. 331–342. doi :10.5441/002/edbt.2014.31.
43. Rand, WM (1971). "Criterios objetivos para la evaluación de métodos de agrupamiento". Revista de la Asociación Estadounidense de Estadística . 66 (336). Asociación Estadounidense de Estadística: 846–850. arXiv : 1704.01036 . doi :10.2307/2284239. JSTOR  2284239.
44. Fowlkes, EB; Mallows, CL (1983). "Un método para comparar dos agrupaciones jerárquicas". Revista de la Asociación Estadounidense de Estadística . 78 (383): 553–569. doi :10.1080/01621459.1983.10478008. JSTOR  2288117.
45. Powers, David (2003). Recall and Precision versus the Bookmaker [Recuerdo y precisión frente al corredor de apuestas] . Conferencia internacional sobre ciencia cognitiva. págs. 529–534.
46. Arabie, P. (1985). "Comparación de particiones". Revista de clasificación . 2 (1): 1985. doi :10.1007/BF01908075. S2CID  189915041.
47. Wallace, DL (1983). "Comentario". Revista de la Asociación Estadounidense de Estadística . 78 (383): 569–579. doi :10.1080/01621459.1983.10478009.
48. Powers, David (2012). El problema con Kappa . Capítulo europeo de la Asociación de Lingüística Computacional. págs. 345–355.
49. Luna-Romera, José María; Martínez-Ballesteros, María; García-Gutiérrez, Jorge; Riquelme, José C. (junio 2019). "Índice de validez de agrupamiento externo basado en prueba estadística de chi-cuadrado". Ciencias de la Información . 487 : 1–17. doi :10.1016/j.ins.2019.02.046. hdl : 11441/132081 . S2CID  93003939.
50. Hopkins, Brian; Skellam, John Gordon (1954). "Un nuevo método para determinar el tipo de distribución de individuos vegetales". Anales de botánica . 18 (2). Annals Botany Co: 213–227. doi :10.1093/oxfordjournals.aob.a083391.
51. Banerjee, A. (2004). "Validación de clústeres mediante la estadística de Hopkins". Conferencia internacional IEEE sobre sistemas difusos de 2004 (IEEE Cat. No. 04CH37542) . Vol. 1. págs. 149–153. doi :10.1109/FUZZY.2004.1375706. ISBN . 978-0-7803-8353-1. Número de identificación del sujeto  36701919.
52. Johnson, Stephen C. (1967-09-01). "Esquemas de agrupamiento jerárquico". Psychometrika . 32 (3): 241–254. doi :10.1007/BF02289588. ISSN  1860-0980. PMID  5234703. S2CID  930698.
53. Hartuv, Erez; Shamir, Ron (31 de diciembre de 2000). "Un algoritmo de agrupamiento basado en la conectividad de grafos". Information Processing Letters . 76 (4): 175–181. doi :10.1016/S0020-0190(00)00142-3. ISSN  0020-0190.
54. Remm, Maido; Storm, Christian EV; Sonnhammer, Erik LL (14 de diciembre de 2001). "Agrupamiento automático de ortólogos y parálogos a partir de comparaciones de especies por pares11Editado por F. Cohen". Revista de Biología Molecular . 314 (5): 1041–1052. doi :10.1006/jmbi.2000.5197. ISSN  0022-2836. PMID  11743721.
55. Botstein, David; Cox, David R.; Risch, Neil; Olshen, Richard; Curb, David; Dzau, Victor J.; Chen, Yii-Der I.; Hebert, Joan; Pesich, Robert (1 de julio de 2001). "Genotipado de alto rendimiento con polimorfismos de un solo nucleótido". Genome Research . 11 (7): 1262–1268. doi :10.1101/gr.157801. ISSN  1088-9051. PMC 311112 . PMID  11435409. 
56. Filipovych, Roman; Resnick, Susan M.; Davatzikos, Christos (2011). "Análisis de clústeres semisupervisado de datos de imágenes". NeuroImage . 54 (3): 2185–2197. doi :10.1016/j.neuroimage.2010.09.074. PMC 3008313 . PMID  20933091. 
57. Di Marco, Antonio; Navigli, Roberto (2013). "Agrupamiento y diversificación de resultados de búsqueda web con inducción del sentido de las palabras basada en gráficos". Computational Linguistics . 39 (3): 709–754. doi :10.1162/COLI_a_00148. S2CID  1775181.
58. Bewley, A., y Upcroft, B. (2013). Ventajas de explotar la estructura de proyección para segmentar nubes de puntos 3D densas. En la Conferencia australiana sobre robótica y automatización [1]
59. "Informe sobre el estado de DevOps en 2022". 29 de septiembre de 2022: 8, 14, 74. {{cite journal}}: Requiere citar revista |journal=( ayuda ) [2]
60. Bewley, A.; et al. "Estimación del volumen en tiempo real de la carga útil de una dragalina". IEEE International Conference on Robotics and Automation . 2011 : 1571–1576.
61. Basak, SC; Magnuson, VR; Niemi, CJ; Regal, RR (1988). "Determinación de la similitud estructural de sustancias químicas mediante índices de teoría de grafos". Discr. Appl. Math . 19 (1–3): 17–44. doi : 10.1016/0166-218x(88)90004-2 .
62. Huth, R.; et al. (2008). "Clasificaciones de patrones de circulación atmosférica: avances y aplicaciones recientes" (PDF) . Ann. NY Acad. Sci . 1146 (1): 105–152. Bibcode :2008NYASA1146..105H. doi :10.1196/annals.1446.019. PMID  19076414. S2CID  22655306.
63. Arnott, Robert D. (1 de noviembre de 1980). "Análisis de clústeres y comovimiento del precio de las acciones". Financial Analysts Journal . 36 (6): 56–62. doi :10.2469/faj.v36.n6.56. ISSN  0015-198X.