Pertinence d’une page web
à la requête en citant les pages par ordre de pertinence Le Web a une structure de graphe due au fait que les pages se citent mutuelle-ment C’est le principe de l’hypertexte : les pages se citent mutuellement par les fameux liens Essayons de déterminer la pertinence d’une page web 2 Un exemple Soit le graphe suivant qui relie 4
Pertinence d’une page web
Pertinence d’une page web Présentation historique du web Le 13 mars 1989, Tim Berners-Lee, engagé au CERN à Genève en 1984 pour travailler sur l’acquisition et le traitement des données, propose de développer un système hypertexte organisé en Web, afin d’améliorer la diffusion des informations internes
Pertinence d’une page Web (TS spécialité)
Pertinence d’une page Web (TS spécialité) Exercice 1 Un groupe de musique a mis en place un site internet selon le plan ci-dessous, où les flèches représentent des liens hypertexte 1 Index 2 Shop 3 Mp3s 4 Contact 5 Result • La page Index est la page d’accueil du site Elle renvoie vers les pages Shop, Mp3s et Contact
DM pertinence d’une page web
DM pertinence d’une page web Exercice 1 (pertinence d’une page web) Les flèches figurent les liens Quand on est sur unepage,pourpasseràunesuivante,soitonlaquitteetonchoisitl’autre,soitonclique
Pertinence d’une page Web L’algorithme PageRank
Pertinence d’une page Web L’algorithme PageRank Exercice 1 On s’intéresse au graphe orienté ci-dessous, représentant un ensemble de 5 pages internet et de leurs liens hypertexte P4 P1 P3 P5 P2 Partie A – Comptage naïf et comptage pondéré 1 Classer les pages par ordre de pertinence selon le comptage naïf 2
Pertinence d’une page Web L’algorithme PageRank
Pertinence d’une page Web L’algorithme PageRank Exercice 2 (version longue) Un groupe de musique a mis en place un site internet selon le plan ci-dessous, où les flèches représentent des liens hypertexte 1 Index 2 Shop 3 Mp3s 4 Contact 5 Result • La page Index est la page d’accueil du site Elle renvoie vers les pages Shop
pertinence page web tsspé - clainefr
DE LA PERTINENCE D’UNE PAGE WEB Matrices Travaux Pratiques 1 Comment un moteur de recherche classe les pages web On a représenté ci-dessous cinq pages Internet comprenant des articles sur le sujet « les élèves de terminales S font-ils des études scientifiques ? » Sur certaines des pages, un lien pointe vers une autre
La pertinence : une question cognitive centrale
l’on mesure la pertinence d’une page de la Toile par le nombre de liens qui pointent vers elle ou la pertinence d’un article scientifique par le nombre de fois qu’il est cité La présente étude, en proposant de nouvelles définitions de la notion de pertinence, a pour but d’ouvrir la voie à des mesures plus directes
METHODE DEVALUATION DE LA PERTINENCE DUN PROJET Michel
garanties d'adéquation (maximum de pertinence) L'existence d'une incertitude interne et externe persistante,malgré le souci de les réduire,tant sur le plan des comportements des agents que sur celui des états de la nature,pourrait conduire à croire que la recherche d'une pertinence optimale est un problème d'école
[PDF] les types de serveurs
[PDF] qu'est ce qu'un poste client
[PDF] extrait texte autobiographique
[PDF] un institut effectue un sondage pour connaitre
[PDF] marche aléatoire terminale s
[PDF] soustraction matrice
[PDF] matrice puissance 2
[PDF] matrice nulle
[PDF] tableau entrée sortie exercice corrigé
[PDF] question a poser a un auteur de livre
[PDF] matrice nilpotente exemple
[PDF] matrice nilpotente propriété
[PDF] on ne badine pas avec l'amour
[PDF] cours graphes tes pdf
DERNIÈRE IMPRESSION LE12 mai 2015 à 14:54
Pertinence d"une page web
PAUL MILAN
Lycée d"Adultes de la ville de Paris :
http://www.lyceedadultes.fr/index.html1 Que fait un moteur de recherche
Contrairement à une base de données structurée dont on peut facilement extraire des informations, le Web est une immense collection de textes de toutes natures qui évolue en permanence. Le moteur de recherche copie préalablement les pages sur des milliers d"ordina- teurs (60 000 pour Google!) et les trie par ordre alphabétique (selon les mots clé). Lors d"une requête relative à un mot clé, le moteur répond par la liste des pages contenant ce mot clé. Mais il y en a des dizaines de milliers en général. C"est ici qu"intervient l"innovation de Larry Page (fondateur avec Serguei Brin de Google) connue sous le nom dePagerank(to rank : classer). L"idée est de répondre à la requête en citant les pages par ordre de pertinence. Le Web a une structure de graphe due au fait que les pages se citent mutuelle- ment. C"est le principe de l"hypertexte : les pages se citent mutuellement par les fameux liens. Essayons de déterminer la pertinence d"une page web.2 Un exemple
Soit le graphe suivant qui relie 4 pages
Web : 3 2143 Mesurer la pertinence
3.1 Comptage pondéré
Il est clair qu"une page importante reçoit de nombreux liens. Cependant certaines pages émettent beaucoup de liens ce qui d"une certaine façon diminue leur poids. On pondère alors les liens qui relient les pages. La page 1 pointe vers 3 pages (2,3,4). Chacun de ces liens sera alors pondéré du coefficient 1 3PAUL MILAN1TERMINALE S SPÉ
On peut associer à ce graphe la matrice
M= (aij)oùaijreprésente le coefficient
de la pageiqui pointe surj.M=((((((((((
01313131
20120 0 0 0 1 1 201
20))))))))))
3 2141 3 0,51 0,5 1 3 0,5 0,5 1 3 On peut alors définir la mesure de pertinenceμide la pageien comptant le nombre de liens pondérés qui pointent vers elle : i=∑ ja ji
3,μ3=43,μ4=43Les pages 3 et 4 sont donc les plus pertinentes.On pose la matrice ligne des pertinencesPet la matrice ligneJavec que des 1, on
a alors :P=J×M
Remarque :Mais ce comptage est très facile à manipuler, puisqu"il suffit de créer des "fausses" pages pointant vers la pageipour en augmenter l"importance.3.2 Comptage récursif
La pertinence d"une page est renforcée par la pertinence des pages qui pointent vers elle et elle est diminuée par la dispersion éventuelle des liens issus de ces dernières. En reprenant la pondération précédente, on peut définir la pertinence d"une page ide la façon suivante : i=∑ ja ji×μj Le risque de manipulation consistant en l"ajout de pages vides de sens est alors ici annulé puisqu"une telle page recevrait une mesure de pertinence nulle.On a alors :P=P×M
On obtient le système suivant :
1=12μ2+12μ3
2=13μ1
3=13μ1+12μ2+12μ4
4=13μ1+μ3D"où les pertinences en fonction deμ1:
2=13μ1,μ3=43μ1,μ4=53μ1
Si on fixe la somme des pertinences à 1,
on obtient alors : 1=313,μ1=113,μ3=413,μ4=513
Remarque :La page 4 est alors la plus
pertinente.PAUL MILAN2TERMINALE S SPÉ
4. PERTINENCE ET PROBABILITÉ
4 Pertinence et probabilité
Dans la matrice1M, on peut remarquer que la somme des coefficientsaijsur une ligne est égal à 1. Ces coefficientsaijpeuvent donc s"interpréter comme la probabilité, pour un "sur- feur" qui se trouverait à la pageide suivre le lien qui l"amènerait à la pagej. On suppose que le surfeur est sur une page donné à l"instant 0 et qu"il évolue de page en page en cliquant sur les liens au hasard. En notantUnla matrice ligne admettant pour coefficient à la colonneila probabi- lité que le surfeur se trouve à la pageiau bout denclics, les relations précédentes peuvent se traduire par la relation matricielle suivante : U n+1=Un×M?Un=U0×(M)n On peut montrer que cette suite(Un)converge vers?313;113;413;513?
et ce quelque soit l"état d"origine. On a donc bien une probabilité plus grandede se retrouver en page 4 après un grand nombre de clics! Remarque :Toutefois, il peut arriver que certaines pages ne comportent aucun lien vers d"autres pages; dans ce cas, lorsque le surfeur aléatoirearrive sur l"une d"entre elles, il lui est impossible de la quitter.5 Saut aléatoire
C"est pourquoi Google utilise une astuce : à chaque page, avec une probabilitép le surfeur peut renoncer à suivre les liens et abandonner sa page actuelle pour une autre page choisie au hasard parmi lesnpages du Web.On obtient alors une nouvelle matriceM?carac-
térisant le nouveau système. M ?=p4J+ (1-p)M
Si on prendp=1
5, on obtient :
M ?=120J+45M=(((((((((((((1
20196019601960
920120920120
1201201201720
920120920120)))))))))))))On démontre que les puissances de la matrice
M ?conduisent à une matrice limite et à des in- dices de pertinence qui sont : 135572,3232860,171572,10072860
à comparer aux indices trouvés précédemmentμ1μ2μ3μ4
Sans saut aléatoire0,230,080,310,38
Avec saut aléatoire0,240,110,300,35
Danslesdeuxcaslapage4demeurelaplusper-
tinente Pour résumer, plus vous aurez de liens de qualité vers votre site, plus votrePage- Ranksera élevé, plus vos chances d"apparaître en bonne position dans le moteur de recherche Google seront accrues.1. Cette matrice est une matrice de transition d"une chaîne de Markov. Une chaîne de Markov
est un processus aléatoire portant sur un nombre fini d"états, avec des probabilités de transition
sans mémoire