Politechnika Łódzka


Dekompozycja zadania wielodecyzyjnego na sieć podzadań binarnych



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

3.3. Dekompozycja zadania wielodecyzyjnego na sieć
podzadań binarnych

W przypadku złożonych zadań klasyfikacji można spodziewać się sukcesu przy właściwym zastosowaniu algorytmów działających w oparciu o zasadę „dziel i rządź” (ang. divide-and-conquer). Niejednokrotnie w praktyce liczba rozróżnianych klas w zadaniu jest większa od dwóch. Można zatem oczekiwać, że podejście polegające na rozłożeniu zadania wielodecyzyjnego na równoległą sieć klasyfikatorów binarnych (dychotomizerów), a następnie złożeniu ich wyników w celu podjęcia finalnej decyzji, umożliwi dokładniejsze skupienie się na podzadaniach i w konsekwencji doprowadzi do poprawy jakości klasyfikacji.

Schemat dekompozycyjny zadania wielodecyzyjnego ma dwa etapy. W pierw­szym dana próbka jest podawana (równolegle) na wejście wielu osobnych (tj. nie komunikujących się) klasyfikatorów dwudecyzyjnych. W drugim etapie nadawana jest próbce etykieta klasy na podstawie wyjść komponentów sieci.

Wady i zalety takiego podejścia są w dużej mierze analogiczne do wad i zalet innych schematów równoległych. Zasadniczą wadą jest arbitralność wyboru kompo­nentów i metody głosowania (scalania głosów składowych). Komponenty dwudecy­zyjne na ogół działają z niekompletną informacją względem pełnego (oryginalnego) zbioru danych. Utrata informacji polega zazwyczaj na odrzuceniu części próbek (np. ograniczeniu się tylko do dwóch danych klas) lub nadania nowych etykiet elementom zbioru uczącego tak, aby zredukować liczbę klas do dwóch (można w takim przypadku użyć terminu: „superklasy”). Dodatkową wadą podejścia dekompozycyjnego jest zazwyczaj wolniejsza, w stosunku do modelu bazowego, klasyfikacja i uczenie.

Zaletą podejścia jest natomiast osobne uczenie stosowane do klasyfikatorów składowych, np. osobna selekcja cech i osobne szukanie optymalnej wartości k dla k‑NN. Co więcej, niektóre typy klasyfikatorów mogą z natury być przeznaczone do zadań binarnych (np. szukające liniowej rozdzielności klas czy ich podzbiorów), a ich uogólnienie na wiele klas nie jest proste, a zatem schemat dekompozycyjny cechuje się dużą elastycznością. Dodatkową zaletą podejścia są własności samokorygujące (ang. self-correcting) schematu równoległego. Oznaczają one, że pojedynczy klasyfikator może się mylić, ale prawdopodobieństwo, że błędną decyzję podejmie zespół (np. w wyniku prostego głosowania) powinno być mniejsze, gdyż mylne głosy często zostaną przegłosowane.

Schematy dekompozycyjne można podzielić na dwie grupy: te, w których dekompozycja dokonywana jest a priori, tj. bez uwzględniania informacji płynących ze zbioru uczącego, oraz schematy a posteriori, w których topologia sieci powstaje po zapoznaniu się ze zbiorem uczącym. Nietrudno odgadnąć, że schematy z dekompo­zycją a posteriori są bardziej obiecujące.


3.3.1. Algorytm „jedna klasa przeciwko pozostałym”

Zapewne najprostszym schematem dekompozycji zadania wielodecyzyjnego jest algorytm „jedna klasa przeciwko pozostałym” (ang. One-Per-Class, OPC) (Nilsson, 1965). W oryginalnej propozycji każda z c działających równolegle sieci neuronowych uczyła się indywidualnej funkcji binarnej fi, i = 1..c, skojarzonej z i-tą klasą. Klasyfikowana próbka p jest przypisywana do tej klasy j, dla której funkcja fj zwraca największą wartość. W przypadku klasyfikatorów minimalnoodległościowych kompo­nentami OPC są klasyfikatory k-NN wybierające pomiędzy pojedynczą klasą (inną dla każdego z c komponentów) a superklasą powstałą ze scalenia c–1 pozostałych klas. W wyniku finalnej decyzji nieznany obiekt przypisany zostaje do tej z oryginalnych klas, która uczestniczyła w największej liczbie zwycięstw. Łatwo widać, że OPC jest schematem a priori.



