Les K-plus proches voisins pondérés

add2.png

\bullet Présentation:

Les K-plus proches voisins pondérés, publié en 1951 par Evelyn Fix et Joseph L. Hodges et noté KKNN, est un outil permettant de discriminer une variable réponse Y binaire ou polychotomique (C \geq 2 classes) à partir d’une matrice de P variables explicatives continues \mathbf{X} = (X ^1, \cdots, X ^p).

L’Algorithme des K-plus proches voisins pondérés fait partie des outils de discrimination par apprentissage statistique. Il permet notamment d’élaborer des frontières de toutes les formes possibles et offre l’avantage de ne pas nécessiter d’hypothèse à priori sur la distribution de \mathbf{X}.

L’Idée de l’algorithme est de déterminer la classe d’une observation en fonction d’une distance pondérée, par une fonction noyau, entre elle et ses plus proches voisins. Par conséquent, les K plus proches voisins pondérés nécessitent de fixer trois paramètres afin de pouvoir être utilisé.

\bullet Les K plus proches voisins pondérés:

Hypothèse préliminaire: Variables explicatives \mathbf{X} continues, variable réponse Y binaire ou polychotomique.

L’Algorithme des K-plus proches voisins pondérées nécessite de fixer trois paramètres: la fonction noyau f (pondération des distances, que nous pouvons retrouver sous l’appellation kernel dans la littérature), la fonction distance d et le nombre de voisins K. Le choix des paramètres optimaux se fait selon le critère de maximisation des performances.

La fonction noyau f:

Le vote des plus proches voisins est équivalent au mode de distribution de la classe. L’idée étant de pondérer la distance entre l’observation ciblée et celles l’entourant.

Les huit fonctions noyaux suivantes sont les plus utilisées pour l’algorithme des K-plus proches voisins pondérés.

– Rectangulaire: f(d) = \frac{1}{2} \cdot I(\vert d \vert \leq 1)

– Triangulaire: f(d) = (1 - \vert d \vert) \cdot I(\vert d \vert \leq 1)

– Epanechinikov: f(d) = \frac{3}{4} \cdot (1 - d^2) \cdot I(\vert d \vert \leq 1)

– Bi-poids: f(d) = \frac{15}{16} \cdot (1 - d^2) ^2 \cdot I(\vert d \vert \leq 1)

– Tri-poids: f(d) = \frac{35}{32} \cdot (1 - d^2) ^3 \cdot I(\vert d \vert \leq 1)

– Cosinus: f(d) = \frac{\pi}{4} \cdot cos(\frac{\pi}{2} d) \cdot I(\vert d \vert \leq 1)

– Gaussien: f(d) = \frac{1}{\sqrt{2 \pi}} \cdot e ^{-\frac{1}{2} d^2}

– Inverse: f(d) = \frac{1}{\vert d \vert}

Le graphe ci-dessous présente la densité des différents noyaux présentés:

add

Le choix de la distance d:

Les six distances principales utilisées afin de calculer la matrice de distance entre les différents voisins sont:

– La distance euclidienne: d(X_{i_1}, X_{i_2}) = \sqrt{\sum_{j = 1} ^P (X_{i_1} ^j - X_{i_2} ^j) ^2}

– La distance maximale: d(X_{i_1}, X_{i_2}) = max_{j \in [1, P]} | X_{i_1} ^j - X_{i_2} ^j |

– La distance de Manhattan: d(X_{i_1}, X_{i_2}) = \sum_{j = 1} ^P | X_{i_1} ^j - X_{i_2} ^j |

– La distance de Canberra: d(X_{i_1}, X_{i_2}) = \sum_{j = 1} ^P \frac{| X_{i_1} ^j - X_{i_2} ^j |}{| X_{i_1} ^j | + | X_{i_2} ^j |}

– La distance de Minkowski (pour q, paramètre à fixer), qui est entre autre une généralisation de la distance euclidienne: d(X_{i_1}, X_{i_2}) = (\sum_{j = 1} ^P (X_{i_1} ^j - X_{i_2} ^j) ^q) ^{\frac{1}{q}}

L’algorithme KKNN:

Concluons la présentation de la méthodologie des K-plus proches voisins pondérés par l’algorithme d’élaboration de la règle décisionnelle.

