Programmation R pour la fouille de données

Ce cours-TD est une introduction à la programmation en R orienté vers la manipulation des vecteurs, matrices et tableaux de données. Vous trouverez ci-après un ensemble d'exercices associés à ce cours.

Les bases sur les fonctions en R

Blocs en R

Les blocs d'expressions sont des suites d'expressions entourés par des accolades. Les expressions sont évaluées les une à la suite des autres et les affectations sont effectives. Le bloc est lui-même une expression et sa valeur est la dernière expression évaluée dans le bloc.

monbloc <- {

tmp <- 1:10

somme <- sum(tmp) }

tmp

somme

monbloc

Arguments des fonctions

Les fonctions ont des arguments, souvent nombreux pour les fonctions préféfinies. Les arguments ont un nom formel. Lorsqu'on appelle une fonction les arguments doivent recevoir une valeur. Cette association de valeur peut être faite par :

position : donner les valeurs dans l'ordre
nom : donner les valeurs avec argument formel = valeur
valeur par défaut : ne pas donner de valeur alors la valeur par défaut est attribuée si ceci a été prévu dans la définition de la fonction.

args(seq.default)

seq()

seq(1,5)

seq(from=1,to=5)

seq(to=5)

seq(from=1, to=5, by=2)

seq(from=1, to=10, length.out=4)

La façon la plus sure reste par nom non abrégé.

Création de fonctions

On peut créer ses propres fonctions. La syntaxe est la suivante :

fun.name <- function(arglist) expr

où fun.name est le nom d'un objet pour la fonction, arglist est une liste d'arguments formels et expr une expression, généralement un bloc d'expressions. La liste d'arguments peut être vide pour une fonction sans paramètres ou contenir des noms formels séparés par des virgules ou contenir des arguments de la forme nom=valeur lorsqu'on souhaite avoir une valeur par défaut. Dans la fonction il peut y avoir un appel return(val) qui arrête la fonction et renvoie la valeur val. Si rien n’est précisé, la fonction renvoie la valeur de la dernière expression du bloc.

hello <- function() {print("Hello world")}

hello()

