Hace poco tuve que hacer ponderado de selección aleatoria de los elementos de una lista, con y sin reemplazo. Mientras que no son bien conocidos y buenos algoritmos para ponderado de selección, y algunos para ponderado de selección sin reemplazo (tales como las modificaciones de la resevoir algoritmo), no pude encontrar los buenos algoritmos para ponderado de selección con el reemplazo. Yo también quería evitar que los resevoir método, como yo era la selección de una fracción significativa de la lista, que es lo suficientemente pequeño como para mantener en la memoria.

¿Alguien tiene alguna sugerencia sobre el mejor enfoque en esta situación? Tengo mis propias soluciones, pero tengo la esperanza de encontrar algo más eficaz, más simple, o ambos.

ver esta pregunta stackoverflow.com/q/10164303/112100, incluso pensé que C# no de python, es muy poca código por lo que cualquier persona debe entender que
Para cualquier otra persona que tenía que mirar hacia arriba, «embalse de algoritmo» es en la Wikipedia en «embalse de muestreo«. El primer documento citado es Jeffrey Scott Vitter del «Muestreo Aleatorio con un Depósito», de ACM transactions on Software Matemático, Vol. 11, Nº 1, 01 Mar 1985, páginas 37–57.
Para ponderado sin sustitución, donde el peso significa que la probabilidad de ser elegido es proporcional al peso, a ver mi respuesta aquí: stackoverflow.com/a/27049669/262304 tenga en cuenta que algunas entradas no tiene una solución, por ejemplo, elegir 2 de {‘a’: 3, ‘b’: 1, ‘c: 1} debe producir ‘un’ 3x tan a menudo como sea b o c, pero eso es imposible.

OriginalEl autor Nick Johnson | 2008-12-09

