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

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.

¹⁰⁰ %

^A-1

¹⁰⁰ %

¹⁰⁰ %

^Y-20000

^X-10000

^B-1

¹⁰⁰ % ¹⁰⁰ %

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.