Classification supervisée et non supervisée ; règles d'association

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.

• Cours 1 : Présentation de la problématique générale de la fouille de données, de l'apprentissage automatique et des statistiques inférentielles.
• Cours 2 : La classification supervisée : principes généraux, erreur réelle et erreur empirique, règles majoritaire du maximum de vraisemblance, de Bayes, le classeur de Bayes naïf, méthodes d'estimation de l'erreur réelle.
• Cours 3 : arbres de décision, introduction de l'entropie et du critère de Gini, algorithme d'apprentissage d'arbres de décision, techniques d'élagage, extensions (valeurs manquantes, groupement de valeurs, ratio de gain, ...).
• Cours 4 : neurone linéaire et séparation linéaire, algorithmes d'apprentissage par correction d'erreur et critiques, algorithme par descente de gradient (stochastique), le neurone sigmoide et apprentissage par descente de gradient .
• Cours 5 : les machines à vastes marges, les marges douces, le truc du noyau, les principaux noyaux.
• Cours 6 : Introduction de la classification non supervisée : les objets, les applications, les méthodes, les critères de comparaison des méthodes.
• Cours 7 : algorithme des k-moyennes, ses propriétés, définition de l'inertie, choix de k, critiques
• Cours 8 : classification hiérarchique ascendante, distances entre groupes, présentation de l'algorithme, critiques.
• Cours 9 : autres algorithmes tels que EM, DBscan et spectral clustering.
• Cours 10 : règles d'association, algorithme Apriori.

TP : manipuler des jeux de données en R

Les vecteurs

Création de vecteurs

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

Fonctions

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().

Opérations

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.

Indexation

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 !.

Exercice sur les vecteurs

Regardez l'aide sur la fonction runif(). Construisez le vecteur avec :

a <- runif(20)

1. Donnez la somme des composantes de a.
2. Donnez la moyenne et l'écart-type des composantes de a.
3. Affichez les déciles de a.
4. Affichez le vecteur de Booléen permettent d'afficher si une composante est inférieure ou égale à 0.25
5. Calculez la somme des composantes inférieure ou égale à 0.4
6. Regardez l'aide sur la fonction rnorm(). Construisez le vecteur avec : b <- rnorm(20)
7. Donnez la somme des composantes de b, la moyenne et l'écart-type des composantes de b.
8. Calculez le nombre de composantes de a qui sont inférieures à b.
9. Transformez à l'aide d'opérations arithmétiques et de fonctions a en un vecteur c d'entiers entre 1 et 5 pour simuler un tirage uniforme dans l'ensemble des entiers de 1 à 5.
10. Construisez un vecteur nombrec qui contient en composante i le nombre de composantes égales à i dans c. Note : la boucle for peut être utilisée sous la forme : for (i in 1:5) nombrec[i] <- ... Vérifier que pour un nombre de données grand, la répartition tend à être uniforme.

Matrices

Création de matrices

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)

Opérations sur les matrices

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)

Indexation des matrices

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)]

Exercice sur les matrices

1. Ecrire une fonction qui prend en entrée deux matrices A et B et qui retourne T si on peut calculer le produit AB.
2. Ecrire une fonction qui prend en entrée deux matrices A et B et qui retourne le produit AB quand on peut le caluler et un message d'erreur sinon.
3. Ecrire une fonction qui prend en entrée une matrice A (supposée carrée) et un entier n et qui retourne la matrice A élevée à la puissance n.
4. Ecrire une fonction sum.col qui prend en entrée une matrice A et qui retourne un vecteur dont la composante d'indice i est la somme des éléments de la colonne i de A.
5. Ecrire une fonction diag.sum.col qui prend en entrée une matrice A et qui retourne une matrice diagonale dont la diagonale est l'inverse de la somme des éléments des colonnes de A. Ou encore en colonne k de la matrice diagonale, on a l'inverse de la somme des éléments de la colonne k de A.

Data Frames -- tableaux de données

Qu'est ce qu'un data frame ?

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 29

Il 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.

Définir un data frame

à 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 ?

Manipuler les data frame en R

Quand le jeu de données est construit ou chargé, vous pouvez le visualiser :

> jeu1

Vous obtenez:

  p1.palmitic oleic l1.linoleic arachidic eicosenoic

1        1075  7823         672        60         29

