X
Utilizziamo cookie nostri e di terze parti per migliorare i servizi e analizzare le tue preferenze. Continuando la navigazione accetterai automaticamente l'utilizzo dei cookie.
Per maggiori informazioni e modificare le impostazioni visita la pagina dedicata ai cookie.

SEO

Versione Italiana | English Version | Version Française | Versión en español
Qt S60 Mobile Bluetooth Implementation
Qt Symbian HostNotFound Error

Algorithmes génétiques appliqués à la thématique SEO (Search Engine Optimization)

Cet article vous montre comment nous avons utilisé la méthode des algorithmes génétiques pour optimiser la répartition des liens au sein de sites Web afin de maximiser le PageRank de chacune de ses pages.

La théorie

Commençons par expliquer comment se comporte les algorithmes de link analysis ranking (LAR), qui sont très utilisés par les moteurs de recherche pour effectuer le ranking des pages Web. L'algorithme déduit l'importance d'une page Web en se basant sur la structure topologique du graphe, extrait en analysant les liens hypertext du site en question, le parcourant et en analysant les arcs sortants et les arcs entrants, à savoir, les liens sortants et les liens entrants des pages qui composent le graphe. Sur la base de ces informations, une valeur est associée à chaque page et utilisée par la suite pour le classement.

Un des premiers algorithmes de link analysis ranking est InDegree qui calcule la popularité d'une page en tenant compte du nombre de pages qui ont un lien vers elle. Les algorithmes les plus récents et les plus précis sont les suivants:

  • PageRank
  • Kleinberg (ci-après dénommé HITS)
  • Salsa

PageRank effectue un parcours aléatoire dans le graphe de l'Internet, où chaque page propage son poids aux pages vers lesquelles elle a un lien, déterminant ainsi un array de poids nommés à la suite des poids de haute importance. L'algorithme complet pour le calcul du PageRank repose sur l'usage de la théorie des processus de Markov.

