IMAGE9 (2)

Kryterium stopu jest wyznaczane w postaci maksymalnej liczby iteracji lub wartości progowej stosowanej miary jakości podziału. Proces klasyfikacji jest także przerywany, gdy w dwóch kolejnych iteracjach nie nastąpiła zmiana struktury.

Do najbardziej znanych optymalizacyjnych metod taksonometrycznych należą| metoda AT-średnich, metoda Af-centroidów, metoda Wisharta, metoda Thorndike’a.

Z kolei wśród hierarchicznych metod taksonomicznych można wyróżnić:

•    Metody aglomemcyjne, polegające na sukcesywnym łączeniu skupieii (zakłada się, że początkowo każdy obiekt tworzy oddzielną klasę).

•    Metody podziałowe, w ramach których początkowy zbiór obiektów (jedno skupienie) jest dzielony kolejno na dwie części aż do momentu, gdy każdy obiekt znajdzie się w oddzielnej klasie.

Najbardziej.populame są hierarchiczne metody aglomeracyjne, chociaż mogą być stosowane jedynie do stosunkowo małego zbioru obiektów, gdyż proces łączenia odbywa się w N— 1 krokach (gdzie N oznacza liczbę obiektów)^s. Polegają one na tym, że najpierw znajduje się klasy .leżące najbliżej siebie, a następnie łączy się je w jedno skupienie.

Algorytm realizujący grupowanie obiektów w- ramach tych metod składa się ż następujących kroków:

1.    Utwórz n skupień, z których każde zawiera jeden obiekt.

2,    Na podstawie macierzy odległości między skupieniami D = [d/j] znajdź takie dwa skupienia A i B, które leżą najbliżej:

d^=£mmr{4)}sr .

3.    Połącz je w jedno skupienie A i usuń skupienie B (eliminując z macierzy D odpowiedni wiersz i kolumnę).

4.    Oblicz na nowo odległości między nowym skupieniem a wszystkimi pozostałymi, tworząc nową macierz D.

5.    Powtarzaj kroki 2—4 aż do momentu, gdy pozostanie jedno skupienie obejmujące wszystkie obiekty (wymiar macierzy D zredukuje się do 1).

Wśród metod aglomeracyjnych można wymienić np.:

• Metodę najbliższego sąsiedztwa, która odległość między skupieniami

| Chodzi o ograniczenia pamięci operacyjnej komputera, w której przechowywane są wyniki kolejnych etapów łączenia obiektów.

A i fi traktuje jako odległość między dwoma najbliższymi obiektami należącymi do tych klas:

H|| =    '(fg$

gdzie /»

•    Metodę najdalszego sąsiedztwa, która ujmuje odległość między klasami A i B jako dystans między najbardziej odległymi obiektami należącymi do nich:

•    Metodę Warda, która sumuje odległości poszczególnych obiektów od środków ciężkości skupień A i B:

Typową reprezentacją działania metod aglomeracyjnych są dendro-grdmy, będące drzewami binarnymi, których wędy odpowiadają utworzo-ńym ^skupieniom.

W wyniku stosowania większości metod taksonomicznych powstają skupienia rozłączne, czasami jednak (np. w badaniach lingwistycznych) obiekty mogą naleteć do więcej niż jednego skupienia. Metody tego typu powodują także stopniowy podział wyjściowego zbioru obiektów na dwie części: skupienie zawierające obiekty podobne oraz reszta (tj. obiekty odległe od tych, które znajdują się we wspomnianej klasie). Funkcja spójności obiektów, która wyznacza podział na klasy, ma postać (Everitt 1980):

„ ^AA^BB, ■:

gdzie A i fi to klasy (z tym, że A to grupa obiektów podobnych), S_AB to suma wartości miary podobieństwa, p, obiektów należących do A i fi:

>4U

itAJeB,^

Algorytmy tego typu nie są zwykle efektywne, tj. ten sam podział obiektów można uzyskać w oparciu o różne skupienia wyjściowe.

31