Discussion :

[vodevil]

Bonjour , je travaille sur un petit moteur de recherche pour mon site, et j'aimerai qu'il soit le plus précis possible j'ai déjà conçue le bot et l'indexeur mais je n'arrive pas a trouver un méthode potable pour calculer le poids des mots les paramètres dont je dispose sont :

> Le nombre de mots dans la page
> Le poucentage de chaque mot (dans se page de provenance)
> Le nombre d'occurence de chaque mot
> Présence ou non dans les headers de page : titre , description, keywords
> Présence ou non dans les liens interne a mon site

Je cherche depuis près d'une semaine une façon de faire un algo avec tout sa qui soit le meilleur possible , j'ai lue des doc sur google et comment il fesait pour calculer sa mais j'ai rien trouvé de très concluants (dise tous un truc différent).

Si vous avez une idée meme farfelue je suis preneur

Merci de votre aide

[nako]

Salut, c'est sûr que google va pas donner son algorithme de ranking !
T'imagines les conséquences économiques ?
D'ailleurs, il me semble qu'ils le changent régulièrement.

Bref, si c'est pour ton propre site, le mieux est de procéder de manière empirique. Tu attribues à chacun de tes paramaètres un poid, de façon à former une combinaison linéaire. Et puis tu testes !

L'avantage, c'est que c'est ton site, que c'est toi qui l'a programmé, alors tu sais comment tu l'as conçu et surtout comment tu l'as référencé !
De sorte, tu dois savoir intuitivement l'importance d'un mot dans le titre, par rapport à sa présence dans le texte.

Bon courage.
a+

[Strab]

Voici une formule trouvée (essentiellement en bidouillant) par une personne très renommée dans ce domaine, mais dont j'ai oublié le nom :

Soient :
- m le mot cherché.
- x(m) le nombre de documents qui contiennent m
- y(m,d) le nombre d'occurences du mot m dans le document d
- n le nombre de documents indexés
- t(d) la taille d'un document

On note :
- tf(m,d) = log(y(m,d))/log(t(d))
- idf(m) = - log(x(m)/n)

Alors, le scrore d'un document pour une recherche sur le mot m est :
score(m,d) = tf * idf

Il existe d'autres façons de calculer tf et idf, tu devrais en trouver pas mal sur le net. tf signifie Term Frequency et idf Inverted Document Frequency.

Cette méthode n'utilise pas les propriétés des pages web comme les headers et les liens, mais elle devrait déjà donner quelque chose de pas mal.

[Graffito]

Bonjour,

