Agrupamiento jerárquico

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En minería de datos, el agrupamiento jerárquico es un método de análisis de grupos el cual busca construir una jerarquía de grupos. Estrategias para agrupamiento jerárquico generalmente caen en dos tipos:

  • Aglomerativas: Este es un acercamiento ascendente: cada observación comienza en su propio grupo, y los pares de grupos son mezclados mientras uno sube en la jerarquía.
  • Divisivas: : Este es un acercamiento descendente: todas las observaciones comienzan en un grupo, y se realizan divisiones mientras uno baja en la jerarquía.

En general, las mezclas y divisiones son determinadas de forma golosa. Los resultados del agrupamiento jerárquico son usualmente presentados en un dendrograma.

En el caso general, la complejidad del agrupamiento aglomerativo es \mathcal{O}(n^3) , lo cual los hace demasiado lentos para grandes conjuntos de datos. El agrupamiento divisivo con búsqueda exhaustiva es \mathcal{O}(2^n)lo cual es aun peor. Sin embargo, para algunos casos especiales, óptimos y eficientes métodos aglomerativos (de complejidad \mathcal{O}(n^2)) ) son conocidos: SLINK[1] para agrupamiento de enlace-simple y CLINK[2] para agrupamiento de enlace completo.

Disimilitud de grupo[editar]

En orden de decidir cuales grupos deberían ser combinados (para aglomerativo), o cuando un grupo debería ser dividido (para divisivo), una medida de disimilitud entre conjuntos de observaciones es requerida. En la mayoría de los métodos de agrupamiento jerárquico, esto es logrado mediante uso de una métrica apropiada (una medida de distancia entre pares de observaciones), y un criterio de enlace el cual especifica la disimilitud de conjuntos como una función de las distancias dos a dos entre observaciones en los conjuntos.

Métrica[editar]

La elección de una métrica apropiada influenciará la forma de los grupos, ya que algunos pueden estar cerca unos de otros de acuerdo a una distancia y más lejos de acuerdo a otra. Por ejemplo, en un espacio 2-dimensional, la distancia entre el punto (1,0) y el origen (0,0) es siempre 1 de acuerdo a las normas usuales, pero la distancia entre el punto (1,1) y el origen (0,0) puede ser 2, \scriptstyle\sqrt{2} o 1 bajo la distancia Manhattan, la distancia euclidiana o la distancia máxima respectivamente.

Algunas métricas comúnmente usadas para agrupamiento jerárquico son:[3]

Names Formula
Distancia euclidiana  \|a-b \|_2 = \sqrt{\sum_i (a_i-b_i)^2}
Distancia euclidiana al cuadrado  \|a-b \|_2^2 = \sum_i (a_i-b_i)^2
Distancia Manhattan  \|a-b \|_1 = \sum_i |a_i-b_i|
distancia máxima  \|a-b \|_\infty = \max_i |a_i-b_i|
Distancia Mahalanobis  \sqrt{(a-b)^{\top}S^{-1}(a-b)} donde S es la matriz de covarianza
Similitud coseno  \frac{a \cdot b}{\|a\| \|b\|}

Para texto u otro dato no numérico, métricas como la Distancia de Hamming o la Distancia de Levenshtein son frecuentemente usadas.

Criterio de enlace[editar]

El criterio de enlace determina la distancia entre conjuntos de observaciones como una función de las distancias entre observaciones dos a dos. Algunos criterios de enlace entre dos conjuntos de observaciones A y B frecuentemente usados son:[4] [5]

Nombres Fórmula
Agrupamiento de máximo o completo enlace  \max \, \{\, d(a,b) : a \in A,\, b \in B \,\}.
Agrupamiento de mínimo o simple enlace  \min \, \{\, d(a,b) : a \in A,\, b \in B \,\}.
Agrupamiento de enlace media o promedio, o UPGMA  \frac{1}{|A| |B|} \sum_{a \in A }\sum_{ b \in B} d(a,b).
Agrupamiento de mínima energía   \frac {2}{nm}\sum_{i,j=1}^{n,m} \|a_i- b_j\|_2 - \frac {1}{n^2}\sum_{i,j=1}^{n} \|a_i-a_j\|_2 - \frac{1}{m^2}\sum_{i,j=1}^{m} \|b_i-b_j\|_2

Donde d es la métrica escogida. Otros criterios de enlace incluye:

  • La suma de todas las varianzas intra-grupo.
  • El decrecimiento en la varianza para los grupos que están siendo mezclados (criterio de Ward).
  • La probabilidad de que grupos candidatos se produzcan desde la misma función de distribución.(V-enlace)

Discusión[editar]

El agrupamiento jerárquico tiene la ventaja distintiva de que cualquier medida de distancia puede ser usada. De hecho, las observaciones de por si no son requeridas: todo lo que se usa es una matriz de distancia.

Ejemplo para agrupamiento aglomerativo[editar]

Por ejemplo, suponga que estos datos van a ser agrupados, y que la distancia euclidiana será la métrica de distancia.

Cortar el árbol a una altura determinada dará un grupo particionante de una precisión seleccionada. En este ejemplo, cortar después de la segunda fila dará como resultado los grupos {a} {b c} {d e} {f}. Cortar después de la tercera fila dará como resultado los grupos {a} {b c} {d e f}, el cual es un agrupamiento ‘tosco’, con un numero menor de grupos mayores.

Datos sin procesar

