Master 2 MIMSE 2015-2016Apprentissage automatique

TP1 : les k plus proches voisins

1 Données synthétiquesRécupérer les jeux de données synth_train.txt et synth_test.txt. On a Y ∈ {1, 2} et X ∈ R2. On

dispose de 100 données d’apprentissage et 200 données test.

1. Charger le jeu de données d’apprentissage dans R (soit avec la commande read.table, soit avecl’outil d’importation de Rstudio : Tools > Import Dataset). Afficher les données d’apprentissage.

rm(list=ls())# on efface tout ce qui est en memoiretrain <- read.table(file="synth_train.txt", header=TRUE)dim(train)

## [1] 100 3

head(train)

## y x1 x2## 1 2 -0.72221141 2.0044709## 2 2 -0.92467912 0.4836693## 3 2 -0.76602281 0.7943289## 4 2 -0.07328948 0.9699291## 5 1 -1.39291198 0.9996971## 6 2 -0.20223339 1.3503319

X <- train[,-1]Y <- train$y

2. Représenter graphiquement les observations à l’aide de la fonction plot. On pourra colorier lespoints en fonction de leur classe à l’aide du paramètre col et modifier le symbole avec le paramètrepch (=point character) et rajouter une légende à l’aide de la fonction legend.

plot(X, pch=Y, col=Y)legend("topright", legend=c("classe 1", "classe 2"), pch=1:2, col=1:2)

1

−2 −1 0 1

0.0

0.5

1.0

1.5

2.0

2.5

3.0

x1

x2

classe 1classe 2

3. Appliquer la fonction knn du package class avec k = 15 voisins pour prédire les points de coor-données (0,0) et (-2,2).

library(class)Xtest <- matrix(c(0,0,-2,2), nrow=2, byrow=TRUE)pred <- knn(X,Xtest, Y,15)pred

## [1] 2 1## Levels: 1 2

4. Prédire les données de l’ensemble d’apprentissage avec ce classifieur et comparer avec les vraiesclasses. Calculer le taux d’erreur empirique (nombre de fausses prédictions sur l’échantillon d’ap-prentissage divisé par taille de cet échantillon). Recommencer avec k = 1 voisin.

# avec k=15 voisinspred_train <- knn(X, X,Y,15)pred_train != Y

## [1] TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE## [12] FALSE FALSE FALSE TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE## [23] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE## [34] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE## [45] FALSE FALSE TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE## [56] FALSE FALSE TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE## [67] FALSE FALSE TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE

2

## [78] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE## [89] FALSE FALSE FALSE FALSE FALSE FALSE TRUE FALSE TRUE FALSE TRUE## [100] FALSE

sum(pred_train!=Y)/length(Y)

## [1] 0.08

# avec k=1 voisinpred_train <- knn(X, X,Y,1)sum(pred_train!=Y)/length(Y)

## [1] 0

5. Représenter graphiquement la frontière de décision pour k = 15 voisins : commencer par construireune grille de points, prédire ces points, puis ajouter ces points sur le graphique en les coloriant enfonction de leur prédiction. Recommencer avec k = 1 voisin.

a <- seq(from=min(train$x1), to=max(train$x1), length.out=100)b <- seq(from=min(train$x2), to=max(train$x2), length.out=100)grille <- NULLfor (i in a){

grille <- rbind(grille, cbind(i,b))}# avec k=15 voisinspred_grille <- knn(X, grille, Y,15)plot(X, pch=Y, col=Y,main="Frontière de décision pour k=15 voisins")points(grille, pch=20, col=pred_grille, cex=0.5)legend("topright", legend=c("classe 1", "classe 2"), pch=1:2, col=1:2, bg="white")

3

−2 −1 0 1

0.0

0.5

1.0

1.5

2.0

2.5

3.0

Frontière de décision pour k=15 voisins

x1

x2

classe 1classe 2

# avec k=1 voisinpred_grille <- knn(X, grille, Y,1)plot(X, pch=Y, col=Y,main="Frontière de décision pour k=1 voisins")points(grille, pch=20, col=pred_grille, cex=0.5)legend("topright", legend=c("classe 1", "classe 2"), pch=1:2, col=1:2, bg="white")

4

−2 −1 0 1

0.0

0.5

1.0

1.5

2.0

2.5

