3582277769

2. TEORIA 21 Klasyfikator k-NajbUższych Sąsiadów

Jedną z najprostszych i najistotniejszych metod klasyfikacji jest zastosowanie algorytmu K-najbliższych sąsiadów (fc Nearest Neighbours. kNN). Algorytm ten zdobył swoją popularność dzięki wysokiej interpretowalności, prostocie implementacji oraz szerokim zastosowaniu w dziedzinach eksploracji danych i klasyfikacji[10].

21.1 Działanie klasyfikatora

Podstawowym założeniem klasyfikatora jest twierdzenie, że podobne problemy można rozwiązać w podobny sposób. Posiadając wiedzę na temat rozwiązania najbardziej podobnego problemu, stosujemy ją w celu rozwiązania nowego problemu. W ten sposób uzyskać można działanie algorytmu 1NN.

W przypacku zastosowania k-NN. algorytm opiera się na podobieństwie problemu do jego k najbliższych przypadków w zbiorze trenującym oraz wyprowadzeniu rozwiązania z technik rachunku prawdopodobieństwa.

Klasyfikacja konkretnego problemu (danej będącej wektorem znajdującym się w wielowymiarowej przestrzeni) polega na wyznaczeniu k przypadków będących najbardziej podobnych do danych klasyfikowanych pod względem określonej miary podobieństwa. Przykładowymi miarami(odległościami) stosowanymi w algorytmie k Nearest Neighbours mogą byćCSJ:

•    Metryka euklidesowa

d_e(x,y) = V(yi- x_t)² + ...+(y_n-x_n)²    (2.1)

•    Metryka Manhattan

d_m(x,y) = £2=i \x_k-y_k\    (2.2)

•    Metryka Czebyszewa

d_Ch(x,y) = lim(I?= i \xi — D”    (2-3)

m-*a>

• Podobieństwo cosinusowe

d_c(A,B)

Sili AjBj JE!!., Affa., Bf

(2.4)

Ostatnim etapem klasyfikacji jest zdefiniowanie do jakiej klasy przynależy problem wejściowy. W tym celu stosuje się między innymi metody[9]:

•    lnverse Distance Voting (Metoda Sheparda) • Obliczana jest suma odwróconych odległości pomiędzy wybranych k sąsiadów a analizowanym problemem.

•    Majority Voting • Klasa problemu jest określana na podstawie największej przynależności k znalezionych sąsiadów

11