Algorithme de correspondance par point

Bonjour,

Depuis plusieurs jours, je me casse la tête pour trouver un algorithme, sans jamais parvenir une solution convenable.
Mon but est de faire sortir la liste des utilisateurs dont les produits enregistrés correspondent le plus à celle de l'utilisateur qui effectue la requête.
L'ordre de la liste des produits a son importance, et c'est ce qui complique la tâche.
Autre difficulté, l'algorithme doit fonctionner pour une liste d'une taille variable.
J'avais pensé à une boucle attribuant des points de façon dégressive (selon un %), au fur et à mesure des passages sur les colonnes.

Voici un tableau qui sera sans doute plus clair :

Pièce jointe 543705

Dans cet exemple, l'utilisateur 4, qui a le produit a en 2ème position, obtiendrais un score élevé.
L'utilisateur 2, qui a le produit a en 3 position, obtiendrais un score un peu moins élevé.
L'utilisateur 3, qui a le produit b en 1ère position, obtiendrais un score important, mais moins élevé que les précédents utilisateurs, car le produit b n'est qu'en deuxième position pour l'utilisateur 1.

J'espère que vous aurez compris mon besoin, et que quelqu'un aura la compétence (et la gentillesse) pour m'aider.

Merci par avance.


Romain

Si j'ai bien compris, l'utilisateur 1 dans le tableau est « l'utilisateur qui effectue la requête ».
Il ne devrait donc pas figurer dans le tableau, mais plutôt en dehors, comme référence.

Je vais donc partir sur cette base-là, en notant :
- p₁, …, p_n les produits que l'utilisateur de référence a choisi en position 1, …, position n ;
- u l'indice de l'utilisateur dans le tableau ;
- I(u,p_i) =