W pracy (Moreira i Mayoraz, 1998) porównano kilka schematów dekompozy­cyjnych, gdzie klasyfikatorami składowymi były drzewa decyzyjne C4.5. Schemat OPC wypadł najsłabiej pod względem jakości, nieraz gorzej od oryginalnego klasyfikatora wielodecyzyjnego. Jest to zrozumiałe, gdy zauważy się, że zdolności samokorygujące tego schematu są zerowe. Pomyłka tylko jednego komponentu już może prowadzić do błędnej finalnej decyzji.
3.3.2. Algorytm Jóźwika–Vernazzy

Lepszą koncepcją jest dekompozycja zadania na sieć dychotomizerów, z których każdy rozróżnia tylko pomiędzy parą klas (ang. Pairwise Coupling, PWC). Ponieważ par klas jest , więc tyleż jest komponentów sieci. Decyzja wynikowa powstaje w procesie prostego głosowania. Schemat ten (Rys. 3.2), używany od dawna dla percep­tronów wielowarstwowych (Duda i Hart, 1973), w kontekście klasyfikatorów mini­malnoodległościowych został zastosowany po raz pierwszy w pracy (Jóźwik i Vernazza, 1988).

Schemat PWC został sprawdzony w szeregu prac, m. in. (Moreira i Mayoraz, 1998; Jóźwik, 2001), które dowiodły jego efektywności. W pracy (Grabowski, 2001b) użyto tego schematu dla klasyfikatora k-NCN, również otrzymując poprawę jakości w stosunku do oryginalnej reguły k-NCN. Wyniki eksperymentów autora rozprawy z dekompozycją PWC są zamieszczone w Rozdz. 7.6.



Rys. 3.2. Ogólny schemat dekompozycji PWC zadania c-decyzyjnego


3.3.3. Algorytm Moreiry–Mayoraza

Wadą schematu PWC jest przekazywanie do drugiego etapu (tj. do głosowania) nonsensownych odpowiedzi klasyfikatorów binarnych rozróżniających między pew­nymi klasami i oraz j w przypadku, gdy wejściowa próbka nie należy ani do klasy i, ani do klasy j. Co prawda można oczekiwać, że „odpowiednie” klasyfikatory składowe zazwyczaj „przegłosują” takie przypadkowe głosy, niemniej mamy tu do czynienia z szumem, który w jakimś stopniu negatywnie wpływa na jakość klasyfikacji.

Dość udaną próbą naprawienia tego defektu był algorytm „skorygowany zestaw par klas” (ang. Pairwise Coupling — Correcting Classifiers, PWC-CC) zaproponowany w pracy (Moreira i Mayoraz, 1998). Dla danej próbki p i danego klasyfikatora składo­wego rozróżniającego między klasami i oraz j przeprowadzana jest także pomocniczo klasyfikacja p klasyfikatorem binarnym rozróżniającym między superklasą złożoną z sumy mnogościowej klas i oraz j, a superklasą złożoną ze wszystkich pozostałych klas. Wynikiem opisanej pomocni­czej klasyfikacji jest liczba rzeczywista z przedziału [0, 1], która będzie stanowiła wagę głosu „oryginalnego” klasyfikatora składowego rozróżnia­jącego między parą klas (i, j). Jeśli klasyfikator pomocniczy ma zwracać decyzję ostrą (0 lub 1), to novum schematu PWC‑CC można streścić następująco: jeśli dana próbka wydaje się należeć do klasy i lub j, to wtedy i tylko wtedy głos klasyfikatora „i kontra j” jest uwzględniany.

