Método de Ward

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 del enfoque de función objetivo presentado originalmente por Joe H. Ward, Jr.^[1]​ el cual se trata de un procedimiento general donde el criterio para la elección del par de clusters a mezclar en cada paso se basa 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 están contenidos dentro de esta clase general. Para ilustrar el procedimiento, Ward usó el ejemplo donde la función objetivo es el error de la suma de los cuadrados o varianza, 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

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 Euclidiana.

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:

${\displaystyle 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 euclidianas 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

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 ${\displaystyle C_{i}}$  y ${\displaystyle 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 ${\displaystyle C_{i}}$  y ${\displaystyle C_{j}}$ . Sea

• ${\displaystyle d_{ij}}$ , ${\displaystyle d_{ik}}$ , y ${\displaystyle d_{jk}}$  sean los pares de distancia entre los clúster ${\displaystyle C_{i}}$ , ${\displaystyle C_{j}}$ , y ${\displaystyle C_{k}}$ , respectivamente,
• ${\displaystyle d_{(ij)k}}$  es la distancia entre el nuevo clúster creado ${\displaystyle C_{i}\cup C_{j}}$  y ${\displaystyle C_{k}}$ .

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

${\displaystyle d_{(ij)k}=\alpha _{i}d_{ik}+\alpha _{j}d_{jk}+\beta d_{ij}+\gamma |d_{ik}-d_{jk}|,}$ 

Donde ${\displaystyle \alpha _{i},\alpha _{j},\beta ,}$  y ${\displaystyle \gamma }$  son parámetros, que pueden depender del tamaño del clúster, junto con la función de distancia ${\displaystyle 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 ${\displaystyle C_{i},C_{j},}$  y ${\displaystyle C_{k}}$  con tamaño ${\displaystyle n_{i},n_{j},}$  y ${\displaystyle n_{k}}$  respectivamente:

${\displaystyle 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

${\displaystyle \alpha _{i}={\frac {n_{i}+n_{k}}{n_{i}+n_{j}+n_{k}}},\qquad \beta ={\frac {-n_{k}}{n_{i}+n_{j}+n_{k}}},\qquad \gamma =0.}$ 

Referencias

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

• 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.

•   Datos: Q3333621