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

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

pas le but final de mon voyage, mais une passerelle vers une nouvelle destination (cf. figure 3.7a). Il en est de même pour un voyage en avion venant de San-Francisco : je change à New-York pour aller en France (cf. figure 3.7b).

Comme on peut facilement le comprendre, Paris est alors victime de son succès. Les liaisons existantes attirent de nouveaux passagers, ce qui pousse à la création de nouvelles liaisons et ainsi le noeud se spécialise.

Les hôtes des réseaux informatiques chargés d'assurer ces liaisons sont nommés « switchs », « concentrateurs » ou « hubs » (cf. figure 3.7c). Nous proposons d'utiliser la même terminologie dans les graphes de terrain de type « petit monde » et de nommer « hubs » les noeuds fortement concentrateurs. La condition pour qu'un noeud hub existe dans un graphe est bien sûr que le degré de chaque noeud ne soit pas limité.

Dans les réseaux sociaux on retrouve ce même principe, prenons par exemple « la poignée de main » comme créateur de lien. Un candidat à la présidence des Etats-Unis en campagne va créer de cette manière, en quelques mois, des milliers de connexions (cf. figure 3.8c). L'embrassade (serrer dans ses bras), qui peut sembler plus intime, va aussi trouver ses « hubs ». Ainsi, nous pouvons citer le mahatma Amma qui revendique d'avoir pris 29 millions de personnes dans ses bras http://www.amma-europe.org/about-amma.html (cf. figure 3.8b). À l'échelle du quotidien, les professionnels du secteur de la santé et particulièrement en milieu rural (cf. figure 3.8a) peuvent jouer ce rôle de connecteur.

a - Médecin de campagne - Photo
Doisneau 1968

c - Obama en campagne 2010 - Photo David Mcnew

b - Mahatma Amma -
2009 - Photo jean louis
Audebaud

Figure 3.8 : Exemple de personnes « hubs » dans des réseaux sociaux.

Dunbar déclare « En effet, la gestion de relations sociales est consommatrice de temps, ainsi le temps limite le nombre de contacts qu'une personne peut conserver et plus un réseau social est grand, moins la densité est élevée. Elle (la densité) argumente le coût cognitif inhérent à l'entretien de relations sociales. » [Dunbar-1998].

Toutefois dans une représentation graphique de la relation sociale, nous pouvons aussi utiliser un lien dirigé (ce type de lien prend en compte les différentes implications des acteurs des uns vers les autres). Par exemple, pour le Mahatma Amma, le lien social établi avec chacune des 29 millions de personnes embrassée a statistiquement peu d'importance. Mais cela n'est probablement pas le cas dans l'autre sens, si la personne embrassée par le Mahatma Amma n'a que très peu de contacts sociaux on imagine l'importance que ce contact peut

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

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

revêtir. On retrouve aussi l'importance de ce lien quand deux personnes ont fait ensemble la démarche de rencontrer le Mahatma. L'élimination du lien entre ces personnes et le Mahatma va alors rompre la clique.

Dans les graphes de mots il existe aussi des noeuds ayant un degré particulièrement important. Le terme le plus utilisé dans les recherches multi-mots sur Internet en avril et mars 2006, sur le moteur de recherche d'AOL est « of ». Ce mot est le mot « hub » par définition : ( http://gregsadetsky.com/aol-data). Dans les deux premières tentatives pour créer des agrégats nous avions éliminé les mots de ce type. Pourtant ils peuvent participer à la construction de figures telles que des triades, qui sont la base de notre système d'agrégation.

1- Graphe de départ

 
 

Création de l'agrégat

2a-En gardant le mot « vide »

2b-En supprimant le mot « vide »

Une diade existe participant d'une triade

 
 
 
 

La triade est marquée comme le départ

 
 
 

L'ajout de « citée » permet de garder le sous-graphe bi-

connexe

 

Conclusion

L'ajout de « new-york » permet de garder le sous-graphe

bi-connexe

 

Le graphe ne contient pas de diade appartenant
à une triade, aucun agrégat ne peut être créé
avec la méthode

 
 
 
 

Figure 3.9 : Suppression d'un mot hub entrainant la perte de la connectivité nécessaire à la construction d'un agrégat.

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

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

Dans la figure 3.9, la suppression du mot « la » nous fait perdre la possibilité de créer un agrégat contenant les cinq mots {grosse, pomme, New-York, citée, la}.

Un rôle disproportionné pour les mots rares

