Calculer un score avec des votes sur combinaisons aléatoires

[Doubrovski]

Bonjour,

Pour un petit jeu en javascript je cherche à calculer un score.
Le jeu propose de voter "oui" ou "non" pour 150 combinaisons qui s'affichent aléatoirement.
Je récupère les "votes" dans une base de données en indiquant "oui" ou "non" pour chaque id de combinaison.
Je génère un tableau qui indique pour chaque combinaison :
- le nombre d'apparition
- le nombre de de "oui "
- le nombre de "non".

Je peux ensuite classer les combinaisons en fonction de leur nombre de "oui".
Etant donné que les combinaisons s'affichent aléatoirement, certaines ont moins été proposées que d'autres aux joueurs. Le résultat est donc erroné.

Comment calculer un score "honnête" en prenant en compte le nombre d'apparition des combinaisons ?

Je pensais peut-être multiplier le nombre de "oui" par (le nb de "oui" / divisé par le nombre d'apparition)

Merci !

[lyceen95]

En première approche, la solution serait de calculer une proportion : (Nb de Oui )/ (Nb d'apparitions)

Avec les informations que tu donnes, c'est la seule réponse sérieuse.

Comment gères tu les questions, est-ce que tu peux considérer que à peu de chose près, toutes les questions apparaissent le même nombre de fois ( pas trop d'écart) ?
Et que veux tu faire de ce calcul, afficher les questions les mieux notées, ou le classement complet t'intéresse, y compris le bas du classement ?
Combien de questions à peu près, et combien de réponses tu penses avoir ?


Si tu as des questions qui sont posées 100 fois, et d'autres seulement 5, ça peut ne pas suffire.
Avoir 5 oui sur 5 répondants , c'est raisonnable, alors qu'avoir 100 oui sur 100 répondants, ça tient du miracle.

Si l'objectif est d'afficher un 'Top 10' (les 10 questions les plus populaires), tu peux bricoler un truc de ce style :
(Nb de Oui )/ (1+Nb d'apparitions)
Comme ça, les questions qui ont été posées très peu de fois sont pénalisées, elles n'entrent dans le top 10 que si elles ont vraiment un très fort taux de réponse Oui.

[Doubrovski]

Salut , merci pour ton aide.
Pour être plus clair :

Il y a 153 couples possibles dans mon entreprise.
Je fais un Secret Santa pour lequel il faut voter pour déterminer qui fera un cadeau à qui.
Des couples s'affichent, et on swipe à droite ou à gauche quand on pense que le couple devrait se faire des cadeaux.
Au final j'obtiens un classement des couples, je prends le couple le plus voté, puis 2e le plus voté jusqu'à ce que tout le monde soit en couple pour se faire des cadeaux.

J'ai calculé un pourcentage d'apparition des couples pour 400 swipes.
nb de swipes du couple * 100 ) / nb de swipes total
Ca va de 2% à 0.2% des swipes. Ce qui n'est pas très régulier... Je peux essayer d'améliorer le code à ce niveau mais j'ai l'impression que ça ne sera jamais régulier.

Donc j'essaie de trouver une manière de pondérer avec les variables citées.
- nombre d'apparition du couple
- % d'apparition
- nombre de "oui " du couple
- nombre "non" du couple

Si je classe les couples avec le nombre de "oui", un 7 "oui" pour 8 "swipes" gagne sur un 6/6.
En même temps je n'ai pas envie qu'un 3/3 gagne par rapport à un 7/8.
Je ne sais pas si tu vois ce que je veux dire...
Il y a aussi la problématique qu'il y a beaucoup d'égalités.

Merci

[lyceen95]

Si je classe les couples avec le nombre de "oui", un 7 "oui" pour 8 "swipes" gagne sur un 6/6.
En même temps je n'ai pas envie qu'un 3/3 gagne par rapport à un 7/8.

Le 'bricolage' que je proposais résout ce problème.
Je proposais nb Oui)/(1+nb apparitions)
Ainsi :
6 sur 6 donne 6/(1+6)=0.84
7 sur 8 donne 7/(1+8)=0.777
3 sur 6 donne 3/(1+3)=0.75
On trouve le classement demandé.

Il reste un problème, c'est que une fois que tu as associé avec , est casé, et tu ne peux plus l'associer avec un autre. Et peut-être que pour le bon équilibre 'global', ça aurait été mieux de garder pour une autre personne.
Le problème semble similaire au problème de ParcourSup : satisfaire à peu près tout le monde. J'avais vu un truc assez clair sur l'algorithme de ParcourSup, et de mémoire, c'était assez simple.

En d'autres mots, même si tu fais en sorte que chaque couple soit proposé le même nombre de fois, ok, tu sais dire que tel couple a plus de suffrages que tel autre, mais ça ne suffit pas.

Après réflexion, ce n'est pas tout à fait le problème de ParcourSup.
Dans parcourSup, il y a 2 groupes (les étudiants, et les places disponibles)
Toi, tu as 18 personnes, et pas 2 groupes de 9 ou un truc du genre.

Faut réfléchir.

[Doubrovski]

Je proposais : (nb Oui)/(1+nb apparitions)

À première vue ça marche, mais...
4/4 = 0.8
3/3 = 0.75
6/7 = 0.75
5/7 = 0.625
Je trouve un peu étrange que celui qui a 6 "oui" et 1 seul "non" arrive à la fin du classement par rapport à 4/4 "oui". Mais peut-être pas...
Je vais réfléchir aussi de mon côté

[Doubrovski]

Il reste un problème, c'est que une fois que tu as associé avec , est casé, et tu ne peux plus l'associer avec un autre. Et peut-être que pour le bon équilibre 'global', ça aurait été mieux de garder pour une autre personne.

Oui, certains couples appréciés ne seront plus visibles dans le classement et d'autres moins appréciés seront placés en binôme alors qu'ils ne l'auront pas mérité
Mais je ne vois pas comment faire si ce n'est de rendre les règles compétitives (certains auraient plusieurs choix et d'autres rien, certains plusieurs cadeaux et d 'autres rien)

[lyceen95]

C'est une question de dosage, le +1 peut être remplacé par +2 ou par +0.5
Il y a un autre problème, c'est pour les couples qui ont obtenu 0 oui.
0 oui sur 3 votes, ou 0 oui sur 6 votes, ce n'est pas pareil. Donc peut-être une formule de ce type :
x est le nombre de votes Oui, y est le nombre de votes total, et on calcule (x+1)/(y+2) .... 1 et 2 étant 2 paramètres qu'on peut doser comme on veut pour coller avec nos idées.
On doit pouvoir faire plus 'mathématique'.
1) on calcule la proportion de Oui sur la totalité des votes
2) pour un nombre n de votes, on sait calculer l'espérance et l'écart-type (je n'ai pas la formule de tête) pour une succession de votes totalement aléatoires avec tous une probabilité de donner Oui.
3) on peut donc normaliser les données : si on a votes oui, l'indicateur intéressant est Et on peut classer tous les couples sur ce critère.