Dans la pratique, les différentes formules (comme celle indiquée par Strab) donnent des résultats assez peu différents dans la mesure où :
- les mots "pertinents" (ceux que l'on trouve dans peu de documents) ont une pondération forte,
- les mots "outils" (que l'on retrouve partout) ont une pondération faible.

Les vrais améliorations à apporter se trouvent :
- dans les aspects de synonymie (mines=mine, zéro=ZERO, envellope=enveloppe=ENVELOPE, travail=boulot),
- dans l'élimination des mots vides (article, auxiliaire, adverbe courant),
- dans le traitement des co-occurences (mots situés dans la même phrase),
- dans la présentation du résultat : il est très sympa pour l'utilisateur de classe les réponses par les ensembles de mots communs à la question.

[siaoly]

Bonjour,

Dans la pratique, les différentes formules (comme celle indiquée par Strab) donnent des résultats assez peu différents dans la mesure où :
- les mots "pertinents" (ceux que l'on trouve dans peu de documents) ont une pondération forte,
- les mots "outils" (que l'on retrouve partout) ont une pondération faible.

Les vrais améliorations à apporter se trouvent :
- dans les aspects de synonymie (mines=mine, zéro=ZERO, envellope=enveloppe=ENVELOPE, travail=boulot),
- dans l'élimination des mots vides (article, auxiliaire, adverbe courant),
- dans le traitement des co-occurences (mots situés dans la même phrase),
- dans la présentation du résultat : il est très sympa pour l'utilisateur de classe les réponses par les ensembles de mots communs à la question.

Salut a tous
Je m'intéresse moi aussi au moteur de recherche, j'ai une question a propos des aspects synonymique, j'utilise actuellement l'algorithme de levensthein mais celui ne me donne pas entière satisfaction en effet je considère deux termes comme proche si la distance qui les séparent est au maximum de trois hors cela crée pas mal de faux positif par exemple entre

couleur et poulies

l'algo dit 3 c'est un faux positif les deux mots non rien a voir. Connaissez-vous une méthode pour pallier à ce problème ?

Ma seconde interrogation vient des cooccurrences, comment faire pour calculer un taux de cooccurrence j'ai implémenté vos techniques de la phrase et de la position des mots, j'ai trouvé un algo dit de X² mais il me faut un coup de main pour utiliser ce facteur pour pondérer l'importance de chaque mot

voila voila

[Graffito]

Bonjour,

Connaissez-vous une méthode pour pallier à ce problème (de synonymie)?

La méthode que je préfére est celle du dictionnaires qui consiste à associer à chaque forme d'un mot un ou plusieurs sens.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
Exemple : 
chat,chats,CHAT,CHATS -> chat(discussion), chat(animal)
chatte,chattes,CHATTE,CHATTES -> chat(animal), ...(censuré)

comment faire pour calculer un taux de cooccurrence

Il n'y a malheuresement pas de formule magique qui va dire si un doc avec 3 mots communs avec la question, mais avec une cooocurence, sera mieux classé qu'un doc avec 4 mots commun mais sans coocurence.
Dans la pratique, ce qui compte c'est qu'entre docs avec les mêmes mots, la présence des co-occurences "favorisent" les docs avec co-occurence par rapport aux autres.

[goblin]

Pour ton problème de distance de lenvensthein pourquoi ne pas simplement rechercher dans le mot comparé le mot de base via une expression régulière ?

[mobscene]

voila un site fort interessant sur les co-occurences http://www.theses.ulaval.ca/2005/22376/ch05.html

[cryptorchild]

Bonjour,

Dans la pratique, les différentes formules (comme celle indiquée par Strab) donnent des résultats assez peu différents dans la mesure où :
- les mots "pertinents" (ceux que l'on trouve dans peu de documents) ont une pondération forte,
- les mots "outils" (que l'on retrouve partout) ont une pondération faible.

Les vrais améliorations à apporter se trouvent :
- dans les aspects de synonymie (mines=mine, zéro=ZERO, envellope=enveloppe=ENVELOPE, travail=boulot),
- dans l'élimination des mots vides (article, auxiliaire, adverbe courant),
- dans le traitement des co-occurences (mots situés dans la même phrase),
- dans la présentation du résultat : il est très sympa pour l'utilisateur de classe les réponses par les ensembles de mots communs à la question.

Connais tu un algo qui permette de calculer les co-occurences, je cherche désespérement un algo comme sa , ca je n'arrive pas as en faire un (c pas drole )

thanks

[Graffito]

Bonjour,

Pour les co-occurences, l'approche la plus simple consiste lors de la recherche ou de l'indexation de considérer la phrase ou le paragraphe comme un sous-document et de garder le n° de la phrase dans le document avec chaque mot (une autre option consisterait à conserver la position du mot dans le texte, par exemple caractère 823 du texte).

Cette approche est évidement plus gourmande en resources que de compter simplement le nombre de mots dans le document puisqu'un aura pour chaque occurence le n° de phrase.

Lors de la pondération des réponses, il faudra regarder si dans les doc retenus des phrases comportent plusieurs mots de la question (ou si pour chaque mot de la question, il y a une position qui est proche de celle d'un autre mot de la question).

La technique phrase est à peine plus compliquée à implémenter, mais un découpage logique du texte permettra d'afficher la ou les phrases "pertinentes" du document, un peu comme google.

[goblin]

Bonjour,

Pour les co-occurences, l'approche la plus simple consiste lors de la recherche ou de l'indexation de considérer la phrase ou le paragraphe comme un sous-document et de garder le n° de la phrase dans le document avec chaque mot (une autre option consisterait à conserver la position du mot dans le texte, par exemple caractère 823 du texte).

Cette approche est évidement plus gourmande en resources que de compter simplement le nombre de mots dans le document puisqu'un aura pour chaque occurence le n° de phrase.

Lors de la pondération des réponses, il faudra regarder si dans les doc retenus des phrases comportent plusieurs mots de la question (ou si pour chaque mot de la question, il y a une position qui est proche de celle d'un autre mot de la question).

La technique phrase est à peine plus compliquée à implémenter, mais un découpage logique du texte permettra d'afficher la ou les phrases "pertinentes" du document, un peu comme google.

Bonjour graffito as tu une idée de comment agencé une base de données pour prendre en compte ta technique des phrases ?

Le fait d'évaluer pour chaque mot si un autre mot est proche ne vas t'il pas plombé les performances ?

merci

[Graffito]

Bonjour,

as tu une idée de comment agencé une base de données pour prendre en compte ta technique des phrases ?

Sur le plan théorique, les données à enregistrer sont des triplets mots-doc-n°_de_phrase.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
Le fait d'évaluer pour chaque mot si un autre mot est proche 
ne va t'il pas plomber les performances ?

Pour éviter celà, on calcule avec un système sans technique phrase et on se contente d'utiliser la technique sur les meilleurs documents. D'autre part, sur le plan de l'implémentation, on peut créér pour chaque doc ou pour chaque mots-doc, un tableau (enregistré en binaire) des n° de phrases pluttôt qu'un record de la database par triplets.

[vodevil]

J'ai pensé a différente formule mais elle ne rime a rien du genre

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
Ra = (densité*nombre_total_mot_dans_doc)/(occurence)
Ra = Racine carre[ Ra ];

[vodevil]

Je dispose d'un nouvelle info sur les page je peut maintenant savoir le nombre de lien pointant vers elle
J'ai donc comme paramètres

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
> Le nombre de mots dans la page 
> Le poucentage de chaque mot (dans se page de provenance) 
> Le nombre d'occurence de chaque mot 
> Présence ou non dans les headers de page : titre , description, keywords 
> Présence ou non dans les liens interne a mon site
> Nombre de lien pointant vers elle

Bref, si c'est pour ton propre site, le mieux est de procéder de manière empirique. Tu attribues à chacun de tes paramaètres un poid, de façon à former une combinaison linéaire. Et puis tu testes !

L'avantage, c'est que c'est ton site, que c'est toi qui l'a programmé, alors tu sais comment tu l'as conçu et surtout comment tu l'as référencé !
De sorte, tu dois savoir intuitivement l'importance d'un mot dans le titre, par rapport à sa présence dans le texte.

Le problème c'est que je compte en faire un site communautaire avec des articles et tout le taitouin y'aura donc plusieur "admin" du coup je ne peut pas faire comme tu dit.

Je sais pas si sa compte mais j'utilise un index inversé

Chaque mot pointe vers une page ou il a un poids donné

guitare -> id : 112 -> musique.htm

par exemple en simplifiant.

Pour le truc du pagerank heu j'ai trouvé quelque truc sur le net que j'ai repris mais le calcul du poids d'un mot me pose vraiment problème

[Graffito]

Bonjour,

Tu peux utiliser la formule proposée par Trab avec une généralisation consistant à considérer que le nombre d'occurences d'un mot dans une page est un nombre réel (et non un entier). A partir ce là, il suffit d'attribuer (empiriquement) un coefficient multiplicateur d'occurences pour les mots des headers.

Idem en fonction des liens, on attribue un coefficient multiplicateur sur tous les mots de la page en fonction des liens de la page.

[vodevil]

Voici une formule trouvée (essentiellement en bidouillant) par une personne très renommée dans ce domaine, mais dont j'ai oublié le nom :

Soient :
- m le mot cherché.
- x(m) le nombre de documents qui contiennent m
- y(m,d) le nombre d'occurences du mot m dans le document d
- n le nombre de documents indexés
- t(d) la taille d'un document

On note :
- tf(m,d) = log(y(m,d))/log(t(d))
- idf(m) = - log(x(m)/n)

Alors, le scrore d'un document pour une recherche sur le mot m est :
score(m,d) = tf * idf

Il existe d'autres façons de calculer tf et idf, tu devrais en trouver pas mal sur le net. tf signifie Term Frequency et idf Inverted Document Frequency.

Cette méthode n'utilise pas les propriétés des pages web comme les headers et les liens, mais elle devrait déjà donner quelque chose de pas mal.

J'ai une question peut être stupide mais quand tu dit t(d) taille d'un document tu entenf quoi par la ? le nombre total de mot du document ?

[Graffito]

Bonjour,

Oui, il s'agit bien du nombre de mots du documents (sauf mots "vides" non indexés comme article, ponctuation, etc).

Pour compléter ma réponse précédente sur les liens, on peut envisager d'ajouter aux mots de la page, l'ensemble des mots des pages liées avec un coefficient faible par rapport aux mots du document. Si tu le fais, tu seras à ma connaissance un pionnier et je ne vois pas du tout si le résultat en sera amélioré ou parasité.

[vodevil]

Bonjour,

Oui, il s'agit bien du nombre de mots du documents (sauf mots "vides" non indexés comme article, ponctuation, etc).

Pour compléter ma réponse précédente sur les liens, on peut envisager d'ajouter aux mots de la page, l'ensemble des mots des pages liées avec un coefficient faible par rapport aux mots du document. Si tu le fais, tu seras à ma connaissance un pionnier et je ne vois pas du tout si le résultat en sera amélioré ou parasité.

J'ai repris le développement de mon portail, le moteur de recherche fonctionne parfaitement pour l'instant. Je voudrais tester l'idée que tu énonce ci-dessus mais pourrais tu être plus précis sur comment calculé ce fameux coefficient, sa fait bien deux semaines que je me casse la tète dessus et je n'entrevoie pas d'issue a apart ajouter un coefficient statique mais sa risque de pas etre très fiable

[Graffito]

Bonjour,

Il faut vraiment faire des essais à partir d'un coefficient statique (je dirai entre 0,10 et 0,25) et voir le résultat.

On peut aussi imaginer de multiplier ce coefficient par une fonction croissante de t(doc_lié)/t(doc).

Le plus difficile risque d'être l'évaluation de la qualité du moteur pour chaque variante....

[vodevil]

Bonjour,

Oui, il s'agit bien du nombre de mots du documents (sauf mots "vides" non indexés comme article, ponctuation, etc).

Pour compléter ma réponse précédente sur les liens, on peut envisager d'ajouter aux mots de la page, l'ensemble des mots des pages liées avec un coefficient faible par rapport aux mots du document. Si tu le fais, tu seras à ma connaissance un pionnier et je ne vois pas du tout si le résultat en sera amélioré ou parasité.

Ah carrément , sinon existe il unes ou des bases de données de mots "vides" j'ai récupéré la liste de windows et sur un ti moteur en php que j'avais pompé il y'a quelque années mais bon c'est peut-être pas suffisant