Análisis de conglomerados

Agrupar un conjunto de objetos por similitud

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

El análisis de conglomerados o agrupamiento es la tarea de agrupar un conjunto de objetos de tal manera que los objetos del mismo grupo (llamado conglomerado ) sean más similares (en algún sentido específico definido por el analista) entre sí que con los de otros grupos. (racimos). Es una tarea principal del análisis de datos exploratorio y una técnica común para el análisis de datos estadísticos , utilizada en muchos campos, incluido 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 grupo y cómo encontrarlos de manera eficiente. Las nociones populares de conglomerados incluyen grupos con distancias pequeñas entre los miembros del conglomerado, áreas densas del espacio de datos, intervalos o distribuciones estadísticas particulares . Por tanto, el clustering puede formularse como un problema de optimización multiobjetivo . El algoritmo de agrupamiento apropiado y la configuración de los parámetros (incluidos parámetros como la función de distancia a utilizar, un umbral de densidad o el número de grupos esperados) dependen del conjunto de datos individual y del uso previsto de los resultados. El análisis de conglomerados 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 fracaso. A menudo es necesario modificar el preprocesamiento de datos y los parámetros del modelo hasta que el resultado alcance las propiedades deseadas.

Además del término agrupamiento , existen varios términos con significados similares, que incluyen 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 suelen estar en el uso de los resultados: mientras que en la minería de datos lo que interesa son los grupos resultantes, 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 la 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 los rasgos. en psicología de la personalidad .

Definición

La noción de "clúster" no se puede definir con precisión, lo cual es una de las razones por las que existen tantos algoritmos de agrupación. ^[5] Hay un denominador común: un grupo de objetos de datos. Sin embargo, diferentes investigadores emplean diferentes modelos de conglomerados y, para cada uno de estos modelos de conglomerados, se pueden proporcionar diferentes algoritmos. La noción de clúster, tal como la encuentran diferentes algoritmos, varía significativamente en sus propiedades. Comprender estos "modelos de clúster" es clave para comprender las diferencias entre los distintos algoritmos. Los modelos de clúster típicos incluyen:

• Modelos de conectividad : por ejemplo,la agrupación jerárquicaconstruye modelos basados ​​en la conectividad a distancia.
• Modelo de centroide s: por ejemplo, elalgoritmo k-meansrepresenta cada grupo mediante un único vector medio.
• Modelos de distribución : los conglomerados se modelan utilizando distribuciones estadísticas, como lasdistribuciones normales multivariadasutilizadas por elalgoritmo de maximización de expectativas.
• Modelos de densidad : por ejemplo,DBSCANyOPTICSdefinen clústeres como regiones densas conectadas en el espacio de datos.
• Modelos subespaciales : enel biclustering(también conocido como co-clustering o clustering de dos modos), los clusters se modelan tanto con miembros del cluster como con 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 gráficos : unacamarilla, es decir, un subconjunto de nodos en ungráficotal que cada dos nodos del subconjunto estén conectados por un borde, se puede considerar como una forma prototípica de clúster. Las flexibilizaciones del requisito de conectividad completa (puede faltar una fracción de los bordes) se conocen como cuasi-cliques, como en elalgoritmo de agrupamiento HCS.
• Modelos de gráficos firmados : cada camino en un gráfico firmado tiene un signo del producto de los signos en los bordes. Según los supuestos de la teoría del equilibrio , las aristas pueden cambiar de signo y dar como resultado un gráfico bifurcado. El "axioma de agrupabilidad" más débil (ningún ciclo tiene exactamente un borde negativo) produce resultados con más de dos grupos, o subgrafos con solo bordes positivos. ^[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, e incluyen modelos subespaciales 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 agrupaciones, que generalmente 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 como:

• Agrupación dura : cada objeto pertenece a un grupo o no
• Agrupación suave (también:agrupamiento difuso ): cada objeto pertenece a cada grupo hasta cierto punto (por ejemplo, una probabilidad de pertenecer al grupo)

También es posible hacer distinciones más finas, por ejemplo:

• Agrupación de partición estricta : cada objeto pertenece exactamente a un grupo
• Agrupación de partición estricta con valores atípicos : los objetos tampoco pueden pertenecer a ningún grupo, en cuyo caso se consideranvalores atípicos
• Agrupación superpuesta (también:agrupación alternativa,agrupación multivista): los objetos pueden pertenecer a más de un grupo; generalmente involucra grupos duros
• Agrupación jerárquica : los objetos que pertenecen a un clúster secundario también pertenecen al clúster principal.
• Agrupación en subespacio : si bien se trata de una agrupación superpuesta, dentro de un subespacio definido de forma única, no se espera que los grupos se superpongan.

Algoritmos

Como se mencionó anteriormente, los algoritmos de agrupación se pueden clasificar según su modelo de agrupación. La siguiente descripción general solo enumerará los ejemplos más destacados de algoritmos de agrupamiento, ya que posiblemente haya más de 100 algoritmos de agrupamiento publicados. No todos proporcionan modelos para sus grupos y, por lo tanto, no pueden clasificarse fácilmente. 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 señaló, "el agrupamiento depende del ojo de quien mira". ^[5] A menudo es necesario elegir experimentalmente el algoritmo de agrupamiento más apropiado para un problema particular, 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 grupos no convexos. ^[5] La mayoría de los métodos de agrupación tradicionales suponen que los grupos presentan una forma esférica, elíptica o convexa. ^[7]

Agrupación basada en conectividad (agrupación jerárquica)

La agrupación basada en conectividad, también conocida como agrupación jerárquica , se basa en la idea central de que los objetos están más relacionados con objetos cercanos que con objetos más lejanos. Estos algoritmos conectan "objetos" para formar "grupos" según su distancia. Un grupo puede describirse en gran medida por la distancia máxima necesaria para conectar partes del grupo. A diferentes distancias se formarán distintos clusters, que pueden representarse mediante un dendrograma , lo que explica de dónde proviene el nombre común de " clustering jerárquico ": estos algoritmos no proporcionan una única partición del conjunto de datos, sino que proporcionan una extensa jerarquía de grupos que se fusionan entre sí a determinadas distancias. En un dendrograma, el eje y marca la distancia a la que se fusionan los grupos, mientras que los objetos se colocan a lo largo del eje x de manera que los grupos no se mezclen.

La agrupación basada en conectividad es toda una familia de métodos que difieren en la forma en que se calculan las distancias. Además de la elección habitual de funciones de distancia , el usuario también debe decidir el criterio de vinculación (dado que un grupo consta de múltiples objetos, hay múltiples candidatos para calcular la distancia) a utilizar. Las opciones populares se conocen como agrupamiento de enlace simple (el mínimo de distancias de objetos), agrupamiento de enlace completo (el máximo de distancias de objetos) y UPGMA o WPGMA ("Método de grupo de pares ponderados o no ponderados con media aritmética", también conocido como enlace promedio). agrupamiento). Además, la agrupación jerárquica puede ser aglomerativa (comenzando con elementos individuales y agregándolos en grupos) 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 deberá elegir los grupos apropiados. No son muy resistentes a los valores atípicos, que aparecerán como grupos adicionales o incluso provocarán que otros grupos se fusionen (lo que se conoce como "fenómeno de encadenamiento", en particular con la agrupación 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 agrupamiento de enlace único y CLINK ^[10] para agrupamiento de enlace completo. ${\displaystyle {\mathcal {O}}(n^{3})}$ ${\displaystyle {\mathcal {O}}(2^{n-1})}$ ${\displaystyle {\mathcal {O}}(n^{2})}$

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

Agrupación basada en centroides

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

Se sabe que el problema de optimización en sí es NP-difícil y, por tanto, el enfoque común es buscar sólo 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 -medias a menudo incluyen optimizaciones tales como elegir la mejor de varias ejecuciones, pero también restringir los centroides a miembros del conjunto de datos ( k -medoids ), elegir medianas ( k -medians clustering ), elegir los centros iniciales de manera menos aleatoria ( k -means++ ) o permitir una asignación de clúster difusa ( difusa c-means ).

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

K-medias tiene una serie de propiedades teóricas interesantes. Primero, divide el espacio de datos en una estructura conocida como diagrama de Voronoi . En segundo lugar, conceptualmente está cerca de la clasificación del vecino más cercano y, como tal, es popular en el aprendizaje automático . En tercer lugar, puede verse como una variación del agrupamiento basado 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.

• k -means ejemplos de agrupación
• 
  k -means separa los datos en celdas Voronoi, lo que supone grupos del mismo tamaño (no es adecuado aquí).
• 
  k -means no puede representar grupos 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 entornos más elaborados), la tarea es encontrar las mejores ubicaciones de almacenes para atender de manera óptima a un conjunto determinado de consumidores. Se pueden considerar los "almacenes" como centroides de conglomerados y las "ubicaciones de 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 actualmente considerado.

Agrupación basada en distribución

El modelo de agrupamiento más relacionado con la estadística se basa en modelos de distribución . Los conglomerados pueden entonces definirse fácilmente como objetos que probablemente pertenecen a la misma distribución. Una propiedad conveniente de este enfoque es que se parece mucho a la forma en que se generan conjuntos de datos artificiales: muestreando objetos aleatorios de una distribución.

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 elegir la complejidad del modelo adecuada sea inherentemente difícil.

Un método destacado se conoce como modelos de mezcla gaussiana (que utilizan el algoritmo de maximización de expectativas ). Aquí, el conjunto de datos generalmente se modela con un número fijo (para evitar el sobreajuste) de distribuciones gaussianas que se inicializan aleatoriamente y cuyos parámetros se optimizan iterativamente para adaptarse 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 a menudo se asignan a la distribución gaussiana a la que probablemente pertenecen; para agrupaciones suaves, esto no es necesario.