2        1088  7709         781        61         NA

3         911    NA         549        63         29

4         966  7952         619        78         35

5        1051  7771         672        NA         46

6         911    NA         678        70         44

7         922  7990         618        56         29

La 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 :

• la donnée numéro 2 par jeu1 [2,]
• les données dont le numéro est compris entre 2 et 6 par jeu1[2:6,]
• la valeur de l'attribut 5 de la donnée 2 en spécifiant son numéro jeu1 [2, 5]
• les noms des attributs avec names(jeu1)
• la valeur de l'attribut eicosenoic de la donnée 2 en spécifiant son nom, comme ceci jeu1 [2,]$eicosenoic, ou comme cela jeu1 [2, "eicosenoic"] ou encore jeu1$eicosenoic[2]
• la valeur de cet attribut pour toutes les données en spécifiant son numéro jeu1 [,5], ou son nom comme ceci jeu1$eicosenoic, ou encore comme cela jeu1 [["eicosenoic"]]
• tous les attributs sauf les numéros 1 et 3 de la donnée numéro 2 : jeu1 [2, - c (1, 3)]
• et toutes les combinaisons que vous pouvez imaginer !

Statistiques élémentaires

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 :

• la fonction summary() qui s'applique à tous les attributs d'un jeu de données à la fois et fournit des statistiques descriptives élémentaires sur les données ;
• nrow() donne le nombre de lignes, donc de données dans le data frame ;
• ncol() donne le nombre de colonnes, donc d'attributs dans le data frame ;
• dim() donne le nombre de lignes et de colonnes ;
• names() donne le nom des attributs du data frame.

Le cas des attributs discrets (ou qualitatifs)

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().

Les valeurs manquantes

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.

Exercices sur les data frames

exercice valeurs manquantes

On travaille sur le jeu de données jeu2 qui correspond au fichier de données csjeu2.txt.

1. Utilisez la fonction summary() et dire quelles informations on obtient selon la nature de l'attribut.
2. Calculez la moyenne sur l'attribut oleic. Débrouillez-vous pour calculer la moyenne des valeurs non manquantes. Retrouve-t-on le même résultat que celui affiché avec summary() ?
3. Remplacez les valeurs manquantes de l'attribut oleic par la moyenne de cet attribut avec une formule, idem pour arachidic
4. Remplacez les valeurs manquantes de l'attribut eicosenoic par sa valeur la plus fréquente avec une formule.

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.

1. convertir les hauteurs en m
2. convertir les poids en kg
3. calculez les statistiques élémentaires sur ces attributs
4. tracez un graphique avec ces deux attributs
5. calculez l'imc des individus (poids en kg divisé par carré de la taille en m)
6. ajouter une colonne imc au data frame avec les valeurs calculées
7. remplacer la valeur de l'imc par T si l'imc est supérieur à 23 et par F sinon. Renommer la colonne imc en imcrisk.
8. ajouter un nouvel individu de valeur (1.60, 60, F)

Quelques graphiques

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))

Exercices

visualisation jeu de données Iris

1. Donnez le nombre de lignes, d'attributs (de colonnes)
2. Donnez le type des attributs. Y a-t-il des valeurs manquantes ?
3. Donnez le nombre d'iris dans chacune des 3 espèces : setosa, versicolor et virginica
4. Faites une représentation graphique selon les deux premiers attributs (Sepal.Length et Sepal.Width) en colorant les points par espèce.
5. Idem avec les attributs Petal.Length et Petal.Width
6. Idem avec les quatre attributs.

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

