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.