suivant: Présentation du corpus et
monter: Rehaussement de la classification
précédent: Recherche d'information sur des
Sous-sections
La classification automatique consiste à regrouper divers objets (les individus) en
sous-ensembles d'objets (les classes). Elle peut être :
- supervisée : les classes sont connues à priori,
elles ont en général une sémantique associée
- non-supervisée (en anglais clustering) : les classes sont fondées sur la structure des objets,
la sémantique associée aux classes est plus difficile à déterminer
Dans les deux cas, on a besoin de définir la notion de distance
entre deux classes : le critère d'agrégation.
Soit
un ensemble de documents représentés
chacun par une description
,
et
un ensemble de classes,
la classification supervisée suppose connues deux fonctions.
La première fait correspondre à tout individu
une classe . Elle est définit au moyen de couples donnés comme exemples au système.
La deuxième fait correspondre à tout individu sa description .
La classification supervisée consiste alors à déterminer une procédure de classification :
|
(11) |
qui à partir de la description
de l'élément détermine sa classe avec le plus faible taux d'erreurs.
La performance de la classification dépend notamment de l'efficacité de la description.
De plus, si l'on veut obtenir un système d'apprentissage, la procédure de classification
doit permettre de classer efficacement tout nouvel exemple (pouvoir prédictif).
La classification non-supervisée est utilisée lorsque que l'on possède
des documents qui ne sont pas classés et dont on ne connaît pas de classification.
A la fin du processus de classification non-supervisée, les documents
doivent appartenir à l'une des classes générées par la classification.
On distingue deux catégories de classifications non-supervisées : hiérarchiques
et non-hiérarchiques.
Dans la classification hiérarchique(CH),
les sous-ensembles créés sont emboîtés de manière hiérarchique les
uns dans les autres. On distingue la CH descendante (ou divisive) qui
part de l'ensemble de tous les individus et les fractionne en
un certain nombre de sous-ensembles, chaque sous-ensemble étant alors
fractionné en un certain nombre de sous-ensembles, et ainsi de suite.
Et la CH ascendante (ou agglomérative) qui part des individus seuls que
l'on regroupe en sous-ensembles, qui sont à leur tour regroupés, et ainsi de suite.
Pour déterminer quelles classes on va fusionner, on utilise le critère d'agrégation.
Dans la classification non-hiérarchique,
les individus ne sont pas structurés de manière hiérarchique.
Si chaque individu ne fait partie que d'un sous-ensemble, on parle
de partition. Si chaque individu peut appartenir
à plusieurs groupes, avec la probabilité d'appartenir au groupe i,
alors on parle de recouvrement.
Critère d'agrégation
Le critère d'agrégation permet de comparer les classes deux à deux pour sélectionner
les classes les plus similaires suivant un certain critère.
Les critères les plus classiques sont le plus proche voisin, le diamètre maximum,
la distance moyenne et la distance entre les centres de gravités.
La distance entre la classe et la classe est la plus petite distance entre
un élément de et un élément de .
|
(12) |
La distance entre la classe et la classe est la plus grande distance entre
un élément de et un élément de .
|
(13) |
La distance entre la classe et la classe est la moyenne des distances entre
les éléments de et les éléments de .
|
(14) |
Si est le centre de gravité de la classe et
si est le centre de gravité de la classe alors
la distance entre la classe et la classe est la
distance entre leurs centres de gravités.
Ce critère n'a de sens que si le calcul du centre de gravité
possède lui-même un sens sur les données de l'étude.
Nous présentons ici une méthode permettant d'évaluer
une classification supervisée, et des techniques
classiques pour mesurer et comparer des systèmes de classifications
non-supervisées.
Pour tester la qualité d'une procédure de classification supervisée,
on sépare aléatoirement les éléments classés entre une base de référence(R) et une base de
test(T). Ensuite, on détermine la procédure de classification
à partir des exemples de la base de référence. Puis, on utilise pour retrouver
la classe des éléments de la base de test. Enfin, on estime l'erreur de la procédure de classification.
Pour estimer le taux d'erreur d'une procédure de classification , une méthode simple
est de calculer le nombre d'éléments mal classés sur le nombre d'éléments
à classer :
|
(15) |
où est la classe d'origine de .
Dans les cas de classifications simples, on peut être amené à calculer
l'erreur résultant d'une classification purement aléatoire pour la comparer
avec l'erreur faite par notre procédure afin de vérifier la performance de notre système.
Soit la fréquence (ou probabilité à priori) de la classe dans la base de test,
on appelle erreur du système aléatoire :
|
(16) |
où est le nombre de classes et est le nombre d'éléments de qui sont
dans la classe .
L'erreur apparente est dépendante de l'échantillon considéré. Cependant, plus le nombre
d'éléments de l'échantillon est grand, plus l'erreur mesurée tend vers l'erreur réelle de .
Dans le cas non-supervisé, on peut évaluer la classification par rapport
à certaines de ces caractéristiques.
On distingue d'une part, les caractéristiques numériques : le nombre de classes obtenues,
le nombre d'éléments par classe, le nombre moyen d'éléments par classe, l'écart-type des
classes obtenues, et d'autre part, les caractéristiques sémantiques.
Par exemple, si à un document est associé un ensemble de mots clés, la sémantique associée
à une classe pourra se composer des mots les plus fréquents dans la classe.
Pour évaluer l'homogénéité du nombre d'images par classe, on peut utiliser
la variance :
|
(17) |
où
est le nombre moyen
d'éléments par classe et est le nombre de classes obtenues.
L'écart-type
permet d'exprimer la dispersion
dans la même unité que la moyenne.
suivant: Présentation du corpus et
monter: Rehaussement de la classification
précédent: Recherche d'information sur des
Tollari Sabrina
2003-06-10