Construction d'une base de référence par CAH

Dans un premier temps, il s'agit de construire une classification (non-supervisée) des images à partir de leur indexation textuelle uniquement. Cette classification constituera une base de référence qui permettra de mesurer les erreurs de classification, et par la suite, d'indexer de nouvelles images.

Pour réaliser cette classification, nous avons choisi d'utiliser la méthode classique de classification ascendante hiérarchique(CAH)(Lance et Williams, 1967) :

Algorithme Classification ascendante hiérarchique

Données :

 $E$ : ensemble de $n$ éléments à classer


Tableau $n\times n$ des distances entre éléments

Variables :

$C$ : ensemble des $c$ classes

Début

$C\gets\phi$

Pour chaque individu $e$ de $E$ faire


Créer une classe dans $C$ contenant $e$

fin pour

Tant que $c > 1$ faire

Pour chaque couple $(C_i,C_j)$ de classes de $C$ faire


Calculer la distance entre  $C_i$ et $C_j$


pour le critère d'agrégation considéré

fin pour


Agréger les deux classes $C_p$ et $C_q$ de distance minimale

		 		$c\gets c - 1$

fin tant que

Fin

Pour mettre en oeuvre cette classification, il faut disposer de trois composantes :

(i)

une représentation textuelle des images,

(ii)

une mesure de similarité qui permet de comparer les images,

(iii)

un critère d'agrégation qui permet de fusionner les classes.

Dans le cas standard, l'agrégation s'arrête lorsque tous les individus ont été rassemblés dans la même classe. Dans notre cas, le critère d'arrêt sera d'avoir obtenu un ensemble de classes représentatives du corpus d'images et suffisamment homogènes.

Représentation vectorielle du texte des images

Nous avons choisi de représenter(décrire, indexer) une image $d_i$ par un vecteur $\vec{d_i}$ comme présenté à la section 1.2.2, car c'est une représentation efficace classiquement utilisée. A chaque mot-clé du thésaurus est associée une case du vecteur dans l'ordre d'apparition des mots. Une case est initialisée à 1 si le mot-clé appartient à l'image, à 0 sinon. On a donc $\omega_{j,i} \in \{0,1\}$.

De plus, le thésaurus est structuré hiérarchiquement par une relation de généricité ($\prec$) qui implique que si une image est indexée par un mot-clé $t_j$ et que $t_j \prec t_k$ alors cette image est aussi indexée par le mot-clé $t_k$. Il faut donc, comme dans [MCM02], étendre le vecteur $\vec{d_i}=(\omega_{1,i},\ \omega_{2,i},\ \dots,\ \omega_{j,i},\ \dots,\ \omega_{n,i})$ d'une image de façon à ce que

$$\forall j,k\ \in [1,n],\ \omega_{k,i}=1\ si\ \omega_{j,i}=1\ et\ t_j \prec t_k.$$ (18)

Cette méthode d'extension des vecteurs permet de raprocher des documents qui contiennent des termes `frères' dans le thésaurus.

Exemple _exemple   Considérons le thésaurus et l'indexation de l'image $d_3$ dans la figure 5. Le vecteur $\vec{d_3}$ initial est $(0,1,0,0,1,0)$. Puisque $T\acute{e}l\acute{e}phonie \prec Communication$, on a $\omega_{1,3}=1$, et puisque $Radio \prec M\acute{e}dia \prec Communication$, on a $\omega_{4,3}=1$ et $\omega_{1,3}=1$. Le vecteur étendu de l'image $d_3$ est donc $(1,1,0,1,1,0)$. Les vecteurs étendus des images $d_1$ et $d_2$ sont obtenus de façon similaire.

Figure: Extension d'un vecteur relativement à un thésaurus

Mesure de similarité