Mais je reviens sur l'autre point (ce n'était pas ta question, mais je me demande si ça ne pèse pas beaucoup plus sur le résultat final). Imaginons qu'on a 4 personnes et non plus 18. On a donc 6 couples.
Supposons pour simplifier qu'on n'a plus ce problème de nombres de votes différents, chaque couple a été affiché 100 fois !
Résultats :
AB 80
AC 78
AD 75
BC 71
BD 66
CD 30
Dans ton processus, tu associes AB. Et donc tu vas associer ensuite CD. Ok, AB c'est le meilleur couple, de peu. Mais CD, c'est le pire couple possible. La configuration (AB;CD) obtient la note 80+30=110, alors qu'on peut obtenir beaucoup mieux avec (AD;BC) qui donne 75+71=146.

Ici, je consolide les résultats en faisant des sommes ... mais ça aussi, ça peut se discuter ; ici A est beaucoup plus 'populaire' que D , il est compatible avec à peu près tout le monde. Au lieu de faire une somme, on peut faire une somme des carrés des notes (et chercher à maximiser cette note), et dans ce cas, on cherche plus à 'bien marier' les plus populaires. Sur cet exemple, je n'ai pas vérifié si ça changeait le résultat.

Avec seulement 18 personnes, je pense qu'une démarche 'force brute' permet de trouver la meilleure solution, avec un traitement qui prendra quelques secondes.

[Doubrovski]

Merci pour tes pistes.
J'essaie de traduire à ma manière.

1) on calcule la proportion de Oui sur la totalité des votes

donc = Total Nb de Oui / Total Nb de votes

