Politechnika Łódzka



Pobieranie 6.5 Mb.
Strona48/54
Data29.10.2017
Rozmiar6.5 Mb.
1   ...   44   45   46   47   48   49   50   51   ...   54
7.3. Klasyfikatory grafowe

Definicje grafów i indukowanych nimi klasyfikatorów

Oprócz NCN rozważano w literaturze inne przykłady symetrycznego sąsiedztwa (Sánchez i in., 1997a; Zhang i in., 1997). Prawdopodobnie pierwsza definicja tego typu została podana przez O’Callaghana (1975), ale określona została ona tylko dla przestrzeni R2 (uogólnienie na wyższe wymiary nie jest łatwe) i była zależna od aż dwóch wolnych parametrów.

Przyjrzymy się bliżej koncepcji sąsiedztwa grafowego, a konkretniej sąsiedztwa indukowanego dwoma dobrze znanymi grafami bliskości: grafem Gabriela (ang. Gabriel Graph) i grafem pokrewieństwa (ang. Relative Neighborhood Graph). Oba grafy opisane są np. w pracy (Jaromczyk i Toussaint, 1992). Dla oznaczenia grafów będziemy używać skrótów: odpowiednio GG i RNG.



Mówiąc nieformalnie, dwa obiekty uważane są za sąsiadów Gabriela wtedy i tylko wtedy, gdy wnętrze kuli rozpiętej na tych obiektach nie zawiera żadnego obiektu ze zbioru odniesienia. Sąsiedzi Gabriela są w GG połączeni krawędzią. Rys. 7.4 przedstawia sąsiadów Gabriela próbki q, którymi są obiekty 1, 2 i 5.

Rys. 7.4. Sąsiedzi Gabriela próbki q



RNG jest podzbiorem zbioru GG. Kryterium jest bowiem silniejsze: dwa punkty x i ypokrewnymi sąsiadami (ang. relative neighbors) wtedy i tylko wtedy, gdy żaden punkt nie leży bliżej zarówno do x jak i do y niż wynosi odległość od x do y. Na Rys. 7.5 pokrewnymi sąsiadami próbki Q są obiekty o indeksach 1, 5 i 8.

Oryginalnie oba grafy zostały zdefiniowane w metryce euklidesowej, nie widać jednak przeszkód dla rozważania także innych metryk. W rzeczy samej, do ekspery­mentów opisanych niżej autor używał zawsze metryki miejskiej.






Rys. 7.5. Pokrewni sąsiedzi próbki Q



Klasyfikatory indukowane przez GG i RGN (zwane także odpowiednio GGN i RNGN14) zostały zaproponowane w (Sánchez i in., 1997b). Ogólnie mówiąc, klasyfi­kator indukowany przez dany graf znajduje dla danej próbki wszystkich jej m sąsiadów grafowych ze zbioru odniesienia, a następnie przypisuje ją do klasy najliczniej reprezentowanej wśród tych m sąsiadów. Remisy rozstrzygane są arbitralnie (podobnie jak np. przy k-NN; popularnym rozwiązaniem w takiej sytuacji jest przypisanie próbki do najliczniejszej w całym zbiorze klasy spośród klas ex aequo zwycięskich). W testach przeprowadzonych przez Sáncheza i in. klasyfikatory GGN i RNGN zwykle pokonywały k-NN w sensie jakości, a nieraz nawet odnosiły zwycięstwo nad k-NCN. Podobnie jak w przypadku k-NCN, szybkość klasyfikacji może jednak być niestety zbyt mała w niektórych zastosowaniach.
Redukcja sąsiedztwa grafowego

W niniejszym punkcie zaproponowano modyfikację opisanych klasyfikatorów grafowych polegającą na odrzuceniu w czasie klasyfikacji części sąsiadów grafowych danej próbki. Idea autora rozprawy polega na połączeniu obu przedstawionych koncep­cji symetrycznego sąsiedztwa: sąsiedztwa grafowego z regułą k-NCN, ale w zapropo­nowanej wersji lokalnej.