En recherche d'information(RI), on utilise souvent le cosinus défini en 1.3.3 entre le vecteur représentant le document $d$ et le vecteur représentant la requête $q$ comme expliqué dans la section 1.2.2. Mais dans notre cas, nous voulons mesurer la similarité entre deux documents $d_k$ et $d_l$. De plus, compte tenu que les poids sont égaux à 0 ou à 1, on peut simplifier la formule du cosinus en :

$$sim(d_k,d_l)=cos(\vec{d_k},\vec{d_l})= \frac{\sum_{j=1}^{n}\... ...{j=1}^{n}\omega_{j,k}}\times\sqrt{\sum_{j=1}^{n}\omega_{j,l}}}$$ (19)

où $\omega_{j,k}$, $\omega_{j,l}$ et $\omega^*_{j,k,l} \in \{0,1\}$, et $\omega^*_{j,k,l}=1$ si les images $d_k$ et $d_l$ sont indexées par $t_j$, sinon $\omega^*_{j,k,l}=0$.

Pour la classification, c'est la distance entre deux images que l'on a besoin de connaître. Nous la calculons par la formule :

$$dist(d_k,d_l)=1-sim(d_k,d_l).$$ (20)

Deux images similaires ont une distance égale à 0 et deux images entièrement dissimilaires ont une distance égale à 1.

Exemple _exemple   Si l'on considère les images $d_1$, $d_2$ et $d_3$ de la figure 5, on a $sim(d_1,d_2)=0.33$, $sim(d_2,d_3)=0.25$ et $sim(d_1,d_3)=0.25$.

Paramétrages du critère d'agrégation et du critère d'arrêt

A chaque étape d'une classification ascendante hiérarchique, on agrège les deux classes $C_p$ et $C_q$ qui ont une distance $D(C_p,C_q)$ minimum. Il existe plusieurs formules pour calculer cette distance $D$ dont les plus classiques sont définies à la section 2.3. Les distances par plus proche voisin, diamètre maximum et distance moyenne ont été expérimentées.