La agrupación basada en distribución produce modelos complejos para agrupaciones que pueden capturar la correlación y dependencia entre atributos. Sin embargo, estos algoritmos imponen una carga adicional al usuario: para muchos conjuntos de datos reales, puede que no exista un modelo matemático definido de manera concisa (por ejemplo, asumir que las distribuciones gaussianas es una suposición bastante fuerte sobre los datos).

• Ejemplos de agrupación de modelos de mezcla gaussiana
• 
  En datos distribuidos gaussianos, EM funciona bien, ya que utiliza gaussianos para modelar grupos.
• 
  Los conglomerados basados ​​en densidad no se pueden modelar utilizando distribuciones gaussianas.

Agrupación basada en densidad

En la agrupación basada en densidad, ^[12] las agrupaciones se definen como áreas de mayor densidad que el resto del conjunto de datos. Los objetos en áreas dispersas (que se requieren para separar grupos) generalmente se consideran 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 clúster bien definido llamado "densidad-alcanzabilidad". De manera similar a la agrupación basada en enlaces, se basa en conectar puntos dentro de ciertos umbrales de distancia. Sin embargo, sólo conecta puntos que satisfacen un criterio de densidad, definido en la variante original como un número mínimo de otros objetos dentro de este radio. Un grupo consta de todos los objetos conectados por densidad (que, a diferencia de muchos otros métodos, pueden formar un grupo de forma arbitraria) más todos los objetos que se encuentran dentro del alcance 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 fronterizos). en cada ejecución, por lo que no es necesario 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 de agrupamiento de enlaces . DeLi-Clu, ^[16] Density-Link-Clustering combina ideas de agrupación de enlace ú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 }$

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

El desplazamiento medio es un enfoque de agrupación en el que cada objeto se mueve al área más densa en su vecindad, según la estimación de la densidad del núcleo . Finalmente, los objetos convergen a máximos locales de densidad. De manera similar a la agrupación de k-medias, estos "atractores de densidad" pueden servir como representantes del conjunto de datos, pero el desplazamiento medio puede detectar agrupaciones de formas arbitrarias similares a DBSCAN. Debido al costoso procedimiento iterativo y a la estimación de densidad, el cambio medio suele ser más lento que DBSCAN o k-Means. Además de eso, la aplicabilidad del algoritmo de desplazamiento medio a datos multidimensionales se ve obstaculizada por el comportamiento irregular de la estimación de la densidad del núcleo, lo que resulta en una fragmentación excesiva de las colas de los grupos. ^[dieciséis]

• Ejemplos de agrupación basada en densidad
• 
  Agrupación basada en densidad con DBSCAN
• 
  DBSCAN asume grupos de densidad similar y puede tener problemas para separar los grupos cercanos.
• 
  OPTICS es una variante de DBSCAN que mejora el manejo de grupos de diferentes densidades.

Agrupación basada en cuadrículas

La técnica basada en cuadrículas se utiliza para un conjunto de datos multidimensional . ^[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 grillas es rápida y tiene baja complejidad computacional. Hay dos tipos de métodos de agrupación en clústeres basados ​​en cuadrículas: STING y CLIQUE. Los pasos involucrados en el algoritmo de agrupamiento basado en cuadrículas son:

1. Divida el espacio de datos en un número finito de celdas.
2. Seleccione aleatoriamente una celda 'c', donde c no debe atravesarse 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 grupo
   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 en el grupo y repita los pasos 4.2 y 4.3 hasta que no haya ningún vecino con una densidad mayor que la densidad umbral.
5. Repita los pasos 2,3 y 4 hasta atravesar todas las celdas.
6. Detener.

Desarrollos recientes

En los últimos años, se han realizado esfuerzos considerables para 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 ), la voluntad de intercambiar el significado semántico de los grupos generados por el rendimiento ha ido en aumento. Esto llevó al desarrollo de métodos de preagrupación, como la agrupación en dosel , que puede procesar enormes conjuntos de datos de manera eficiente, pero los "agrupaciones" resultantes son simplemente una prepartición aproximada del conjunto de datos para luego analizar las particiones con métodos más lentos existentes, como como k-significa agrupación .

Para datos de alta dimensión , muchos de los métodos existentes fallan debido a la maldición de la dimensionalidad , lo que hace que determinadas funciones de distancia sean problemáticas en espacios de alta dimensión. Esto llevó a nuevos algoritmos de agrupación para datos de alta dimensión que se centran en la agrupación subespacial (donde solo se utilizan algunos atributos y los modelos de agrupación incluyen los atributos relevantes para el grupo) y la agrupación de correlación que también busca subespacio rotado arbitrariamente ("correlacionado") grupos que pueden modelarse dando una correlación de sus atributos. ^[22] Ejemplos de tales algoritmos de agrupamiento son CLIQUE ^[23] y SUBCLU . ^[24]

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

