IMAGE1 (2)

numerycznej, z kolei w taksonomii symbolicznej są znaczącą grupą. Można powiedzieć, że takie algorytmy, jak BPAM, RUMMAGE czy DISCON zapoczątkowały ten kierunek badań.

Przedstawione wyżej algorytmy hierarchiczne są dosyć wymagające pod względem wielkości pamięci komputera i kosztowne w sensie czasu jego pracy. Wymagają bowiem obliczenia wartości albo pewnej miary podobieństwa (odległości) dla każdej pary klas (obiektów), albo pewnej funkcji kryterium dla każdego z możliwych podziałów zbioru obiektów na podzbiory. Ponieważ operacje te zależą od liczby obiektów oraz od liczby cech, nawet w przypadku niezbyt wielkiego zbioru pamięć komputera nie pozwala przechować wszystkich danych\ a czas obliczeń szacuje się na 0(n^{1 2 3}), gdzie n to liczba obiektów.

Ograniczenia te spowodowały, że w ramach taksonomii symbolicznej powstała bardzo liczna grupa algorytmów wykorzystujących nieco inne podejście do tworzenia hierarchii klas, tj. metody sekwencyjne (ang. incremental methods).

Metody sekwencyjne, w odróżnieniu od metod aglomerącyjnych i podziałowych, mogą być stosowane do budowy hierarchicznej struktury klas w sytuacji, gdy zbiór obiektów nie jest skończony. Podczas klasyfikacji nowego obiektu strukturę i charakterystykę klas (pojęć) modyfikuje się tak, by dostosować ją do aktualnie reprezentowanego zbioru. Proces .ten jest odzwierciedleniem przebiegu uczenia się człowieka: wiedza w postaci faktów i doświadczeń jest przyswajana stopniowo, zmieniając strukturę pojęć, system wartości itd.

Bardzo ogólny schemat algorytmu sekwencyjnego składa się. z następujących kroków:

1.    Dołącz obiekt do klasy nadrzędnej (za-pierwszym razem jest to korzeń drzewa).

2.    W zależności od wartości funkcji jakości podziału dołącz obiekt do węzła podrzędnego (klasy) albo utwórz dla niego nowy węzeł (klasę).-,.

3.    Wykonuj rekurencyjnie krok 2 dla każdej z klas podrzędnych aż do chwili, gdy obiekt znajdzie się w klasie, która jest w liściu drzewa.

W przeciwieństwie do poprzednio omawianych metod hierarchicznych tworzone drzewo klas nie jest drzewem binarnym, ponieważ z każdego

węzła (zbioru, klasy) może wychodzić kilka krawędzi prowadzących do węzłów podrzędnych (podzbiorów). Najważniejszym zagadnieniem w przypadku metod sekwencyjnych jest wybór kryterium podziału zbioru w węźle na podzbiory. W tym celu stosuje się różne rozwiązania zaczerpnięte ze statystyki, teorii informacji itp. -

Algorytmy będące implementacjami metody sekwencyjnej, podobnie jak metody iteracyjno-optymalizacyjne, wykorzystują strategię wspinaczki², której słabością jest możliwość wybrania lokalnego — zamiast globalnego — rozwiązania optymalnego. W związku z tym, np. algorytm COBWEB wyposażono w specjalne procedury zmniejszające prawdopodobieństwo zbieżności do optimum lokalnego, tj. łączenie i dzielenie węzłów (klas obiektów).

Do najważniejszych zalet metod sekwencyjnych można zaliczyć;

-r- niskie koszty gromadzenia I przechowywania danych,

|yp~ możliwośćklasyfikacji dużych zbiorów danych;.’

> ~ dosyć krótki czasRobBćżeń^fc

— możliwość uzyskania w rezultacie klasyfikacji hierarchicznej struktury klas,

|E dynamiczne modyfikowanie charakterystyki klas tak, by dopasować ją do aktualnie posiadanych informacji.

. Najważniejszym algorytmem taksonomii symbolicznej opartym na metodzie sekwencyjnej jest COBWEB. Stał się on inspiracją i bazą powstania dalszych algorytmów oraz • -praktycznych -systemów (tablica 4.1), np. GLASSEP, EABIR3®nEH, OXBÓW, TTERATE itd i w związku z tym zostanie omówiony bardziej dokładnie w dalszej części, rozdztaftk

62. Metody podziałowe

Pierwszy algorytm podżiałowy to EPĄM E^AJFeigenbauma, który powstał w lataćh'Vsześćdziesiątych.w ramach psychologii jako .model procesu uczenia się przez zaparmętywanie (Feigenbaam;^; Simon 1984). Stosowany był z powodzeniem także w badaniach lingwistycznych oraz w analizie rozgrywek szachowych. Patrząc na niego .z punktu widzenia taksonomii symbolicznej można powiedzieć, że tworzy on hierarchiczne drzewo klas przez rekurencyjny podział zbioru obiektów na rozłączne podzbiory. ⁴

103

1

Nawet w przypadku tok profesjonalnego programu statystycznego jak SPSS, metody

2

hierarchiczne można stosować tylko wtedy, gdy liczba klasyfikowanych obiektów nie

3

przekracza 200 (Gatnar I995a).

4

Strategię tę omówiono w rozdziale 5.