En cherchant à limiter la taille des agrégats, nous notons des mots ou des noeuds qui se comportent comme des verrous de validation du lien. Ces mots sont ceux qui possèdent un très faible poids. Ces mots rares (de faible usage) font basculer systématiquement la valeur de CFL vers des valeurs extrêmement fortes. Ils sont alors trop fortement liés aux autres mots (et spécialement aux termes très fréquents), pour être supprimés par une augmentation de la valeur de Val-Activ-CFL. Ces mots de faible usage doivent pouvoir être écartés ou encore leur rôle doit pouvoir être minoré pour maintenir une taille d'agrégats en deçà de la taille correspondant au seuil de rupture de la validité sémantique.

100 %

A-1

100 %

100 %

Y-20000

X-10000

B-1

100 % 100 %

Figure 3.10 : Blocage des triades par des mots de très faibles usages.

Dans la figure 3.10, le graphe présente deux mots A et B conjointement utilisés une seule fois avec deux mots très utilisés X et Y. La requête effectuée par l'utilisateur était {A, B, X, Y}. X et Y sont des mots utilisés dans 10000 et 20000 requêtes. La valeur de CFL est pour toutes les liaisons égale à 1 (ou à 100%), ainsi la liaison est toujours valide et cela indépendamment des valeurs de Val-Min-CFL et de Val-Activ-CF.

Les noeuds peu utilisés sont alors des éléments qui verrouillent la validité des liens entre des noeuds plus utilisés, voire même des noeuds de type « hub ». Ainsi deux mots, A et B, utilisés une seule fois conduisent à la création d'un agrégat {A, B, X, Y} (quand bien même A et B n'ont été utilisés que dans une seule recherche sur une période de deux mois). Il existe un fort risque que ces mots soient, en fait mal, orthographiés. En somme, plus leur usage est marginal plus ils constituent la base inamovible d'agrégats (cf. figure 3.10). Ces mots super-agrégeants sont un problème qu'il faut traiter.

3.4.2 Présentation de l'algorithme « Rigidification Régulée »

Ce nouvel algorithme est basé sur les mêmes règles de rigidification que l'algorithme de Rigidification Simple. Mais il est écrit en intégrant la volonté de limiter la taille des agrégats. Les agrégats sont créés de façon à ce que le nombre de mots qu'ils contiennent ne

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

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

dépasse pas le seuil de rupture de la validité sémantique. La valeur des paramètres qui permettent la validation des liaisons ainsi que celles maintenant ou pas un noeud dans la structure vat être modulée de façon à limiter la taille des agrégats. Cette taille reste alors toujours sous le seuil de validité sémantique défini.

La Rigidification Régulée est toujours basée sur la méthode HLS. Son opérateur d'extension définitif respecte les règles définies précédemment :

· le graphe doit rester bi-connexe ;

· un CFL inférieur à Val-Min-CFL supprime la relation sauf si le CFL de sens inverse est supérieur à Val-Activ-CLF. Cette validation de la liaison est conditionnée à la taille de l'agrégat. La liaison est donc validée (ou invalidée) dans une boucle de traitement qui exécute deux actions (grâce au calcul de quatre paramètres et ce à chaque fois que l'agrégat atteint sa taille maximale). Les deux actions sont :

o supprimer des noeuds trop utilisés (mots vides ou faibles) et très peu utilisés (mots super-agrégeant) ;

o augmenter la valeur de Val-Min-CFL et de Val-Activ-CLF pour invalider (supprimer) les liens les plus faibles.

Garantir la validité sémantique par une Taille Maximale de l'Agrégat (TMA)

Grace aux résultats d'expérimentations précédentes (cf. paragraphe 4.4.2) nous savons qu'il existe statistiquement un seuil à la taille d'un agrégat pour garantir une validité sémantique. Nous nommons cette valeur TMA pour Taille Maximale de l'Agrégat.

Notre objectif est de créer des agrégats dont le nombre de mots ne dépasse pas la TMA, pour garantir une bonne cohérence sémantique.

Parmi les quatre paramètres utilisés pour limiter le nombre de noeuds dans un agrégat, les deux premiers permettent de supprimer les liaisons « invalides » :

· Val-Min-CFL : le lien est valide si les deux liens dirigés et pondérés le constituant sont supérieurs à cette valeur.

· Val-Activ-CFL : le lien est valide si au moins un des deux liens dirigés et pondérés le constituant sont supérieurs à cette valeur. Les deux autres valeurs sont utilisées pour écarter de l'agrégat les noeuds trop utilisés (mot vides ou faibles) et très peu utilisés (mots super-agrégeant).

· Poids-Min ou Poids minimum de validité : les noeuds ayant un poids inférieur à Poids-Min sont écartés.

· Poids-Max ou Poids maximum de validité : les noeuds ayant un poids supérieur à Poids-Max sont écartés.

