Eine gewichtete Version von random.choice

Question

Ich musste eine gewichtete Version von random.choice schreiben (jedes Element in der Liste hat eine unterschiedliche Wahrscheinlichkeit ausgewählt zu werden). Das ist, was ich erstellt habe:

def weightedChoice(choices):
    """Wie random.choice, aber jedes Element kann eine andere Chance haben, ausgewählt zu werden.

    choices kann eine beliebige Iterable sein, die Iterable mit zwei Elementen enthält.
    Technisch gesehen können sie mehr als zwei Elemente haben, der Rest wird einfach ignoriert. Das erste Element ist das ausgewählte Element, das zweite Element ist
    sein Gewicht. Die Gewichte können beliebige numerische Werte sein, was zählt sind die
    relativen Unterschiede zwischen ihnen.
    """
    space = {}
    current = 0
    for choice, weight in choices:
        if weight > 0:
            space[current] = choice
            current += weight
    rand = random.uniform(0, current)
    for key in sorted(space.keys() + [current]):
        if rand < key:
            return choice
        choice = space[key]
    return None

Diese Funktion scheint mir übermäßig komplex und hässlich zu sein. Ich hoffe, dass alle hier einige Vorschläge zur Verbesserung oder alternative Möglichkeiten bieten können. Effizienz ist für mich nicht so wichtig wie die Leserlichkeit und die Sauberkeit des Codes.

Answer 1

Eine weitere Möglichkeit, dies zu tun, ist davon auszugehen, dass wir Gewichte am gleichen Index wie die Elemente im Element-Array haben.

import numpy as np
weights = [0.1, 0.3, 0.5] # Gewichte für das Element an Index 0,1,2
# Summe der Gewichte sollte <=1 sein, Sie können auch jedes Gewicht durch die Summe aller Gewichte teilen, um es auf die <=1-Beschränkung zu standardisieren.
trials = 1 # Anzahl der Versuche
num_item = 1 # Anzahl der ausgewählten Elemente in jedem Versuch
selected_item_arr = np.random.multinomial(num_item, weights, trials)
# gibt an, wie oft ein Element an einem bestimmten Index ausgewählt wurde
# dies setzt eine Auswahl mit Wiederholung voraus
# ein mögliches Ergebnis
# selected_item_arr
# array([[0, 0, 1]])
# sagen wir, wenn trials = 5, könnte das mögliche Ergebnis sein 
# selected_item_arr
# array([[1, 0, 0],
#   [0, 0, 1],
#   [0, 0, 1],
#   [0, 1, 0],
#   [0, 0, 1]])

Nehmen wir jetzt an, dass wir in einem Versuch 3 Elemente auswählen müssen. Sie können davon ausgehen, dass drei Kugeln R, G, B in großer Menge im Verhältnis ihrer Gewichte gemäß dem Gewichtsarray vorhanden sind, das folgende könnten mögliche Ergebnisse sein:

num_item = 3
trials = 1
selected_item_arr = np.random.multinomial(num_item, weights, trials)
# selected_item_arr könnte ein Ergebnis wie folgt liefern:
# array([[1, 0, 2]])

Sie können auch die Anzahl der ausgewählten Elemente als Anzahl der binomialen/multinomialen Versuche innerhalb eines Sets betrachten. Daher kann das obige Beispiel immer noch funktionieren als

num_binomial_trial = 5
weights = [0.1,0.9] # sagen wir, ein unfaire Münze-Gewicht für K/K
num_experiment_set = 1
selected_item_arr = np.random.multinomial(num_binomial_trial, weights, num_experiment_set)
# mögliches Ergebnis
# selected_item_arr
# array([[1, 4]])
# d.h. K kam 1 Mal und K kam 4 Mal in 5 binomialen Versuchen. Und ein Set enthält 5 binomiale Versuche.

Answer 2

Bei Machine Learning muss ich nicht nur zufällig ein Element aus einem Array auswählen, sondern auch sicherstellen, dass das Element in einer vollen Runde eine stabile Anzahl von Malen ausgewählt wird.

Die Idee besteht darin, jeden Index N-mal gemäß seiner Auftretenswahrscheinlichkeit zu duplizieren. Die minimale Chance beträgt 0,001, sodass, wenn es ein Element mit einer Wahrscheinlichkeit von 0,001 gibt, ein Index mit einer Wahrscheinlichkeit von 1,0 1000 Mal dupliziert wird.

Daher habe ich eine Choicer-Klasse erstellt. Sie unterstützt auch verschachtelte Choicer.

from __future__ import annotations

from typing import Any, Sequence

import numpy as np