| (la place à laquelle se trouve le produit p_i pour l'utilisateur u) - i |, si l'utilisateur u a choisi ce produit ;
n, sinon ;

- C₁(u,p_i) =

1, si l'utilisateur u n'a pas choisi le produit p_i, et sinon :
(n - 1) / (n - i), pour 1 ≤ i ≤ n/2 si n est pair, pour 1 ≤ i ≤ (n+1)/2 si n est impair ;
(n - 1) / (i - 1), pour n/2+1 ≤ i ≤ n si n est pair, pour (n+1)/2 ≤ i ≤ n si n est impair ;

- C₂(p_i) = (n - i + 1) / n.

Ainsi, on va pouvoir affecter à tout utilisateur u une distance le séparant de l'utilisateur de référence : D(u) = C₁(u,p₁)C₂(p₁)I(u,p₁) + … + C₁(u,p_n)C₂(p_n)I(u,p_n).
On peut vérifier que si u est l'utilisateur de référence, D(u) = 0, car par définition, I(u,p_i) = 0 pour tout i.
Les C₁(u,p_i) sont là pour corriger la pondération implicite (et injustifiée) qu'introduit la définition des I(u,p_i) : moins d'importance aux produits choisis vers le milieu (i proche de n/2).
Les C₂(p_i) sont une manière de pondérer la somme pour que les choix des utilisateurs soient d'importance décroissante du produit 1 au produit n : on peut en imaginer plein d'autres.

+++

Appliqué à l'exemple, voilà ce que ça donne :
D(2) = 1*1*2 + 1*3/4*4 + 1*2/4*4 + 1*1/4*4 = 8
D(3) = 1*1*4 + 3/2*3/4*1 + 1*2/4*4 + 1*1/4*1 = 59/8 = 7,375
D(4) = 1*1*1 + 1*3/4*4 + 3/2*2/4*1 + 1*1/4*1 = 23/4 = 5,75

On obtient donc un résultat où l'utilisateur 2 est plus éloigné de la référence que l'utilisateur 3 : il faut dire que l'utilisateur 3 coche 2 cases, quand l'utilisateur 2 n'en coche qu'une, et que les cases que l'utilisateur 3 coche sont moins éloignées de la référence que celle que coche l'utilisateur 2.
Ça n'est donc pas absurde, mais si on veut que le produit 1 ait un poids relatif plus important dans le calcul de la distance, de sorte que l'utilisateur 2 apparaisse finalement moins éloigné de la référence que l'utilisateur 3, on peut jouer sur la pondération C₂(p_i), en l'élevant par exemple au carré :
C₂(p_i) = (n - i + 1)² / n²

Avec cette nouvelle pondération, on obtient :
D(2) = 1*1*2 + 1*9/16*4 + 1*4/16*4 + 1*1/16*4 = 11/2 = 5,5
D(3) = 1*1*4 + 3/2*9/16*1 + 1*4/16*4 + 1*1/16*1 = 5 + 29/32 = 5,90625
D(4) = 1*1*1 + 1*9/16*4 + 3/2*4/16*1 + 1*1/16*4 = 31/8 = 3,875
Cette fois-ci, l'utilisateur 3 est donc plus éloigné de la référence que l'utilisateur 2.

Je propose une autre solution, pas basée sur une distance.

L'utilisateur de référence a choisi (a,b,c,d)

Dans mon traitement , a va avoir un coefficient 1, b coeff 1/2 ; c coeff 1/3 ; d coeff 1/4
Pour chaque utilisateur à comparer à cet utilisateur de référence, j'introduis aussi un jeu de coefficient selon la même logique, mais en commençant à 1/2
Dans ton exemple, l'utilisateur 2 avait choisi (d,e,a,f) ; d aura un coeff 1/2, e coeff 1/3 , a coeff 1/4 et f coeff 1/5
Cet utilisateur aura la note 1*1/4 + 1/4*1/2 = 3/8
1*1/4 pour la lettre a, et 1/4*1/2 pour la lettre d ; les lettres e et f n'apportent rien, parce qu'elles ne figurent pas dans la liste de référence.

L'utilisateur 3 a choisi (b,f,d) , donc b=1/2 ; f=1/3 et d=1/4 ; sa note finale est 1/2*1/2 + 1/4*1/4 =5/16
L'utilisateur 4 a choisi (f,a,g,c), donc f=1/2 ; a=1/3 ; g=1/4 et c=1/5 ; sa note finale est 1*1/3 + 1/3*1/5=2/5

Il faut bien entendu avoir le plus gros score. Et l'ordre obtenu est bien celui voulu : 4 puis 2 puis 3.
Si un utilisateur choisit (b,c,d), il n'a pas l'élément a, mais il a les 3 autres, il marque 1/2*1/2 + 1/3*1/3 + 1/4*1/4 = 61/144 ; Ce serait le meilleur score. Je je sais pas si c'est le résultat voulu.

Bonjour :coucou:

Citation:

---

L'utilisateur 3, qui a le produit b en 1ère position, obtiendrais un score important, mais moins élevé que les précédents utilisateurs, car le produit b n'est qu'en deuxième position pour l'utilisateur 1.

---

Cette phrase est la clef. C'est juste un tri avec deux critères.
De ce que je comprends, tu fais simplement un tri par rapport aux produits, puis par rapport à l'éloignement du produit par rapport à l'utilisateur de référence.

Dans ton exemple à 4 produits, en considérant tous les utilisateurs possibles, il y aurait l'ordre suivant des 93 possibilités: ("e" symbolise n'importe quel autre produit, qui ne joue pas.)

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93

abcd abce abde abee acde acee adee aeee bacd bace dabc eabc cabd cabe eabd bade dabe baee eabe eacd dace eace cade caee eade daee eaee dbac ebac cbad cbae ebad dbae ebae dcab ecab edab eeab ecad edac dcae ecae eeac eead edae eeae dcba ecba edba eeba edca eeca eeda eeea ebcd dbce ebce cbde cbee ebde dbee ebee ecbd bcde edbc dcbe bcee ecbe eebc eebd bdee edbe beee eebe edcb eecb eedb eeeb eecd edce eece ecde eedc dcee ecee eeec cdee ceee eeed eede edee deee eeee

---

Pour obtenir ce classement, on peut calculer un score égal à la multiplication de PRESENCE et ANTIDISTANCE. PRESENCE est le score si le produit est présent (par exemple, 100000 pour a, 10000 pour b, 1000 pour c, 100 pour d). ANTIDISTANCE est la différence d'un majorant et la distance à la référence (ici, 5 - distance).
Exemple :
abcd score : 555500
dbac score : 354200
eeac score : 304000
eeee score : 0

Merci infiniment pour vos réponses, c'est vraiment sympa !
Je vais les étudier chacune (et essayer de les comprendre...).

Encore merci.


Romain