Politechnika Łódzka



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


Wyniki drugiego testu prezentuje Tab. 7.2. Są to średnie błędy rozważanych klasyfikatorów na pięciu zbiorach UCI. Dodatkowo skonfrontowano wyniki klasyfika­torów grafowych z wynikami reguły k-NCN (ostatnia kolumna; wyniki k-NCN zostaną powielone w Tab. 7.5a). Tym razem widoczna jest duża rozbieżność wyników, i tak np. zaproponowana idea przynosi wyraźną poprawę jakości dla klasyfikatora GGN na zbiorze Wine, natomiast znacznie pogarsza jakość na zbiorze Pima. Średnie błędy po wszystkich pięciu zbiorach zostały zmniejszone tylko nieznacznie.
Tabela 7.2: Średni błąd (w %) klasyfikatorów grafowych
oraz reguły k-NCN na zbiorach UCI

zbiór


RNGN





RNGN +
lokalna k-NCN

GGN



GGN + lokalna k-NCN


k-NCN


Bupa

38,26

38,09

33,62

35,88

30,38

Glass

29,82

29,72

30,56

27,57

29,92

Iris

6,53

5,20

6,93

5,07

4,40

Pima

29,89

30,62

22,91

28,30

24,48

Wine

4,96

3,50

6,42

2,71

3,16

średnia

21,89

21,43

20,09

19,91

18,47

Oto wnioski, jakie można wysnuć z analizy wyników eksperymentów. Klasyfikatory grafowe są bardzo niestabilne w porównaniu z innymi klasyfikatorami. Choć w niektórych przypadkach jakość oferowana przez zaproponowaną hybrydę GGN z lokalną regułą k-NCN była bardzo dobra (zbiory Glass i Wine), to jednak średnio wszystkie algorytmy grafowe przegrywają z k-NCN i k-NSN (p. Rozdz. 7.6). Tym niemniej, klasyfikatory z tej rodziny mają pewne zalety, które nie pozwalają na odrzucenie całej koncepcji.

Przede wszystkim, klasyfikatory grafowe nie wymagają uczenia, gdyż przy klasyfikacji nie korzystają z żadnego wyuczonego (ani też zadanego ad hoc) parametru. Prostota i elegancja koncepcji powinna również ułatwić analizę zachowania się algorytmu, na co można też spojrzeć od drugiej strony: porównanie danego klasy­fikatora grafowego z innym klasyfikatorem może dać cenną informację o charakterze konkretnego zadania.

Po drugie, wstępne eksperymenty (wyniki nie zamieszczone w rozprawie) sugerują, iż klasyfikatory grafowe są stosunkowo odporne na zbędne cechy — zjawisko to wymaga jednak dokładniejszego zbadania.



7.4. Schemat z głosowaniem dla różnych wartości parametru k

Zaproponowany w niniejszym podrozdziale algorytm jest dość ogólnym schematem klasyfikacji z głosowaniem klasyfikatorów tego samego typu używających do klasy­fikacji pewnej liczby sąsiadów k. Ponieważ w pracy opisano trzy proste reguły decy­zyjne działające w oparciu o głosowanie k sąsiadów (k – niezmienne w obrębie danego zadania), zatem z przedstawionego poniżej wzorca można wyprowadzić trzy konkretne algorytmy, które nazwano voting k-NN (Grabowski, 2002b), voting k-NCN (Grabowski, Jóźwik i Chen, 2003; Grabowski i Sokołowska, 2003) i voting k-NSN (Grabowski, Jóźwik i Chen, 2003).


Klasyfikator voting k-NN

Wadą reguły k-NN w przypadku skończonym jest konieczność wyboru odpowiedniej wartości k, co jest zwykle realizowane przy pomocy metody minus jednego elementu i nie gwarantuje optymalnej jakości klasyfikacji na zbiorze testowym. Innymi słowy, pomimo dużej prostoty nawet reguła k-NN nie jest zabezpieczona przed przeuczeniem, gdyż estymowana optymalna wartość parametru k nie musi naprawdę implikować najlepszej jakości w zadaniu.