Se han propuesto varios sistemas de agrupación 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] También la propagación de creencias , un desarrollo reciente en informática y 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 implican una evaluación " interna ", donde la agrupación se resume en un único puntaje de calidad, una evaluación " externa ", donde la agrupación se compara con una clasificación "verdadera" existente, una evaluación " manual " realizada por un experto humano, y evaluación " indirecta " evaluando la utilidad de la agrupación en su aplicación prevista. ^[35]

Las medidas de evaluación interna adolecen del problema de que representan funciones que en sí mismas pueden verse como un objetivo de agrupación. Por ejemplo, se podrían agrupar los datos establecidos por el coeficiente de silueta; 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 tales etiquetas de "verdad sobre el terreno", entonces no necesitaríamos agruparnos; y en aplicaciones prácticas normalmente no tenemos este tipo de etiquetas. Por otro lado, 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 una agrupación, pero esto requiere una evaluación humana ^[35] , que es altamente subjetiva. Sin embargo, estas estadísticas pueden ser bastante informativas para identificar agrupaciones incorrectas, ^[36] pero no se debe descartar la evaluación humana subjetiva. ^[36]

Evaluación interna

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

Por lo tanto, las medidas de evaluación interna son las más adecuadas para obtener una idea de 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 modelo no tiene ninguna posibilidad si el conjunto de datos contiene un conjunto de modelos radicalmente diferente, 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 asumen agrupaciones convexas. En un conjunto de datos con clusters no convexos, ni el uso de k -medias ni de un criterio de evaluación que asuma convexidad es correcto.

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 en función de 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 conglomerados, es el centroide del conglomerado , es la distancia promedio de todos los elementos del conglomerado al centroide y es la distancia entre los centroides y . Dado que los algoritmos que producen grupos con distancias bajas dentro de los grupos (alta similitud dentro de los grupos) y altas distancias entre grupos (baja similitud entre grupos) tendrán un índice de Davies-Bouldin bajo, el algoritmo de agrupación que produce una colección de grupos 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 conglomerados densos y bien separados. Se define como la relación entre la distancia mínima entre grupos y la distancia máxima dentro de los grupos. Para cada partición del clúster, 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 grupos i y j , y d '( k ) mide la distancia intra-grupo del grupo k . La distancia entre grupos d ( i , j ) entre dos grupos puede ser cualquier número de medidas de distancia, como la distancia entre los centroides de los grupos. De manera similar, la distancia dentro del grupo d '( k ) se puede medir de diversas formas, como la distancia máxima entre cualquier par de elementos en el grupo  k . Dado que el criterio interno busca grupos con alta similitud intragrupo y baja similitud entre grupos, los algoritmos que producen grupos con alto índice de Dunn son más deseables.

• Coeficiente de silueta

El coeficiente de silueta contrasta la distancia promedio a elementos del mismo grupo con la distancia promedio a 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 la agrupación de k -medias, ^{[ cita necesaria ]} y también se utiliza para determinar el número óptimo de agrupaciones.

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 clases conocidas y puntos de referencia externos. Estos puntos de referencia consisten en un conjunto de elementos preclasificados, y estos conjuntos suelen ser creados por humanos (expertos). Por lo tanto, los conjuntos de puntos de referencia pueden considerarse como 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 debatido si esto es adecuado para datos reales o solo para conjuntos de datos sintéticos con una verdad fundamental, ya que las clases pueden contener una estructura interna, los atributos presentes pueden no permitir la separación de grupos o las clases pueden contener anomalías . ^[40] Además, desde el punto de vista del descubrimiento de conocimientos , la reproducción de conocimientos conocidos puede no ser necesariamente el resultado previsto. ^[40] En el escenario especial de agrupamiento restringido , donde la metainformación (como etiquetas de clase) ya se utiliza en el proceso de agrupamiento, la retención de información para fines de evaluación no es trivial. ^[41]

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

Al igual que 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 grupos contienen una sola clase. ^[37] Su cálculo se puede considerar de la siguiente manera: para cada grupo, cuente el número de puntos de datos de la clase más común en dicho grupo. Ahora tome la suma de todos los grupos 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 puntos de datos de partición, la pureza se puede definir 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 tener muchos racimos, y más racimos facilitarán la producción de una alta pureza. Siempre es posible obtener una puntuación de pureza de 1 colocando cada punto de datos en su propio grupo. Además, la pureza no funciona bien con datos desequilibrados, donde 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 99,9%.

• Índice rand ^[42]

El índice Rand calcula qué tan similares son los grupos (devueltos por el algoritmo de agrupamiento) a las clasificaciones de referencia. Se puede calcular usando 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 correctas por pares . Es decir, es el número de pares de puntos que están agrupados en la partición predicha y en la partición de verdad fundamental, es el número de pares de puntos que están agrupados en la partición predicha pero no en la partición de verdad fundamental, etc. 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 de 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 agrupación en clústeres. La medida F aborda esta preocupación, ^{[ cita necesaria ] al igual que el} índice Rand ajustado corregido por probabilidad .