Jak wi­dać, PWC-CC jest, w przeciwieństwie do dwóch poprzednich algorytmów, schematem a posteriori. W cytowanej pracy przewaga jakości predykcji schematu PWC-CC nad PWC była dość znaczna na kilku zbiorach UCI, przy zastosowaniu drzew decyzyjnych C4.5 jako dychotomizerów. Również praca (Masulli i Valentini, 2000) potwierdza efektywność schematu, tym razem z perceptronami MLP jako składowymi sieci. W Rozdz. 7.6 zamieszczono wyniki autora rozprawy dla schematu PWC-CC wykorzysta­nego w klasyfikatorach minimalnoodległościowych.


3.3.4 Wyjściowe kody samokorygujące (ECOC)

Inną koncepcją schematu dekompozycji było rozważenie „sztucznego” zestawu klasyfikatorów dwudecyzyjnych, mając na uwadze trzy kryteria: łańcuchy binarne („słowa kodowe”, ang. code words) dla różnych klas muszą być maksymalnie odległe w sensie metryki Hamminga; odległości między parami słów kodowych mają być możliwie równe i wreszcie poszczególne klasyfikatory składowe muszą się możliwie różnić przy klasyfikacji różnych klas, gdyż tylko taka różnorodność zapewnia małą korelację między nimi.



Konkretną propozycją utworzenia takiego zestawu słów kodowych był schemat z „wyjściowymi kodami samokorygującymi” (Error-Correcting Output Codes, ECOC) zaproponowany przez Diettericha i Bakiriego (1991). Jako słowa kodowe przyjęto kody samokorygujące BCH (Bose i Ray-Chauduri, 1960), co zagwarantowało utrzymanie minimalnej odległości Hamminga d między słowami (a zatem schemat ECOC potrafi skorygować maksymalnie , d – nieparzyste, błędów klasyfikatorów składowych). W kolejnej pracy tych autorów (Dietterich i Bakiri, 1995), słów kodowych szukano przy pomocy stochastycznej wersji procedury „wspinania się po wzgórzu” (ang. hill climbing). W obu pracach stwierdzono, iż ECOC zwiększa jakość klasyfikacji przy klasyfikatorach działających globalnie (drzewa decyzyjne, np. ID3, C4.5, sieci neuronowe z propagacją wsteczną), natomiast uważano, że schemat ten nie sprawdza się przy klasyfikatorach lokalnych (np. k-NN), z uwagi na dużą korelację między składowymi dychotomizerami. Ricci i Aha (1998) pokazali jednak, że osobna selekcja cech dla poszczególnych klasyfikatorów składowych umożliwia osiągnięcie sukcesu w tym podejściu także przy klasyfikatorach typu 1-NN, o ile dla różnych komponentów zostaną wybrane różne zestawy cech. Co więcej, w cytowanej pracy potwierdzono eksperymentalnie intuicyjne przypuszczenie, iż schemat ECOC przynosi korzyść w tym większym stopniu, im większa jest różnorodność pomiędzy wybranymi zestawami cech. W pracy stwierdzono także, że poprawa jakości w schemacie NN-ECOC okupiona jest nieznacznym wzrostem wariancji wyników.

W pracy (Windeatt i Ghaderi, 2000) pokazano, iż z założenia optymalności (w sensie Bayesa) klasyfikatorów składowych (dychotomizerów działających na super­klasach) i jednakowej odległości Hamminga między wszystkimi parami słów kodowych wynika, iż najlepszą możliwą strategią klasyfikacji — równoważną regule Bayesa — jest wybór klasy najbliższej w sensie odległości Hamminga między odpowiednimi słowami kodowymi.


3.4. Równoległe podejście do problemu selekcji cech

Klasyfikatory minimalnoodległościowe są stabilne, tzn. dodanie lub usunięcie niewielkiej liczby próbek do/ze zbioru uczącego w niewielkim stopniu wpływa na predykcję. Cecha ta odróżnia metodę k-NN (oraz 1-NN z pełnym zbiorem odniesienia) od np. drzew decyzyjnych.

