Visualisation des pages Web en double

Nous venons de modifier la façon dont nous détectons les pages Web en double ou quasi-dupliquées dans notre robot d’exploration personnalisé pour mieux vous servir. Notre code précédent produisait de bons résultats, mais il pouvait s’effondrer lors de grandes analyses (celles de plus de 85 000 pages environ) et prendre un temps excessivement long (parfois de l’ordre de plusieurs semaines) pour se terminer.

Maintenant que le changement est en ligne, vous verrez de grandes améliorations et quelques changements :

L’heuristique que nous utilisons actuellement pour mesurer la similarité entre deux pages s’appelle empreintes. Les empreintes digitales reposent sur la transformation de chaque page en un vecteur de 128 entiers 64 bits de manière à ce que les pages en double ou presque en double aboutissent à un vecteur identique ou presque identique. La différence entre une paire de pages est proportionnelle au nombre d’entrées correspondantes dans les deux vecteurs qui ne sont pas les mêmes.

L’heuristique la plus rapide sur laquelle nous travaillons s’appelle une hachage de similarité, ou simhash pour faire court. Un simhash est un seul entier non signé de 64 bits, calculé à nouveau de telle manière que les pages dupliquées ou presque dupliquées donnent des valeurs de simhash qui sont identiques ou presque. La différence entre les pages est proportionnelle au nombre de bits qui diffèrent dans les deux nombres.

Le problème est que ces deux mesures sont très différentes : l’une est un vecteur de 128 valeurs, tandis que l’autre est une valeur unique. En raison de cette différence, les mesures peuvent varier dans la façon dont elles voient la différence de page. Avec la possibilité d’un seul crawl contenant plus d’un million de pages, c’est énormément de chiffres que nous devons comparer pour déterminer la meilleure valeur de seuil possible pour la nouvelle heuristique.

Plus précisément, nous devons définir le seuil heuristique pour détecter autant de doublons et de quasi-doublons que possible, tout en minimisant le nombre de faux doublons. Il est plus important de minimiser absolument le nombre de paires de pages qui ne sont pas des doublons, donc nous ne supprimons pas une page en tant que doublon à moins qu’elle *n’est* réellement un doublon. Cela signifie que nous devons être en mesure de détecter les pages où :

Nous sommes extrêmement prudents à ce sujet pour éviter l’expérience client la plus négative que nous anticipions : un changement en coulisse de notre heuristique de détection des doublons, provoquant l’apparition soudaine d’erreurs de “page en double” incorrectes sans raison apparente.

Notre besoin de prendre une décision impliquant de nombreuses quantités numériques est un cas classique où la visualisation des données peut être utile. Notre scientifique des données SEOmoz, Matt Peters, a suggéré que la meilleure façon de normaliser ces deux mesures très différentes du contenu des pages était de se concentrer sur la façon dont elles mesuraient la différence entre les pages existantes. Prenant cela à cœur, j’ai décidé de l’approche suivante :

Le tracé résultant de cette approche ressemble à ceci :

Immédiatement, un problème est évident : il n’y a aucune mesure de tendance centrale (ou son absence) dans cette image. Si plus d’une paire de pages a la même différence telle que mesurée par les empreintes digitales héritées et le simhash, le logiciel de traçage placera simplement un deuxième point rouge précisément au-dessus du premier. Et ainsi de suite pour les troisième, quatrième, centième et éventuellement millième points de données identiques.

Une façon de résoudre ce problème consiste à colorer les points différemment selon le nombre de paires de pages qu’ils représentent. Alors que se passe-t-il si nous sélectionnons la couleur en utilisant une longueur d’onde lumineuse qui correspond au nombre de fois où nous dessinons un point au même endroit ? Cette tactique nous donne un tracé avec du rouge (une longue longueur d’onde) indiquant le plus de points de données, passant par l’orange, le jaune, le vert, le bleu et le violet (vraiment, le magenta sur cette échelle) représentant seulement une ou deux valeurs :

Quel dommage! C’est presque pas de changement du tout. Cependant, si vous regardez attentivement, vous pouvez voir quelques points bleus dans cette mer de magenta, et le plus important de tous, le point en bas à gauche est rouge, représentant le plus grand nombre d’instances de tous. Ce qui se passe ici, c’est que le point rouge représente un compte tellement supérieur à tous les autres comptes que la plupart des autres couleurs entre lui et celles représentant les nombres les plus bas finissent inutilisées.

La solution consiste à attribuer des couleurs de manière à ce que la plupart des couleurs finissent par être utilisées pour coder les comptes inférieurs, et à attribuer progressivement moins de couleurs à mesure que les comptes augmentent. Ou, en termes mathématiques, d’attribuer des couleurs basées sur une échelle logarithmique plutôt que linéaire. Si nous faisons cela, nous nous retrouvons avec ce qui suit :