– Étape 1: définition du nombre de voisins K, de la fonction distance d et de la fonction noyau f.

– Étape 2: Soit l’échantillon d’apprentissage L de définition  \lbrace (Y_i, X_i), i \in [1,n_L]. Pour l’ensemble des observations i \in [1,n_L] nous appliquons les étapes 3 à 6 suivantes.

– Étape 3: Sélection des (K + 1) plus proche voisins de X_i selon d(X,X_i), \forall i \in [1,n_L].

– Étape 4: Standardisation des K plus proches petites distances via le (K + 1)^{eme} plus proche voisin afin d’obtenir des valeurs comprises entre [0,1]:

D(i) = D(X,X_i) = \frac{d(X,X_i)}{d(X,X_k)} \forall i \in [1,K]

– Étape 5: Transformation des distances normalisées D(i) en pondération w(i) à partir de la fonction noyau:

w(i) = f(D(i))

– Étape 6: La classe de X_i est déterminée via vote majoritaire au sein des K plus proches voisins pour les différentes classes C de Y:

\overbrace{y} = max_{c \ in [1,C]} (\frac{1}{\sharp \lbrace \mbox {Voisins consideres de classe Y = c} \rbrace} \times \sum_{i = 1} ^k w(i) \cdot I(y(i) = c))

– Étape 7: Une fois les étapes 3 à 6 parcourues pour l’ensemble des observations i \in [1,n_L], nous obtenons une carte des secteurs des différentes classes de Y à partir de laquelle nous pouvons prédire la classe d’une nouvelle observation. Le modèle est alors vérifier avec le jeu test.

\bullet Annexe théorique:

Nous rappelons dans cette section de l’article les propriétés qu’une fonction f doit rempir pour être une fonction noyau,

\int_{- \infty} ^{+ \infty} f(x) dx = 1

f(d) \geq 0, \forall d \in R

f(d) \rightarrow max pour d = 0

f(d) \searrow quand d \rightarrow + \infty

\bullet Exemple:

Soit la base de données suivante,

add

Avec « Statut » notre variable réponse et (X ^1, X ^2) nos variables explicatives. Fixons les paramètres suivants pour l’étape 1:

– Nombre de voisins à considérer: K = 3,

– Le kernel sera la fonction noyau inverse,

– La fonction distance d est la distance de Minkowski pour q = 1.

L’étape 2, qui consiste au calcul de la matrice des distances via le paramètre d, nous donne:

\begin{pmatrix} & i_1 & i_2 & i_3 & i_4 & i_5 & i_6 & i_7 & i_8 & \ldots \\ i_2 & 1.9014 & . & . & . & . & . & . & . & \ldots \\ i_3 & 8.5548 & 8.4748 & . & . & . & . & . & . & \ldots \\ i_4 & 4.9442 & 3.0428 & 10.1440 & . & . & . & . & . & \ldots \\ i_5 & 4.7993 & 4.7193 & 6.3519 & 3.7921 & . & . & . & . & \ldots \\ i_6 & 8.9926 & 8.9126 & 0.4378 & 10.2952 & 6.5031 & . & . & . & \ldots \\ i_7 & 6.2970 & 6.3288 & 2.2578 & 9.3716 & 5.5795 & 2.6956 & . & . & \ldots \\ i_8 & 2.7784 & 4.6798 & 5.9764 & 7.7226 & 3.9305 & 6.4142 & 3.7186 & . & \ldots \\ i_9 & 4.2673 & 2.3659 & 9.4671 & 1.5595 & 3.3878 & 9.6183 & 8.6947 & 7.0457 & \ldots \\ i_{10} & 5.2645 & 3.3631 & 10.4643 & 0.7099 & 4.1124 & 10.6155 & 9.6919 & 8.0429 & \ldots \\ i_{11} & 8.5914 & 10.4928 & 4.0040 & 13.5356 & 9.7435 & 4.4418 & 4.1640 & 5.8130 & \ldots \\ i_{12} & 2.6820 & 2.7620 & 11.2368 & 5.6530 & 7.4813 & 11.6746 & 8.9790 & 5.2604 & \ldots \\ i_{13} & 1.5493 & 1.6293 & 10.1041 & 4.5203 & 6.3486 & 10.5419 & 7.8463 & 4.1277 & \ldots \\ i_{14} & 10.1913 & 10.1113 & 8.8043 & 7.2203 & 5.3920 & 8.9555 & 8.0319 & 7.6129 & \ldots \\ i_{15} & 5.9395 & 5.8595 & 10.8505 & 2.9685 & 4.4986 & 11.0017 & 10.0781 & 8.4291 & \ldots \\ i_{16} & 11.6593 & 11.5793 & 3.4025 & 8.6883 & 6.8600 & 3.5537 & 5.3623 & 9.0809 & \ldots \\ i_{17} & 4.9571 & 6.8585 & 5.6527 & 9.9013 & 6.1092 & 6.0905 & 3.3949 & 2.1787 & \ldots \\ i_{18} & 3.0667 & 3.1467 & 11.6215 & 6.0377 & 7.8660 & 12.0593 & 9.3637 & 5.6451 & \ldots \\ i_{19} & 6.1799 & 6.0999 & 10.9295 & 3.2089 & 4.5776 & 11.0807 & 10.1571 & 8.5081 & \ldots \\ i_{20} & 8.4202 & 6.5188 & 13.6200 & 3.4760 & 7.2681 & 13.7712 & 12.8476 & 11.1986 & \ldots \\ \end{pmatrix}

