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.​ 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 la suma de los cuadrados de error 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 la varianza total dentro de los clúster. Es decir, minimiza la suma, sobre todos los clusters, de la varianza dentro del cluster. En cada paso del algoritmo se debe encontrar el par de clúster que llevan al incremento mínimo de la varianza total dentro de los clúster después de mezclarlos. El par de clúster que al unirse hagan mínima la varianza total dentro de los clúster, son mezclados. 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:

$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 $C_{i}$ y $C_{j}$ son los próximos a mezclar. En este momento, todas las distancias entre cualquier par de clúster son conocidas. La forma recursiva brinda las distancias de los clúster actualizadas siguiendo las mezclas pendientes de los 2 clúster $C_{i}$ y $C_{j}$. Sea

• $d_{ij}$, $d_{ik}$, y $d_{jk}$ las distancia de a pares 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.​​​

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 _{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.$

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