Clustering k-means

Introduction :

Présentation de la méthode des k-means :

La méthode des k-means, est une méthode de classification non-supervisée, à l’inverse d’une classification supervisée : cela consiste à repérer des groupes d’individus non-étiquetés initialement tandis que la classification supervisée vise à ranger des individus dans sous des étiquettes prédéfinies. On cherche donc à diviser un groupe de n individus dans k groupes appelés cluster.

En considérant une distance type, il nous est possible d’accomoder regroupements selon des covariances ou des variances respectives. Seulement, pour des raisons pratiques et théorique nous trairerons le sujet avec la distance euclidienne.

Distance de Mahalanobis, interprétation, utilisation :

Considérant un vecteur à plusieurs variables \(x = (x_1,x_2,x_3,...,x_p)^T\) et un ensemble de vecteurs de valeurs moyennes \(c = (c_1,c_2, c_3,...,c_p)^T\) accompagné d’unee matrice de covariance \(\sum\). Alors la distance de Mahalanobis est définie telle que : \[D_M(x) = \sqrt{(x-c)^T \sum^{-1}(x-c)}\].

Il est en réalité remarquable de dire que si la matrice de covariance est la matrice identité, ou algébriquement, les vecteurs sont indépendants\(\perp\) et de même variance \(= 1\), ainsi nous avons l’égalité suivante :\[Id^{-1} = Id\]. Alors naturellement :

\[ D_M(x) = \sqrt{(x-c)^T \sum^{-1} (x-c)} = \sqrt{\left( \begin{matrix} (x_1 - c_1)\\ (x_2 - c_2)\\ . . .\\ (x_p-c_p) \\ \end{matrix} \right) . \left( \begin{matrix} 1 & 0 &...&0\\ 0 & 1 &...&0\\\\ ...& .. .&.. .&...\\ 0 & 0 &...&1\\ \\ \end{matrix} \right) . \left( \begin{matrix} (x_1 - c_1)\\ (x_2 - c_2)\\ . . .\\ (x_p-c_p) \\ \end{matrix} \right)} = \sqrt{\sum_{i=1}^p(x_i - c_i)^2} \]

On retrouve ainsi la distance euclidienne bien connue de nos petits cerveaux !

Cette distance sert à visuliser des nuages de points où l’on connait une éventuelle corrélation entre les données, ceci dit, la partition que l’on pourrait obtenir ne serait dont pas régulière ou uniforme mais pourrait prendre a forme d’ellipse. De nos jours il n’existe pas de démonstration solide vérifiant la théorie de cette approche.

Détermination du nombre de cluster k à choisir

Revenons à nos k groupes à évaluer : comment déterminer de manière judicieuse d’un bon entier k dans un groupe de p individus autre que \(k \in [0,\ p]\) ?

Il est pourtant nécessaire de discuter de ce choix, tant il est grand, il pourrait scinder des groupes importants à observer, de la même manière, si le nombre choisi est trop petit, il se pourrait que l’on remarque tout simplement rien de notable dans notre jeu de données.

Ainsi la méthode la plus usuelle afin de déterminer un nombre “optimal” est en réalité de faire tourner l’algorithme à différents k’s afin d’en minimiser la variance intra-groupe. Cette fonction est en réalité donnée dans l’énoncé :

\[ W(\mu,c) = \int_{\mathbb R^d}\min_{j = 1,...,k}\|x-c_j\|^2d\mu(x) = \mathbb E \min_{j = 1,...,k}\|x-c_j\|^2 \]

Ainsi, nous avons donc codé une première fonction afin de déterminer un nombre de cluster “optimal” selon le jeu de données en minimisant cette variance intra :

##                      V1       V2       V3       V4       V5       V6
## Cluster            2.00    3.000    4.000    5.000   6.0000   7.0000
## Variance Intra 11181.09 4169.739 1147.301 1037.012 940.3458 848.9565
##                     V7       V8
## Cluster          8.000   9.0000
## Variance Intra 769.226 723.7615

Ici, on serait tenté de prendre un \(k=4\) Il est en réalité difficile de déterminer le nombre de K “optimal” pour que la partition mette correctement en évidence les différents clusters que l’on pourrait observer. Ainsi, en séparant initialement les données (ici nous avons choisi un partage de 70/30%), on partitionne sur nos 70% d’entraînement, puis nous évaluons l’erreur quadratique que nous avons entre nos 30% de valeurs test ainsi que leur centroides les plus proches. Nous obtenons ainsi un tableau et un graphe de la forme suivante :

##                     V1       V2       V3       V4       V5       V6
## Cluster           2.00    3.000   4.0000   5.0000   6.0000   7.0000
## Variance Intra 3646.05 1698.572 358.2567 329.7906 298.3391 280.5894
##                      V7       V8
## Cluster          8.0000   9.0000
## Variance Intra 250.7742 259.6873

Application de la méthode des k-means

Initilisation des centres

L’algorithme des k-means nécessite une initialisation des centres. La première idée et de choisir k points de l’échantillon au hasard. Cependant, cette technique n’est pas optimal. En effet, une initialisation non réfléchie peut induire un nombre d’itération élevé de partition et d’actualisation.

La seconde idée est de choisir le premier centre au hasard, puis de prendre le point qui maximise la distance avec le premier centre comme second centre. On calcule ensuite les distances des points aux centres et on prend celui qui maximise la distance à son centre le plus proche comme nouveau centre. On répète ceci jusqu’à avoir k centres. Cette méthode connait des limites. En effet, celà peut nous amener à prendre comme centres des valeurs extrèmes isolées, ce qui a pour conséquence d’avoir besoin de beaucoup d’itérations pour la partition et l’actualisation.