1. Donnez le nombre de lignes, d'attributs (de colonnes)
2. Donnez le type des attributs. Y a-t-il des valeurs manquantes ?
3. Vous remarquez que les données ont des noms. Affichez les caractéristiques de la Nissan Maxima V6.
4. Construisez le vecteur des effectifs par type de voiture, trouvez le type le plus fréquent, le vecteur des fréquences, faites un graphique (plot(table(car$Type)) et barplot(table(car$Type)).
5. Que peut-on dire du type de l'attribut reliability ? Cela vous semble-t-il la bonne solutions ? Transformez le facteur (le jeu de données car doit être modifié en conséquence). Affichez les voitures les plus fiables (plus haute valeur de reliability).
6. Etudiez les dépendances 2 à 2 entre attributs en visualisant le jeu de données. Vous serez attentif aux affichages en fonction des types des attributs :
7. > plot(car$Weight,car$Disp)
8. > plot(car$Type,car$Price)
9. > plot(car$Price, car$Type)

Arbres de décision

Introduction

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.

La construction d'un arbre de décision

Chargement de la bibliothèque rpart

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.

Chargement du jeu de données

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 Jouer

1  Ensoleille        27.5       85 Faible    Non

2  Ensoleille        25.0       90   Fort    Non

3     Couvert        26.5       86 Faible    Oui

4       Pluie        20.0       96 Faible    Oui

5       Pluie        19.0       80 Faible    Oui

6       Pluie        17.5       70   Fort    Non

7     Couvert        17.0       65   Fort    Oui

8  Ensoleille        21.0       95 Faible    Non

9  Ensoleille        19.5       70 Faible    Oui

10      Pluie        22.5       80 Faible    Oui

11 Ensoleille        22.5       70   Fort    Oui

12    Couvert        21.0       90   Fort    Oui

13    Couvert        25.5       75 Faible    Oui

14      Pluie        20.5       91   Fort    Non

Vous 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).

Construction d'un arbre de décision

La commande suivante permet de construire l'arbre de décision en précisant :

• l'attribut qui doit être prédit (la classe : Jouer) ;
• les attributs qui doivent être utilisés pour effectuer cette prédiction (pour l'instant, ce seront les 4 autres attributs) ;
• le jeu d'exemples avec lequel on construit l'arbre ;

> ad.tennis <- rpart (Jouer ~ Ciel + Temperature + Humidite + Vent, tennis)

Dans cette commande, la notation :

Jouer ~ Ciel + Temperature + Humidite + Vent

est 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.tennis

Quel 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é.

Représentation graphique des arbres

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 :

• plot (ad.tennis, uniform=T)
• text (ad.tennis, use.n=T, all=T)
• plot (ad.tennis, branch=0)
• plot (ad.tennis, branch=.7)
• text (ad.tennis, use.n=T)
• plot (ad.tennis, branch=.4, uniform=T, compress=T)
• text (ad.tennis, all=T,use.n=T)
• plot (ad.tennis, branch=.2, uniform=T, compress=T, margin=.1)
• text (ad.tennis, all=T, use.n=T, fancy=T)

La prédiction de la classe d'une donnée par un arbre de décision

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").

Exercice

1. Utilisez l'arbre pour donner une prédiction dans les situations suivantes :

        Ciel Temperature Humidite   Vent

1 Ensoleille          30       90 Faible

2    Couvert          25       70   Fort

3      Pluie          15       86   Fort

Vous avez deux possibilités :

1. mettre ces données dans un fichier dont le format est similaire à tennum.txt, puis le chargez dans un data frame et faire la prédiction ;
2. créer directement un data frame.

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) *

Arbre optimal et élagage

Exercice

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).

Validation croisée, élagage et estimation des erreurs apparente et réelle

É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       xstd

1 0.28888889      0 1.00000000 1.1333333 0.06146363

2 0.20000000      1 0.71111111 0.8444444 0.08294973

3 0.13333333      2 0.51111111 0.7111111 0.08587483

4 0.04444444      3 0.37777778 0.5333333 0.08432740

5 0.03333333      5 0.28888889 0.6222222 0.08587483

6 0.02222222      9 0.15555556 0.5555556 0.08486251

7 0.01111111     14 0.04444444 0.5111111 0.08369059

8 0.01000000     18 0.00000000 0.5111111 0.08369059

Il 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 :

• l'arbre le plus élagué (ligne 1 de la cptable) s'obtient pour cp dans l'intervalle ]0.28888889; 1] ;
• le deuxième (un peu moins élagué) (ligne 2 de la cptable) s'obtient pour cp dans l'intervalle ]0.2; 0.28888889] ;
• le troisième (encore un peu moins élagué) (ligne 3 de la cptable) s'obtient pour cp dans l'intervalle ]0.13333333; 0.2] ;
• etc.

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().

Détermination de l'arbre optimal

Vous avez obtenu cet arbre dont nous n'indiquons que le début ci-dessous :

> ad.car

n= 60

node), 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().

Exercices

Exercice 1