f <- function(x) { # f(x) = 3x^2

3 * x^2 # valeur renvoyée par la fonction }

f(1)

f(2)

f()

g <- function(x,a=2) { # g(x,a) = a x^2

return (a * x^2) # return pas nécessaire }

g(5,2)

g(5)

g(5,4)

mafonction <- function(a = 1, b = 2, c) {

resultat <- c(a, b, c)

names(resultat) <- c("a", "b", "c")

return(resultat) }

mafonction(6, 7, 8)

mafonction(c=5)

args(mafonction)

body(mafonction)

Les variables sont d'abord cherchées dans le corps de la fonction puis à l'extérieur du corps de la fonction. La priorité est de considérer d'abord la variable comme locale.

Petits exercices

Ecrire une fonction qui calcule x^2+x+1
Même question mais par défaut, on prend x=0
Ecrire une fonction is.mult3 qui retourne TRUE si x est un nombre entier divisible par 3
Ecrire une fonction prod.scal qui calcule le produit scalaire de deux vecteurs
Ecrire une fonction norme qui calcule la norme d'un vecteur

Les structures de contrôle en R

Expressions conditionnelles

On dispose du si qui s'écrit if (condition) {instructions} et du si alors sinon qui s'écrit if (condition) {instructionsA} else {instructionsB}.

f <- function(x) {

if (x%%2 == 0) {

return("pair") } }

f(2)

f(3)

f <- function(x) {

if (x%%2 == 0) {

return("pair") }

else {

return("impair") } }

f(2)

f(3)

Il existe une version vectorisée du si qui s'applique à toutes les composantes d'un vecteur.

signe <- function(x) {ifelse(x>=0,"positif","négatif")}

x<-rnorm(10)

signe(x)

Exercices avec SI

Ecrire une fonction is.mult3 qui retourne "multiple de 3" si x est un nombre entier divisible par 3 et "non multiple de 3" sinon
Ecrire une fonction qui remplace dans un vecteur les valeurs manquantes par 0.
Ecrire une fonction qui remplace dans un vecteur les valeurs manquantes par la moyenne des valeurs non manquantes.
Ecrire une fonction qui remplace dans un vecteur les valeurs manquantes par le mode (la valeur la plus fréquente) des valeurs non manquantes.

Itérations

On dispose des itérations classiques de type pour et tant que. Le pour s'écrit for (var in seq) {instructions} et le tant que s'écrit while (cond) {instructions}. Il faut noter que lorsqu'on manipule des vecteurs (des matrices, des data frames), il existe très souvent des instructions et fonctions qui permettent de faire le traitement pour tous les éléments sans utiliser de boucle. Ou encore, il existe des fonctions apply, lapply et sapply qui permettent d'appliquer des fonctions à des vecteurs et listes sans utiliser de boucle explicite.

x <- rnorm(10)

for (i in 1:length(x)) {

if (x[i] < 0)

x[i] <- -1 }

Ceci aurait pu être obtenu (et devrait plutôt être écrit) avec x[x < 0] <- -1, ou encore avec x <- ifelse(x < 0, -1, x) !

Exercices avec itération

Vous donnerez pour ces exercices une réponse avec boucle explicite et, quand c'est possible, une réponse utilisant des expressions ou fonctions sur les vecteurs.

Ecrire une fonction qui calcule la norme d'un vecteur en utilisant une boucle. Notez que nous avons précédemment défini cette fonction sans boucle.
Ecrire une fonction qui calcule la somme des n premiers entiers. Vous donnerez au moins trois solutions : une avec boucle explicite, une avec expression et une utilisant vos connaissances mathématiques.
Même question avec la somme des n premiers entiers pairs.
Même question avec la somme des carrés des n premiers entiers.
Ecrire une fonction qui calcule la suite de Syracuse en s'arrêtant dès qu'on arrive sur la valeur 1. Pour quelles valeurs êtes vous capables de vérifier la conjecture de Syracuse ?
Définir une fonction équivalente à la fonction min de R avec une boucle explicite.
Ecrire une fonction qui prend en entrée un vecteur supposé trié (on a utilisé sort) et un nombre et qui sort le vecteur trié avec le nombre inséré au bon endroit.
Ecrire une fonction qui retourne l'indice du premier élément négatif dans un vecteur ou -1 si toutes les composantes sont positives.
Ecrire une fonction pgcd utilisant l'algorithme d'euclide (voir Wikipedia si vous avez oublié).

Structures de données en R

Les structures utiles sont les vecteurs, les matrices, les tableaux de données et les listes. Une présentation des vecteurs et des tableaux de données peut être trouvée dans la fiche d'exercices sur les jeux de données. Les programmes sur les matrices peuvent être facilement adaptés pour les vecteurs et les tabelaux de données.

Les matrices en R -- création

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)

dim(x) <- c(4,3)

nrow(x)

ncol(x)

dim(x)

rownames(x) <- paste("ligne", 1:nrow(x), sep = "")

colnames(x) <- letters[1:ncol(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)

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 <- 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 matrices en R -- Opérations

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 + 2

x + c(2,3,4)

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)

Les matrices en R -- Indexation

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[2,3]

y[2,2:3]

y[2,]

y[-3,-2]

y[1:2,-c(1,3)]

Exercices sur les matrices

Ecrire une fonction qui prend en entrée deux matrices A et B et qui retourne T si on peut calculer le produit AB.
Ecrire une fonction mult.mat qui prend en entrée deux matrices A et B et qui retourne le produit AB quand on peut le calculer et un message d'erreur sinon.
Ecrire une fonction randmat.rect.norm qui prend en entrée un nombre de lignes et un nombre de colonnes et construit une matrice aléatoire générée avec une loi normale.
Ecrire une fonction Gram qui prend en entrée une matrice A et calcule le produit de la transposée de A par A.
Appeler la fonction mat.rect.norm avec 100 lignes et 1000 colonnes pour construire une matrice aléatoire alea. Appeler la fonction Gram sur la matrice alea. Augmenter la taille des matrices pour tester les capacités de R en calcul matriciel.
Ecrire une fonction puiss.mat 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.
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.
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.

Les listes en R -- Introduction

Une liste est une suite ordonnée d'éléments. Les listes sont un moyen de construire des structures de données complexes car les listes en R peuvent contenir des objets de types différents. En voici quelques exemples :

lis <- list(firstname = "jean", lastname = "dupond", age = 35, childAges = c(3, 5, 9))

names(lis) # nom des éléments de la liste

[1] "firstname" "lastname" "age" "childAges"

names(lis) <- c("f", "l", "a", "c") # renommer

lis # afficher la liste lis

[1] "jean"

[1] "dupond"

[1] 35

[1] 3 5 9

lis <- list(c("a", "b"), 5, c(3, 2)) # saisie d'une liste sans nommer les éléments

lis

[[1]]

[1] "a" "b"

[[2]]

[1] 5

[[3]]

[1] 3 2

vect <- c(2, 3)

lis <- list(a = vect, b = c("a"))

vect[1] <- 7 # on modifie le vecteur nommé vect

lis

[1] 2 3 # remarquer que le vecteur dans la liste n'a pas été modifié !

[1] "a"

Les listes en R -- Accéder aux éléments

Il y a différents modes d'accès aux éléments d'une liste : par nom ou par indice :

lis <- list(firstname = "jean", lastname = "dupond", age = 35, childAges = c(3, 5, 9))

lis$lastname

[1] "dupond"

lis[["age"]]

[1] 35

lis[[1]]

[1] "jean"

lis[[3]]

[1] 35

Les listes en R -- Traiter les éléments

On peut parcourir une liste en utilisant une boucle (for ou while) parcourant les indices de 1 à la longueur de la liste (fonction length()). On peut aussi utiliser la structure : for (element in lis) {suite d'instructions traitant element}

On peut ajouter des éléments à une liste avec c (exemple : c(lis,married=TRUE)), convertir en vecteur avec unlist(), convertir un vecteur en liste avec as.list(). Les fonctions lapply() et sapply() permettent d'appliquer une fonction à tous les éléments d'une liste.

lis <- list(a = c(2, 3, 4), b = c(5, 6, 7), c = c(8, 9))

lis

[1] 2 3 4

[1] 5 6 7

[1] 8 9

lapply(lis, mean)

[1] 3

[1] 6

[1] 8.5

sapply(lis, mean)

a b c

3.0 6.0 8.5

Exercices sur les listes

On suppose que la liste contient des nombres réels. Ecrire une fonction qui renvoie les nombres arondis à l'entier le plus proche. Ecrire une fonction qui ajoute 1 à tous les éléments de la liste.
On suppose que la liste contient des chaînes de caractères. Ecrire une fonction qui renvoie la chaîne la plus longue.
On suppose que les éléments de la liste sont des vecteurs. Ecrire une fonction qui sort la liste des sommes des vecteurs, une fonction qui sort le vecteur des sommes des vecteurs, une fonction qui sort la somme des sommes des vecteurs.

Exercices de programmation sur les jeux de données

Suite de Syracuse

Ecrire une fonction qui vous permet de vérifier la conjecture de Syracuse. Votre programme prendra en entrée un entier et sortira un vecteur qui contient les éléments consécutifs de la suite de Syracuse commencant avec cette valeur jusqu'à l'obtention de 1.
Ecrire une fonction qui prend en entrée un entier n et qui calcule la suite de Syracuse pour les entiers de 2 à n et qui renvoie la plus longue des suites générées. Testez. Le temps de calcul reste raisonnable jusque quelques milliers.

Vecteurs

On a récupéré un vecteur qui contient des valeurs numériques mais aussi des valeurs textuelles (exemple : a <- c(3,"abi","abj",5.5)). Regarder le type des éléments du vecteur. On souhaite cependant calculer la moyenne des valeurs numériques apparaissant dans ce vecteur (exemple : on doit trouver 4.25 pour a). Ecrire une fonction qui calcule la moyenne des composantes numériques d'un vecteur (exemple : la fonction appelée avec a doit retourner 4.25).

Matrices et tableaux de données

Ecrire une fonction sansNA.continu qui prend un dataframe dont on suppose toutes les colonnes continues en entrée et qui pour chaque colonne, s'il existe des valeurs manquantes,les remplace par la moyenne de la colonne. On pourra tester avec les jeux de données house :

HOUSE <- read.csv("http://www.grappa.univ-lille3.fr/~gilleron/jeuxdonnees/house.test",header=TRUE)

Ecrire une fonction sansNA.touttype qui prend un dataframe et qui pour chaque colonne, s'il existe des valeurs manquantes, pour une colonne avec des valeurs continues remplace les valeurs manquantes par la moyenne, pour une colonne avec des valeurs discrètes remplace les valeurs manquantes par le mode. On pourra tester avec les jeux de données crx :

CRX <- read.csv("http://www.grappa.univ-lille3.fr/~gilleron/jeuxdonnees/crx.data",header=F,na.strings="?")

Ecrire une fonction sansNAdiscretise qui prend un dataframe et un entier, applique la fonction précédente, puis pour chaque colonne continue la discrétise avec la méthode des quantiles correspondant à l'entier passé en paramètre. On pourra tester avec les jeux de données crx

Un mini PageRank

Introduction

Graphes, matrices et marches aléatoires

Un système de recherche d'information base le classement des pages sur un calcul de score. Un premier élément qui intervient dans le calcul de ce score est une mesure de la proximité entre les mots de la requête et les documents du Web. Cette première mesure est basée sur le contenu des pages. Un deuxième élément est une mesure de l'importance des pages en fonction du nombre de pages qui pointent sur elle et aussi de l'importance de ces pages. C'est ce deuxième élément inventé par Google qui lui a permis de devenir leader incontesté des moteurs de recherche dans les années 2000. Nous allons développer une version simple de l'algorithme PageRank de calcul de l'importance des pages.

On va représenter le Web par un (très très grand) graphe dans lequel chaque noeud représente une page et un arc est présent entre un noeud A et un noeud B si il existe un lien de la page A vers la page B. On suppose une numérotation des liens de 1 à n. Nous allons considérer la matrice A ou l'élément en ligne i et en colonne j vaut 1 si et seulement si il existe un lien du noeud j vers le noeud i (Note : parfois on prend la transposée et il faut changer l'ordre des multiplications matricielles). Nous allons travailler avec des exemples jouet (de petite taille).

1. Soit le graphe G défini par les noeuds 1, 2, 3 et 4 et les arcs (1,2), (1,3), (1,4), (2,3), (3,1) et (4,3). Faites une représentation graphique de G1. Définir la matrice A pour le graphe G.

a <- matrix(c(0,1,1,1,0,0,1,0,1,0,0,0,0,0,1,0),nrow=4)

2. Calculer et interpréter les matrices A au carré, A puissance 3, ...

3. Prendre le vecteur x égal à (1,0,0,0) et calculer x1=Ax, interpréter, calculer x2=Ax1, interpréter, ...

4. On va pondérer par le nombre de liens sortant d'une page. Pour cela, construire une matrice diagonale D où le terme en colonne k est l'inverse de la somme des termes de la colonne k de A.

5. Puis, calculer la matrice T obtenue en multipliant A par D. Vérifier que cette matrice est telle que la somme des colonnes est égale à 1 (matrice probabiliste).

6. Calculer et interpréter les matrices T au carré, T puissance 3, ...

7. Prendre le vecteur x égal à (1,0,0,0) et calculer x1=Tx, interpréter, calculer x2=Tx1, interpréter, ..., jqa prendre des valeurs d'exposant assez grands. Interpréter.

8. Prendre le vecteur x égal à (0.5,0,0.5,0) et calculer x1=Tx, interpréter, calculer x2=Tx1, interpréter, ..., jqa prendre des valeurs d'exposant assez grands. Interpréter. Comparer avec les résultats du 7.

9. Reprendre les questions avec GG construit en ajoutant le noeud 5 et les liens (4,5) et (5,5) au graphe G. Que se passe-t-il ?

10. On ajoute le noeud 6 et le lien (6,6). Quel problème voyez-vous apparaître ?

Introduction de sauts aléatoires

Avec le modèle précédent, on considère la suite définie par x0, x1 = Tx0, ..., xn+1=Txn. Cette suite représente une marche aléatoire dans le graphe : on suit des liens selon des probabilités définies par T. Une telle marche aléatoire est censée modéliser un "surfeur" qui suit les liens sur les pages. Cependant, on peut rencontrer des problèmes de convergence de la suite à cause de puits, de problèmes de connexité. On modifie le modèle en introduisant la possibilité de saut aléatoire. Cela modélise la possibilité pour le "surfeur" de sauter vers une nouvelle page sur le Web (plutôt que de suivre des liens, il décide d'aller sur une page).

On introduit un paramètre réel c et, avec une probabilité c, le "surfeur" choisit une page au hasard parmi les pages du Web et avec une probabilité 1-c, il suit un lien comme précédemment, c'est-à-dire avec une probabilité uniforme égale à l'inverse du nombre de liens sortants du noeud où il se trouve.

1. Construire la matrice carrée U dont tous les coefficients sont égaux à c/n où c est la constante choisie égale à 0.15 et n est le nombre de noeuds du graphe.

2. Construire la matrice TT égale à U+(1-c)T=U+0.85 T

3. Reprendre les calculs de la partie 1 en utilisant TT en lieu et place de TT. Vérifier, en particulier, que nous ne rencontrons plus de problème de convergence (ceci peut être démontré).

Le calcul de score par l'utilisation de marches aléatoires avec sauts aléatoires constitue l'algorithme PageRank dont nous allons implanter une version naïve en R.

algorithme PageRank (naïf) en R

Nous allons programmer une version basique de l'algorithme PageRank utilisant le calcul matriciel. Notre programme prend en entrée une matrice A associée à un graphe où l'élément en ligne i et en colonne j vaut 1 si et seulement si il existe un lien du noeud j vers le noeud i. La sortie sera un score attribué à chacun des noeuds dans un vecteur de score. Pour celà, il suffit de programmer avec des fonctions R les calculs faits précédemment.

1. Ecrire une fonction qui prend en entrée la matrice A et sort la matrice T (matrice probabiliste en colonne : la somme de chacune des colonnes vaut 1).

2. Ecrire une fonction qui prend en entrée la matrice A et un réel c et sort la matrice TT (matrice probabiliste avec saut aléatoire de probabilité c et suivi d'un lien avec probabilité 1-c).

3. Ecrire une fonction qui prend deux vecteurs et calcule la somme des différences au carré entre les composantes. Cette quantité sera appelée distance entre les deux vecteurs.

4. Ecrire une fonction qui prend en entrée une matrice t et un réel e, qui initialise le vecteur x avec une probabilité uniforme pour chacun des noeuds et qui calcule la limite de la suite tx, t^2x, t^3x, ..., soit encore x1 = tx, x2=tx1, x3=tx2, ...en prenant comme critère d'arrêt que la distance entre deux vecteurs successifs doit être plus petite que e.

5. Ecrire une fonction (utiliser les fonctions précédentes : calculer t, calculer tt, calculer la limite de la suite et sortir cette limite) qui prend en entrée une matrice d'adjacence a, un réel c et un réel e, et qui calcule le score pagerank de chacune des pages.

6. Testez chacune des fonctions et la fonction principale sur les graphes G et GG. On prendra c=0 pour retrouver les résultats sans saut aléatoire. Avec saut aléatoire, il est courant de choisir c égal à 0.15

7. testez avec le graphe défini par

A <- matrix(c(1,1,0,0,0,0,0, 0,1,1,1,0,0,0, 0,1,0,0,0,0,0, 0,0,0,1,1,0,0, 0,0,0,0,0,1,0, 0,0,0,1,1,1,0, 0,0,0,0,0,1,1),nrow=7)

et on choisira c = 0.14 et e=0.000001. Discuter le vecteur de score obtenu.

Conclusion sur notre algorithme

Nous avons vu les bases de l'algorithme PageRank. Les difficultés sont de faire passer cet algorithme à l'échelle, c'est à dire de le faire fonctionner sur des graphes de très très grande taille. On utilise pour cela des propriétés des calculs sur les matrices creuses, des optimisations algorithmiques, des méthodes de calcul réparti, ...

Enfin, l'algorithme utilise aussi des particularités du graphe du Web en utilisant la notion de hub et authority où un hub est une page qui pointe sur de nombreuses pages (liste de liens supposés intéressant) et une "authority" est une page référente d'un domaine.

Pour conclure, rappelons que le score de Google est un mélange entre un score de contenu des pages et un score d'importance des pages dans le graphe.

Exercices sur tirages aléatoires dans des jeux de données

Avec en entrée un jeu de données, il est souvent important de pouvoir échantillonner ce fichier. Un data frame df en R a ses éléments indicés en ligne entre 1 et nrow(df). Il suffit donc d'être capable de construire un ensemble d'indices indtrain d'entiers entre 1 et nrow(df). En effet, vous pouvez alors construire avec train <- df[indtrain,] et test <- df[- indtrain,]. Nous allons voir différentes méthodes pour cela et des extensions pour traiter des flux de données.

Ecrire une fonction indices1sur2 qui prend en entrée un data frame df et qui sort un ensemble d'indices en mettant 1 ligne sur 2 dans l'ensemble. Note : utile si vous savez que l'ordre n'influe pas sur les répartitions des différents attributs (variables).
Ecrire une fonction indices1sur3 qui prend en entrée un data frame df et qui sort un ensemble d'indices en mettant 1 ligne sur 3 dans l'ensemble.
Ecrire une fonction indicesalea qui prend en entrée un data frame df et une proportion c entre 0 et 1 et qui renvoie un ensemble d'indices de taille c% du nombre de lignes du data frame. Vous utiliserez avec profit la fonction sample() de R.
Nous allons maintenant utiliser un algorithme de tirage uniforme en ligne, c'est-à-dire on va de 1 à nrow(df) et on décide pour chaque valeur de i si on met i dans l'ensemble d'indices ou pas. Ecrire une fonction indicesaleaenligne qui prend en entrée un data frame et une proportion c centre 0 et 1. Le programme fonctionne de la façon suivante : on calcule d'abord le nombre d'éléments à mettre dans l'ensemble d'indices résultat. Puis, pour chaque valeur de i, on la met dans l'ensemble avec une probabilité (nombre d'élements restant à tirer) divisé par (nombre d'éléments restant à parcourir.
L'algorithme précédent suppose que vous ayez accès au nombre d'éléments total du data frame. Nous allons faire comme si nous ne le connaissions pas. c'est le cas quand vous recevez des flux de données (des commandes sur le Web, des connexions à un site Web, des informations d'un capteur). Ecrire une fonction indicesaleaenflux qui prend en entrée un data frame df et une taille n d'échantillon et qui simule la méthode du réservoir sampling. Pour cela, on remplit l'ensemble d'indices avec les n premiers éléments. Puis pour les éléments suivants, on tire un nombre r avec proba uniforme entre 1 et index de l'élément courant, si le nombre tiré r est inférieur à n, on le met dans l'ensemble d'indices (le réservoir) en place r sinon on passe au suivant. Un exemple : mon ensemble d'indices courant (on a choisi n=10) est (1,2,23,35,5,18,45,8,76,55), je traite l'élément d'indice 91, je tire un nombre entre 1 et 91, le résultat est r= 67, je ne fais rien, je passe à l'indice 92, je tire un nombre entre 1 et 92, le résultat est r=8, je remplace dans ma liste le 8ème élément par 92 et ma liste est maintenant (1,2,23,35,5,18,45,92,76,55), je passe à 93 ...

Exercices de Programmation pour le clustering

Les k-moyennes avec le meilleur k

Un problème difficile est de choisir le nombre de groupes lorsqu'on utilise une méthode comme kmeans pour faire de la classification non supervisée (ou clustering). Vous pouvez parcourir par exemple la page suivante de wikipedia.

Rule of thumb. Ecrire une fonction bonsenskmeans qui prend en entrée un jeu de données x et sort le résultat de kmeans avec le k choisi comme entier inférieurle plus proche de sqrt(n/2) où n est le nombre d'objets dans x.
Elbow method (cf cours). Ecrire une fonction bestkmeans qui prend en entrée un jeu de données x et une valeur entière kmax, qui appelle la fonction monkmeans pour k variant de 2 à kmax avec nstart=30 et qui sort la liste résultat de kmeans correspondant au meilleur clustering en utilisant le critère de décroissance de l'inertie intraclasse. Note : il faut penser à un critère quantitatif, il faut penser à quoi renvoyer quand il n'y a pas de meilleure valeur de k. Tester votre programme et adapter le au besoin en l'appliquant sur les jeux de données iris, jeu1, jeu2, jeu3 et jeu11 du TP sur les k-moyennes.
Validation croisée. Implanter la méthode de validation croisée pour trouver le meilleur k puis pour sortir le meilleur clustering. Note : réfléchir avant d'agir.

Clustering hiérarchique

Vous pourrez tester vos fonctions avec les vecteurs v et w et le data frame iri définis par les commandes R suivantes :

> iri <- iris [,1:4]

> iris.hclust <- hclust (dist (iri))

> plot (iris.hclust)

> iris.hclust.5 <- rect.hclust (iris.hclust, 5)

> v <- iris.hclust.5[[1]]

> w <- iris.hclust.5[[2]]

> v

[1] 103 106 108 110 118 119 123 126 130 131 132 136

> w

[1] 51 52 53 55 57 59 64 66 69 71 73 74 75 76 77 78 79 84 86

[20] 87 88 92 98 101 102 104 105 109 111 112 113 114 115 116 117 120 121 122

[39] 124 125 127 128 129 133 134 135 137 138 139 140 141 142 143 144 145 146 147

[58] 148 149 150

> iris.hclust.5

[[1]]

[1] 103 106 108 110 118 119 123 126 130 131 132 136

[[2]]

[1] 51 52 53 55 57 59 64 66 69 71 73 74 75 76 77 78 79 84 86

[20] 87 88 92 98 101 102 104 105 109 111 112 113 114 115 116 117 120 121 122

[39] 124 125 127 128 129 133 134 135 137 138 139 140 141 142 143 144 145 146 147

[58] 148 149 150

[[3]]

[1] 54 56 58 60 61 62 63 65 67 68 70 72 80 81 82 83 85 89 90

[20] 91 93 94 95 96 97 99 100 107

[[4]]

[1] 1 2 3 4 5 7 8 9 10 13 14 18 23 26 28 29 30 31 35 36 38 39 40 41 42

[26] 43 46 48 50

[[5]]

[1] 6 11 12 15 16 17 19 20 21 22 24 25 27 32 33 34 37 44 45 47 49

Rappeler la signification de la liste de vecteurs produits en sortie des fonctions hclust et rect.hclust
Ecrire une fonction qui calcule les coordonnées des centres des points du jeu de données iri dont les indices sont donnés dans un vecteur. Testez avec v et w.
Ecrire une fonction qui prend en entrée une liste telle que iris.hclust.5 et retourne la liste des centres des groupes.
Ecrire une fonction qui prend en entrée une liste telle que iris.hclust.5 et retourne la liste des inerties des groupes.
Ecrire une fonction qui prend en entrée un jeu de données x et un nombre de groupes k, qui fait le clustering hiérarchique et qui renvoie un vecteur de n éléments, où n est le nombre d'objets de x, qui indique pour chaque indice d'objet le groupe dans lequel il est rangé. Note : il faut utiliser la sortie de rect.hclust.

Exercices utilisés en contrôle

Fonctions et vecteurs

Nous allons écrire, sur un exemple, le recherche du minimum d'une fonction de variable réelle par une descente de gradient. On rappelle que cette méthode consiste à choisir une valeur initiale réelle x0 et un pas de gradient delta, on effectue alors un calcul par récurrence ou le terme d'ordre n+1 est obtenu en faisant xn - delta * g(xn) où xn est le terme d'ordre n et g est la dérivée de la fonction dont on cherche le minimum

Ecrire une fonction qui calcule f(x)= x^3 - 3 x^2 +1
Ecrire une fonction qui calcule g(x) = 3 x^2 - 6 x (g est la dérivée de f)
On considère la fonction f de dérivée g, écrire une fonction qui prend en entrée une valeur initiale réelle x0, un pas de gradient delta et un réel epsilon et qui retourne un vecteur (x0,x1,x2, ..., xn) de termes consécutifs de la descente de gradient avec x0 comme valeur initiale, delta comme pas de gradient et où n est choisi tel que la différence entre xn et le terme précédent est inférieur à epsilon.
Faîtes un graphique de la fonction f. Testez avec différentes valeurs de x0, delta et epsilon et commentez le comportement d'une descente de gradient pour la recherche d'un minimum de la fonction f.

Matrices et tableaux de données

Ecrire une fonction qui prend en entrée un matrice et qui calcule la somme des éléments de la deuxième diagonale d'une matrice carrée (M(n,1) + M(n-1,2) + ... M(1,n))
Ecrire une fonction indices.NA qui prend en entrée un dataframe df et retourne le vecteur des indices des lignes contenant au moins un NA.
Ecrire une fonction sansNA qui prend en entrée un dataframe df et qui retourne un dataframe constitué de toutes les lignes de df où aucun NA n'apparaît. On pourra tester avec un des jeux de données house :

house <- read.csv("http://www.grappa.univ-lille3.fr/~gilleron/jeuxdonnees/house.data",header=TRUE)

Classification non supervisée

Ecrire une fonction qui prend en entrée une liste telle que iris.hclust.5 et retourne la liste des inerties des groupes. Vous pourrez utiliser la fonction listescentres qui calcule la liste des centres des groupes et est définie ci-après. Vous pourrez tester avec le data frame iri.

listescentres <- function(df, liste){ # df est le data frame d'entree, liste une liste de vecteurs d'indices de df

df.centres <- list()

for (k in 1:length(liste)) {df.centres[[k]] <- colMeans(df[liste[[k]],])}

return(df.centres)

}

> iri <- iris [,1:4]

> iris.hclust <- hclust (dist (iri))

> iris.hclust.5 <- rect.hclust (iris.hclust, 5)

> listescentres(iri,iris.hclust.5)

[[1]]

Sepal.Length Sepal.Width Petal.Length Petal.Width

7.475 3.125 6.300 2.050

[[2]]

Sepal.Length Sepal.Width Petal.Length Petal.Width

6.360000 2.931667 5.068333 1.810000

etc