Saltar al contenido

Muestra aleatoria ponderada sin reemplazo en python

Deseamos enseñarte la mejor solución que hemos encontrado en internet. Esperamos que te resulte de mucha utilidad y si quieres comentarnos algo que nos pueda ayudar a perfeccionar nuestra información hazlo con total libertad.

Solución:

Puedes usar np.random.choice con replace=False como sigue:

np.random.choice(vec,size,replace=False, p=P)

donde vec es su población y P es el vector de peso.

Por ejemplo:

import numpy as np
vec=[1,2,3]
P=[0.5,0.2,0.3]
np.random.choice(vec,size=2,replace=False, p=P)

Solución integrada

Como sugirió Miriam Farber, puede usar la solución integrada de numpy:

np.random.choice(vec,size,replace=False, p=P)

Equivalente puro de Python

Lo que sigue está cerca de lo que entumecido hace internamente. Por supuesto, utiliza matrices numpy y numpy.random.choices():

from random import choices

def weighted_sample_without_replacement(population, weights, k=1):
    weights = list(weights)
    positions = range(len(population))
    indices = []
    while True:
        needed = k - len(indices)
        if not needed:
            break
        for i in choices(positions, weights, k=needed):
            if weights[i]:
                weights[i] = 0.0
                indices.append(i)
    return [population[i] for i in indices]

Problema relacionado: Selección cuando los elementos se pueden repetir

Esto a veces se llama un urna problema. Por ejemplo, dada una urna con 10 bolas rojas, 4 bolas blancas y 18 bolas verdes, elige nueve bolas sin reemplazo.

para hacerlo con entumecidogenere las selecciones únicas del recuento total de la población con muestra(). Luego, divida en dos los pesos acumulativos para obtener los índices de población.

import numpy as np
from random import sample

population = np.array(['red', 'blue', 'green'])
counts = np.array([10, 4, 18])
k = 9

cum_counts = np.add.accumulate(counts)
total = cum_counts[-1]
selections = sample(range(total), k=k)
indices = np.searchsorted(cum_counts, selections, side='right')
result = population[indices]

Para hacer esto sin *numpy’, se puede implementar el mismo enfoque con bisecar() y acumular() de la biblioteca estándar:

from random import sample
from bisect import bisect
from itertools import accumulate

population = ['red', 'blue', 'green']
weights = [10, 4, 18]
k = 9

cum_weights = list(accumulate(weights))
total = cum_weights.pop()
selections = sample(range(total), k=k)
indices = [bisect(cum_weights, s) for s in selections]
result = [population[i] for i in indices]

numpy es probablemente la mejor opción. Pero aquí hay otra solución de Python puro para muestras ponderadas sin reemplazo.

Hay un par de formas de definir el propósito de los parámetros para population y weights. population se puede definir para representar la población total de artículos, y weights una lista de sesgos que influyen en la selección. Por ejemplo, en una simulación de carrera de caballos, population podrían ser los caballos – cada uno único con un nombre, y weights sus calificaciones de desempeño. Las siguientes funciones siguen este modelo.

from random import random
from bisect import bisect_left
from itertools import accumulate

def wsample(population, weights, k=1):
    wts   = list(weights)
    sampl = []
    rnums = [random() for _ in range(k)]
    for r in rnums:
        acm_wts = list(accumulate(wts))
        total   = acm_wts[-1]
        i       = bisect_left(acm_wts, total * r)
        p       = population[i]
        wts[i]  = 0
        sampl.append(p)
    return sampl

Los individuos seleccionados se eliminan efectivamente de otras selecciones al establecer su peso en 0 y volver a calcular los pesos acumulados. Si usa esto, asegúrese k <= len(population).

La primera versión proporciona un buen punto de referencia para probar esta segunda versión. La siguiente versión es muy rápida en comparación con la primera.

En esta próxima versión, los pesos acumulados se calculan una vez y las colisiones en el muestreo generan reintentos. Esto tiene el efecto de eliminar rangos de las posibles selecciones, mientras que los rangos que aún no han sido tomados se agrupan en bandas relativamente proporcionadas a las otras bandas activas para mantener en juego las probabilidades correctas de selección.

Un diccionario tecleado en índices seleccionados asegura que cada miembro seleccionado sea un individuo único. los dict conserva el orden en que se agregan los elementos y los devuelve en el orden de selección.

La idea parece funcionar. Los resultados bajo prueba se comparan muy de cerca entre estas dos implementaciones.

def wsample(population, weights, k=1):
    accum = list(accumulate(weights))
    total = accum[-1]
    sampl = 
    while len(sampl) < k:
        index        = bisect_left(accum, total * random())
        sampl[index] = population[index]
    return list(sampl.values())

A pesar del hecho de que las posibilidades de bucles adicionales más de k los tiempos son altos (dependiendo de los parámetros) cada selección, la eliminación del O(n) accumulate() operación cada iteración lo compensa con creces en tiempos de ejecución más rápidos. Esto podría hacerse aún más rápido si requiriera que los pesos se acumularan previamente, pero para mi aplicación, estos deben calcularse cada ciclo una vez de todos modos.

Para usar esto, es posible que desee protegerse contra bucles infinitos si es posible en cualquier aplicación que lo use. Y posiblemente realice una verificación o dos para asegurarse de que los parámetros sean los esperados para que funcione.

En las siguientes pruebas, la población consta de 10 000 elementos con los mismos pesos correspondientes generados aleatoriamente. Esto se ejecutó en una VM alojada en una computadora de más de 10 años; cualquiera puede obtener mejores resultados que esto, pero muestra las velocidades relativas de los dos enfoques.

Primera versión:

timeit.timeit("wsample(population, weights, k=5)", globals=globals(), number=10**4)
21.74719240899867

Segunda versión:

timeit.timeit("wsample(population, weights, k=5)", globals=globals(), number=10**4)
4.32836378099455

Segunda versión modificada para pesos preacumulados:

timeit.timeit("wsample(population, acm_weights, k=5)", globals=globals(), number=10**4)
0.05602245099726133

Comentarios y valoraciones del post

Si guardas alguna cuestión o capacidad de refinar nuestro enunciado eres capaz de ejecutar un comentario y con placer lo leeremos.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *