Politechnika Łódzka


Inne klasyfikatory kaskadowe (Grabowski, 2003a)



Pobieranie 6.5 Mb.
Strona52/54
Data29.10.2017
Rozmiar6.5 Mb.
1   ...   46   47   48   49   50   51   52   53   54

Inne klasyfikatory kaskadowe (Grabowski, 2003a)


Szereg następnych zaproponowanych klasyfikatorów można uznać za jedną rodzinę ze względu na identyczny schemat ich konstrukcji. W pierwszym etapie występuje zespół klasyfikatorów, a ich decyzja uważana jest za ostateczną wtedy i tylko wtedy, gdy wszystkie głosy są identyczne. W sytuacji braku jednomyślności używany jest (wolniejszy) klasyfikator drugiego etapu. Ów drugi klasyfikator również może mieć postać równoległą, ale tym razem jednomyślność głosów nie ma już znaczenia.

Proponowane klasyfikatory to:



  • voting k-NN + k-NCN;

  • voting k-NN + k-NSN;

  • voting k-NN + voting k-NCN;

  • voting k-NN + voting k-NSN.

Celem autora rozprawy nie było uzyskanie wyższej jakości klasyfikacji niż ta, którą oferuje klasyfikator z drugiego etapu traktowany pojedynczo. Eksperyment zostaje uznany za pomyślny, jeśli wyniki klasyfikatorów kaskadowych będą porówny­walne z wynikami klasyfikatorów z drugiego etapu, przy założeniu, że do drugiego etapu nie wchodzi znaczący odsetek testowych próbek (np. 50% lub więcej). Ponieważ pierwszy etap jest zazwyczaj przynajmniej kilkakrotnie szybszy niż drugi, więc w opisanej sytuacji otrzymywane jest znaczące przyspieszenie klasyfikacji w stosunku do osobnego klasyfikatora z drugiego etapu.

We wszystkich wyliczonych powyżej schematach kaskadowych pierwszy etap stanowi klasyfikator k-NN z głosowaniem po różnych wartościach k. Zespół takich klasyfikatorów może uzyskać consensus głosów nawet przy pewnym poziomie szumu w otoczeniu testowanej próbki. Zjawisko to ilustruje Rys. 7.7. Mimo iż najbliższym sąsiadem próbki testowej q jest obiekt nr 1 z klasy „kółek” (ewidentnie będący szumem), to jednak istnieje szansa, że odpowiedź wszystkich klasyfikatorów składowych pierwszego etapu klasyfikatora kaskadowego, tj. voting k-NN, będzie identyczna i klasyfikacja zakończy się w pierwszym etapie. Dokładniej, próbka q może być poprawnie sklasyfikowana przez wszystkie L komponenty typu ki-NN pierwszego etapu (tj. przypisana do klasy „krzyżyków”), o ile ki ≥ 3, i = 1..L.


Rys. 7.7. Demonstracja odporności na szum zespołu klasyfikatorów typu voting k-NN


Gdyby pierwszym etapem klasyfikatora kaskadowego była reguła k-NN pojmowana jako klasyfikator równoległy, to znacznie więcej próbek musiałoby przechodzić do drugiego, bardziej kosztownego, etapu.
7.6. Wyniki eksperymentów i dyskusja

Autor niniejszej rozprawy przeprowadził szereg testów opisanych metod na następujących zbiorach danych: Ferrites, Remotes, Bupa, Glass, Iris, Pima i Wine. Porównano następujące algo­rytmy:



  • k-NN;

  • voting k-NN;

  • k-NCN;

  • voting k-NCN;

  • k-NSN (przy różnej liczbie mutacji);

  • voting k-NSN (przy różnej liczbie mutacji);

  • sieć równoległa zbiorów zredukowanych Skalaka + k-NCN;

  • voting k-NN + k-NCN;

  • voting k-NN + k-NSN;

  • voting k-NN + voting k-NCN;

  • voting k-NN + voting k-NSN.