Toujours avec le jeu de données car, on peut aussi essayer de prédire un autre attribut qualitatif.

• On peut ainsi tenter de prédire « Country ». Construisez l'arbre de décision non élagué avec minsplit=1. Déterminez l'arbre de décision optimal.
• On peut ainsi tenter de prédire « Reliability ». Mais cet attribut qualitatif prend des valeurs qui sont considérées comme numériques. mais sa valeur est un nombre. Dans ce cas, rpart croit que c'est un attribut quantitatif. Aussi, pour répondre correctement à la question, il faut d'abord transformer l'attribut « Reliability » en un attribut qualitatif. Ceci peut être fait à l'aide de la fonction as.factor() ou en remplaçant les valeurs numériques 1, 2, 3, 4 et 5 par les valeurs « un », « deux », « trois », « quatre » et « cinq ». Construisez l'arbre de décision non élagué avec minsplit=1. Déterminez l'arbre de décision optimal.

Exercice 2

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.

Exercice 3

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.

1. Quel est le nombre d'exemples en apprentissage ? en test ? Quel est le nombre d'attributs ? Le type des attributs ? Supprimez les deux attributs useless1 et useless2 dans les jeux de données house.app et house.test.
2. L'attribut à prédire est l'attribut class.price. Donnez le nombre d'éléments dans la classe top 20%, dans la classe bottom 80%. Donnez la procédure majoritaire. Son erreur apparente mesurée sur l'ensemble d'apprentissage. Son erreur estimée sur l'ensemble test
3. Apprendre avec CART en utilisant minsplit = 20. Donnez la taille de l'arbre, le test à la racine, l'erreur apparente mesurée sur l'ensemble d'apprentissage. Son erreur estimée sur l'ensemble test.
4. Apprendre avec CART en utilisant minsplit = 2. Donnez la taille de l'arbre, le test à la racine, l'erreur apparente mesurée sur l'ensemble d'apprentissage. Son erreur estimée sur l'ensemble test.
5. Apprendre avec CART en utilisant minsplit = 2 puis chercher l'arbre optimal. Donner son erreur estimée en test.
6. A-t-on appris, c'est-à-dire, améliore-t-on la procédure majoritaire ? Quel est le meilleur arbre trouvé ? Mèneririez vous d'autres essais ? Conclure.

Exercice 4*

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.

• Déterminez cet attribut le moins important (Aide : utilisez une boucle).
• Comment vous y prendriez-vous pour déterminer les attributs les plus importants ? Pensez-vous que vous pourriez mettre en œuvre cette idée dans un cas réel, ou même dans le cas du jeu de données car.test.frame ?

Références

• An Introduction to Recursive Partitioning Using the RPART Routines, T. M. Thernau et E. J. Atkinson, 1997
• Reference Manual

Annexes

La fonction plot()

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")

La fonction lines()

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.

La fonction points()

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.

C5.0 : un algorithme d'arbres de décision

Introduction

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.

Préparation du travail

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.

Exemple introductif

* 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.

Jeux de données

* 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.

Elagage

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.

Test d'arrêt

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.

Valeurs manquantes

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 ?

Validation croisée

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 ?

Attributs continus vs discrets - groupement de valeurs

* 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.

Les coûts

Sur le problème banding, définir des coûts permettant de ne jamais classer un "noband" en "band".

Les séparateurs à vastes marges (SVMs) en R

Choix du package

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').

Jeux d'échauffement et découverte

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.

Utilisation des SVMs linéaires

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)

• Est-ce que le modèle arrive à classer correctement les données ?
• Déterminez en vous aidant de la fonction predict() le seuil de coupure trouvé par le SVM linéaire. Le modèle model1 possède 4 vecteurs de support.
• Ajoutez cost=10 dans la commande de construction du modèle. On a désormais 2 vecteurs de support. Expliquez.
• Est-ce que vous trouvez un modèle linéaire pour le jeu numéro 2 ? Pourquoi ?

Utilisation des SVMs à noyau polynomial

Interprétez la commande suivante :

 model2 <- svm(data2,classes2,type='C',kernel='polynomial', degree

= 2)

• Est-ce que le modèle arrive à classer correctement les données ?
• Relisez l'aide sur svm(). Est-ce qu'on obtient des variations de performance en jouant sur le paramètre coef ?
• Même question avec le paramètre cost.
• Donnez une valeur des paramètres pour lesquelles les données d'apprentissage sont bien classées.