Konkretnie, dla danej próbki znajdowani są jej wszyscy sąsiedzi GG (RNG), a następnie wyłącznie w zbiorze znalezionych sąsiadów grafowych znajdowanych jest sąsiadów scentrowanych (tj. NCN) z k wybieranym lokalnie w taki sposób, aby odległość środka ciężkości rozpatrywanego układu była jak najbliższa testowej próbce. Otrzymany podzbiór używany jest do prostego głosowania w celu otrzymania finalnej etykiety klasy. Można powiedzieć nieformalnie, iż ideą propozycji jest otrzymanie „jeszcze bardziej symetrycznego” sąsiedztwa. Warto zauważyć, że podobnie jak orygi­nalne klasyfikatory grafowe, proponowany schemat również nie wymaga kosztownego uczenia — liczba sąsiadów nie zależy od żadnego współczynnika, ani też nie szacuje się przed klasyfikacją wartości k.

Sánchez i in. (1997b) twierdzą, iż zbyt wielu sąsiadów grafowych (co zdarza się często zwłaszcza z grafem GG) może źle wpłynąć na klasyfikację. Propozycja autora rozprawy redukuje liczbę sąsiadów grafowych z uwzględnieniem kryterium środka ciężkości układu.

Warto zastanowić się nad pewnymi formami przybliżonego sąsiedztwa grafo­wego. Choć jakość klasyfikacji jest pierwszoplanowym kryterium, efektem ubocznym może być większa szybkość klasyfikacji w takich schematach. Ogólny wzorzec otrzy­mania takiego klasyfikatora może wyglądać następująco: 1) wybierz pewną liczbę obiektów, które „wyglądają na dobre kandydatury” na sąsia­dów; 2) zredukuj ten zbiór np. przy użyciu reguły k-NCN z lokalnymi wartościami k; 3) przypisz próbkę testową do klasy najliczniej reprezentowanej w otrzymanym zbiorze.

Hybrydy klasyfikatorów grafowych GGN i RNGN z lokalną regułą k-NCN przedsta­wiono w pracy (Grabowski, 2001b).
Wyniki testów klasyfikatorów grafowych

Przeprowadzono empiryczne porównanie opisanych metod na kilku rzeczywistych zbiorach danych. Dane zostały znormalizowane, używano zawsze metryki miejskiej. Remisy rozstrzygano na korzyść klasy z mniejszym numerem.15

Tab. 7.1 przedstawia błędy klasyfikatorów grafowych na poszczególnych dziesięciu losowych partycjach zbioru Ferrites oraz średnie i odchylenia standardowe błędów. Dla obu klasyfikatorów bazowych zaproponowana idea ograniczania sąsiedz­twa przyniosła zarówno zmniejszenie błędu, jak i jego wariancji.
Tabela 7.1: Błędy (w %) klasyfikatorów grafowych na zbiorze Ferrites

partycja

RNGN

RNGN +
lokalna
k-NCN

GGN

GGN + lokalna
k-NCN

1

10,26

10,06

10,77

9,73

2

11,68

10,99

12,01

9,64

3

10,86

10,57

11,61

9,99

4

10,77

10,53

12,10

9,99

5

10,77

10,30

11,79

9,68

6

11,28

10,55

11,73

9,66

7

10,70

10,64

12,57

9,86

8

11,30

10,88

11,86

9,77

9

10,42

10,28

11,08

9,35

10

11,39

11,39

12,35

10,66

średnia
odch. std.

10,94
0,45

10,62
0,39

11,79
0,54

9,83
0,35

Pobieranie 6.5 Mb.

Share with your friends:
1   ...   44   45   46   47   48   49   50   51   ...   54




©operacji.org 2020
wyślij wiadomość

    Strona główna