Powyższe algorytmy, z wyjątkiem oryginalnych reguł k-NN i k-NCN, zostały zaproponowane przez autora rozprawy. Ponadto na zbiorach Ferrites i Remotes prze­testowano algorytmy k-NCN i k-NSN w dwóch wariantach dekompozycyjnych: Jóź­wik–Vernazza oraz Moreira–Mayoraz (p. Rozdz. 3.3). Każda para klas uczestniczą­cych w głosowaniu używała w tych algorytmach własnej wyuczonej wartości parametru k.

We wszystkich eksperymentach dane zostały poddane wstępnej standaryzacji (klasycznej, tj. z użyciem odchylenia standardowego), używano zawsze metryki miej­skiej. Remisy rozstrzygano na korzyść klasy z mniejszym numerem.



Tab. 7.3 zawiera wyniki (średnie błędy i odchylenia standardowe z 10 losowych partycji) algorytmów na zbiorze Ferrites. Litery PW w odpowiednich wierszach Tabel 7.3 i 7.4 oznaczają schematy dekompozycyjne (od ang. PairWise).
Tabela 7.3: Średnie i odchylenia standardowe błędów
testowanych klasyfikatorów na zbiorze Ferrites

klasyfikator

średnia [%]

odch. std. [%]

k-NN

10,96

0,77

k-NCN

10,18

0,82

k-NSN, 500 mut.

9,98

0,85

k-NSN, 2500 mut.

9,94

0,86

voting k-NN

10,42

0,56

voting k-NCN

9,96

0,80

voting k-NSN, 500 mut.

9,38

0,87

voting k-NSN, 2500 mut.

9,45

0,84

voting k-NN + k-NCN

9,99

0,88

voting k-NN + k-NSN, 500 mut.

9,88

0,92

voting k-NN + voting k-NCN

9,64

0,80

voting k-NN + voting k-NSN, 500 mut.

9,45

0,84

PW (J–V) k-NN

10,51

0,76

PW (M–M) k-NN

10,24

0,61

PW (J–V) k-NCN

9,66

0,59

PW (M–M) k-NCN

9,76

0,45

PW (J–V) k-NSN, 500 mut.

9,58

0,42

PW (M–M) k-NSN, 500 mut.

9,42

0,43

PW (J–V) k-NSN, 2500 mut.

9,00

0,28

PW (M–M) k-NSN, 2500 mut.

9,12

0,25

Tab. 7.4 przedstawia wyniki dla zbioru Remotes, przy trzech licznościach zbiorów uczących: po 100, 150 i 250 próbek na klasę. Kolejne wiersze zawierają średnie błędy i odchylenia standardowe dla testowanych klasyfikatorów. Ostatnia kolumna jest szacunkowym (rzecz jasna, względnym) określeniem typowej szybkości klasyfikacji danego algorytmu. Określenie szybkości typu „średnia/mała” dla klasyfika­torów kaskadowych oznacza, że szybkość ta zależy od zbioru: jeśli etykiety zdecydowa­nej większość próbek zostaną określone w pierwszym etapie klasyfikacji, to szybkość będzie „średnia”; w przeciwnym razie szybkość ta może być „mała”.



Dodatkowo, na Rys. 7.8 przedstawiono w postaci graficznej różnice średnich błędów między klasyfikatorem k-NN (pojmowanym jako wzorzec odniesienia) a pozo­stałymi testowanymi klasyfikatorami na zbiorze Remotes250. Słupki odpowiadające klasyfikatorom różnych typów („pojedyncze”, typu voting, kaskadowe i z dekompo­zycją na pary klas) zostały oznaczone różnymi odcieniami szarości.
Tabela 7.4: Średnie i odchylenia standardowe błędów testowanych klasyfikatorów na zbiorze Remotes

liczba próbek
na klasę 

100

150

250

szybkość klasyfikacji

klasyfikator




błąd [%]




błąd [%]




błąd [%]

k-NN

śred.

24,81

śred.

23,32

śred.

21,63

średnia

odch. std.

