Détermination automatique du nombre de classes

Bonjour,

Je recherche actuellement un algorithme de classification automatique de données.

J'ai par exemple un tableau à 3 variables avec n individus. Je sais qu'en réalité, ces individus sont représentatifs de 4 classes.

Quel algorithme me conseillez-vous afin de déterminer automatiquement le nombre de classes de ce tableau de données, sans connaitre à priori ce nombre ?

Mon choix s'est pour le moment tourné vers une classification ascendante hiérarchique (CAH) mais cette méthode ne permet toujours pas de déterminer le nombre de classes automatiquement (le choix du nombre de classe se fait à l'oeil grâce à un dendrogramme ou à partir de la variance expliquée).

Merci d'avance pour votre aide et vos conseils.

Bonjour,

tu peux automatiser la détection de la meilleure coupure dans la CAH.
Il existe aussi des mesures spécifiques pour le faire :
http://machaon.karanagai.com/validation_algorithms.html
Si tu ne veux pas utiliser la CAH, tu peux opter pour une méthode de partitionnement (k-means, kohonen maps).
Tu peux également combiner CAH et partitionnement pour les performances.

je dirais aussi que cela dépend de ce qui est sous-tendu par "classe" et "variables"..

les classes ont-elles des critères objectifs, indépendants des valeurs des variables, ou bien sont-elles uniquement déterminées par ce qui est présent comme valeurs ?

Cependant il existe aussi des critères pour déterminer automatiquement le nombre de groupes, notamment avec k-means il existe le critère de Coleman, Harabasz et Davies-Bouldin (applicable à d'autres méthodes comme CAH). Ces critères mesurent à la fois la compacité et la séparation des groupes pour chaque estimation de k (nombre de groupes). Bien évidemment ça a ces limites, mais si les clusters sont relativement séparés sans trop d'overlapping, ça marche très bien.

Citation:

---

Envoyé par Pistolero_JB

Cependant il existe aussi des critères pour déterminer automatiquement le nombre de groupes, notamment avec k-means il existe le critère de Coleman, Harabasz et Davies-Bouldin (applicable à d'autres méthodes comme CAH). Ces critères mesurent à la fois la compacité et la séparation des groupes pour chaque estimation de k (nombre de groupes). Bien évidemment ça a ces limites, mais si les clusters sont relativement séparés sans trop d'overlapping, ça marche très bien.

---

oui mais les solutions peuvent être très différentes...

Si les classes sont pré-déterminées (par exemple un système-expert devant reconnaîttre si telle ou telle mesure tombe dans telle combinaison de contraintes et donc dans telle classe), une simple table de conditions et une simple boucle de test fera l'affaire..

Et sera logiquement plus simple et plus correspondante à la réaltié (car quantifiable et reproductible)

.

C'est vrai si les individus sont représentatifs de 4 classes, le nombre de classes est déjà pré-déterminé, alors pourquoi chercher le nombre de classes ? Il suffit de couper le dendogramme là où le niveau hiérarchique atteint 4 groupes, non ?

absolument ..

Par exemple :

si les 4 classes peuvent être définies par les domaines :

min1 < var1 < max1
min21 < var2 < max21 ou min22 < var2 < max22
min3 < var3 < max3
min41 < var4 < max41 ou min42 < var4 < max42

on peut simplement utiliser des tests bien ordonnés...

La classification n'est pas si simple dans le cas où var est une variable multidimensionnelle, elle peut avoir une ambiguïté entre plusieurs classes. Le recouvrement des classes (lié souvent au bruit) fait qu'il n'est pas possible de comparer var en séparant ses composantes.

C'est pour cela que CAH ou k-means utilisent une notion de similarité pour comparer l'échantillon et la classe, le plus souvent avec la distance Euclidienne. L'appartenance d'un échantillon dans une classe est donc mesurer par la similarité de cette échantillon et la représentation de ce que contient la classe, dans k-means et CAH c'est la moyenne des échantillon déjà trié dans la classe, ou d'un échantillon référent dans le cas d'apprentissage supervisé (expert humain dans la boucle).

C'est pour ça que je posais la question..

Car on trouve ici tout un tas de super-méthodes, mais on peut trouver une solution beaucoup plus simple si on connait les choses..

Pour exemple, j'ai développé il y a maintenant de nombreuses années un système-expert pour la météo.

Il y avait 4000 règles dans l'analyse de base, et la programmation (via Prolog),

En repassant et ré-analysant le problème, je me suis rendu compte qu'en fait ces règles étaient réduites et automatisées, car :

elles faisaient référence à 8 variables comportant chacune environ 3 domaines de valeurs (en dur) possibles.

Fabriquer alors un fichier comportant l'écriture des règles par simplement leur formatage en colonne a permis de formaliser ça en 6 boucles imbriquées.

Et une réduction du temps de calcul d'un facteur 4000 ... :P

Avec un algo (et donc une maintenance) hyper simple , tant du point de vue du code (100 lignes) que du point de vue des règles (éditer les bonnes colonnes ou lignes)


Donc comme je disais ça dépend du problème et du fait de savoir si les classes sont fixes ou à déterminer au vol..

Merci à vous tous pour vos réponses.

En fait, le nombre de 4 classes était donné en exemple.
L'algorithme ne connait pas le nombre de classes à priori, je le teste avec des données représentatives de 4 classes, mais seulement moi le sait, pas l'algorithme.

L'algorithme doit déterminer le nombre d'appareils d'une installation (les classes en question) à partir de données électriques (les 3 variables).

Les bornes des classes ne sont donc pas définies à l'avance, c'est également à l'algorithme de déterminer les limites à partir d'une phase d'apprentissage.

Pour la CAH, j'avais opté pour la méthode de Ward (distance des barycentres pondérée par le nombre d'individus par classe) mais il s'est avéré finalement que la classification n'était pas bonne. En effet, si un appareil a un comportement très différent des autres, seulement 2 classes seront créées : une classe avec cet appareil et une autre classe avec tous les autres appareils. Or, je souhaite une classe par appareil.

Je regarde actuellement la méthode "single linkage" pour voir si elle peut être adaptée à mon problème.

Bonsoir,

le fait d'avoir 4 appareils n'impliquent pas nécessairement que 4 classes sont suffisantes pour classer tes données. Même en prenant un algorithme de clustering sous contraintes, tu pourras obtenir plus de 4 classes : la seule chose que tu puisses imposer c'est que les individus d'une même classe correspondent bien au même appareil.

Sinon, pour le choix de la mesure de similarité, il dépend bien évidemment du type de données que tu manipules (numériques, ordinales, binaires, catégorielles, ...). Il faut aussi penser à normaliser tes données.

Bonjour,

je ne connais pas exactement les algorithmes que tu recherches, toutefois j'utilise très régulièrement Weka et dans la partie clustering tu peux décider de lancer les calculs avec détermination automatique du nombre de classes.
Comme c'est OpenSource, tu as accès au code et dans chaque classe, il est marqué les références des articles sur lesquels le code est basé. Donc tu auras les articles que tu souhaites, en plus c'est ceux utilisés par une librairie qui commence à faire référence dans le domaine.