7 Comentarios

  1. 30

    Una de las maneras más rápidas de hacer muchos con la sustitución de las muestras de una inmutable es la lista de alias de método. El núcleo de la intuición es que podemos crear un conjunto de tamaño igual contenedores para la ponderación de la lista que pueden ser indexados de manera muy eficiente a través de bits de operaciones, para evitar una búsqueda binaria. Será que, si se realiza correctamente, tendremos que almacenar solamente dos elementos de la lista original, por bin, y por lo tanto puede representar la división con un porcentaje único.

    Nos vamos a tomar el ejemplo de cinco igualmente ponderados de las opciones, (a:1, b:1, c:1, d:1, e:1)

    Para crear el alias de búsqueda:

    1. Normalizar los pesos tales que se suma a 1.0. (a:0.2 b:0.2 c:0.2 d:0.2 e:0.2) Esta es la probabilidad de elegir cada peso.

    2. Encontrar el más pequeño de potencia de 2 mayor o igual que el número de variables, y crear este número de particiones, |p|. Cada partición representa una probabilidad de masa de 1/|p|. En este caso, podemos crear 8 particiones, cada una capaz de contener 0.125.

    3. Tomar la variable con el menor peso restante, y el lugar tanto de la masa como sea posible en una partición vacía. En este ejemplo, vemos que a llena la primera partición. (p1{a|null,1.0},p2,p3,p4,p5,p6,p7,p8) con (a:0.075, b:0.2 c:0.2 d:0.2 e:0.2)

    4. Si la partición no está lleno, tomar la variable con más peso, y llenar la partición con esa variable.

    Repita los pasos 3 y 4, hasta que ninguno de los que el peso de la partición original necesita ser asignado a la lista.

    Por ejemplo, si nos encontramos con otra iteración de 3 y 4, vemos

    (p1{a|null,1.0},p2{a|b,0.6},p3,p4,p5,p6,p7,p8) con (a:0, b:0.15 c:0.2 d:0.2 e:0.2) a la izquierda para ser asignado

    En tiempo de ejecución:

    1. Obtener un U(0,1) número aleatorio, decir binario 0.001100000

    2. bitshift se lg2(p), la búsqueda de la partición de índice. Por lo tanto, lo cambiamos por 3, produciendo 001.1, o la posición 1, y por lo tanto la partición 2.

    3. Si la partición está dividida, el uso de la parte decimal de la cambió de número aleatorio para decidir la división. En este caso, el valor es 0.5, y 0.5 < 0.6, así que el regreso a.

    Aquí está algo de código y otra explicación, pero por desgracia no use la bitshifting técnica, ni he hecho verificado.

    El bit a bit truco es muy linda, pero hay que tener en cuenta que el número aleatorio que se utiliza tiene que ser lo suficientemente grande como para seleccionar una partición y para seleccionar un valor dentro de esa partición. No estoy seguro de cómo calcular el número necesario de bits necesarios para calcular la 2ª parte, pero uno debe asegurarse de tener suficiente bits… (por ejemplo, en un equipo de 32 bits con 2^32 particiones, vas a necesitar más que bits de un solo número al azar!) Acabo de utilizar dos números aleatorios para cada muestreo.
    Esto es cierto, usted necesita saber cuántos bits aleatorios que se prometió por su generador para una muestra dada para que esto funcione correctamente. Si usted no sabe, dos, debido a que en los modernos generadores de la fase (o uniforme de dependencia entre las muestras) es muy grande.
    Aquí está una implementación de Ruby de los Walker Alias método así: github.com/cantino/walker_method
    Usted no necesita el más grande siguiente potencia de dos restricción. N contenedores para N pesos funciona bien. En la empinada 3, usted no necesita un artículo con el menos peso restante, sólo uno menos que el promedio. En realidad, esto acelera el algoritmo de mucho, porque no es necesario ordenar los pesos, sólo partición en/pesado ligero.
    La potencia de dos es para el bit de desplazamiento. Usted no tiene que usar bit de desplazamiento, y si no usted no está limitado a potencias de dos. También, el más ligero de peso restante se da en la búsqueda de la acumulación de tiempo, no el tiempo de la muestra, por lo que no hace mucha diferencia. Si a pesar de que es una preocupación, el uso de un min-heap. Yo entiendo que hay algunos sutil corrección de los casos si no se selecciona el mínimo, pero no recuerdo de ellos. En otras palabras, hacer lo contrario a su propio riesgo.

    OriginalEl autor John with waffle

  2. 5

    Aquí es lo que se me ocurrió para ponderado de selección sin reemplazo:

    def WeightedSelectionWithoutReplacement(l, n):
      """Selects without replacement n random elements from a list of (weight, item) tuples."""
      l = sorted((random.random() * x[0], x[1]) for x in l)
      return l[-n:]

    Este es O(m log m) sobre el número de elementos en la lista para ser seleccionado. Estoy bastante seguro de que esto le peso de los elementos correctamente, aunque no he verificado en cualquier sentido formal.

    Aquí es lo que se me ocurrió para ponderado de selección con reemplazo:

    def WeightedSelectionWithReplacement(l, n):
      """Selects with replacement n random elements from a list of (weight, item) tuples."""
      cuml = []
      total_weight = 0.0
      for weight, item in l:
        total_weight += weight
        cuml.append((total_weight, item))
      return [cuml[bisect.bisect(cuml, random.random()*total_weight)] for x in range(n)]

    Este es O(m + n log m), donde m es el número de elementos en la lista de entrada, y n es el número de elementos a seleccionar.

    Que la primera función es brillante, pero por desgracia no peso los elementos correctamente. Considere la posibilidad de WeightedSelectionWithoutReplacement([(1, 'A'), (2, 'B')], 1). Se va a elegir Una con una probabilidad de 1/4, 1/3 no. Difícil de arreglar.
    Por cierto, más rápido, pero los algoritmos más complejos son, en mi respuesta aquí: stackoverflow.com/questions/2140787/…
    Agradable encontrar @JasonOrendorff. De hecho, la diferencia es bastante malo. Para los pesos (1, 2, 3, 4), que esperas «1» para ser elegido 1/10 del tiempo, pero va a ser elegido 1/94 de la época. Yo realmente quería que trabajar!
    ¿Cómo calcular 1/4? Si usted tiene una fórmula para que, podemos invertir y reemplazar el original de pesas con pesos que va a dar resultados correctos?
    para el 1/4, aquí es como yo lo veo: (aleatorio()*1) rangos de 0-1. Si es 1, la probabilidad de que sea mayor que (aleatorio()*2) 1/2. Si es 0, la probabilidad es 0. El promedio de probabilidades es: 1/4.

    OriginalEl autor Nick Johnson

  3. 4

    Yo te recomiendo empezar por mirar la sección 3.4.2 de Donald Knuth del Seminumerical Algoritmos.

    Si las matrices son grandes, hay algoritmos más eficaces en el capítulo 3 de Principios de Azar de la Variable aleatoria Generación por Juan Dagpunar. Si las matrices no son muy grandes o no te preocupa apretando con tanta eficiencia como sea posible, el más simple de los algoritmos en Knuth son probablemente muy bien.

    Acabo de tomar un vistazo a la sección 3.4.2, y cubre sólo el imparcial de selección con y sin reemplazo – no hay ninguna mención de la ponderación de selección.

    OriginalEl autor John D. Cook

  4. 4

    Un enfoque sencillo que no ha sido mencionado aquí es una propuesta en Efraimidis y Spirakis. En python se puede seleccionar m elementos de n >= m ponderado de los elementos estrictamente positivo pesos almacenados en pesos, la devolución de los índices seleccionados, con:

    import heapq
    import math
    import random
    
    def WeightedSelectionWithoutReplacement(weights, m):
        elt = [(math.log(random.random()) / weights[i], i) for i in range(len(weights))]
        return [x[1] for x in heapq.nlargest(m, elt)]

    Esto es muy similar en estructura a la primera enfoque propuesto por Nick Johnson. Por desgracia, ese enfoque es parcial en la selección de los elementos (véase el comentario sobre el método). Efraimidis y Spirakis demostrado que su enfoque es equivalente a la de muestreo aleatorio sin reemplazo en los enlaces de papel.

    OriginalEl autor josliber

  5. 4

    La siguiente es una descripción de azar ponderado de selección de un elemento de un
    set (o conjunto múltiple, si se repite están permitidos), con y sin reemplazo en O(n) espacio
    y O(log n) tiempo.

    Consiste en la aplicación de un árbol de búsqueda binario, ordenados por los elementos a ser
    seleccionado, donde cada nodo del árbol contiene:

    1. el mismo elemento (elemento)
    2. la onu normalizado peso del elemento (elementweight), y
    3. la suma de todas la naciones unidas normalizada de pesos de la izquierda-nodo hijo y todos los de
      sus hijos (leftbranchweight).
    4. la suma de todas la naciones unidas normalizada de pesos de los derecho del niño nodo y todos los de
      su chilren (rightbranchweight).

    A continuación, se selecciona aleatoriamente un elemento de la BST por el descenso del árbol. Un
    aproximada de la descripción del algoritmo de la siguiente manera. El algoritmo se da un nodo de
    el árbol. A continuación, los valores de leftbranchweight, rightbranchweight,
    y elementweight de nodo se suman y los pesos son divididos por este
    suma, lo que resulta en los valores leftbranchprobability,
    rightbranchprobability, y elementprobability, respectivamente. A continuación, un
    número aleatorio entre 0 y 1 (randomnumber) se obtiene.

    • si el número es menor que elementprobability,
      • elimina el elemento de la BST como normal, la actualización de leftbranchweight
        y rightbranchweight de todos los nodos, y devolver el
        elemento.
    • por el contrario, si el número es menor que (elementprobability + leftbranchweight)
      • recurse en leftchild (ejecutar utilizando el algoritmo de leftchild como nodo)
    • más
      • recurse en rightchild

    Cuando por fin encontramos que el uso de estos pesos, que es el elemento a ser devuelto, o bien simplemente a cambio (con reemplazo) o nos la quita y actualización pertinente de pesos en el árbol (sin reemplazo).

    DESCARGO de responsabilidad: El algoritmo es áspera, y un tratado sobre la correcta aplicación
    de un BST es que no se trató de aquí; más bien, se espera que esta respuesta te ayude
    aquellos que realmente necesitan una rápida ponderado de selección sin reemplazo (como yo).

    Para el promedio ponderado de-sin-algoritmo de reemplazo, esto produce un resultado erróneo. Es decir, los elementos no serán seleccionadas con probabilidad proporcional a su peso. Consulte stackoverflow.com/a/27049669/262304 para una solución.

    OriginalEl autor djhaskin987

  6. 3

    Es posible hacer Ponderado de Selección al Azar con reemplazo de la O(1) hora después de la creación de un adicional de S(N) tamaño de la estructura de datos en O(N) tiempo. El algoritmo se basa en la Método Alias desarrollado por Walker y Vose, que está bien descrito aquí.

    La idea esencial es que cada bin en un histograma sería elegido con probabilidad 1/N por un uniforme de RNG. Así que vamos a caminar a través de él, y para cualquier poco poblado bin que quisiera recibir el exceso de visitas, asignar el excedente a un superpoblado de reciclaje. Para cada bin, almacenamos el porcentaje de visitas que pertenecen a ella, y la pareja de reciclaje para el exceso. Esta versión pistas pequeñas y grandes contenedores en el lugar, la eliminación de la necesidad de una pila adicional. Se utiliza el índice de la pareja (almacenado en bucket[1]) como un indicador de que ya han sido procesados.

    Aquí es de un mínimo de implementación de python, basado en la implementación en C de aquí

    def prep(weights):
        data_sz = len(weights)
        factor = data_sz/float(sum(weights))
        data = [[w*factor, i] for i,w in enumerate(weights)]
        big=0
        while big<data_sz and data[big][0]<=1.0: big+=1
        for small,bucket in enumerate(data):
            if bucket[1] is not small: continue
            excess = 1.0 - bucket[0]
            while excess > 0:
                if big==data_sz: break
                bucket[1] = big
                bucket = data[big]
                bucket[0] -= excess
                excess = 1.0 - bucket[0]
                if (excess >= 0):
                    big+=1
                    while big<data_sz and data[big][0]<=1: big+=1
        return data
    
    def sample(data):
        r=random.random()*len(data)
        idx = int(r)
        return data[idx][1] if r-idx > data[idx][0] else idx

    Ejemplo de uso:

    TRIALS=1000
    weights = [20,1.5,9.8,10,15,10,15.5,10,8,.2];
    samples = [0]*len(weights)
    data = prep(weights)
    
    for _ in range(int(sum(weights)*TRIALS)):
        samples[sample(data)]+=1
    
    result = [float(s)/TRIALS for s in samples]
    err = [a-b for a,b in zip(result,weights)]
    print(result)
    print([round(e,5) for e in err])
    print(sum([e*e for e in err]))

    OriginalEl autor AShelly

  7. 0

    Supongamos que usted desea para la muestra 3 elementos sin el reemplazo de la lista [‘blanco’,’azul’,’negro’,’amarillo’,’verde’] con una prob. distribución [0.1, 0.2, 0.4, 0.1, 0.2]. El uso de numpy.al azar módulo es tan fácil como esto:

        import numpy.random as rnd
    
        sampling_size = 3
        domain = ['white','blue','black','yellow','green']
        probs = [.1, .2, .4, .1, .2]
        sample = rnd.choice(domain, size=sampling_size, replace=False, p=probs)
        # in short: rnd.choice(domain, sampling_size, False, probs)
        print(sample)
        # Possible output: ['white' 'black' 'blue']

    Configuración de la replace bandera a True, tiene un muestreo con reemplazo.

    Más info aquí:
    http://docs.scipy.org/doc/numpy/reference/generated/numpy.random.choice.html#numpy.random.choice

    OriginalEl autor Maroxo

Dejar respuesta

Please enter your comment!
Please enter your name here