3.0

Frontière de décision pour k=1 voisins

x1

x2

classe 1classe 2

6. Charger le jeu de données test dans R. Afficher les données test. Prédire les données de l’ensembletest avec k = 15 voisins puis avec k = 1 voisin. Calculer le taux d’erreur empirique dans les deuxcas. Comparer avec les taux d’erreur des prédictions de l’ensemble d’apprentissage.

test <- read.table(file="synth_test.txt", header=TRUE)Xtest <- test[,-1]Ytest <- test$y# 15 voisinspred_test <- knn(X,Xtest,Y,15)sum(pred_test!=Ytest)/length(Ytest)

## [1] 0.075

# 1 voisinpred_test <- knn(X,Xtest,Y,1)sum(pred_test!=Ytest)/length(Ytest)

## [1] 0.065

7. On choisit à partir de maintenant le classifieur knn avec k = 15 voisins. Calculer le taux de vraipositifs (TVP) et le taux de vrai négatif (TVN) de ce classifieur sur l’échantillon test sachant queTV P = V P

V P + FNet TV N = V N

V N + FPet que ici 1=positif et 2=négatif.

# prédictions knn avec 15 voisinspred <- knn(X,Xtest,Y,15)# matrice de confusion

5

table(Ytest,pred)

## pred## Ytest 1 2## 1 47 15## 2 0 138

# TVP ou sensibilité47/(47+15)

## [1] 0.7580645

# TVN ou spécificité138/138

## [1] 1

8. On souhaite maintenant associer un coût 3 fois plus important aux faux negatifs. On utilise donc la

matrice de coût C =(

0 31 0

)dans la règle de classification de Bayes. Les probabilités à posteriori

P(Y = 1|X = x) d’une entrée x sont estimées par la fréquences de voisins de x appartenant à laclasse 1.(a) Programmer une fonction prob_knn qui estime les probabilités P(Y = 1|X = x) d’un ensemble

de données d’entrées.

prob_knn <- function(X,Y,Xtest,k){

K <- length(unique(Y))prob <- rep(NA,nrow(Xtest))for (i in 1:nrow(test)){

x0 <- Xtest[i,]d <- apply(X,1,function(x){sum((x-x0)^2)})Nx0 <- sort(d,index.return=TRUE)$ix[1:k]prob[i]<- sum(Y[Nx0]==1)/k

}return(prob)

}

(b) Appliquer cette fonction aux données de l’ensemble test. En déduire leur prédiction avec larègle de Bayes incluant les coûts. Vous pouvez utiliser la fonction I pour construire le code R.

#estimation des probas d'être dans la classe 1prob <- prob_knn(X,Y,Xtest,15)head(prob)

## [1] 0.00000000 0.20000000 0.20000000 0.00000000 0.00000000 0.06666667

#verification avec les probas de la fonction knn#attention : il s'agit des probas de la classe effectivement predite !res <- knn(X,Xtest,Y,15,prob=TRUE)head(attr(res,"prob"))

## [1] 1.0000000 0.8000000 0.8000000 1.0000000 1.0000000 0.9333333

6

#prediction avec la règle de Bayes et la matrice de coûtspred_cout <- 1*I(3*prob>(1-prob))+2*I(3*prob<(1-prob))

(c) Calculer le taux de vrai positifs (TVP) et le taux de vrai négatif (TVN).

#matrice de confusiontable(Ytest,pred_cout)

## pred_cout## Ytest 1 2## 1 54 8## 2 4 134

# TVP ou sensibilité54/(54+8)

## [1] 0.8709677

# TVN ou spécificité138/(134+8)

## [1] 0.971831

# TBC(54+134)/200

## [1] 0.94

(d) Faire un petit bilan métodologique de cet exercice.

2 Données réellesRécuperer le jeu de données Desbois.rda. Les données concernent n = 1260 exploitations agricoles répartiesen K = 2 groupes : le groupe des exploitations saines et le groupe des exploitations défaillantes. On veutconstruire un score de détection du risque financier applicable aux exploitations agricoles. Pour chaqueexploitation agricole on a mesuré une batterie de critères économiques et financiers et finalement p = 4ratios financiers on étés retenus pour construire le score :

