Introduction

En apprentissage non supervisé, on souhaite déterminer dans le jeu de données une structure de groupe basée sur une notion de similarité entre observations. Ainsi, on peut regrouper les données en classes aussi homogènes et séparées que possible. Cela permet ensuite de pouvoir réaliser un apprentissage supervisé sur ces données. Pour cela, lorsqu’on analyse l’évolution de la variance interclasses en fonction du nombre de classes (pour une méthode de classification donnée), on constate qu’elle décroît de façon très nette quand le nombre de classes k augmente, mais à partir d’une certaine valeur de k, on observe une décroissance beaucoup moins marquée. Il existe des procédures statistiques qui permettent de formaliser l’approche selon laquelle la recherche d’un ’coude’ est une indication du nombre optimal de classes k, c’est à dire le point où la perte de variance interclasses devient trop grande, et le Gap Statistic en est une. Dans ce projet, nous verrons donc le principe du Gap Statistic, qui surpasse les autres méthodes d’estimation du nombre optimal de groupes. De surcroît, elle peut être appliquée à toute méthode de classification.

I Explication Mathématique

1) Jeu de données et Clustering

Pour pouvoir bien estimer le nombre de « clusters » avec la méthode du « gap », il faut tout d’abord effectuer une classification non supervisée (k-means, classification ascendante hiérarchique, …). Pour cela, nous partons d’un jeu de données de n observations indépendantes sur p variables. Ensuite, nous devons calculer les distances entre individus pris 2 à 2, à l’aide d’une fonction de distance (par exemple, la distance euclidienne). Finalement, on obtient k groupes distincts \(C_1,...,C_k\)

2) Méthode du gap

