Wprowadzenie

Uczenie klasyfikatora opartego o drzewo klasyfikacyjne polega na skonstruowaniu takiego drzewa klasyfikacyjnego w oparciu o zbiór uczący aby zapewnić możliwie wysoką sprawność klasyfikatora. Uzyskane drzewo powinno charakteryzować się możliwie niewielkim rozmiarem, uczenie polega zatem na wyborze odpowiednich testów dla wartości atrybutów w taki sposób aby możliwie szybko i z jak najmniejszym błędem przebiegając po drzewie osiągać liście wskazujące etykiety klas.

Procedura budowy drzewa polega na:

  • Sprawdź, czy rozpatrywany zbiór obiektów jest jednorodny pod względem cechy Y (lub spełnione zostało inne kryterium stopu): TAK - zatrzymanie postępowania dla tego zbioru, NIE: Rozważ wszystkie możliwe sposoby podziału zbioru obiektów na rozłączne podzbiory, tj. rozważ wszystkie możliwe zmienne X i dla każdej zmiennej wszystkie możliwe punkty podziału,
  • Dokonaj oceny jakości każdego podziału i wybierz najlepszy z nich,
  • Podziel zbiór obiektów w wybrany sposób.
  • Dla każdego podzbioru powtórz całą procedurę.

Celem tej części projektu jest zbudowania optymalnego klasyfikatora opartego o drzewo klasyfikacyjne dla danych znajdujących się zbiorze danych credit.

library(tree)
library(rpart)
library(rpart.plot)

load("C:/Users/mbuko/OneDrive/Dokumenty/credit.RData")

Przygotowanie danych

Zmienne porządkowe

Analiza z wykorzystaniem drzewa klasyfikacyjnego została przeprowadzona na podstawie wszystkich zmiennych ilościowych i jakościowych ze zbioru danych credit. Sposób oraz liczba możliwych podziałów w każdym z wierzchołków zależy od rodzaju zmiennych. Z tego też względu w ramach przygotowania danych wskazano zmienne o charakterze porządkowym, do których zaliczono: stan konta czekowego, oszczędności i staż pracy.

credit$konto_czekowe <- factor(
  x = credit$konto_czekowe,
  levels = c("< 0", "brak", "0-200",">200"),
  ordered = T
)

credit$oszczednosci <- factor(
  x = credit$oszczednosci,
  levels = c( "brak" , "<100",  "100-500",  "500-1000" ,">1000" ),
  ordered = T
)

credit$staz_pracy <- factor(
  x = credit$staz_pracy,
  levels = c("bezrobotny",  "<1 rok", "1-4" , "4-7", ">7" ),
  ordered = T
)

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(123) # for reproducibility
random <- sample(1:nrow(credit), 0.75 * nrow(credit))


data_train<-credit[random, ]
data_test <- credit[-random, ]

Budowa drzewa dla całego zbioru na podstawie domyślnych argumentów funkcji

Poniżej zaprezentowano rysunek drzewa klasyfikacyjnego zbudowanego na podstawie całości danych credit z wykorzystaniem domyślnych argumentów funkcji rpart. W wyniku zatrzymania podziału na podstawie domyslnych ustawień funkcji otrzymamy przynajmniej część zbiorów, które są będą homogeniczne. Aby nadać takiemu drzewu cech drzewa klasyfikacyjnego stosuje się zasadę majoryzacji. Oznacza to, że wszystkie obiekty w zbiorze k przypisuje się do takiej klasy j, która występuje w zbiorze najliczniej.

drz.credit <- rpart(jakosc ~., data = credit)

rpart.plot(drz.credit)

Budowa drzewa optymalnego

Drzewo maksymalne

Przy tworzeniu drzewa z wykorzystaniem domyślnych parametrów zatrzymanie podziału wynika z domyslnego kryterium Stop dla wartości parametru cp = 0.01. Parametr złozoności cp oznacza o ile minimalnie musi zmniejszyć się błąd resubstytucji (względem błędu korzenia), żeby podział w węźle był dalej wykonywany. Poziom zmiejszenia błędu redystrybucji rel_error dla drzewa domyślnego można sprawdzić na podstawie:

