Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Algorithme de correspondance par point


Sujet :

Algorithmes et structures de données

  1. #1
    Futur Membre du Club
    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 :



    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

  2. #2
    Membre averti
    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 :
    - p1, …, pn 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,pi) =
    | (la place à laquelle se trouve le produit pi pour l'utilisateur u) - i |, si l'utilisateur u a choisi ce produit ;
    n, sinon ;
    - C1(u,pi) =
    1, si l'utilisateur u n'a pas choisi le produit pi, 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 ;
    - C2(pi) = (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) = C1(u,p1)C2(p1)I(u,p1) + … + C1(u,pn)C2(pn)I(u,pn).
    On peut vérifier que si u est l'utilisateur de référence, D(u) = 0, car par définition, I(u,pi) = 0 pour tout i.
    Les C1(u,pi) sont là pour corriger la pondération implicite (et injustifiée) qu'introduit la définition des I(u,pi) : moins d'importance aux produits choisis vers le milieu (i proche de n/2).
    Les C2(pi) 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 C2(pi), en l'élevant par exemple au carré :
    C2(pi) = (n - i + 1)2 / n2

    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.

  3. #3
    Rédacteur/Modérateur

    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.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  4. #4
    Expert éminent sénior
    Bonjour

    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 :Sélectionner tout -Visualiser dans une fenêtre à part
    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
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

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

    Encore merci.


    Romain