Método de Ward

Em estatística , o método de Ward é um critério aplicado na análise hierárquica de cluster . O método de variância mínima de Ward é um caso especial da abordagem da função objetivo originalmente apresentada por Joe H. Ward, Jr. [1] Ward sugeriu um procedimento geral de agrupamento hierárquico aglomerativo , onde o critério para escolher o par de clusters a serem mesclados em cada etapa é com base no valor ideal de uma função objetivo. Esta função objetivo poderia ser “qualquer função que reflita o propósito do investigador”. Muitos dos procedimentos padrão de clustering estão contidos nesta classe muito geral. Para ilustrar o procedimento, Ward usou o exemplo onde a função objetivo é a soma dos quadrados dos erros , e este exemplo é conhecido como método de Ward ou mais precisamente método de variância mínima de Ward .

O algoritmo de cadeia de vizinhos mais próximos pode ser usado para encontrar o mesmo agrupamento definido pelo método de Ward, em tempo proporcional ao tamanho da matriz de distância de entrada e espaço linear no número de pontos sendo agrupados.

O critério de variância mínima

O critério de variância mínima de Ward minimiza a variância total dentro do cluster. Para implementar este método, em cada etapa encontre o par de clusters que leva ao aumento mínimo na variância total dentro do cluster após a fusão. Este aumento é uma distância quadrada ponderada entre os centros do cluster. Na etapa inicial, todos os clusters são singletons (clusters contendo um único ponto). Para aplicar um algoritmo recursivo sob esta função objetivo , a distância inicial entre objetos individuais deve ser (proporcional ao) quadrado da distância euclidiana .

As distâncias iniciais do cluster no método de variância mínima de Ward são, portanto, definidas como a distância euclidiana quadrada entre os pontos:

Nota: Em software que implementa o método de Ward, é importante verificar se os argumentos da função devem especificar distâncias euclidianas ou distâncias euclidianas quadradas.

Algoritmos Lance-Williams

O método de variância mínima de Ward pode ser definido e implementado recursivamente por um algoritmo Lance-Williams. Os algoritmos Lance-Williams são uma família infinita de algoritmos de agrupamento hierárquico aglomerativo que são representados por uma fórmula recursiva para atualizar as distâncias dos clusters em cada etapa (cada vez que um par de clusters é mesclado). Em cada etapa, é necessário otimizar a função objetivo (encontrar o par ideal de clusters para mesclar). A fórmula recursiva simplifica encontrar o par ideal.

Suponha que os clusters e sejam os próximos a serem mesclados. Neste ponto, todas as distâncias atuais dos clusters em pares são conhecidas. A fórmula recursiva fornece as distâncias atualizadas dos clusters após a fusão pendente dos clusters e . Deixar

  • , , e sejam as distâncias aos pares entre os clusters , , e , respectivamente,
  • seja a distância entre o novo cluster e .

Um algoritmo pertence à família Lance-Williams se a distância atualizada do cluster puder ser calculada recursivamente por

onde e são parâmetros, que podem depender do tamanho do cluster, que juntamente com a função de distância do cluster determinam o algoritmo de agrupamento. Vários algoritmos de agrupamento padrão, como ligação única , ligação completa e método de média de grupo, possuem uma fórmula recursiva do tipo acima. Uma tabela de parâmetros para métodos padrão é fornecida por vários autores. [2] [3] [4]

O método de variância mínima de Ward pode ser implementado pela fórmula de Lance – Williams. Para clusters disjuntos e com tamanhos e respectivamente:

Portanto, o método de Ward pode ser implementado como um algoritmo Lance-Williams com

Variações

A popularidade do método Ward levou a variações dele. Por exemplo, Ward p introduz o uso de pesos de recursos específicos de cluster, seguindo a ideia intuitiva de que os recursos podem ter diferentes graus de relevância em diferentes clusters. [5]

Referências

  1. ^ Ward, JH, Jr. (1963), "Agrupamento hierárquico para otimizar uma função objetiva", Journal of the American Statistical Association , 58, 236–244.
  2. ^ Cormack, RM (1971), "A Review of Classification", Journal of the Royal Statistical Society , Série A , 134(3), 321-367.
  3. ^ Gordon, AD (1999), Classificação, 2ª Edição , Chapman e Hall, Boca Raton.
  4. ^ Milligan, GW (1979), "Algoritmos de agrupamento hierárquico ultramétrico", Psychometrika , 44(3), 343–346.
  5. ^ RC de Amorim (2015). "Relevância de recursos no cluster hierárquico de Ward usando a norma Lp" (PDF) . Diário de Classificação . 32 (1): 46–62. doi :10.1007/s00357-015-9167-1. S2CID18099326  .

Leitura adicional

  • Everitt, BS, Landau, S. e Leese, M. (2001), Cluster Analysis, 4ª Edição , Oxford University Press, Inc., Nova York; Arnold, Londres. ISBN 0340761199 
  • Hartigan, JA (1975), Algoritmos de Cluster , Nova York: Wiley.
  • Jain, AK e Dubes, RC (1988), Algoritmos para agrupamento de dados , Nova Jersey: Prentice – Hall.
  • Kaufman, L. e Rousseeuw, PJ (1990), Encontrando grupos em dados: uma introdução à análise de cluster , Nova York: Wiley.
Obtido em "https://en.wikipedia.org/w/index.php?title=Ward%27s_method&oldid=1192319269"