Politechnika Łódzka


Przegląd innych wybranych algorytmów selekcji cech



Pobieranie 6.5 Mb.
Strona25/54
Data29.10.2017
Rozmiar6.5 Mb.
1   ...   21   22   23   24   25   26   27   28   ...   54

2.5. Przegląd innych wybranych algorytmów selekcji cech


Dość oryginalną koncepcją wyróżnia się algorytm RC (Relevance in Context) kontekstowego doboru cech dla rozważanych obiektów, zaproponowany w pracy (Domingos, 1997). Jeśli dana cecha j rozważanej próbki x jest identyczna (z pewną dokładnością — dobór tej tolerancji jest w pracy uzasadniony) z wartością tej cechy u najbliższego sąsiada x i dodatkowo odrzucenie j-tej cechy dla próbki x nie powoduje zwiększenia błędu szacowanego metodą minus jednego elementu, to j-tą cechę dla próbki x należy odrzucić. Jak widać, novum metody polega na osobnym doborze cech dla poszczególnych obiektów (zauważyć można jednak inspirację omawianymi na początku bieżącego rozdziału kontekstowymi metodami ważenia cech, np. pracą (Aha i Goldstone, 1992)). Na większości testowanych zbiorów UCI, algorytm RC osiągnął wyższą jakość klasyfikacji niż „standardy” FSS i BSS; w porównaniu używano klasyfikatora 1-NN. Można jednak wnioskować, że na zbiorach, dla których optymalny zestaw cech nie zmienia się w zależności od kontekstu, metoda Domingosa nie przyniesie poprawy, a na małych (lub mocno zaszumionych) zbiorach tego typu prawdopodobne jest nawet pogorszenie jakości w stosunku do FSS i BSS, co przyznaje autor metody.

Zastosowanie algorytmów genetycznych do selekcji cech proponowano kilkakrotnie (Brill i in., 1992; Guo i Uhrig, 1992; Vafaie i De Jong, 1992; Cherkauer i Shavlik, 1996; Yang i Honavar, 1997; Kuncheva i Jain, 1999); tylko ostatnia z wymie­nionych prac dotyczy jednak klasyfikatora 1-NN (w pozostałych schematach klasyfi­katorami były drzewa decyzyjne lub sieć neuronowa). Jako ciekawostkę można podać fakt, iż algorytm genetyczny został także z sukcesem wykorzystany do wyboru cech odpowiednich do bezstratnej kompresji chorałów Bacha (Hall, 1995). Za podejś­ciem genetycznym może przemawiać naturalna reprezentacja cech jako chromosomów (bit 1: dana cecha należy do zestawu, bit 0: cecha nie należy), wewnętrzna równoległość i niestosowanie często wiodącego „na manowce” kryterium monotoniczności oraz elastyczność działania wynikająca z pewnej liczby zadanych z góry współczynników. W pracy Kunchevy i Jaina (1999) połączono selekcję cech z redukcją zbioru odniesienia, osiągając obiecujący kompromis między stopniem redukcji (niskim iloczy­nem wyniko­wej liczby cech i liczności zbioru) a jakością. Należy jednak podkreślić, że względna prostota implementacyjna algorytmów genetycznych nie idzie w parze z łatwością zrozumienia ich działania, a zatem wolno chyba stwierdzić, iż eksperymenty w tym kierunku przypominają metodę „prób i błędów”.

Bardzo prostą i szybką metodę wyboru zestawu cech o zadanej liczności zapre­zentowali Holmes i Navill-Manning (1995). Oceniają oni jakość pojedynczych cech przy użyciu reguł Holte’a (1993), które de facto są drzewami decyzyjnymi o jednym poziomie. Użytkownik podaje docelową liczbę cech i otrzymuje na wyjściu odpo­wiedni zestaw najlepszych (osobno) atrybutów. Niestety, nie ma gwarancji, że cechy najlepsze osobno stanowią najlepszy zestaw łącznie (brak np. zabezpieczenia przed pełną korelacją cech).

Warto jeszcze wspomnieć o równoległym algorytmie konkurencyjnym (ang. schemata racing) zaproponowanym w pracy (Maron i Moore, 1997), w którym przyspieszenie procedury otrzymywane jest dzięki odrzucaniu części zbioru odniesienia w trakcie oceny zestawów.