• Medida F

La medida F se puede utilizar para equilibrar la contribución de los falsos negativos ponderando el recuerdo a través de un parámetro . Dejemos que la precisión y el recuerdo (ambas medidas de evaluación externa en sí mismas) se definan 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 usando 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 cada vez mayor 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 de 0 hacia arriba sin límite. ${\displaystyle TN}$

• índice jaccard

El índice de Jaccard se utiliza para cuantificar la similitud entre dos conjuntos de datos. El índice 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}}}$

Esto 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 sin dejar de ignorar : ${\displaystyle TP}$ ${\displaystyle TN}$

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

• Índice de Fowlkes-Mallows ^[43]

El índice Fowlkes-Mallows calcula la similitud entre los grupos devueltos por 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 conglomerados y las clasificaciones de referencia. Se puede calcular usando 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 que también se conoce como medida G, mientras que la medida F es su media armónica. ^{[44] [45]} Además, la precisión y la recuperación también se conocen como índices de Wallace y . ^[46] Las versiones normalizadas de probabilidad de recuerdo, precisión y medida G corresponden a la información , la marca y la correlación de Matthews y se relacionan fuertemente con Kappa . ^[47] ${\displaystyle TP}$ ${\displaystyle FP}$ ${\displaystyle FN}$ ${\displaystyle FM}$ ${\displaystyle P}$ ${\displaystyle R}$ ${\displaystyle B^{I}}$ ${\displaystyle B^{II}}$

• El índice Chi ^[48] es un índice de validación externa que mide los resultados de agrupamiento aplicando la estadística chi-cuadrado . Este índice valora positivamente el hecho de que las etiquetas sean lo más dispersas posible en los conglomerados, es decir, que cada conglomerado tenga la menor cantidad posible de etiquetas diferentes. Cuanto mayor sea el valor del índice Chi, mayor será la relación entre los grupos resultantes y la etiqueta utilizada.
• La información mutua es una medida teórica de la información de cuánta información se comparte entre una agrupación y una clasificación de verdad fundamental que puede detectar una similitud no lineal entre dos agrupaciones. La información mutua normalizada es una familia de variantes corregidas por azar de esta que tiene un sesgo reducido para diferentes números de conglomerados. ^[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 agrupación). Muestra cuán diferente es un grupo del grupo estándar de oro.

Tendencia de conglomerado

Medir la tendencia de los conglomerados es medir hasta qué punto existen conglomerados 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 grupos.

• Estadística de Hopkins