Maintenant, nous arrivons quelque part ! Comme prévu, il y a une tendance centrale dans les données, même si elle est assez large. Une chose qui est immédiatement évidente est que, bien qu’en théorie, la différence mesurée par simhash puisse aller jusqu’à un maximum de 64, en pratique, elle dépasse rarement 46 (les trois quarts du maximum). En revanche, en utilisant la différence des empreintes digitales, de nombreuses pages atteignent la différence maximale possible de 128 (voyez tous les points rouges et oranges le long du côté droit du graphique). Gardez à l’esprit que ces points rouges et orange représentent de très gros comptes, car l’échelle de couleurs est logarithmique.

Là où nous devons être le plus prudents, c’est sur le bord inférieur des choses. Cela représente des valeurs simhash qui indiquent des paires de pages assez similaires. Si deux pages ne sont pas, en fait, similaires, mais que simhash les mesure de manière similaire là où les empreintes digitales ont vu une différence significative, c’est précisément le type d’expérience client négative que nous essayons d’éviter. Un point problématique potentiel est encerclé ci-dessous :

Le point encerclé représente une paire de pages qui sont en fait assez différentes, mais que simhash pense être assez similaires. (Le point à gauche et encore plus bas s’avère ne pas être un problème : il représente une paire de pages presque en double que l’ancienne heuristique a ratées !)

La position verticale du point gênant représente une différence de simhash de 6 (6 bits correspondants dans les deux valeurs de simhash 64 bits diffèrent). Ce n’est pas le seul cas non plus : occasionnellement, de telles paires de pages apparaissent de temps en temps. Cela arrive dans 1 % ou moins des crawls, mais cela arrive. Si nous choisissons un seuil de différence simhash de 6 (correspondant au seuil que nous avons actuellement défini pour les anciennes empreintes digitales), il y aura des faux positifs.

Heureusement, 6 semble être un cas limite. Au-dessus de 6 bits de différence, le risque d’un faux positif augmente. En dessous de 6, je n’ai pas pu trouver de tels cas pathologiques, et j’ai examiné des milliers de crawls en essayant d’en trouver un. J’ai donc choisi un seuil de différence de 5 pour la détection des doublons basée sur simhash. Cela se traduit par une situation représentée par le graphique final :

Ici, nous avons des lignes tracées pour représenter les deux seuils de différence. Tout ce qui se trouve à gauche de la ligne verticale représente ce que le code actuel signalerait comme doublon. Tout ce qui se trouve en dessous de la ligne horizontale représente ce que le code simhash rapportera. En gardant à l’esprit l’échelle de couleurs logarithmique et le point rouge dans le coin inférieur gauche, nous voyons que le nombre de paires de pages où les deux heuristiques s’accordent sur la similarité dépasse le nombre de paires de pages où elles ne sont pas d’accord.

Notez qu’il y a encore des choses dans le quadrant “faux positif” (en bas à droite). Il s’avère que ces paires ont tendance à ne pas différer beaucoup des paires où les deux mesures concordent, ou, d’ailleurs, des paires de faux négatifs dans le quadrant supérieur gauche. En d’autres termes, avec les seuils choisis, le simhash et les anciennes empreintes digitales ne voient pas de véritables quasi-doublons.

Avec cette décision de seuil, le nombre de faux négatifs dépasse le nombre de faux positifs. Cela répond à notre objectif de minimiser le nombre de faux positifs, même au prix de faux négatifs. Notez que les “faux positifs” dans le quadrant inférieur droit sont en fait assez similaires les uns aux autres, et seraient donc plus précisément décrits comme les faux négatifs de l’heuristique des empreintes digitales héritées, plutôt que comme les faux positifs de l’heuristique des empreintes digitales.

Les aspects les plus visibles du changement vis-à-vis des clients sont doubles :

1. Moins d’erreurs de page en double : une diminution générale du nombre d’erreurs de pages en double signalées. Cependant, il convient de souligner que :

2. Vitesse, vitesse, vitesse : L’heuristique simhash détecte les doublons et les quasi-doublons environ 30 fois plus rapidement que le code d’empreintes digitales hérité. Cela signifie que bientôt, aucun crawl ne passera plus d’une journée à parcourir le traitement post-crawl, ce qui facilitera une livraison beaucoup plus rapide des résultats pour les grands crawls.

J’espère que cet article vous donnera un aperçu significatif de nos changements à venir. J’ai hâte d’entendre vos pensées dans les commentaires ci-dessous.