— R2 : capitaux propres / capitaux permanents,— R7 : dette à long et moyen terme / produit brut,— R17 : frais financiers / dette totale,— R32 : (excédent brut d’exploitation - frais financiers) / produit brut.

La variable qualitative à expliquer est donc la variable difficulté de paiement (0=sain et 1=défaillant).Voici les 5 premières lignes du tableau de données.

DIFF R2 R14 R17 R321 saine 0.622 0.2320 0.0884 0.43132 saine 0.617 0.1497 0.0671 0.39893 saine 0.819 0.4847 0.0445 0.31874 saine 0.733 0.3735 0.0621 0.43135 saine 0.650 0.2563 0.0489 0.4313

1. Charger le jeu de données dans R avec la commande load.

7

rm(list=ls())# on efface tout ce qui est en memoireload("Desbois.rda")dim(data)

## [1] 1260 5

2. On s’intéresse d’abord à la méthodologie du choix de k

(a) Créer un jeu de données de données d’apprentissage de taille 945 (75% des données) et un jeude données test de taille 315 (25% des données) avec le code suivant.

set.seed(30)tr <- sample(1:nrow(data),945)train <- data[tr,]test <- data[-tr,]

(b) Cacluler les taux d’erreur sur les données test pour k variant de 1 à 100. Avec la foncton plot,représenter ce taux d’erreur test en fonction de k (contrôler que l’abscisse du graphique partde 0). Avec la fonction which.min trouver le nombre de voisins qui donne la plus petite erreurtest.

(c) Recommencer avec un autre découpage aléatoire apprentissage/test et représenter la courbed’évolution du taux d’erreur test sur le même graphique qu’à la question précédente.

library(class)kmax=100err_test <- rep(NA,kmax)for (k in 1:kmax){

pred <- knn(train[,-1],test[,-1],train$DIFF,k)err_test[k] <- sum(pred!=test$DIFF)/length(test$DIFF)

}lim <- c(0,max(err_test))plot(err_test,type="l",ylim=lim,col=2,xlab="nombre de voisins",

ylab="taux d'erreur")which.min(err_test)

## [1] 3

#Nouveau decoupage apprentissage/testset.seed(10)tr <- sample(1:nrow(data),900)train <- data[tr,]test <- data[-tr,]for (k in 1:kmax){

pred <- knn(train[,-1],test[,-1],train$DIFF,k)err_test[k] <- sum(pred!=test$DIFF)/length(test$DIFF)

}points(err_test,type="l",col=4)legend("bottomright", legend=c("decoupage 1", "decoupage 2"),

lty=1, col=c(2,4))

8

0 20 40 60 80 100

0.00

0.05

0.10

0.15

nombre de voisins

taux

d'e

rreu

r

decoupage 1decoupage 2

which.min(err_test)

## [1] 9

(d) Executer le code suivant et faire un choix pour k.B<- 20kmax <- 100err_test <- matrix(NA,kmax,B)

for (b in 1:B){

tr <- sample(1:nrow(data),900)train <- data[tr,]test <- data[-tr,]for (k in 1:kmax){

pred <- knn(train[,-1],test[,-1],train$DIFF,k)err_test[k,b] <- sum(pred!=test$DIFF)/length(test$DIFF)

}}

mean_err_test <- apply(err_test,1,mean)lim <-c(0,max(err_test))matplot(err_test,type="l",lty=2,col=2,ylim=lim,

xlab="nombre de voisins",ylab="taux d'erreur")

9

matpoints(mean_err_test,type="l",col=2,lwd=4)legend("bottomright", legend=c("Erreur moyenne", "Erreurs conditionnelles"),

lty=c(1,3),lwd=c(4,2),col=c(2,2))

0 20 40 60 80 100

0.00

0.05

0.10

0.15

0.20

nombre de voisins

taux

d'e

rreu

r

Erreur moyenneErreurs conditionnelles

which.min(mean_err_test)

## [1] 22

(e) Choisir maintenant le nombre k de voisin en utilisant par validation croisée (cross validation)leave-one-out (LOO) avec la fonction knn.cv.

?knn.cverr_test <- rep(NA,kmax)for (k in 1:kmax){

pred <- knn.cv(data[,-1],data$DIFF,k)err_test[k] <- sum(pred!=data$DIFF)/length(data$DIFF)

}lim <-c(0,max(err_test))plot(err_test,type="l",col=2,ylim=lim,xlab="nombre de voisins",

ylab="taux d'erreur")points(mean_err_test,type="l",col=4,lwd=1)legend("bottomright", legend=c("Erreur loo", "Erreur moyenne"),

col=c(2,4),lty=1)