L’objectif de cette méthode est de trouver le k optimal, c’est à dire le nombre de groupes approprié pour obtenir un bon clustering. La recherche du k optimal se fait en 3 étapes, pour chaque k allant de 1 à K (K=20 est déjà largement suffisant). Au préalable, on doit donc se munir d’une distance, ici l’euclidienne, pour pouvoir mesurer l’écart entre deux observations i et \(i^{'}\) (\(x_{ij}\) étant la valeur de la variable j pour une observation i) :

\[d(x_i,x_{i^{'}}) = \sum_{j=1}^p(x_{ij} - x_{i^{'}j})^2\]

-1ère étape : Calcul de la somme des distances 2 à 2 pour tous les points du groupe r, r=1,….,k :

\[D_r = \sum_{i,i^{'} \in C_r} d_{ii^{'}}\] -2ème étape : Calcul des \(W_k\) (k allant de 1 à K). Chacun d’eux correspond à la dispersion des points de chaque classe par rapport au centre de cette dernière, c’est à dire la moyenne des sommes de distances \(D_r\) pondérées par la taille des classes \(C_r\) , (r variant de 1 à k).

\[W_k= \sum_{r=1}^k\frac{1}{2n_r}\times D_r\]

-3ème étape : Calcul de la statistique \(Gap_n(k)\) :

Pour ce faire, l’idée est d’effectuer la différence entre l’espérance de \(log(W_k)\) sous une distribution nulle de référence, autrement dit une distribution sans classe évidente, par exemple en faisant une simulation de Monte Carlo selon une loi uniforme, et le \(log(W_k)\), avec pour objectif de trouver le plus grand « gap » (ou écart). Par conséquent, la valeur de k optimale est celle pour laquelle le \(log(W_k)\) se trouve le plus en-dessous par rapport à la courbe de référence, autrement dit on calcule l’écart entre la valeur observée sur les données \(W_k\) et la valeur sous l’hypothèse nulle. Ainsi, le gap statistic est défini comme suit : \[Gap_n(k) = E_{n}^{*}[log(W_k)] - log(W_k)\] avec \(E_{n}^{*}\) l’espérance d’un échantillon de taille n de la distribution de référence, définie par le boostrap qui génère B copies du jeu de données de référence et calcule la moyenne. Le nombre de classes optimal k est celui qui maximise le \(Gap_n(k)\). Cela signifie que la structure des classes est la plus éloignée possible de la distribution uniforme des points. De plus, cette estimation est générale ; en effet, elle ne dépend ni de la méthode de classification ni de la distance d choisies.

II Implémentation informatique

Tout d’abord, nous estimons \(E_{n}^{*}[log(W_k^{*})]\) par une moyenne de B copies \(log(W_k^{*})\), chacune étant calculée à partir d’un échantillon de Monte Carlo \(X_1^{*},....,X_n^{*}\) provenant de la distribution de référence. Ensuite, nous devons évaluer la distribution d’échantillonnage du Gap Statistic. Pour cela, on définit \(sd(k)\) comme l’écart-type des B répliques de Monte Carlo \(log(W_k^{*})\). La prise en compte supplémentaire de l’erreur de simulation dans \(E_{n}^{*}[log(W_k)]\) entraîne la quantité suivante : \[s_k=\sqrt{1+\frac{1}{B}}sd(k)\]

On se sert de cette dernière pour déterminer le nombre de clusters \(\hat{k}\) comme étant le plus petit k tel que l’on ait \(Gap(k) \ge Gap(k+1)\)

On peut désormais se tourner vers l’algorithme lui-même, qui s’effectue en 3 étapes :

-1ère étape : On regroupe les données observées, en faisant varier le nombre total de clusters k de 1 à K, en donnant également les mesures de dispersion \(W_k\)

-2ème étape : Ensuite, on génère des ensembles de données de référence B et on regroupe chacun d’entre eux pour donner une dispersion \(W^{*}_{kb}\),avec b variant de 1 à B. Ainsi, on peut calculer le Gap Statistic estimé, qui est donné par :

\[Gap(k) = \frac{1}{B}\sum_blog(W^{*}_{kb})-log(W_{k})\] -3ème étape : On pose maintenant \(\hat{l}\) tel que : \(\hat{l} = \frac{1}{B}\sum_blog(W^{*}_{kb})\), et on calcule l’écart-type \(sd_k\) défini par:

\[sd_k = [\frac{1}{B}\sum_b[log(W^{*}_{kb})-\hat{l}]^{2}]^{\frac{1}{2}}\] Puis on en déduit \(s_k\),défini comme précédemment. Il ne nous reste plus qu’à déterminer \(\hat{k}\), qui correspond au nombre optimal de clusters.

III Application à différents jeu de données

Première Simulation

Dans la suite, à partir de plusieurs jeux de données nous allons effectuer la méthode du gap statistic sur chacun d’entre eux. Tout d’abord en présentant les données, ensuite en établissant les graphes des W ainsi que ceux des logW et E.logW. Ce qui nous permettra d’avoir le gap c’est à dire la différence entre E.logW et logW et ainsi d’en établir sa courbe. Avec le k optimal obtenu grâce à la méthode, nous effectuerons la méthode des k-means avec ce dernier.

Simulation et graphe des données

Dans cette première simulation , on simule nos données à partir de plusieurs lois normales de moyenne et de variance différentes à partir d’un sample de vecteur de moyennes et de variances.

Graphes des W, logW et E.logW

On obtient ensuite la fonction W, ainsi que la fonction logW et E.logW.

Gap Statistic

En calculant l’écart entre E.logW et logW on obtient la courbe du gap.

K-Means avec k optimal

On va ensuite effectuer l’algorithme des K-means pour notre jeu de données avec le k optimal trouvé (ici k=1) grâce à la méthode du gap statistic.

Deuxieme simulation

Simulation et graphe des données

Ici on simule nos données à partir de 2 lois normales de variance 1 et de moyenne respective 0 et 6.

Graphes des W, logW et E.logW

Gap Statistic

K-Means avec k optimal

On trouve ici k=2 comme k optimal

Troisieme simulation

Simulation et graphe des données

Ici on simule nos données à partir de 4 lois normales de même variance et de moyenne différentes (0,1,2,3).

Graphes des W, logW et E.logW

Gap Statistic

K-Means avec k optimal

On trouve ici k=4 comme k optimal

Quatrieme simulation

Simulation et graphe des données

Ici on prend simplement les données Iris de R comme jeu de données.

Graphes des W, logW et E.logW

Gap Statistique

K-Means avec k optimal

Le k optimal n’est pas forcément 4 ici, mais c’est le début du ‘coude’ ainsi on le choisira dans un souci d’interprétation et de clairvoyance sur notre jeu de données.

Conclusion

Nous avons donc vu dans ce projet différentes applications de la méthode du Gap. En plus de cette méthode de détermination du nombre de clusters optimal, il en existe d’autres telles que celles de Gordon, Cuevas ou encore Milligan et Cooper entre autres. Selon les études de simulation pour cette méthode du Gap, l’estimation de l’écart est bonne pour identifier des groupes bien séparés. Cependant, estimer un nombre de clusters dans un jeu de données reste compliqué quelle que soit la méthode utilisée. En effet lors de nos simulations nous avons rencontré et observé quelques difficultés avec les jeux de données éparses et ceux avec beaucoup de variables. De plus le fait de compiler k fois l’algorithme des K-means peut vite s’avérer couteux avec un grand nombre d’observations.