Klasyfikator NNFP


Oryginalna koncepcja została zaprezentowana w pracach (Akkus i Güvenir, 1996) i (Kubat i Chen, 1998). Wszystkie próbki zbioru uczącego są rzutowane na pojedyncze cechy. Klasyfikacja — w schemacie nazwanym regułą najbliższego sąsiada z projekcją cech (Nearest Neighbor with Feature Projection, NNFP) — polega na znalezieniu klasy najbliższego sąsiada po każdej poszczególnej cesze, a następnie głosowaniu wyłaniającym zwycięską klasę. W drugiej z wymienionych prac idea została ulepszona. Schemat wNNFP (Weighted Nearest Neighbor with Feature Projection) dokonuje heurystycznej redukcji próbek na poszczególnych cechach (bez straty informacji potrzebnej do klasyfikacji), a dodatkowo, co istotniejsze, używa wag dla cech. Cechom, które osobno dość słabo dyskryminują próbki zbioru uczącego, będą przypi­sane niskie wagi i odwrotnie. Eksperymenty na zbiorach sztucznych i rzeczywistych potwierdziły to, co można było przypuszczać: k‑NN daje wyższą jakość w przypadkach małej liczby nieistotnych cech i/lub znaczących korelacji między cechami. Schematy z projekcją cech, a zwłaszcza schemat z wagami, są konkurencyjne w przypadku dużej liczby nieistotnych cech, a także niezależności cech istotnych (warto zauważyć pokrewieństwo klasyfikatora NNFP z naiwnym klasyfikatorem Bayesa, przedstawio­nym w Rozdz. 1.2.4). Niewątpliwymi zaletami NNFP i wNNFP są szybka klasyfikacja (najbliższy sąsiad dla danej cechy znajdowany jest przy pomocy wyszukiwania binarnego), naturalna obsługa próbek z brakującymi cechami (w takim przypadku dana cecha, innymi słowy: dany klasyfikator składowy, powstrzymuje się od wzięcia udziału w głosowaniu), niewrażliwość na skalowanie cech i pewna odporność na szum (tylko wNNFS).

Poniżej pokazano, jak zastąpić heurystyczną redukcję próbek dla danej cechy redukcją optymalną (idea ta została przeoczona przez Kubata i Chena5).


­­­ – + + + + – – – – + Ti

– + + – – + Ti


Rys. 2.2 (przykład z pracy (Kubat i Chen, 1998)). Zbiór Ti’ to Ti po redukcji
Heurystyka Kubata i Chena polega na usunięciu wszystkich próbek, dla których najbliżsi sąsiedzi „po obu stronach” są z tej samej klasy, co dana próbka. Ilustruje to Rys. 2.2.
– + + – – + Ti
o o o Ti’’
Rys. 2.3. Kółka oznaczają końce następujących po sobie przedziałów,
w których nie zmienia się decyzja o przynależności do klasy
Z kolei Ti’’ na Rys. 2.3 to wynik zastosowania optymalnej redukcji. W procesie klasyfikacji nie szuka się tym razem najbliższego sąsiada dla próbki o wartości danej cechy wynoszącej x, natomiast należy znaleźć najbliższy kraniec przedziału (czyli na Rys. 2.3 najbliższe kółko) nie mniejszy niż x. Następnie odczytuje się z tablicy, z jaką klasą jest ten przedział związany — co kończy klasyfikację dla danej cechy. Warto zauważyć, że w przypadku dwóch klas tablicowanie przedziałów nie jest potrzebne, gdyż wystarczy odczytanie parzystości indeksu danego przedziału (rzecz jasna, aby wyszukiwanie binarne było możliwe, przedziały muszą być przechowywane w posorto­wanej kolejności).
Rozdział III

Zespoły klasyfikatorów minimalnoodległościowych

W rozdziale przedstawiono koncepcję intensywnie rozwijanych w ostatnich latach zespołów klasyfikatorów, z położeniem szczególnego nacisku na metody dekompozycji oryginalnego zadania dla klasyfikatorów typu k-NN i pokrewnych. Opisano opracowaną przez autora rozprawy (Grabowski, 2002a) metodę uczenia zestawów cech dla klasyfikatora „wiele podzbiorów cech” (Multiple Feature Subsets, MFS) (Bay, 1998) stosującego głosowanie po różnych podzbiorach cech, wraz z wynikami eksperymentów i ich dyskusją.


