Politechnika Łódzka


Rozdział VI Algorytmy redukcji dla reguły decyzyjnej 1-NN



Pobieranie 6.5 Mb.
Strona38/54
Data29.10.2017
Rozmiar6.5 Mb.
1   ...   34   35   36   37   38   39   40   41   ...   54

Rozdział VI

Algorytmy redukcji dla reguły decyzyjnej 1-NN

Główną wadą reguły decyzyjnej typu k najbliższych sąsiadów (k-NN), a tym bardziej takich klasyfikatorów, jak opisywane w Rozdz. 7 k-NCN i k-NSN, jest stosunkowo wolna klasyfikacja, nie do przyjęcia w niektórych zastosowaniach, np. przy analizie obrazu metodą piksel po pikslu. Wadę tę w niemałym stopniu dziedziczy również najszybsza wersja reguły k-NN, tj. 1-NN. Czas klasyfikacji przy użyciu wymienionych reguł decyzyjnych zależy od wielkości zbioru odniesienia. Jest zatem jasne, iż redukcja zbioru odniesienia, tj. zastąpienie oryginalnego zbioru zbiorem mniejszym, lecz możliwie dobrze aproksymującym powierzchnie decyzyjne między klasami, przyniesie przyspieszenie klasyfikacji.

W rozdziale omówiono kryteria oceny przydatności poszczególnych algorytmów redukcji, opisano bliżej kilka najczęściej używanych i ważnych historycznie koncepcji, przedstawiono szereg algorytmów nowszych, a następnie zaproponowano opraco­wany przez autora rozprawy schemat z lokalnym wyborem zbioru zredukowanego, polegający na zastąpieniu tradycyjnie pojedynczego zbioru zredukowanego zespołem kilku (kilkunastu) takich zbiorów, z których dla danej próbki wybierany jest tylko jeden przy pomocy bardzo szybkiego kryterium (Grabowski, 2002c; Grabowski i Jóźwik, 2003). Wyniki ekspery­mentów, opisanych w Rozdz. 6.5, sugerują atrakcyjność przedstawio­nego podejścia.

Ponadto zaproponowano modyfikacje niektórych znanych algorytmów oraz przedstawiono i porównano empirycznie kilka heurystycznych implementacji tworzenia zbioru zredukowanego Tomeka.


6.1. Specyfika problemu i kryteria oceny algorytmów

Redukcja zbioru odniesienia ma sens zasadniczo dla reguły 1-NN. Redukcja powoduje „rozrzedzenie” zbioru, a zatem przy zastosowaniu np. reguły k-NN istniałoby poważne niebezpieczeństwo, iż część sąsiadów znajdzie się zbyt daleko od badanej próbki, aby dobrze przewidywać jej klasę. Tym niemniej, niekiedy — zwłaszcza na zbiorach zaszu­mionych — algorytmy redukcji pierwotnie przewidziane dla reguły 1-NN adaptuje się do reguł k-NN z małymi wartościami k, np. 3 (Wilson i Martinez, 2000).


Rys. 6.1. Przykładowa redukcja zbioru 2-wymiarowego złożonego z 2 klas.


Elementy wyróżnione („krzyżyki” z otoczką i wypełnione „kółka”)
wchodzą do zbioru zredukowanego.
W literaturze podaje się ponad 20 algorytmów redukcji zbioru odniesienia. W zdecydowanej większości algorytmów zredukowany zbiór jest pewnym podzbiorem zbioru oryginalnego (poglądową ilustrację efektu działania redukcji ukazuje Rys. 6.1). Większość algorytmów redukcji podawanych w literaturze produkuje zbiory zgodne z oryginalnymi zbiorami odniesienia. Zgodność oznacza, iż reguła 1-NN wykorzystująca zbiór zredukowany jako zbiór odniesienia poprawnie klasyfikuje wszystkie próbki ze zbioru oryginalnego. Kryterium zgodności ma być niejakim potwierdzeniem, iż algorytm redukcji produkuje zbiór zredukowany wyznaczający powierzchnie decyzyjne bliskie powierzchniom decyzyjnym zdefiniowanym w oparciu o oryginalny zbiór odniesienia. Jak pokazano w dalszej części rozdziału, przekonanie to jest złudne, gdyż algorytmy bazujące na kryterium zgodności są mocno podatne na przeuczenie. Szybkość redukcji ma zwykle znaczenie drugorzędne, gdyż proces ten wykonywany jest tylko raz dla danego zbioru. Tym niemniej, niektóre algorytmy wydają się zbyt wolne dla bardzo dużych zbiorów. Dla ogromnych zbiorów odniesienia, liczących setki tysięcy lub miliony obiektów, nawet najszybszy z algorytmów produkujących zbiór zgodny z oryginalnym, tj. algorytm „skondensowany najbliższy sąsiad” (Condensed Nearest Neighbor, CNN) (Hart, 1968), może być zbyt wolny. W takim przypadku rezygnacja z wymogu zgodności jest już koniecznością (Jóźwik i in., 1995).

