Politechnika Łódzka



Pobieranie 6.5 Mb.
Strona46/54
Data29.10.2017
Rozmiar6.5 Mb.
1   ...   42   43   44   45   46   47   48   49   ...   54

Rozdział VII

Klasyfikatory oparte na koncepcji
symetrycznego sąsiedztwa

Pojęcie sąsiedztwa (ang. neighborhood) używane jest nie tylko w klasycznym rozpoznawaniu obrazów, ale i w takich — często pokrewnych — dziedzinach, jak „widze­nie” maszynowe (ang. computer vision), geometria wyliczeniowa (ang. computa­tional geometry), przetwarzanie obrazu (ang. image processing) i inne. Ogólnie biorąc, sąsiadami próbki q w d-wymiarowej przestrzeni są obiekty położone blisko q. Sama bliskość (ang. proximity) nie musi być jedyną pożądaną właściwością sąsiedztwa. Wydaje się, iż korzystnie jest, gdy sąsiedzi umiejscowieni są w przestrzeni cech możliwie symetrycznie wokół obiektu q. Reguła k najbliższych sąsiadów ignoruje ów drugi aspekt sąsiedztwa. Jak wiadomo, asymptotyczna optymalność reguły k-NN nie gwarantuje odpowiednio wysokiej jakości klasyfikacji w przypadkach rzeczywis­tych (skończonych). Zatem próby poszukiwań nowych klasyfikatorów, także opartych o kryterium „symetryczności” sąsiedztwa, są uzasadnione.

W niniejszym rozdziale zaprezentowano kilka klasyfikatorów działających z wy­korzystaniem koncepcji symetrycznego sąsiedztwa (ang. surrounding neighborhood), zaczynając od rozwiązań podawanych w literaturze i przechodząc stopniowo do własnych idei autora. Wprowadzono regułę decyzyjną k Near Surrounding Neighbors (k-NSN) (Grabowski, 2002d) będącą rozwinięciem idei klasyfikatora „k scentrowanych sąsiadów” (k-NCN) i optymalizującą jedno­cześnie oba wykorzystywane przez k-NCN kryteria, opisano schematy voting k-NN (Grabowski, 2002b), voting k‑NCN i voting k-NSN (Grabowski, i in., 2003; Grabowski, 2003a) wykorzystujące opracowaną przez autora rozprawy koncepcję głosowania homogenicz­nych (tj. o jednakowej strukturze) klasyfikatorów z różnymi wartościami parametru k, a także zmodyfikowano klasyfikatory grafowe GGN i RNGN poprzez redukcję ich sąsiedztwa przy użyciu kryterium środka ciężkości (Grabowski, 2001b). Zaprezentowano również rodzinę klasyfika­torów kaskado­wych stosujących w pierwszej fazie równoległą sieć klasyfikatorów homogenicznych (np. typu k-NN), zaś w fazie drugiej dokonujących predykcji na bazie symetrycznego sąsiedztwa (Grabowski, 2003a). Wszystkie opisane klasyfikatory zostały przetestowane na wielu zbiorach. Ponadto przetestowano schematy dekompozycji zadań wielodecyzyj­nych: Jóźwik–Vernazza i Moreira–Mayoraz, dla kilku opisywanych klasyfikatorów, czego nawet dla znanej od kilku lat koncepcji k-NCN brakowało w literaturze.


7.1. Reguła decyzyjna k scentrowanych sąsiadów (k-NCN)

Chaudhuri (1996) podał interesującą koncepcję, rozwiniętą później (Sánchez i in., 1997b) do reguły decyzyjnej, skupiającą się na sąsiadach położonych nie tylko blisko danej próbki, ale także rozłożonych możliwie jednorodnie wokół niej. Regułę decy­zyjną, o której mowa, określa się w niniejszej pracy mianem reguły k scentrowanych sąsiadów12 (ang. k Nearest Centroid Neighbors) lub wymiennie oryginalnym skrótem k‑NCN. K scentrowanych sąsiadów próbki q otrzymuje się w sposób następujący:



– pierwszym sąsiadem próbki q jest jej najbliższy sąsiad, oznaczmy go przez n1;

­– i-tym sąsiadem, ni, , jest próbka, dla której centroid (tj. środek ciężkości) zbioru złożonego z ni i wszystkich uprzednio wybranych sąsiadów n1, ..., ni–1 jest położony możliwie najbliżej q.

Rys. 7.1. Reguła k-NCN, k=3. Próbka q zostanie przypisana do klasy „krzyżyków”.


Nietrudno zauważyć, że wybór pierwszego scentrowanego sąsiada nie jest arbitralny, gdyż środek ciężkości zbioru zawierającego tylko jednego sąsiada również jest zminimalizowany (zatem definicję można zapisać zwięźlej, tracąc nieco na przejrzystości). Przykład działania reguły k-NCN dla jest przedstawiony na Rys. 7.1.

Z definicji sąsiadów NCN, jak będziemy wymiennie nazywać scentrowanych sąsiadów wynika, że pod uwagę brany jest również przestrzenny układ rozważanego podzbioru. Z drugiej strony, iteracyjny sposób, w jaki znajdowani są kolejni sąsiedzi gwarantuje ich bliskość względem próbki q.

Eksperymenty przeprowadzone przez Sáncheza i in. (Sánchez i in., 1997b, 1998) zarówno na zbiorach rzeczywistych, jak i sztucznych, potwierdziły atrakcyjność reguły k-NCN, szczególnie w zastosowaniach, gdzie jakość klasyfikacji jest ważniejsza od szybkości. Reguła k-NCN zazwyczaj oferuje wyższą jakość klasyfikacji niż k-NN.

W eksperymentach autora rozprawy (Jóźwik i Grabowski, 2003) reguła k-NCN została także z sukcesem wykorzystana do odszumiania zbioru odniesienia w duchu idei Wilsona (1972) używanej tradycyjnie z regułą k-NN.



Podobnie jak przy k-NN, także dla reguły k-NCN liczba sąsiadów (tj. parametr k) musi być estymowana przy użyciu zbioru uczącego, np. metodą minus jednego ele­mentu.
Idea k-NCN z lokalnie wybieranym k

Zachłanny (ang. greedy) charakter procedury otrzymywania kolejnych sąsiadów w k‑NCN zachęca do prób poszerzenia przestrzeni poszukiwań sąsiadów, stale jednak z uwzględnieniem kryterium środka ciężkości układu. Wydaje się to jednak trudne z uwagi na kryterium bliskości. Idea przedstawiona w niniejszym punkcie jest bardzo prosta: dla danej próbki q znajdowanych jest jej k scentrowanych sąsiadów, a następnie wybierana taka liczba , , pierwszych sąsiadów1, ..., nk(q), aby odległość od centroidu ck(q) do q była zminimalizowana po wszystkich odległościach z centroidów cj, j1, ..., k. Innymi słowy, kryterium środka ciężkości zostaje zminimalizowane lokalnie, co w niewielkim stopniu modyfikuje oryginalną procedurę. Wartość k, będąca w tym wariancie maksymalną liczbą sąsiadów, musi być wyznaczona wcześniej (globalnie, off-line).

Niestety, opisana reguła decyzyjna zawodzi na większości zbiorów danych (z wyjątkiem zbioru Ferrites, gdzie średni błąd lokalnej k-NCN wyniósł 10,17%, tj. praktycznie tyle samo, co dla oryginalnej reguły k-NCN). Podano ją jedynie dlatego, iż idea ta (tj. lokalny wybór liczby sąsiadów przy użyciu kryterium środka ciężkości układu) została jednak z pewnym sukcesem wykorzystana do konstrukcji nowych klasyfikatorów grafowych, opisanych w Rozdz. 7.3.
Pobieranie 6.5 Mb.

Share with your friends:
1   ...   42   43   44   45   46   47   48   49   ...   54




©operacji.org 2020
wyślij wiadomość

    Strona główna