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 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
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 :
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é.
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.
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)
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)
x
for (i in 1:length(x)) {
if (x[i] < 0)
x[i] <- -1 }
x
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) !
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.
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 sont des vecteurs auxquels on ajoute des dimensions avec la fonction dim(). On peut redimensionner une matrice. On accède au nombre de lignes avec nrow() et au nombre de colonnes avec ncol(). On peut nommer les lignes et colonnes. Les éléments d'une matrice sont tous du même type. Ici, nous considérons des matrices numériques.
x <- 1:12
dim(x) <- c(3,4)
x
dim(x) <- c(4,3)
x
nrow(x)
ncol(x)
dim(x)
rownames(x) <- paste("ligne", 1:nrow(x), sep = "")
colnames(x) <- letters[1:ncol(x)]
x
Les matrices peuvent également être créées avec la fonction matrix() en précisant le nombre de lignes, le nombre de colonnes et comment remplir la matrice. On peut ajouter des colonnes avec cbind(), des lignes avec rbind().
y <- matrix(seq(-2,2,length.out=12), nrow=3, ncol=4)
y
z <- matrix(seq(-2,2,length.out=12), nrow=3, ncol=4, byrow=TRUE)
z # comprendre la différence entre y et z
z <- rbind(z,c(4,3,2,1))
z
z <- cbind(z,0)
z # remarque l'extension du 0
On peut également créer des matrices diagonales.
I5 <- diag(1, nrow = 5, ncol = 5)
diag(5:1)
Les opérations et fonctions sur les matrices opèrent comme sur les vecteurs, c'est-à-dire composante par composante.
x <- matrix(1:9, nrow = 3)
x
x+x
x + 2
x + c(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)
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)]
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
$f
[1] "jean"
$l
[1] "dupond"
$a
[1] 35
$c
[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
$a
[1] 2 3 # remarquer que le vecteur dans la liste n'a pas été modifié !
$b
[1] "a"
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
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
$a
[1] 2 3 4
$b
[1] 5 6 7
$c
[1] 8 9
lapply(lis, mean)
$a
[1] 3
$b
[1] 6
$c
[1] 8.5
sapply(lis, mean)
a b c
3.0 6.0 8.5
HOUSE <- read.csv("http://www.grappa.univ-lille3.fr/~gilleron/jeuxdonnees/house.test",header=TRUE)
CRX <- read.csv("http://www.grappa.univ-lille3.fr/~gilleron/jeuxdonnees/crx.data",header=F,na.strings="?")
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.
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.
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.
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.
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.
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
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
house <- read.csv("http://www.grappa.univ-lille3.fr/~gilleron/jeuxdonnees/house.data",header=TRUE)
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