Wiele algorytmów redukcji, zwłaszcza w klasie algorytmów spełniających wymóg zgodności, działa w sposób przyrostowy albo — przeciwnie — poprzez kolejną eliminację zbędnych elementów. W pierwszym przypadku procedura redukcji startuje z pustego zbioru zredukowanego i sukcesywnie go powiększa (do liczności zadanej przez użytkownika albo wyznaczonej automatycznie). Algorytm redukcji przez eliminację zaczyna od kompletnego zbioru odniesienia i po kolei usuwa elementy, aż do spełnienia kryterium stopu.


Poniżej omówiono systematycznie kryteria decydujące o przydatności danego algorytmu redukcji.

Szybkość klasyfikacji. Jest to jedno z najważniejszych kryteriów. Szybkość klasyfika­cji jest ściśle związana z wielkością zbioru zredukowanego. Nie musi to być jednak zależność wprost proporcjo­nalna; może być subliniowa, jeśli oprócz redukcji używa się odpowiedniego algorytmu szybkiego szukania NS (p. Rozdz. 5).

Pamięć dla klasyfikatora (tj. dla zbioru zredukowanego). Wielkość pamięci przechowu­jącej zbiór zredukowany wiąże się z szybkością klasyfikacji. Samo obciążenie pamięciowe nie jest obecnie już tak dotkliwe jak przed laty, ale również może mieć znaczenie przy bardzo dużych zbiorach. Warto zaznaczyć, iż w niektórych algoryt­mach, np. z pracy (Wettschereck i Dietterich, 1995), oprócz próbek, zbiór zredukowany może zawierać bardziej złożone obiekty (np. hiperprosto­kąty); ich reprezentacja będzie zapewne bardziej kosztowna pamięciowo niż w przypadku punktów.

Jakość klasyfikacji (ogólna). Kolejne bardzo ważne kryterium. Przy redukcji estymuje się ją przeważnie z użyciem zbioru testowego. Na ogół po redukcji jakość klasyfikacji nieco się pogarsza. Może jednak się poprawić: próbki z oryginalnego zbioru ewidentnie „źle leżące” (tj. szum) mogą zostać usunięte i tym samym granice między klasami wygładzone.

Jakość klasyfikacji w obecności szumu. Obecność szumu stwarza dwa podstawowe niebezpieczeństwa. Pierwsze polega na tym, że niewiele próbek zostanie usuniętych z oryginalnego zbioru, gdyż algorytm będzie starał się możliwie wiernie oddać zaszu­mione (czyli w sztuczny sposób skomplikowane) granice decyzyjne między klasami (zjawisko przeuczenia). Drugi problem to możliwość usunięcia „dobrych” próbek, a pozostawienia „złych”, tj. będących szumem. Przykładowo, jest na to narażony algorytm CNN (Hart, 1968). Algorytmy słabo radzące sobie z opisanymi problemami (mówi się: wrażliwe na szum) na ogół oferują niską jakość klasyfikacji.

Pomocnymi „narzędziami” do usuwania szumu mogą być wstępna selekcja cech oraz reklasyfikacja lub odfiltrowanie zbioru odniesienia (techniki te zostały omówione w dalszej części rozdziału).



Szybkość uczenia (generacji zbioru zredukowanego). Kryterium mniej ważne, gdyż proces uczenia wykonywany jest tylko raz. W praktyce jednak, zbyt wolne algorytmy nie mogą być zastosowane na bardzo dużych zbiorach. Niestety, redukcja jest najbar­dziej potrzebna właśnie w przypadku bardzo dużych zbiorów, zatem warto dbać o optymalizację i tego kryterium.

Pamięć potrzebna do uczenia. Na ogół koszt pamięciowy uczenia jest niski i wynosi , nliczność oryginalnego zbioru, a nawet — jeśli dane wejściowe podawane są kolejno (np. w czasie trwania eksperymentu) i nie muszą być wszystkie przechowy­wane w pamięci — może wynosić tylko , h – wielkość zbioru zredukowanego (tak będzie w przypadku algorytmu IB2 (Kibler i Aha, 1987), będącego de facto pierwszym cyklem algorytmu Harta).

Z drugiej strony, w przypadku algorytmu selektywnego (Ritter i in., 1975) do uczenia potrzebna jest macierz binarna nn, co może wykluczyć tę metodę z niektó­rych zastosowań.



Zdolność szybkiej modyfikacji zbioru zredukowanego w przypadku dynamicznym. Jeśli już po wygenerowaniu zbioru zredukowanego oryginalny zbiór uczący zostanie zmieniony (przybędą nowe próbki i/lub zostaną usunięte niektóre inne próbki), to zignorowanie tego faktu w oczywisty sposób prowadzić musi do utraty szansy poprawy jakości klasyfikacji. Dlatego też w takiej sytuacji zbiór zredukowany powinien zostać uaktualniony. Najniżej zostanie oceniony algorytm, dla którego usunięcie bądź dodanie jednej próbki do zbioru oryginalnego wymaga generacji zbioru zredukowanego „od zera”.

Pobieranie 6.5 Mb.

Share with your friends:
1   ...   34   35   36   37   38   39   40   41   ...   54




©operacji.org 2020
wyślij wiadomość

    Strona główna