Discussion :

[camboui]

J'ai une grande base de documents, livres. Il y a un moteur de recherche dessus ainsi qu'un ensemble de facilités de navigation genre bookmark, etc.

Mais j'aimerais adjoindre des "plus". Par exemple proposer aux lecteurs les documents "semblables" à celui qu'il est en train de lire.
Comment donc déterminer, parmi tous les documents, les plus "semblables" à un document donné?

Une recherche via google ne me donne rien de concret (autre que de la théorie).
Dans une première approche intuitive, peut-être simpliste, je me proposais d'établir un vecteur binaire de chaque document où chaque bit correspond à un mot existant (donc chaque document aurait son vecteur de 100000 bits s'il y a 100000 mots au total dans l'ensemble des documents). Ensuite on comparerait les vecteurs de chaque document deux à deux (en faisant un "ET" binaire) pour déterminer les plus proches (après comptage des bits étant restés à "1" suite au "ET").

J'y vois déjà plusieurs inconvénients.
-Aucune pondération sur la quantité des mots dans chaque document, ni sur leur position relative;
-temps d'execution d'ordre N² pour déterminer, pour chaque document, les documents qui lui sont les plus proches (même si c'est précalculé, avec 1 million de documents se sera long...);
-le résultat est quantitatif, pas nécessairement qualitatif. Par exemple, imaginons que deux documents seulement parlent de la comète de Haley. Il serait dommage que ces documents ne soient pas "proches" l'un de l'autre. Une pondération sur certaines expressions, termes ou mots serait bienvenue.

En reprenant les idées de base que j'ai pu trouver dans les "théories", il faudrait donner une "empreinte" à chaque document, empreinte qui serait un vecteur de valeurs. Ce vecteur permettrait de placer le document dans un espace à dimension réduite (deux idéalement). Ensuite on obtiendrait les documents les plus proches en cherchant ceux qui se trouvent à "proximité" dans l'espace à dimension réduite via un calcul de "distance".

Voilà, voilà, merci pour vos idées et vos lumières

[Neo82]

Salut

Il me parait assez évident que tu ne trouveras pas grand chose de "concret", mais uniquement de la théorie...

Il faut essayer de voir du côté des classifieurs de documents...

J'ai un bon pdf la dessus si ca t'interesse.... mais faut bien s'accrocher

Pour ceux qui ont lu le post sur la reconnaissance de zones de texte ds une image, il s'agit encore de SVM...

Donc si ca t'interesse, fais moi signe ;)

@++

[camboui]

Merci. Et donc je te fais signe

Le principe théorique est le suivant.

Pour chaque document, on construit son histogramme sur l'ensemble des mots, le dictionnaire. Ainsi, chaque document possède un vecteur d'occurence de chacun des mots du dictionnaire. Ensuite, on peut calculer la "distance" des documents 2 à 2 simplement par (distance euclidienne)
SQRT[(W11-W12)²+(W21-W22)²+(W31-W32)²+(W41-W42)²+...+(Wn1-Wn2)²]
wi1 et wi2 étant les occurences du mot i (1 à n) dans les documents 1 et 2.

Et voilà, j'ai gagné, j'ai toutes mes distances, et donc la similitude de mes documents (les distances les plus courtes). Sauf que j'ai ce résultat après 2000 jours en supposant qu'un calcul de distance est effectué en 1ms sur mon PC...

Bon, que dit la "théorie" pour obtenir un résultat un peu plus rapidement. Simple
Première étape, réduire l'histogramme à un vecteur de 64 composantes sans perdre la notion d'empreinte pour permettre la "similitude" avec d'autres.
Ensuite, au lieu de calculer toutes les distances 2 à 2 (ordre N², à banir), on positionne ces vecteurs dans un espace à 2 dimensions. Pour obtenir les documents semblables à un document donné, on cherche sur cet espace (qui est un plan en somme) dans le voisinnage du document.

Alors pour cette dernière opération, il parait qu'on utilise des SOM (Self-organizing maps). Il s'agit de réseaux à neurones permettant de projecter dans un espace à 2 dimensions les points d'un espace à grande dimensions tout en préservant les relations de proximité (les distances, quoi).

C'est là que je sèche pour l'instant

[Neo82]

Donne moi ton mail... je t'envoie le document dont je parlais..

Je pense que tu y trouveras ton bonheur ;)

++

[camboui]