pour un nombre n de votes, on sait calculer l'espérance et l'écart-type (je n'ai pas la formule de tête) pour une succession de votes totalement aléatoires avec tous une probabilité de donner Oui.

= Nb de votes du couple
espérance = donc Nb votes du couple x (Total Nb de Oui / Total Nb de votes)
écart-type = j'ai lu cet article mais pas sûr de pouvoir le reproduire.
1 - On calcule la moyenne arithmétique de la série.
2 - On calcule le carré de l'écart à la moyenne de chacune des valeurs de la série.
3 - On calcule la somme des valeurs obtenues.
4 - On divise par l'effectif de la série.

Donc...
Moyenne arithmétique = (Somme du Nb de Oui des couples) / Nb de couples
Pour chaque couple >> (Nb de oui du couple - Moyenne arthmétique)²
écart-type = Racine carré de (Somme de ces valeurs / Nb de couples)

3) on peut donc normaliser les données : si on a votes oui, l'indicateur intéressant est Et on peut classer tous les couples sur ce critère.

Score = (Nb votes oui du couple - espérance) / écart-type

je vais voir si je ne reste pas plutôt sur une de tes propositions précédentes, mais si tu me confirmes qu'il n'y a pas d'erreur, je peux essayer.

Avec seulement 18 personnes, je pense qu'une démarche 'force brute' permet de trouver la meilleure solution, avec un traitement qui prendra quelques secondes.

Je pense avoir compris, en effet c'est intéressant.
Cependant je n'arrive pas à en faire un algorithme.
Pour chaque couple je peux calculer le carré de son score, mais je ne vois pas trop comment trouver la somme maximale de ces scores ni dans quel ordre calculer les comparaisons.

[lyceen95]

Quelques secondes de temps de traitement, c'était très optimiste.
Les algorithmes de type 'force brute' sont un peu particuliers à programmer.
Comme on a seulement 18 personnes, j'ai testé un truc avec une base SQL (sur un serveur assez puissant), j'ai expérimenté en mettant des données aléatoires, j'obtiens la meilleure solution en environ une minute.
Si tu as des vraies données, je peux les charger et te donner les résultats.

Je n'ai pas relu ce que tu écris sur les écarts-types, plutôt demain.

[Doubrovski]

Salut,
une minute de traitement c'est long en effet

Je suis en javascript côté serveur/client avec une base Mongo qui contient une collection de "swipes" positif ou négatif. J'ai une API qui récupère ces données dans la base et fournit des calculs accessibles via des URL (ici les 9 couples, ou le classement général des 153 combinaisons).
En frontend j'utilise react sur nextjs. La page de résultats affiche un décompte jusqu'à une date précise. Le jour venu, c'est une requête http qui est envoyée du frontend vers l'API pour afficher la page.
Si le traitement est trop long, il faudrait qu'il dépende d'un calcul indépendant qui actualise une autre base de donnée qui contiendrait des résultats.

Concernant l'algorithme de classement général des 153 combinaisons, j'ai testé (x+1) / (y+2) qui convient assez bien. Le soucis est qu'il y a beaucoup d'égalités en dessous de 1000, voire 5000 swipes. Donc les personnes ayant un prénom en début d'ordre alphabétique sont un peu privilégiées j'ai l'impression.

Code: Tout sélectionner

  {
    "id": 48,
    "k1": "robert",
    "k2": "cunegonde",
    "name": "Robert & Cunégonde",
    "swipes": 4,
    "yes": 4,
    "no": 0,
    "appear": 1.1560693641618498,
    "score": 0.35714285714285715
  },
  {
    "id": 85,
    "k1": "rodolphe",
    "k2": "germaine",
    "name": "Rodolphe & Germaine",
    "swipes": 4,
    "yes": 4,
    "no": 0,
    "appear": 1.1560693641618498,
    "score": 0.35714285714285715
  }


Concernant l'algorithme qui choisit les 9 couples, je n'ai pas réussi à faire mieux que choisir le couple ayant le meilleur score, puis le deuxième ne contenant pas les 2 premières personnes.

[lyceen95]

On peut trouver un bon compromis entre les 2 algorithmes (le meilleur couple à chaque étape, ou la force brute pour comparer tous les cas possibles et imaginables).
Typiquement, sur les 18 personnes, on a 2 ou 3 personnes très populaires, on peut les associer ensemble ou avec n'importe qui, elles ont un bon score. On a aussi 2 ou 3 personnes très impopulaires, qui obtiennent un score pas terrible sur les 17 lignes où elles apparaissent.
On peut calculer pour chaque personne une popularité moyenne : nombre total de Plus pour cette personne, divisé par nombre total de Votes pour cette personne.
Dans ta démarche, tu cherches le couple qui a la meilleure note.
L'amélioration envisagée, c'est de chercher le couple qui a la meilleure plus-value. Si plusieurs couples ont une note proche du max, et que parmi ces couples, il y a un couple qui associe des personnes avec une popularité très basse, c'est ce couple là qu'on va garder.

