Les méthodes à estimation de densité

add.png

\bullet Présentation:

Les méthodes à estimation de densité font parties des trois familles d’outils d’analyse non supervisée les plus répandues avec la classification ascendante hiérarchique (CAH) et les méthodes de partitionnement.

Les méthodes à estimation de densité sont particulièrement efficaces dans la construction de clusters/groupes d’observations d’une matrice de données à P \geq 1 variable(s) continue(s), \mathbf{X} = (X ^1, \cdots, X ^P), à partir de la structure même des données sans apport informatif d’une variable auxiliaire.

Le clustering, ou l’action de créer des groupes d’observations, ou clusters dans un argo-anglicisme bien souvent utilisé pour simplifier le propos, s’exécute via un algorithme ascendant en fonction d’un paramètre préalablement fixé et en fonction de la méthode choisie.

Les trois méthodes à estimation de densité les plus connues sont les K-plus proches voisins, la méthode du noyau uniforme et la méthode hybride de Wong.

\bullet Les K-plus proches voisins:

Les K-plus proches voisins ont été élaborés par Anthony M. Wong et Tom Lane en 1983 et se base sur le principe de vote majoritaire en fonction de la proximité aux K voisins les plus proches pour déterminer à quel groupe appartient l’observation que nous cherchons à regrouper.

L’Algorithme nécessite au préalable de fixer le paramètre K dont l’influence sera majeure sur le résultat final. Il n’existe pas de méthodes pour optimiser ce paramètre.

Le choix du regroupement est donc calculé au travers de la formule:

Si d_{X_{i_1},X_{i_2}} \leq max(r_K (X_{i_1}), r_K (X_{i_2})) alors d_{X_{i_1},X_{i_2}} ^* = \frac{1}{2} (\frac{1}{f(X_{i_1})} + \frac{1}{f(X_{i_2})})

Avec,

r_K (X_i) la distance entre l’observation X_i et son Kème voisin le plus proche au sens de la distance euclidienne.

f(X_i) la fonction estimée de densité en X_i ou le rapport entre le nombre d’observations incluses dans la sphère, ou du cercle si P = 2, de rayon r_K (X_i) centrée en X_i et le volume, respectivement l’aire, de la sphère, respectivement du cercle.

Les K-plus proches voisins restent l’un des algorithmes les plus efficaces de la famille des méthodes à estimation de densité, principalement de part sa logique et sa facilité de déroulement. Une version pour analyse supervisée existe également et demeure tout aussi efficace.

add2

\bullet La méthode du noyau uniforme:

La méthode du noyau uniforme se base sur le principe de la création d’une sphère de rayon R (ou d’un cercle si P = 2) centrée en chacune des observations et du nombre d’observations qui y sont incluses pour déterminer à quel groupe appartient l’observation que nous cherchons à regrouper.

L’Algorithme nécessite au préalable de fixer le paramètre R dont l’influence sera majeure sur le résultat final. Il n’existe pas de méthodes pour optimiser ce paramètre.

Le choix du regroupement est donc calculé au travers de la formule:

Si d_{X_{i_1},X_{i_2}} \leq R alors d_{X_{i_1},X_{i_2}} ^* = \frac{1}{2} (\frac{1}{f(X_{i_1})} + \frac{1}{f(X_{i_2})})

, avec f(X_i) la fonction estimée de densité en X_i ou le rapport entre le nombre d’observations incluses dans la sphère, ou du cercle si P = 2, de rayon R centrée en X_i et le volume, respectivement l’aire, de la sphère, respectivement du cercle.

add2

\bullet La méthode hybride de Wong:

La méthode hybride de Wong, développée par Anthony M. Wong et C. Schaack en 1982, se base sur un algorithme en deux temps (d’où le terme d’hydride).

– Dans un premier temps il s’agit de lancer une partition selon la méthode des K-means de la famille des méthodes de partitionnement et de conserver la classification préliminaire ainsi obtenue. La méthode nécessite donc de fixer le paramètre K du nombre de clusters à obtenir.

– A partir de là, le second temps consiste à regrouper les différents clusters préliminaires. La recherche de deux clusters adjacents se fait au travers de la formule,

d ^2 (Cl_{k_1}, Cl_{k_2}) < d ^2 (Cl_{k_1}, Cl_{k_3}) + d ^2 (Cl_{k_2}, Cl_{k_3})

Dés lors la distance à minimiser pour déterminer les deux clusters adjacents à regrouper est,

d (Cl_{k_1}, Cl_{k_2}) ^* = \frac{(\sum_{i \in Cl_{k_1}} ||X_i - \overline{X_{Cl_{k_1}}}|| ^2 + \sum_{i \in Cl_{k_2}} ||X_i - \overline{X_{Cl_{k_2}}}|| ^2 + \frac{n_{k_1} + n_{k_2}}{4} d ^2(Cl_{k_1}, Cl_{k_2})) ^{\frac{\lambda}{2}}}{(n_{k_1} + n_{k_2}) ^{1 + \frac{\lambda}{2}}}