Je t'ai envoyé un MP afin que tu m'envoies mon bonheur
Merci!

[coco]

fait une recherche sur les thésaurus...

[camboui]

Une recherche sur "thésaurus" dans google me donne un peu de tout et n'importe quoi.
Une recherche sur "document similitude" ou "document similarities" est bien plus efficace.
Au total, beaucoup de théorie mais peu de concret malgré tout.

[camboui]

Entre autres, ceci.

[camboui]

Je pense que je peux applaudir et chaleureusement remercier Neo82.
Bien que, à cause de lui, j'ai maintenant la tête comme un seau après une première lecture du document qu'il m'a envoyé

Grace à lui j'ai p-ê une soluce toute faite, celle qui se trouverait ici:
http://svmlight.joachims.org/

Si ça vous intéresse, je vous tiens au courant.

Merci à tous.

PS: parfois, je me dis que j'aurais mieux fait d'être électricien, ou plombier, ou plafonneur, ou maçon... 8)

[Neo82]

Mais de rien.. :)

je n'ai fait que partager les documents que j'ai ;) c'est tout à fait normal, enfin je trouve

@++

[Selenite]

Voilà une idée, qui vaut ce qu'elle vaut ;-).


La complexité est N, puisque tu utilise un document de référence. Tu fais la recherche à la demande. Donc pas de précalcul en N*N. (Tu peux choisir la méthode du précalcul, mais seulement si tu as quelques millions d'années devant toi ;-))

Déjà, il faut associer à chaque document une série de mots clefs. Eventuellement, une série primaire, et une série secondaire.
On pourrait déjà s'arrèter là. Les résultats seraient bons. Pour parvenir à cette liste de mots clefs, tu peut tout simplement compter les occurences de chaque mots, favorisé les mots placés dans les titres, etc.
Chercher les documents similaires à un autre reviendrait à faire une recherche avec tout les mots clefs du document de référence.

Pour chercher ensuite les similitudes proprement dites, tu peux faire ceci.
Tu extrait un texte non formaté de chacun de la paire de documents à évaluer. A est la taille du premier texte compressé (un coup de zip, et c'est bon). B la taille du second texte compressé. C est la taille des deux texte concaténés puis compressés. Un indicateur de la similitude entre les deux texte est A + B - C. Plus cet indicateur est grand, plus la similitude est grande.

[Neo82]

Salut

Selenite, je ne suis absolument pas d'accord avec la deuxième méthode que tu propose (avec les textes compressées).. ou alors je n'ai pas compris ce que tu voulais dire

Deux fichiers compressés qui se ressemblent ne veut pas du tout dire que les 2 fichiers originaux se ressemblent

L'algo Zip, ou Rar ou tout ce que tu veux est tellement complexe que tu perds toute notion de ressemblance

Enfin c'est mon avis
@++

[Selenite]

Salut

Selenite, je ne suis absolument pas d'accord avec la deuxième méthode que tu propose (avec les textes compressées).. ou alors je n'ai pas compris ce que tu voulais dire

Deux fichiers compressés qui se ressemblent ne veut pas du tout dire que les 2 fichiers originaux se ressemblent

L'algo Zip, ou Rar ou tout ce que tu veux est tellement complexe que tu perds toute notion de ressemblance

Enfin c'est mon avis
@++

Cette méthode donne d'excellents résultats. Je l'ai connue dans un article de Pour la Science (je n'ai ps le numéro en tête, demande moi si tu veux que je cherche).

Je réexplique le principe.

Mettons que chaque texte soit composé d'une partie différente (A pour le premier texte et B pour le second) et d'une partie commune C, les similitudes. Les deux partie peuvent être éventuellement entre-mèlées.

T1 = A + C
T2 = B + C

S est la fonction qui donne la taille compressée d'un texte. (ex: S(A) = 40 octets.)

On considère que
S(T1) = S(A) + S(C)
S(T2) = S(B) + S(C)

D'ou
S(T1) + S(T2) = S(A) + S(C) + S(B) + S(C)

A quoi est égal S(T2 + T1) ?
Elle pourrait être égale à
S(T1 + T2) = S(A) + S(B) + 2*S(C)

Mais comme un algorithme de compression compresse (on est bien d'accord là dessus, hein ? ) les occurences multiples, on a
S(T1 + T2) = S(A) + S(B) + S(C)

D'où
S(T1) + S(T2) - S(T1 + T2) = S(C).

S(C) est la taille des similitudes compressées. Plus S(C), plus les similitudes sont donc grandes.



Cette méthode est basée sur les théories de l'information. Elle requiert un algorithme de compression parfait. L'algorithme de compression est en fait ici un outils de mesure de la complexité. Le méthode ne peut pas être appliquée sur des format déjà compressés (JPG, PDF, etc).
Cette méthode est donc théoriquement exacte. Mais peut-on considérer les algorithmes de compression comme de bon outils pour mesurer la complexité ? L'expérience montre que oui. La méthode a été appliquées à plusieurs type de données pour former ainsi des arbres. Appliquée au génome de différentes espèces elle donne à très peu de chose près la phylogénique de ces espèces. Appliquée à la traduction en plusieurs langues d'un même texte, la méthode donne l'arbre de parentée de langages, etc. Cette méthode donne donc d'excellents résultats. Dans le cas d'un moteur de recherche, je ne connais pas la qualité des résultats quelle peut donner.

J'espère t'avoir convaincu ;-).

[Neo82]

Ben si l'expérience montre que ca marche.... je ne peux pas ne pas être convaincu, puisque je n'ai pas testé ;)


Je reste néanmoins persuadé que la taille de 2 documents compressée n'est pas forcément égale à la taille de ces 2 docs compressés séparement..... Peut etre que je me trompe....

@+

[Selenite]

Je reste néanmoins persuadé que la taille de 2 documents compressée n'est pas forcément égale à la taille de ces 2 docs compressés séparement..... Peut etre que je me trompe....

Tu ne te trompe pas. C'est même ce sur quoi est basé la méthode.

S(T1) + S(T2) = S(T1 + T2)
équivaut à dire que
S(C) = 0

Autrement dit, les documents n'ont aucune similitudes.


L'équation
S(T1) = S(A) + S(C)
est valable puisque A et C n'ont aucune similitudes, par définition des parties A et C.

L'équation
S(T1 + T2) = S(A) + S(B) + S(C)
est valable puisque A et B n'ont aucune similitudes (elles sont dans C les dimilitudes de T1 et T2) tandis que les deux parties C sont identiques et sont donc compressée ensemble.



Exemple.

T1 = "qsdfghazerty"
T2 = "wxcvbnazerty"

Ici, T1 et T2 ont pour similitude le mot azerty.
On a un super algo qui permet de compresser une phrase. Sur une phrase aléatoire (T1 et T2 ont les propriété d'un chaine aléatoire: statistiques normales, etc), il gagne un facteur 2 (simplement par l'utilisation d'un jeu de caractère réduit ;-)).

S(T1) = 6 octets
S(T2) = 6 octets

On a
T1 + T2 = "qsdfghazertywxcvbnazerty"

Notre super algo commence à compressé T1+T2. Il repère immédiatement la répétition du mot azerty. Il ne lui reste plus qu'à compresser la chaine aléatoire (puisque sans répétitions)
"qsdfghazertywxcvbn" (notre super algo utilise très très peu de place pour coder la répétion).

S(T1+T2) = 9 octets

S(T1) + S(T2) - S(T1 + T2) = 3 octets

Le degré de similitude entre les deux chaine est 3 octets.

[Neo82]

Ok ...

à condition que la méthode de compression soit béton!! :)

@++

[Selenite]

à condition que la méthode de compression soit béton!!

C'est pour ça que l'on pensait la méthode inapplicable en pratique. C'est l'expérience qui finalement à montré que les méthodes de compression actuelles étaient suffisament performantes ;-).

[Neo82]

Mais dans le cas présent.... il parait quand meme inconcevable de se taper l'implémentation d'un algo comme Zip ou Rar...

Tu ne crois pas?

[Selenite]

Il n'y a pas besoin de reprogrammer un algorithme de compression. Il suffit de réutiliser des bibliothèques déjà construites.

Voici l'article dont je te parlait: http://www.pourlascience.com/index.php?ids=AjyFGHwsyqeZerDNctdS&Menu=Pls&Action=3&idn3=3833#

Voici un logiciel qui utilise la méthode en question pour comparer des fichiers textes, notament pour trouver les copieurs dans un paquet de copies: http://homepages.cwi.nl/~rooij/programming/findfraud/ (je ne l'ai pas essayer).

[Neo82]

Merci pour l'article ;)