Sélection aléatoire pondérée d'une ligne

[Babcool]

Bonjour

Je me demandais s'il était possible de réaliser une sélection aléatoire en pondérant les chances de sélections selon une expression.

J'ai trouvé qu'il était possible de choisir aléatoire une ligne avec :

Code :

1
2
3
4
5
 
SELECT col
FROM tab
ORDER BY random()
LIMIT 1;

Mais la sélection est alors strictement aléatoire. J'aurais aimé pondérer les chances de sélection de chaque ligne. Une idée?

Merci d'avance...

[CinePhil]

Quelles seraient les règles de cette pondération ?

[Babcool]

En appellant score la valeur de pondération, la probabilité de sélections d'une ligne sera son score / somme des scores.

La manière habituelle de procéder (mais dans du code, pas dans le cadre d'un accès à une base) est de normaliser la somme des scores, puis de générer un nombre aléatoire entre 0 et 1 et de réaliser le cumul des scores jusqu'au moment ou l'on atteint le nombre aléatoire tiré. Je ne sais pas si cela peut être réalisé en SQL ...

[CinePhil]

Et où est stocké ce score ? Une colonne de la table ?

[Babcool]

Soit c'est une colonne de la table, soit une expression composée de plusieurs colonnes (si possible, mais une colonne de la table me convient aussi).

[CinePhil]

Si je comprends bien, ce que tu souhaites, c'est ne garder que A lignes prises aléatoirement parmi les P premières classées par score ?

[Babcool]

Nan, pas exactement. C'est peut-être cette solution que je garderais au final, mais mon objectif est de ne sélectionner qu'une ligne pour l'instant.

Je vais prendre un petit exemple pour expliquer un peu mieux ma situation:

J'ai 5 entrées
id score
1 5
2 3
3 2
4 3
5 4

On a somme des scores = 17
Je voudrais faire un tirage aléatoire avec la loi de proba suivante
P(1) = 5/ 17
P(2) = 3 / 17
P(3) = 2 / 17
...

En général, dans mon code, quand je dois faire une telle sélection, je fais ainsi :
1. Je définis un score normalisé :
S_n(1) = 5/17
S_n(2) = 3/17
...

2. Je tire un nombre aléatoire en 0 et 1, par exemple 9/17

3. Je réalise un cumul des scores jusqu'a atteindre mon nombre
C_s(1) = 5/17
C_s(2) = 7/17
C_s(3) = 10/17
Je m'arrête dès que le nombre aléatoire tiré est atteint, la ligne sélectionnée serait alors ici la 3.

Il est possible de trier les lignes en ordre de score décroissant pour optimiser la dernière étape, mais ce n'est pas une priorité pour l'instant.

Mon objectif serait de réaliser ce tirage aléatoire directement dans la bdd plutot que de charger de grandes quantitiés d'objets pour réaliser le tirage ensuite en local...

[CinePhil]

En une requête, tu peux facilement obtenir la probabilité P pour chaque id :

Code :

1
2
3
4
5
6
SELECT id, score, 
    score / (
        SELECT SUM(score)
        FROM la_table
    ) AS P
FROM la_table

Ensuite tu peux obtenir l'écart des probabilités de la table par rapport à une valeur donnée et il suffit de trier ces écarts dans l'ordre et de ne conserver que la première ligne résultat :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
SELECT id,
    ABS(
        valeur_donnee - (
            score / (
                SELECT SUM(score)
                FROM la_table
            )
        )
    ) AS ecart
FROM la_table
ORDER BY 
    ABS(
        valeur_donnee - (
            score / (
                SELECT SUM(score)
                FROM la_table
            )
        )
    ) AS ecart
LIMIT 1

[Babcool]

Effectivement, il y a une bonne piste ici. Par contre, il faut modifier un peu la première requete que tu propose. En effet, au lieu de stocker le score pondéré, je peux stocker le cumul de tous les scores supérieurs ou égal au score considéré. Pour cela, au lieu de diviser le score de la ligne par la somme des scores, on diviser la somme des scores supérieurs par la somme de tous les scores.

Par contre, ça va douiller en cout de calcul, sauf si le moteur arrive a le gérer très bien (genre, faire une seule fois la somme, et entre chaque ajout, faire la vérification). Car j'ai l'impression que je vais être en n^2 (pour chaque ligne, je réalise la somme des scores supérieurs ou égaux a cette ligne). J'essayerai de limiter l'amplitude de la sélection initiale dans ce cas...

Je peux aussi me passer du abs ensuite, pour ne prendre que la ligne qui a le cumul des scores minimal tout en étant supérieur au nombre tiré au hasard.

Je viendrais poster la requete dès que ca sera fait

[CinePhil]

Envoyé par Babcool

Effectivement, il y a une bonne piste ici. Par contre, il faut modifier un peu la première requete que tu propose. En effet, au lieu de stocker le score pondéré, je peux stocker le cumul de tous les scores supérieurs ou égal au score considéré.

Tu fais comme tu veux, je suis juste parti de ton exemple.

Pour cela, au lieu de diviser le score de la ligne par la somme des scores, on diviser la somme des scores supérieurs par la somme de tous les scores.

Euh... si tu le dis...

Par contre, ça va douiller en cout de calcul, sauf si le moteur arrive a le gérer très bien (genre, faire une seule fois la somme, et entre chaque ajout, faire la vérification). Car j'ai l'impression que je vais être en n^2 (pour chaque ligne, je réalise la somme des scores supérieurs ou égaux a cette ligne). J'essayerai de limiter l'amplitude de la sélection initiale dans ce cas...

Tu réfléchis en développeur qui boucle sur un tableau alors qu'un SGBD travaille sur une logique ensembliste.

Le SGBD va se débrouiller tout seul pour optimiser tout ça :
- Calcul de la somme des scores en une seule fois (la petite requête dans le SELECT) et mémorisation du résultat ;
- Calcul de l'écart pour chaque ligne en utilisant le résultat mémorisé (donc il ne fait pas la petite requête à chaque ligne) ;
- Tri de l'ensemble des lignes résultat.

Le calcul n'est pas compliqué, je pense qu'il peut faire ça très vite, même avec quelques centaines de milliers de lignes.

Le seul truc qu'il faut peut être faire et que je n'ai pas inclus dans ma requête, c'est du trasntypage en FLOAT pour que la division donne bien 0,x et ne soit pas arrondie à 0 ou à 1.
Je n'ai pas Postgresql sous la main pour vérifier.

Bonne chance !