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.
| 