3.1. Wprowadzenie

Zasadniczym problemem pojawiającym się praktycznie we wszystkich zadaniach klasyfikacji jest niebezpieczeństwo przeuczenia. Zjawisko to polega na wyborze takiego modelu klasyfikacji, tj. klasyfikatora i jego parametrów, którego bardzo dobra jakość na zbiorze uczącym nie przekłada się na zdolność generalizacji, tj. dobrą predykcję etykiet próbek nieznanych (testowych). Problemu tego nie da się wyelimi­nować całkowicie, ze względu na skończoną wielkość rzeczywistych zbiorów danych. Duża wariancja błędu w testach wykonywanych na różnych zbiorach uczących i testowych dla danego zadania lub przy kolejnych uruchomieniach algorytmu probabi­listycznego sugeruje, iż dany algorytm klasyfikacji jest podatny na przeuczenie.

Jednym z najatrakcyjniejszych podejść mających na celu zwiększenie jakości klasyfikacji i/lub zmniejszenie wariancji błędu jest łączenie klasyfikatorów (ang. combining classifiers). Lata 90-te minionego stulecia to okres intensywnych badań w dziedzinie zespołów klasyfikatorów (ang. ensembles of classifiers), czego owocem były trzy zasadniczo odmienne podejścia do łączenia klasyfikatorów:


  • schematy równoległe z głosowaniem (ang. classifier fusion, mixture of experts), gdzie poszczególne klasyfikatory składowe dokonują niezależnie predykcji, tj. zwracają etykietę (niekiedy rozmytą) klasyfikowanej próbki, a model wyższego rzędu „scala” ich predykcje (Kittler i in., 1998; Kuncheva i in., 2001) — najpro­stszą metodą pozyskiwania finalnej decyzji jest głosowanie większościowe (ang. majority voting);

  • schematy z lokalnym wyborem klasyfikatora (ang. classifier selection), gdzie dla danej próbki wybierany jest odpowiedni (pojedynczy) klasyfikator (Dasarathy i Sheela, 1979);

  • schematy kaskadowe (ang. cascade classifiers, multistage classifiers) — próbka podawana jest na wejście pierwszego, najszybszego, ale i najbardziej „niewyszukanego” klasyfikatora; jeśli uzna on próbkę za zbyt trudną (tj. jego predykcja obciążona byłaby zbyt dużą niepewnością), to odsyła ją do następnego, wolniejszego, ale dokładniejszego klasyfikatora itd. (Baram, 1998; Alpaydin i Kaynak, 1998).

Najwięcej prac dotyczy schematów z głosowaniem. Ideę takiego podejścia można wyjaśnić następująco: jeśli każdy klasyfikator składowy generuje inne przybliżenie prawdziwych granic decyzyjnych między klasami, to można oczekiwać, że w procesie głosowania — czyli uśredniania — szum zostanie (częściowo) usunięty, a granice decyzyjne „wygładzone”, zwłaszcza jeśli liczba komponentów jest duża. Istnieje proste twierdzenie mówiące, iż błąd klasyfikacji popełniany w wyniku prostego (większościo­wego) głosowania zespołu niezależnych klasyfikatorów maleje asymptotycznie do zera, jeśli błędy popełniane przez pojedyncze klasyfikatory są równe i mniejsze od 0,5. Twierdzenie to zostało podane w szeroko cytowanej pracy Hansena i Salamona (1990), warto jednak wiedzieć, iż jest to wynik z XVIII wieku (!), udowodniony przez Markiza Condorceta (Condorcet, 1781). Zdaniem autora niniejszej rozprawy, znaczenie tego twierdzenia jest często przeceniane. Weźmy przykład sztucz­nego zbioru, dla którego błąd Bayesa można policzyć i niech wynosi on 0,15. Załóżmy teraz, że mamy trzy niezależne klasyfikatory popełniające na tym zbiorze błąd z prawdopodobieństwem 0,2. Proste obliczenia pokazują, że błąd w wyniku głosowania naszego zespołu klasyfikatorów wynosi 0,104 (tj. 0,23 + 3  0,22  (1–0,2)). Sprzeczność (tj. „zej­ście” poniżej błędu Bayesa) pokazuje, iż niemożliwe jest wygenerowanie opisanych trzech niezależnych klasyfikatorów.