0,65

odch. std.

0,72

odch. std.

0,66

k-NCN

śred.

24,30

śred.

21,97

śred.

20,77

mała

odch. std.

1,18

odch. std.

0,59

odch. std.

0,69

k-NSN, 500 mut.

śred.

23,86

śred.

21,61

śred.

20,53

mała

odch. std.

0,65

odch. std.

0,53

odch. std.

0,83

k-NSN,

2500 mut.



śred.

23,78

śred.

21,81

śred.

20,45

mała

odch. std.

0,76

odch. std.

0,69

odch. std.

0,88

voting k-NN

śred.

24,07

śred.

22,62

śred.

21,08

średnia

odch. std.

0,42

odch. std.

0,74

odch. std.

0,66

voting k-NCN

śred.

23,12

śred.

21,32

śred.

20,11

mała

odch. std.

0,74

odch. std.

0,61

odch. std.

0,56

voting k-NSN,

500 mut.


śred.

22,43

śred.

20,95

śred.

19,73

mała

odch. std.

0,57

odch. std.

0,59

odch. std.

0,62

voting k-NSN,

2500 mut.



śred.

22,62

śred.

21,08

śred.

19,71

mała

odch. std.

0,78

odch. std.

0,59

odch. std.

0,59

voting k-NN +

k-NCN

śred.

23,13

śred.

21,44

śred.

20,03

średnia/mała

odch. std.

0,93

odch. std.

0,47

odch. std.

0,64

voting k-NN +

k-NSN, 500 mut.

śred.

22,88

śred.

21,33

śred.

19,91

średnia/mała

odch. std.

0,76

odch. std.

0,47

odch. std.

0,67

voting k-NN +

voting k-NCN



śred.

22,64

śred.

21,25

śred.

19,83

średnia/mała

odch. std.

0,69

odch. std.

0,58

odch. std.

0,60

voting k-NN +

voting k-NSN, 500



śred.

22,37

śred.

21,02

śred.

19,71

średnia/mała

odch. std.

0,53

odch. std.

0,57

odch. std.

0,55

PW (J–V)

k-NCN

śred.

23,51

śred.

21,71

śred.

20,34

bardzo mała

odch. std.

0,60

odch. std.

0,92

odch. std.

0,79

PW (M–M)

k-NCN

śred.

22,98

śred.

21,13

śred.

19,90

bardzo mała

odch. std.

0,66

odch. std.

0,66

odch. std.

0,58

PW (J–V)

k-NSN, 500 mut.

śred.

22,70

śred.

21,15

śred.

19,87

bardzo mała

odch. std.

0,82

odch. std.

0,60

odch. std.

0,66

PW (M–M)

k-NSN, 500 mut.

śred.

22,55

śred.

20,89

śred.

19,68

bardzo mała

odch. std.

0,81

odch. std.

0,80

odch. std.

0,53

PW (J–V)

k-NSN, 2500 mut.

śred.

22,42

śred.

20,74

śred.

19,42

bardzo mała

odch. std.

0,87

odch. std.

0,70

odch. std.

0,59

PW (M–M)

k-NSN, 2500 mut.

śred.

22,67

śred.

20,89

śred.

19,65

bardzo mała

odch. std.

0,70

odch. std.

0,62

odch. std.

0,54

Tab. 7.5a, b i c przedstawiają średnie błędy algorytmów na pięciu zbiorach UCI. Metodologia testów w tym przypadku była nieco inna. Pięć razy przeprowadzono 5‑krotną walidację skrośną (ang. 5-fold cross validation), a zatem błędy w Tabelach są średnimi z 25 otrzymanych dla każdej pary (zbiór, klasyfikator) wyników. Dodatkowo przetestowano wspomnianą w Rozdz. 7.2 wersję k-NSN z głosowaniem po pięciu znalezionych różnych sąsiedztwach NSN (z tą samą jednak wartością k), oznaczaną w tabelach przez vk-NSN. Dla zbiorów UCI nie przetestowano wersji dekompozycyj­nych J–V i M–M, gdyż największe z tych zbiorów, tj. Pima i Bupa, przedstawiają zadania dwudecyzyjne, zaś pozostałe zbiory są dość małe (ok. 200 obiektów lub mniej), a zatem niebezpieczeństwo przeuczenia jest znaczne. Co więcej, 216-elementowy zbiór Glass złożony jest aż z sześciu klas.



