3.4 : Méthode 3 : Rigidification Régulée
110
Chapitre 3. Les méthodes d'agrégations
proposées
La boucle principale
La boucle principale a pour but de trouver les valeurs de
démarrage et de fin de la boucle fine. Elle recherche
grossièrement et donc rapidement des valeurs pour lesquelles
l'agrégat est soit inconstructible (la diade de départ n'est plus
intégrée dans une triade), soit possède moins de mots que
la TMA.
Les valeurs finales de la boucle principale ont soit permis
de créer un agrégat de taille inférieure au TMA
soit rompu le lien de la diade de départ ou celui reliant la diade
de départ et l'agrégat. La boucle principale est un test rapide
permettant de trouver les valeurs des quatre paramètres pour valider ou
invalider l'agrégat.
Les valeurs utilisées par la boucle principale dans
l'avant dernier passage c'est-à-dire au « step final -1 »
sont toujours celles permettant la création d'un agrégat
intégrant la diade de départ mais dépassant en nombre de
noeuds la TMA. Les valeurs au « step final » sont
celles permettant de créer un agrégat valide de taille
inférieure au TMA ou d'invalider l'agrégat.
Dans la boucle principale les paramètres liés
à l'usage des mots s'étendent sur une échelle très
importante, le nombre d'utilisations (poids) d'un mot allant, par exemple, de 1
à plus de 300 000 dans une de nos expérimentations. Pour
respecter une meilleure proportionnalité dans l'évolution des
valeurs basées sur le poids des mots, nous utilisons une échelle
logarithmique.
Dans la table 3.1 Step_bl représente le
nombre de fois où l'agrégat a atteint la taille maximale
(TMA) dans la boucle principale. Avg(G.weight)
représente la moyenne du poids des mots dans l'ensemble du
graphe.
Paramètres
|
VD : Valeurs de
Démarrage
|
|
Valeurs Finales
|
|
Valeur en fonction de l'incrément
Step_bp=
Step_bp +1
|
Val-Min-CFL
|
VDVMC = Observation
|
|
prédéterminée (10)
|
|
VDVMC + (10- VDVMC)* ( Step_bl /
NbSteps)
|
Val-Activ-CFL
|
VDVAC = Observation
|
|
Prédéterminée (51)
|
|
VDVAC + (51- VDVAC)* ( Step_bl /
NbSteps)
|
Poids-Min
|
Poids minimum
noeuds
|
des
|
Moyenne des poids mots
|
des
|
Avg( G.weight ) ^ ( Step_bl /NbSteps)
|
Poids-Max
|
Poids maximum
noeuds
|
des
|
Moyenne des poids mots + 1
|
des
|
Max(G.weight ) ^ ((NbStep - Step_bl) / NbStep) +
Avg(G.weight)
|
|
Table 3.1 : Limites et calculs des valeurs des quatre
paramètres dans la boucle principale.
Les valeurs de départ de Val-Min-CFL et
Val-Activ-CFL sont choisies par une observation de populations
spécifiques. En comparant la distribution du poids relatif des liens
entre des mots typés comme monosémiques et des mots quelconques
nous parvenons à déterminer des valeurs justifiées de ces
deux paramètres.
Les valeurs finales de Val-Min-CFL et
Val-Activ-CFL sont choisies selon les critères suivants :
? en statistique médicale par exemple, une
différence supérieure à 5% entre des groupes
témoins est nécessaire pour que les résultats soient
considérés comme validés. Ces 5% sont appelés
« signification statistique » [Weber&al-2001].
Il ne s'agit pas d'une barrière de validité mais davantage d'un
seuil à partir
3.4 : Méthode 3 : Rigidification Régulée
111
Chapitre 3. Les méthodes d'agrégations
proposées
duquel les résultats sont à considérer
comme de plus en plus valables. Si on double ce pourcentage, s'affiche alors un
chiffre de 10% dont la valeur peut d'autant moins être ignorée. La
valeur de 10% est donc choisie comme valeur de Val-Min-CFL, ce qui
signifie qu'en aucun cas l'on ne pourra écarter une diade pour laquelle
le lien représente 10% ou plus des usages pour les deux mots la
constituant ;
· la valeur de 51% comme valeur finale de
Val-Activ-CF est simplement l'expression qu'il n'est pas possible
d'ignorer un lien majoritaire pour un des noeuds. Cela indique que l'on ne
pourra écarter une diade si l'un des noeuds a 51% ou plus de ses usages
avec l'autre noeud.
Il faut garder à l'esprit que ces valeurs sont un
maximum théorique qui ne correspond absolument pas aux valeurs qui
seront véritablement utilisées par l'algorithme pour construire
les agrégats.
La boucle fine
La boucle fine s'exécute après la boucle
principale et conserve le même algorithme que la boucle principale.
La boucle fine crée des agrégats en utilisant
les valeurs finales et les valeurs précédent les valeurs finales
de la boucle principale (celles utilisées dans la boucle principale au
« step final » et au « step final -1 »).
Elles sont beaucoup plus proches entre-elles que les valeurs minimales et
maximales utilisées dans la boucle principale. Du fait que, dans la
boucle fine, les valeurs de départs et valeurs finales sont
resserrées, l'incrémentation est différente ; un
incrément de type linéaire est ainsi plus adapté qu'une
variation logarithmique.
C'est entre les valeurs finales de la boucle principale
(valeurs utilisées au « step final ») et celles
à l'avant dernière exécution de la boucle principale
(valeurs utilisées au « step final -1 ») que la
boucle fine cherche à optimiser et valider un agrégat de telle
sorte que :
· l'agrégat possède un nombre de mots
inférieur au TMA ;
· l'agrégat possède un maximum de mots (de
façon à inclure les mots rares et les mots hubs) ;
· l'agrégat inclue la diade de départ.
Paramètres
|
VD : Valeurs de Démarrage
|
VF : Valeurs Finales
|
Valeur en fonction de l'incrément
Step_bf=
Step_bf +1
|
Val-Min-CFL
|
VDVMC = Val-Min-CFL de la boucle principale pour step_bp -
1
|
VFVMC = Val-Min-CFL de la boucle principale pour
step_bp
|
VDVMC + VFVMC * ( Step_bf /
NbSteps)
|
Val-Activ-CFL
|
VDVAC = Val-Activ-CFL de la boucle principale pour step_bp -
1
|
VFVAC = Val-Activ-CFL de la boucle principale pour
step_bp
|
VDVAC + VFVAC * ( Step_bf /
NbSteps)
|
Poids-Min
|
VDPoids-Min = Poids-Min
de la boucle principale pour step_bp - 1
|
VFPoids-Min = Poids-Min de
la
boucle principale pour step_bp
|
VDPoids-Min +
VFPoids-Min * ( Step_bf / NbSteps)
|
Poids-Max
|
VDPoids-Max = Poids-Max
de la boucle principale pour step_bp - 1
|
VFPoids-Max = Poids-Max de
la
boucle principale pour step_bp
|
VDPoids-Max +
VFPoids-Max * ( Step_bf / NbSteps)
|
|
Table 3.2 : Limites et calculs des valeurs des quatre
paramètres dans la boucle fine.
3.4 : Méthode 3 : Rigidification Régulée
112
Chapitre 3. Les méthodes d'agrégations
proposées
Dans la table 3.2 Step_bf (nombre de pas dans la
boucle fine) représente le nombre de fois où l'agrégat a
atteint la taille maximale (TMA) dans la boucle fine.
Pour Chaque noeud X faire
[PC-1] faire
Step_bp=0
Rechercher les noeuds Y tels que la diade X-Y fasse partie d'une
triade valide (selon les quatre paramètres =
valeurs de départ)
Pour chaque diade X-Y valide faire
[PC-2] faire
Si il n'existe pas d'agrégat incluant X
et Y et que le couple « X-Y » est une diade non testée
alors [SI-1]
Créer un agrégat AX-Y et ajouter X et
Y
Fin_de_Boucle_Principale= Faux
|
Faire - [Boucle Principale]
Tant que l'on ajoute des noeuds à
l'agrégat et que le nombre de noeuds est inférieur
faire
Ajouter de nouveaux noeuds respectant les paramètres de
poids et formant un sous-
graphe bi-connexe
Fin de Tant que
Si le nombre de noeuds dans l'agrégat
>= TMA alors
Step_bp = Step_bp + 1
Vérifier la validité de la diade [X-Y] tel que la
diade X-Y fasse partie d'une triade valide
(respect des quatre paramètres = valeurs
calculées)
Fin de SI
Si le nombre de noeuds dans l'agrégat
< TMA alors
Fin_de_Boucle_Principale = Vrai
Fin de SI
Tant que Non Fin_de_Boucle_Principale
[Boucle Principale]
|
Calculer les valeurs de départ des 4 paramètres
pour la boucle fine (step_bp-1) Calculer les valeurs finales des 4
paramètres pour la boucle fine (step_bp) Step_bf= 0
Suppression et recréation de l'agrégat « X-Y
»
Fin_de_Boucle_fine= Faux
|
Faire - [Boucle Fine]
Tant que l'on ajoute des noeuds à
l'agrégat et que le nombre de noeuds est inférieur à
TMA
Ajouter de nouveaux noeuds respectant les paramètres de
poids et formant un sous-
graphe biconnexe
Fin de Tant que
Si le nombre de noeuds dans l'agrégat
>= TMA alors
Step_bf = Step_bf + 1
Vérifier la validité de la diade [X-Y] tel que la
diade X-Y fasse partie d'une triade valide
(respect des quatre paramètres = valeurs
calculés)
Fin de SI
Si le nombre de noeuds dans l'agrégat
< TMA alors
Fin_de_Boucle_fine= Vrai
Fin de SI
Tant que Non Fin_de_Boucle_fine [Boucle
fine]
|
Si le nombre de noeuds dans l'agrégat
> 2 alors
sauvegarder l'agrégat
Fin de si
Marquer la diade comme testée
Fin de si [SI-1]
Fin de pour [PC-2]
Fin de pour
[PC-1]
|
|
Algorithme 3.4 : Algorithme complet incluant les deux
boucles de la méthode de Rigidification
Régulée.
Si la boucle principale a permis de créer un
agrégat, il peut sembler inutile de lancer la boucle fine. C'est le cas
si l'agrégat au sortir de la boucle principale a une taille égale
au
| 