Na szczęście, nawet jeśli klasyfikatory nie są niezależne (sytuacja właściwie zawsze pojawiająca się w praktyce), to i tak zwykle można oczekiwać poprawy jakości klasyfikacji w wyniku głosowania. Generalnie, klasyfikatory składowe powinny być możliwie dokładne i możliwie różnorodne (ang. diverse), przy czym różnorodność rozumie się jako możliwie małą korelację błędów poszczególnych klasyfikatorów składowych. Argumentowano również, że negatywna korelacja między klasyfikatorami może być lepsza niż brak korelacji (Kuncheva i in., 2000). Poważną wadą tego podejścia jest jednak wydłużony czas klasyfikacji (w przybliżeniu proporcjonalny do liczby klasyfikatorów składowych i ich średniej szybkości klasyfikacji).

Rys. 3.1 pokazuje, w jaki sposób sieć pięciu prostych klasyfikatorów z głosowa­niem większościowym potrafi rozwiązać klasyczny problem „XOR”. Warto zwrócić uwagę, iż komponenty sieci nie są niezależne (dla przykładu, klasyfikatory 1 i 5 dokonują zawsze tych samych predykcji).




Rys. 3.1. Realizacja funkcji XOR przy pomocy sieci klasyfikatorów


Charakterystyczną cechą sieci klasyfikatorów z głosowaniem jest zmniejszona zrozumiałość (ang. comprehensibility) wygenerowanego modelu w stosunku do klasyfikatora bazowego. W przypadku klasyfikatorów minimalnoodległościowych ma to niewielkie znaczenie, z uwagi na immanentną trudność ludzkiej interpretacji działania nawet pojedynczego klasyfikatora tego typu, jednak w przypadku drzew decyzyjnych — które wszak w najprostszym przypadku dzielą przestrzeń na zestaw rozłącznych hiperprostopadłościanów płaszczyznami równoległymi do osi układu współrzędnych — może być to znaczną wadą z punktu widzenia końcowego użytkownika takiego systemu.6
3.2. Przegląd koncepcji

Poniżej dokonano przeglądu idei tworzenia zespołu klasyfikatorów oraz metod łączenia ich predykcji. W osobnych podrozdziałach omówiono bliżej naszkicowane wcześniej trzy podejścia do konstrukcji klasyfikatorów o strukturze sieciowej, podano metody głosowania klasyfikatorów składowych, a także wspomniano używane miary różnorod­ności klasyfikatorów w zespole.


3.2.1. Schematy z głosowaniem

Większość schematów wymienionych w tym podrozdziale to klasyfikatory równoległe, tj. z nie komunikującymi się komponentami. Szczególnie w tego typu topologiach sieciowych istotne jest wygenerowanie możliwie różnorodnego zespołu klasyfikatorów składowych.



Bagging (skrót od bootstrap aggregation) (Breiman, 1996a) polega na k-krotnym wylosowaniu z powtórzeniami n próbek z n-elementowego zbioru odniesienia, w wyniku czego otrzymywanych jest k zbiorów odniesienia, z których każdy zawiera średnio ok. 63,2% () różnych próbek z oryginalnego zbioru. Każdy z otrzyma­nych zbiorów służy do wygenerowania osobnego modelu składowego (sieci neuronowej lub drzewa decyzyjnego). W praktyce już 10 składowych drzew decyzyjnych w modelu bagging wystarcza do osiągnięcia zadawalającej jakości klasyfikacji (większa liczba komponentów nie daje znaczącej poprawy) (Indurkhya i Weiss, 1998).

Boosting (Schapire, 1990; Freund i Schapire, 1996; Breiman, 1996b) to ogólna metoda przyrostowej konstrukcji zespołu klasyfikatorów (zazwyczaj dla sieci neuronowej), w której każda próbka zbioru uczącego ma swoją wagę, przy czym wagi próbek niepoprawnie klasyfikowanych przez poprzednio zbudowane klasyfikatory są zwiększane, a tym samym nacisk na „nauczenie” się tych właśnie trudnych próbek rośnie. Finalna decyzja powstaje w wyniku ważonego głosowania komponentów. Należy zwrócić uwagę, iż boosting nie jest schematem równoległym.