Voici un programme qui fait le job :
J'ai une structure qenreg :

Code: Tout sélectionner

type qenreg struct {
   i1    int
   i2    int  // i1 et i2 sont les n° des 2 personnes en question
   nbv   int // nbVotes à propos de ce couple
   nbp   int  // nb Plus pour ce couple
}

et j'ai un tableau tb qui contient 153 lignes de type qenreg.
Programme principal :

Code: Tout sélectionner

for i := 0; i < 8; i++ {
      i1, i2 := f10_bestcouple(tbenreg, 17-2*i)
      tbenreg = f10_nettoie(tbenreg, i1, i2)
      fmt.Println(i1, i2)
   }

J'affiche les 8 premiers couples ; les 2 personnes restantes formeront le 9ème couple.
Et les 2 fonctions f10_bestcouple() et f10_nettoie()

Code: Tout sélectionner

func f10_bestcouple(tb []qenreg, nnnb int) (int, int) {
   var i1, i2 int
   var sumVotes [18]int
   var sumPlus [18]int
   var enreg qenreg
   var bestrg int
   var bestNote int
   for i := 0; i < len(tb); i++ {
      enreg = tb[i]
      i0 := enreg.i1
      sumVotes[i0] += enreg.nbv
      sumPlus[i0] += enreg.nbp
      i0 = enreg.i2
      sumVotes[i0] += enreg.nbv
      sumPlus[i0] += enreg.nbp
   }
   bestrg = 0
   bestNote = -100000
   for j := 0; j < len(tb); j++ {
      enreg = tb[j]
      ii1 := enreg.i1
      ii2 := enreg.i2
      znote := 20000*(enreg.nbp+1)/(enreg.nbv+2) - (10000*sumPlus[ii1]/sumVotes[ii1]) - (10000*sumPlus[ii2]/sumVotes[ii2])
      if znote > bestNote {
         bestNote = znote
         bestrg = j
      }
   }
   enreg = tb[bestrg]
   i1 = enreg.i1
   i2 = enreg.i2
   return i1, i2
}

func f10_nettoie(tb []qenreg, ii1 int, ii2 int) []qenreg {
   var t0 []qenreg
   var ee qenreg
   for i := 0; i < len(tb); i++ {
      ee = tb[i]
      if ee.i1 != ii1 && ee.i1 != ii2 && ee.i2 != ii1 && ee.i2 != ii2 {
         t0 = append(t0, ee)
      }
   }
   return t0
}

En temps de traitement, c'est quasi instantané.
Et accessoirement, ça règle le problème des ex-aequo.

[Doubrovski]

Salut, merci pour ton aide.
Je ne comprends pas tout ton code en python mais j'ai essayé de trouver une logique en m'inspirant des tes conseils. Du moins de départager les égalités avec un score de popularité ou une différence de popularité entre les deux personnes du couple.

J'ai tenté de calculer l'indicateur pour chaque couple et chaque personne de la manière dont je l'ai compris plus haut.

Même si j'ai possiblement fait des erreurs, le classement des couples me semble assez pertinent, même si un peu étrange sur la fin du classement :
7/7 > 6/6 > 6/7 > 4/4 > 7/9 > 5/6 > 3/3 > 6/8 > 4/5 > 2/2 > 5/7 > 3/4 > 1/1 > 4/6 > 2/3 > 5/8 > 3/5 > 1/2

L'équation (x+1) / (y+2) a plus tendance à mettre en valeur les votes positifs avec pas mal d'égalités de score même si les votes sont plus nombreux
7/7 > 6/6 > 4/4 > 3/3 > 6/7 > 2/2 = 5/6 > 7/9 > 4/5 > 6/8 > 1/1 = 3/4 = 5/7 > 4/6 > 2/3 = 5/8 > 3/5 > 4/7 > 5/9 > 1/2

L'équation (x+1) / (y+5) n'est pas mal non plus
7/7 > 6/6 > 6/7 > 7/9 > 4/4 > 5/6 > 6/8 > 4/5 = 5/7 = 3/3 > 5/8 > 4/6 >3/4 > 2/2 > 3/5 > 4/8 > 2/3 > 3/6 > 1/1 = 2/4 > 1/2

