El método de Ward.

Criterio aplicado en el análisis de conglomerados jerárquico.

En estadística , el método de Ward es un criterio aplicado en el análisis de conglomerados jerárquico . El método de varianza mínima de Ward es un caso especial del enfoque de la función objetivo presentado originalmente por Joe H. Ward, Jr. ^[1] Ward sugirió un procedimiento de agrupamiento jerárquico aglomerativo general , donde el criterio para elegir el par de grupos a fusionar 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 de agrupación estándar están contenidos en esta clase tan general. Para ilustrar el procedimiento, Ward utilizó el ejemplo donde la función objetivo es el error de la suma de cuadrados , y este ejemplo se conoce como método de Ward o más precisamente método de varianza mínima de Ward .

El algoritmo de la cadena del vecino más cercano se puede utilizar para encontrar la misma agrupación definida por el método de Ward, en el tiempo proporcional al tamaño de la matriz de distancias de entrada y en el espacio lineal en el número de puntos que se agrupan.

El criterio de varianza mínima

El criterio de varianza mínima de Ward minimiza la varianza total dentro del grupo. Para implementar este método, en cada paso encuentre el par de conglomerados que conduzca a un aumento mínimo en la varianza total dentro del conglomerado después de la fusión. Este aumento es una distancia ponderada al cuadrado entre los centros de los grupos. En el paso inicial, todos los grupos son únicos (grupos que contienen un solo punto). Para aplicar un algoritmo recursivo bajo esta función objetivo , la distancia inicial entre objetos individuales debe ser (proporcional a) la distancia euclidiana al cuadrado .

Por lo tanto, las distancias de grupo iniciales en el método de varianza mínima de Ward se definen como la distancia euclidiana al cuadrado entre puntos:

${\displaystyle d_{ij}=d(\{X_{i}\},\{X_{j}\})={\|X_{i}-X_{j}\|^{2}}.}$

Nota: En el software que implementa el método de Ward, es importante comprobar si los argumentos de la función deben especificar distancias euclidianas o distancias euclidianas al cuadrado.

Algoritmos de Lance-Williams

El método de varianza mínima de Ward se puede definir e implementar de forma recursiva mediante un algoritmo de Lance-Williams. Los algoritmos de Lance-Williams son una familia infinita de algoritmos de agrupamiento jerárquico aglomerativo que están representados por una fórmula recursiva para actualizar las distancias de los grupos en cada paso (cada vez que se fusiona un par de grupos). En cada paso, es necesario optimizar la función objetivo (encontrar el par óptimo de grupos para fusionar). La fórmula recursiva simplifica encontrar el par óptimo.

Supongamos que los grupos y fueran los siguientes en fusionarse. En este punto se conocen todas las distancias actuales de los grupos por pares. La fórmula recursiva proporciona las distancias de los grupos actualizadas después de la fusión pendiente de los grupos y . Dejar ${\displaystyle C_{i}}$ ${\displaystyle C_{j}}$ ${\displaystyle C_{i}}$ ${\displaystyle C_{j}}$

• ${\displaystyle d_{ij}}$, , y sean las distancias por pares entre los grupos , , y , respectivamente, ${\displaystyle d_{ik}}$ ${\displaystyle d_{jk}}$ ${\displaystyle C_{i}}$ ${\displaystyle C_{j}}$ ${\displaystyle C_{k}}$
• ${\displaystyle d_{(ij)k}}$ser la distancia entre el nuevo grupo y . ${\displaystyle C_{i}\cup C_{j}}$ ${\displaystyle C_{k}}$

Un algoritmo pertenece a la familia Lance-Williams si la distancia del grupo actualizada se puede calcular de forma recursiva mediante ${\displaystyle d_{(ij)k}}$

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

donde y son parámetros, que pueden depender del tamaño de los conglomerados, que junto con la función de distancia del conglomerado determinan el algoritmo de agrupamiento. Varios algoritmos de agrupamiento estándar, como el enlace único , el enlace completo y el método de promedio de grupo, tienen una fórmula recursiva del tipo anterior. Varios autores proporcionan una tabla de parámetros para métodos estándar. ^{[2] [3] [4]} ${\displaystyle \alpha _{i},\alpha _{j},\beta ,}$ ${\displaystyle \gamma }$ ${\displaystyle d_{ij}}$

El método de varianza mínima de Ward se puede implementar mediante la fórmula de Lance-Williams. Para grupos disjuntos y con tamaños y respectivamente: ${\displaystyle C_{i},C_{j},}$ ${\displaystyle C_{k}}$ ${\displaystyle n_{i},n_{j},}$ ${\displaystyle n_{k}}$

${\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 tanto, el método de Ward puede implementarse como un algoritmo de Lance-Williams con

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

Variaciones

La popularidad del método de Ward ha dado lugar a variaciones del mismo. Por ejemplo, Ward _p introduce el uso de ponderaciones de características específicas de cada grupo, siguiendo la idea intuitiva de que las características podrían tener diferentes grados de relevancia en diferentes grupos. ^[5]

Referencias

1. Ward, JH, Jr. (1963), "Agrupación jerárquica para optimizar una función objetivo", Revista de la Asociación Estadounidense de Estadística , 58, 236–244.
2. Cormack, RM (1971), "Una revisión de la clasificación", Revista de la Royal Statistical Society , Serie A , 134(3), 321-367.
3. Gordon, AD (1999), Clasificación, segunda edición , Chapman y Hall, Boca Raton.
4. Milligan, GW (1979), "Algoritmos de agrupamiento jerárquico ultramétrico", Psychometrika , 44 (3), 343–346.
5. RC de Amorim (2015). "Relevancia de las características en la agrupación jerárquica de Ward utilizando la norma Lp" (PDF) . Revista de Clasificación . 32 (1): 46–62. doi :10.1007/s00357-015-9167-1. S2CID  18099326.

Otras lecturas

• Everitt, BS, Landau, S. y Leese, M. (2001), Cluster Analysis, cuarta edición , Oxford University Press, Inc., Nueva York; Arnold, Londres. ISBN 0340761199 
• Hartigan, JA (1975), Algoritmos de agrupación , Nueva York: Wiley.
• Jain, AK y Dubes, RC (1988), Algoritmos para agrupar datos , Nueva Jersey: Prentice-Hall.
• Kaufman, L. y Rousseeuw, PJ (1990), Encontrar grupos en datos: una introducción al análisis de conglomerados , Nueva York: Wiley.