Le tableau 2 présente les meilleurs résultats que nous avons pu obtenir pour chacun des critères. Les classes obtenues avec les critères du plus proche voisin et de la distance moyenne sont sémantiquement homogènes, mais on observe que les classes les plus peuplées sont les plus attractives, et donc il y une grande hétérogénéité numérique (une grande classe qui contient la plupart des images, et beaucoup de petites classes qui contiennent une seule image). Cette grande classe est peut-être due à la configuration de nos données, en effet, certains mots génériques comme `portrait' sont présents dans beaucoup d'images. Le critère du diamètre maximum donne des classes numériquement plus homogènes, mais les images appartenant à une même classe sont sémantiquement trop différentes.

Tableau: Résultat des meilleurs classifications ascendantes hiérarchiques obtenues pour chacun des critères (min : nombre minimal d'images dans une classe, max : nombre maximal d'images dans une classe, moy : nombre moyen d'images par classe, c : nombre de classes obtenues et m : nombre d'images totales). Le critère choisi pour la CAH est le diamètre maximum contraint 0.7 filtré.

Résultats CAH	min	max	moy	écart-type	c	m
Plus proche voisin	1	238	13.3	33.7	50	665
Plus proche voisin	8	238	41.2	65.9	10	412
filtré
Diamètre maximum	1	98	10.2	14.6	65	665
Diamètre maximum	8	98	20.6	20.6	23	474
filtré
Diamètre maximum	1	98	11.7	16.5	57	665
contraint 0.7
Diamètre maximum	8	98	21.5	21.4	24	517
contraint 0.7 filtré

Ces résultats étant peu satisfaisants, un compromis a alors été recherché entre la méthode du plus proche voisin et celle du diamètre maximum pour garder les avantages de l'une et de l'autre. Ce compromis a été d'utiliser le diamètre maximum, mais au lieu de prendre la distance maximale, nous avons pris la plus grande distance inférieure à un certain seuil (la contrainte $CT$).

On appelle diamètre maximum contraint de contrainte $CT \in [0,1]$ la distance entre la classe $C_p$ et la classe $C_q$ :

$$D(C_p,C_q)=\Bigg\{ \begin{array}{ll} 0&si\ \exists d_r, d_s... ...min\{dist(d_r,d_s);d_r\in C_p,\ d_s\in C_q\}&sinon. \end{array}$$ (21)

La première condition permet aux documents ayant exactement les mêmes descriptions de se retrouver dans la même classe. La deuxième élargit la recherche aux documents éloignés, mais pas trop. La dernière est pour les cas extrêmes ou toutes les distances entre deux images seraient plus grandes que la contrainte.

Nous avons déterminé de manière empirique que pour nos données les meilleurs résultats étaient obtenus pour $CT=0,7$. En effet, ils sont meilleurs numériquement, car les classes sont plus homogènes que celles obtenues par le critère du plus proche voisin (écart-type 21.4$<$65.9). Et sémantiquement les images d'une même classe sont plus similaires que par le critère du diamètre maximum.

Pour le critère d'arrêt de la classification, nous avons déterminé de manière empirique que pour obtenir des classes représentatives, il fallait arrêter la classification lorsque la distance d'agrégation obtenue était de 0,55. On a ainsi obtenu 57 classes.

Pour obtenir des classes qui soient suffisamment représentatives, il faut que les classes aient certaines caractéristiques. Une classe doit avoir un nombre d'images $n_{C_k}$ suffisant (fixé à 8) pour contenir assez d'informations visuelles, et les images qu'elle contient ne doivent pas être indexées par les mêmes mot-clés pour avoir suffisamment de diversités textuelles. On exprime cela sous-forme de contraintes dont l'union forme un filtre. Chaque classe $C_k$ doit vérifier :

$$\exists d_r,d_s \in C_k,\ dist(d_r,d_s)\not=0\ et\ n_{C_k}\geq 8, %%et \ sim(i,j)<0.55\$$ (22)

sinon elle est supprimée ainsi que les images qu'elle contient.

Après filtrage, nous obtenons 24 classes sémantiquement pertinentes et dont les images sont suffisamment bien réparties. Nous pouvons donc l'utiliser comme base de référence. Le tableau 3 donne un aperçu des mot-clés de chacune des classes obtenues et la figure 6 montre un exemple d'une classe et de ses images.

Tableau: Nombre ($m_k$) d'images par classe et liste des 3 premiers mot-clés les plus fréquents ($f_1>f_2>f_3$) dans chaque classe

Classe	$m_k$	$T_{f_1}$	$T_{f_2}$	$T_{f_3}$
1	19	Mexique	Politique	Portrait
2	8	Israël	Judaïsme	Patrimoine
3	9	Constructeurs	Transport	Automobile
4	18	Contemporaine	Portrait	Rhône
5	29	Portrait	Armée de l'air	Aéronautique
6	8	Société	Famille	Enfant
7	18	Cameroun	Agriculture	Géographie physique
8	22	Municipalité	Portrait	Les Verts
9	12	Elevages	Santé	Police national
10	9	Portrait	Média	Administrations
11	10	Femme	Ouvriers	Industrie de précision
12	8	Région	Municipalité	Conseil régionaux
13	9	Communication	Télécommunications	Multimédia
14	8	Production	Travail	Alimentation
15	8	Israël	Liban	Urbanisation
16	28	Parti socialiste	Portrait	Municipalité
17	8	Multimédia	Start'up	Ouvriers
18	21	Jeux de société	Humain	Librairies
19	18	Problèmes sociaux	Conflits sociaux	Europe
20	48	Politique	Paris	Bourse
21	71	Bars et Café	Restauration rapide	Etats-Unis
22	12	Infrastructures routières	Innondation	Véhicules
23	98	Portrait	Municipalité	RPR-UMP
24	18	Justice	Portrait	Scandales politiques

Figure 6: Exemple de classe obtenue par notre CAH