next up previous
suivant: Présentation du corpus et monter: Rehaussement de la classification précédent: Recherche d'information sur des

Sous-sections

Classification

La classification automatique consiste à regrouper divers objets (les individus) en sous-ensembles d'objets (les classes). Elle peut être :

Dans les deux cas, on a besoin de définir la notion de distance entre deux classes : le critère d'agrégation.

Classification supervisée

Soit $D=\{d_1, d_2, \dots, d_i ,\dots, d_m\}$ un ensemble de documents représentés chacun par une description $\vec{d_1}, \vec{d_2}, \dots, \vec{d_m}$, et $C=\{C_1, C_2, \dots, C_k, \dots, C_c\}$ un ensemble de classes, la classification supervisée suppose connues deux fonctions. La première fait correspondre à tout individu $d_i$ une classe $C_k$. Elle est définit au moyen de couples $(d_i,C_k)$ donnés comme exemples au système. La deuxième fait correspondre à tout individu $d_i$ sa description $\vec{d_i}$. La classification supervisée consiste alors à déterminer une procédure de classification :
\begin{displaymath}
C^f:\vec{d_i} \to C_k
\end{displaymath} (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).

Classification non-supervisée

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é $p_i$ 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.

Plus proche voisin

La distance entre la classe $C_p$ et la classe $C_q$ est la plus petite distance entre un élément de $C_p$ et un élément de $C_q$.
\begin{displaymath}
D(C_p,C_q)=\min\{ dist(i,j) ; i\in C_p, j\in C_q\}
\end{displaymath} (12)

Diamètre maximum

La distance entre la classe $C_p$ et la classe $C_q$ est la plus grande distance entre un élément de $C_p$ et un élément de $C_q$.
\begin{displaymath}
D(C_p,C_q)=\max\{ dist(i,j) ; i\in C_p, j\in C_q\}
\end{displaymath} (13)

Distance moyenne

La distance entre la classe $C_p$ et la classe $C_q$ est la moyenne des distances entre les éléments de $C_p$ et les éléments de $C_q$.
\begin{displaymath}
D(C_p,C_q)=\frac{ \sum_{i,j}\{dist(i,j) ; i\in C_p, j\in C_q\}}{ Card(C_p) \times Card(C_q)}
\end{displaymath} (14)

Distance entre les centres de gravité

Si $G_p$ est le centre de gravité de la classe $C_p$ et si $G_q$ est le centre de gravité de la classe $C_q$ alors la distance entre la classe $C_p$ et la classe $C_q$ est la distance entre leurs centres de gravités.

\begin{displaymath}D(C_p,C_q)=dist(G_p,G_q)\end{displaymath}

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.

Evaluation d'un système de classification

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.

Corpus de test (cas supervisé)

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 $C^f$ à partir des exemples de la base de référence. Puis, on utilise $C^f$ 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 $TE$ d'une procédure de classification $C^f$, une méthode simple est de calculer le nombre d'éléments mal classés sur le nombre d'éléments à classer :

\begin{displaymath}
TE(C^f)=\frac{1}{card(T)}\sum_{t=1}^{card(T)}(C^f(\vec{d_t})\not=C_{d_t})
\end{displaymath} (15)

$C_{d_t}$ est la classe d'origine de $d_t$.

Dans les cas de classifications simples, on peut être amené à calculer l'erreur résultant d'une classification purement aléatoire $C^a$ pour la comparer avec l'erreur faite par notre procédure $C^f$ afin de vérifier la performance de notre système.

Soit $P_k$ la fréquence (ou probabilité à priori) de la classe $k$ dans la base de test, on appelle erreur $TE_a$ du système aléatoire :

\begin{displaymath}
TE_a=1-\sum_{k=1}^{c}(P_k)^2=1-\sum_{k=1}^{c}\left(\frac{card(C_k\vert T)}{card(T)}\right)^2
\end{displaymath} (16)

$c$ est le nombre de classes et $card(C_k\vert T)$ est le nombre d'éléments de $T$ qui sont dans la classe $C_k$.

L'erreur apparente $TE(C^f)$ 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 $C^f$.

Cas non-supervisé

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 :

\begin{displaymath}
V=\sigma^2=\frac{1}{c}\sum_{k=1}^{c}(card(C_k)-moy)^2
\end{displaymath} (17)

$moy=\frac{1}{c}\sum_{k=1}^{c}card(C_k)$ est le nombre moyen d'éléments par classe et $c$ est le nombre de classes obtenues. L'écart-type $\sigma=\sqrt{V}$ permet d'exprimer la dispersion dans la même unité que la moyenne.


next up previous
suivant: Présentation du corpus et monter: Rehaussement de la classification précédent: Recherche d'information sur des
Tollari Sabrina 2003-06-10