Le modèle de Kleinberg, à la différence de PageRank, propose un schéma de propagation des poids à deux niveaux, distinguant les " authorities " (pages recevant beaucoup de liens) des " hubs " (pages contenant beaucoup de liens vers de bonnes pages). Une page ayant une haute valeur de hub, est une page qui contient des liens vers des pages de qualité (c'est-à-dire avec une grande autorité) et symétriquement une page de haute autorité, sera une bonne liste de liens.

Salsa est un hybride entre les deux algorithmes précédents.
Pour se rapprocher de ces algorithmes, prenons en considération la formule initialement développée par les fondateurs de Google.

Rank[A] = ( 1 - d ) + d i (Rank[Pi] / Link[Pi])
  • Rank[A] est la valeur de PageRank de la page A que nous souhaitons calculer
  • P[i] sont les pages qui contiennent au moins un lien vers A
  • Rank[Pi] sont les valeurs de rank des pages Pi
  • Link[Pi] est le nombre total de liens contenus dans la page qui offre le lien
  • d (Facteur d'amortissement) est un facteur choisi par Google qui dans la documentation originale a une valeur égale à 0.85. Il peut être modifié par Google pour déterminer le pourcentage du PageRank, qui doit passer d'une page à l'autre et la valeur minimum de rank attribué à chaque page dans la base de données.

Les algorithmes en question sont évidemment beaucoup plus complexes et notre but n'est pas de les reproduire fidèlement, mais d'obtenir un modèle mathématique qui parvient à s'en approcher pour obtenir "notre" valeur de Rank qui nous permette de déterminer la bonté de la structure topologique calculée avec l'algorithme génétique après avoir été appliqué.

Faisons maintenant un aperçu des algorithmes génétiques.

L 'algorithme génétique est un algorithme d'analyse de données, et appartient à une classe particulière d'algorithmes utilisés dans divers domaines, y compris l'intelligence artificielle. Il s'agit d'une méthode heuristique de recherche et d'optimisation, inspirée du principe de la sélection naturelle de Charles Darwin qui régit l'évolution des espèces.

Principes de fonctionnement

Un algorithme génétique typique part d'un certain nombre de solutions possibles (individuelles) appelée population et se charge de les faire évoluer au cours de l'exécution: à chaque itération, il fait une sélection d'individus de la population moyenne, l'utilisant pour générer de nouveaux éléments de cette même population, qui remplacera un nombre égal d'individus déjà présents, et constituer ainsi une nouvelle population par l'itération (ou la génération) suivante. Cette succession de générations contribue à l'élaboration d'une solution optimale pour le problème attribué.

L 'évolution est obtenue par le biais d'une recombinaison partielle des solutions, chaque individu transmet une partie de son patrimoine génétique à sa descendance. L'introduction de mutations aléatoires dans la population de départ, génère sporadiquement de nouveaux individus, dont les caractéristiques ne figurent pas parmi celles qui sont présentes dans le bagage génétique de l'espèce d'origine.

Une fois l'étape de l'évolution terminée, la population générée à chaque itération est analysée et ne sont retenues que les meilleures solutions pour résoudre le problème : les individus ayant les qualités les plus appropriées à l'environnement dans lequel ils se trouvent, sont les plus susceptibles de survivre et de se reproduire. Ces solutions vont subir une nouvelle phase de développement et ainsi de suite.

En fin de compte, nous nous attendons à trouver une population de solutions permettant de résoudre le problème. Il n'est pas possible de déterminer à l'avance si l'algorithme sera effectivement en mesure de trouver une solution acceptable. En règle générale, les algorithmes génétiques sont utilisés pour les problèmes d'optimisation pour lesquels on ne connait pas d'algorithmes de complexité linéaire ou polynomiale.

Détail du fonctionnement

La solution du problème est codée dans une structure de données, généralement une chaîne de caractères, appelée gène.

A l'origine, un certain nombre de gènes est créé au hasard et on définit une fonction qui renvoie la "qualité" d'un gène comme une solution au problème, dit la fonction de fitness.
L'algorithme consiste à appliquer des opérations qui tendent à modifier la population de gènes dans la tentative visant à les améliorer afin d'obtenir en permanence une meilleure solution.

L'évolution procède par étapes. Chacune commence par un classement de gènes sur la base du résultat de la fonction de fitness. Ensuite, sont réalisées les opérations sur un certain nombre de gènes paramètres établis par l'algorithme, qui en générale déterminent le nombre de gènes devant subir crossover et mutation, et dans quelle mesure.

L'algorithme évolue à travers les points suivants:

  • Génération, au hasard dans une population initiale
  • Création d'une séquence de nouvelles populations, ou générations. Dans chaque itération, les individus de la population sont utilisés pour créer la génération successive et, à cette fin, et font les dernères étapes :
    • Chaque membre de la population actuelle est estimée en calculant la valeur de leur fitness respectif
    • On détermine un ordre de ces individus, sur la base des valeurs de fitness
    • Les individus les plus prometteurs sont sélectionnés en tant que parents
    • De ces personnes, on génère un nombre égal de personnes de la génération suivante, et cela peut se faire de deux manières, c'est-à-dire en faisant des changements aléatoires sur un seul parent (mutation) ou en combinant de façon appropriée les caractéristiques d'un couple de parents (croisement)
    • Les personnes ainsi produits, vont remplacer les parents en permettant la formation de la prochaine génération
  • Enfin, l'algorithme s'interrompt lorsque l'un des critères d'arrêt est rempli.

Selon un coefficient déterminé au départ, certaines parties des gènes de meilleurs résultats sont échangés, en supposant que cela peut améliorer les résultats de la fonction de fitness à la prochaine "étape évolutive".

Single point crossover

Il existe différentes techniques de crossover. Un des moyens les plus simples est le " single point crossover ", qui est de prendre deux individus et de couper leurs chaînes de caractères d'encodage à un endroit au hasard. On crée ainsi deux têtes et deux queues. A ce moment-là, on échange les têtes et les queues, obtenant deux nouveaux gènes. Le crossover n'est pas toujours appliqué, mais avec une probabilité pc. Dans le cas où il n'est pas appliqué, les enfants sont tout simplement des copies des parents.

Expérimentalement, vous pouvez voir que l'amélioration est la bienvenue seulement après un certain nombre de mesures. Dans ce cas moins de chance, bien sûr.

Mutation

La mutation est le changement aléatoire de certaines parties de gènes d'une valeur de fitness plus basse, sur la base de facteurs définis initialement. Ces changements visent à améliorer la valeur de la fonction pour le gène en question.

En réalité, il n'est pas bon de penser à changer seulement les chromosomes ayant un fitness plus bas ; afin d'assurer une meilleure capacité d'exploration de l'algorithme (et ne pas finir en un seul endroit excellent) les mutations de chromosomes ayant la même valeur haute de fitness sont également considérés comme utiles. En fin de compte les mutations servent principalement à explorer le domaine de recherche, et n'ont pas de meilleur but.

Application

Un site Web est en fait un graphe. Et c'est au graphe du site en examen que nous appliquerons l' algorithme génétique.

La représentation utilisée est celle la matrice de proximité.

La matrice de proximité constitue une structure de données particulière utilisée dans la représentation des graphes. En particulier, elle est largement utilisée dans la préparation des algorithmes qui opèrent sur des graphes et en général dans leur représentation informatique.

Depuis ses tout graphe de la matrice adjacente se compose d'une matrice carrée binaire, qui a, comme indices de lignes et de colonnes, les noms des sommets du graphe. A l'endroit (i, j) de la matrice, on trouve un 1, si et seulement si, il y a un arc dans le graphe qui va du sommet i au sommet j, sinon il y a un 0.

Si au lieu des 1 de la matrice se trouvent des nombres, ceux-ci sont à interpréter comme le poids donné à chaque arc. Par exemple, si l'ensemble des sommets du graphe représente une série de points sur une carte géographique, le poids des arcs peut être interprété comme étant la distance des points que ceux-ci connectent. Dans notre cas, cela indiquera la quantité de liens.

Dans le cas de la représentation de graphes non-orientés, la matrice est symétrique par rapport à la diagonale principale.

L'une des caractéristiques fondamentales de cette matrice est de permettre d'obtenir le nombre de chemins d'un noeud i à un noeud j qui doivent traverser n noeuds. Pour obtenir tout cela, il suffit de faire la puissance n-ième de la matrice et de voir le numéro qui apparaît au lieu i, j.

Comme expliqué précédemment un gène est une chaîne binaire, c'est-à-dire une séquence de 0 et de 1. L'idée qui est à la base de cet algorithme, est qu'une matrice aussi peut être considérée comme une chaîne binaire, et donc un gène. Si nous voulons accéder à l'élément en position X, Y d'une matrice organisée comme une chaîne de caractères, il suffit d'appliquer la formule suivante:

Value(x,y) = Matrix[ (y*matrixsize) +x ]

Applicant un algorithme génétique au graphe du site, on peut obtenir une meilleure structure topologique qui améliore le rank de chaque page.

Ont été étudiés et mis en oeuvre d'autres processus d'évolution autre que celui de crossover qui a été expliqué précédemment, spécialement conçues pour la problématique SEO.

La fonction de fitness est assez complexe et parmi les paramètres qu'elle prend en compte, il y a le PageRank moyen des pages objectif, le nombre moyen de liens par page et le nombre de pages vide.

L'objectif pages sont les pages du site qui nous intéressent. En règle générale, dans la plupart des cas, on parle de pages de feuille.

Par page vide, on entend une page avec une même valeur de rang égal à 0,15 (qui est déduit facilement de la formule de classement citée ci-dessus), ou bien de la valeur déterminée par l'utilisateur.

L 'algorithme est aussi capable de prendre en compte les contraintes de rédaction et d'évoluer en fonction d'elles.

Les résultats

Cas 1

L'application a permis de faire de nouvelles considérations sur ceux d'avant, qui ont été peut-être considérés comme des certitudes par le SEO. En parlant avec différents spécialistes de seo, en lisant des forums, une des considérations qui l'emporte, est que nous devons "équilibrer" la distribution des liens. Ou bien (en ce qui concerne les liens internes) si une page a un lien pointant à une autre, il convient que celle-ci le lui rende, ou fasse le compte, pour chaque page, autant de liens sortants que de liens entrants. Le modèle mathématique, toutefois, semble dire complètement l'opposé. La page "objectif", que nous voulons optimiser est représentée par le noeud 5.

Modèle circulaire

nodo 1 → 0.999518
nodo 2 → 0.999591
nodo 3 → 0.999652
nodo 4 → 0.999704
nodo 5 → 0.999749
Modèle complexe

nodo 1 → 1.377268
nodo 2 → 1.714694
nodo 3 → 0.993759
nodo 4 → 0.544196
nodo 5 → 0.265642

Comme on peut le voir dans le modèle complexe, la page que nous voulons valoriser a été pénalisée. Il est clair que cette exemple est un peu forcé, mais il s'agit d'une simplification de la structure de nombreux sites Web. Le but de ce test n'est pas de toute évidence de proposer un modèle circulaire pour vos sites, mais celui de montrer comment il n'est pas écarté la validité des structures pour lesquelles nous sommes convaincus.

Cas 2

À la suite des résultats de l'application de l'algorithme génétique à l'adresse suivante: http://www.fratellileonelli.it
Vous pouvez voir la représentation 3D du graphe avant et après le processus. La taille des sphères vertes indique la valeur de rank des pages, tandis que les arcs sont représentés en violet.

Avant l'application
Avant l'application
Après l'application
Après l'application

On peut voir en un clin d'œil la différence avant et après le traitement. Les sphères (les pages Web individuelles) ont un plus grand diamètre, ce qui signifie un rang supérieur, et sont beaucoup plus interconnectées.


Un extrait de l'algorithme génétique résultats
Url Rank Avant Rank Après Variation en %
/20.86998413.694373-34.3824
/come-raggiungerci/1.9239491.051139-45.3655
/foto/3.0787811.464144-52.444
/eventi/1.9821731.14884-42.0414
/progettazione/20.34529513.828813-32.0294
/realizzazione/20.46470313.718434-32.9654
/manutenzione/20.57415813.976818-32.0661
/potatura/20.67448814.024247-32.1664
/erbacee-perenni/29.89837522.935853-23.2873
/arbusti/26.29643116.967085-35.4776
/foto/azienda-florovivaistica-leonelli-0007/0.2154241.110144415.33
/foto/azienda-florovivaistica-leonelli-0008/0.2154240.29862138.6201
/foto/azienda-florovivaistica-leonelli-0009/0.2154240.32209349.5158
/foto/azienda-florovivaistica-leonelli-0010/0.2154240.518017140.464
/eventi/mostra-mercato/0.3184851.077961238.466
/eventi/open-day/0.3184850.40023325.6678
/erbacee-perenni/agastache/rupestris/0.2881620.38049732.0427
/erbacee-perenni/ajuga-reptans/atropurpurea/0.2881620.35359122.7053
/erbacee-perenni/alchemilla/mollis/0.2881620.43985352.6408
/erbacee-perenni/allium/karataviense/0.2886830.53878786.6362
/erbacee-perenni/allium/tuberosum/0.2886830.36386226.0422
/erbacee-perenni/allium-karataviense/ivory-queen/0.2881620.314569.16076
/erbacee-perenni/alyssum/montanum/0.2891210.45696658.0534
/erbacee-perenni/alyssum/saxatile/0.2891211.010271249.429
/foto/azienda-florovivaistica-leonelli-0001/0.2154240.29164235.3805
/foto/azienda-florovivaistica-leonelli-0002/0.2154240.26832324.5558
/foto/azienda-florovivaistica-leonelli-0003/0.2154240.28124930.5559
/foto/azienda-florovivaistica-leonelli-0004/0.2154240.33584855.9007
/foto/azienda-florovivaistica-leonelli-0005/0.2154240.35353364.1102
/foto/azienda-florovivaistica-leonelli-0006/0.2154240.31786447.5525
/erbacee-perenni/alyssum/saxatile-compactum/0.2891211.260897336.114
/erbacee-perenni/amsonia/tabernaemontana/0.2881620.54298488.4299
/erbacee-perenni/anemone/honorine-jobert/0.2900980.39012534.4802
/erbacee-perenni/anemone/konigin-charlotte/0.2900980.35142221.139
/erbacee-perenni/anemone/prinz-heinrich/0.2900981.071951269.513
/erbacee-perenni/anemone/richards-ahrends/0.2900980.43524250.0325
/erbacee-perenni/anemone/rosenschale/0.2900980.39189635.0908
/erbacee-perenni/anemone/whirlwind/0.2900980.3346415.354
/erbacee-perenni/aquilegia/vulgaris/0.2881621.104393283.254
/erbacee-perenni/aquilegia-cerualea/red-hobbit/0.2881621.041284261.353
/erbacee-perenni/aquilegia-cerulea/rose-queen/0.2881620.34679620.3473
/erbacee-perenni/aquilegia-flabellata-pumila/ministar/0.2881620.39112335.7299
/erbacee-perenni/aquilegia-hybride/biedermeier/0.2881620.4502256.2383
/erbacee-perenni/arabis-caucasica/snowball/0.2881620.39051735.5197
/erbacee-perenni/arenaria-montana/alba/0.2881620.43730651.7567
/erbacee-perenni/artemisia/powis-castle/0.2886830.34034617.896
/erbacee-perenni/artemisia/stelleriana/0.2886831.002906247.407
/erbacee-perenni/asclepias/tuberosa/0.2881620.40472340.4497
/erbacee-perenni/aster/snow-flurry/0.2881620.49603272.1363
/erbacee-perenni/aster-dumosus/kippenberger/0.2886830.34891520.8643
/erbacee-perenni/aster-dumosus/schneekissen/0.2886830.34566419.7384
/erbacee-perenni/aster-laterifolius/lady-black/0.2881620.35959524.789
/erbacee-perenni/astilboides/tabularis/0.2881620.40452240.38
/erbacee-perenni/aubretia/blue-cascade/0.2881620.34845420.9227
/erbacee-perenni/begonia/envasiana-bianca/0.2881620.40579340.8208
/erbacee-perenni/belamcanda/chinensis/0.2881620.33134714.9863
/erbacee-perenni/brunnera/macrophilla/0.2881620.44786955.4226
/erbacee-perenni/callirhoe/involucrata/0.2881620.55003990.878
/erbacee-perenni/campanula/loddon-anna/0.2891210.42371746.5537
/erbacee-perenni/campanula/porscharskyana-lisduggan/0.2891210.44134652.6511
/erbacee-perenni/campanula/poscharskyana-stella/0.2891210.35155421.5942
/erbacee-perenni/campanula-persicifolia/telham-beauty/0.2881620.47605765.2042
/erbacee-perenni/campanula-poscharskyana/eh.-frost/0.2881620.42013645.7984
/erbacee-perenni/campanula-punctata/rubriflora/0.2881620.44112653.0825
/erbacee-perenni/centaurea/pulcherrima/0.2881620.44010952.7295
/erbacee-perenni/centranthus/ruber/0.2881620.38574533.8636
/erbacee-perenni/ceratostigma/plumbaginoides/0.2881621.198788316.011
/erbacee-perenni/chrisantemum-coccineus/robin-red/0.2881620.38702934.3093
/erbacee-perenni/chrysantemum/weirichii/0.2881621.040353261.03
/erbacee-perenni/cimicifuga/racemosa/0.2881620.36412626.3612
/erbacee-perenni/convallaria-japonica/nana/0.2881620.48250567.4419
/erbacee-perenni/coreopsis/grandiflora-aureo-marginata/0.2891210.47727565.0779
/erbacee-perenni/coreopsis/verticillata-grandiflora/0.2891211.244313330.378

Il est important de noter que l'algorithme a essayé de distribuer de manière plus homogène le classement du site.
Dans le tableau des résultats définitifs sont mis en évidence en rouge les plus valeurs les plus importants.

Les pages qui sont présentes dans le menu comme vous pouvez l'imaginer sont celles ayant le meilleur rang, à la fois avant et après. Cependant, leur grade a été abaissé pour les pages d'objectif.

Bien entendu, ce problème peut être motivé selon le besoin. Dans ce cas particulier, pour le client il était important d'élever le rang de pages qui contiennent la description de la plante, donc par conséquent, l'algorithme a évolué dans ce sens.

Dans ce qui suit, vous pouvez voir comment ont été positionnés les liens supplémentaires calculés par le processus:

Si vous êtes intéressés par logiciel (gratuit) décrit, vous pouvez télécharger genesis.


Sebastiano Galazzo

tel .: +39 338 5482810

18 novembre 2008

Commenti

rSkVpsSgHQ
2011-10-25 10:38:06
Didn't know the forum rules allowed such brililant posts.

La tua domanda