PRESENTATION

La détection automatique de clusters est une méthode de

découverte de connaissances non dirigée (ou

apprentissage sans supervision). Cette méthode ne

nécessite aucun apprentissage, et son principe consiste à nécessite aucun apprentissage, et son principe consiste à

regrouper les éléments par similarités successives. La

méthode des K-moyennes

UTILISATION

L'objectif de cette technique est de procéder à uneclassification du type regroupement par similitude. Chaquegroupe est appelé cluster. C'est une technique trèspuissante et son champ d'application est important. Unepuissante et son champ d'application est important. Uneutilisation classique consiste à clusteriser une populationpuis, après étude de chaque cluster, faire une offrecommerciale tout à fait adaptée à la population.

K-moyennesLa méthode des K-moyennes permet de découper une population

en K clusters. Ce nombre K est défini par l'utilisateur. Le principe

de fonctionnement est assez simple :

On détermine un nombre K de clusters. Ensuite on positionne les K

premiers points (appelés graines) au hasard (on utilise en général

les K premiers enregistrements). Chaque enregistrement est

affecté à la graine dont il est le plus proche (en utilisant la

fonction de distance). A la fin de la première affectation, la valeur

moyenne de chaque cluster est calculée et la graine prend cette

nouvelle valeur. Le processus est répété jusqu'à stabilisation des

clusters.

FONCTIONNEMENTLa grande difficulté de cette technique est de trouver une fonction de

mesure de distance performante. Cela ne semble poser aucun problème à priori pour des variables numériques. Pourtant le nombre de possibilités est important : distance Euclidienne, mesure de l'angle, sommation, sommation normalisée, …pondéré, avec changement de repère, d'échelle, centré et réduit … La complexité devient plus repère, d'échelle, centré et réduit … La complexité devient plus importante pour des valeurs énumératives non ordonnées. Si aucune métrique n'est possible, il est courant de prendre une distance égale à 0 si les variables sont identiques et 1 dans le cas contraire. D'autres solutions consistent à prendre le nombre de mots communs dans un champs texte par exemple.

Une bonne fonction de distance donnera de bons résultats.

METTRE EN ŒUVRE LE RBM

Classifier des individus selon leurs âges. Soit une liste

aléatoire d'individus dont les âges sont les suivants :

27 - 51 - 52 - 33 - 45 - 22 - 28 - 44 - 40 - 38 - 20 - 5727 - 51 - 52 - 33 - 45 - 22 - 28 - 44 - 40 - 38 - 20 - 57

METTRE EN ŒUVRE LE RBM

Fixons K=3. Les 3 premières graines prennent les trois

premières valeurs. Calculons la distance (ici distance =

différence / (amplitude maximum) = différence / 37) entre

chaque point et chaque graine, puis affectons au plus près. chaque point et chaque graine, puis affectons au plus près.

Cela nous donne le tableau suivant :

27 51 52 33 45 22 28 44 40 38 20 57

Graine 27 0.00 0.65 0.68 0.16 0.49 0.14 0.03 0.46 0.35 0.30 0.19 0.81

Graine 51 0.65 0.00 0.03 0.49 0.16 0.78 0.62 0.19 0.30 0.35 0.84 0.16

Graine 52 0.68 0.03 0.00 0.51 0.19 0.81 0.65 0.22 0.32 0.38 0.86 0.14

Minimum 0 0 0 0.16 0.16 0.14 0.03 0.19 0.3 0.3 0.19 0.14

Affectation 1 2 3 1 2 1 1 2 2 1 1 3

METTRE EN ŒUVRE LE RBM

Une première affectation nous donne :

� Graine 1 (27) : 27 - 33 - 22 - 28 - 38 - 20

Graine 2 (51) : 51 - 45 - 44 - 40� Graine 2 (51) : 51 - 45 - 44 - 40

� Graine 3 (52) : 52 - 57

METTRE EN ŒUVRE LE RBMPour le calcul des nouveaux centroïdes, prenons la moyenne arithmétique de

chaque cluster, soit 28 pour la graine 1, 45 pour la graine 2 et 54.5 pour la graine

3. Ces valeurs représentent les positions des nouvelles graines. Recommençons

le processus de calcul de distance par rapport à ces nouvelles valeurs. Cela

donne le tableau suivant :

27 51 52 33 45 22 28 44 40 38 20 57

Graine 28 0.03 0.62 0.65 0.14 0.46 0.16 0 0.43 0.32 0.27 0.22 0.78

Graine 45 0.49 0.16 0.19 0.32 0 0.62 0.46 0.03 0.14 0.19 0.68 0.32

Graine 54.5 0.74 0.09 0.07 0.58 0.26 0.88 0.72 0.28 0.39 0.45 0.93 0.07

Minimum 0.03 0.09 0.07 0.14 0 0.16 0 0.03 0.14 0.19 0.22 0.07

Affectation 1 3 3 1 2 1 1 2 2 2 1 3

METTRE EN ŒUVRE LE RBM

L'affectation donne donc la répartition suivante :

Graine 1 (28) : 27 - 33 - 22 - 28 - 20 Moyenne = 26

Graine 2 (45) : 45 - 44 - 40 - 38 Moyenne = 41.75

Graine 3 (54.5) : 51 - 52 - 57 Moyenne = 53.33

En réitérant le processus, nous voyons qu'il ne modifie plus les affectations. Les clusters sont donc finalisés :

Cluster 1: 27 - 33 - 22 - 28 - 20 Jeunes majeurs - Centroïde = 26

Cluster 2: 45 - 44 - 40 - 38 Quadragénaires - Centroïde = 41.75

Cluster 3: 51 - 52 - 57 Quinquagénaires - Centroïde = 53.33

EvaluationLorsque les clusters sont déterminés, par la méthode des K-moyennes, il

faut évaluer la qualité de chaque cluster. L'intérêt de la technique est de regrouper des populations statistiques avec le plus grand degré de similarité. Une solution possible consiste à étudier la variance de la distance de cette population. Un cluster solide sera constitué d'une population significative et d'une variance faible. population significative et d'une variance faible.

D'autres évaluations sont à faire :

Si la population d'un cluster est trop faible, il pourrait être valable de grouper ce cluster avec un autre.

Si un cluster est trop dominant, il sera préférable de scinder la population en deux (dans et hors cluster) et de relancer le processus pour chaque sous groupe.

EvaluationLES POINTS FORTS

Les points forts de cette technique sont :

� Les résultats sont clairs,

� La technique est plutôt facile à mettre en œuvre

� La méthode des K-moyennes n'est pas grosse consommatrice de ressources

� Son application est facile

LES POINTS FAIBLESLES POINTS FAIBLES

Les points faibles de cette technique sont :

� Il est difficile de trouver une bonne fonction de distance

� Certains clusters résultants peuvent être difficiles à expliquer

SYNTHESE

La détection automatique de clusters est une technique de découverte de connaissances non dirigée (ou apprentissage sans supervision). Elle consiste à regrouper les enregistrements en fonction de leurs similitudes. Chaque groupe représente un cluster. C'est une excellente technique pour démarrer un projet d'analyse ou de data mining. Les groupes de similitudes permettront de mieux comprendre les données et d'imaginer comment les utiliser au mieux.

ExerciceClassifier des individus selon leurs âges. Soit une liste

aléatoire d'individus dont les âges sont les suivants :

13- 57- 41- 62- 18- 21- 30- 42- 46- 34- 16- 59