Breiman (1996b) oraz Schapire i in. (1997) pokazali, iż bagging zmniejsza wariancję błędu, czyli poprawia stabilność klasyfikatora. Z drugiej strony boosting jest klasyfikatorem mniej przewidywalnym, tj. bardziej wrażliwym na szum (choć średnio osiąga mniejsze błędy niż oryginalny schemat bagging). Tłumaczono to zjawisko dwoma przyczynami: nadmiernym być może naciskiem kładzionym na trudne (tj. często zaszumione) próbki (Opitz i Maclin, 1999) oraz ważoną metodą głosowania, która jest bardziej podatna na przeuczenie niż głosowanie większościowe (bez wag) (Sollich i Krogh, 1996).

Zazwyczaj uważa się, że wprowadzenie głosowania z wagami do modelu bagging nie przynosi poprawy wyników, z uwagi na zmniejszoną różnorodność komponentów (Indurkhya i Weiss, 1998). Jednak Grossman i Williams (1999) dokonali pomyślnej próby ważenia głosów w tym modelu: zaproponowane wagi uwzględniały jakość predykcji danego komponentu na nie wylosowanych z oryginalnego zbioru próbkach w stosunku do jakości predykcji tych próbek dokonanej przez inne komponenty. Wadą tego podejścia jest większa liczba komponentów potrzebna do stabilizacji wyników (ok. 50), co wydłuża czas uczenia i klasyfikacji oraz zmniejsza zrozumiałość modelu.

Wprowadzanie losowości do modelu jest standardową techniką generacji zespołu sieci neuronowych (Kollen i Pollack, 1991). W najprostszej wersji idea polega na ustawieniu losowych wag startowych dla każdej ze składowych sieci. W literaturze spotyka się sprzeczne stwierdzenia nt. tej metody: wg (Parmanto i in., 1996) efektyw­ność techniki jest stosunkowo niewielka, natomiast w testach na 23 zbiorach UCI oraz z University of Wisconsin wypada ona dobrze, znacząco lepiej niż pojedyncza sieć neuronowa (Opitz i Maclin, 1999).

Eksperymentowano również z dodawaniem losowości do próbek wejściowych. Raviv i Intrator (1996) zakłócali wartości cech szumem gaussowskim, otrzymując tym samym różne zbiory uczące dla zespołu sieci neuronowych. Idea ta, w połączeniu z metodą bagging, dała bardzo dobre wyniki na zbiorze sztucznym oraz w zastosowaniu medycznym.

Koncepcję głosowania zespołu klasyfikatorów 1-NN ze zredukowanym zbiorem odniesienia wprowadził Skalak (1997); zostanie ona dokładniej opisana w Rozdz. 6.2. Inną pracę tego typu przedstawił Alpaydin (1997), gdzie zbiorami zredukowanymi były zbiory Harta (p. Rozdz. 6.2), a różnice między nimi wynikały z losowych kolejności próbek zbioru uczącego na wejściu algorytmu redukcji.

Podobnie koncepcje: dekompozycji zadania wielodecyzyjnego na sieć klasyfi­katorów binarnych oraz głosowania po różnych zespołach cech zostaną dokładnie omówione w osobnych podrozdziałach (odpowiednio: 3.3 i 3.4–3.5), z uwagi na ich doniosłość dla problematyki klasyfikatorów minimalnoodległościowych.

W Rozdz. 7.4 zaproponowano schemat z głosowaniem wielu klasyfikatorów typu k-NN (lub innych klasyfikatorów opartych na k sąsiadach), z których każdy znajduje własną wartość k na podstawie losowej partycji zbioru uczącego. Eksperymenty pokazują, iż schemat ten osiąga wyższą jakość predykcji niż oryginalna reguła k-NN.


3.2.2. Lokalny wybór klasyfikatora

W odróżnieniu od schematów z głosowaniem, schematy z lokalnym wyborem klasyfikatora dla zadanej próbki używają tylko jednego (wybranego) modelu, a zatem są potencjalnie szybsze. Po raz pierwszy koncepcja ta pojawiła się już na przełomie lat 70-tych i 80-tych (Dasarathy i Sheela, 1979; Rastrigin i Erenstein, 1981), jednak nie od razu przebiła się do szerszej świadomości badaczy.7

