Metoda Warda

W statystyce metoda Warda jest kryterium stosowanym w hierarchicznej analizie skupień . Metoda minimalnej wariancji Warda jest szczególnym przypadkiem podejścia opartego na funkcji celu, pierwotnie przedstawionego przez Joe H. Warda, Jr. Ward zasugerował ogólne aglomeracyjne hierarchiczne grupowanie procedura, w której kryterium wyboru pary skupień do połączenia na każdym kroku opiera się na optymalnej wartości funkcji celu. Ta funkcja celu może być „dowolną funkcją, która odzwierciedla cel badacza”. Wiele standardowych procedur grupowania jest zawartych w tej bardzo ogólnej klasie. Aby zilustrować procedurę, Ward posłużył się przykładem, w którym funkcja celu jest sumą błędów kwadratów , a ten przykład jest znany jako metoda Warda lub dokładniej metoda minimalnej wariancji Warda .

Algorytm łańcucha najbliższego sąsiada może być użyty do znalezienia tego samego skupienia zdefiniowanego metodą Warda, w czasie proporcjonalnym do rozmiaru wejściowej macierzy odległości i przestrzeni liniowej w liczbie grupowanych punktów.

Kryterium minimalnej wariancji

Kryterium minimalnej wariancji Warda minimalizuje całkowitą wariancję wewnątrz klastra. Aby zaimplementować tę metodę, na każdym kroku znajdź parę skupień, która po połączeniu prowadzi do minimalnego wzrostu całkowitej wariancji wewnątrz skupień. Ten wzrost jest ważoną kwadratową odległością między centrami klastrów. Na początkowym etapie wszystkie klastry są singletonami (klastrami zawierającymi pojedynczy punkt). Aby zastosować algorytm rekurencyjny w ramach tej funkcji celu , początkowa odległość między poszczególnymi obiektami musi być (proporcjonalna do) kwadratu odległości euklidesowej .

Początkowe odległości klastrów w metodzie minimalnej wariancji Warda są zatem zdefiniowane jako kwadrat odległości euklidesowej między punktami:

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

Uwaga: W oprogramowaniu implementującym metodę Warda ważne jest sprawdzenie, czy argumenty funkcji powinny określać odległości euklidesowe, czy kwadraty odległości euklidesowych.

Algorytmy Lance'a-Williamsa

Metodę minimalnej wariancji Warda można zdefiniować i zaimplementować rekurencyjnie za pomocą algorytmu Lance-Williamsa. Algorytmy Lance'a-Williamsa to nieskończona rodzina aglomeracyjnych, hierarchicznych algorytmów grupowania, które są reprezentowane przez rekurencyjną formułę aktualizacji odległości klastrów na każdym kroku (za każdym razem, gdy para klastrów jest łączona). Na każdym kroku konieczna jest optymalizacja funkcji celu (znalezienie optymalnej pary skupień do połączenia). Formuła rekurencyjna upraszcza znalezienie optymalnej pary.

Załóżmy, że klastry $jot {\ displaystyle$ do $}}$ miały być następnie połączone. W tym momencie znane są wszystkie obecne odległości klastrów parami. odległości $}$ po oczekującym połączeniu klastrów i ${ \ displaystyle C_ {j$ Pozwalać

• ${\ Displaystyle d_ {ij}}$ , ${\ Displaystyle d_ {ik}}$ i ${\ Displaystyle d_ {jk}}$ być parami odległości między skupieniami ${\ displaystyle C_ {i }}$$j}}$ odpowiednio do jot {\ Displaystyle C_ $k}}$ i do
• ${\ Displaystyle d_ {(ij) k}}$ będzie odległością między nowym klastrem ${\ Displaystyle C_ {i} \ kubek C_ {j}}$ i do $\ Displaystyle C_ {k}}$ .

Algorytm należy do rodziny Lance-Williams, jeśli zaktualizowaną odległość klastra ${\ Displaystyle d_ {(ij) k}}$ obliczyć rekurencyjnie przez re

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

gdzie ${\ Displaystyle \ alfa _ {i}, \ alfa _ {j}, \ beta,}$$i$ są , które mogą zależeć od rozmiarów klastrów, które razem za pomocą funkcji odległości $klastra$ algorytm Kilka standardowych algorytmów grupowania, takich jak pojedyncze powiązanie , pełne powiązanie , a metoda średniej grupowej ma formułę rekurencyjną powyższego typu. Kilku autorów podaje tabelę parametrów dla metod standardowych.

Metodę minimalnej wariancji Warda można zaimplementować za pomocą wzoru Lance-Williamsa. Dla klastrów $i$$n_$$o$ do n odpowiednio i ${\ displaystyle n_ {k}}$

${\ Displaystyle d (C_ {i} \ kubek 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}).}$

Stąd metodę Warda można zaimplementować jako algorytm Lance-Williamsa z

${\ Displaystyle \ alfa _ {i} = {\ Frac {n_ {i} + n_ {k}} {n_ {i} + n_ {j} + n_ {k}}}, \ qquad \ alfa _ {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.}$

Wariacje

Popularność metody Warda doprowadziła do jej odmian. Na przykład Ward _p wprowadza stosowanie wag funkcji specyficznych dla klastrów, zgodnie z intuicyjną ideą, że cechy mogą mieć różne stopnie istotności w różnych klastrach.

Dalsza lektura

•   Everitt, BS, Landau, S. and Leese, M. (2001), Cluster Analysis, 4th Edition , Oxford University Press, Inc., Nowy Jork; Arnold, Londyn. ISBN 0340761199
• Hartigan, JA (1975), Algorytmy klastrowania , Nowy Jork: Wiley.
• Jain, AK i Dubes, RC (1988), Algorytmy grupowania danych , New Jersey: Prentice – Hall.
• Kaufman, L. i Rousseeuw, PJ (1990), Znajdowanie grup w danych: wprowadzenie do analizy skupień , Nowy Jork: Wiley.