Dernier test avec (x+1) / (y+10)
7/7 > 6/6 > 7/9 > 6/8 > 5/6 > 4/4 > 5/7 > 4/5 = 5/8 > 5/9 > 4/6 > 3/3 > 4/7 > 3/4 > 4/8 > 3/5 > 4/9 > 2/2 > 3/6= 2/2 > 2/3 > 3/8 > 2/4 > 3/9 > 2/5 > 2/6 > 1/1 > 1/2

Je ne sais pas trop quoi choisir comme calcul mais une fois que j'ai obtenu un classement des couples, et un classement des personnes, je pensais départager les couples à égalité en prenant le score de popularité le plus faible pour maximiser (additionner la popularité de chaque personne, OU choisir le couple qui a le score de popularité le plus élevé, OU la différence de popularité la moins grande entre les deux personnes (ce qui me séduit pas mal comme idée, même si ça va créer des couples non compatibles).
Bref, je dois finir demain

[lyceen95]

A/ Le code que j'ai posté n'est pas du Python, mais du Go.

B/ Tu as testé des variantes (x+1)/(y+2), (x+1)/(y+5) ... tu peux tester d'autres variantes (x+0.5)/(y+2), (x+9)/(y+10) etc etc.
Tu parlais d'environ 1000 votes, c'est à dire en gros entre 4 et 10 votes pour chaque couple. C'est peu, donc j'ajouterais un petit nombre à la fois au numérateur et au dénominateur : (x+0.6)/(y+1)

C/ Restons sur environ 1000 votes en tout. Chaque vote est une mesure de popularité du couple A+B, mais on peut aussi le voir comme une mesure de popularité de A et de B.
Avec ce point de vue, chaque personne est notée environ 1000x2/18=111 fois.
Chaque personne est notée environ 111 fois, et je compte le nombre de Plus qu'elle a obtenu. Dans mon programme, sumVotes[i] vaut donc environ 111, et sumPlus[i] vaut quelque chose comme 30 (personne très difficile à marier) à 90 voire 100 (personne considérée comme compatible presque partout.
SumPlus[i]/SumVotes[i] est en gros la popularité de chacun.
Petite parenthèse, le dénominateur est un nombre proche de 100, le risque d'avoir 2 personnes avec la même popularité 'totale' est plus faible.
Toutes les popularités que je manipule sont des "pourcentages", des nombres entre 0 et 1
Dans mon calcul, je fais : 2 * Popularité du couple MOINS popularité du membre 1 MOINS popularité du membre 2
Et je multiplie par 10000 parce que je n'aime pas les nombres à virgules, mais ça, c'est juste ma phobie.

Peut-être que cette méthode donne un peu trop de bonus pour les ronchons difficiles à caser, peut-être que
2 * Popularité du couple MOINS MAX( popularité du membre 1 , popularité du membre 2) serait plus équilibré.
Tu peux aussi tester 3 * Popularité du couple MOINS popularité du membre 1 MOINS popularité du membre 2 et toutes les variantes possibles.

Pour chaque couple, je fais ce calcul, et je garde le couple pour lequel ce calcul donne la valeur la plus grande.

Puis je boucle, en supprimant ces 2 personnes.
Au passage, je supprime de ma '''base de données''' tout ce qui concerne ces 2 personnes avec la fonction 'nettoie'
Et on continue donc avec environ 95 votes pour chaque participant, au lieu des 111 du début.

Je ne sais pas si ce 'nettoyage' est vraiment justifié, mais il simplifiait la programmation.

[Doubrovski]

Merci pour tes conseils, j'ai fini par comprendre.
J'ai lancé l'app en attendant de finir l'algorithme de classement, mais je viens de finir ce soir.
Entre temps il y a eu 2049 swipes, donc on peut miser sur 3000 ou un peu plus en fin de semaine.
J'ai choisi (x+0.6) / (y+1) pour calculer la popularité, même si ça privilégie beaucoup ceux qui n'ont pas de votes négatifs. Dans un sens, c'est normal, personne n'a envie de voter "non" pour ces couples, et donc ils se retrouvent ensemble.
La fille qui m'a aidé tout le weekend à faire le design obtient avec moi le meilleur score, donc l'algo me semble plutôt bon
Un autre collègue mal aimé se voit casé avec le choix "le moins pire", on évite les damas.
Effet pervers : l'indice de popularité des personnes n'est pas vraiment représentatif. Car on a envie de "préserver" certaines personnes des mauvais binômes, et donc ça baisse leur indice de popularité.
Moi par exemple ils ont tendance à ne pas me préserver pour me faire payer l'affront de les mettre en concurrence, et donc ça augmente ma popularité.
Merci encore !

[lyceen95]

Merci, je me suis aussi amusé avec ce challenge.