2212791074

3.2.2. Algorytm CNN

Pierwszą metodą kondensacyjną jest algorytm CNN (ang. condensed nearest neighbor rule). Jest to metoda przyrostowa, w której do początkowo pustego zbioru obiektów referencyjnych przyporządkowywane są nowe wektory. W pierwszym kroku wybierany jest losowo jeden wektor jako prototyp P. W kolejnym kroku sprawdza się czy kolejne wektory należą do zbioru treningowego T pomniejszonego o zbiór P. Jeśli któryś z wektor zostanie błędnie sklasyfikowany to jest on dodawany do zbioru P. Procedura ta jest powtarzana, tak długo, aż wszystkie wektory będą sklasyfikowane poprawnie. Schemat omawianego algorytmu przedstawiony jest na ilustracji 7.[ 10] [11]

Reąuire: T

m <— sizeof{ T)

Pi Xi

flaga <— true while flaga do flaga <— false for i = 1... m do <7(x_f) =fc-NN (P.Xi) if Cfe) ± C(Xi) then P^PUXj;

T <- T \ x* flaga true end if end for end while return P

Rysunek 7 Schemat algorytmu CNN[15].

Metoda CNN została pierwszy raz przedstawiona przez Harta w 1967 roku. W wyniku działania algorytmu CNN jest mniejsza liczba wektorów referencyjnych niż w rozwiązaniu ENN. W metodzie tej nie usuwa się wektorów odstających i brzegowych, co można uznać, jako wadę. Kolejną wadą algorytmu CNN jest losowa inicjalizacja algorytmu, co może skutkować, że wielokrotny start algorytmu daje różne wyniki.[11]

19