Utilisation des SVMs à noyau gaussien

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 ?

Etude des SVMs pour le jeu de données IRIS

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) 

1. Affichez les caractéristiques du modèle obtenu par les commandes print() et summary().
2. Quel est le type de prédiction choisi par défaut ?
3. Quel est le noyau utilisé par défaut ?
4. Quelle est la valeur du paramètre de régularisation choisi par défaut ?

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))

1. Calculez l'erreur apparente du SVM obtenu avec un noyau linéaire,
2. Même question avec un noyau polynomial de degré 2,
3. Même question avec un noyau polynomial de degré 3.
4. Quel est le meilleur choix des paramètres pour l'erreur apparente ?

Erreur réelle estimée par validation croisée

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).

1. Calculez l'erreur réelle estimée du SVM obtenu avec un noyau linéaire,
2. Même question avec un noyau polynomial de degré 2,
3. Même question avec un noyau polynomial de degré 3.
4. Quel est le meilleur choix de noyau avec la régularisation par défaut ?
5. Quel est le meilleur choix des paramètres pour les SVMs sur le jeu de données IRIS ?

Comparaison avec les arbres de décision

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.

Jeu de données House

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.

Clustering hiérarchique ascendant en R

La fonction de clustering hclust()

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]))

Définition et visualisation de la segmentation

À 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é.

choisir k : la fonction cutree()

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) ?

Choisir k : visualiser le dendogramme

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.

Exercices

Exercice 1 : IRIS

1. Faites une classification hiérarchique des iris puis construisez une segmentation en 3 groupes. Faites un graphique représentant les iris colorés en fonction de leur groupe en considérant les différentes projections sur deux attributs.
2. Comparez la segmentation à 3 groupes obtenue par segmentation hiérarchique avec celle obtenue par les k-moyennes : visuellement puis via leur matrice de confusion.
3. Mêmes questions pour une segmentation en 4 groupes.
4. Par défaut, la fonction hclust() utilise la distance entre groupes nommée "complete". Regardez l'aide sur la fonction hclust(). Comparez les résultats obtenus avec les distances du cours : minimum, maximum et mean.

Exercice 2 : variations sur un jeu de données

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.

Exercice 3 : les serpentins

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 ?

Exercice 4 : les cercles concentriques

on considère le jeu de données jeu5.txt. Répondez aux mêmes questions que dans l'exercice précédent.

Exercice 5 : passage à l'échelle

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 ?

Règles d'association en R

package arules

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.

Jeu de transactions

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.

La fonction apriori()

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.

Fouiller les 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).

Exercices

Autres questions sur le jeu Adult

1. Lancez Apriori pour obtenir les règles d'association avec support 10% et confiance supérieure à 50%. Cherchez les règles de membre gauche contenant "age=Young" et de membre droit "marital-status=Never-married" et d'amélioration supérieure a 2. Les trier par confiance.
2. Lancez Apriori pour obtenir les règles d'association avec support 1%. Cherchez les règles de membre gauche contenant "age=" et de membre droit "income=large" et d'amélioration supérieure à 1 (allez voir l'aide sur subset et les variantes du prédicat %in%). Les trier par support.
3. Un autre problème des règles de décision peut venir du fait qu'il est parfois long d'effectuer les calculs à cause du nombre de données. Dans ce cas, il peut être intéressant de ne travailler que sur un sous échantillon des données initiales. Cela peut se faire simplement grâce à la commande sample. Comme taille de sous échantillon, si l'on vise un support s et une confiance 1-c avec un taux d'erreur acceptable e, il est raisonnable de prendre 2 log(c)/(se). Vous vérifierez que le graphe des fréquences est sensiblement le même ainsi que pour les meilleures règles obtenues, le tout avec un temps de calcul inférieur (pouvant être mesuré grâce à la commande system.time(). Mais notez qu'il vaut valider les règles obtenues et que vous ne pourrez pas obtenir des associations entre intems peu fréquents car ceux-ci peuvent disparaître dans l'échantillonnage.

Sur un jeu de transactions classique

Analysez le jeu de données Groceries

Sur le jeu LENSES

Analysez ce jeu de données lenses