El método de Ward

Criterio aplicado en el análisis de conglomerados jerárquicos

En estadística , el método de Ward es un criterio aplicado en el análisis de conglomerados jerárquicos . 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 general de agrupamiento jerárquico aglomerativo , donde el criterio para elegir el par de conglomerados que se fusionarán 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 de agrupamiento estándar están contenidos en esta clase muy general. Para ilustrar el procedimiento, Ward utilizó el ejemplo donde la función objetivo es la suma de cuadrados del error , y este ejemplo se conoce como el método de Ward o, más precisamente, el método de varianza mínima de Ward .

El algoritmo de cadena del vecino más cercano se puede utilizar para encontrar la misma agrupación definida por el método de Ward, en un tiempo proporcional al tamaño de la matriz de distancia de entrada y en un 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 grupos que conduce al aumento mínimo en la varianza total dentro del grupo después de la fusión. Este aumento es una distancia al cuadrado ponderada entre los centros de los grupos. En el paso inicial, todos los grupos son singletons (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 agrupamiento 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 verificar 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 se representan mediante una fórmula recursiva para actualizar las distancias de los clústeres en cada paso (cada vez que se fusiona un par de clústeres). En cada paso, es necesario optimizar la función objetivo (encontrar el par óptimo de clústeres para fusionar). La fórmula recursiva simplifica la búsqueda del par óptimo.

Supongamos que los clústeres y se fusionarán a continuación. En este punto, se conocen todas las distancias de clústeres por pares actuales. La fórmula recursiva proporciona las distancias de clústeres actualizadas después de la fusión pendiente de los clústeres y . Sea ${\displaystyle C_{i}}$ ${\displaystyle C_{j}}$ ${\displaystyle C_{i}}$ ${\displaystyle C_{j}}$

• ${\displaystyle d_{ij}}$, , y sean las distancias por pares entre los clústeres , , y , respectivamente, ${\displaystyle d_{ik}}$ ${\displaystyle d_{jk}}$ ${\displaystyle C_{i}}$ ${\displaystyle C_{j}}$ ${\displaystyle C_{k}}$
• ${\displaystyle d_{(ij)k}}$sea ​​la distancia entre el nuevo cluster 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 de los tamaños de los clústeres, que junto con la función de distancia de los clústeres determinan el algoritmo de agrupamiento. Varios algoritmos de agrupamiento estándar, como el de ligamiento simple , el de ligamiento completo y el de promedio de grupo, tienen una fórmula recursiva del tipo anterior. Varios autores proporcionan una tabla de parámetros para los 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 conglomerados 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 lo tanto, el método de Ward se puede implementar 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, el método de Ward _p introduce el uso de ponderaciones de características específicas de cada conglomerado, siguiendo la idea intuitiva de que las características podrían tener distintos grados de relevancia en distintos conglomerados. ^[5]

Referencias

1. Ward, JH, Jr. (1963), "Agrupamiento jerárquico para optimizar una función objetivo", Journal of the American Statistical Association , 58, 236–244.
2. Cormack, RM (1971), "Una revisión de la clasificación", Journal of the Royal Statistical Society , Serie A , 134(3), 321-367.
3. Gordon, AD (1999), Clasificación, 2.ª 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.

Lectura adicional

• Everitt, BS, Landau, S. y Leese, M. (2001), Cluster Analysis, 4.ª edición , Oxford University Press, Inc., Nueva York; Arnold, Londres. ISBN 0340761199 
• Hartigan, JA (1975), Algoritmos de agrupamiento , 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.