Método de Ward

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

En estadísticas, el Método de Ward es un criterio aplicado al Análisis de clúster jerárquico. El método de Ward de varianza mínima es un caso especial de la función objetivo de aproximación presentado originalmente por Joe H. Ward, Jr.[1] Ward sugirió un procedimiento general de aglomeración de clúster jerárquico donde el criterio para la elección del par de cluster a mezclar en cada paso es basado en el valor óptimo de una función objetivo. Esta función objetivo podría ser "cualquier función que refleje el propósito del investigador". Muchos de los procedimientos estándares de agrupamiento son contenido en esta clase general. Para ilustar el procedimiento, Ward usó el ejemplo donde la función objetivo es el error de la suma de los cuadrados, y este ejemplo es conocido por Método de Ward o más preciso como el método de varianza mínima de Ward.

Criterio de Varianza Mínima[editar]

Criterio de Varianza Mínima de Ward minimiza el total dentro de la varianza del clúster. En cada paso el par de clúster con distancia mínima entre ellos son mezclados. Para implementar este método , en cada paso se debe encontrar el par de clúster que llevan al incremento mínimo del total de la varianza del clúster después de mezclarlos. Este incremento es la distancia cuadrada con un peso asignado entre los centros de los clúster. En el paso inicial , todos los clúster contienen un punto único (solitario). Para aplicar algoritmo recursivo bajo esta función objetivo, la distancia inicial entre los objetos individuales debe ser proporcional al cuadrado de la Distancia Euclideana.

Las distancias iniciales del clúster en el método de varianza mínima de Ward se definen como el cuadrado de la distancia euclidiana entre puntos:

d_{ij}=d(\{X_i\}, \{X_j\}) = { \|X_i - X_j\|^2}.

Nota: En las implementaciones de software del método de Ward es importante chequear el argumento de la función especificando las distancias euclidianas o sus cuadrados. En la Función R hclust, es necesario pasar el cuadrado de las distancias euclideanas para obtener el método de varianza mínima de Ward. Para otros método de ‘hclust’ (sencillos, completos etc.) se requiere la distancia Euclidiana.

Algoritmo de Lance–Williams[editar]

El método de varianza mínima de Ward puede ser definido e implementado recursivamente por el algoritmo de Lance-Williams.[2] El algoritmo de Lance-Williams consiste en una familia infinita de aglomeración de algoritmos jerárquicos de clúster, los cuales son representados mediante una forma recursiva para actualizar la distancia de clúster en cada paso (cada vez se mezcla un par de clúster).En cada paso es necesario la optimización de la función objetivo (encontrar el par de clúster óptimo a mezclar). La fórmula recursiva simplifica la búsqueda del par óptimo.

Suponiendo que el clúster C_i y C_j son los próximos a mezclar. En este momento todas las distancias entre cualquier par de clúster es conocida. La forma recursiva brinda las distancias de los clúster actualizada siguiendo las mezclas pendientes de los 2 clúster C_i y C_j. Sea

  • d_{ij}, d_{ik}, y d_{jk} sean los pares de distancia entre los clúster C_i, C_j, y C_k, respectivamente,
  • d_{(ij)k} es la distancia entre el nuevo clúster creado C_i \cup C_j y C_k.

Un algoritmo pertenece a la familia Lance-Williams si la actualización de la distancia del clúster d_{(ij)k} puede ser computada recursivamente por la fórmula



 d_{(ij)k} = \alpha_i d_{ik} + \alpha_j d_{jk} + \beta d_{ij} +  \gamma |d_{ik} - d_{jk}|,

Donde \alpha_i, \alpha_j, \beta, y \gamma son parámetros, que pueden depender del tamaño del clúster , junto con la función de distancia d_{ij} determinando el algoritmo de agrupamiento. Varios estándares de algoritmos de agrupamiento vínculo simple, vínculo completo , y un grupo de métodos de promedio tienen una fórmula recursiva como la de arriba. Una tabla de parámetros para los métodos estándares es dada por varios autores.[2] [3] [4]

El método de varianza mínima de Ward puede ser implementado por la fórmula de Lance–Williams. Para clúster disjuntos C_i, C_j, y C_k con tamaño n_i, n_j, y n_k respectivamente:


d(C_i \cup C_j, C_k) = 
 \frac{n_i+n_k}{n_i+n_j+n_k}\;d(C_i,C_k) +
 \frac{n_j+n_k}{n_i+n_j+n_k}\;d(C_j,C_k) -
 \frac{n_k}{n_i+n_j+n_k}\;d(C_i,C_j).

Por lo tanto el método de Ward puede ser implementado como el algoritmo de Lance-Williams


 \alpha_l = \frac{n_l+n_k}{n_i+n_j+n_k}, \qquad
 \beta =\frac{-n_k}{n_i+n_j+n_k}, \qquad
 \gamma = 0.

Referencias[editar]

  1. Ward, J. H., Jr. (1963), "Hierarchical Grouping to Optimize an Objective Function", Journal of the American Statistical Association, 58, 236–244.
  2. Cormack, R. M. (1971), "A Review of Classification", Journal of the Royal Statistical Society, Series A, 134(3), 321-367.
  3. Gordon, A. D. (1999), Classification, 2nd Edition, Chapman and Hall, Boca Raton.
  4. Milligan, G. W. (1979), "Ultrametric Hierarchical Clustering Algorithms", Psychometrika, 44(3), 343–346.

Otras Lecturas[editar]

  • Everitt, B. S., Landau, S. and Leese, M. (2001), Cluster Analysis, 4th Edition, Oxford University Press, Inc., New York; Arnold, London. ISBN 0-340-76119-9
  • Hartigan, J. A. (1975), Clustering Algorithms, New York: Wiley.
  • Jain, A. K. and Dubes, R. C. (1988), Algorithms for Clustering Data, New Jersey: Prentice–Hall.
  • Kaufman, L. and Rousseeuw, P. J. (1990), Finding Groups in Data: An Introduction to Cluster Analysis, New York: Wiley.