Discussion :

[maccormick]

Bonjour à tous,
Je cherche à classer des messages, extraits de fichiers EML puis rangés dans une base de données, dans des conversations. Ces messages ont un id, un sujet, que je nettoie et que je tronque à 15 caractères, et un numéro. Je travaille sur des bases de 10000 à 40000 messages, donc les fils de discussion peuvent être interrompus, puis repris plus tard ... etc. Voici ce que je fais :
1/ je demande 2 paramètres : un nombre de messages et une distance de levenshtein (expliqués plus bas)
2/ je fais une requête qui classe mes messages selon le sujet tronqué puis le numéro de messages : je range les messages dans des tableaux (je travaille en java) : id, sujet tronqué, numéro message
3/ je calcule la distance de levenshtein, qui est le nombre de caractères de différence, entre le message i et le message i-1
-> si cette distance est inférieure ou égale au paramètre voulu, je passe au 4/; sinon, je crée une nouvelle conversation
4/ je fais un test sur les numéro de messages i et i-1 :
a) si le numéro de message en cours est inférieur à la valeur absolue de la différence entre les 2 numéros de messages i et i-1 => je les range dans la même conversation
b) si non => je crée une nouvelle conversation

L'inconvénient principal est que pour calculer une vraie distance de levenshtein, il faudrait que je compare tous les sujets entre eux ... chose impossible à moins de laisser poireauter l'utilisateur pendant 10 heures ! -> donc comment faire pour la prendre quand même en compte

Bref, je suis un peu dubitatif quant à la manière d'optimiser tout ça, sachant que ça marche bien pour disons 80% des messages.
Je voulais donc savoir si il existe des algos déjà fait pour parvenir à un classement de messages, ou si vous avez des idées neuves à ce propos ? Merci d'avance !

PS : dans les fichiers EML que j'analyse, il y a des références aux précédents messages, aux réponses ... etc mais ce n'est pas fiable à 100% car cela dépend des clients mail de chacun

[Graffito]

Bonjour,

Pourrais-tu clarifier les points suivants.

je range les messages dans des tableaux (je travaille en java) : id, sujet tronqué, numéro message

Dans un tableau, les sujets tronqués son-ils tous identiques ?
Sinon, sur quel critère classes-tu un message dans un tableau ou un autre ?

je calcule la distance de levenshtein, qui est le nombre de caractères de différence, entre le message i et le message i-1
...
il faudrait que je compare tous les sujets entre eux

Ne fais-tu la distance que sur 2 éléments consécutifs d'un tableau ?

si le numéro de message en cours ...

le numéro de message en cours : c'est-à-dire ?

[maccormick]

Bonjour,

Dans un tableau, les sujets tronqués son-ils tous identiques ?
Sinon, sur quel critère classes-tu un message dans un tableau ou un autre ?

Je fais une requête et range les id messages dans un tableau d'id, les sujets tronqués de message, dans un tableau de sujets tronqués et les numéros de messages, dans un tableau de numéros de messages. J'ai donc 3 tableaux. J'ai voulu travaillé avec des tableaux de tableaux de tableaux, mais c'était un peu compliqué et je n'avais pas le temps, idem pour les listes chainées, et là je vais essayer avec des map ...

Ne fais-tu la distance que sur 2 éléments consécutifs d'un tableau ?

Oui, car comme je le dis plus bas dans mon message, calculer pour chaque sujet sa distance par rapport à TOUS les autres sujets, me coûte beaucoup trop de temps de calcul. Et vu que je classe avant les sujets pas ordre alphabétique, je ne me plante pas trop (par exemple, je vais louper la correspondance entre un sujet "saluttoicava" et "aluttoicava" car ils ne sont pas consécutifs dans un classement alphabétique. par contre, j'aurai "saluttoicava", "salutoicava", "saluoicava" ...etc)

Globalement, ma méthode marche, mais comme j'ai trop le nez dedans, je me dis qu'il y aurait peut être d'autres façons de faire ! Merci de ton aide.

[Aleph69]

Bonjour,

Oui, car comme je le dis plus bas dans mon message, calculer pour chaque sujet sa distance par rapport à TOUS les autres sujets, me coûte beaucoup trop de temps de calcul.

En général, pour ce genre de choses, on réduit la dimension du problème à l'aide d'une méthode de classification hiérarchique (ex:cah) et d'une méthode de partitionnement (ex:k-means).
On emploie une approche hybride : on lance un k-means avec beaucoup de clusters, puis une cah sur ces clusters pour déterminer le nombre adéquat de clusters existants dans ton problème, puis encore un k-means mais cette fois-ci avec le nombre de clusters donné par la cah.

Après, tu pourras calculer les distances entre éléments d'un même cluster sans trop te préoccuper des autres éléments.

[maccormick]

Ok, je vais essayer de faire ça.
Merci !

[Graffito]

Une bonne méthode pourrait consister en une indexation des sujets par leurs mots clés comme le font les moteurs de recherche : ce qui donnerait un "dictionnaire" comportant autant de d'entrées que de mots dans l'ensemble des messages traités et à chaque entrée (un mot) correspondra la liste des numéros de message dans lequel le mot apparait.

Quand on veut déterminer à quellle liste de messages un message peut se raccorder, on prend chaque mot du message et, via le dictionnaire, on obtient la liste des messages avec des mots communs et, pour chacun des messages de la liste, on sait quels sont les mots communs.

Un seuil de "similarité" (distance) dépendant du nombre de mots communs et de leur pertinence (les mots apparaissanrt dans peu de messages étant les plus pertinents) permettra de mettre en relation le message avec ceux de la liste dépassant le seuil de "similarité" (==> conversation).

Si le principe t'interesse, regarde cette discussion sur les moteurs de recherche : http://www.developpez.net/forums/d10...eur-recherche/