img047

47

4.2. Metoda NN

Algorytm tej metody opiszemy, stosując powszechnie przyjmowaną w literaturze informatycznej notację pascalopodobną. Notacja ta zakłada podporządkowanie zapisu regułom zbliżonym do obowiązujących w języku Pascal, jednak zapis nie jest w ścisłym sensie programem w Pascalu, ponieważ wiele mało istotnych a uciążliwych szczegółów algorytmu zastępuje się słownymi omówieniami. Przy prezentacji tego algorytmu przyjmuje się następujące założenia: zdefiniowane są następujące tablice i zmienne oraz funkcje (w nawiasach podano oznaczenia używane we wzorach):

numclass - liczba rozpoznawanych klas (L), dim - wymiar przestrzeni cech (n), num - liczba obiektów ciągu uczącego (N), sampl[l.. num][l.. dim -fi] - ciąg uczący (t/), rec - identyfikator rozpoznanego obrazu (i), obj[l ..dim] - rozpoznawany obiekt (x).

dist(sampl [k], obj) - funkcja podająca odległość (p) między ib-tym elementem ciągu uczącego a rozpoznawanym obiektem

procodure NNrec (obj, var rec);

begin

rec := 0; min := MaxReal; for k := 1 to num do

if dist(sampl[k], obj) < min then begin

min := dist(sampl(k], obj); rec := sampl[k] [dim-f 1]; end

end

4.3. Metoda aNN

Czysta metoda NN (tak, jak ją przedstawiono) ma liczne wady. Jedną z nich jest jej duża wrażliwość na błędy ciągu uczącego U (rys. 4.3). Istotnie, jeśli błędnie określona zostanie przynależność i^k chociaż jednego elementu x^k ciągu uczącego U, to wówczas całe jego otoczenie będzie błędnie klasyfikowane.