IMAGE0 (2)

Rozdział 6

Metody hierarchiczne

6.1. Podstawowe własności

Historycznie biorąc, metody hierarchiczne były pierwszymi, jakie powstały w ramach taksonomii numerycznej. Zostały wymyślone- przez biologów tworzących hierarchię gromad, rzędów, rodzin, rodzajów .oraz gatunków zwierząt. Na szczycie takiej struktury znajduje się klasa najbardziej ogólna, zawierająca wszystkie obiekty, a na najniższym poziomie — pojedyncze obiekty, tj. klasy najbardziej szczegółowe.

Jak już wspomniano w rozdziale 2, w ramach taksonometrii powstały dziesiątki algorytmów hierarchicznych. Okazuje się, że również w ramach taksonomii symbolicznej są one najbardziej liczną grupą (tablica 4.1).    .

W zależności od sposobu konstruowania hierachii klas można wyodrębnić:

■ — metody agłomeracyjne,

— metody podziałowe (deglomeracyjne).

W ramach pierwszej grupy metod każdy obiekt jest początkowo traktowany jako oddzielna, jednoelementowa klasa. Klasy te następnie stopniowo łączy się aż do chwili, gdy wszystkie obiekty znajdą się w jednym zbiorze. Rozważany proces odbywa się w oparciu o pewną miarę podobieństwa (odległości), za pomocą której można wybrać te klasy, które w następnym kroku zostaną'połączone.

Przebieg grupowania obiektów w ramach metod, aglomeracyjnych odbywa się w następujących krokach:

1.    Utwórz n klas zawierających pojedyncze obiekty.

2.    Oblicz wartość pewnej miary podobieństwa (odległości) dla wszystkichpar klas.

3.    Połącz dwie klasy najbardziej podobne.

4.    Jeśli wszystkie obiekty należą do jednej klasy, to zakończ pracę. W przeciwnym przypadku przejdź do kroku 2.

Graficzną ilustracją tego procesu jest najczęściej dendrogram, będący binarnym drzewem klas.

(oj, 02, 03.04.05. 06.07. 0*1

Proces klasyfikacji w ramach metod podziałowych przebiega w odwrotnym kierunku. Zbiór wszystkich obiektów dzieli się w kolejnych krokach na podzbiory aż do uzyskania zbioru klas zawierających pojedyncze obiekty. Problem określenia kryterium podziału zbioru obiektów na podzbiory jest znacznie trudniejszy niż przy ich łączeniu. Należy bowiem rozważyć wszystkie możliwe podziały i wybrać najlepszy ze względu na przyjęte kryterium. Ponieważ jednak w praktyce odbywa się to w oparciu o wartości pojedynczych cech klasyfikowanych obiektów, wystarczy porównać m różnych podziałów (m — liczba cech).

Postępowanie w ramach metod podziałowych można zapisać w postaci algorytmu:

1.    Utwórz jedną klasę (zbiór) zawierającą wszystkie obiekty.

2.    Porównaj wartości funkcji kryterium w przypadku wszystkich możliwych podziałów klasy na dwa lub więcej podzbiorów.

. 3. Wybierz najlepszy podział i zrealizuj go.

4. Jeśli każdy z obiektów znajduje się w oddzielnej klasie, zakończ pracę; w przeciwnym przypadku wykonuj rekurencyjnie kroki 2-4 dla każdej .klasy.

Algorytmy podziałowe., są -bardzo rzadko spotykane w taksonomii

101