Comparaison de liste

[pythonic]

Bonjour tout le monde,

Ne sachant pas trop dans quelle catégorie poser ma question, je me suis dis que j'allais aller faire un tour au café...

Voilà... Je possède un certain nombre de phrases (oui, de vrais phrases en français), que je regroupe suivant leur sens en un certain nombre de groupes. J'obtiens un ensemble d'ensemble de phrases, qui sera mon classement de référence :
{ {p11, p12, ... p1N}, ... {pi1, pi2, ... piN}, ... {pN1, pN2, ... pNN} }

J'ai également, réalisés avec les même phrases, des classements réalisés automatiquement avec un ordinateur, qui contiennent plus ou moins d'erreurs selon l'algorithme d'analyse lexical utilisé.

par exemple, si le classement de référence est :
{ {p1,p2,p3,p4}, {p5,p6,p7,p8}, {p9,p10,p11} {p12,p13,p14}, {p15,p16}, {p17,p18} }

un classement parfait est :
{ {p1,p2,p3,p4}, {p5,p6,p7,p8}, {p9,p10,p11} {p12,p13,p14}, {p15,p16}, {p17,p18} }

un très bon classement est : (p4 est dans le mauvais groupe)
{ {p1,p2,p3}, {p4,p5,p6,p7,p8}, {p9,p10,p11} {p12,p13,p14}, {p15,p16}, {p17,p18} }

un très mauvais classement est (rien n'est bon):
{ {p1,p5,p9,p12,p15,p17}, {p2,p6,p10,p13,p18}, {p3,p7,p11,p14}, {p4,p8} }

Afin de déterminer si un classement est bon ou mauvais, il faudrait déterminer le nombre d'opérations élémentaires nécessaires, pour passer d'un classement donné au classement de référence, avec comme opérations élémentaires choisis:
-O1: séparer un groupe en deux :
{..., {p1,p2,p3,p4,p5}, ...} => {..., {p1,2}, {p3,p4,p5}, ...}

-O2: fusionner deux groupes :
{..., {p1,2}, {p3,p4,p5}, ...} => {..., {p1,p2,p3,p4,p5}, ...}

-O3 déplacer un élément d'un groupe vers un autre:
{..., {p1,2}, {p3,p4,p5}, ...} => {..., {p1,p2,p3},{p4,p5}, ...}

L'idée serait alors de trouver :
- le chemin minimisant le nO1 nombre d'opération O1,
- ou le chemin minimisant nO2 le nombre d'opération O2,
- ou le chemin minimisant nO3 le nombre d'opération O3,
- ou le chemin minimisant nO1+nO2+nO3,
- ou le chemin minimisant C1*nO1 + C2*nO2 + C3*nO3, avec C1, C2, C3 des coefficients constants donnés


Je trouve le problème assez joli... Mes questions:
- pensez vous que le problème est mathématiquement bien posé?
- pensez vous que le problème ait une solution?
- pensez vous que l'algorithme trouvant les chemins est facile à programmer?
- pensez vous que c'est un problème classique, que des algorithmes existent déjà?
- vers quels domaines me tournez pour trouver des solutions, ie quels mots clefs taper dans google? théorie des groupes? comparaison de liste? minimisation de chemins?

Chaleureux merci à tout ceux qui pourront m'apporter une aide!

[fatal_error]

salut,

pour évaluer la qualité du classement, tu pourrais par exemple procéder de cette sorte :
pour chaque groupe de référence tu étudies un caractère discriminant qui sépare tous tes groupes.
Ensuite quand tu run ton algo, tu regardes simplement si chaque p_i à laquelle tu a affecté à un groupe tombe dans le bon groupe.
Si elle tombe pas, ben tu comptes une erreur. ca me parait être le plus naturel.

Ensuite, si tu veux mesurer une ressemblance, par rapport au classement, le premier mot qui me vient à l'esprit est distance de levenshtein.
Ca consiste a comparer deux chaines de caracteres, et compter le nombre d'addition suppression et substitution de caracteres (ce que tu fais "a peu pres avec tes O_i").

En revanche pour évaluer apres la qualité du classement je reste perplexe. Mais bon, pourquoi pas?

pour la classif de documents, j'étais tombé sur LDA (pas linear discriminant analysis, l'autre). C'est pareil avec tes phrases sauf boulettes. Mais j'ai pas eu le courage de lire jusqu'au bout.

pour trouver le nombre d'opérations nécessaires (minimum, en fonction des criteres), je trouve ca intéressant (mais uniquement si tu cherches à mesurer une ressemblance de classement (et encore)). Mais à première vue, je dirais que min(somme(O_i)) est le plus intéressant à faire. Même si je sais pas si c'est facile.
minimiser O_1 tu trouveras toujours 0, vu que tu peux substituer avec O_3.
De même pour O_2
quant à O_3 tu peux faire une combi de O_1 et O_2...
donc à la rigueur minimiser la somme des opérations.


edit : dsl je viens de voir que en fait tu connais pas les labels en sorti, tas plus un truc genre cluster. Ben dans ce cas là ca revient à mesurer la qualité des clusters...bref je sais pas.