IMAGE2 (2)

Obiekt jest klasyfikowany w ten sposób, że przesuwa się go od korzenia do liścia drzewa, zgodnie z wartościami jego cech. Decyzja o wyborze krawędzi zależy od rezultatu testu znajdującego się w danym węźle drzewa (rys. 6.2). Jeśli obiekt spełnia opis klasy (pojęcia) znąjdujqccj się w liściu drzewa, to zostaje do niej włączony i opis klasy zmodyfikuje się przez proces dopasowania. W przeciwnym przypadku realizuje się proces dyskryminacji.

Rys. 6.2. Przy kład drzewa klas tworzonego przez EPAM

Algorytm EPAM składa się z czterech kroków:

1.    Weź obiekt i dołącz go do węzła nadrzędnego (za pierwszym razem jest to korzeń) drzewa.

2.    Jeśli węzeł jest liściem, sprawdź czy występują różnice między wartościami cech obiektu a opisem klas. Jeśli tak, dokonaj dyskryminacji, w przeciwnym przypadku — dopasowania.

3.    Jeśli węzeł nie jest liściem, przesuń go w dół, do węzła podrzędnego, zgodnie z wynikiem testu.

4.    Wykonaj rekurencyjnie kroki 2—3 dla wszystkich węzłów podrzędnych w stosunku do węzła bieżącego.

Proces dyskryminacji polega na tym, że nowo klasyfikowany obiekt wprowadza się do węzła drzewa i poddaje testowi, który się w nim znajduje. Ponieważ EPAM jest algorytmem monofetycznym, test jest

pytaniem o wartość pewnej cecljy; na rys. .6,2 jest to zysk, -Jeśli wartość analizowanej cechy spełniaten test, obiekt przenosi.się w dół drzewa, wzdłuż odpowiedniej krawędzi. Jeśli obiekt nie spełnia testu; EPAM tworey dla niego nową podr^ną klasę; (węzd)._:u :

Jeśli ohiektzostaje w zbiorze opisywanym przez liść, EPAM porównuje jego cechy z charakterystyką klasy. Jeśli są różnice, liść zamienia się w węzeł, w którym znajduje się test dyskryminujący klasyfikowany obiekt oraz obiekty, które wcześniej się tam znalazły. Powstają zatem dwa podrzędne węzły — liście. :

-,-^rfićęs dopasowania powoduje zmianę charakterystyki klasy, do której wprowadzono nowy obiekt. W takim przypadku obiekt może mieć cechy nieobecne do tej pory w opisie klasy, które powinny zostać do niego .dodane,-

Następnym algorytmem podziałowym znanym z literatury jestDISCON Lańgleya i Sage’a (1984). Podobnie jak EPAM, także jest to algorytm monotetyczny,^ v_tzn, tworzy hierarchiczną strukturę klas przez-podział ^tnprp^o.biektów na podzbiory w oparciu o wartości pojedynczych cech.

. • Ponieważ nie stosuje on żadnych kryteriów jakości podziału, musi wszystkie możliwe hierarchie klas (drzewa), a następnie wybrać fó ^^o, ^óm jmaT najmniejszą liczbę węzłów. Wymaga to niemal pełnego przeszukania, przestrzeni podziałów i jest bardzo kosztowne w sensie czasu óbjicz^d. A^ tego uniknąć, w innych algorytmach starano się zastosować mechanizmy ograniczające y^nuar 'tó| przestrzeni, np. pr^^^wdfe h^^s^mi^^l^enÓw oceny,jakości^    klas. .

‘. _;Zana^    algorytm podziałowy wramach-taksonomii

ŚymbpUcmęj i^ęźy uznać RUMMAGE D.Fishera, który powstał w roku . 1984 (Fisher^S^. Także on tworzy hierarchiczne drzewo klas j także jest ^goryjniędi . moąotetycznym. RUMMAGE jest jednak znacznie szybszy niż EPAh|_x(^DtSCdŃ_Agdyź przeszukuje zdecydowanie mniejszą przestrzeli podziałówr Nie jest też czuły na złą jakość danych.

Dokonując podziału zbioru obiektów S charakteryzowanych przez cechy Xi ha rozłączne podzbiory S_lt RUMMAGE wybiera taką cechę .**, której wartości dają najlepszą strukturę podzbiorów. Proces ten następnie powtarza się dla każdego podzbioru 5; i kończy się, gdy nie można już uzyskać lepszego podziału.

. • Algorytm RUMMAGE wykorzystuje również strategię wspinaczki, tj. znajduje cechę decydującą p podziale w. ten sposób; że podziały zbioru obiektów według wszystkich cech ocenia ze względu na przyjęte