Dasarathy i Sheela (1979) stosują klasyfikator liniowy dla „łatwych” próbek oraz regułę k-NN dla próbek „trudnych”, zakładając przy tym dwie klasy w zadaniu. Dokładniej, wyznaczana jest para płaszczyzn, z których każda po jednej stronie zawiera próbki tylko z jednej klasy, natomiast pomiędzy płaszczyznami znajduje się tzw. strefa konfliktu (ang. region of conflict); próbki testowe, które znajdą się w strefie konfliktu, są klasyfikowane przy użyciu reguły k-NN, jednak ze zbiorem odniesienia ograniczonym tylko do próbek uczących z tej strefy.

Rastrigin i Erenstein (1981) używają zestawu klasyfikatorów wraz z metaklasy­fikatorem, określającym dla danej próbki, w czyj „region kompetencji” ona wpada. Należy zauważyć, iż poprawne przydzielenie modelu dla klasyfikacji danej próbki owocuje klasyfikacją nie gorszą niż oferowana przez dowolny pojedynczy model z danego zespołu użyty globalnie. Rzecz jasna, główna trudność w schematach tego typu polega właśnie na trafnym przydzieleniu modelu.

W pracach (Woods i in., 1997; Giacinto i Roli, 1997) kryterium lokalnego wyboru jest oparte na regule k najbliższych sąsiadów z pełnym zbiorem odniesienia, a zatem jest dość wolne (mimo iż użytymi komponentami są perceptrony, a więc klasyfikatory szybsze niż k-NN).

Kuncheva (2000) podzieliła zbiór odniesienia przy pomocy klasteryzacji metodą k średnich (MacQueen, 1967), a następnie z każdym klastrem skojarzyła najlepszą dla tego klastra sieć neuronową — jeden z pięciu osobno wyuczonych perceptronów wielowarstwowych. Głównym wnioskiem, jaki można wyciągnąć z wyników autorki, jest możliwość uzyskania mniejszych błędów przy lokalnym wyborze zbioru odniesie­nia niż przy głosowaniu większościowym zespołu, gdy składowe sieci neuronowe są „niedouczone” (mała liczba epok w sesjach treningowych). Oznacza to, że zaletą sche­matu z lokalnym wyborem zbioru odniesienia może być nie tylko szybka klasyfikacja, ale także stosunkowo krótki czas uczenia.

Warto dodać, że istnieją algorytmy pośrednie pomiędzy podejściem pierwszym (głosowanie) a drugim (lokalny wybór jednego modelu). Mianowicie w pracach (Jacobs i in., 1991) oraz (Alpaydin i Jordan, 1996) autorzy nominują lokalnie do podję­cia decyzji pewną grupę klasyfikatorów, które następnie uczestniczą w głosowaniu.

W Rozdz. 6.4 zaproponowano schemat z lokalnym wyborem zbioru zreduko­wanego, gdzie kryterium wyboru może być oparte na klasteryzacji lub podziale hiperpłaszczyznami zbioru uczącego.


3.2.3. Schematy kaskadowe

Komponenty w zespole nie muszą być klasyfikatorami tego samego typu ani podobnej złożoności. W praktyce, rozpiętość kosztu klasyfikacji pomiędzy najprostszymi i najszybszymi a najwolniejszymi używanymi klasyfikatorami, np. między klasyfika­torem liniowym a k-NCN (p. Rozdz. 7), wynosi nawet 4–5 rzędów wielkości. Rzecz jasna, klasyfikatory prostsze zwykle oferują gorszą predykcję, gdyż nie uwzględniają pełnej złożoności problemu.

