WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

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


par Christian Belbèze
Université Toulouse 1 Capitole - Doctorat en informatique 2012
  

précédent sommaire suivant

3.2 Méthode 1 : Détection de cliques

3.2.1 La clique ou une densité maximale

Quand on cherche à former des ensembles de termes les plus cohérents possibles, le modèle de la « clique » (cf. chapitre 1) s'impose de lui-même. Il est en effet porteur de la densité maximale possible. Dans notre espace de travail, l'appartenance à une clique pour un mot-clé signifie qu'il a été employé dans au moins une recherche avec chacun des autres mots de la clique et qu'il n'existe pas d'autres mots-clés dans la population étudiée (suivant cette règle) qui ne soit pas placé dans la clique.

3.2 : Méthode 1 : Détection de cliques 91

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

On peut donc penser que par le lien présent entre chacun des éléments, ce modèle garantira une forte cohérence sémantique au sein des agrégats.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

a : Graphe G

 

b : Les cliques du graphe G : {1, 2,

3},

{1,

3,

5},

{3,

4,

5,

6}

2 1 3

1 3 5

Figure 3.1 : Un graphe et ses cliques.

7

3

4

4

5

6

6

A la lecture du graphe G représenté dans la figure 3.1a on constate que l'élément diade {1, 2] est un couple de mots-clés utilisés conjointement (au moins une fois) dans une recherche par un internaute. Il en est de même pour la diade {1, 3] et la diade {2, 3]. La triade {1, 2, 3] (cf. figure 3.1b) représente donc une clique de trois mots-clés, telle que chaque mot-clé a été utilisé au moins dans une requête (mais pas nécessairement la même) avec chacun des deux autres. La clique {3, 4, 5, 6] signifie de même que chaque mot-clé a été utilisé au moins dans une requête (mais pas nécessairement la même) avec chacun des trois autres.

1

2

3

5

3.2.2 Mécanisme de regroupement des mots-clés en cliques

Par définition, dans une population, une triade ne peut appartenir qu'à une seule clique et une clique complète contient tous les éléments de la population concernée.

Cette caractéristique nous permet, une fois toutes les cliques issues d'un mot-clé de départ (X) et de ses diades (X-Y) créées, de ne plus avoir à le considérer comme pouvant appartenir à de nouvelles cliques.

Pour chaque mot-clé X classé par MCID* Ascendant faire

Récupérer les mots-clés Y en diade avec X s'il existe Z en triade avec X et Y si Y.MCID est supérieur

à X.MCID

Pour chaque diade X - Y faire

Initialisation clique-en-cours

Ajouter-a-clique (clique-en-cours, X, Y)

Appel Recherche-de-clique (clique-en-cours)

Fin Pour chaque diade X - Y

Fin Pour de chaque mot-clé X

Sub Recherche-de-clique (clique-en-cours)

Ordonner la clique-en-cours par MCID croissant

Si il existe des mots en corrélation avec tous les mots contenus dans clique-en-cours ordonnés par

valeur de MCID et que la valeur de MCID est supérieure à celle du dernier mot alors

Appel Recherche-de-clique (clique-en-cours)

Sinon

Sauvegarde de la clique

Fin de SI

Fin de Recherche-de-clique

Algorithme 3.1 : Création de cliques (*« X.MCID » détermine l'identifiant associé au mot-clé X).

3.3 : Méthode 2 : Rigidification Simple 92

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

En ordonnant les mots-clés par leur identifiant (MCID) nous pouvons ainsi, à l'aide d'une fonction récursive, limiter l'exploration de la population aux mots-clés possédant un identifiant (MCID) supérieur à celui du mot-clé en test (cf. Algorithme 1). Afin d'apprécier l'avantage de cet algorithme, nous proposons d'en mesurer le gain par rapport à une exploration classique.

Considérons un ensemble E de mots-clés (dans un fichier de traçage) contenant 10 éléments : (card(E) = 10). Si nous dénombrons les tests nécessaires à la validation de cliques en testant toutes les combinaisons et en considérant les suites (a,b,c) et (c,a,b) comme différentes, nous déterminons alors que le nombre de suites à 3 éléments dans E est égal à :

= 10 x 9 x 8 = 720

Dans l'algorithme présenté nous avons décidé de classer les éléments (les mots-clés) selon leur identifiant MCID, et de ne considérer comme candidat à la création d'une triade que des mots-clés ayant un identifiant supérieur à celui du mot-clé de départ. Nous établissons ensuite une relation d'ordre, permettant de ne plus revenir sur les ensembles ayant déjà été considérés. Nous pouvons donc utiliser ici des sous-ensembles en lieu et place des suites proposées par un algorithme basique effectuant un balayage total de la matrice. Dans notre exemple, le nombre de sous-ensembles à trois éléments est égal à :

Cela signifie que nous n'aurions que 120 combinaisons à tester au lieu de 720 pour des cliques de 3 éléments.

Dans un ensemble X de n éléments (n ) dans lequel on formera des cliques ayant

jusqu'à 10 éléments, le nombre de recherches sera divisé alors par 10 ! = 3 628 800.

Nous avons recherché ici un modèle de regroupement simple qui devait nous servir de base d'étude. Intuitivement ce modèle semble être en capacité de créer des agrégats sémantiquement cohérents.

précédent sommaire suivant