Rys. 7.8. Bezwzględne różnice średniego błędu między klasyfikatorem k-NN
a pozostałymi testowanymi klasyfikatorami na zbiorze Remotes250.
Większe wartości oznaczają wyższą jakość danego klasyfikatora

Tabela 7.5a: Średnie błędy (w %) klasyfikatorów „pojedynczych” na zbiorach UCI






1

2

3

4

5

zbiór

k-NN

k-NCN

k-NSN, 100

k-NSN, 500

k-NSN, 2500

Bupa

35,54

30,38

30,90

31,48

33,16

Glass

28,80

29,92

28,62

28,06

28,06

Iris

5,87

4,40

4,67

4,93

4,93

Pima

24,73

24,48

24,22

24,95

25,42

Wine

3,04

3,16

2,82

2,26

2,37

średnia

19,60

18,47

18,25

18,34

18,79

Tabela 7.5b: Średnie błędy (w %) klasyfikatorów z głosowaniem


po różnych wartościach k na zbiorach UCI




6

7

8

9

10

zbiór

voting k-NN

voting k-NCN

voting
k-NSN, 100

voting
k-NSN, 500

voting
k-NSN, 2500

Bupa

34,20

30,43

30,49

30,78

32,75

Glass

28,43

28,69

25,99

26,18

26,18

Iris

5,47

4,00

4,13

3,87

4,67

Pima

24,71

24,16

24,53

24,16

24,37

Wine

3,37

2,36

2,03

2,36

2,37

średnia

19,24

17,93

17,43

17,47

18,07

Duża ilość zgromadzonych wyników utrudnia ich analizę. Aby ułatwić tę czynność, w oparciu o dane z Tabel 7.5a–c policzono dla poszczególnych algorytmów sumy rang na poszczególnych zbiorach. Algorytm o najmniejszym średnim błędzie dla danego zbioru otrzymał rangę 0, drugi pod względem jakości algorytm — rangę 1 itd. W przypadku remisów, rangi były równe, np. jeśli na danym zbiorze pewne dwa algorytmy osiągnęły najwyższą jakość, to otrzymywały one rangę 0,5. W Tab. 7.6 podane są rangi poszczególnych metod na pojedynczych zbiorach UCI (kolumny 2–6) oraz ich sumy (kolumna 7). Dodatkowo w kolumnie 8 podano ogólną rangę metody, zaczynając numerację od 1.


Tabela 7.5c: Średnie błędy (w %) klasyfikatorów kaskadowych
oraz wersji k-NSN z głosowaniem na zbiorach UCI




11

12

13

14

15

16

17

18

zbiór

5·Skalak
+
k-NCN

voting
k-NN + k-NCN

voting
k-NN + voting k-NCN

voting
k-NN + k-NSN, 500

voting
k-NN + voting k-NSN, 500

vk-NSN, 100

vk-NSN, 500

vk-NSN, 2500

Bupa

31,19

30,84

30,78

30,67

30,96

31,42

30,67

32,99

Glass

28,04

28,60

28,04

27,50

26,46

28,25

28,43

28,25

Iris

4,53

4,53

4,27

4,80

4,53

4,53

4,67

4,93

Pima

24,11

23,90

24,14

23,98

24,11

24,43

24,58

24,61

Wine

3,03

2,26

1,92

1,92

2,14

3,04

2,48

2,03

średnia

18,18

18,03

17,83

17,77

17,64

18,33

18,17

18,56

Tabela 7.6: Rangi testowanych algorytmów: zbiorcze i na poszczególnych zbiorach danych



1

2

3

4

5

6

7

