K-plus proches voisins
Fondamentaux
La notion de voisinage d'un point est assez intuitive. Une définition simple serait : une zone de l'espace qui comprend ce point. C'est une notion centrale en mathématique, particulièrement en analyse lorsqu'on souhaite unifier la notion de finitide (calcul de limites) d'un espace métrique.
Dans les espaces métriques, une autre notion centrale est la notion de distance qui est de fait très imbriquée à la notion de voisinage.
Définissons donc le voisinage d'un point comme étant l'ensemble des autres points qui sont à une certaine distance de lui.
La notion de distance même dépasse largement le cadre de cet exposé. L'avantage de cette définition provisoire nous permet au moins une incursion dans la statistique qui se contente en général des définitions sommaires, non rigoureuses et qui par l'extension des propriétés permet un raisonnement asymptotique : c'est à dire, s'appuyant sur la loi des grands nombres.
Garder à l'esprit les fondements mathématiques de la notion de distance et de la notion de voisinage permet d'être très critique sur les résultats que les algorithmes que nous verrons plus loin donnent.
Définition
les K-nn (K-nearest neighbor) : Méthode d'apprentissage supervisée qui raisonnent avec le principe sous-jacent : “dis moi qui sont tes amis, je te dirais qui tu es”. Elle diffère des méthodes d'apprentissages traditionnelles car aucun modèle n'est induit à partir d'exemple. A chaque fois que l'on veut classer un nouvel individu, on refait tourner l'algorithme et on cherche de nouveaux amis. Exemple : Si l'on veut prédire la probabilité de survenue d'un cancer chez un nouveau patient on procède en deux étapes : 1. On recherche selon les caractéristiques de ce patient les patients qui lui ressemble 2. Si parmi ces “voisins”, il y a eu plus de cancer, alors le patient a une forte probabilité d'avoir le cancer.
Pourquoi j'aime cette méthode
Les limites d'utilisation de cette méthode étaient liées aux architectures et à la capacité des ordinateurs. Le déploiement de cette méthodologie dans un environnement de production se faisait généralement en créant des grosses classes induites par l'apprentissage et ensuite des nouveaux individus étaient affectés en fonction de la distance à ces classes, ce qui évitait de refaire tourner l'algorithme à chaque fois et de reconsidérer les classes.
Aujourd'hui, il n'est plus nécessaire de le faire. Un modèle peut être reconsidéré à chaque mis à jour et on peut recalculer un voisinage en quelques secondes. Cette méthode reviendra donc bientôt, j'en suis persuadé, au goût du jour lorsqu'un problème de classification sera évoqué.
A quoi cela sert?
Les domaines de prédilection sont variés
Un qui a le vent en poupe est la classification des documents indexés dans un moteur de recherche
Plus ancien, dans le geomarketing, lorsqu'on a des points de vente en réseau dispersés sur un territoire donnés, il peut être très efficace lorsqu'on souhaite en ouvrir un d'imaginer à quel autre point de vente il pourrait ressembler pour anticiper son chiffre d'affaire
Si l'on veut construire un moteur de recommandation sur un site internet, les achats des autres visiteurs du site permettent de définir les suggestions à d'autres potentiels acheteurs sous forme de recommandation d'achats
Si l'on veut déterminer quel client d'une enseigne est appétent à une carte de fidélité/un crédit etc, on peut simplement regarder qui dans la base de données à disposition lui ressemble au mieux.
Toutes ces choses dites, on se rend bien compte qu'il s'agit en réalité du bon sens dans le commerce. Une amie n'ayant aucune connaissance statistique, travaillant dans un magasin de vêtements me faisait remarquer que lorsqu'une client entre, elle détermine quel type d'articles serait susceptibles de l'intéresser en regardant simplement la façon dont elle est habillée, le sac à main à son bras, en estimant son âge.
il me semble que c'est ce que cette méthode fait aussi.
Les principales difficultés / Exemples Introductifs
Par définition même, la mise en oeuvre de cette méthodologie se heurte à deux problèmes fondamentaux
- Le choix du voisinage (Combien de voisins retenir?)
- Quelle distance considérée?
Les résultats obtenus par la méthode dépendent de ces deux critères. On peut arriver à des résultats totalement différent selon les méthodes. (Insérer schéma)
Exemple:
Nous sommes en pleine période d'espionnage généralisé alors considérons une site internet qui souhaite alerter la direction des impôts sur les potentiels “fraudeurs à l'impôt”. On dispose des informations suivantes que le site a réussi à collecter :
- l'achat d'un livre : Placer son argent dans paradis fiscaux
- L'âge
- le revenu
- le nombre de cartes de crédits
- Le statut marital
On suppose aussi que nous avons une direction des impôts qui emploie de bons data scientists et qui a donc réussi à partir des adresses Ip des clients du site internet à retrouver lesdits contribuables simplement parce qu'ils ont payés leur impôt à partir de leur ordinateur.
Sur ces clients là, les impôts ont la possibilité de savoir si les individus ont fraudé à l'impôt ou non et se pose la question de construire un modèle d'apprentissage pour détecter les potentiels fraudeurs à l'impôt.
Outre le côté “big brother”, cette approche n'est pas si éloignée de ce que pourrait être la réalité.
getwd()
## [1] "/Users/guibert/Desktop/knn"
setwd("Users/Guibert/Desktop/knn")
## Error: impossible de changer de répertoire de travail
rm(list = ls())
impots <- read.csv(file = "impots.csv", header = T, sep = ";")[, -1]
row.names(impots) = paste0("Contr", seq(1:dim(impots)[1]))
head(impots)
## revenu nbCartes age statutM aFraude
## Contr1 150 3 30 1 1
## Contr2 90 2 40 1 0
## Contr3 100 1 55 0 1
## Contr4 80 2 35 1 0
## Contr5 15 1 20 0 0
## Contr6 250 3 28 0 1
Considérons monsieur Perrier agé de 25 ans, ayant un revenu de 35keur, 1 carte de crédit, Célibataire et l'on se demande s'il faudrerait l'impot :
- On va calculer la distance entre monsieur Perrier et les autres menmbres de la liste
- On va décider que ces voisins sont les gens qui sont le plus proches de lui
- On va regarder parmi ces voisins combien ont fraudé à l'impôt
- On décidera si monsieur Perrier est un potentiel fraudeur
Quel distance choisir? Il n y a pas de réponse définitive. La distance euclidienne est en général la plus utilisée? mais signalons qu'il en existe d'autres (la distance L1, la distance de Manhatan, de Minlowski, maximum, binaire, etc) On peut d'ailleurs soit même construire sa distance, tant qu'elle respecte les propriétés de base d'une distance :
- d(A,A)=0
- d(A,B)=d(B,A)
- d(A,B)<=d(A,C)+d(C,B)
J'aime bien la distance d = |x-y| Elle est simple et traduit bien l'idée que l'on se fait de la distance
Mesurons la distance de Mr Perrier aux autres contribuables
attach(impots)
infoPerrier <- data.frame(revenu = 25, nbCartes = 1, age = 25, sttutM = 0)
maDist <- function(x, y) {
d = sqrt(sum((x - y)^2))
return(d)
}
df.dist = vector()
for (k in 1:nrow(impots)) {
df.dist[k] <- maDist(impots[k, -5], infoPerrier)
}
(impotsDist = cbind(impots, df.dist))
## revenu nbCartes age statutM aFraude df.dist
## Contr1 150 3 30 1 1 125.12
## Contr2 90 2 40 1 0 66.72
## Contr3 100 1 55 0 1 80.78
## Contr4 80 2 35 1 0 55.92
## Contr5 15 1 20 0 0 11.18
## Contr6 250 3 28 0 1 225.03
## Contr7 350 2 65 0 1 327.45
## Contr8 185 1 65 1 0 164.93
## Contr9 100 2 60 1 1 82.78
## Contr10 80 3 35 0 0 55.94
## Contr11 85 4 26 1 1 60.09
## Contr12 35 1 25 1 0 10.05
## Contr13 45 1 23 0 0 20.10
## Contr14 70 1 70 1 1 63.65
## Contr15 65 3 29 1 1 40.26
Si l'on trie le tableau par distance croissante, on s'aperçoit que les plus proches de Mr Perrier sont :
library(plyr)
arrange(impotsDist, df.dist)
## revenu nbCartes age statutM aFraude df.dist
## 1 35 1 25 1 0 10.05
## 2 15 1 20 0 0 11.18
## 3 45 1 23 0 0 20.10
## 4 65 3 29 1 1 40.26
## 5 80 2 35 1 0 55.92
## 6 80 3 35 0 0 55.94
## 7 85 4 26 1 1 60.09
## 8 70 1 70 1 1 63.65
## 9 90 2 40 1 0 66.72
## 10 100 1 55 0 1 80.78
## 11 100 2 60 1 1 82.78
## 12 150 3 30 1 1 125.12
## 13 185 1 65 1 0 164.93
## 14 250 3 28 0 1 225.03
## 15 350 2 65 0 1 327.45
Combien de voisins choisir? On verra par la suite que cette question est moins simple. Mais ici, que l'on choisisse 1,2,3,4,5,6 voisins la majorité des voisins de Mr Perrier ne sont pas des fraudeurs. On peut donc sortir Mr Perrier de la liste des potentiels fraudeurs. Cela se traduit en général par un calcul naif de probabilité. Entendre naïf au sens sans à priori. Si on choisit 5 voisins, combien de voisins parmi les 5 ont froudé : 1/5. Soit 4/5 n'ont pas fraudé. On peut aussi faire des prédictions plus complexes en associant au calcul des probabilité une notion de poids. Par exemple en utilisant la fonction inverse. Si Poids = 1/distance, ce qui se traduirait par… plus on est proche dans le voisinage plus on compte dans la prédiction. Pour aller plus loin, s'il s'agissait non pas de prédire l'appartenance ou non à une classe, mais plutôt d'évaluer le degré d'appétence à la fraude, on pourrait imaginer toute fonction de poids qui donnerait de l'importance à des observations proches. Cette fonction de pondération peut prendre plusieurs formes. Voici deux que j'aime particulièrement:
d = seq(0, 2, 0.1)
par(mfrow = c(2, 1))
plot(d, 1/d, type = "b", main = "Fonction inverse")
plot(d, exp(-d^2), type = "b", main = "Sigmoîde")
par(mfrow = c(1, 1))
Une remarque importante à faire ici est la suivante : Si l'on choisit un très grand nombre de voisins, proche du nombre d'observations, il ne sert plus à rien de calculer les distances pour prédire. En réalité, faire ce choix revient à prédire la classe dont les effectifs sont les plus important dans l'ensemble d'apprentissage. Le choix raisonnable de k est donc un art à part entière. La technique la plus répandue(celle qui donne de meilleurs résultats pratiques) est sans doute la validation croisée.
Et le sur-apprentissage? Il est presqu'inexistant avec cette technique. C'est un autre de ces avantages non négligeable. Le choix de grandes valeurs de k a plutôt pour fonction de lisser le bruit qui peut exister dans l'échantillon d'étude.
Le big data : Les ensembles étant de plus en plus volumineux, le temps de calcul des distances peut être un vrai frein à l'utilisation de cette méthode. Il est recommandé de souvent faire précéder cette technique par une technique de réduction de dimension. Je ne suis pas partisan de ces techniques lorsque les machines ont les capacités de réaliser ces opérations. pour une raison évidente : l'information contenu dans les marges est souvent très utile dans un grand ensemble de données.
Mise en oeuvre avec R
Si on reprend l'exemple de Monsieur Perrier, avec R, la mise en oeuvre d'un classifieur basé sur les plus voisins est simple. On peut directement appliquer le modèle à l'aide de la fonction knn du package FNN.
De la manière la plus simple qui soit en utilisant la validation croisée,
library(FNN)
train = impots[, 1:4]
fraude = as.factor(impots$aFraude)
labels = row.names(impots)
model.knn <- knn(train = train, test = train, k = 3, cl = fraude, prob = TRUE)
model.knn
## [1] 1 0 1 0 0 1 1 1 1 0 0 0 0 1 0
## attr(,"prob")
## [1] 0.6667 1.0000 0.6667 0.6667 1.0000 0.6667 0.6667 0.6667 0.6667 0.6667
## [11] 0.6667 1.0000 0.6667 1.0000 0.6667
## attr(,"nn.index")
## [,1] [,2] [,3]
## [1,] 1 8 3
## [2,] 2 4 10
## [3,] 3 9 2
## [4,] 4 10 11
## [5,] 5 12 13
## [6,] 6 8 1
## [7,] 7 6 8
## [8,] 8 1 6
## [9,] 9 3 2
## [10,] 10 4 11
## [11,] 11 10 4
## [12,] 12 13 5
## [13,] 13 12 15
## [14,] 14 9 3
## [15,] 15 4 10
## attr(,"nn.dist")
## [,1] [,2] [,3]
## [1,] 0 49.538 55.95
## [2,] 0 11.180 11.27
## [3,] 0 5.196 18.08
## [4,] 0 1.414 10.49
## [5,] 0 20.640 30.15
## [6,] 0 74.826 100.02
## [7,] 0 106.630 165.01
## [8,] 0 49.538 74.83
## [9,] 0 5.196 22.36
## [10,] 0 1.414 10.39
## [11,] 0 10.392 10.49
## [12,] 0 10.247 20.64
## [13,] 0 10.247 21.00
## [14,] 0 31.639 33.56
## [15,] 0 16.186 16.19
## Levels: 0 1
Le modèle affecte la valeur 0 ou 1 en fonction du fait que l'individu est potentiellement fraudé ou non et fournit aussi des informations comme les voisins utilisés pour le classement et les distances associées à chaque voisin.
voisins <- attr(model.knn, "nn.index")
labels.voisins = as.data.frame(apply(voisins, 2, function(col) labels[col]))
# Les probabilités
prob <- attr(model.knn, "prob")
prob <- ifelse(model.knn == "1", prob, 1 - prob)
knn.impots <- cbind(impots, labels.voisins, prob)
knn.impots
## revenu nbCartes age statutM aFraude V1 V2 V3 prob
## Contr1 150 3 30 1 1 Contr1 Contr8 Contr3 0.6667
## Contr2 90 2 40 1 0 Contr2 Contr4 Contr10 0.0000
## Contr3 100 1 55 0 1 Contr3 Contr9 Contr2 0.6667
## Contr4 80 2 35 1 0 Contr4 Contr10 Contr11 0.3333
## Contr5 15 1 20 0 0 Contr5 Contr12 Contr13 0.0000
## Contr6 250 3 28 0 1 Contr6 Contr8 Contr1 0.6667
## Contr7 350 2 65 0 1 Contr7 Contr6 Contr8 0.6667
## Contr8 185 1 65 1 0 Contr8 Contr1 Contr6 0.6667
## Contr9 100 2 60 1 1 Contr9 Contr3 Contr2 0.6667
## Contr10 80 3 35 0 0 Contr10 Contr4 Contr11 0.3333
## Contr11 85 4 26 1 1 Contr11 Contr10 Contr4 0.3333
## Contr12 35 1 25 1 0 Contr12 Contr13 Contr5 0.0000
## Contr13 45 1 23 0 0 Contr13 Contr12 Contr15 0.3333
## Contr14 70 1 70 1 1 Contr14 Contr9 Contr3 1.0000
## Contr15 65 3 29 1 1 Contr15 Contr4 Contr10 0.3333
La prédiction devient alors aisée. en regardant les probabilités.
Dans la modélisation ci dessus on a considéré que l'échantillon d'apprentissage et de test était identique. Dans le cas d'un nouvel échantillon, on remplacera l'échantillon de test par l'entrée correspondante. Exemple pour monsieur Perrier tout à l'heure, il suffit de :
train = impots[, 1:4]
test = infoPerrier
fraude = as.factor(impots$aFraude)
labels = row.names(impots)
model.knn <- knn(train = train, test = infoPerrier, k = 3, cl = fraude, prob = TRUE)
probP <- attr(model.knn, "prob")
(probP <- ifelse(model.knn == "1", prob, 1 - prob))
## [1] 0.3333
model.knn
## [1] 0
## attr(,"prob")
## [1] 1
## attr(,"nn.index")
## [,1] [,2] [,3]
## [1,] 12 5 13
## attr(,"nn.dist")
## [,1] [,2] [,3]
## [1,] 10.05 11.18 20.1
## Levels: 0
On retrouve les mêmes résultats comme obtenus manuellement tout à l'heure.
L'exercice que l'on vient de faire, qui consiste à affecter la bonne classe est généralisable. Si l'on souhaite par exemple estimer l'endettement (variable aléatoire réelle positive) et non plus la fraude(binaire 0/1), alors on peut employer les mêmes méthodes : 1 - Rechercher les voisins les plus proches 2 - Estimer que l'endettement pour un nouveau client est la moyenne(pondérée) des endettements de ces voisins.
Ceci est une thématique très utilisée en geomarketing, dès qu'il y a une notion de réseau. Les points de ventes statistiquement proches ont potentiellement des chiffres d'affaire pas très éloignés. reprenons notre exemple et considérons la variable dette :
endet <- impots[, c(-2, -4:-5)]
dette = c(100, 200, 100, 70, 50, 10, 30, 40, 65, 25, 150, 50, 43, 35, 70)
endet$dette <- dette
train = endet[1:10, ]
test = endet[11:15, ]
# Récupérer les voisins statistiques pour chacun des individus dont on veut
# evaluer l'endettement
voisins = FNN::get.knnx(data = train[, -3], query = test[, -3], k = 3)
v = voisins$nn.index
labels = row.names(train)
(labels.voisins = as.data.frame(apply(v, 2, function(col) labels[col])))
## V1 V2 V3
## 1 Contr10 Contr4 Contr2
## 2 Contr5 Contr4 Contr10
## 3 Contr5 Contr4 Contr10
## 4 Contr9 Contr3 Contr2
## 5 Contr4 Contr10 Contr2
test.knn = cbind(test, labels.voisins)
test.knn
## revenu age dette V1 V2 V3
## Contr11 85 26 150 Contr10 Contr4 Contr2
## Contr12 35 25 50 Contr5 Contr4 Contr10
## Contr13 45 23 43 Contr5 Contr4 Contr10
## Contr14 70 70 35 Contr9 Contr3 Contr2
## Contr15 65 29 70 Contr4 Contr10 Contr2
Si l'on considère le Contr11, l'estimation de sa dette se fera par une moyenne de la dette de Contr2, Contr10 et Contr4.
Soit donc :
mean(c(200, 25, 70))
## [1] 98.33
Le package FNN fournit une fonction qui fonctionne sur ce principe :
knn.reg(train = train[, -3], test = test[, -3], y = train$dette, k = 3, algorithm = c("kd_tree"))
## Prediction:
## [1] 98.33 48.33 48.33 121.67 98.33
Je précise -chose importante - qu'il ne s'agit que d'une moyenne et une meilleure approche consiste à pondérer cette moyenne par une fonction de la distance.
Je n'ai pas encore trouvé de moyen agréable de visualiser les knn. Appel à contribution :)
Il existe tout de même un moyen (pas très joli).
d = dist(impots[, -5])
fit <- cmdscale(d, eig = TRUE, k = 2)
x <- fit$points[, 1]
y <- fit$points[, 2]
plot(x, y, xlab = "Coordinate 1", ylab = "Coordinate 2", main = "En utilisant le MDS",
type = "n", )
text(x, y, labels = row.names(impots), cex = 0.7, col = "blue2")
On viot bien que les proximités que l'on retrouve çà et là sont celles que l'on apercevait dans le modèle précédemment.