printcp(drz.credit)
## 
## Classification tree:
## rpart(formula = jakosc ~ ., data = credit)
## 
## Variables actually used in tree construction:
## [1] cel           czas          historia      konto_czekowe kwalifikacje 
## [6] kwota         oszczednosci  poreczyciel  
## 
## Root node error: 300/1000 = 0.3
## 
## n= 1000 
## 
##         CP nsplit rel error  xerror     xstd
## 1 0.035000      0   1.00000 1.00000 0.048305
## 2 0.023333      3   0.87667 0.93000 0.047277
## 3 0.020000      5   0.83000 0.94333 0.047482
## 4 0.016667      6   0.81000 0.94000 0.047431
## 5 0.015000      7   0.79333 0.93667 0.047380
## 6 0.013333      9   0.76333 0.92000 0.047120
## 7 0.011667     14   0.69000 0.89000 0.046632
## 8 0.010000     16   0.66667 0.89000 0.046632

Aby określić optymalną liczbę węzłów w drzewie nalezy zbudować drzewo maksymalnych rozmiarów, tj. takiego w którym podział jest konntynuowany mimo braku zmiany poziomu błędu (cp =0).

drzewo.max <- rpart(jakosc ~ ., data = data_train,
                 control = rpart.control(cp = 0, 
                                         xval = 10)) # liczba prób w sprawdzaniu krzyżowym (domyślna)
plot(drzewo.max)

bledy <- printcp(drzewo.max)
## 
## Classification tree:
## rpart(formula = jakosc ~ ., data = data_train, control = rpart.control(cp = 0, 
##     xval = 10))
## 
## Variables actually used in tree construction:
##  [1] cel           czas          historia      konto_czekowe kwalifikacje 
##  [6] kwota         oszczednosci  plec          rata_%doch    staz_pracy   
## [11] wiek          zamieszkanie 
## 
## Root node error: 219/750 = 0.292
## 
## n= 750 
## 
##           CP nsplit rel error  xerror     xstd
## 1  0.0441400      0   1.00000 1.00000 0.056858
## 2  0.0319635      3   0.86758 1.00913 0.057010
## 3  0.0273973      4   0.83562 0.96804 0.056310
## 4  0.0228311      5   0.80822 0.95434 0.056066
## 5  0.0182648      8   0.73973 0.94521 0.055900
## 6  0.0136986     10   0.70320 0.87215 0.054481
## 7  0.0121766     11   0.68950 0.89041 0.054852
## 8  0.0091324     15   0.63014 0.88128 0.054668
## 9  0.0053272     18   0.60274 0.91324 0.055300
## 10 0.0045662     24   0.57078 0.96347 0.056229
## 11 0.0018265     26   0.56164 0.96347 0.056229
## 12 0.0000000     31   0.55251 0.95434 0.056066
matplot(x = bledy[, "nsplit"],
        y = bledy[, c("rel error",  # błąd na próbie uczącej (w stosunku do błędu dla korzenia)
                      "xerror")],  # błąd w sprawdzaniu krzyżowym
        type = "l",
        xlab = "wielkość drzewa",
        ylab = "błąd")
legend(x = "bottom", legend = c("błąd na próbie uczącej", 
                                  "błąd w sprawdzaniu krzyżowym"),
       col = c("black", "red"),
       lty = 1:2)

Przycinanie drzewa

Jednym z kryteriów przycinanie drzewa jest tzw. “zasada jednego błędu standardowego”, “1 SE rule”). Umożliwia ona wybór najmniejszego drzewa, którego błąd w sprawdzaniu krzyżowym jest większy od minimalnego błędu nie więcej niż o jedno odchylenie standardowe. Procedura przycinania drzewa zgodnie z zasadą jednego błędu standardowego polega na:

  • znalezieniu minimalnej wartości błędu w sprawdzaniu krzyżowym (xerror) - \(min_{xerror}\),
  • obliczeniu sumy \(min_{xerror}\) i odpowiadającej jej wartości xstad,
  • znalezieniu pierwszej wartości xerror spełniającej warunek: \[ xerror < min_{xerror} + xstd \]
tmp1 <- which.min(bledy[, "xerror"])  # min błąd w sprawdzaniu krzyżowym
tmp2 <- sum(bledy[tmp1, c("xerror", "xstd")]) # min błąd + odchylenie standardowe
optymalny <- which(bledy[, "xerror"] < tmp2)[1] # nr optymalnego drzewa

Optymalna liczba węzłów wynosi 10, co odpowiada cp = 0.0136986

Drzewo optymalne

Optymalna postać drzewa

drzewo.opt <- prune(drzewo.max, cp = bledy[optymalny, "CP"]) # przycięcie drzewa
rpart.plot(drzewo.opt)

Ocena jakości klasyfikacji