10

0 20 40 60 80 100

0.00

0.05

0.10

0.15

nombre de voisins

taux

d'e

rreu

r

Erreur looErreur moyenne

which.min(err_test)

## [1] 9

(f) Faire un petit bilan méthodologique concernant le choix du paramètre k.3. On veut maintenant non seulement choisir k mais également avoir une idée de l’erreur de prédiction

de ce classifieur. Pour cela, il faut utiliser des données n’ayant jamais été utilisées. Les donnéesdoivent donc être découpées en trois parties : apprentissage/validation/test(a) Couper aléatoirement les données deux parties : un ensemble "apprentissage-validation" de taille

945 (75 % des données) et un ensemble test de taille 315 (25% des données).

set.seed(30)tr <- sample(1:nrow(data),945)trainval <- data[tr,]test <- data[-tr,]

(b) Utiliser la première approche pour choisir k sur l’ensemble "apprentissage-validation" :i. Choisir k en découpant les 945 données de l’ensemble "apprentissage-validation" en deux

parties : une partie "apprentissage" de taille 630 (50% des données) et une partie "validation"de taille 315 (25 % des données). Choisir k qui minimise le taux d’erreur moyen sur lesensembles de validations de B = 25 découpages.B <- 25kmax <- 50err_valid <- matrix(NA,kmax,B)

11

for (b in 1:B){

tr <- sample(1:nrow(trainval),630)train <- trainval[tr,]valid <- trainval[-tr,]for (k in 1:kmax){

pred <- knn(train[,-1],valid[,-1],train$DIFF,k)err_valid[k,b] <- sum(pred!=valid$DIFF)/length(valid$DIFF)

}}

mean_err_valid <- apply(err_valid,1,mean)plot(mean_err_valid,type="l")

0 10 20 30 40 50

0.13

0.14

0.15

0.16

0.17

Index

mea

n_er

r_va

lid

which.min(mean_err_valid)

## [1] 29

ii. Constuire le classifieur avec ce nombre de voisins sur l’ensemble "apprentissage-validation"et calculer le taux d’erreur des données test.

pred <- knn(trainval[,-1],test[,-1],trainval$DIFF,k=which.min(mean_err_valid))sum(pred!=test$DIFF)/length(test$DIFF)

## [1] 0.1333333

12

(c) Utiliser la seconde approche pour choisir k par validation croisée LOO sur l’ensemble "apprentissage-validation". Calculer ensuite le taux d’erreur des données test.

err_valid <- rep(NA,kmax)for (k in 1:kmax){

pred <- knn.cv(trainval[,-1],trainval$DIFF,k)err_valid[k] <- sum(pred!=trainval$DIFF)/length(trainval$DIFF)

}which.min(err_valid)

## [1] 8

pred <- knn(trainval[,-1],test[,-1],trainval$DIFF,k=which.min(err_valid))sum(pred!=test$DIFF)/length(test$DIFF)

## [1] 0.1174603

4. Pour les courageux, on pourrait recommencer avec plusieurs découpages des données en deuxparties "apprentissage-validation" et "test". Cela permettrait d’avoir une erreur test moyenne, etune idée de sa variabilié. C’est assez rapide à faire avec la méthode de LOO pour le choix de k :

B <- 10kmax <- 50err_valid <- rep(NA,kmax)err_test <- rep(NA,B)for (b in 1:B){

tr <- sample(1:nrow(data),945)trainval <- data[tr,]test <- data[-tr,]for (k in 1:kmax){

pred <- knn.cv(trainval[,-1],trainval$DIFF,k)err_valid[k] <- sum(pred!=trainval$DIFF)/length(trainval$DIFF)

}pred <- knn(trainval[,-1],test[,-1],trainval$DIFF,k=which.min(err_valid))err_test[b] <- sum(pred!=test$DIFF)/length(test$DIFF)

}boxplot(err_test,main="Erreurs test pour 50 decoupages")

13

0.11

0.12

0.13

0.14

0.15

0.16

Erreurs test pour 50 decoupages

14