class Choicer:

    def __init__(self, items : Sequence[ Any|Choicer ],
                       probs : Sequence[int|float]|np.ndarray ):
        """ probs   [ 0.001 .. 1.0 ] """
        self._items = items
        self._probs = probs = np.array(probs, np.float32).clip(0.001, 1.0)

        if len(probs) != len(items):
            raise ValueError('muss len(probs) == len(items)')

        # wie oft jedes Element auftreten wird
        rates = (probs/probs.min()).astype(np.int32)

        # Basis-Indexsequenz, z.B. Choicer(['a', 'b', 'c'], [1,1,0.5]) , idxs_base == [0,0,1,1,2]
        self._idxs_base = np.concatenate([np.full( (x,), i, dtype=np.uint32) for i,x in enumerate(rates)], 0)

        self._idxs = None
        self._idx_counter = 0

    @property
    def items(self) -> Sequence[ Any|Choicer ]: return self._items
    @property
    def probs(self) -> np.ndarray: return self._probs

    def pick(self, count : int) -> Sequence[Any]:
        """pick `count` items"""
        out = []
        if len(self._items) != 0:
            while len(out) < count:
                if self._idx_counter == 0:
                    self._idxs = self._idxs_base.copy()
                    np.random.shuffle(self._idxs)
                    self._idx_counter = len(self._idxs)

                self._idx_counter -= 1
                idx = self._idxs[self._idx_counter]

                item = self._items[idx]
                if isinstance(item, Choicer):
                    item = item.pick(1)[0]

                out.append(item)
        return out

Beispiel:

c = Choicer(['a', 'b', 'c'], [1,1,0.5])

print( c.pick(5) ) # ['c', 'a', 'b', 'a', 'b']
print( c.pick(5) ) # ['a', 'a', 'b', 'b', 'c']
print( c.pick(5) ) # ['a', 'c', 'a', 'b', 'b']

Verschachteltes Choicer-Beispiel:

c = Choicer(['a', 
             'b', 
             Choicer(['c0','c1','c2'], [1,1,1]),
             ],            
             [1,1,0.5])

print( c.pick(15) )
# ['b', 'a', 'b', 'c0', 'a', 'b', 'a', 'b', 'c1', 'a', 'b', 'c2', 'a', 'a', 'b']

Answer 3

Wenn Sie nicht im Voraus festlegen, wie viele Elemente Sie auswählen möchten (also keine Angabe wie k=10 machen) und nur Wahrscheinlichkeiten haben, können Sie das Folgende tun. Beachten Sie, dass Ihre Wahrscheinlichkeiten nicht auf 1 addiert werden müssen; sie können unabhängig voneinander sein:

soup_items = ['pepper', 'onion', 'tomato', 'celery'] 
items_probability = [0.2, 0.3, 0.9, 0.1]

selected_items = [item for item,p in zip(soup_items,items_probability) if random.random()>>['pepper','tomato']

Answer 4

Geben Sie random.choice() eine vorgewichtete Liste:

Lösung & Test:

import random

optionen = ['a', 'b', 'c', 'd']
gewichte = [1, 2, 5, 2]

gewichtete_optionen = [[opt]*wgt for opt, wgt in zip(optionen, gewichte)]
gewichtete_optionen = [opt for sublist in gewichtete_optionen for opt in sublist]
print(gewichtete_optionen)

# test

ergebnisse = {c: 0 for c in optionen}
for x in range(10000):
    ergebnisse[random.choice(gewichtete_optionen)] += 1

for opt, wgt in zip(optionen, gewichte):
    wgt_r = ergebnisse[opt] / 10000 * sum(gewichte)
    print(opt, ergebnisse[opt], wgt, wgt_r)

Ergebnis:

['a', 'b', 'b', 'c', 'c', 'c', 'c', 'c', 'd', 'd']
a 1025 1 1.025
b 1948 2 1.948
c 5019 5 5.019
d 2008 2 2.008

Answer 5

Ich mochte die Syntax von keinem davon. Ich wollte wirklich nur angeben, was die Elemente waren und wie das Gewicht von jedem war. Mir ist klar, dass ich random.choices hätte verwenden können, aber stattdessen habe ich schnell die folgende Klasse geschrieben.

import random, string
from numpy import cumsum

class randomChoiceWithProportions:
    '''
    Akzeptiert ein Wörterbuch von Entscheidungen als Schlüssel und Gewichten als Werte. Beispiel, wenn Sie einen unfairen Würfel möchten:

    choiceWeightDic = {"1":0.16666666666666666, "2": 0.16666666666666666, "3": 0.16666666666666666
    , "4": 0.16666666666666666, "5": .06666666666666666, "6": 0.26666666666666666}
    dice = randomChoiceWithProportions(choiceWeightDic)

    samples = []
    for i in range(100000):
        samples.append(dice.sample())

    # Sollte nahe bei .26666 sein
    samples.count("6")/len(samples)

    # Sollte nahe bei .16666 sein
    samples.count("1")/len(samples)
    '''
    def __init__(self, choiceWeightDic):
        self.choiceWeightDic = choiceWeightDic
        weightSum = sum(self.choiceWeightDic.values())
        assert weightSum == 1, 'Gewichte summieren sich zu ' + str(weightSum) + ', nicht 1.'
        self.valWeightDict = self._compute_valWeights()

    def _compute_valWeights(self):
        valWeights = list(cumsum(list(self.choiceWeightDic.values())))
        valWeightDict = dict(zip(list(self.choiceWeightDic.keys()), valWeights))
        return valWeightDict

    def sample(self):
        num = random.uniform(0,1)
        for key, val in self.valWeightDict.items():
            if val >= num:
                return key