L’initialisation k-means ++ est une amélioration de cette seconde idée. On prend toujours le premier centre au hasard. On calcule la distance de chaque points à ce centre. On crée une probabilité discrète à partir des distances : \(p(x_i) = \frac{D^2(x_i)}{\sum_{i=1}^{n} D^2(x_i)}\) où \(D(x_i)\) est la distance du point \(x_i\) au centre. La valeur de i pour laquelle \(p(x_i)\) est maximum est notre nouveau centre. Pour les centres suivants, on calcule les distances entre \(x_i\) et les centres. Pour chaque \(x_i\) on prend la plus petite distance aux centres. On crée de nouveaux une probabilité discrète : \(p(x_i) = \frac{D^2(x_i)}{\sum_{i=1}^{n} D^2(x_i)}\) où \(D(x_i)\) est la distance entre \(x_i\) et le centre le plus proches de lui. La valeur de i pour laquelle \(p(x_i)\) est maximum est notre nouveau centre. On recommence jusqu’à avoir nos k centres initialisés.

L’intéret de k-means ++ est qu’il permet d’initialisé un centre dans chaque futur cluster. Ansi le nombre d’itérations est grandement diminuée dans la suite du programme.

Algorithme - Diagramme de Voronoï

En théorie, comme dit dans l’introduction, en classification non supervisé, l’objectif et d’étiquettés des groupes d’individus sans indication au préalable. Ainsi les données à classer sont représentées comme telles :

\[ X = \left( \begin{matrix} x_{(1,1)} & x_{(1,2)} \\ x_{(2,1)} & x_{(2,2)} \\ ... & ... \\ x_{(p,1)} & x_{(p,2)} \\ \end{matrix} \right) \]

dans les premiers test nous essayerons de partionner sur le plan \(\mathbb R^2\) ainsi qu’avec la distance euclidienne. Les données et les clusters seront initialisés aléatoirement suivant des lois uniformes, on posera alors une variance commune aux données générées et les moyennes uniformément aléatoire dans le vecteur : \((0,2,6,7,10,15)\)

Désormais nos moyennes posées aléatoirement on partitionne nos données en les affectant au cluster le plus proche selon la distance Euclidienne. La partition ainsi construite est appelée Diagramme de Voronoï. Nous l’accompagnerons de sa distorsion afin de pouvoir observer la décroissance de cette dernière et ainsi comprendre la convergene de la méthode.

## [1] "Distorsion de la première partition :"
## [1] 3965.431

## [1] "Distorsion :"
## [1] 3965.431

## [1] "Distorsion :"
## [1] 1041.027

## [1] "Distorsion :"
## [1] 1037.212

## [1] "Distorsion :"
## [1] 1037.029

## [1] "Distorsion :"
## [1] 1036.927

Application sur un exemple :

Les caracteristiques chimiques du vin sont-elles facteurs de qualité ?

##                      V1       V2      V3       V4       V5       V6
## Cluster           2.000    3.000    4.00    5.000    6.000    7.000
## Variance Intra 3450.359 2382.879 1833.62 1457.713 1278.015 1147.732
##                      V7       V8
## Cluster           8.000   9.0000
## Variance Intra 1059.228 928.5145

##                     V1       V2       V3       V4       V5       V6
## Cluster           2.00    3.000   4.0000   5.0000   6.0000   7.0000
## Variance Intra 1398.05 1006.148 742.9773 663.5921 583.0693 534.6027
##                      V7       V8
## Cluster          8.0000   9.0000
## Variance Intra 491.0674 420.9583

On peut désormais choisir facilement un nombre de cluster que nous souhaiterons mettre en évidence, puis appliquons tout simplement la méthode codée par nos soins. Ici nous prendrons \(k= 5\)

## [1] "Distorsion de la première partition :"
## [1] 6546.606

## [1] "Distorsion finale :"
## [1] 1455.021

Les nombres associés à chaque donnée est leur critère de qualité contenu dans la data initiale. Evidemment si l’on avait pris l’ensemble des caractéristiques chimiques les classes auraient certaienement été bien plus précise quant à la qualité d’un vin. Cependant pour de

Conclusion :

Non néecessairement de lois connus pour observer defs comportements L’algorithme admet une beaucoup trop grosse complexité algorithmique pour les immenses jeux de données

Nous avons vu que la méthode k-means est efficace si l’initialisation est bien pensée. Elle permet de traiter sur des données, sans avoir besoin de connaitre les lois que suivent ces données.

Cependant, comme toute méthode elle a ses limites. En effet le choix du nombre k se discute, il n’y a pas de méthode universelle pour le trouver. Cette méthode et gourmande en calcul et peut être longue suivant la taille des données à utiliser, ce qui peut amener à un coût élevé. De plus, la visualisation classifiée est limitée à \(R^3\).

Mais le plus gros inconvénient est que pour un même jeu de données, en partant de deux initialisations différentes on peut arriver à des clusters différents. Avec k-means ++ on arrive à limiter ce problème mais ici encore cela se discute. En effet, il existe d’autres méthodes d’initialisation telle que k-mean ||.

Enfin, dans ce projet nous nous sommes penchés que sur des données de type quantitatives, et de plus continues. On peut imaginer une application de k-means sur des données qualitatives. Pour cela il faudrait redéfinir la distance grâce au barycentre, i.e le profil moyen. Ainsi on normaliserait les distances par le barycentre, avec par conséquent, des distances propres aux données observées.

Pour conclure, on peut donc voir la méthode k-means comme une méthode de classification non supervisée pouvant s’adapter aux données que l’on rencontre pour tenter une analyse de comportement au sein d’un jeu de données et ainsi pouvoir éventuellement étiquetter les clusters en question.