Seleziona a caso dalla lista con probabilità aumentate

2

Ho una lista di entità. Ogni entità contiene un numero che contiene quante volte l'entità è stata selezionata. Ho bisogno di fare una funzione che seleziona n (diciamo il 25%) delle entità, a caso. Quello che voglio fare è aumentare le quote per le entità che sono state selezionate meno volte. Supponiamo che dopo 5 corse le volte che le entità siano state selezionate possono essere ovunque da 0 a 5. Ma non voglio avere una tale diffusione. Voglio che i tempi in cui le entità siano selezionate più o meno siano uguali.

Come posso scrivere una funzione che aumenta le probabilità per le entità che non sono state selezionate così spesso come altre?

Un modo in cui potrei pensare è di creare una lista che ha più occorrenze di entità selezionate minori, aumentando la possibilità che il randomizzatore selezioni quell'entità. Qualche suggerimento, consigli, idee?

Modifica Wow. Chiuso come non una vera domanda e riaperto di nuovo. Per non essere una vera domanda ha ottenuto molte risposte e commenti. Grazie per quello. Ho ottenuto esattamente quello che volevo da loro. Ho delle buone idee per allenarmi e testare.

    
posta Jeroen 24.01.2013 - 20:42
fonte

6 risposte

4

Ordina per intervallo casuale

È possibile ordinare gli elementi in base a un'espressione, in cui viene selezionato un numero casuale tra gli elementi numero di visualizzazioni corrente e il numero massimo di visualizzazioni. Ciò garantisce che agli oggetti con un elevato numero di visualizzazioni sia assegnato un numero casuale di dimensioni elevate. Mentre gli oggetti con un basso numero di visualizzazioni hanno più probabilità di essere randomizzati.

Ordina l'elenco in base alla seguente espressione random(item.views,max_viewx+1)

Ho dato il max_views+1 in modo che un nuovo elenco di elementi con% viste di% co_de continui a produrre un ordinamento casuale.

Testato tramite SQL

Penso che questo sia qualcosa che un giorno potrei usare su un blog. Quindi ecco un tentativo di verificare questo approccio come una tabella MySQL.

Crea innanzitutto una tabella di base 0 .

CREATE  TABLE 'articles' (
  'id' INT UNSIGNED NOT NULL AUTO_INCREMENT ,
  'title' VARCHAR(45) NOT NULL ,
  'views' INT NOT NULL DEFAULT 0 ,
  PRIMARY KEY ('id') );

Ora inserisci alcuni articoli con diversi contatori di vista.

INSERT INTO 'articles' ('title', 'views') VALUES ('Home Page', 20);
INSERT INTO 'articles' ('title', 'views') VALUES ('Portfolio', 10);
INSERT INTO 'articles' ('title', 'views') VALUES ('Contact Us', 5);
INSERT INTO 'articles' ('title', 'views') VALUES ('Product - ABC', 2);
INSERT INTO 'articles' ('title', 'views') VALUES ('Product - SHR', 1);
INSERT INTO 'articles' ('title', 'views') VALUES ('Product - DBS', 0);
INSERT INTO 'articles' ('title', 'views') VALUES ('Product - ZZZ', 100);

Ora posso ordinare dalla colonna articles per mettere views in basso, ma vogliamo che questo sia casuale.

SELECT * FROM 'articles'
    ORDER BY 'views'+(RAND()*(100-'views'+1));

Questo funziona per me, posizionando Product - ZZZ nella parte inferiore del 100% delle volte, ma gli elementi a bassa vista hanno più probabilità di essere ordinati più in alto nell'elenco.

SELECT * FROM 'articles'
    ORDER BY 'views'+(RAND()*(100-'views'+25));

Aggiungendo Product - ZZZ a +25 , quindi sono in grado di aumentare ORDER BY leggermente più in alto nell'elenco e rendere più casuali gli altri elementi. Quindi puoi controllare l'effetto randomizzante.

    
risposta data 24.01.2013 - 22:02
fonte
1

Innanzitutto, è importante sottolineare che se la tua funzione di selezione è veramente casuale (o anche in modo pseudocasuale in modo convincente), tutti gli elementi avranno lo stesso numero di selezioni a lungo termine .