Błędy w klasyfikacji na podstawie zbioru testowego

Ocenę jakości klasyfikacji dokonano na podstawie zbioru testowego, z wykorzystaniem macierzy błędnych klasyfikacji:

predykcja <- predict(object = drzewo.opt,
                     newdata = data_test,
                     type = "class")  



macierz_drzewo<-table(przewidywane = predykcja, rzeczywiste = data_test$jakosc)

macierz_drzewo
##             rzeczywiste
## przewidywane dobry zly
##        dobry   151  55
##        zly      18  26

Błąd klasyfikacji wynosi:

sum(predykcja != data_test$jakosc) / nrow(data_test)  
## [1] 0.292

Ocena 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 
##   169    81
sum(data_test$jakosc == "zly")/nrow(data_test)
## [1] 0.324

Precyzja, czułość, miara F

Wzory dotyczące tych parametrów oceny znajdują się w dokumencie metody5, zaś ich szczegółowy opis w dokumencie metody6

Poniżej przedstawiono obliczenia dla modelu drzewa klasyfikacyjnego i 0R.

precyzja_drzewo <- macierz_drzewo[1,1]/(macierz_drzewo[1,1]+macierz_drzewo[1,2])
precyzja_drzewo
## [1] 0.7330097
czulosc_drzewo <-macierz_drzewo[1,1]/(macierz_drzewo[1,1]+macierz_drzewo[2,1])
czulosc_drzewo
## [1] 0.8934911
miaraF_drzewo<-2/(1/precyzja_drzewo+1/czulosc_drzewo)
miaraF_drzewo
## [1] 0.8053333
precyzja_0R <- macierz_0R[1]/(macierz_0R[1]+macierz_0R[2])
as.numeric(precyzja_0R["dobry"])
## [1] 0.676
czulosc_0R <-macierz_0R[1]/(macierz_0R[1])
as.numeric(czulosc_0R["dobry"])
## [1] 1
miaraF_0R<-2/(1/precyzja_0R+1/czulosc_0R)
as.numeric(miaraF_0R["dobry"])
## [1] 0.8066826

Poró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   0

Na jej podstawie można obliczyć koszt błędnej klasyfikacji dla modelu k-NN

conf_matrix<-as.matrix(table(przewidywane = predykcja, rzeczywiste = data_test$jakosc))

sum(koszty*conf_matrix)
## [1] 128

i dla modelu 0R

sum(koszty[1,]*as.matrix(table(data_test$jakosc)))
## [1] 162

Minimalizacja kosztu błędów

Budowa modelu

Model uwzględniający różne koszty błędnych klasyfikacji może zostać zbudowany w poniższy sposób:

koszty2 <- matrix(c(0, 2, 1, 0), 2, 2, 
                 dimnames = list(rzeczywiste = c("yes", "no"), 
                                 prognozowane = c("yes", "no")))
drz.credit.koszt <- rpart(jakosc ~., data = data_train,
                          parms = list(loss = koszty2))

rpart.plot(drz.credit.koszt, type = 0)

Sprawdzenie modelu dla zbioru testowego

Ocena jakości klasyfikacji na podstawie macierzy błędnych klasyfikacji dla zbioru testowego:

predykcja2 <- predict(object = drz.credit.koszt,
                     newdata = data_test,
                     type = "class")  



mklas.koszt <- table(przewidywane = predykcja2, rzeczywiste = data_test$jakosc)
mklas.koszt
##             rzeczywiste
## przewidywane dobry zly
##        dobry   128  27
##        zly      41  54

Ocena jakości klasyfikacji

Procentu błędów:

sum(predykcja2 != data_test$jakosc) / nrow(data_test)  
## [1] 0.272

Precyzja, czułość, miara F

precyzja_drzewo_koszt <- mklas.koszt[1,1]/(mklas.koszt[1,1]+mklas.koszt[1,2])
precyzja_drzewo_koszt
## [1] 0.8258065
czulosc_drzewo_koszt <-mklas.koszt[1,1]/(mklas.koszt[1,1]+mklas.koszt[2,1])
czulosc_drzewo_koszt
## [1] 0.7573964
miaraF_drzewo_koszt<-2/(1/precyzja_drzewo_koszt+1/czulosc_drzewo_koszt)
miaraF_drzewo_koszt
## [1] 0.7901235

oraz łącznego kosztu z uwzględnieniem różnych kosztów błednych klasyfikacji:

sum(koszty * mklas.koszt)  
## [1] 95