El dendrograma del agrupamiento jerárquico sería como este:

Representación tradicional

Este método construye la jerarquía desde los elementos individuales mediante progresivamente ir mezclando grupos. En nuestro ejemplo, tenemos seis elementos {a} {b} {c} {d} {e} y {f}. El primer paso es determinar cuales elementos mezclar en un grupo. Usualmente, queremos tomar lo dos elementos más cercanos, de acuerdo a una distancia escogida.

Opcionalmente, uno solo puede construir una matriz de distancias a este nivel, donde el numero en la i-ésima fila j-ésima columna es la distancia entre los i-ésimo y j-ésimo elementos. Entonces, a medida que el agrupamiento progresa, filas y columnas son mezcladas como también son mezclados los grupos y las distancias actualizadas. Esta es una forma común de implementar este tipo de agrupamiento y tiene el beneficio de almacenar las distancias entre grupos. Un algoritmo de agrupamiento aglomerativo simple es descrito en la página agrupamiento de enlace simple; puede ser fácilmente adaptado a diferentes tipos de enlace (ver abajo).

Suponga que hemos mezclado los dos elementos más cercanos b y c, ahora tenemos los siguientes grupos {a}, {b, c}, {d}, {e} y {f}}, y queremos mezclarlos más adelante. Para hacerlo, necesitamos tomar la distancia entre {a} y {b c}, y por tanto definir la distancia entre dos grupos.

Usualmente la distancia entre dos grupos \mathcal{A} and \mathcal{B} es una de los siguientes:

  • • La distancia máxima entre elementos de cada grupo (también llamada agrupamiento de enlace completo):
 \max \{\, d(x,y) : x \in \mathcal{A},\, y \in \mathcal{B}\,\}.
  • • La distancia mínima entre elementos de cada grupo (también llamada agrupamiento de enlace simple):
 \min \{\, d(x,y) : x \in \mathcal{A},\, y \in \mathcal{B} \,\}.
  • • La distancia media entre elementos de cada grupo (también llamada agrupamiento de enlace promedio, usado e.g. en UPGMA):
 {1 \over {|\mathcal{A}|\cdot|\mathcal{B}|}}\sum_{x \in \mathcal{A}}\sum_{ y \in \mathcal{B}} d(x,y).
  • La suma de todas las varianzas intra-grupo..
  • El aumento en la varianza de los grupos que están siendo mezclados (método de Ward).
  • La probabilidad de que grupos candidatos sean producidos desde la misma función de distribución (enlace-V).

Cada aglomeración ocurre a una mayor distancia entre grupos que la aglomeración anterior, y no puede decidir parar de agrupar ya sea cuando los grupos están muy lejos para ser mezclados (criterio de distancia) o cuando hay un suficientemente pequeño número de grupos (criterio de número).

Software[editar]

Libre[editar]

  • R tiene varias funciones de agrupamiento jerárquico: ver CRAN Task View: Cluster Analysis & Finite Mixture Models para más información.
  • Orange, una suite software gratis de minería de datos, módulo orngClustering para hacer scripts en Python, o análisis de grupo a través de visual programming.
  • hcluster es software Python, basado en NumPy, el cual soporta agrupamiento jerárquico y plotting.
  • Cluster 3.0 provee una agradable GUI para acceder a diferentes rutinas de agrupamiento y está disponible para Windows, Mac OS X, Linux, Unix. Ver: [1]
  • ELKI incluye múltiples algoritmos de agrupamiento jerárquico.
  • figue Un paquete JavaScript que implementa algunas funciones de agrupamiento aglomerativo (enlace simple, enlace completo, enlace promedio) y funciones para visualizar resultados de agrupamientos (e.g. dendrogramas) (Online demo).
  • MultiDendrograms Una aplicación open source en Java para agrupamiento jerárquico aglomerativo de grupos variables, con GUI.
  • CrimeStat implementa dos rutinas de agrupamiento jerárquico, una de vecino más cercano (Nnh) y una de riesgo-ajustado (Rnnh).
  • Complete C# DEMO implementado como proyecto de Visual Studio que incluye procesado real de archivos de texto, construcción de matrices documento-termino con filtrado de stopwords y stemming. El mismo sitio ofrece comparación con otros algoritmos.
  • HAC C# es una implementación de un algoritmo de agrupamiento aglomerativo que usa enlace-simple.

Comercial[editar]

Ver además[editar]

Notas[editar]

  1. R. Sibson (1973). «SLINK: an optimally efficient algorithm for the single-link cluster method». The Computer Journal (British Computer Society) 16 (1):  pp. 30–34. http://www.cs.gsu.edu/~wkim/index_files/papers/sibson.pdf. 
  2. D. Defays (1977). «An efficient algorithm for a complete link method». The Computer Journal (British Computer Society) 20 (4):  pp. 364–366. http://comjnl.oxfordjournals.org/content/20/4/364.abstract. 
  3. «The DISTANCE Procedure: Proximity Measures». SAS/STAT 9.2 Users Guide. SAS Institute. Consultado el 26-04-2009.
  4. «The CLUSTER Procedure: Clustering Methods». SAS/STAT 9.2 Users Guide. SAS Institute. Consultado el 26-04-2009.
  5. Székely, G. J. and Rizzo, M. L. (2005) Hierarchical clustering via Joint Between-Within Distances: Extending Ward's Minimum Variance Method, Journal of Classification 22, 151-183.

Referencias y otras lecturas[editar]