Koncepcja klasyfikatora kaskadowego bazuje na powyższej obserwacji. Uczenie polega na wygenerowaniu kilku (w praktyce zwykle zaledwie 2–3) klasyfikatorów uszeregowanych od najprostszego do najbardziej złożonego. Oprócz samych klasyfika­torów potrzebne są też kryteria ufności, tj. oceniające, czy dany etap klasyfikacji jest wystarczający do dostatecznie pewnej predykcji zadanej próbki. Jeśli pierwszy klasyfi­kator w zespole nie potrafi nadać etykiety testowej próbce z dostateczną pewnością, to próbka zostaje przekazana na wejście drugiego klasyfikatora. Analogiczna reguła rządzi również na następnych etapach klasyfikacji. W przypadku najprostszym, tj. gdy klasyfikator kaskadowy złożony jest tylko z dwóch etapów, etap pierwszy może być postrzegany jako ogólna reguła, natomiast etap drugi jest obsługą wyjątków od tej reguły („trudnych” próbek). Zakładając, że klasyfikacja większości próbek zostaje zakończona na pierwszym, szybkim, etapie, klasyfikator kaskadowy może być atrakcyjnym rozwiązaniem zapewniającym zarówno wysoką jakość, jak i szybkość predykcji. W praktyce, oczywiście, nie jest łatwo zarówno dobrać zespół klasyfika­torów, jak i kryteria ufności.

Kaynak i Alpaydin (2000) przedstawili klasyfikator dwu- lub trójstopniowy używający jednego lub dwóch perceptronów wielowarstwowych (lub perceptronu jednowarstwowego w pierwszej fazie) oraz reguły k-NN w ostatniej fazie klasyfikacji, osiągając na kilku zbiorach UCI jakość porównywalną z jakością zwykłej reguły k-NN przy kilkakrotnie wyższej szybkości klasyfikacji.

Jóźwik i in. (1996) zaproponowali klasyfikator kaskadowy używający reguł 1-NN i k-NN. Jeśli próbka testowa jest położona dostatecznie blisko obiektów jednej tylko klasy, to zostaje ona przypisana do tej klasy, a zatem zgodnie z regułą 1-NN. W sytuacji, gdy próbka testowa znajduje się w strefie nakładania się klas (co w najgorszym przypadku można stwierdzić po policzeniu odległości do wszystkich próbek zbioru uczącego, a więc po wykonaniu pierwszej fazy klasyfikacji), o jej etykiecie decyduje reguła k-NN. Wreszcie w przypadku, gdy dana próbka położona jest poza strefami wszystkich klas, klasyfikator wstrzymuje się od podjęcia decyzji. Taka konstrukcja klasyfikatora może być przydatna w aplikacjach z mocno niesymetryczną funkcją straty, np. w medycynie, gdzie sklasyfikowanie pacjenta chorego jako zdrowego może być znacznie groźniejsze niż pomyłka odwrotna.

W Rozdz. 7.5 zaproponowano rodzinę klasyfikatorów kaskadowych, wykorzy­stującą koncepcję symetrycznego sąsiedztwa oraz podejmującego decyzję w pierwszym etapie, jeśli istnieje konsensus wśród klasyfikatorów równoległych tego etapu.


3.2.4. Metody łączenia głosów klasyfikatorów równoległych

Większość równoległych schematów klasyfikacji może być postrzegana jako metakla­syfikatory: pierwszy (najniższy) poziom to osobne jednostki działające na oryginalnych danych, poziom wyższy zaś to klasyfikator, którego danymi są wyjścia klasyfikatorów pierwszego poziomu (stacked generalization, Wolpert, 1992). W najprostszej wersji klasyfikator drugiego poziomu jest trywialny: dokonuje on tylko głosowania większo­ściowego, tj. przypisuje próbkę do tej klasy, na którą oddało głos najwięcej klasyfi­katorów składowych pierwszego poziomu. W przypadku, gdy klasyfikatory składowe zwracają rozmyte etykiety klas, możliwe są także na ich wyjściach operacje: „maksimum”, „minimum”, uśrednienie oraz iloczyn (wszystkie wspomniane metody opisano np. w pracy (Kittler i in., 1998)).

Metody powyższe nie wymagają uczenia. Istnieją jednak schematy łączenia głosów składowych adaptujące się do zbioru uczącego, które w pełni zasługują na określenie ich mianem klasyfikatora. Przykładowo, metoda behavior-knowledge space (BKS) (Huang i Suen, 1995) polega na znalezieniu dla każdej możliwej kombinacji wyjść zespołu L klasyfikatorów składowych najczęstszej etykiety klasy wśród tych elementów zbioru uczącego, dla których zespół klasyfikatorów zwraca daną L‑elementową kombinację odpowiedzi. Próbka x zbioru uczącego jest przypisywana do klasy skojarzonej z zespołem odpowiedzi klasyfikatorów składowych dla x (obsługa przypadków kombinacji odpowiedzi, które nie wystąpiły dla żadnego elementu zbioru uczącego, jest osobnym zagadnieniem).

