Agrégats de mots sémantiquement cohérents issus d'un grand graphe de terrain

3.3.3 Les étapes de la méthode HLS

La méthode HLS comprend 2 étapes : L'analyse

Une première phase d'analyse consiste à regrouper les agrégats tant que des regroupements sont possibles. La phase d'analyse se compose de trois parties : fusion, extension et condensation

- la fusion recherche les agrégats de taille minimale ;

- l'extension consiste à inclure un objet voisin dans l'agrégat courant et ce, tant qu'il existe un objet voisin à insérer (l'opération d'extension utilise un opérateur d'extension qui va étendre l'agrégat courant « A » aux objets voisins ; l'opérateur d'extension est défini comme une condition et doit être adapté en fonction des éléments à agréger) ;

- la condensation place les objets regroupés dans l'agrégat en cours de constitution et met à jour le plan d'assemblage, qui est présenté dans la section suivante.

L'assemblage

La phase d'assemblage exécute un plan d'assemblage où chaque agrégat est considéré comme un objet de départ. Nous n'utilisons pas cette phase dans nos travaux afin de mieux mesurer la qualité de la phase d'extension. Les travaux de Jermann C. présentent plusieurs mises en oeuvre possibles [Jermann&al-20041 [Jermann-20021 de la phase d'assemblage. L'Enrichissement par Gravité présenté en paragraphe 3.20, est une instanciation possible de cette phase.

3.3.4 Implantation et adaptation de la méthode HLS

Définissons S un G.C.S.P. tel que S=(MC,R) où MC est l'ensemble noeuds et R l'ensemble des relations et où A=(MCA, RA). A est un agrégat dans le G.C.S.P., le voisinage de A est le sous ensemble MC' des objets géométriques de S qui sont liés par des relations à des objets de A par l'opérateur d'extension O.

Dans notre instanciation, nous définissons l'agrégat minimum comme une clique. La phase de fusion recherche donc ces objets.

La phase d'extension est déterminée par la connaissance du voisinage de l'agrégat de départ et par la capacité à étendre cet agrégat. L'opération d'extension utilise un opérateur

3.3 : Méthode 2 : Rigidification Simple 95

Chapitre 3. Les méthodes d'agrégations proposées

d'extension O obéissant à la règle suivante : le graphe de l'agrégat doit toujours rester bi-connexe pendant les opérations d'extension. La figure 3.2 donne un exemple du déroulement de la phase d'extension.

^E

^D

^F

^D

^F

K

^L

C

D

^E

E

^F

^K

^C

^H

^K

^A

^B

^I

L

^A

^B

^I

^L

Figure 3.2. Illustration du déroulement de l'algorithme Fusion/Extension dans notre implantation de H.L.S.

^A

^B

^E

D'autres critères interviennent dans l'opération d'extension, tels que le poids des mots et des relations.

^C

^H

^C

^H

K

^A

^B

^I

^L

^A

^B

^I

Nous nommons poids, le nombre de recherches liées à un objet. Cet objet est soit un

mot-clé soit une relation R inter mots-clés. Le poids d'un mot-clé est le nombre de requêtes

incluant ce mot-clé. Le poids _PRAB d'une relation _RAB entre un mot-clé A et un mot-clé B est

égal au nombre de requêtes incluant conjointement les deux mots-clés A et B.

^D

F

^D

^C

^H

? Le poids d'un mot-clé : Nb étant le nombre total de requêtes, _MCT,Q étant

l'élément valant 1 si le mot-clé T est présent dans la requête Q et 0 sinon. On

définira le poids d'un mot-clé A noté PA comme suit :

PA= MA,Q

? Le poids d'une relation : Soient les deux mots-clés A et B, la relation _RAB telle que A _RAB B, Nb le nombre total de requêtes, Ri étant l'élément de valeur « vrai » ou « faux » si les mots-clés sont conjointement présents dans la requête (vrai valant 1, faux valant 0). On définira le poids d'une relation _RAB ^noté _PRAB comme suit :

PRAB = RI

Remarque : Le poids total d'un mot-clé n'est pas nécessairement la somme des poids de ses relations. En effet, une même recherche peut inclure plusieurs mots-clés et donc

3.3 : Méthode 2 : Rigidification Simple 96

Chapitre 3. Les méthodes d'agrégations proposées

compter pour 1 dans le poids du mot-clé qui est en relation avec « n » mots-clés (cf. figure 3.3).

Graphe non orienté													Matrice symétrique des poids du graphe
													Mot	Poids mot	A	B	C	D	E
													A	8	-	6	7	0	2
													B	10	6	-	10	0	0
													C	20	7	10	-	2	1
													D	500	0	0	2	-	1
													E	2	2	0	1	1	-

^{8 6 B-10}

²

^{1 D 500}

Figure 3.3 : Graphe et Matrice non orientés.

^A

^{7 10}

^{2 C}

²⁰

¹

^E-2

Utilisation du poids pour l'orientation du graphe et l'amélioration de

l'opérateur d'extension

Nous proposons de compléter l'opérateur d'extension par une prise en compte de la notion de poids relatif. Il semble évident que le poids de la relation est à comparer aux poids des mots-clés en relation. Une relation d'un poids de « 1 » entre un mot-clé A pesant « 1000 » et un mot-clé B pesant « 2 » ne représente pas du tout la même importance relative. Ainsi la relation pèse 10^-3 du poids du mot-clé A et .5 du poids du mot-clé B. Afin de prendre en compte ce poids relatif, nous orientons et pondérons le graphe de la matrice présenté en figure 3.3. Nous utilisons pour ceci la valeur du poids du mot-clé de départ sur le poids de la relation du mot-clé de départ avec le mot-clé cible. On note ce rapport CFL ou Coefficient de Fiabilité de Lien.

Ainsi pour un mot-clé A en relation avec un mot-clé B noté A _RAB B, PA le poids du mot-clé A, _PRAB le poids de la relation _RAB. On définit le Coefficient de Fiabilité de Lien du mot-clé A vers le mot-clé B noté _CFLA=>B comme suit :

CFLA=>B = PA / PRAB

La figure 3.4 présente le résultat de cette opération sur le graphe proposé en figure 3.3

3.3 : Méthode 2 : Rigidification Simple 97

Chapitre 3. Les méthodes d'agrégations proposées

^E

²

²

60% B

^A

^25% 8 ^{6 10}

^100%

^50%

^0,5%

¹

^{35% 7 100%}

^50%

^0.2%

^87,5%

¹

²⁰

^C

^75%

^50%

¹⁰

^0.4%

²

^10%

^D

⁵⁰⁰

Figure 3.4 : Graphe orienté pondéré du CFL de la matrice présentée en figure 3.3. (CFL est ici présenté en pourcentage pour en faciliter la lecture).

Matrice symétrique - graphe non dirigé								Matrice asymétrique - graphe dirigé - CFL (%)
Mot	Poids	A	B	C	D	E		Mot	Relation	A	B	C	D	E
A	8	-	6	7	0	2		A	->	-	75	87.5	0	25
B	10	6	-	10	0	0		B	->	60	-	100	0	0
C	20	7	10	-	2	1		C	->	35	50	-	10	5
D	500	0	0	2	-	1		D	->	0	0	0.4	-	0.25
E	2	2	0	1	1	-		E	->	100	0	50	50	-

Tableau 3.1. Matrice asymétrique d'un graphe orienté pondéré - CFL.

Définition d'un opérateur d'extension

L'utilisation de cet algorithme avec un opérateur d'extension qui ne tient pas compte de la valeur relative des liaisons a pour conséquence la création d'un agrégat massif de plusieurs milliers de mots-clés. Il paraît donc indispensable de définir des seuils de validité. Pour ne pas maintenir des liens présentant un CFL trop faible, nous ne prenons en compte que les relations présentant un CFL supérieur à une valeur nommée Valeur Minimale de CFL ou Val-Min-CFL. De même, pour les mots de faible poids en relation avec des mots de poids fort, nous maintenons quel que soit le CFL de sens inverse toutes relations ayant un CFL supérieur à la valeur d'activation prédéterminée ou Val-Activ-CFL. Dans cette méthode les valeurs Val-Min-CFL et Val-Activ-CFL sont définies arbitrairement après un ensemble d'essais ayant pour but de détecter un ordre de grandeur permettant à l'opérateur de fonctionner.

Dans l'exemple ci-dessus (cf. Figure 3.4), l'opérateur défini est appliqué à la phase d'extension.

L'opérateur d'extension définitif sera donc basé sur les deux règles suivantes :

? le graphe doit rester bi-connexe ;

? un CFL inférieur à Val-Min-CFL supprimera la relation sauf si le CFL de sens inverse est supérieur à Val-Activ-CL.

3.3 : Méthode 2 : Rigidification Simple 98

Chapitre 3. Les méthodes d'agrégations proposées

Dans l'exemple de la figure 3.5 nous représentons sur le graphe déjà présenté en figure 3.4 le déroulement de l'algorithme de la phase d'extension. La valeur de Val-Min-CFL est arbitrairement fixée à 5 et celle de Val-Activ-CLF arbitrairement à 20. La liaison C-D n'est pas maintenue car le _CFLD=>C est inférieur au Val-Min-CFL fixé et le CFLc=>d est inférieur au Val-Activ-CFL fixé. L'élément « D » ne peut donc rejoindre l'agrégat car le graphe résultant ne serait alors plus bi-connexe.

Étape I : Validation du lien A-E. Le lien appartient à une triade.

Étape II : Extension vers le noeud C. Validation des liens A-C et E-C : « Bien que le CFLC=>E soit inférieur au Val-Min-CFL le lien est maintenu CFLE=>C est supérieur à Val-Activ-CFL ».

250A ^8 E287,5 50 ^35

^75 B ^10 ^50 100

250A ^8 E2 ^35 50

^75 B ^10 87,5 ^50 100

0,5 D

0,5 D

^C

^C

20

500 0,4

20 ^0,2 ^50%

0,4 ^500 ^10

^10

^0,2 ^50%

Étape III : Extension vers le noeud B. Validation des liens A-B et C-B.

Étape IV : Tentative d'extension CFLD=>C est inférieur à Val-Min-CFL inférieur à Val-Activ-CFL. Le lien maintenu.

vers le noeud B, et CFLC=>D est C-D ne peut être

iâ0 ^A ^8 ^E2 50 ^35

^60 ^75 B 10 87,5 ^50 100

in0 ^A 75 ^8 ^E 2 87,5 ^35 50

^B ^10 ^50 100

0,5 D

0,5

D

^C

^C 20

^500 0,4

20

500 0,4

^0,2 ^50%

^10

^0,2 ^50%

^10

Étape V : Le noeud D est définitivement l'agrégat son intégration ne permet un graphe de l'agrégat

exclut de pas de maintenir bi-connexe.

L'agrégat définitif est constitué des noeuds E, A, B et C.

^A E2

^8

B 10

^A E 2

^8

^B ^10

^D

-

C

500

20

ç

^20

Figure 3.5 : Illustration du déroulement de l'algorithme Fusion/Extension en utilisant l'opérateur d'extension

définitif.

3.3 : Méthode 2 : Rigidification Simple 99

Chapitre 3. Les méthodes d'agrégations proposées

Mécanisme de regroupement des mots-clés en agrégats (application de la méthode HLS)

Si un mot-clé peut appartenir à plusieurs agrégats, une paire de mots-clés constituant une diade ne peut appartenir au plus qu'à un agrégat. En effet, s'il existe un troisième mot-clé formant avec les deux premiers une triade, cette triade ne sera présente que dans un et un seul agrégat. S'il n'existe pas de triade incluant la diade alors la diade n'est dans aucun agrégat. C'est sur cette règle que se fonde l'algorithme de regroupement en agrégats proposé (cf. Algorithme 3.2).

Pour chaque mot-clé X faire [Phase de fusion]

Extraire les mots-clés Y qui forment une triade valide selon l'opérateur d'extension avec X

Pour chaque couple de mots-clés X-Y valides faire [Phase d'extension]

S'il n'existe pas d'agrégat contenant le couple X-Y et que le couple n'a pas été testé

alors

Créer un nouvel agrégat « X-Y » et ajout de X-Y

Tant que l'on ajoute des mots-clés dans l'agrégat faire

Pour les mots de l'agrégat faire

Rechercher de nouveaux mots en triade

Ajouter des mots-clés formant la triade avec les mots de

l'agrégat

Noter des couples trouvés comme « testés »

Fin de Pour

Fin de Tant que

Fin de Si

Fin de Pour [Fin de Phase d'extension] Fin de Pour [Fin de Phase de Fusion]

Algorithme 3.2 : Regroupement des mots-clés en agrégats (application de la méthode HIS)

A titre d'exemple et afin d'éclairer le lecteur sur les résultats que la technique d'agrégation permet d'obtenir, nous proposons ici une représentation schématique des différents agrégats générés incluant le mot « Apple ».

3.4 : Méthode 3 : Rigidification Régulée 100

Chapitre 3. Les méthodes d'agrégations proposées

^1-Pomme

^4-Fleur

^daylily

^pie

^spice

^3-Cidre

^{de pomme}

^gala

^pollinator

^Apple

^cider

^viniger

^vinegar

^relat

^investor

^2-Ordinateur

^computer

Figure 3.6 : Exemple de 4 agrégats partageant le même mot commun « Apple » résultant de notre proposition.

Comme on peut le remarquer dans la figure 3.6, les quatre agrégats sont cohérents et illustrent quatre contextes (acceptions) différents identifiés par rapport au mot-clé « Apple ». Ainsi, l'agrégat 1 fait référence au fruit (pomme) lui-même, le 2 à la marque d'ordinateur bien connue, le 3 au cidre de pomme et enfin le numéro 4 à une fleur nommée « Daylily » (un Lis) ayant pour non « Apple Pie Spice ».

Afin de valider les résultats, nous proposons plusieurs méthodes. Nous reviendrons en détail sur ces méthodes de validation dans le chapitre 4 consacré aux expérimentations et validations.