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 función objetivo presentado originalmente por Joe H. Ward, Jr. [1] Ward sugirió un agrupamiento jerárquico aglomerativo generalprocedimiento, donde el criterio para elegir el par de conglomerados a fusionar 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 agrupación en clústeres estándar están incluidos en esta clase muy general. Para ilustrar el procedimiento, Ward utilizó el ejemplo en el que la función objetivo es la suma de cuadrados del error , 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 el mismo agrupamiento definido por el método de Ward, en el tiempo proporcional al tamaño de la matriz de distancia de entrada y 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 conglomerado. Para implementar este método, en cada paso encuentre el par de grupos que conduzca a un 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 conglomerados. 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 los conglomerados iniciales en el método de varianza mínima de Ward se definen como la distancia euclidiana al cuadrado entre puntos:
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 cuadradas.
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 clústeres para fusionar). La fórmula recursiva simplifica la búsqueda del par óptimo.
Supongamos que los clusters y fueron 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 conglomerados actualizadas después de la fusión pendiente de los conglomerados. y . Dejar
- , , y ser las distancias por pares entre grupos , , y , respectivamente,
- ser la distancia entre el nuevo clúster y .
Un algoritmo pertenece a la familia Lance-Williams si la distancia del clúster actualizada se puede calcular de forma recursiva por
dónde y son parámetros, que pueden depender del tamaño de los conglomerados, que junto con la función de distancia del conglomerado determinar 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]
El método de varianza mínima de Ward se puede implementar mediante la fórmula de Lance-Williams. Para clústeres disjuntos y con tallas y respectivamente:
Por lo tanto, el método de Ward se puede implementar como un algoritmo de Lance-Williams con
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 clústeres, siguiendo la idea intuitiva de que las características podrían tener diferentes grados de relevancia en diferentes clústeres. [5]
Referencias
- ^ Ward, JH, Jr. (1963), "Agrupación jerárquica para optimizar una función objetiva", Revista de la Asociación Estadounidense de Estadística , 58, 236–244.
- ^ Cormack, RM (1971), "Una revisión de la clasificación", Revista de la Royal Statistical Society , Serie A , 134 (3), 321-367.
- ^ Gordon, AD (1999), Clasificación, 2ª edición , Chapman y Hall, Boca Raton.
- ^ Milligan, GW (1979), "Algoritmos de agrupamiento jerárquico ultramétrico", Psychometrika , 44 (3), 343–346.
- ^ RC de Amorim (2015). "Relevancia de la función en la agrupación jerárquica de Ward mediante 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, 4ª edición , Oxford University Press, Inc., Nueva York; Arnold, Londres. ISBN 0340761199
- Hartigan, JA (1975), Clustering Algorithms , Nueva York: Wiley.
- Jain, AK y Dubes, RC (1988), Algoritmos para agrupar datos , Nueva Jersey: Prentice – Hall.
- Kaufman, L. y Rousseeuw, PJ (1990), Finding Groups in Data: An Introduction to Cluster Analysis , Nueva York: Wiley.