38446 P3200185

Ml 4 Analiza skupień

4.8. Wybór liczby grup

Warnym elementem procesu grupowania jest określenie lic/.by skupień. Jest lo Sou K in cel i sens grupowania. Określanie liczby grup pojaw ia się w grupowaniu zarówno hierarchiczm m. jak i podziałowym, jakkolwiek nie są to zagadnienia w pełni identyczne, lest łatwo zadecydować o liczbie grup, ale zwykle nie chodzi o decyzję całkowicie arbitralną, lecz optymalną z punktu widzenia rozsądnego kryterium. I choć powiada się, że badacz, dostatecznie dobrze znający badane zagadnienie wie najlepiej czy dane grupowanie jest sensowne z punktu widzenia celu badania, to jednak reguły , które by wsparły taką decyzję są pożądane.

W odniesieniu do grupowania hierarchicznego chodzi o najwłaściwszą liczbę grup, czyli podział, jaki wynika z hierarchii, który byłby w jakimś sensie optymalny. Każdy etap hierarchicznego grupowania wyróżnia określoną liczbę skupień, która zmniejsza się sekwencyjnie w miarę wzrostu poziomu hierarchii. Badacz nie musi byc zainteresowany pełną hierarchią, lecz tylko jednym lub dwoma podziałami, które można otrzymać z takiego sposobu grupowania. Chodzi więc o wypracowanie jakiejś reguły przerywania grupowania (ang. stopping rule), która będzie pomocna w wyborze jednego z wielu podziałów.

Wśród możliwych podejść w tym względzie najprostsza jest metoda oceny dendrogramu, polegająca na wskazaniu dużej różnicy między sąsiadującymi poziomami łączenia. Jeżeli taka zmiana poziomów przebiega między n — k a n — k — 1 grupami, to rozwiązaniem będzie n — k grup.

W tym samym kierunku zmierza też propozycja, którą przedstawił Timm (2002). Polega ona na analizie wykresu odległości, na których następują kolejne łączenia w procesie grupowania hierarchicznego względem liczby grup w kolejnych partycjach hierarchii. Linia łamana łącząca kolejne punkty o współrzędnych (n — k, \\ gdzie n — kdla k = 0,1,..., n — 1 oznacza liczbę skupień (liczna obiektów n minus liczba kroków k), zaś !\ jest poziomem łączenia, w wyniku którego powstaje n — kskupień (zob. rysunek 4.17). Kształt kolanka na wykresie może stanowić wskazanie liczby skupień. Rysunek 4.17 ujawnia jedno kolanko dla odciętej równej 3 (ostre załamanie krzywej), a zatem wskazuje na istnienie trzech skupień.

Ponieważ jest to metoda subiektywna, prowadząca nieraz do wyboru tego, czego oczekujemy, zasugerowano pewne inne propozycje. Bardziej znaną spośród „obiektywnych’' propozycji jest sugestia R. Mojeny ^H\ oparta na względnej wysokości różnych poziomów łączenia (h). Polega ona na wyborze liczby grup odpowiadającej temu poziomowi dendrogramu (etapowi łączenia), dla którego spełniona jest nierówność ¹¹⁶ R. Mo jena HieroKhicol gmuping methods and stopping rules: an cvaluation, Computer Journal. 20, i 977 Zoh Kwrift i Dunn (1991). Everift (1993).

h„ __k__x > hbar 4- ś * s

A 140

gdzie h, ,h₂..,h_B__l - poziomy łączenia odpowiadające etapem*; z n.— V... .1 skupieniami¹¹ ,

h - średnia z wartości z h ,h_;.....h_r ,

s_h - odchylenie standardowe (nieobciążone) w zbiorze wartości H . h .....h_r_..

a - stała.

Jeśli operujemy macierzą podobieństwa, a nie macierzą odległości to ze względu na to, że h, > h, >... > h, _ . należy w nierówność ¹4 140 zmienić zwrot

< i — a • s_fc    (4.141)

Mojena twierdzi, że stała a powinna przy miowac wartości ;■ przedziału od 2,75 do 3,50. jeżeli nie ma wartości h spełniające] merowno^c 4 i 4 to o znać za to, że obiekty tworzą jedną grupę Nie ma jednak pełnei nasnosci w kwestii siało a w regule Mojeny, skoro inni badacze sugerutą ze wartość ta p« winna wynosić a = 1,25. Zbyt wysokie wartości a mogą spowodować ze rozroznientc grup będzie niemożliwe lub też mogą doprowadzić do podziału w ktorvm icdna grupa jest bardzo liczna, zaś pozostałe nieliczne obiekty będą oddzielm m icdnoeiemen to wy mi skupieniami.

#.4

10-1

0 ► o    2    3    *    5    6    7 n~ą

8

6 2

Rysunek 4.17. Krzywa poziomów łączcnu względem 1ic/b\ skupień v grupowaniu hierarchicznym (metoda najdalszego sąsiada n ~ . k ~ 0.1. n — 1 7 przykładu 4 4)

Omawiając metody grupowania podziałowego zakładano żc lic/ba grup. na które zamierza się rozdzielić zbiór obiektów test 7 gon określona ¹ zwykle przez badacza). I.iczba grup jest jednak ważnym problemem dla większości zastosowań optymalizacyjnych metod grupowania lest to problem ważniejszy ni/ w prz\ padku grupowania hierarchicznego, w którym wszystkie partycje odpowiadaiąc\

"⁷ ^ u ważmy, że poziomy łączenia są poszczególnymi, różniącymi się odległościami kotem tycznymi, przy czym h. = min{d, ) * c„ dla dwóch pierwszych łączących się obiektów (w pierw szym kroku).