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

précédent sommaire suivant