Nous cherchons à classer le premier individu i_1. Nous commençons donc par la recherche des trois voisins les plus proches. En regardant dans la table ci-dessus, nous trouvons qu’il s’agit des observations i_{13}, i_2 et i_{12}. Enfin, le (K+1) ^{ieme} = 4 ^{ieme} plus proche voisin qui servira à la standardisation des distances est i_8.

En étape 3, nous standardisons donc les distances entre i_1 et ces trois observations relevés par rapport à sa distance avec i_8:

D_{i_1} (i_{13}) = \frac{d(X_{i_1}, X_{i_{13}})}{d(X_{i_1}, X_{i_8})} = \frac{1.5493}{2.7784} = 0.5576231

D_{i_1} (i_2) = \frac{d(X_{i_1}, X_{i_2})}{d(X_{i_1}, X_{i_8})} = \frac{1.9014}{2.7784} = 0.6843507

D_{i_1} (i_{12}) = \frac{d(X_{i_1}, X_{i_{12}})}{d(X_{i_1}, X_{i_8})} = \frac{2.6820}{2.7784} = 0.9653038

L’avant dernière étape pour la classification de l’observation i_1 nous amène à la pondération en fonction de la fonction noyau f paramétrée. Nous obtenons alors:

w_{i_1} ( i_{13} ) = \frac{1}{\vert 0.5576231 \vert} = 1.793326

w_{i_1} ( i_2 ) = \frac{1}{\vert 0.6843507 \vert} = 1.461239

w_{i_1} ( i_{12} ) = \frac{1}{\vert 0.9653038 \vert} = 1.035943

Pour l’étape 5, nous allons évaluer les deux classifications possibles et voir pour laquelle nous obtenons le plus de voix.

Nous avons,

V_{Y = 1} = \frac{1}{\sharp \lbrace \mbox{ Voisins consideres de classe Y = 1 } \rbrace} \times \sum_{i = 1} ^k w_{i_1}(i) \cdot I(y(i) = 1)

 = \frac{1}{1} \times (1.793326 \times 0 + 1.461239 \times 1 + 1.035943 \times 0)

 = 1.461239

Ensuite, nous avons:

V_{Y = 2} = \frac{1}{\sharp \lbrace \mbox{ Voisins consideres de classe Y = 2 } \rbrace} \times \sum_{i = 1} ^k w_{i_1}(i) \cdot I(y(i) = 2)

 = \frac{1}{2} \times (1.793326 \times 1 + 1.461239 \times 0 + 1.035943 \times 1)

 = 1.414635

Nous constatons que V_{Y = 2} = 1.414635 < 1.461239 = V_{Y = 1} soit que nous classons i_1 chez les patients malades.

En appliquant ce raisonnement à toutes les observations nous obtenons la matrice de confusion et la carte des individus suivantes:

\begin{tabular}{|l|c|c|} \hline & Predit Y1 & Predit Y2 \\ \hline Y1 & 10 & 0 \\ \hline Y2 & 4 & 6 \\ \hline \end{tabular}