8

zbiór danych ►
algorytm ▼


Bupa

Glass

Iris

Pima

Wine

suma
rang


ranga metody

k-NN

17

16

17

15

14,5

79,5

18

k-NCN

0

17

4

10

16

47

10

k-NSN, 100

8

14

10

7

12

51

13

k-NSN, 500

12

7,5

14

16

5,5

55

15

k-NSN, 2500

15

7,5

14

17

9,5

63

16

voting k-NN

16

11,5

16

14

17

74,5

17

voting k-NCN

1

15

1

5,5

7,5

30

6

voting k-NSN, 100

2

0

2

11

2,5

17,5

1

voting k-NSN, 500

5,5

1,5

0

5,5

7,5

20

3

voting k-NSN, 2500

13

1,5

10

8

9,5

42

9

5 · Skalak + k-NCN

10

5,5

6,5

2,5

13

37,5

8

voting k-NN + k-NCN

7

13

6,5

0

5,5

32

7

voting k-NN +
voting k-NCN

5,5

5,5

3

4

0,5

18,5

2

voting k-NN +
k-NSN, 500

3,5

4

12

1

0,5

21

4

voting k-NN +
voting k-NSN, 500

9

3

6,5

2,5

4

25

5

vk-NSN, 100

11

9,5

6,5

9

14,5

50,5

12

vk-NSN, 500

3,5

11,5

10

12

11

48

11

vk-NSN, 2500

14

9,5

14

13

2,5

53

14

Sumy rang przetestowanych algorytmów są dodatkowo zaprezentowane w formie graficznej na Rys. 7.9.



Drugim podstawowym kryterium oceny klasyfikatora, obok jakości klasyfikacji, jest jej szybkość. W przypadku klasyfikatorów hybrydowych pewną miarą szybkości jest odsetek próbek rozstrzyganych w każdym etapie. Dodatkowo, warto zwrócić uwa­gę na błędy predykcji w pierwszym oraz drugim etapie. Tab. 7.7a i 7.7b przedsta­wiają statystyki dotyczące klasyfikatorów „5 · Skalak + k-NCN” oraz „voting k-NN + voting k‑NSN”, tj. odpowiednio średnio najgorszego i najlepszego, w sensie jakości predykcji, spośród zaproponowanych klasyfikatorów kaskadowych.
Tabela 7.7a: Statystyki dotyczące klasyfikatora kaskadowego „5·Skalak + k-NCN”

zbiór

błąd
ogółem [%]


% próbek
w II etapie


błąd
w I etapie [%]


błąd
w II etapie [%]


Bupa

31,19

67,07

27,64

32,93

Glass

28,04

47,48

11,03

46,85

Iris

4,53

9,33

1,47

34,29

Pima

24,11

40,10

14,65

38,25

Wine

3,03

12,36

0,26

22,73

Ferrites

10,10

19,38

4,59

33,05

Remotes100

20,55

38,51

10,55

36,51

średnia

17,36

33,46

10,03

34,94


Rys. 7.9. Sumy rang poszczególnych metod na zbiorach UCI.


Mniejsze wartości są korzystniejsze.
Tabela 7.7b: Statystyki dotyczące klasyfikatora kaskadowego
voting k-NN + voting k-NSN (500 mutacji)

zbiór

błąd
ogółem [%]


% próbek
w II etapie


błąd
w I etapie [%]


błąd
w II etapie [%]


Bupa

30,96

50,96

25,86

34,93

Glass

26,46

34,11

17,32

43,27

Iris

4,53

5,73

2,98

32,14

Pima

24,11

19,19

20,29

40,00

Wine

2,14

5,84

0,47

30,80

Ferrites

9,88

13,84

4,75

42,16

Remotes100

22,88

26,03

15,56

43,67

Średnia

17,28

22,24

12,46

38,14