Klasyfikator voting k-NN próbuje przezwyciężyć opisaną wadę k-NN poprzez użycie zespołu wielu klasyfikatorów k-NN działających z tym samym zbiorem odniesie­nia, ale z wyselekcjonowanymi osobno wartościami k. Predykcje poszczegól­nych kla­syfikatorów k-NN są uśredniane w wyniku prostego głosowania. Komponenty zespołu uczone są na losowych partycjach całego zbioru uczącego. Nietrudno zauwa­żyć, że pewną wadą schematu w stosunku do zwykłej k-NN jest dłuższy czas uczenia (zjawisko niemal zawsze występujące przy zespołach klasyfikatorów).

W Rozdz. 7.2 podano, iż reguła k-NN może być postrzegana jako klasyfikator równoległy. W pewnym ujęciu zatem, voting k-NN jest klasyfikatorem hierarchicznym, tj. z głosowaniem w dwóch etapach. Przykład działania schematu voting k-NN dla sieci trzech komponentów ukazany jest na Rys. 7.6. Wejściowa próbka zostanie przypisana do klasy „białej”, bo tak wskazują dwa z trzech klasyfikatorów składowych.



Rys. 7.6. Podejmowanie decyzji w schemacie voting k-NN na przykładzie


zespołu trzech klasyfikatorów z wyuczonymi wartościami k równymi 3, 6 i 5
Powstaje pytanie, jak skonstruować (nauczyć) składowe klasyfikatory k-NN, aby zapewnić zarazem pewną ich różnorodność, jak i stosunkowo wysoką jakość klasyfi­kacji. Znaną techniką pozwalającą ocenić jakość klasyfikatora w czasie uczenia (czyli na etapie projektowania) jest podział całego zbioru uczącego na część tzw. Konstruk­cyjną (ang. construction set) oraz część walidacyjną (ang. validation set). Rozważany na etapie projektowania klasyfikator jest uczony na zbiorze konstruk­cyjnym, zaś testowany na zbiorze walidacyjnym. Oczywistą wadą tej techniki jest zmniejszenie się właściwego zbioru uczącego. Wydaje się jednak, iż jest to cena, którą trzeba zapłacić za komfort pewnej oceny klasyfikatora już w fazie uczenia. Powstaje jednak problem: jak podzielić dany zbiór na opisane dwie części? Zbyt mało próbek w zbiorze konstrukcyjnym powoduje bardzo słabą aproksymację rzeczywistego rozkładu prawdo­podobieństw w zadaniu. Z drugiej strony, zbyt niewielki zbiór walida­cyjny oznacza niepewną estymację wygenerowanego klasyfikatora.

Autor rozprawy podjął decyzję, aby podzielić zbiór uczący (odniesienia) na równe części (połowy). Szukano następnie optymalnej wartości k testując wyniki klasyfikacji próbek z części walidacyjnej w odniesieniu do części konstrukcyjnej. Opisany podział zbioru odniesienia przeprowadzony został losowo L razy. W wyniku uczenia komponentów otrzymano wartości k1, ..., kL.

Procedura uczenia zaprezentowana jest także poniżej.
// Tr – zbiór uczący (treningowy)

Dla i=1 ... L // L prób

{

Niech RS(i) = losowy_wybor(rozmiar(Tr) / 2);



// RS(i) – losowy podzbiór Tr

CVS(i) = Tr \ RS(i); // CVS(i) – aktualny zbiór walidacyjny

k(i) = znajdz_optymalne_k(RS(i), CVS(i));

// na zbiorze RS(i) z odniesieniem do zbioru walidacyjnego CVS(i)



}

// wyjście: wyuczone parametry k(1), ..., k(L)


Klasyfikacja próbki q polega na znalezieniu L etykiet klas dla q zgodnie z regułami ki-NN, i=1..L, a następnie przypisaniu q do klasy najliczniej występującej wśród znalezionych etykiet.

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