Innymi metodami głosowania wymagającymi uczenia są m. in. kombinacja Bayesa (ang. Bayes combination) (Xu i in., 1992) i użycie wzorców decyzyjnych (ang. decision templates) (Kuncheva i in., 2001).


3.2.5. Miary korelacji klasyfikatorów składowych

Innym zagadnieniem jest pomiar korelacji — lub „różnorodności” (ang. diversity) — zespołu klasyfikatorów składowych. Ponieważ prawdziwa niezależność komponentów jest w praktyce niemożliwa, pożądaną rzeczą byłaby choć znajomość korelacji popełnianych przez nie błędów, celem np. odrzucenia komponentów zbyt „podobnych” do innych, które pogarszają predykcję i/lub szybkość działania całego układu. Estymacja korelacji nie jest łatwa, z uwagi na niewielkie zazwyczaj liczności zbiorów uczących.

Należy podkreślić, że miary korelacji komponentów zespołu klasyfikatorów niekoniecznie są bardziej wiarygodne od bezpośredniej estymacji błędu zespołu na zbiorze uczącym. Ich wprowadzanie argumentuje się raczej możliwością głębszego zrozumienia, jak działa klasyfikator równoległy, co — można oczekiwać — pomoże w znalezieniu lepszych heurystyk lub nawet matematycznej teorii projektowania efek­tywnych zespołów.8

Ogólnie miary korelacji można podzielić na dwie kategorie: estymujące ją na bazie wszystkich par klasyfikatorów składowych i uśredniające wyniki (ang. pairwise diversity measures) oraz w bezpośredni sposób estymujące korelację dla całego zespołu (ang. non-pairwise diversity measures).



Do miar pierwszej grupy, z których wiele znanych jest w statystyce od dziesięcioleci (Sneath i Sokal, 1973), można zaliczyć m. in. współczynnik Yule’a Q przyjmujący wartości od –1 (maksymalna negatywna korelacja) przez 0 (niezależność) do 1 (pełna pozytywna korelacja, tj. oba klasyfikatory popełniają błędy na dokładnie tych samych próbkach), miarę niezgodności D, tj. frakcję próbek ze zbioru uczącego, dla których jeden z pary klasyfikatorów dawał poprawną odpowiedź, a drugi błędną, oraz miarę „podwójny błąd” (ang. double-fault measure), czyli frakcję próbek, dla których oba klasyfikatory podały błędną odpowiedź. Wszystkie wymienione miary opisane są w cytowanej wyżej monografii Sneatha i Sokala.

Do miar w bezpośredni sposób estymujących korelację całego zespołu należą m. in. miara trudności (ang. measure of difficulty) (Hansen i Salamon, 1990), będąca wariancją frakcji poprawnych odpowiedzi komponentów dla poszczególnych próbek zbioru uczącego oraz wariancja Kohaviego–Wolperta (1996), oparta na podobnych przesłankach, lecz niejako faworyzująca (w sensie niższej estymowanej korelacji) komponenty o predykcji bliskiej 50% (są to często tzw. słabe (ang. weak) klasyfikatory, czyli klasyfikatory o zdolności predykcji niewiele wyższej od losowego odgadywania).

Wszystkie wymienione metody łączenia głosów oraz miary korelacji kompo­nentów zostały eksperymentalnie zbadane przez Kunchevą i in. (Shipp i Kuncheva, 2002; Kuncheva i Whitaker, 2003); na podstawie tych prac oraz pracy (Kuncheva, 2002), do najlepszych metod łączenia głosów klasyfikatorów składowych należy zaliczyć wzorce decyzyjne, kombinację Bayesa i prawdopodobnie głosowanie większo­ściowe, natomiast miarami korelacji najbardziej wrażliwymi na wybór metody głosowania, czyli mogącymi znacząco pomóc na etapie projektowania klasyfikatora, są miara trudności oraz nieco gorsza, lecz szybsza obliczeniowo, miara „podwójny błąd”.
Pobieranie 6.5 Mb.

Share with your friends:
1   ...   21   22   23   24   25   26   27   28   ...   54




©operacji.org 2020
wyślij wiadomość

    Strona główna