El muestreo de yacimientos es una familia de algoritmos aleatorios para elegir una muestra aleatoria simple , sin reemplazo, de k elementos de una población de tamaño desconocido n en una sola pasada sobre los elementos. El algoritmo no conoce el tamaño de la población n y, por lo general, es demasiado grande para que los n elementos quepan en la memoria principal . La población se revela al algoritmo a lo largo del tiempo y el algoritmo no puede mirar hacia atrás en elementos anteriores. En cualquier momento, el estado actual del algoritmo debe permitir la extracción de una muestra aleatoria simple sin reemplazar el tamaño k sobre la parte de la población vista hasta ahora.
Motivación
Suponga que vemos una secuencia de elementos, uno a la vez. Queremos mantener diez elementos en la memoria y que se seleccionen al azar de la secuencia. Si conocemos el número total de elementos n y podemos acceder a los elementos arbitrariamente, entonces la solución es fácil: seleccione 10 índices distintos i entre 1 y n con la misma probabilidad, y mantenga los elementos i -ésimo. El problema es que no siempre conocemos la n exacta de antemano.
Algoritmo simple
Un algoritmo simple y popular pero lento, comúnmente conocido como Algoritmo R , se debe a Alan Waterman. [1]
El algoritmo funciona manteniendo un depósito de tamaño k , que inicialmente contiene los primeros k elementos de la entrada. Luego, itera sobre los elementos restantes hasta que se agota la entrada. Usando la indexación de matriz basada en uno , dejeser el índice del ítem actualmente bajo consideración. El algoritmo genera entonces un número aleatorio j entre (e incluyendo) 1 e i . Si j es como máximo k , entonces el elemento se selecciona y reemplaza al elemento que ocupa actualmente la j -ésima posición en el depósito. De lo contrario, el artículo se descarta. En efecto, para todo i , el i- ésimo elemento de la entrada se elige para ser incluido en el yacimiento con probabilidad. De manera similar, en cada iteración, el j- ésimo elemento de la matriz de yacimientos se elige para ser reemplazado con probabilidad. Se puede demostrar que cuando el algoritmo ha terminado de ejecutarse, cada elemento de la población de entrada tiene la misma probabilidad (es decir,) de ser elegido para el embalse: .
(* S tiene elementos para muestrear, R contendrá el resultado *) ReservoirSample ( S [ 1 .. n ] , R [ 1 .. k ]) // llene la matriz del reservorio para i : = 1 a k R [ i ] : = S [ i ] // reemplazar elementos con gradualmente decreciente de probabilidad para i : = k + 1 a n (* randominteger (a, b) genera un número entero uniforme desde el rango inclusivo {a, ..., b} *) j : = randominteger ( 1 , i ) si j <= k R [ j ] : = S [ i ]
Si bien es conceptualmente simple y fácil de entender, este algoritmo necesita generar un número aleatorio para cada elemento de la entrada, incluidos los elementos que se descartan. Su tiempo de funcionamiento asintótico es, por tanto,. Esto hace que el algoritmo sea innecesariamente lento si la población de entrada es grande.
Un algoritmo óptimo
El algoritmo L [2] mejora este algoritmo al calcular cuántos elementos se descartan antes de que el siguiente elemento ingrese al depósito. La observación clave es que este número sigue una distribución geométrica y, por lo tanto, se puede calcular en tiempo constante.
(* S tiene elementos para muestrear, R contendrá el resultado *) ReservoirSample ( S [ 1 .. n ] , R [ 1 .. k ]) // llene la matriz del reservorio para i = 1 a k R [ i ] : = S [ i ] (* random () genera un número aleatorio uniforme (0,1) *) W : = exp ( log ( random ()) / k ) while i <= n i : = i + floor ( log ( random ()) / log ( 1 - W )) + 1 si i <= n (* reemplaza un elemento aleatorio del depósito con el elemento i *) R [ randomInteger ( 1 , k )] : = S [ i ] // índice aleatorio entre 1 y k, inclusive W : = W * exp ( log ( random ()) / k )
Este algoritmo calcula tres números aleatorios para cada artículo que se convierte en parte del depósito y no dedica tiempo a artículos que no lo hacen. Por lo tanto, su tiempo de ejecución esperado es, [2] que es óptimo. [1] Al mismo tiempo, es simple de implementar de manera eficiente y no depende de desviaciones aleatorias de distribuciones exóticas o difíciles de calcular.
Con ordenación aleatoria
Si asociamos con cada elemento de la entrada un número aleatorio generado uniformemente, los k elementos con los valores asociados más grandes (o, de manera equivalente, los más pequeños) forman una muestra aleatoria simple. [3] Un muestreo de yacimiento simple mantiene así los k elementos con los valores asociados más grandes actualmente en una cola de prioridad .
(* S es un flujo de elementos para muestrear S. Actual devuelve el elemento actual en el flujo S. Siguiente avanza el flujo a la siguiente posición soporte de cola de prioridad mínima : Recuento -> número de elementos en la cola de prioridad Mínimo -> devuelve el valor de clave mínimo de todos los elementos Extraer-Mín () -> Eliminar el elemento con la clave mínima Insertar (clave, Elemento) -> Agrega el elemento con la clave especificada *) ReservoirSample ( S [ 1 .. ? ]) H : = nuevo mínimo - prioridad - cola mientras S tiene datos r : = aleatorio () // uniformemente aleatorio entre 0 y 1, exclusivo si H . Conde < k H . Insertar ( R , S . Actual ) else // torreón k elementos con claves asociadas más grandes si r > H . Mínimo H . Extraer - Min () H . Insertar ( R , S . Actual ) S . Próximos artículos devueltos en H
El tiempo de ejecución esperado de este algoritmo es y es relevante principalmente porque se puede extender fácilmente a artículos con pesos.
Muestreo aleatorio ponderado
Algunas aplicaciones requieren que las probabilidades de muestreo de los elementos estén de acuerdo con los pesos asociados con cada elemento. Por ejemplo, podría ser necesario muestrear consultas en un motor de búsqueda con ponderación como el número de veces que se realizaron para que la muestra pueda analizarse para determinar el impacto general en la experiencia del usuario. Deje que el peso del artículo i sea, Y la suma de todos los pesos sea W . Hay dos formas de interpretar los pesos asignados a cada artículo del conjunto: [4]
- En cada ronda, la probabilidad de que todos los elementos no seleccionados se seleccionen en esa ronda es proporcional a su peso en relación con los pesos de todos los elementos no seleccionados. Si X es la muestra actual, entonces la probabilidad de un artículo ser seleccionado en la ronda actual es .
- La probabilidad de que cada elemento se incluya en la muestra aleatoria es proporcional a su peso relativo, es decir, . Tenga en cuenta que esta interpretación puede no ser posible en algunos casos, por ejemplo,.
Algoritmo A-Res
Efraimidis y Spirakis dieron el siguiente algoritmo que utiliza la interpretación 1: [5]
(* S es un flujo de elementos para muestrear S. Current devuelve el elemento actual en el flujo S.Weight devuelve el peso del elemento actual en el flujo S.Next avanza el flujo a la siguiente posición El operador de energía está representado por ^ min-priority-queue admite: Recuento -> número de elementos en la cola de prioridad Mínimo () -> devuelve el valor de clave mínimo de todos los elementos Extraer-Mín () -> Eliminar el elemento con la clave mínima Insertar (clave, Elemento) -> Agrega el elemento con la clave especificada *) ReservoirSample ( S [ 1 .. ? ]) H : = nuevo min - prioridad - cola mientras que S tiene datos r : = aleatorio () ^ ( 1 / S . Peso ) // random () produce un número uniformemente aleatorio en (0, 1) si H . Conde < k H . Insertar ( R , S . Actual ) else // torreón k elementos con claves asociadas más grandes si r > H . Mínimo H . Extraer - Min () H . Insertar ( R , S . Actual ) S . Próximos artículos devueltos en H
Este algoritmo es idéntico al algoritmo dado en Muestreo de yacimientos con ordenación aleatoria, excepto por la generación de claves de los elementos. El algoritmo equivale a asignar una clave a cada elemento.donde r es el número aleatorio y luego seleccionando los k elementos con las claves más grandes. De manera equivalente, una formulación numéricamente más estable de este algoritmo calcula las claves comoy seleccione los k elementos con las teclas más pequeñas . [6] [ verificación fallida ]
Algoritmo A-ExpJ
El siguiente algoritmo es una versión más eficiente de A-Res , también proporcionado por Efraimidis y Spirakis: [5]
(* S es un flujo de elementos para muestrear S. Current devuelve el elemento actual en el flujo S.Weight devuelve el peso del elemento actual en el flujo S.Next avanza el flujo a la siguiente posición El operador de energía está representado por ^ min-priority-queue admite: Recuento -> número de elementos en la cola de prioridad Mínimo -> clave mínima de cualquier elemento en la cola de prioridad Extraer-Mín () -> Eliminar el elemento con clave mínima Insertar (Clave, Elemento) -> Agrega elemento con clave especificada *) ReservoirSampleWithJumps ( S [ 1 .. ? ]) H : = nuevo min - prioridad - cola mientras que S tiene datos y H . Conde < k r : = aleatorio () ^ ( 1 / S . Peso ) // random () produce un número uniformemente aleatorio en (0,1) H . Insertar ( R , S . Actual ) S . Siguiente X : = log ( aleatorio ()) / log ( H . Mínimo ) // esta es la cantidad de peso que debe ser saltado por encima mientras que S tiene datos X : = X - S . Peso si X <= 0 t : = H . Mínimo ^ S . Peso r : = aleatorio ( t , 1 ) ^ ( 1 / S . Peso ) // aleatorias (x, y) produce un número uniformemente aleatorio en (x, y) H . Extraer - Min () H . Insertar ( R , S . Actual ) X : = log ( aleatorio ()) / log ( H . Mínimo ) S . Próximos artículos devueltos en H
Este algoritmo sigue las mismas propiedades matemáticas que se utilizan en A-Res , pero en lugar de calcular la clave para cada elemento y verificar si ese elemento debe insertarse o no, calcula un salto exponencial al siguiente elemento que se insertará. Esto evita tener que crear variantes aleatorias para cada artículo, lo que puede resultar caro. El número de variantes aleatorias necesarias se reduce de a en expectativa, donde es el tamaño del depósito, y es el número de elementos de la secuencia. [5]
Algoritmo A-Chao
El siguiente algoritmo fue proporcionado por MT Chao usa la interpretación 2: [7]
(* S tiene elementos para muestrear, R contendrá el resultado S [i] .Weight contiene el peso de cada elemento *) WeightedReservoir - Chao ( S [ 1 .. n ] , R [ 1 .. k ]) WSum : = 0 // llenar la matriz del depósito para i : = 1 a k R [ i ] : = S [ i ] WSum : = WSum + S [ i ] . Peso para i : = k + 1 a n WSum : = WSum + S [ i ] . Peso p : = k * S [ i ] . Peso / WSum // probabilidad para este elemento j : = aleatorio () ; // uniformemente aleatorio entre 0 y 1 si j <= p // seleccionar el elemento de acuerdo con la probabilidad R [ randomInteger ( 1 , k )] : = S [ i ] // selección uniforme en el reservorio para reemplazo
Para cada artículo, se calcula su peso relativo y se usa para decidir aleatoriamente si el artículo se agregará al depósito. Si se selecciona el elemento, entonces uno de los elementos existentes del depósito se selecciona uniformemente y se reemplaza con el nuevo elemento. El truco aquí es que, si las probabilidades de todos los elementos en el depósito ya son proporcionales a sus pesos, entonces al seleccionar uniformemente qué elemento reemplazar, las probabilidades de todos los elementos siguen siendo proporcionales a su peso después del reemplazo.
Algoritmo A-Chao con saltos
De manera similar a los otros algoritmos, es posible calcular un peso aleatorio j
y restar los valores de masa de probabilidad de los elementos, saltándolos mientras se j > 0
reduce la cantidad de números aleatorios que deben generarse. [4]
(* S tiene elementos para muestrear, R contendrá el resultado S [i] .Weight contiene el peso de cada elemento *) WeightedReservoir - Chao ( S [ 1 .. n ] , R [ 1 .. k ]) WSum : = 0 // llenar la matriz del depósito para i : = 1 a k R [ i ] : = S [ i ] WSum : = WSum + S [ i ] . Peso j : = aleatorio () // uniformemente aleatorio entre 0 y 1 pnone : = 1 // probabilidad de que no hay ningún elemento se ha seleccionado hasta ahora (en este salto) para i : = k + 1 a n WSum : = WSum + S [ i ] . Peso p : = k * S [ i ] . Peso / WSum // probabilidad para este elemento j - = p * pNinguno pNone : = pNone * ( 1 - p ) if j <= 0 R [ randomInteger ( 1 , k )] : = S [ i ] // selección uniforme en depósito para reemplazo j = aleatorio () p Ninguno : = 1
Relación con la reproducción aleatoria de Fisher-Yates
Suponga que uno quisiera sacar k cartas al azar de una baraja de cartas. Un enfoque natural sería barajar el mazo y luego tomar las primeras k cartas. En el caso general, el barajado también debe funcionar incluso si no se conoce de antemano el número de cartas en el mazo, una condición que se satisface con la versión de adentro hacia afuera del barajado de Fisher-Yates : [8]
(* S tiene la entrada, R contendrá la permutación de salida *) aleatoria ( S [ 1 .. n ] , R [ 1 .. n ]) R [ 1 ] : = S [ 1 ] para i de 2 a n do j : = randomInteger ( 1 , i ) // rango inclusivo R [ i ] : = R [ j ] R [ j ] : = S [ i ]
Tenga en cuenta que aunque el resto de las cartas se barajan, solo las primeras k son importantes en el contexto actual. Por lo tanto, la matriz R solo necesita rastrear las tarjetas en las primeras k posiciones mientras realiza la mezcla, reduciendo la cantidad de memoria necesaria. Truncando R a la longitud k , el algoritmo se modifica en consecuencia:
(* S tiene elementos para muestrear, R contendrá el resultado *) ReservoirSample ( S [ 1 .. n ] , R [ 1 .. k ]) R [ 1 ] : = S [ 1 ] para i de 2 a k do j : = randominteger ( 1 , i ) // inclusive gama R [ i ] : = R [ j ] R [ j ] : = S [ i ] para i de k + 1 a n hacer j : = randominteger ( 1 , i ) // rango inclusivo si ( j <= k ) R [ j ] : = S [ i ]
Dado que el orden de las primeras k tarjetas es irrelevante, el primer bucle se puede eliminar y R se puede inicializar para que sean los primeros k elementos de la entrada. Esto produce el algoritmo R .
Propiedades estadísticas
Las probabilidades de selección de los métodos de yacimiento se discuten en Chao (1982) [7] y Tillé (2006). [9] Si bien las probabilidades de selección de primer orden son iguales a(o, en el caso del procedimiento de Chao, a un conjunto arbitrario de probabilidades desiguales), las probabilidades de selección de segundo orden dependen del orden en que se clasifican los registros en el yacimiento original. El problema se supera con el método de muestreo de cubos de Deville y Tillé (2004). [10]
Limitaciones
El muestreo de yacimientos supone que la muestra deseada encaja en la memoria principal , lo que a menudo implica que k es una constante independiente de n . En aplicaciones en las que nos gustaría seleccionar un subconjunto grande de la lista de entrada (digamos un tercero, es decir,), es necesario adoptar otros métodos. Se han propuesto implementaciones distribuidas para este problema. [11]
Referencias
- ↑ a b Vitter, Jeffrey S. (1 de marzo de 1985). "Muestreo aleatorio con reservorio" (PDF) . Transacciones ACM en software matemático . 11 (1): 37–57. CiteSeerX 10.1.1.138.784 . doi : 10.1145 / 3147.3165 . S2CID 17881708 .
- ^ a b Li, Kim-Hung (4 de diciembre de 1994). "Algoritmos de muestreo de reservorios de complejidad de tiempo O (n (1 + log (N / n)))". Transacciones ACM en software matemático . 20 (4): 481–493. doi : 10.1145 / 198429.198435 . S2CID 15721242 .
- ^ Fan, C .; Muller, ME; Rezucha, I. (1962). "Elaboración de planes de muestreo mediante el uso de técnicas de selección secuencial (elemento por elemento) y computadoras digitales". Revista de la Asociación Estadounidense de Estadística . 57 (298): 387–402. doi : 10.1080 / 01621459.1962.10480667 . JSTOR 2281647 .
- ^ a b Efraimidis, Pavlos S. (2015). "Muestreo aleatorio ponderado sobre flujos de datos". Algoritmos, probabilidad, redes y juegos . Apuntes de conferencias en Ciencias de la Computación. 9295 : 183-195. arXiv : 1012.0256 . doi : 10.1007 / 978-3-319-24024-4_12 . ISBN 978-3-319-24023-7. S2CID 2008731 .
- ^ a b c Efraimidis, Pavlos S .; Spirakis, Paul G. (16 de marzo de 2006). "Muestreo aleatorio ponderado con reservorio". Cartas de procesamiento de información . 97 (5): 181-185. doi : 10.1016 / j.ipl.2005.11.003 .
- ^ Arratia, Richard (2002). Bela Bollobas (ed.). "Sobre la cantidad de dependencia en la factorización prima de un entero aleatorio uniforme". Combinatoria contemporánea . 10 : 29–91. CiteSeerX 10.1.1.745.3975 . ISBN 978-3-642-07660-2.
- ^ a b Chao, MT (1982). "Un plan de muestreo de probabilidad desigual de propósito general". Biometrika . 69 (3): 653–656. doi : 10.1093 / biomet / 69.3.653 .
- ^ Consejo Nacional de Investigaciones (2013). Fronteras en el análisis masivo de datos . Prensa de las Academias Nacionales. pag. 121. ISBN 978-0-309-28781-4.
- ^ Tillé, Yves (2006). Algoritmos de muestreo . Saltador. ISBN 978-0-387-30814-2.
- ^ Deville, Jean-Claude; Tillé, Yves (2004). "Muestreo equilibrado eficiente: el método del cubo" (PDF) . Biometrika . 91 (4): 893–912. doi : 10.1093 / biomet / 91.4.893 .
- ^ Muestreo de yacimientos en MapReduce