Évaluation de la qualité d'une clusterisation

Marine Campedel

www.tsi.enst.fr/~campedel

29 novembre 2005

Motivations

Mesure de qualité pour

Évaluer le nombre de clusters le plus adapté aux

données (ou à l'algo de clusterisation ?)

Comparer des algorithmes de clusterisation

Évaluer la partition obtenue – qualité de la

description des données obtenue

Qualité d'une clusterisation ?

Classification supervisée : on dispose de

données étiquetées -> comptage des erreurs de

prédiction, courbes ROC, …

Cas non supervisé : les labels sont inconnus

"stabilité" : qualité de la prédiction des étiquettes

par les données (on se sert du résultat de

clusterisation pour se ramener au cas supervisé)

a priori : les données qui se ressemblent doivent

avoir les mêmes labels

Qualité d'une clusterisation ?

Critères internes

à relier au critère optimisé pendant l'opération de

clusterisation

Critères externes

Comparaison avec une clusterisation de

référence

Indices divers reposant généralement sur des

rapports de distance intra/extra clusters

Les indexes actuels

Gèrent parfaitement des configurations

patatoïdes bien séparées mais pas les autres.

Idée 1 : se ramener à l'aide de fonction noyau, à

une configuration patatoïde ;

Idée 2 : proposer un index du même style qui

permette d'analyser les configurations des

données.

Nouvel index : NNI

Taille du voisinage = % de la taille du cluster auquel

appartient une donnée

Résultat = une courbe fonction de ce %

i de voisinagele dans data nb

dans classées i de voisinagele dans data nb),(

donnée une désigne i ),(1

)(

clusterun désignek )(1

k

Xxk

K

k

XkiNNI

kiNNIN

kNNI

kNNIK

NNI

ki

Utilisation de NNI

NNI global

Comparaison de méthodes de clustering (en

particulier sélection de modèles pour kernel

KMeans) ;

Estimation du nombre de clusters (pour kMeans

par exemple).

NNI des clusters et données

Mesure de qualité des clusters ;

Hypothèses sur la configuration des données.

Exemple 1

Exemple 1

Méthode

KernelKMeans

Choix d'un

noyau gaussien

-> test de

diverses valeurs

Exemple 1: résultat du meilleur clustering

Exemple 1: comparaison avec entropie et pureté

Exemple 1 : outliers

Exemple 1 : outliers

Exemple 2 : trouver K

Exemple 2

K? K est.

2 2

3 3

4 4

5 4

6 3

7 3

8 4

9 5

10 4

Conclusion NNI : indexe simple qui ouvre des perspectives intéressantes

sur l'exploitation du résultat d'une clusterisation ou plutôt sur

l'emploi d'une méthode de clusterisation ;

Idée intéressante : courbe et non un seul point

Distance calculée pour le voisinage : laquelle ? (N.B. : dans le

cadre supervisé, peut-on s'en servir pour sélectionner un

espace plus adéquat ?)

Travaux futurs :

exploitation dans les techniques de sélection non

supervisée de caractéristiques (clusterisation des

features).

exploitation de la stabilité