À chaque fois que l'agrégat dépasse la TMA, une modification des quatre paramètres est effectuée afin d'écarter un certain nombre de noeuds et de liaisons.

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

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

Pour chaque diade faire

Fin_de_traitement = Faux

Tant que le nombre de noeuds de l'agrégat est inférieur au seuil garantissant la cohérence

sémantique et que l'on peut ajouter des noeuds en gardant un graphe bi-connexe et que PAS

Fin_de_traitement faire

Recherchez de nouveaux noeuds à rajouter dans l'agrégat

Fin de tant que

Si le nombre de noeuds > 2 et nombre de noeuds < seuil garantissant la cohérence sémantique alors

Sauvegarde agrégats

Fin_de_traitement = Vrai

Si Non SI nombre de noeuds > seuil garantissant la cohérence sémantique alors

Suppression des liaisons invalides par augmentation de Val-Min-CFL et Val-Activ-CLF

Suppression des noeuds les plus utilisés Poids > Poids-max et les plus rares Poids < Poids-min

Augmentation de Val-Min-CFL, Val-Activ-CLF, Poids-max et diminution de Poids-min

Si non

Agrégat marqué comme impossible Fin_de_traitement = Vrai

Fin de SI

Fin de Pour

Algorithme 3.3 : Présentation simplifiée de l'algorithme de rigidification incluant un auto-paramétrage des valeurs de rigidification et une auto-suppression des noeuds et liaisons les moins signifiants.

Les deux parties de l'algorithme

Afin d'optimiser la vitesse d'exécution nous avons choisi de séparer l'algorithme en deux parties :

? une première boucle qui recherche rapidement des valeurs efficientes des quatre paramètres. Ces valeurs encadrent des valeurs qui permettrait la création de l'agrégat dans les meilleures conditions ;

? une seconde boucle qui explore finement l'espace entre les valeurs proposées par la boucle principale pour rechercher les valeurs les mieux adaptées à la création de l'agrégat dans les meilleures conditions.

Pour les deux boucles, la condition d'arrêt de la recherche d'agrégat est la même : ou la diade est incluse dans un agrégat dont la taille est inférieure au TMA et supérieure à 2 ou elle ne permet pas la construction d'un agrégat.

La première boucle ou « boucle principale » a pour but d'incrémenter rapidement les valeurs des quatre paramètres pour trouver les valeurs de démarrage et les valeurs finales de la seconde boucle qui est en charge d'optimiser l'agrégat.

La seconde boucle, nommée « boucle fine », cherche à construire un agrégat en affinant les valeurs proposées par la boucle principale. Elle recherche les valeurs précises des quatre paramètres permettant la construction d'un agrégat respectant les règles préétablies.

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

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

V - Step_bf=Step_bf +1 - Incrément des 4 paramètres

vers la valeur suivante afin de supprimer les liaisons et les noeuds

invalides [Boucle Fine]

l'agrégat

et sauvegarde de la diade de

départ comme testée

VI - Echec de la création de

VI - Sauvegarde de l'agrégat

Step-bl et recalculer les 4 « valeurs d'arrêt » comme valeurs de Fin de Step_bl

Oui

[Boucle Principale]

Oui

II - Step_bp=Step_bp +1 - Modification des 4 paramètres

vers la valeur suivante afin de supprimer les liaisons et les noeuds

invalides [Boucle Principale]

Auto-paramétrage

III - Initialisation Boucle Fine : fixer les 4 paramètres aux «valeurs de départ» pour

IV - Création d'agrégats

Utilisation de la règle de rigidification et des

agrégats comme sous-graphes bi-connexes

et

 

non testée qui n'est pas incluse dans

Fin de

 
 
 

I - Création d'agrégats

Trop

 
 

Utilisation de la règle de rigidification et des

agrégats comme sous-graphes bi-connexes

 
 
 
 

de mots dans

 

Existe-t-il une diade appartenant au

moins à une triade

un agrégat?

[Boucle Fine]

Oui

Auto paramétrage

Non

Non

Trois mots au moins

dans l'agrégat?

Trop de mots dans

l'agrégats?

Création des agrégats

Oui

Boucle Principale

l'agrégat?

Non

Boucle Fine

l'algorithme

Sous Processus

Non

Figure 3.11 : Agrégation basée sur la limitation de la taille des agrégats et l'auto-paramétrage des valeurs de rigidification.

Début / fin Test Processus

Les deux boucles (la boucle principale puis la boucle fine) (cf. figure 3.11) sont successivement utilisées pour la création de chacun des agrégats. Chaque boucle calcule la progression des quatre paramètres de manière dissemblable en raison des différences d'échelle des paramètres dans les deux boucles.

précédent sommaire suivant