\bullet Application informatique:

Procédure SAS:

%macro WKNN(DATA =, Y =, d = , k = , kernel =);

/* La macro suivante permet d’appliquer l’algorithme des K-plus proches voisins pondérés pour P variables et Y binaire ou polychotomique
Les paramètres nécessaires sont: – DATA la base de données
– Y la variable réponse
– d la distance à appliquer et dont le codage peut être retrouver sur le site de la proc DISTANCE de SAS
– k le nombre de voisins
– kernel le noyau (Rectangulaire, Triangulaire, Epanechinikov, Bipoids, Tripoids, Cosinus, Gaussien, Inverse)
Le programme renvoie la base de données DATA avec ses prédictions selon l’outil WKNN ainsi que la matrice de confusion */

/* Initialisation des options pour épurer la log */
options nonotes spool;

/* Récupération du nombre d’observations */
proc sql noprint;
select count(*) into: n from &DATA.;
quit;

/* Sortie de la liste des variables explicatives */
proc contents data = &DATA. (drop = &Y.) out = biblio noprint;
run;

proc sql noprint;
select distinct(name) into: list_vars separated by  »  » from biblio;
quit;

/* Calcul de la matrice de distance selon la distance d paramétrée */
proc distance data = &DATA. method = &d. out = distX;
var interval(&list_vars.);
run;

/* Création de l’id unique */
data distX;
set distX;
id = _n_;
run;

/* Pour la récupération du statut réel, du nombre de classes et de leur nom respectif */
data Y;
set &DATA.;
Obs = _n_;
keep &Y. Obs;
run;

proc freq data = Y noprint;
tables &Y. / out = list_class;
run;

proc sql noprint;
select distinct(&Y.) into: list_class separated by  »  » from list_class;
select count(*) into: nb_class from list_class;
quit;

%let nmoinsun = %eval(&n.-1);

/* La matrice de distance produite par la proc distance n’est pas symétrique, nous menons les manipulations pour quel le soit */
%do i1 = 1 %to &nmoinsun.;

%let it = %eval(&i1. + 1);

%do i2 = &it. %to &n.;

data _null_;
set distX;
keep Dist&i1.;
if id = &i2.;
call symput(« valeur »,Dist&i1.);
run;

data distX;
set distX;
if id = &i1. then Dist&i2. = &valeur.;
run;

%end;

%end;

%let voisins = %eval(&k. + 1);

/* Détermination pour chaque observation de la classe selon l’outil WKNN */
%do i = 1 %to &n.;

data plusprochesvoisins;
run;

/* Récupération des distances entre l’observation i et les autres */
data distXencours;
set distX;
keep Dist&i. id;
if id ne &i.;
run;

/* Recherche des k plus proches voisins selon d */
%do v = 1 %to &voisins.;

proc sql noprint;
create table min as select min(Dist&i.) as min, Dist&i., id from DistXencours;
quit;

data min;
set min;
if Dist&i. = min;
run;

data min;
set min;
if _n_ = 1;
call symput(« min »,min);
call symput(« obs »,id);
run;

/* Nous complétons la table de synthèse des k plus proches voisins ainsi que du k+1 afin de pouvoir standardiser les calculs */
data plusprochesvoisins;
set plusprochesvoisins end = eof;
output;
if eof then do;
Obs = &obs.;
Dist = &min.;
ordre = &v.;
output;
end;
run;

data DistXencours;
set DistXencours;
if id ne &obs.;
run;

%end;

/* Calcul des pondérations selon le kernel paramétré */
data _null_;
set plusprochesvoisins;
if ordre = &voisins.;
call symput(« Denom »,Dist);
run;

