k - NN
Wprowadzenie
Algorytm k-najbliższych sąsiadów, znany również jako KNN lub k-NN, jest nieparametrycznym, nadzorowanym klasyfikatorem uczenia się, który wykorzystuje bliskość do dokonywania klasyfikacji lub przewidywań dotyczących grupowania poszczególnych punktów danych. W przypadku klasyfikacji etykieta klasy jest przypisywana na podstawie głosowania większościowego, tzn. używana jest etykieta, która jest najczęściej reprezentowana wokół danego punktu danych.
Schemat k-NN
Podsumowując, celem algorytmu k-najbliższego sąsiada jest zidentyfikowanie najbliższych sąsiadów danego punktu, aby możliwe było przypisanie etykiety klasy do tego punktu
library(kknn)
library(ggplot2)
load("C:/Users/mbuko/OneDrive/Dokumenty/credit.RData")Przygotowanie danych
Zmienne porządkowe
Analiza z wykorzystaniem klasyfikacji k-NN została przeprowadzona na
podstawie wszystkich zmiennych ilościowych i jakościowych ze zbioru
danych credit. W ramach przygotowania danych wskazano
zmienne o charakterze porządkowym, do których zaliczono: stan konta
czekowego, oszczędności i staż pracy.
levels(credit$konto_czekowe)## [1] "< 0" ">200" "0-200" "brak"credit$konto_czekowe <- factor(
x = credit$konto_czekowe,
levels = c("< 0", "brak", "0-200",">200"),
ordered = T
)
levels(credit$oszczednosci)## [1] "<100" ">1000" "100-500" "500-1000" "brak"credit$oszczednosci <- factor(
x = credit$oszczednosci,
levels = c( "brak" , "<100", "100-500", "500-1000" ,">1000" ),
ordered = T
)
levels(credit$staz_pracy)## [1] "<1 rok" ">7" "1-4" "4-7" "bezrobotny"credit$staz_pracy <- factor(
x = credit$staz_pracy,
levels = c("bezrobotny", "<1 rok", "1-4" , "4-7", ">7" ),
ordered = T
)
levels(credit$oszczednosci)## [1] "brak" "<100" "100-500" "500-1000" ">1000"levels(credit$staz_pracy)## [1] "bezrobotny" "<1 rok" "1-4" "4-7" ">7"class(credit$konto_czekowe) # ordered factor - aby funkcja dobrze liczyła odległości## [1] "ordered" "factor"str(credit)## 'data.frame': 1000 obs. of 21 variables:
## $ konto_czekowe : Ord.factor w/ 4 levels "< 0"<"brak"<"0-200"<..: 1 3 2 1 1 2 2 3 2 3 ...
## $ czas : int 6 48 12 42 24 36 24 36 12 30 ...
## $ historia : Factor w/ 5 levels "brak","istniejace_spł",..: 3 2 3 2 4 2 2 2 2 3 ...
## $ cel : Factor w/ 10 levels "AGD","biznes",..: 8 8 3 5 9 3 5 10 8 9 ...
## $ kwota : int 1169 5951 2096 7882 4870 9055 2835 6948 3059 5234 ...
## $ oszczednosci : Ord.factor w/ 5 levels "brak"<"<100"<..: 1 2 2 2 2 1 4 2 5 2 ...
## $ staz_pracy : Ord.factor w/ 5 levels "bezrobotny"<"<1 rok"<..: 5 3 4 4 3 3 5 3 4 1 ...
## $ rata_%doch : int 4 2 2 2 3 2 3 2 2 4 ...
## $ plec : Factor w/ 2 levels "K","M": 2 1 2 2 2 2 2 2 2 2 ...
## $ poreczyciel : Factor w/ 2 levels "brak","tak": 1 1 1 2 1 1 1 1 1 1 ...
## $ zamieszkanie : int 4 2 3 4 4 4 4 2 4 2 ...
## $ zabezpieczenie: Factor w/ 4 levels "brak","nieruchomosc",..: 2 2 2 4 1 1 4 3 2 3 ...
## $ wiek : int 67 22 49 45 53 35 53 35 61 28 ...
## $ inne_zobow : Factor w/ 3 levels "bank","brak",..: 2 2 2 2 2 2 2 2 2 2 ...
## $ rodzaj_miesz : Factor w/ 3 levels "czynsz","wlasne",..: 2 2 2 3 3 3 2 1 2 2 ...
## $ l_kredytow : int 2 1 1 1 2 1 1 1 1 2 ...
## $ kwalifikacje : Factor w/ 4 levels "niewykwal_nierez",..: 3 3 2 3 3 2 3 4 2 4 ...
## $ l_osob : int 1 1 2 2 2 2 1 1 1 1 ...
## $ telefon : Factor w/ 2 levels "brak","tak": 2 1 1 1 1 2 1 2 1 1 ...
## $ obcokrajowiec : Factor w/ 2 levels "nie","tak": 2 2 2 2 2 2 2 2 2 2 ...
## $ jakosc : Factor w/ 2 levels "dobry","zly": 1 2 1 1 2 1 1 1 1 2 ...Podział danych na zbiór uczący i testowy
W ramach przygotowania zbiór danych podzielono na zbiór uczący i zbiór testowy w proporcji 75% - 25%.
set.seed(121) # for reproducibility
random <- sample(1:nrow(credit), 0.75 * nrow(credit))
data_train<-credit[random, ]
data_test <- credit[-random, ]Normalizacja
Aby określić, które obiekty znajdują się najbliżej danego punktu zapytania, należy obliczyć odległość między punktem zapytania a innymi obiektami ze zbioru danych. Istnieje kilka miar odległości. Najczęściej stosowana jest ogólna odległość potęgowa/Minkowskiego:
\[ d_{x,y} = (\sum_{i=1}^n|x_{i} - y_{i}|)^{1/p} \]
Aby obliczyć odległość między obiektami zmienne powinny być wyrażone na tej samej skali. Z tego względu należy dokonać normalizacji.
Normalizację zmiennych ilościowych przeprowadzono poprzez ich standaryzację Wartość po standaryzacji x’ może zostać obliczona ze wzoru: \[ x' = \frac{x - \mu}{\sigma} \]
Następnie zmienne \(v_{i}\) są normalizowane poprzez podzielenie przez przeciętne odchylenie standardowe zmiennych oraz przeważone przez odwrotność liczby wariantów (m):
\[ v^{'}_{i}= \frac{v_{i}}{\sqrt{\frac{1}{m}\sum_{i=1}^m s^2(v_i)}}\frac{1}{m} \]
Klasyfikacja
Model k-NN dla k = 5
Bo budowy modelu wykorzystano funkcję kknn z pakietu
kknn. Jednym z wymaganych parametrów, które muszą być
określone jest k - liczba obiektów, na podstawie których
następuje przypisanie nowych obiektów do odpowiednich klas. W zalezności
od przyjetej liczby k dokładność klasyfikacji może być różna.
Poniżej przedstawiono wyniki klasyfikacji prz k=5.
knn.5 <- kknn(formula = jakosc ~ .,
train=data_train, test=data_test,
k = 5,
distance = 2,
kernel = "rectangular",
scale = T)
head(knn.5$fitted.values, 15)## [1] dobry zly dobry dobry dobry dobry dobry dobry dobry dobry dobry dobry
## [13] zly dobry dobry
## Levels: dobry zlyocena jakości za pomocą macierzy błędnych klasyfikacji i wielkości błędu
table(
przewidywane = knn.5$fitted.values,
rzeczywiste = data_test$jakosc)## rzeczywiste
## przewidywane dobry zly
## dobry 153 63
## zly 13 21mean(data_test$jakosc != knn.5$fitted.values)## [1] 0.304Optymalne parametry modelu
Obliczona wielkość błędu klasyfikacji jest równa 0.304. Zastoswanie
funkcji train.kknn daje możliwość zwiększenia dokładności
klasyfikacji poprzez zmianę parametrów funkcji:
- k - liczba sasiadów - w obliczeniach przyjęto
liczbę k od 1 do 31, co 2;
- kernel - sposób ważenia głosów w zależności od
odległości sąsiadów. Możliwe parametry funkcji to
“rectangular”, “triangular”, “epanechnikov”, “biweight”,
“triweight”, “cos”, “inv”, “gaussian”, “rank”, “optimal”;
- distance - parametr p przy obliczaniu odległości Minkowskiego. W obliczeniach przyjęto p = 1, 2 i 3.
accurency<-data.frame(matrix(ncol = 10, nrow = 0))
colnames(accurency)<-c( "rectangular", "triangular", "epanechnikov", "biweight", "triweight", "cos",
"inv", "gaussian", "rank", "optimal")
for (i in 1:3) {
knn.cv <- train.kknn(
formula = jakosc ~ .,
data = data_train,
# kmax = 15,
ks = seq(1, 31, 2),
distance = i,
kernel = c( "rectangular", "triangular", "epanechnikov", "biweight", "triweight", "cos",
"inv", "gaussian", "rank", "optimal"))
accurency<-rbind(accurency, as.data.frame(knn.cv$MISCLASS))
}
accurency$k<-rep(seq(1, 31, 2),3)
accurency$i<-c(rep(1, 16), rep(2, 16), rep(3, 16))
accurency<-as.matrix(accurency)
head(accurency)## rectangular triangular epanechnikov biweight triweight cos inv
## 1 0.3053333 0.3053333 0.3053333 0.3053333 0.3053333 0.3053333 0.3053333
## 3 0.2826667 0.2933333 0.2973333 0.2973333 0.2973333 0.2933333 0.2853333
## 5 0.2626667 0.2866667 0.2866667 0.2986667 0.3026667 0.2893333 0.2640000
## 7 0.2640000 0.2720000 0.2666667 0.2906667 0.3000000 0.2720000 0.2613333
## 9 0.2466667 0.2613333 0.2586667 0.2773333 0.2893333 0.2600000 0.2453333
## 11 0.2520000 0.2480000 0.2480000 0.2733333 0.2893333 0.2453333 0.2480000
## gaussian rank optimal k i
## 1 0.3053333 0.3053333 0.3053333 1 1
## 3 0.2826667 0.2773333 0.3053333 3 1
## 5 0.2626667 0.2746667 0.2866667 5 1
## 7 0.2613333 0.2640000 0.2800000 7 1
## 9 0.2466667 0.2533333 0.2626667 9 1
## 11 0.2493333 0.2480000 0.2560000 11 1Wyszukanie w macierzy najmniejszej wielkości błędów.
which(accurency == min(accurency), arr.ind = TRUE)## row col
## 131 23 7
## 131 23 8Prezentacja graficzna wyników obliczeń w zależności od parametrów funkcji.
accurency<-as.data.frame(accurency)
for(j in 1:10) {
print(
ggplot(accurency, aes(x = k, y = accurency[ ,j],
col = as.factor(accurency$i))) +
geom_line()+
ylab("błędne klasy") +
ggtitle(colnames(accurency)[j])+
labs(color='i')
)
print(colnames(accurency)[j])
Sys.sleep(3)
}
## [1] "rectangular"
## [1] "triangular"
## [1] "epanechnikov"
## [1] "biweight"
## [1] "triweight"
## [1] "cos"
## [1] "inv"
## [1] "gaussian"
## [1] "rank"
## [1] "optimal"Model k-NN przy optymalnych parametrach
Postać modelu
Przedstawione wyniki wskazują, iż najlepszy model uzyskać można przy następujacych wartościach parametrów:
- k = 13,
- distance = 2,
- kernel = “gaussian”.
Wyniki obliczeń przedstawiono poniżej
knn <- kknn(formula = jakosc ~ .,
train=data_train,
test=data_test,
k = 13,
distance = 2,
kernel = "gaussian",
scale = T
)
macierz_kNN<-table(
przewidywane = knn$fitted.values,
rzeczywiste = data_test$jakosc)
macierz_kNN## rzeczywiste
## przewidywane dobry zly
## dobry 161 66
## zly 5 18mean(data_test$jakosc != knn$fitted.values) # błąd dla modelu## [1] 0.284Ocena modelu w porównaniu z klasyfikacją 0R
Obliczony procent błędnych klasyfikacji może być porównany z procentem złych klas przy przyjęciu założenia, że wszystkie nowe obiekty posiadają klasę częściej występującą w zbiorze testowym:
macierz_0R<-table(data_test$jakosc)
macierz_0R##
## dobry zly
## 166 84sum(data_test$jakosc == "zly")/nrow(data_test) #błąd przy klasyfikacji 0R## [1] 0.336Precyzja, czułość, miara F
Wzory dotyczące tych parametrów oceny znajdują się w dokumencie metody5.
- Precyzja to liczba wartości prawidłowo
sklasyfikowanych jako pozytywne (TP) przez sumę wszystkich wartości
sklasyfikowanych jako pozytywnie (również tych błędnie sklasyfikowanych
jako pozytywne). W efekcie dowiadujemy się, ile wśród przykładów
sklasyfikowanych jako pozytywne jest rzeczywiście pozytywnych.
- czułość oznacza udział prawidłowo sklasyfikowanych
przypadków pozytywnych (TP) wśród wszystkich przypadków pozytywnych
(również tych, które błędnie zostały zaklasyfikowane do negatywnych –
FN). Warto pamiętać, że jeśli algorytm nie zaklasyfikuje żadnego
pozytywnego przypadku błędnie (czyli nic nie trafi do kategorii FN), to
czułość będzie wynosić 1.
- miara F to średnia harmoniczna pomiędzy precyzją (precision) i czułością (recall). Im bliższa jest jedynki, tym lepiej to świadczy o algorytmie klasyfikującym.
Poniżej przedstawiono obliczenia dla modelu k-NN i 0R.
precyzja_kNN <- macierz_kNN[1,1]/(macierz_kNN[1,1]+macierz_kNN[1,2])
precyzja_kNN## [1] 0.7092511czulosc_kNN <-macierz_kNN[1,1]/(macierz_kNN[1,1]+macierz_kNN[2,1])
czulosc_kNN## [1] 0.9698795miaraF_kNN<-2/(1/precyzja_kNN+1/czulosc_kNN)
miaraF_kNN## [1] 0.8193384precyzja_0R <- macierz_0R[1]/(macierz_0R[1]+macierz_0R[2])
precyzja_0R## dobry
## 0.664czulosc_0R <-macierz_0R[1]/(macierz_0R[1])
czulosc_0R## dobry
## 1miaraF_0R<-2/(1/precyzja_0R+1/czulosc_0R)
miaraF_0R## dobry
## 0.7980769Porównanie modeli przy różnych kosztach błędu
Ocena jakości modelu może zostać ptrzeprowadzona nie tylko na podstawie dokładności klasyfikacji, ale także na podstawie kosztów błędów wynikających z niewłaściwej klasyfikacji. Przykładowo z punktu widzenia banku koszt akceptacji wniosku, który powinien zostać odrzucony może być dwa razy większy od kosztu nieprzyznania kredytu osobie, która byłaby dobrym kredytobiorcą. (Bank więcej traci dając kredyt tym którzy go nie powinni otrzymać niż niedając kredytu tym którzy powinni go dostać). Macierz kosztów ma postać:
koszty <- matrix(c(0, 1, 2, 0), 2, 2,
dimnames = list(
prognozowane = c("dobry", "zly"),
rzeczywiste = c("dobry", "zly")))
koszty## rzeczywiste
## prognozowane dobry zly
## dobry 0 2
## zly 1 0Na jej podstawie można obliczyć koszt błędnej klasyfikacji dla modelu k-NN
conf_matrix<-as.matrix(table(
przewidywane = knn$fitted.values,
rzeczywiste = data_test$jakosc))
sum(koszty*conf_matrix)## [1] 137i dla modelu 0R
sum(koszty[1,]*as.matrix(table(data_test$jakosc)))## [1] 168