Posso pensare a un certo numero di modi per realizzare ciò che vuoi. Eccone uno:

  • Assegna ad ogni articolo un peso iniziale di, per esempio, 1.0.
  • Disporre tutti gli elementi in un elenco. Ordina l'elenco in base ai pesi degli articoli.
  • Quando vuoi scegliere un nuovo oggetto, usa una funzione casuale per scegliere un numero tra 0 e la somma dei pesi di tutti gli oggetti. Successivamente, aggiungi i pesi degli articoli a partire dall'inizio della lista fino a raggiungere il numero che hai appena scelto. Scegli quell'elemento.
  • Infine, dovrai regolare i pesi e assicurarti che l'elenco rimanga ordinato (o riordinarlo di nuovo o adattarlo in modo da mantenere l'ordinamento).

Come si regolano i pesi avrà un grande impatto sul proprio algoritmo, ma suggerirei qualcosa come: sottrarre 1.0 dal peso dell'oggetto scelto e aggiungere 1 / (n-1) ai pesi di tutti gli altri elementi.

    
risposta data 24.01.2013 - 21:24
fonte
1

Le volte che le entità vengono selezionate avranno una media uguale a ... dato un tempo e una selezione sufficiente. C'è davvero la possibilità che un'entità possa essere fortunata e vincere i primi 5 giochi. Ma questo è raro. In generale, direi che non devi preoccuparti di questo.

Ma se vuoi che sia impossibile, basta escludere qualsiasi entità dal lotto che ha più di una deviazione standard delle vincite. A numeri bassi, questo escluderebbe chiunque abbia vinto una singola scommessa.

Nota, questo è per un gioco, i giocatori sono particolarmente interessati a quando le probabilità sono state manomesse. Se qualcuno non può mai vincere due volte di seguito, lo noterà.

    
risposta data 24.01.2013 - 21:27
fonte
1

Hai le voci A, B, C, D ed E che sono state selezionate 3, 1, 1, 0, 0 volte.

Il massimo di questo set è 3. Sottrarre il valore correntemente selezionato dal massimo + 1 (una voce che ha i valori massimi dovrebbe avere qualche possibilità di vincere ancora, sebbene uno come quella voce avrà solo un rappresentante nel prossima lotteria).

Ora hai l'associazione di: A = > 1, B = > 3, C = > 3, D = > 4, E = > 4.

Costruisci un array basato su questo, ad esempio: A,B,B,B,C,C,C,D,D,D,D,E,E,E,E e seleziona un vincitore casuale. Le voci che hanno vinto il minor numero di volte in passato avranno maggiori possibilità di vincere questa volta.

La tua domanda può essere interpretata come "seleziona n delle voci" con o senza sostituzione. Se è senza sostituzione, quindi ricalcalo, rimuovendo il vincitore dal turno precedente fino a quando non selezioni il numero richiesto di vincitori.

Variazioni:

  • Invece di usare il massimo del set, si potrebbe invece usare la somma del set.
  • Cambia il valore di N in max + N valore per pareggiare la distribuzione

Suggerirei di eseguire una serie di simulazioni Monte-carlo sul set di dati per identificare quali valori funzionano meglio per la tua situazione.

    
risposta data 24.01.2013 - 22:05
fonte
0

Se vuoi limitare la differenza di occorrenze a un massimo di 1:

  1. Mescola l'elenco delle entità (usando un rimescolamento di Fisher-Yates)
  2. Scegli i tuoi valori casuali secondo l'ordine dell'elenco mescolato
  3. Una volta raggiunta la fine dell'elenco mescolato, vai a 1

Puoi anche consentire maggiori differenze nelle occorrenze aggiungendo ogni entità n -times all'elenco quando desideri una differenza massima di n .

    
risposta data 24.01.2013 - 21:23
fonte
0

Una volta ho implementato qualcosa del genere:

Assegna inizialmente a ogni oggetto della tua piscina lo stesso numero di probabilità. Quando si effettua una scelta casuale, sommare il numero totale di possibilità e quindi scorrere l'elenco per trovare quale è stato ottenuto. (Sì, è O (n) piuttosto che O (1). Avrai bisogno di qualcosa di più divertente se la tua lista è gigantesca o non in memoria.)

Quando un oggetto viene selezionato, ne rimuovi una possibilità.

Quando hai selezionato tutti gli elementi che l'elenco contiene, prova a aggiungerne uno per ogni possibilità.

(Non avevo l'ultimo passaggio perché volevo che i pick selezionati andassero via e non tornassero più.)

    
risposta data 24.01.2013 - 21:37
fonte

Leggi altre domande sui tag