data plusprochesvoisins;
set plusprochesvoisins;
if Obs ne .;
Std = Dist/&Denom.;
%if &kernel. = Rectangulaire %then %do;
if Dist < 1 or Dist = 1 then W = 0.5; if Dist > 1 then W = 0;
%end;
%if &kernel. = Triangulaire %then %do;
if Dist < 1 or Dist = 1 then W = 1 – abs(Dist); if Dist > 1 then W = 0;
%end;
%if &kernel. = Epanechinikov %then %do;
if Dist < 1 or Dist = 1 then W = 0.75 * (1 – Dist **2); if Dist > 1 then W = 0;
%end;
%if &kernel. = Bipoids %then %do;
if Dist < 1 or Dist = 1 then W = (15/16) * (1 – Dist **2) **2; if Dist > 1 then W = 0;
%end;
%if &kernel. = Tripoids %then %do;
if Dist < 1 or Dist = 1 then W = (35/32) * (1 – Dist **2) **3; if Dist > 1 then W = 0;
%end;
%if &kernel. = Cosinus %then %do;
if Dist < 1 or Dist = 1 then W = (constant(« pi »)/4) * cos(Dist*constant(« pi »)/2); if Dist > 1 then W = 0;
%end;
%if &kernel. = Gaussien %then %do;
W = (1/sqrt(2*constant(« pi »))) * exp(-0.5 * Dist **2);
%end;
%if &kernel. = Inverse %then %do;
W = 1/abs(Std);
%end;
run;

proc sort data = plusprochesvoisins;
by Obs;
run;

/* Fusion entre les calculs fait et le statut réel pour le vote majoritaire */
data plusprochesvoisins;
merge plusprochesvoisins Y;
by Obs;
if Dist ne .;
run;

proc freq data = plusprochesvoisins noprint;
tables &Y. / nopercent out = eff_Y;
run;

/* Calcul du score pour chaque classe en fonction des k voisins retenus */
%do c = 1 %to &nb_class.;

data eff_Yc;
set eff_Y;
if &Y. = « %scan(&list_class.,&c.) »;
call symput(« eff_c »,count);
run;

proc sql noprint;
select count(*) into: verif from eff_Yc;
quit;

%if &verif. = 0 %then %do;
%let eff_c = 0;
%end;

data calc_vote;
set plusprochesvoisins;
if &Y. ne « %scan(&list_class.,&c.) » then W = 0;
run;

proc sql noprint;
select sum(W) into: somme from calc_vote;
quit;

data plusprochesvoisins;
set plusprochesvoisins;
%if &eff_c. > 0 %then %do;
V_&c. = (1/&eff_c.) * &somme.;
%end;
%if &eff_c. = 0 %then %do;
V_&c. = 0;
%end;
run;

%end;

/* Choix de la classe de prédiction en fonction du vote */
proc contents data = plusprochesvoisins out = list_V noprint;
run;

data list_V;
set list_V;
if index(name, »V_ ») > 0;
run;

proc sql noprint;
select distinct(name) into: list_vote separated by « , » from list_V;
select distinct(name) into: list_vote2 separated by  »  » from list_V;
quit;

data plusprochesvoisins;
set plusprochesvoisins;
maxV = max(&list_vote.);
call symput(« max »,maxV);
run;

proc transpose data = plusprochesvoisins out = prediction;
var &list_vote2.;
run;

data prediction;
set prediction;
max = &max.;
compar_i = put(COL1,10.);
compar_v = put(max,10.);
if compar_i = compar_v then pred = _n_;
keep _name_ compar_i compar_v pred;
call symput(« pred »,pred);
run;

data _null_;
set prediction;
if pred ne .;
call symput(« pred »,pred);
run;

data &DATA.;
set &DATA.;
if _n_ = &i. then Pred_WKNN = &Pred.;
run;

%put Observation &i. traitée;

%end;

/* Sortie de la matrice de confusion dans la log*/
proc freq data = &DATA.;
tables &Y. * Pred_WKNN;
run;

/* Suppression des tables temporaires et inutiles */
proc datasets lib = work nolist;
delete distX biblio Y list_class plusprochesvoisins distXencours min eff_Y eff_Yc calc_vote list_V prediction;
run;

/* Reset des options d’affichage de la log */
options notes nospool;

%mend;

Package et fonction R: http://www.inside-r.org/packages/cran/kknn/docs/kknn

\bullet Bibliographie:

– An important contribution to nonparametric discriminant analysis and density estimation de Evelyn Fix et Joseph L. Hodges

– Algorithme des K-plus proches voisins pondérés et application en diagnostic de Eve Mathieu-Dupas

– The elements of statistical learning de Trevor Hastie, Robert Tibshirani et Jerome Friedman

– Theory of reproducing Kernel de N. Aronszajn