¿Cómo mantener un subconjunto aleatorio de una secuencia de datos?

Question

Tengo una corriente de eventos que fluye a través de mis servidores. No es posible para mí almacenarlos todos, pero me gustaría poder procesar algunos de ellos periódicamente. Por lo tanto, quiero mantener un subconjunto de la transmisión que sea una muestra aleatoria de todo lo que he visto, pero está limitado a un tamaño máximo.

Por lo tanto, para cada nuevo elemento, necesito un algoritmo para decidir si debo agregarlo al conjunto almacenado, o si debería descartarlo. Si lo agrego, y ya estoy en mi límite, necesito un algoritmo para desalojar uno de los elementos antiguos.

Obviamente, esto es fácil siempre y cuando esté por debajo de mi límite (simplemente guarde todo). Pero, ¿cómo puedo mantener un buen muestreo al azar sin estar predispuesto hacia los artículos viejos o nuevos artículos una vez que he superado ese límite?

Gracias,

Answer 1

Mientras this paper no es exactamente lo que está buscando, puede ser un buen punto de partida en su búsqueda.

Answer 2

almacena muestras en una cola de primero en entrar primero en salir (FIFO).

establezca una frecuencia de muestreo de tantos eventos entre muestras, o aleatorice esto un poco, dependiendo de sus patrones de eventos.

guarde cada enésimo evento, o siempre que su ritmo lo indique, luego péguelo hasta el final de la cola.

pop uno de la parte superior si el tamaño es demasiado grande.

Answer 3

Asigne una probabilidad de registrar cada evento y almacenar el evento en una estructura de datos indexable. Cuando el tamaño de la estructura llegue al umbral, elimine un elemento aleatorio y agregue nuevos elementos. En Ruby, puede hacer esto:

@storage = [] 
prob = 0.002 

while (message = getnextMessage) do 
    @storage.delete((rand() * @storage.length).floor) if @storage.length > MAX_LEN 
    @storage << message if (rand() < prob) 
end 

Esto aborda su tamaño máximo Y su no sesgo hacia cuando ocurrió el evento. También puede elegir qué elemento se elimina al dividir los elementos almacenados en cubos y luego eliminar un elemento de cualquier contenedor que tenga más de un elemento. El método de cubeta le permite guardar uno de cada hora, por ejemplo.

También debe saber que la teoría del muestreo es Big Math. Si necesita algo más que la idea de un lego sobre esto, debe consultar a un matemático calificado en su área.

Answer 4

Esto supone que no conoce el número total de eventos que se recibirán y que no necesita un número mínimo de elementos en el subconjunto.

arr = arr[MAX_SIZE] //Create a new array that will store the events. Assuming first index 1. 
counter = 1 //Initialize a counter. 

while(receiving event){ 
    random = //Generate a random number between 1 and counter 
    if(counter == random){ 
    if(counter <= MAX_SIZE){ 
     arr[counter] = event 
    } 
    else{ 
     tmpRandom = //Generate a random number between 1 and MAX_SIZE 
     arr[tmpRandom] = event 
    } 
    } 
    counter =+ 1 

} 

Answer 5

Esta es una pregunta común de la entrevista.

Una manera fácil de hacerlo es guardar el enésimo elemento con probabilidad k/n (o 1, el que sea menor). Si necesita eliminar un elemento para guardar la nueva muestra, desaloje un elemento aleatorio.

Esto le proporciona un subconjunto uniformemente aleatorio de los n elementos. Si no conoce n, puede estimarlo y obtener un subconjunto aproximadamente uniforme.

Answer 6

Esto se denomina muestreo aleatorio.Fuente: http://en.wikipedia.org/wiki/Reservoir_sampling

array R[k]; // result 
integer i, j; 

// fill the reservoir array 
for each i in 1 to k do 
    R[i] := S[i] 
done; 

// replace elements with gradually decreasing probability 
for each i in k+1 to length(S) do 
    j := random(1, i); // important: inclusive range 
    if j <= k then 
     R[j] := S[i] 
    fi 
done 

Una explicación decente/prueba: http://propersubset.com/2010/04/choosing-random-elements.html