Existen múltiples formulaciones de la estadística de Hopkins . ^[49] Uno típico es el siguiente. ^[50] Sea el conjunto de puntos de datos en el espacio dimensional. Considere una muestra aleatoria (sin reemplazo) de puntos de datos con miembros . También genere un conjunto de puntos de datos distribuidos uniformemente aleatoriamente. Ahora defina dos medidas de distancia, que sean la distancia de su vecino más cercano en X y la distancia de su vecino más cercano en X. Luego definimos el estadístico 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 solo un gaussiano también obtendrán una puntuación cercana a 1, ya que esta estadística mide la desviación de una distribución uniforme , no de la multimodalidad , lo que hace que esta estadística sea en gran medida inútil en su aplicación (ya que los datos reales nunca son ni 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 grupos de organismos (individuos) a nivel de especie, género o nivel superior que comparten una serie de atributos.

Transcriptómica

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

Análisis de secuencia

La agrupación de secuencias se utiliza para agrupar secuencias homólogas en familias de genes . ^[53] Este es un concepto muy importante en bioinformática y 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. ^[54]

Agrupación genética humana

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

Medicamento

Imagenes medicas

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. ^[55]

Análisis de actividad antimicrobiana.

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

Segmentación IMRT

La agrupación se puede utilizar para dividir un mapa de fluencia en distintas regiones para convertirlo 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 mercado 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 comprender mejor las relaciones entre diferentes grupos de consumidores/ clientes potenciales , y para utilizarlo en la segmentación de mercados , posicionamiento de productos , desarrollo de nuevos productos y selección de mercados de prueba.

Agrupación de artículos de compras.

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 puede utilizarse para reconocer comunidades dentro de grandes grupos de personas.

Agrupación de resultados de búsqueda

En el proceso de agrupación inteligente de archivos y sitios web, se puede utilizar la agrupación 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 agrupación en clústeres basadas en 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 pueda 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 arroje resultados completos seleccionando el resultado superior de cada grupo. ^[56]

Optimización de mapas resbaladizos

El mapa de fotografías de Flickr y otros sitios de mapas utilizan la agrupación para reducir la cantidad de marcadores en un mapa. ^{[ cita necesaria ]} 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 en el código al reformar la funcionalidad que se ha dispersado. Es una forma de reestructuración y, por tanto, es una forma de mantenimiento preventivo directo.

Segmentación de imagen

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 . ^[57]

Algoritmos evolutivos

La agrupación se puede utilizar para identificar diferentes nichos dentro de la población de un algoritmo evolutivo de modo que las oportunidades reproductivas puedan 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 elementos según los gustos del usuario. A veces utilizan algoritmos de agrupación para predecir las preferencias de un usuario en función de las preferencias de otros usuarios en el grupo del usuario.

Métodos Monte Carlo de la cadena de Markov

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

Detección de anomalías

Las anomalías/valores atípicos suelen definirse (ya sea explícita o implícitamente) con respecto a la estructura de agrupación de los datos.

Procesamiento natural del lenguaje

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

DevOps

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

Ciencias Sociales

Análisis de secuencias en 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 crimen

El análisis de conglomerados se puede utilizar para identificar áreas donde hay mayores incidencias de tipos particulares de delitos. Al identificar estas áreas distintas o "puntos críticos" donde ha ocurrido un delito similar durante un período de tiempo, es posible gestionar los recursos policiales de manera más efectiva.

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 emprendidos 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 que la conciencia situacional robótica rastree objetos y detecte valores atípicos en los datos de los sensores. ^[59]

quimica matematica

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

Climatología

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

Finanzas

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

Geología del petróleo

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

Geoquímica

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

Ver también

Tipos especializados de análisis de conglomerados.

• Algoritmos de agrupamiento automático
• Agrupación equilibrada
• Agrupación de datos de alta dimensión
• Agrupación conceptual
• Agrupación de consenso
• Agrupación restringida
• Detección comunitaria
• Agrupación de flujos de datos
• Agrupación HCS
• Agrupación de secuencias
• Agrupación espectral

Técnicas utilizadas en el análisis de conglomerados.

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

Proyección y preprocesamiento de datos.

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

Otro

• Modelado ponderado por conglomerados
• Maldición de dimensionalidad
• Determinar el número de grupos en un conjunto de datos
• Coordenadas paralelas
• Análisis de datos estructurados
• Separabilidad lineal

Referencias

1. Conductor y Kroeber (1932). "Expresión Cuantitativa de Relaciones Culturales". Publicaciones de la Universidad de California en Arqueología y Etnología Estadounidenses . Berkeley, CA: Prensa de la Universidad de California. Expresión cuantitativa de relaciones culturales: 211–256. Archivado desde el original el 6 de diciembre de 2020 . Consultado el 18 de febrero de 2019 .
2. Zubin, José (1938). "Una técnica para medir las ideas afines". La 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 . Hermanos Edwards.
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 agrupació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) "Agrupación y equilibrio estructural en gráficos", Human Relations 20:181–7
7. Gao, Carolina X.; Dwyer, Domingo; Zhu, Ye; Smith, Catalina L.; Du, Lan; Filia, Kate M.; Bayer, Juana; Menssink, Jana M.; Wang, Teresa; Bergmeir, Christoph; Madera, Esteban; Algodón, Sue M. (1 de septiembre de 2023). "Una descripción general de los métodos de agrupación con directrices 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) . La revista informática . Sociedad Británica de Computación. 16 (1): 30–34. doi :10.1093/comjnl/16.1.30.
10. Defays, D. (1977). "Un algoritmo eficiente para un método de enlace completo". La revista informática . Sociedad Británica de Computación. 20 (4): 364–366. doi : 10.1093/comjnl/20.4.364.
11. Lloyd, S. (1982). "Cuantización de mínimos cuadrados en PCM". Transacciones IEEE sobre teoría de la información . 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). "Agrupación basada en densidad". WIREs Minería de datos y descubrimiento de conocimientos . 1 (3): 231–240. doi :10.1002/widm.30. S2CID  36920706.
13. Búsqueda académica de Microsoft: artículos de minería de datos más citados Archivado el 21 de abril de 2010 en Wayback Machine : DBSCAN ocupa el puesto 24, cuando se accedió el: 18/04/2010
14. Ester, Martín; Kriegel, Hans-Peter ; Sander, Jörg; Xu, Xiaowei (1996). "Un algoritmo basado en densidad para descubrir grupos 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) . Prensa AAAI . págs. 226-231. ISBN 1-57735-004-9.
15. Ankerst, Mihael; Breunig, Markus M.; Kriegel, Hans-Peter ; Sander, Jörg (1999). "ÓPTICA: Ordenar puntos para identificar la estructura de agrupación". Conferencia internacional ACM SIGMOD sobre Gestión de datos . Prensa ACM . págs. 49–60. CiteSeerX 10.1.1.129.6542 . 
16. 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 mediante una clasificación de par más cercano". Avances en descubrimiento de conocimiento y minería de datos . Apuntes de conferencias sobre 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.). Agrupación de datos: algoritmos y aplicaciones . ISBN 978-1-315-37351-5. OCLC  1110589522.
18. Sculley, D. (2010). "Agrupación de k-means a escala web ". Proc. XIX 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 conocimientos . 2 (3): 283–304. doi :10.1023/A:1009769707641. S2CID  11323096.
20. R. Ng y J. Han. "Método de agrupación eficiente y eficaz para la extracción de datos espaciales". En: Actas de la XX Conferencia VLDB, páginas 144–155, Santiago, Chile, 1994.
21. Tian Zhang, Raghu Ramakrishnan, Miron Livny. "Un método eficaz de agrupación de datos para bases de datos muy grandes". En: Proc. Conferencia Internacional. sobre Gestión de Datos, ACM SIGMOD, págs. 103–114.
22. Kriegel, Hans-Peter ; Kröger, Peer; Zimek, Arthur (julio de 2012). "Agrupación subespacial". Reseñas interdisciplinarias de Wiley: minería de datos y descubrimiento de conocimientos . 2 (4): 351–364. doi :10.1002/widm.1057. S2CID  7241355.
23. Agrawal, R.; Gehrke, J.; Gunópulos, D.; Raghavan, P. (2005). "Agrupación subespacial automática de datos de alta dimensión". Minería de datos y descubrimiento de conocimientos . 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. "Agrupación subespacial conectada por densidad para datos de alta dimensión ". En: Proc. Internacional SIAM. Conf. sobre minería de datos (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 grupos subespaciales". Descubrimiento de conocimientos en bases de datos: PKDD 2006 . Apuntes de conferencias sobre 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 subespaciales". Avances en Bases de Datos: Conceptos, Sistemas y Aplicaciones . Apuntes de conferencias sobre 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). "Jerarquías mineras de clústeres de correlación". XVIII Congreso 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. S2CID  2679909.
28. Böhm, C.; Kailing, K.; Kröger, P.; Zimek, A. (2004). "Cálculo de grupos de objetos conectados por correlación". Actas de la conferencia internacional ACM SIGMOD 2004 sobre gestión de datos - SIGMOD '04 . pag. 455. CiteSeerX 10.1.1.5.1279 . doi :10.1145/1007568.1007620. ISBN  978-1581138597. S2CID  6411037.
29. Achtert, E.; Bohm, C.; Kriegel, HP ; Kröger, P.; Zimek, A. (2007). "Sobre la exploración de relaciones complejas de grupos de correlación". XIX Conferencia Internacional sobre Gestión de Bases de Datos Científicas y Estadísticas (SSDBM 2007) . pag. 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 kernel . Apuntes de conferencias sobre 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, Alejandro; Stögbauer, Harald; Andrzejak, Ralph G.; Grassberger, Peter (1 de diciembre de 2003). "Agrupación jerárquica basada en información mutua". arXiv : q-bio/0311039 . Código Bib : 2003q.bio....11039K. {{cite journal}}: Citar diario requiere |journal=( ayuda )
32. Auffarth, B. (18 al 23 de julio de 2010). "Agrupación mediante un algoritmo genético con operador de mutación sesgado". Wcci Cec . IEEE.
33. Frey, BJ; Dueck, D. (2007). "Agrupación pasando mensajes entre puntos de datos". Ciencia . 315 (5814): 972–976. Código Bib : 2007 Ciencia... 315.. 972F. CiteSeerX 10.1.1.121.3145 . doi : 10.1126/ciencia.1136800. PMID  17218491. S2CID  6502291. 
34. Pfitzner, Darío; Leibbrandt, Richard; Poderes, David (2009). "Caracterización y evaluación de medidas de similitud para pares de agrupaciones". Sistemas de Conocimiento y Información . Saltador. 19 (3): 361–394. doi :10.1007/s10115-008-0150-6. S2CID  6935380.
35. Feldman, Ronen; Sanger, James (1 de enero de 2007). El manual de minería de textos: enfoques avanzados para el análisis de datos no estructurados . Universidad de Cambridge. Prensa. ISBN 978-0521836579. OCLC  915286380.
36. Weiss, Sholom M.; Indurkhya, Nitin; Zhang, Tong; Damerau, Fred J. (2005). Minería de textos: métodos predictivos para analizar información no estructurada . Saltador. 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 . Prensa de la Universidad de Cambridge. ISBN 978-0-521-86571-5.
38. Descubrimiento de conocimientos en bases de datos - Parte III - Agrupación (PDF) , Universidad de Heidelberg , 2017{{citation}}: CS1 maint: location missing publisher (link)
39. Dunn, J. (1974). "Clústeres bien separados y particiones difusas óptimas". Revista de Cibernética . 4 : 95-104. doi :10.1080/01969727408546059.
40. Färber, Inés; 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 .
41. Pourrajabi, M.; Moulavi, D.; Campello, RJGB; Zimek, A .; Sander, J.; Goebel, R. (2014). "Selección de modelo para agrupación semisupervisada". Actas de la 17ª Conferencia Internacional sobre Ampliación de Tecnología de Bases de Datos (EDBT) . págs. 331–342. doi :10.5441/002/edbt.2014.31.
42. Rand, WM (1971). "Criterios objetivos para la evaluación de métodos de agrupamiento". Revista de la Asociación Estadounidense de Estadística . Asociación Estadounidense de Estadística. 66 (336): 846–850. arXiv : 1704.01036 . doi :10.2307/2284239. JSTOR  2284239.
43. Fowlkes, EB; Malvas, 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.
44. Poderes, David (2003). Recordatorio y precisión frente a la casa de apuestas . Congreso Internacional sobre Ciencias Cognitivas. págs. 529–534.
45. Arabia, P. (1985). "Comparación de particiones". Revista de Clasificación . 2 (1): 1985. doi :10.1007/BF01908075. S2CID  189915041.
46. Wallace, DL (1983). "Comentario". Revista de la Asociación Estadounidense de Estadística . 78 (383): 569–579. doi :10.1080/01621459.1983.10478009.
47. Poderes, David (2012). El problema con Kappa . Capítulo Europeo de la Asociación de Lingüística Computacional. págs. 345–355.
48. 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.
49. Hopkins, Brian; Skellam, John Gordon (1954). "Un nuevo método para determinar el tipo de distribución de individuos vegetales". Anales de botánica . Annals Botany Co. 18 (2): 213–227. doi : 10.1093/oxfordjournals.aob.a083391.
50. Banerjee, A. (2004). "Validación de conglomerados mediante la estadística de Hopkins". Conferencia internacional IEEE de 2004 sobre sistemas difusos (IEEE Cat. No.04CH37542) . vol. 1. págs. 149-153. doi :10.1109/FUZZY.2004.1375706. ISBN 978-0-7803-8353-1. S2CID  36701919.
51. Johnson, Stephen C. (1 de septiembre de 1967). "Esquemas de agrupamiento jerárquico". Psicometrika . 32 (3): 241–254. doi :10.1007/BF02289588. ISSN  1860-0980. PMID  5234703. S2CID  930698.
52. Hartuv, Erez; Shamir, Ron (31 de diciembre de 2000). "Un algoritmo de agrupamiento basado en conectividad de gráficos". Cartas de procesamiento de información . 76 (4): 175–181. doi :10.1016/S0020-0190(00)00142-3. ISSN  0020-0190.
53. Remm, Maido; Tormenta, Christian EV; Sonnhammer, Erik LL (14 de diciembre de 2001). "Agrupación automática de ortólogos y parálogos a partir de comparaciones de especies por pares11 Editado por F. Cohen". Revista de biología molecular . 314 (5): 1041-1052. doi :10.1006/jmbi.2000.5197. ISSN  0022-2836. PMID  11743721.
54. Botstein, David; Cox, David R.; Risch, Neil; Olshen, Richard; Frenar, David; Dzau, Víctor J.; Chen, Yii-Der I.; Hébert, Juana; Pesich, Robert (1 de julio de 2001). "Genotipado de alto rendimiento con polimorfismos de un solo nucleótido". Investigación del genoma . 11 (7): 1262-1268. doi :10.1101/gr.157801. ISSN  1088-9051. PMC 311112 . PMID  11435409. 
55. Filipovych, romano; Resnick, Susan M.; Davatzikos, Christos (2011). "Análisis de conglomerados semisupervisado de datos de imágenes". NeuroImagen . 54 (3): 2185–2197. doi : 10.1016/j.neuroimage.2010.09.074. PMC 3008313 . PMID  20933091. 
56. Di Marco, Antonio; Navigli, Roberto (2013). "Agrupación y diversificación de resultados de búsqueda web con inducción del sentido de palabras basada en gráficos". Ligüística computacional . 39 (3): 709–754. doi :10.1162/COLI_a_00148. S2CID  1775181.
57. Bewley, A., & Upcroft, B. (2013). Advantages of Exploiting Projection Structure for Segmenting Dense 3D Point Clouds. In Australian Conference on Robotics and Automation [1]
58. "2022 Accelerate State of DevOps Report". 29 September 2022: 8, 14, 74. {{cite journal}}: Cite journal requires |journal= (help) [2]
59. Bewley, A.; et al. "Real-time volume estimation of a dragline payload". IEEE International Conference on Robotics and Automation. 2011: 1571–1576.
60. Basak, S.C.; Magnuson, V.R.; Niemi, C.J.; Regal, R.R. (1988). "Determining Structural Similarity of Chemicals Using Graph Theoretic Indices". Discr. Appl. Math. 19 (1–3): 17–44. doi:10.1016/0166-218x(88)90004-2.
61. Huth, R.; et al. (2008). "Classifications of Atmospheric Circulation Patterns: Recent Advances and Applications" (PDF). Ann. N.Y. Acad. Sci. 1146 (1): 105–152. Bibcode:2008NYASA1146..105H. doi:10.1196/annals.1446.019. PMID 19076414. S2CID 22655306.
62. Arnott, Robert D. (1980-11-01). "Cluster Analysis and Stock Price Comovement". Financial Analysts Journal. 36 (6): 56–62. doi:10.2469/faj.v36.n6.56. ISSN 0015-198X.