arrays - sort - Selección aleatoria ponderada de matriz
shuffle array javascript (12)
Me gustaría seleccionar aleatoriamente un elemento de una matriz, pero cada elemento tiene una probabilidad de selección conocida.
Todas las posibilidades juntas (dentro de la matriz) suman a 1.
¿Qué algoritmo sugerirías como el más rápido y el más adecuado para cálculos enormes?
Ejemplo:
id => chance
array[
0 => 0.8
1 => 0.2
]
para este pseudocódigo, el algoritmo en cuestión debería devolver cuatro elementos estadísticamente en cuatro identificadores en id 0 para un elemento en id 1 .
Calcule la función de densidad acumulativa discreta (CDF) de su lista, o en términos simples, la matriz de sumas acumulativas de los pesos. Luego genere un número aleatorio en el rango entre 0 y la suma de todos los pesos (podría ser 1 en su caso), haga una búsqueda binaria para encontrar este número aleatorio en su matriz CDF discreta y obtenga el valor correspondiente a esta entrada; esto es su número aleatorio ponderado.
El algoritmo es directo
rand_no = rand(0,1)
for each element in array
if(rand_num < element.probablity)
select and break
rand_num = rand_num - element.probability
Este es un código PHP que utilicé en producción:
/**
* @return /App/Models/CdnServer
*/
protected function selectWeightedServer(Collection $servers)
{
if ($servers->count() == 1) {
return $servers->first();
}
$totalWeight = 0;
foreach ($servers as $server) {
$totalWeight += $server->getWeight();
}
// Select a random server using weighted choice
$randWeight = mt_rand(1, $totalWeight);
$accWeight = 0;
foreach ($servers as $server) {
$accWeight += $server->getWeight();
if ($accWeight >= $randWeight) {
return $server;
}
}
}
Esto se puede hacer en O (1) tiempo esperado por muestra de la siguiente manera.
Calcule el CDF F (i) para cada elemento i como la suma de probabilidades menores o iguales a i.
Defina el rango r (i) de un elemento i como el intervalo [F (i - 1), F (i)].
Para cada intervalo [(i - 1) / n, i / n], cree un depósito que consista en la lista de los elementos cuyo rango se solapa con el intervalo. Esto toma O (n) tiempo en total para la matriz completa, siempre que sea razonablemente cuidadoso.
Cuando muestreas aleatoriamente la matriz, simplemente calcula en qué depósito está el número aleatorio y lo compara con cada elemento de la lista hasta que encuentre el intervalo que lo contiene.
El costo de una muestra es O (la longitud esperada de una lista elegida al azar) <= 2.
He encontrado que este artículo es el más útil para comprender este problema por completo. Esta pregunta de también puede ser lo que estás buscando.
Creo que la solución óptima es usar el Método Alias (wikipedia) . Requiere O (n) tiempo para inicializar, O (1) tiempo para hacer una selección y O (n) memoria.
Aquí está el algoritmo para generar el resultado de hacer rodar un dado ponderado en n (de aquí es trivial seleccionar un elemento de un conjunto de longitud y n ) como tomar de este artículo . El autor asume que tienes funciones para lanzar un dado justo ( floor(random() * n) ) y lanzar una moneda sesgada ( random() < p ).
Algoritmo: Método Alias de Vose
Inicialización:
- Crear matrices Alias y Prob , cada una de tamaño n .
- Crea dos listas de trabajo, pequeña y grande .
- Multiplica cada probabilidad por n .
- Para cada probabilidad escalada p i :
- Si p i <1 , agregue i a Small .
- De lo contrario ( p i ≥ 1 ), agregue i a Grande .
- Mientras que Small y Large no están vacíos: ( Large se puede vaciar primero)
- Retire el primer elemento de Pequeño ; llámalo l .
- Retire el primer elemento de Grande ; llámalo g .
- Set Prob [l] = p l .
- Establecer Alias [l] = g .
- Establecer pg: = (p g + p l ) -1 . (Esta es una opción más numéricamente estable).
- Si p g <1 , agregue g a Small .
- De lo contrario ( p g ≥ 1 ), agregue g a Grande .
- Mientras Large no está vacío:
- Retire el primer elemento de Grande ; llámalo g .
- Set Prob [g] = 1 .
- Mientras que Small no está vacío: esto solo es posible debido a la inestabilidad numérica.
- Retire el primer elemento de Pequeño ; llámalo l .
- Set Prob [l] = 1 .
Generacion:
- Genera una tirada justa de un dado n -dado; llamar al lado i .
- Lanza una moneda sesgada que sale cara con la probabilidad Prob [i] .
- Si la moneda sale "cara", devuelve i .
- De lo contrario, devuelva Alias [i] .
Me imagino que los números mayores o iguales que 0.8 pero menores que 1.0 seleccionan el tercer elemento.
En otros términos:
x es un número aleatorio entre 0 y 1
si 0.0> = x <0.2: elemento 1
si 0.2> = x <0.8: elemento 2
si 0.8> = x <1.0: elemento 3
Otro ejemplo de Ruby:
def weighted_rand(weights = {})
raise ''Probabilities must sum up to 1'' unless weights.values.inject(&:+) == 1.0
u = 0.0
ranges = Hash[weights.map{ |v, p| [u += p, v] }]
u = rand
ranges.find{ |p, _| p > u }.last
end
Cómo utilizar:
weights = {''a'' => 0.4, ''b'' => 0.4, ''c'' => 0.2}
weighted_rand weights
Que esperar:
d = 1000.times.map{ weighted_rand weights }
d.count(''a'') # 396
d.count(''b'') # 406
d.count(''c'') # 198
Si la matriz es pequeña, le daría a la matriz una longitud de, en este caso, cinco y asignar los valores según corresponda:
array[
0 => 0
1 => 0
2 => 0
3 => 0
4 => 1
]
Solución Ruby usando la gema pickup :
require ''pickup''
chances = {0=>80, 1=>20}
picker = Pickup.new(chances)
Ejemplo:
5.times.collect {
picker.pick(5)
}
dio salida:
[[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 1]]
Un ejemplo en ruby
#each element is associated with its probability
a = {1 => 0.25 ,2 => 0.5 ,3 => 0.2, 4 => 0.05}
#at some point, convert to ccumulative probability
acc = 0
a.each { |e,w| a[e] = acc+=w }
#to select an element, pick a random between 0 and 1 and find the first
#cummulative probability that''s greater than the random number
r = rand
selected = a.find{ |e,w| w>r }
p selected[0]
Voy a mejorar la respuesta de .
Básicamente, se crea una gran matriz donde la cantidad de veces que aparece un elemento es proporcional al peso.
Tiene algunos inconvenientes.
- El peso puede no ser un número entero. Imagine que el elemento 1 tiene probabilidad de pi y el elemento 2 tiene probabilidad de 1-pi. ¿Cómo divides eso? O imagine si hay cientos de tales elementos.
- La matriz creada puede ser muy grande. Imagine que si el multiplicador menos común es 1 millón, entonces necesitaremos una matriz de 1 millón de elementos en la matriz que queremos elegir.
Para contrarrestar eso, esto es lo que haces.
Cree dicha matriz, pero solo inserte un elemento al azar. La probabilidad de que se inserte un elemento es proporcional al peso.
Luego selecciona un elemento aleatorio de lo habitual.
Entonces, si hay 3 elementos con varios pesos, simplemente elige un elemento de una matriz de 1-3 elementos.
Pueden surgir problemas si el elemento construido está vacío. Es que simplemente sucede que no aparecen elementos en la matriz porque sus dados ruedan de manera diferente.
En cuyo caso, propongo que la probabilidad de insertar un elemento es p (insertado) = wi / wmax.
De esta forma, se insertará un elemento, a saber, el que tiene la probabilidad más alta. Los otros elementos se insertarán por la probabilidad relativa.
Digamos que tenemos 2 objetos.
el elemento 1 aparece .20% del tiempo. el elemento 2 aparece un .40% del tiempo y tiene la probabilidad más alta.
En thearray, el elemento 2 aparecerá todo el tiempo. El elemento 1 aparecerá la mitad del tiempo.
Así que el elemento 2 se llamará 2 veces más que el elemento 1. Por general, todos los demás elementos se denominarán proporcionales a su peso. Además, la suma de todas sus probabilidades es 1 porque la matriz siempre tendrá al menos 1 elemento.
el truco podría ser muestrear una matriz auxiliar con elementos repetidos que reflejan la probabilidad
Teniendo en cuenta los elementos asociados con su probabilidad, como porcentaje:
h = {1 => 0.5, 2 => 0.3, 3 => 0.05, 4 => 0.05 }
auxiliary_array = h.inject([]){|memo,(k,v)| memo += Array.new((100*v).to_i,k) }
ruby-1.9.3-p194 > auxiliary_array
=> [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4]
auxiliary_array.sample
si quieres ser lo más genérico posible, debes calcular el multiplicador según la cantidad máxima de dígitos fraccionarios y usarlo en lugar de 100:
m = 10**h.values.collect{|e| e.to_s.split(".").last.size }.max