La méthode requiert également de fixer le paramètre de lissage \lambda.

L’Algorithme nécessite au préalable de fixer les paramètre K, \lambda dont les influences seront majeures sur le résultat final. Il n’existe pas de méthodes pour optimiser ces paramètres. La méthode hybride de Wong est considérée comme a éviter lorsque n < 100.

add2

\bullet Exemple:

Soit le jeu de données ci-dessous,

add1

La projection des observations nous donne la carte des individus suivante,

add2.png

Appliquons la méthode des 2-plus proches voisins afin d’établir notre classification.

Dans un premier temps nous calculons la matrice des distances sur \mathbf{X},

D_{\mathbf{X}}= \begin{pmatrix} & obs1 & obs2 & obs3 & obs4 & obs5 & obs6 & obs7 & obs8 & obs9 \\  obs2 & 1.730431 & & & & & & & & \\ obs3 & 7.306695 & 7.851494 & & & & & & & \\ obs4 & 0.991125 & 1.378891 & 8.214224 & & & & & & \\ obs5 & 2.229135 & 2.740852 & 5.190977 & 3.050761 & & & & & \\ obs6 & 10.860636 & 12.570271 & 10.627881 & 11.603027 & 10.847912 & & & & \\ obs7 & 8.594840 & 10.314997 & 9.309023 & 9.311560 & 8.746753 & 2.311944 & & & \\ obs8 & 6.403463 & 8.123649 & 9.287647 & 6.955009 & 7.149683 & 5.065955 & 2.830877 & & \\ obs9 & 5.463783 & 6.765099 & 11.353934 & 5.386607 & 7.317928 & 9.069772 & 6.941757 & 4.141981 & \\ obs10 & 4.224611 & 5.452226 & 10.553691 & 4.075979 & 6.198213 & 9.640028 & 7.401122 & 4.578377 & 1.327253 \\ \end{pmatrix}

Dans un second temps, calculons la distance moyenne avec les deux observations les plus proche de chaque observation prise individuellement,

D_{2-\mbox{proches voisins}}= \begin{pmatrix} Obs & 1er & 2nd & \overline{D} \\ obs1 & obs2 & obs4 & 1.360778 \\ obs2 & obs1 & obs4 & 1.554661 \\ obs3 & obs1 & obs5 & 6.248836 \\ obs4 & obs1 & obs2 & 1.360778 \\ obs5 & obs1 & obs2 & 2.484993 \\ obs6 & obs7 & obs8 & 3.688949 \\ obs7 & obs6 & obs8 & 3.688949 \\ obs8 & obs7 & obs9 & 3.486429 \\ obs9 & obs8 & obs10 & 2.734617 \\ obs10 & obs1 & obs9 & 2.775932 \\ \end{pmatrix}

– La distance minimale sur ces deux tables est tout d’abord celle entre les observations N°1 et N°4, formant ainsi le cluster Cl_{1,4}.

– Vient ensuite, la distance entre l’observation N°9 et l’observation N°10, formant le cluster Cl_{9,10}.

– Le troisième regroupement concerne l’observation N°2 avec le cluster Cl_{1,4} et formant désormais le cluster Cl_{1,2,4}.

– Le prochain regroupement est celui de l’observation N°6 et N°7, formant le cluster Cl_{6,7}. A noter que la distance entre les observations N°1 et N°5 est inférieure à celle citée ci-avant, mais étant donné que l’observation N°1 est déjà regroupée, il convient de prendre en compte sa distance pondérée par les 2 plus proches voisins (seconde table).

– Le cinquième regroupement met l’observation N°5 avec le cluster Cl_{1,2,4}, formant ainsi le cluster Cl_{1,2,4,5}.

– Maintenant c’est au tour de l’observation N°8 d’être regroupé eau cluster Cl_{6,7} même si sa distance avec ses deux plus proches voisins est plus petite, malheureusement elle implique deux clusters distincts Cl_{6,7} et Cl_{9,10} et reste plus proche du premier que du second. Nous obtenons ainsi le cluster Cl_{6,7,8}.

– Enfin, le dernier regroupement est celui de l’observation N°3 au cluster Cl_{1,2,4,5}, formant le cluster Cl_{1,2,3,4,5}.

Nous obtenons ainsi les trois groupes suivants,

add

\bullet Application informatique:

– Procédure SAS: https://support.sas.com/documentation/cdl/en/statug/63033/HTML/default/viewer.htm#cluster_toc.htm

– Package et fonction R: http://finzi.psych.upenn.edu/R/library/spatstat/html/nndist.html

\bullet Bibliographie:

– Data Mining et statistique décisionnelle. L’Intelligence des données de Stéphane Tufféry

– A K-th Nearest Neighbor Clustering Procedure de Anthony M. Wong et Tom Lane

– A Hybrid Clustering Method for Identifying High-Density Clusters de Anthony M. Wong