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