Techniques descriptives du data mining

1

Méthode des Centres Mobiles

K-means

Qu’est ce que la classification?

� Regrouper des objets en groupes, ou classes, ou familles, ou segments, ou clusters, de sorte que :

- 2 objets d’un même groupe se ressemblent le + possible- 2 objets de groupes distincts diffèrent le + possible- nombre des groupes est parfois fixé

� Les objets à classer sont - des individus - des variables

� Méthode descriptive :- pas de variable cible privilégiée- décrire de façon simple une réalité complexe en la résumant

� Utilisation en marketing, médecine, sciences humaines…

2

Exemple de classification

3

Les différentes méthodes

• Méthodes de partitionnement

- k-means, k-modes, k-prototypes, k-représentants (k-medoids)

- réseaux de Kohonen

• Méthodes hiérarchiques

- ascendantes basées sur une notion de distance ou de densité

- descendantes

4

Applications du Clustering 1• Marketing :

découper la clientèle en segments dotés chacun d’une offre et d’une

communication spécifique

• Commercial :

répartir l’ensemble des magasins d’une

enseigne en établissements homogènes du point de vue type

de clientèle, taille du magasin…

• Médical : déterminer des groupes de patients susceptibles d’être

soumis à des protocoles thérapeutiques déterminés, chaque groupe

regroupant tous les patients réagissant identiquement

5

• Sociologie : découper la population en groupes homogènes du

point de vue sociodémographique, Style de vie, opinions, attentes…

• Détection des profils de clients de banques :

- clients dont on est la 2ème de banque

- clients à tendance « épargne »

- clients à tendance « crédit consommation »

- clients à tendance « crédit habitat »

6

Applications du Clustering 2

K-means

7

Méthode de partitionnement K-meansAlgorithme K-moyennes

Entrée : k le nombre de groupes cherchéDébut• Choisir aléatoirement les centres des groupesRépéter• Affecter chaque cas au groupe dont il est le plus proche

au son centre (utiliser une distance adéquate)• Recalculer le centre de chaque groupejusqu‘à ce que (stabilisation des centres) ou (nombre

d'itérations =t) ou (stabilisation de l’inertie totale de la population)Fin

8

• Inertie totale Itot : somme de l’inertie intraclasse IA et

de l’inertie interclasse IC

• Inertie intraclasse IA : somme des inerties totales de

chaque classe

• Inertie interclasse Ic : moyenne (pondérée par la somme

des poids de chaque classe) des carrés des distances des

barycentres de chaque classe au barycentre global

9

Méthode de partitionnement K-means

Illustration de K-means

Soit le tableau 1 de sept individus

caractérisés par 2 variables. On

souhaite construire deux groupes

homogènes à partir de ces

individus.

On propose de commencer la

construction à partir des deux

groupes du tableau 2.

Continuer la construction des

groupes en utilisant la distance

euclidienne pour mesurer la

similarité entre individus.

10

Tableau 1

Tableau 2

)||...|||(|),( 22

22

2

11 pp jx

ix

jx

ix

jx

ixjid −++−+−= : Distance euclidienne

entre i et j

Résultat de la première boucle :

11

Illustration de K-means

Résultat de la deuxième boucle :

12

Illustration de K-means

2 groupes stables

• Principaux inconvénients :

- Le choix de k est subjectif dans le cas où le nombre de

classes est inconnu au sein de l’échantillon.

- L'algorithme du k-means ne trouve pas nécessairement la

configuration la plus optimale correspondant à la fonction

objective minimale.

- Les résultats de l'algorithme du k-means sont sensibles à

l'initialisation aléatoires des centres.

13

Méthode de partitionnement K-means

Etude de cas K-meansEtudier la qualité des résultats de K-means dans la constructionde groupes de fleurs selon leurs caractéristiques.

14

Etude de cas K-means

K-means clustering avec R :

Appliquer K-means avec K=3 :

15

Etude de cas K-meansComparer les résultats de K-means avec la classification réelle :

Représentation les groupes en 2 dimensions :

16

Classification non supervisée avec R :

�En utilisant la commande kmeans de la librairie STATS,

construire deux groupes d’entreprises en fonction de

toutes les variables quantitatives disponibles via la

méthode K-means.

�Utiliser la commande table afin de quantifier la qualité

de la classification de la méthode des K-means.

17