Stabilność klasyfikatora sprawia, iż niełatwo jest wygenerować zespół istotnie różnych (ang. diverse) klasyfikatorów tego typu. Jeśli w zespole nie ma dostatecznej różnorodności, wówczas trudno oczekiwać poprawy klasyfikacji przy kolektywnej predykcji. Argumentowano, iż technika bagging, opisana w Rozdz. 3.2, „nie działa” w połączeniu z regułą k-NN.

Sytuacja nie jest jednak beznadziejna. Jedną z kilku możliwości wygenerowania różnorodnego zespołu klasyfikatorów minimalnoodległościowych jest użycie różnych zestawów cech dla komponentów zespołu. Idea znana jest od kilku lat w kontekście sieci neuronowych (Tumer i Ghosh, 1996; Cherkauer, 1996), natomiast pierwszymi doniesieniami o użyciu różnych zestawów cech w zespołach klasyfikatorów minimalno­odległościowych były powstałe niezależnie prace (Bay, 1998) i (Ho, 1998b). W tym samym okresie Ho opublikowała jeszcze jeden artykuł zawierający opis analogicznej techniki zastosowanej do drzew decyzyjnych (Ho, 1998a). Co ciekawe, w pracach Bay’a i Ho zestawy użytych cech są losowe.

Bay określił swój algorytm etykietą: „wiele podzbiorów cech” (Multiple Feature Subsets, MFS). Ten klasyfikator równoległy z innego punktu widzenia jest de facto niekonwencjonalnym podejściem do problemu selekcji cech. Zamiast wyboru pojedyn­czego zestawu „dobrych” cech, klasyfikator MFS wybiera wiele (w eksperymentach Bay’a aż 100) czysto losowych zestawów cech; liczba cech w każdym zestawie jest jednakowa i zostaje ustalona dla zbioru uczącego przy pomocy walidacji skrośnej lub metody minus jednego elementu zastosowanej z użyciem całego zespołu jako estymatora błędu klasyfikacji. Klasyfikacja nieznanych próbek polega na głosowaniu większościowym klasyfikatorów składowych typu 1-NN, z których każdy uwzględnia jedynie własny zestaw cech. Bay testował dwie wersje algorytmu: z losowaniem cech dla zestawu z powtórzeniami i bez powtórzeń; ponieważ jednak wyniki obu wersji były bardzo zbliżone, autor niniejszej rozprawy postanowił w testach ograniczyć się tylko do bardziej konwencjonalnej wersji bez powtórzeń. Stwierdzono, że klasyfikator jest dość silnie wrażliwy na liczbę cech w zestawie; jeżeli jednak liczba ta jest wybrana przy pomocy zbioru uczącego (a nie zadana ad hoc), wówczas w średnim przypadku można oczekiwać, iż MFS osiągnie wyższą jakość niż takie klasyczne metody selekcji cech jak FSS i BSS, a co więcej, będzie także bardziej odporny na szum.
3.5. Uczenie zestawów cech dla klasyfikatora MFS

W pracy (Grabowski, 2002a) autor rozprawy dokonał modyfikacji wyloso­wanych zbiorów cech dla klasyfikatora równoległego MFS. Stochastyczny charakter procedury selekcji podzbiorów cech, którą opisano poniżej, sugeruje iż otrzymane klasyfikatory składowe nadal będą „do pewnego stopnia” niezależne, podczas gdy ich indywidualne zdolności predykcji zostaną znacząco polepszone w stosunku do zestawów losowych.

Procedura selekcji zestawów cech, którą stosowano, została zainspirowana metodą generacji zbioru zredukowanego Skalaka (Skalak, 1994). Jest to prosta technika probabilistyczna, która w niniejszej wersji wygląda następująco. Na wstępie losowa­nych jest r cech z pełnego zbioru (r – zadane z góry). Następnie w pętli próbuje się dokonywać tzw. mutacji, polegających na odrzuceniu jednej losowej cechy z aktualnego zestawu wybranych cech i jednoczesnym dodaniu jednej losowej cechy ze zbioru wszystkich cech aktualnie nie wybranych. Jeśli wynikiem takiej zamiany jest poprawa jakości klasyfikacji na zbiorze uczącym, estymowana metodą minus jednego elementu, wtedy i tylko wtedy zamianę (=mutację) należy zaakceptować. Iteracja taka powtarza­na jest m razy, gdzie m jest kolejnym wolnym parametrem.

