Ce cours est donné à des étudiants de master non informaticiens. Les objectifs du cours sont la compréhension des principaux algorithmes de fouille de données : le clustering avec les k-moyennes, la classification hiérarchique et un algorithme par densité ; l'algorithme Apriori pour les règles d'association ; les algorithmes de classification supervisée par arbres de décision, par séparation linéaire (correction d'erreur, gradient, gradient stochastique, systèmes à vastes marges) et leurs extensions au cas non linéaire (réseaux de neurones, noyaux). Ce cours est le point de départ d'un livre d'introduction à l'apprentissage destiné à des non spécialistes.
L'accent est porté sur la compréhension des algorithmes et leur complexité. Il insiste également sur l'évaluation des performances d'un algorithme. Ceci contribue à permettre à un utilisateur de faire un bon choix de méthode d'apprentissage face à un problème réel.
Les TPs sont faits avec le logiciel R et sont décrits dans la suite de cette page.
Un vecteur peut-être créé de différentes manières. Un procédé de construction directe est d'utiliser la fonction c. Par exemple, créons un vecteur dont les éléments sont 0, -1, pi et 4,78, et mettons-le dans une variable dont le nom est v puis affichons la valeur de v :
> v <- c (0, -1, pi, -5)
> v
D'autres constructions utiles, en particulier pour l'indexation de vecteurs sont les intervalles et les séquences. Un vecteur d'entiers peut être défini par un intervalle d'entiers en en donnant la borne supérieure et la borne inférieure séparées par le symbole :
> w <- -1:2
> w
> b <- -3:3
> b
Un vecteur d'entiers peut aussi être défini par une séquence définie à l'aide de la fonction seq() en précisant le point de départ, la limite supérieure, et le pas
> b <- seq(-3,3)
> b
> b <- seq(from = -3, to =3)
> b
> c <- seq(from = 1, to = 91, by = 10)
> c
De nombreuses fonctions s'appliquent aux vecteurs. En particulier, toutes les fonctions peuvent s'appliquer à des vecteurs, elles s'appliquent terme à terme. Par exemple, appliquez les fonctions abs() et log() à a, b, c, v.
D'autre part, il existe un certain nombre de fonctions spécifiques aux vecteurs. Appliquez les fonctions suivantes au vecteur v et trouvez la signification de chacune de ces fonctions : length(), min(), max(), range(), sum(), prod(), which.min(), which.max().
Enfin, des fonctions statistiques sont disponibles pour les vecteurs telles que mean(), var(), sd() et summary(). Donnez la sémantique de ces fonctions et, en particulier, comprenez les valeurs retournées par la fonction summary(). Regardez l'aide sur les fonctions median() et quantile().
On peut effectuer les opérations entre un vecteur et un scalaire, entre deux vecteurs. Une opération arithmétique entre deux vecteurs n'est possible que pour deux vecteurs de même longueur. Calculez les vecteurs doublev (de deux façons) dont les composantes sont les doubles des composantes de v, oppv dont les composantes sont les opposés des composantes de v, carrev dont les composantes sont les carrés des composantes de v.
Une opération classique est de calculer le produit scalaire de deux vecteurs. Trouver une formule (simple) de calcul du produit scalaire. Vérifier que l'opérateur %*% calcule également le produit scalaire.
On peut accéder directement à la composante d'un vecteur par le nom du vecteur et l'indice entre crochets. Par exemple v[3] désigne la composante d'indice 3 du vecteur v. On peut également accéder à plusieurs composantes en indexant par un vecteur d'entiers. Par exemple v[c(2,4)] crée un vecteur à deux composantes qui correspondent aux composantes 2 et 4 du vecteur v.
On peut également indicer les vecteurs par des vecteurs de Booléens. Un Booléen peut prendre deux valeurs TRUE (abrégé en T) et FALSE (abrégé en F). Les Booléens sont très utilisés dans les langages informatiques car ils correspondent aux résultats que peut prendre un test. Un test est une comparaison de deux valeurs (de même type) construit à l'aide des opérateurs de comparaison ==, !=, <=, <, >=, >. Les tests peuvent être étendus aux vecteurs. Les résultats de test sur les vecteurs fournissent des vecteurs de Booléens qui indicent des vecteurs (ceux pour lesquels la composante vaut TRUE.
> v < w
> v[v < w]
> v[v < w] <- 10
> v
On peut combiner les Booléens à l'aide des opérateurs logiques ET, OU et NON qui, dans le langage R, se notent respectivement &, | et !.
Regardez l'aide sur la fonction runif(). Construisez le vecteur avec :
a <- runif(20)
Les matrices en R sont des vecteurs auxquels on ajoute des dimensions avec la fonction dim(). On peut redimensionner une matrice. On accède au nombre de lignes avec nrow() et au nombre de colonnes avec ncol(). On peut nommer les lignes et colonnes. Les éléments d'une matrice sont tous du même type. Ici, nous considérons des matrices numériques.
> x <- 1:12
> dim(x) <- c(3,4)
> x
> dim(x) <- c(4,3)
> x
> nrow(x)
> ncol(x)
> dim(x)
> rownames(x) <- paste("ligne", 1:nrow(x), sep = "")
> colnames(x) <- letters[1:ncol(x)]
> x
Les matrices peuvent également être créées avec la fonction matrix() en précisant le nombre de lignes, le nombre de colonnes et comment remplir la matrice. On peut ajouter des colonnes avec cbind(), des lignes avec rbind().
> y <- matrix(seq(-2,2,length.out=12), nrow=3, ncol=4)
> y
> z <- matrix(seq(-2,2,length.out=12), nrow=3, ncol=4, byrow=TRUE)
> z # comprendre la différence entre y et z
> z <- rbind(z,c(4,3,2,1))
> z
> z <- cbind(z,0)
> z # remarque l'extension du 0
On peut également créer des matrices diagonales.
> I5 <- diag(1, nrow = 5, ncol = 5)
> diag(5:1)
Les opérations et fonctions sur les matrices opèrent comme sur les vecteurs, c'est-à-dire composante par composante.
> x <- matrix(1:9, nrow = 3)
> x
> x+x
> x + 2
> x + c(5,5,5)
> x + c(10,20)
> x * x
> log(x)
Il existe des opérations et fonctions particulières comme la multiplication des matrices, la transposition, le calcul de déterminant et l'inversion.
> t(x)
> det(x)
> x % * % x
> inv.x <- solve(x)
> x[3,3] <- 1
> det(x)
> inv.x <- solve(x)
> x * inv.x
> zapsmall(x % * % inv.x)
> zapsmall(inv.x % * % x)
> eigen(x)
Même principe que les vecteurs mais on a deux indices pour les matrices à deux dimensions.
> y <- matrix(seq(-2,2,length.out=12), nrow=3, ncol=4)
> y
> y[2,3]
> y[2,2:3]
> y[2,]
> y[-3,-2]
> y[1:2,-c(1,3)]
En statistique et en fouille de données, les données sont généralement disponibles sous forme de tableaux de données, chaque ligne correspondant à une donnée, chaque colonne à un attribut. En R, un tableau de données porte le nom de **data frame**. La différence avec les matrices est que les attributs (les variables) peuvent être de nature (de type) différente. On peut avoir des attributs quantitatifs (numériques), qualitatifs (un nombre fini de valeurs possibles ; par exemple bleu, vert ou rouge), logiques (vrai ou faux). Un data frame peut contenir des valeurs manquantes (la donnée n'est pas connue).
Considérons un jeu de données de N exemples avec p attributs. Ce jeu de données pourra être représenté par un data frame. La structuration interne à R est celle d'une liste de p vecteurs. Le vecteur d'indice i contient les valeurs de l'attribut i pour les N données donc chaque vecteur contient N valeurs. De plus, chaque colonne/vecteur du data frame possède un nom qui permet de le référencer : c'est le nom de l'attribut.
Illustrons tout cela sur un exemple. Par exemple, considérons le jeu de données suivant :
p1-palmitic oleic l1-linoleic arachidic eicosenoic 1075 7823 672 60 29 1088 7709 781 61 NA 911 NA 549 63 29 966 7952 619 78 35 1051 7771 672 NA 46 911 NA 678 70 44 922 7990 618 56 29Il est constitué de 8 lignes. La première contient le nom des attributs, les noms sont séparés les uns des autres par un espace. Les 7 lignes suivantes contiennent les valeurs de ces attributs pour chacune des 7 données (ou 7 exemples) dans ce fichier.
à la main
On peut saisir un data frame à l'aide de la fonction data.frame(). On peut ajouter des colonnes avec cbind(), des lignes avec rbind() ou par d'autres moyens. Tout ceci est illustré par l'exemple suivant :
> p1.palmitic <- c(1075, 1088,911,966,1051) # création colonne
> oleic <- c(7823, 7709, NA, 7952, 7771) # création colonne
> jeu <- data.frame(p1.palmitic,oleic) #création data frame
> jeu
> l1.linoleic <- c(672,781,63,619,671) # création colonne
> jeu <- cbind(jeu,l1.linoleic) # ajout colonne meth 1
> jeu
> jeu$arachidic <- c(60,61,63,78,NA) # ajout colonne meth 2
> jeu
> jeu <- rbind(jeu,c(911,NA,678,70) # ajout ligne
> jeu
> jeu[nrow(jeu)+1,] <- c(922,7990,618,56) # ajout ligne
> jeu
> jeu <- cbind(jeu, eicosenoic = c(29,NA,29,35,46,44,29)) # ajout colonne meth 3
> jeu
lecture d'un fichier
En règle générale, on récupère des jeux de données qui ont été générés par des études ou des applications. On récupère donc les jeux de données à partir du gestionnaire de fichier ou à partir du Web. Pour cela, on utilise la fonction read.table() ou la fonction read.csv().
Pour charger un jeu de données à partir du système de fichiers, on utilise une des deux fonctions et on désigne le fichier par son nom relativement au répertoire courant. Par exemple, si vous souhaitez charger le fichier csjeu1.txt qui se trouve dans le répertoire courant et ranger le jeu de données dans une variable jeu1, il suffit de faire :
> jeu1 <- read.table("csjeu1.txt", header = TRUE)
Si il est ailleurs, il suffit de donner un chemin relatif à partir du répertoire de travail ou un chemin absolu (**attention :** la description du chemin s'écrit avec des /). Vous écrirez par exemple
> jeu1 <- read.table("U:/classification/tpjeuxenR/csjeu1.txt", header = TRUE)
Si le fichier est accessible par le Web, vous pouvez le charger en spécifiant l'URL où il peut être trouvé :
> jeu1 <- read.table("http://www.grappa.univ-lille3.fr/~gilleron/jeuxdonnees/csjeu1.txt", header = TRUE)
Si vous avez des problèmes d'accès réseau, on peut sauvegarder le fichier dans un répertoire et utiliser la méthode précédente.
exercice
Cherchez la signification de csv (dans wikipedia, par exemple). Quelle est la différence entre table et csv ? Regardez l'aide sur la fonction read.table(). Quel est le rôle de header = TRUE ? du paramètre na.strings ? du paramètre row.names ?
Quand le jeu de données est construit ou chargé, vous pouvez le visualiser :
> jeu1
Vous obtenez:
p1.palmitic oleic l1.linoleic arachidic eicosenoic1 1075 7823 672 60 292 1088 7709 781 61 NA3 911 NA 549 63 294 966 7952 619 78 355 1051 7771 672 NA 466 911 NA 678 70 447 922 7990 618 56 29La première ligne indique le nom des attributs. Cette ligne a été récupérée dans le fichier csjeu1.txt grace au "header=TRUE". Les lignes suivantes correspondent aux données. On peut remarquer que les données ont été numérotées de 1 à N. On peut alors accéder aux données :
Nous savons donc accéder à tout ou partie des données dans le data frame. On peut alors appliquer toutes les opérations et fonctions déjà vues. Ainsi,
> mean (jeu1$l1.linoleic)
permet de calculer la moyenne de l'attribut l1.linoleic. Des fonctions spécifiques et très utiles pour les data frame sont :
Naturellement, un attribut peut être qualitatif. Par exemple, le fichier csjeu2.txt contient le même jeu de données, si ce n'est que l'attribut eicosenoic a été discrétisé. **Charger le fichier et le ranger dans la variable jeu2**. Dans R, un attribut qualitatif est dénommé un *facteur*. Pour un attribut qualitatif, la fonction levels() fournit la liste des valeurs possibles de cet attribut ; la fonction table() fournit une table de contingence pour cet attribut.
> levels(jeu2$eicosenoic)
> table(jeu2$eicosenoic)
Vous pouvez spécifier les choix de type des attributs dans les paramètres des fonctions read.table() et read.csv(). En effet, que doit faire R si une colonne prend les valeurs 1, 2, 3, 4 et 5. Considérer comme numérique ? comme discret avec 5 valeurs possibles ? Vous pouvez aussi utiliser des fonctions de conversion : as.numeric(), as.factor(), as.logical().
Elles sont, par convention en R, représentées par NA (pour Non Available). La fonction is.na() produit un booléen qui vaut TRUE si son paramètre est une valeur NA. Ainsi, is.na(jeu2$eicosenoic) donne comme résultat
> [1] FALSE TRUE FALSE FALSE FALSE FALSE FALSE
Ce vecteur pourra être utilisé si vous souhaitez, par exemple, remplacez les valeurs manquantes par la valeur la plus fréquente dans le cas d'attributs qualitatifs (jeu2) ou la valeur moyenne de l'attribut dans le cas d'attributs numériques (jeu1) ou de faire des traitements qui ne s'appliquent qu'aux valeurs manquantes ou qu'aux valeurs présentes.
exercice valeurs manquantes
On travaille sur le jeu de données jeu2 qui correspond au fichier de données csjeu2.txt.
exercice manipulation attributs
La fonction data() permet d'obtenir la liste des jeux de données fournis avec R. Essayez data(women), puis women pour l'afficher. Nous travaillons avec ce jeu de données qui représentent les tailles et poids de femmes américaines. Note : vous pouvez le ranger dans une variable workwomen si vous avez peur de faire des erreurs.
Les graphiques sont un élément essentiel d'un travail de fouille de données ou de statistique. R permet de faire des tas de graphiques. Nous en voyons quelques uns ici ; nous en verrons d'autres par la suite. Chargez le data frame csjeu3.txt dans une variable olives. Attention, il n'y a pas de noms d'attributs.
Pour prendre connaissance du jeu de données, regardez combien il contient de données, combien il contient d'attributs, les noms attribués aux attributs, les statistiques élémentaires sur je jeu de données.
Si l'on veut visualiser l'attribut V3, on tape la commande :
> plot (olives$V3)
On obtient ainsi une représentation planaire de cet attribut : en abscisse, on a simplement le numéro de la donnée, et en ordonnée, la valeur de cet attribut pour cette donnée. On peut alors éventuellement distinguer des tendances. Vous voyez quelque chose ici ? On y reviendra durant le cours régulièrement mais disons-le dès maintenant : **face à un jeu de données, il est toujours utile d'étudier les statistiques élémentaires et de le visualiser**. En effet, des propriétés remarquables peuvent apparaître et l'analyse permettra de quantifier ces propriétés, de les confirmer ou, à l'inverse, de démontrer que ce que l'on a cru voir n'existe pas (du moins qu'il n'est pas statistiquement significatif).
Pour faire un travail sérieux, il convient de mettre des légendes à ce graphique : une légende sur chacun des deux axes, un titre et les points en bleu :
> plot (olives$V3, main = "attribut 3 du jeu de données olives", xlab = "numéro de la donnée", ylab = "V3", col = "blue")
On peut aussi vouloir obtenir le graphe de l'attribut V6 en fonction de l'attribut V3. En effet, un des objectifs de la fouille de données est de trouver des corrélations (linéaires ou pas) entre attributs. On obtient ce graphe comme suit :
> plot(olives$V3, olives$V6)
où vous ajouterez les options nécessaires pour obtenir les légendes adéquates. Vous pouvez terminer en testant
> plot(olives)
Les commandes points() et lines() premettent d'ajouter des points et des lignes à un graphique existant.
La fontion plot() est très riche et a de nombreux comportement en fonction des objets qui lui sont donnés en argument. Par exemple, exécutez, puis visualisez et interprétez le comportement de plot() sur l'exemple suivant :
> x <- rpois(100, lambda = 2)
> x
> class(x)
> plot(x, main = paste("plot pour la classe", class(x)))
> xx <- table(x)
> xx
> class(xx)
> plot(xx, main = paste("plot pour la classe", class(xx)))
> z <- hist(x, plot = FALSE)
> z
> class(z)
> plot(z, main = paste("plot pour la classe", class(z)), col = grey(0.7))
visualisation jeu de données Iris
visualisation jeu de données car.test.frame
Pour charger le jeu de données dans une variable car :
> library(rpart) # charger la librairie qui contient le jeu
> data(car.test.frame) ## charger jeu en mémoire
> car <- car.test.frame
L'objectif de ce TP est de vous faire manipuler des arbres de décision. On utilisera pour cela la bibliothèque rpart de R. Celle-ci contient les fonctions permettant de construire et exploiter un arbre de décision ; l'algorithme utilisé ici est CART qui utilise une construction gloutonne de l'arbre de décision avec un critère de gain basé sur la fonction de Gini avec un élagage effectué en utilisant la validation croisée.
Pour pouvoir construire des arbres de décision, nous allons utiliser la bibliothèque rpart de l'environnement R. Il faut tout d'abord la rendre accessible. Pour cela, on tape la la commande suivante :
library(rpart)À chaque fois que vous lancez R et que vous voulez utiliser les fonctions qui vont être décrites ci-dessous, il faut taper cette commande.
Nous allons tout d'abord découvrir cette bibliothèque sur l'exemple du jeu de tennis. Commençons par charger le jeu de données comme on l'a vu lors du premier TP :
> tennis <- read.table("http://www.grappa.univ-lille3.fr/~gilleron/jeuxdonnees/tennum.txt")Placé dans un data frame, on peut maintenant visualiser ce jeu de données :
> tennis Ciel Temperature Humidite Vent Jouer1 Ensoleille 27.5 85 Faible Non2 Ensoleille 25.0 90 Fort Non3 Couvert 26.5 86 Faible Oui4 Pluie 20.0 96 Faible Oui5 Pluie 19.0 80 Faible Oui6 Pluie 17.5 70 Fort Non7 Couvert 17.0 65 Fort Oui8 Ensoleille 21.0 95 Faible Non9 Ensoleille 19.5 70 Faible Oui10 Pluie 22.5 80 Faible Oui11 Ensoleille 22.5 70 Fort Oui12 Couvert 21.0 90 Fort Oui13 Couvert 25.5 75 Faible Oui14 Pluie 20.5 91 Fort NonVous regarderez également les statistiques descriptives du jeu de données, diverses représentations graphiques avant de vous lancer dans la construction d'arbres de décision (ou de toute autre méthode de classification).
La commande suivante permet de construire l'arbre de décision en précisant :
> ad.tennis <- rpart (Jouer ~ Ciel + Temperature + Humidite + Vent, tennis)Dans cette commande, la notation :
Jouer ~ Ciel + Temperature + Humidite + Ventest courante en R, lorsqu'il s'agît de construire un modèle de prédiction (classification supervisée ou régression). Elle signifie : prédire l'attribut Jouer en fonction des attributs Ciel, Temperature, Humidite et Vent Après avoir exécuté cette commande, la variable ad.tennis contient l'arbre de décision qui a été construit. On peut alors afficher le résultat de la construction sous forme de texte :
> ad.tennisQuel est l'arbre de décision obtenu ? A quelle procédure correspond-t-il ? Il semble que CART n'est pas trouvé bon de construire un arbre ! Regardez l'aide sur la fonction rpart() puis sur rpart.control. Donnez le rôle de minsplit et sa valeur par défaut. Pouvez-vous maintenant justifier le résultat obtenu.
Nous allons remédier à ce problème car notre échantillon est un échantillon jouet et minsplit doit être choisi plus petit. Pour celà, nous allons spécifier le paramètre minsplit :
> ad.tennis.cnt <- rpart.control (minsplit = 1)Remarque : la variable ad.tennis.cnt stocke les paramètres de l'algorithme. Le nom utilisé pour cette variable, ad.tennis.cnt suit la convention R : il indique qu'il s'agît d'un arbre de décision (préfixe ad), pour le jeu de tennis (tennis !) et qu'il s'agît des paramètres de contrôle (cnt) ; des points (.) séparent ces différentes informations. Tout cela est complétement libre ; on aurait pu l'appeler toto, R ne nous l'aurait pas interdit. Par contre, pour nous, humains, c'est autrement plus parlant. Vous prendrez donc l'habitude de nommer les variables en suivant ce principe.)
> ad.tennis <- rpart (Jouer ~ Ciel + Temperature + Humidite + Vent, tennis, control = ad.tennis.cnt)On peut alors afficher le résultat de la construction sous forme de texte. On obtient :
n= 14 node), split, n, loss, yval, (yprob) * denotes terminal node 1) root 14 5 Oui (0.3571429 0.6428571) 2) Ciel=Ensoleille,Pluie 10 5 Non (0.5000000 0.5000000) 4) Humidite>=82.5 5 1 Non (0.8000000 0.2000000) 8) Temperature>=20.25 4 0 Non (1.0000000 0.0000000) * 9) Temperature< 20.25 1 0 Oui (0.0000000 1.0000000) * 5) Humidite< 82.5 5 1 Oui (0.2000000 0.8000000) 10) Temperature< 18.25 1 0 Non (1.0000000 0.0000000) * 11) Temperature>=18.25 4 0 Oui (0.0000000 1.0000000) * 3) Ciel=Couvert 4 0 Oui (0.0000000 1.0000000) *Prenez le temps d'essayer de comprendre ce qui est affiché.
On peut également obtenir une représentation graphique. La commande plot dessine l'arbre alors que la commande text affiche le texte dans les nœuds et sur les branches. :
> plot (ad.tennis)> text (ad.tennis)Voyez si ce que vous voyez graphiquement est compatible avec ce que vous aviez compris dans la représentation textuelle. Si nécessaire, reprenez le temps de comprendre la représentation textuelle. L'aspect graphique de l'arbre peut être paramétré. Essayez et interprétez chaque commande ainsi que toutes les valeurs affichées :
On construit un modèle, ici un arbre de décision, pour pouvoir classer de nouvelles données. Dans la librairie rpart() de R, la fonction predict() joue ce rôle. Elle prend en paramètres l'arbre et un data frame qui contient les données dont il faut prédire la classe. Pour prédire la classe des données du jeu d'exemples (avec lesquels on a construit l'arbre de décision), on tapera la commande :
> predict(ad.tennis, tennis) Interprétez le résultat obtenu. Pour celà, allez voir l'aide sur la fonction predict(). Cette fonction est générique à de nombreux modèles de prédiction donc allez voir l'aide sur predict.rpart(). Donnez l'interprétation du résultat et essayez predict(ad.tennis, tennis,"class"), predict(ad.tennis, tennis,"prob"), predict(ad.tennis, tennis,"vector").
1. Utilisez l'arbre pour donner une prédiction dans les situations suivantes :
Ciel Temperature Humidite Vent1 Ensoleille 30 90 Faible2 Couvert 25 70 Fort3 Pluie 15 86 FortVous avez deux possibilités :
Il FAUT que vous sachiez faire les deux. Donc, faites-le.
2. Déterminez la valeur du paramètre minsplit pour obtenir l'arbre suivant :
1) root 14 5 Oui (0.3571429 0.6428571) 2) Ciel=Ensoleille,Pluie 10 5 Non (0.5000000 0.5000000) 4) Humidite>=82.5 5 1 Non (0.8000000 0.2000000) * 5) Humidite< 82.5 5 1 Oui (0.2000000 0.8000000) * 3) Ciel=Couvert 4 0 Oui (0.0000000 1.0000000) *On va utiliser ici le jeu de données car.test.frame. Affichez les 5 premières lignes. Donnez le nombre de lignes, le nombre d'attributs, le nom des attributs, le type des attributs, les statistiques descriptives sur ce jeu de données. Nous allons, par la suite, essayer de prédire la valeur de l'attribut Type en fonction des valeurs des autres attributs. Quel est le nombre de classes (de valeurs de Type) ? Quelle est la procédure majoritaire ? Quelle est son erreur apparente ?
Construisez un arbre de décision (appelez-le ad.car) à partir de ce jeu de données pour prédire la variable Type à partir des autres variables (Price, Country, ...). Vous utiliserez minsplit=1. Que pensez-vous de l'arbre obtenu (taille, lisibilité,...) ? Regardez les prédictions pour la "Chevrolet Camaro V8", la "Chevrolet Beretta 4" et la "Plymouth Laser". Regardez le résultat de summary(ad.car) avec ,en particulier, un regard sur ce qui se passe aux différents noeuds. Nous allons voir comment calculer l'erreur apparente et estimer l'erreur réelle et expliquer la table obtenue en résultat de summary(ad.car).
Élagage
L'arbre produit peut être élagué à l'aide de la fonction prune() (qui veut dire élaguer, en anglais) (ça veut dire prune aussi, d'ailleurs). Essayez par exemple, sur l'arbre des voitures prune(ad.car, 0.2). La valeur passée en paramètre (0.2) s'appelle le « complexity parameter ». Sa définition exacte se trouve dans le document pdf mis en référence. Augmentez progressivement la valeur de ce paramètre pour visualiser les différents élagages de l'arbre ad.car jusqu'à obtenir un élagage qui correspond à la procédure majoritaire.
On peut noter que vous pouvez également spécifier un "complexity parameter" directement en spécifiant ad.car.cnt <- rpart="" control="" minsplit="1," cp="0.2)</tt"> avant l'appel de rpart() .
rpart calcule les élagués et estime les erreurs
L'algorithme rpart() construit et produit un arbre (grand) d'erreur apparente petite (avec un critère d'arrêt dépendant de minsplit) mais calcule également les élagués, leur erreur apparente et une estimation de l'erreur réelle. Pour estimer cette erreur réelle, rpart() effectue une validation croisée à 10 plis sur chaque arbre élagué. Les mesures effectuées au long de cette procédure sont stockées dans une table dénommée la cptable. La commande ad.car$cptable affiche cette table :
> ad.car$cptable CP nsplit rel error xerror xstd1 0.28888889 0 1.00000000 1.1333333 0.061463632 0.20000000 1 0.71111111 0.8444444 0.082949733 0.13333333 2 0.51111111 0.7111111 0.085874834 0.04444444 3 0.37777778 0.5333333 0.084327405 0.03333333 5 0.28888889 0.6222222 0.085874836 0.02222222 9 0.15555556 0.5555556 0.084862517 0.01111111 14 0.04444444 0.5111111 0.083690598 0.01000000 18 0.00000000 0.5111111 0.08369059Il est possible que vous n'obteniez pas les mêmes résultats car le choix des exemples dans la validation croisée est aléatoire. rel error mesure l'erreur apparente (erreur d'entraînement). xerror mesure le taux d'erreur dans la validation croisée à 10 plis que l'on considère comme un estimateur de l'erreur réelle. xstd est l'écart-type de l'erreur de validation croisée.
Les autres arbres
Les lignes précédentes correspondent aux différents élagages de cet arbre qui produisent des arbres de plus en plus petits, jusqu'à obtenir une racine-feuille.
Vous pouvez obtenir tous les autres arbres aussi (les 7 autres, ici). Pour cela, il faut indiquer le cp dans la fonction prune(). Il faut bien comprendre comment se lit cette table et la relation entre valeur de cp et l'arbre élagué correspondant :
Notez bien que la borne inférieure de l'intervalle est exclus : la valeur de cp = 0,2 correspond à l'arbre 3, pas au 2. Visualisez les arbres obtenus pour ces différentes valeurs de cp. Vous devez retrouver les arbres obtenus avec la fonction prune().
Vous avez obtenu cet arbre dont nous n'indiquons que le début ci-dessous :
> ad.carn= 60node), split, n, loss, yval, (yprob) * denotes terminal node 1) root 60 45 Compact (0.25 0.05 0.22 0.22 0.15 0.12) 2) Weight>=2567.5 45 30 Compact (0.33 0.067 0.29 0 0.16 0.16) 4) Weight< 3127.5 24 9 Compact (0.62 0 0.17 0 0.21 0)...Les nombres 60 et 45 indiquent respectivement le nombre d'exemples avec lesquels l'arbre est construit (60) et le nombre d'exemples mal classés par la racine-feuille (45). Réduit à une simple racine, c'est-à-dire à la procédure majoritaire, l'arbre fait donc une erreur de 45/60.
Dans la cptable, les valeurs d'erreur sont normalisées pour en simplifier l'interprétation. Cette normalisation consiste à faire en sorte que l'erreur apparente de la racine-feuille soit égale à 1. Clairement, pour cela, R a divisé cette valeur (ainsi que toutes les valeurs des colonnes rel error, xerror et xstd) par l'erreur de la racine-feuille que l'on a calculé juste au-dessus (45/60).Maintenant, on peut calculer l'erreur apparente de chacun des arbres construits par rpart :
vec.err.app <- ad="" car="" cptable="" rel="" error="" 45="" 60="" pre="">L'arbre qui nous intéresse est celui qui minimise xerror*45/60 + xstd (l'erreur réelle estimée + 1 écart-type). Si plusieurs arbres minimisent cette valeur, on prend toujours le plus petit (à performances équivalentes, on choisit le plus petit modèle). Construisez le vecteur vec.err.eststd contenant xerror*45/60 + xstd, déterminez l'indice de valeur minimale, en déduire la valeur optimale cp.opt de cp, et construisez l'arbre optimal ad.car.opt en élaguant l'arbre ad.car avec la valeur de cp.opt.
Pour visualiser les erreurs, vous pouvez tracer l'évolution des erreurs apparente et réelle en fonction de la taille de l'arbre (nombre de nœuds = nsplit + 1). On pourra utiliser les commandes lines() et points().
Toujours avec le jeu de données car, on peut aussi essayer de prédire un autre attribut qualitatif.Etudiez le jeu de données IRIS en le visualisant et en affichant les statistiques descriptives de ce jeu de données à l'aide de la commande summary(). L'objectif est de prédire le type d'iris (5ème colonne) à partir des tailles des sépales et des pétales (quatre premières colonnes). Déterminez l'arbre de décision optimal, une estimation de son erreur, un intervalle de confiance.Lancer R et charger les jeux de données :
house.app <- read.csv("http://www.grappa.univ-lille3.fr/~gilleron/jeuxdonnees/house.data",header=TRUE)
house.test <- read.csv("http://www.grappa.univ-lille3.fr/~gilleron/jeuxdonnees/house.test",header=TRUE)
Le jeu de données house.app est l'échantillon d'apprentissage. Le jeu de données house.test est le jeu de test qui sert à estimer l'erreur réelle.
On continue sur le jeu de données des voitures et on revient à la prédiction du « Type ». Parmi les autres attributs, on veut déterminer celui qui est le moins important pour prédire le type. Pour cela, on va construire des arbres de décision utilisant tous les attributs sauf 1. L'attribut manquant qui sera associé au meilleur arbre de décision est l'attribut le moins important.On indique uniquement les bases de la fonction plot(). Elle permet de faire des graphes de courbes. Supposons que vous tapiez :
x <- c="" 1="" 3="" 2="" -5="" y="" -="" 0="" 9="" -0="" 05="" plot="" x="" pre="">vous obtenez un graphique avec 4 points dont les abscisses sont dans le vecteur x, les ordonnées dans le vecteur y. Plutôt que des vecteurs, ce peut être aussi des colonnes (attributs) d'un data frame.
Vous pouvez spécifier des légendes et une couleur (verte) pour les points :
plot (x, y, main = "graphique de base", xlab = "légende des x", ylab = "légende des y", col = "green")lines() permet d'ajouter une ligne brisée sur un graphique déjà commencé avec plot(). Supposons que l'on veuille ajouter une ligne bleue qui va du point (-2, 0.2) au point (0, 0.1), de là au point (-4, 0.6) et de là, au point (1, 0.5). Je tape les commandes suivantes : (en supposant que vous avez tapé au préalable les commandes ci-dessus concernant la fonction plot())
x.zigzag <- c="" -2="" 0="" -4="" 1="" y="" zigzag="" -="" 2="" 6="" 5="" lines="" x="" col="blue" pre="">Le paramètre lty permet de représenter les segments en pointillés, ... Par exemple :
lines (c(-1,1,-3), c (0.1, -0.1, 0.5), col = "green", lty=2)La valeur de lty est un entier compris entre 1 (lignes pleines = par défaut) et 6. Faites des essais.
points() permet d'ajouter des points sur un graphique déjà commencé avec plot(). Supposons que l'on veuille ajouter des points rouges en (0, 0), (1, 1) et (-2, 0.5). Je tape les commandes suivantes : (en supposant que vous avez tapé au préalable les commandes ci-dessus concernant la fonction plot())
x.points <- c="" 0="" 1="" -2="" y="" points="" -="" 5="" x="" col="red" pre="">Le paramètre pch permet de représenter les points de différentes manières (disque plein, carré, triangle, ...). Par exemple :
points (c (0.45, 0.45), c(0.55, 0.65), col = "dark blue", pch = 19)affiche les points sous forme de disques (pch = 19) bleus foncés (col = "drak blue"). La valeur de pch est un entier compris entre 1 (par défaut : un cercle) et 25. Faites des essais.
Nous allons utiliser la version démonstration de l'algorithme C5.0 d'arbres de décision conçu par R. Quinlan. Cet algorithme est diffusé par la société rulequest, il est aussi implanté dans des suites de fouille de données. La version de démonstration sous Windows s'appelle See5-demo. la limitation porte sur le nombre d'exemples qui est limité à 400.
Copiez le dossier Sample qui se trouve sur le disque local C dans Program Files/See5 Demo sur le disque U (votre répertoire local). Dans ce même dossier copiez le fichier tennum.txt qui se trouve à l'adresse http://www.grappa.univ-lille3.fr/~gilleron/jeuxdonnees.
* Lancer see5. Regardez l'aide. En particulier allez voir et comprendre l'aide sur les fichiers d'extension .data et .names. * Modifiez le fichier tennum.txt (pour créer un fichier tennis.data. Créez le fichier tennis.names. * Construisez un arbre de décision avec see5 en utilisant les paramètres par défaut. Quel est la taille de l'arbre, l'erreur apparente obtenue ? * Comment est classé l'exemple (Ensoleille, 18, 80, Fort) ? L'exemple (Ensoleille, 18, 100, Fort) ? L'exemple (Ensoleille, 18, ?, Fort) ? * Lancez see5 avec le choix de générer un système de règles. Comparez avec l'arbre obtenu précédemment. Donnez des avantages et inconvénients de ces deux représentations.
* Visualisez les contenus des fichiers names et data associés aux jeux de données anneal, banding, breast-cancer, housing et soybean. * Complétez un tableau avec en ligne le nom du jeu de données et en colonnes : le nombre d'attributs, le type des attributs, le nombre d'exemples en apprentissage, en test et le nombre de classes du problème.
L'algorithme C5.0 effectue une opération d'élagage après avoir construit un arbre de décision avec un critère basé sur l'entropie. Le critère d'élagage est basé sur un test statistique contrôlé par un coefficient CF dont la valeur par défaut est 25. * Lancer see5 sur les problèmes housing et soybean avec les paramètres par défaut. Donner les tailles des arbres, les erreurs apparentes et estimées. Comment est estimée l'erreur réelle ? * Lancer see5 sur les problèmes housing et soybean pour des valeurs de CF égales à 1, 10, 25, 50, 75 et 100. Vous noterez pour chaque expérience la taille de l'arbre élagué, l'erreur apparente et l'erreur estimée. Vous en déduirez le rôle de CF et commenterez les résultats.
Mêmes questions en laissant CF à sa valeur par défaut et en faisant varier le paramètre Minimum Case. Concluez sur son rôle.
On considère le problème banding. * Contient-il des valeurs manquantes ? en apprentissage ? en test ? pour quels attributs ? * Lancer see5 sur ce problème avec les valeurs par défaut. L'algorithme a-t-il utilisé les exemples avec valeur manquante ? Comment l'arbre classe-t-il un exemple avec valeur manquante ?
Lancer see5 sur le problème anneal avec les paramètres par défaut en demandant la validation croisée. Interprétez les résultats. Un arbre a-t-il été construit par see 5 ? Comment le construirait-on ? Comment utiliserait-t-on la validation croisée ?
* Lancer see5 sur le problème breast-cancer avec les paramètres par défaut. Noter la taille de l'arbre résultat, l'erreur apparente et l'erreur estimée. Noter les tests utilisés dans l'arbre. * Modifier le fichier breast-cancer.names pour déclarer les attributs comme discrets avec des valeurs de 1 à 10 et enregistrez le sous le nom breast-cancer-discret.names. Copier les fichiers breast-cancer.data et breast-cancer.test dans breast-cancer-discret.data breast-cancer-discret.test. Lancer see5 sur le problème breast-cancer-discret avec les paramètres par défaut. Noter la taille de l'arbre résultat, l'erreur apparente et l'erreur estimée. Noter les tests utilisés dans l'arbre. * Lancer see5 sur le problème breast-cancer-discret en demandant à Grouper les valeurs. Noter la taille de l'arbre résultat, l'erreur apparente et l'erreur estimée. Noter les tests utilisés dans l'arbre.
Sur le problème banding, définir des coûts permettant de ne jamais classer un "noband" en "band".
Il existe plusieurs implantations des SVMs en R. Nous utilisons le package e1071. En cas de non installation de ce package, vous pouvez l'installer par la commande install.packages('e1071').
Construisez les jeux de données suivants :
data1 <- seq(1,10,by=2) classes1 <- c('a','a','a','b','b') test1 <- seq(1,10,by=2) + 1 data2 <- seq(1,10) classes2 <- c('b','b','b','a','a','a','a','b','b','b')Première découverte du package en parcourant l'aide sur la fonction svm() en repérant les paramètres qui vous semblent importants.
Interprétez la commande suivante :
model1 <- svm(data1,classes1,type='C',kernel='linear')Exécutez les commandes suivantes en interprétant les résultats
print(model1) summary(model1) predict(model1,data1) table(predict(model1,data1), classes1) predict(model1,test1)Interprétez la commande suivante :
model2 <- svm(data2,classes2,type='C',kernel='polynomial', degree= 2)Lancez et interprétez les commandes suivantes :
model2 <- svm(data2,classes2,type='C',kernel='radial') table(predict(model2,data2), classes2)Que peut-on dire des performances obtenues ? Est-ce surprenant ?
Etudiez le jeu de données IRIS en le visualisant et en affichant les statistiques descriptives de ce jeu de données à l'aide de la commande summary(). L'objectif est de prédire le type d'iris (5ème colonne) à partir des tailles des sépales et des pétales (quatre premières colonnes).
On se limite d'abord à la prédicion du type d'iris en utilisant seulement les deux premiers attributs. Nous allons utiliser les paramètres par défaut de la fonction svm(). Pour celà, lancez les commandes suivantes :
x <- iris[,1:2] y <- iris[,5] svm.default.iris <- svm(x,y) Pour étudier les performances du modèle sur l'ensemble d'apprentissage, tapez les commandes suivantes
pred <- predict(svm.default.iris, x) table(pred,y) plot(iris[,1], iris[,2], col=as.integer(y)) plot(iris[,1], iris[,2], col=as.integer(pred))Cherchez comment utiliser la commande svm pour effectuer une validation croisée. Vous pourrez visualiser l'erreur estimée par la commande summary(). On considère le problème IRIS avec les quatre premiers attributs (longueur et largeur des sépales, des pétales) pour prédire l'espèce (cinquième attribut).
Comparez les résultats obtenus par les arbres de décision sur IRIS et les SVMs par défaut sur le même jeu de données. On pourra comparer les résultats obtenus par validation croisée. Mais, quelle serait la procédure à mettre en oeuvre pour que les résultats des validations croisées soit réellement comparables.
Lancer R et charger les jeux de données :
house.app <- read.csv("http://www.grappa.univ-lille3.fr/~gilleron/jeuxdonnees/house.data",header=TRUE)house.test <- read.csv("http://www.grappa.univ-lille3.fr/~gilleron/jeuxdonnees/house.test",header=TRUE)Le jeu de données house.app est l'échantillon d'apprentissage. Le jeu de données house.test est le jeu de test qui sert à estimer l'erreur réelle. Etudier ce jeu de données avec les SVMs. Vous testerez avec noyau linéaire, polynomial de degré 2, de degré 3, Gaussien. Vous estimerez les performances sur l'ensemble test. vous comparerez avec les résultats obtenus pour les arbres de décision.
L'algorithme de segmentation hiérarchique ascendante est disponible au travers de la fonction hclust() de R. Elle s'applique non pas à un jeu de données, mais à une matrice de distance. On peut facilement obtenir cette matrice pour un data frame à l'aide de la fonction dist() qui calcule la distance euclidienne entre chaque paire de données du data frame.
iris [1:6,1:4] dist(iris [1:6,1:4]) dist(iris [,1:4])Par conséquent, si on souhaite effectuer une classification hiérarchique ascendante sur les 4 premières colonnes (les quatre attributs longueur et largeur des sépales et des pétales), on appelle les deux fonctions et on mémorise le résultat :
iris.hclust <- hclust (dist (iris [,1:4]))À l'issue de son exécution, hclust() a construit un dendrogramme. On peut le visualiser à l'aide de la fonction plot() avec la commande
plot(iris.hclust). Chaque feuille du dendrogramme est étiquetée par le numéro d'une donnée. L'affichage permet de visualiser les regroupements hiérarchiques. Il reste à constituer les groupes. Plusieurs méthodes sont possibles pour découper le dendrogramme et obtenir une segmentation en k groupes, k étant fixé.
D'une segmentation hiérarchique, on peut obtenir autant de groupes (de 1 à N) que l'on veut en découpant l'arbre au nouveau adéquat. Cela se fait avec la fonction cutree comme cela : pour obtenir 3 groupes à partir de la segmentation hiérarchique précédente, on tape la commande
cutree(iris.hclust, 3)si on souhaite découper en 3 groupes. Cette commande fournit en sortie un vecteur de N entiers : l'élément i indique le groupe de la donnée i ; les groupes sont numérotés de 1 à k.
Pour visualiser le clustering obtenu, on peut utiliser la fonction rect.hclust() qui fait la même chose que cutree(), mais le fait visuellement. Ainsi la commande
rect.hclust(iris.hclust,5)met en évidence les 5 groupes du dendrogramme (remarque : il faut avoir fait un plot (iris.hclust) auparavant). On peut aussi spécifier la couleur des bordures
rect.hclust(iris.hclust, 5, border = c ("blue", "green", "red", "pink", "black"))et on peut aussi n'entourer que certains des groupes, par exemple le deuxième et le cinquième
rect.hclust(iris.hclust, 5, which = c (2,5))De plus, si l'on affecte le résultat à un objet en tapant :
iris.hclust.5 <- rect.hclust (iris.hclust, 5)alors iris.hclust.5 est une liste contenant 5 éléments (autant que de groupes) et chaque élément de la liste contient la liste des numéros des données de ce groupe. Question : comment faites-vous pour connaître la moyenne des données de chacun des 5 groupes (de la manière la plus simple qui soit) ?
On peut aussi afficher le dendrogramme et indiquer à la souris où (les segments verticaux) on veut couper. On utilise pour cela la fonction identify :
plot (iris.hclust) identify (iris.hclust)Vous pouvez alors cliquer avec le bouton gauche de la souris sur les segments verticaux au niveau desquels vous voulez découper le dendrogramme. Faites 4 découpes (par exemple). Quand vous avez terminé, cliquez avec le bouton droit (tout cela dans la fenêtre graphique). À nouveau, vous pouvez récupérer la composition de chacun des groupes en affectant le résultat de la fonction identify à un objet :
plot (iris.hclust) iris.hclust.id <- identify (iris.hclust)Comme avec rect.hclust(), iris.hclust.id est une liste dans laquelle chaque élément correspond à un groupe et contient la liste des numéros des données de ce groupe.
Effectuez une classification hiérarchique ascendant avec les trois méthodes single (distance minimum), complete (par défaut, distance maximum) et average (distance average). Comparez les résultats ainsi que ceux obtenus avec les k-moyennes. Faites ceci pour les jeux de données : jeu1.txt, jeu2.txt, jeu3.txt et jeu11.txt.
On considère le jeu de données jeu4.txt. Faites en une segmentation hiérarchique en 3 groupes avec les méthodes single et complete. Visualisez le jeu de données en coloriant chaque point par une couleur différente en fonction du groupe. Qu'en déduisez-vous sur la capacité à gérer des formes quelconques ?
on considère le jeu de données jeu5.txt. Répondez aux mêmes questions que dans l'exercice précédent.
Prendre le jeu de données jeu1. Construire un jeu de données jeu1.2 qui contient 2000 lignes en répétant jeu1, jeu1.3 qui contient 3000 lignes en répétant 3 fois jeu1, etc. Lancez sur ces jeux de données l'algorithme des k-moyennes et la classification hiérarchique, mesurez les temps de calcul et comparez. Qu'en concluez-vous ?
Nous allons utiliser une implantation en R de l'algorithme Apriori disponible dans le package arules de R. Si la librairie n'est pas disponible, une des façons de l'installer est de taper dans R, donc après avoir lancé le logiciel R, la commande :
install.packages("arules",repos="http://R-Forge.R-project.org")Cette commande aura pour effet d'installer le paquet dans votre répertoire. Sinon vous pouvez télécharger un fichier d'installation compressé et installer le package. Il peut être nécessaire d'installer aussi le package Matrix.
Nous allons travailler sur le jeu de transaction Adult :
library("arules") data("Adult") inspect(Adult[1:2])Combien y a-t-il de transactions ? Combien y a-t-il d'items ? Quel est le lien entre les items et les 13 attributs catégoriels précédents ? Quel est la longueur des transactions ? Pourquoi certaines transactions ont-elles moins de 13 items ? Regardez l'aide sur les fonctions itemFrequency() et itemFrequencyPlot(). Affichez le graphique des items de support supérieur à 0.2. Affichez le graphique des 10 items les plus fréquents.
Enfin il est possible d'exécuter Apriori avec la fonction apriori(). Regardez l'aide sur cette fonction. Par exemple pour obtenir les règles ayant un support d'au moins 1% et une confiance supérieure à 60%, il suffit de lancer la commande :
rules<-apriori(Adult,parameter=list(support=0.01,confidence=0.6))Comprenez les messages affichés lors de l'exécution de l'algorithme. Vous pouvez utiliser les fonctions summary() et inspect() pour répondre aux questions suivantes : combien de règles ? Pour combien de transactions ? Affichez les dix premières règles obtenues et discutez leur utilité. Affichez les dernières règles. Diminuez la valeur de la confiance (par exemple 0.1) et du support (par exemple 0.001, 0.0001, 0.00001) et regardez l'évolution du nombre de règles.
On souhaite extraire de l'information du jeu de transactions et on constate que le nombre de règles obtenu peut être très grand, bien plus grand que le nombre de transactions ! Il faut donc être capable de fouiller l'ensemble des règles obtenues pour chercher des règles utiles.
Un premier outil est de trier les règles. Regardez l'aide sur la fonction sort(). Calculez l'ensemble des règles de support supérieur à 0.1. Les trier par valeur de confiance. Affichez les 10 premières règles. Que pensez-vous de l'utilité des règles obtenues ? Les trier par valeur d'amélioration (lift). Mêmes questions.
Un deuxième outil est de spécifier des propriétés des règles recherchées. On va donc spécifier la forme des règles qui nous intéresse avec la fonction subset(). On peut ensuite trier le résultat puis regarder les règles obtenues. Par exemple, on peut choisir de se focaliser sur la prédiction de règles ayant en membre droit l'item income=small et trier par confiance :
rules<-apriori(Adult,parameter=list(support=0.001)) rules.IncomeSmall <- subset(rules, subset = rhs %in% "income=small") rules.IncomeSmall <- sort(rules.IncomeSmall, by = "confidence") inspect(rules.IncomeSmall)Vous remarquerez le petit nombre de règles obtenu. On peut aussi dans l'appel de subset() combiner des tests. Par exemple
subset = rhs %in% "income=small" & lift >1.5.Recherchez les règles permettant de prédire un gain en capital important. Il est aussi possible d'utiliser d'autres mesures d'intérêt des règles (hyper-lift, all-confidence).
Analysez le jeu de données Groceries
Analysez ce jeu de données lenses