Analiza wyników zaprezentowanych w tym podrozdziale pozwala na wyciągnię­cie kilku spostrzeżeń.



  • Należy zauważyć, że średnio najniższą jakość klasyfikacji osiągnęła oryginalna reguła k-NN. Fakt ten z badawczego punktu widzenia oznacza, iż konstrukcja całkowicie nowych typów klasyfikatorów nie jest jałowym zajęciem.

  • Niektóre klasyfikatory są mało stabilne na tle konkurencji. Przykładowo, klasyfikator k-NCN osiąga najlepszy wynik na zbiorze Bupa, natomiast najgorszy na zbiorze Glass. Praktyczną trudnością jest także odpowiedni wybór liczby mutacji dla klasyfikatora k-NSN (również w wersji z głosowaniem po wielu wartościach k).

  • Wszystkie algorytmy z głosowaniem po wielu wartościach k osiągają zazwyczaj wyższą jakość klasyfikacji od swych pierwowzorów (np. voting k-NN jest przeważnie lepsza od oryginalnej k-NN itd.). Godny podkreślenia jest fakt, iż metody te są niewiele wolniejsze od wersji oryginalnych (w przypadku reguły voting k-NN, spowolnienie w stosunku do k-NN jest wręcz marginalne w typowym przypadku).

  • Klasyfikatory kaskadowe cechują się korzystnym kompromisem między jakością a szybkością klasyfikacji. Jak wynika z Tabel 7.7, średnio ok. 70% predykcji próbek jest dokonywanych w pierwszym etapie (dla szybszego klasyfikatora pierwszego etapu, jakim jest sieć równoległa zbiorów zredukowanych Skalaka, odsetek ten jest nieco mniejszy, natomiast zbliża się do 80% dla klasyfikatorów korzystających z voting k-NN w pierwszej fazie). Wartości te są jednak mocno uzależnione od zbioru danych. Zauważyć trzeba, iż użyte kryterium podejmo­wania decyzji silnie dyskrymi­nuje zbiory próbek testowych: ogólnie mówiąc, próbki „łatwe” (średnie błędy niewiele ponad 10%) są rozstrzygane w pierwszym etapie, próbki „trudne” (błędy ok. 35%–40%) obsługiwane są przez klasyfikator drugiego etapu. Własność ta jest korzystna, gdyż oznacza, iż klasyfikator może z sukcesem dobierać złożoność (tj. koszt czasowy) reguły decyzyjnej w zależności od stopnia trudności zadanej próbki.

  • Dekompozycja zadania wielodecyzyjnego na sieć dychotomizerów wydaje się jedną z ważniejszych technik poprawy jakości klasyfikacji. Prawdopodobnie lepszym z dwóch przetestowanych schematów jest algorytm Moreiry–Mayoraza, jednak silniejsze stwierdzenie wymaga przeprowadzenia większej liczby eksperymentów.

W najnowszej pracy autor rozprawy zaproponował jeszcze jeden klasyfikator kaskadowy (Grabowski, 2003b), tym razem oparty wyłącznie na zespołach zbiorach zredukowanych, z wykorzystaniem idei zawierania się zbiorów i jednomyślnego głoso­wania. Otrzymane wyniki pozwalają na przypuszczenie, że klasyfikator ten oferuje lepszy kompromis pomiędzy szybkością klasyfikacji a trafnością predykcji niż pojedyn­czy zespół zbiorów zredukowanych. Co więcej, algorytm ten można w naturalny sposób rozbudować dodając dalsze fazy klasyfikatora kaskadowego; wstępne wyniki (dotąd nieopublikowane) są bardzo obiecujące.

Dalsze plany badawcze autora obejmują także implementację i testy szereg innych hybryd kaskadowych, implementację wersji dekompozycyjnych rozważanych klasyfi­katorów oraz większe zróżnicowanie decyzji dotyczącej dalszej klasyfikacji w zależ­ności od odpowiedzi zespołu klasyfikatorów pierwszego etapu.


Pobieranie 6.5 Mb.

Share with your friends:
1   ...   46   47   48   49   50   51   52   53   54




©operacji.org 2020
wyślij wiadomość

    Strona główna