Opisana procedura wykonywana jest L-krotnie i w wyniku otrzymuje się L klasyfikatorów, które będą uczestniczyły w głosowaniu.



Przeprowadzono eksperymenty na parach klas zbioru Ferrites (30 cech). Użyto 10 niezrównoważonych partycji całego zbioru i dla każdej partycji (tj. zbioru uczącego i testowego) w danym teście używano tylko jednej wybranej pary klas. Ponieważ 6 z 8 klas w 1400-elementowych oryginalnych zbiorach uczących liczyło po 200 obiektów, a dwie klasy po 100 obiektów, zatem zbiory uczące w rozważanych zadaniach binarnych liczyły od 200 do 400 obiektów. Tab. 3.1 prezentuje uśrednione po 10 uruchomieniach wyniki (błędy predykcji) dla każdej pary klas oraz czterech algo­rytmów.
Tabela 3.1: Głosowanie zespołów cech
kontra klasyczne strategie selekcji cech (BSS i FSS)




błąd [%]

para
klas

BSS

FSS

MFS,
zbiory losowe
(5 • 5)

zbiory otrzymane dzięki
RMHC
(5 • 5)

1/2

0,81 (5,0)

0,74 (2,4)

1,81

0,64

1/3

0,33 (1,6)

0,10 (1,0)

0,45

0,21

1/4

0,29 (3,1)

0,50 (1,8)

2,53

0,27

1/5

0,16 (1,9)

0,05 (1,0)

0,10

0,03

1/6

8,06 (12,0)

6,03 (16,3)

10,82

6,73

1/7

0,50 (1,3)

0,07 (1,1)

0,42

0,19

1/8

9,42 (10,4)

9,05 (13,8)

8,94

8,54

2/3

3,05 (8,5)

2,90 (6,4)

3,40

2,16

2/4

3,47 (9,5)

3,02 (6,7)

5,85

2,97

2/5

0,64 (3,1)

0,32 (2,7)

0,75

0,51

2/6

0,44 (5,0)

0,59 (5,3)

1,63

0,38

2/7

4,10 (15,5)

2,44 (10,3)

4,24

2,05

2/8

1,18 (6,7)

0,96 (3,7)

1,79

0,61

3/4

1,73 (6,4)

1,04 (3,1)

2,47

0,78

3/5

1,80 (5,3)

1,76 (3,6)

2,21

1,59

3/6

0,19 (1,0)

0,32 (1,0)

0,52

0,07

3/7

9,03 (12,3)

8,70 (16,0)

11,28

8,14

3/8

0,26 (1,2)

0,23 (1,3)

0,76

0,18

4/5

3,69 (9,4)

3,79 (12,1)

3,47

3,46

4/6

0,14 (2,1)

0,15 (1,2)

1,87

0,15

4/7

1,02 (5,0)

0,87 (3,1)

1,12

0,54

4/8

0,12 (3,8)

0,16 (1,5)

2,09

0,09

5/6

0,36 (2,3)

0,05 (1,0)

0,33

0,06

5/7

2,31 (5,6)

2,25 (7,9)

2,28

2,30

5/8

0,35 (1,6)

0,07 (1,0)

0,27

0,19

6/7

0,52 (2,7)

0,35 (1,3)

1,12

0,21

6/8

23,68 (17,2)

19,93 (12,6)

19,99

16,86

7/8

1,02 (4,8)

0,59 (1,6)

2,42

0,54

Pobieranie 6.5 Mb.

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




©operacji.org 2020
wyślij wiadomość

    Strona główna