10 votos

Estimación del tamaño de una intersección de múltiples conjuntos utilizando una muestra de un conjunto

Estoy trabajando en un algoritmo que necesita calcular el tamaño de un conjunto generado por las intersecciones de al menos 2 conjuntos. Más concretamente:

$$ z = \left |A_0 \cap \ldots \cap A_n \right | $$

Los conjuntos que se cruzan son generados por consultas SQL, y en un esfuerzo por mantener las cosas rápidas, obtengo un recuento de cada consulta por adelantado, luego tomo el conjunto con el menor recuento ( $A_0$ ) y utilizar esos IDs como límites en el resto de las grandes consultas, por lo que la intersección se convierte efectivamente:

$$ z = \left |\left ( A_0 \cap A_1 \right ) \cap \ldots \cap \left ( A_0 \cap A_n \right ) \right | $$

Incluso esta estrategia me deja con algunas consultas bastante grandes para ejecutar, ya que $\left | A_0 \right |$ a veces puede ser grande. Mi idea para tratar esto es tomar una muestra aleatoria de $A_0$ y la intersección con el resto de los conjuntos antes de extrapolar a una estimación adecuada de $z$ . Mi pregunta es: ¿cuál es la mejor manera de realizar el muestreo y luego extrapolar para llegar a un valor de $z$ que, si no es totalmente preciso, tiene un rango de error predecible?


Esto es lo que he probado hasta ahora (en pseudocódigo, más o menos):

sample_threshold := 10000
factor := 1
if (len(A0) > sample_treshold) {
    factor = sample_threshold / len(A0)
}

// Take a random sample of size 10000 from A0

// Intersect all the other sets with the A0 sample, then with each other
working_set := A0
for i, a := range A {
    a = intersect(A0, a)
    working_set = intersect(working_set, a)
}

z := len(working_set) * (1 / factor)

Este código funciona, pero parece sobrestimar sistemáticamente z con un tamaño de muestra menor que produce una estimación mayor. Además, no estoy seguro de cómo se escalaría esto con más de dos conjuntos para intersecar.

Espero que esta pregunta tenga sentido, dime si puedo aclarar algo más. Además, si esta pregunta está fuera de tema o pertenece a otro lugar, por favor hágamelo saber y estaré encantado de moverla.


Por Comentario de Bill He realizado algunas pruebas rápidas para mostrar el tamaño de la muestra frente al error. Cada cubo de tamaño de muestra se ejecutó 20 veces, y como se puede ver hay una tendencia bastante clara:

Plot

0 votos

Creo que un simple muestreo aleatorio sin reemplazo debería funcionar. Me desconcierta que se obtengan sobreestimaciones. Esto parece que se corresponde exactamente con la estimación de la media de la población utilizando la media de la muestra de una muestra aleatoria. Usted está tratando de estimar la probabilidad de la población de que un elemento de $A_0$ está en la intersección de los otros $A$ s. He jugado con un ejemplo sencillo y funciona bien. ¿Qué tan seguro estás de que estás sobreestimando consistentemente? ¿Ha sucedido como 15 veces de 20 o como 150 veces de 200? ¿La muestra es realmente aleatoria?

1 votos

@Bill He añadido un gráfico del tamaño de la muestra frente al error que ilustra lo que estoy viendo. Es más bien 20 veces de 20. En cuanto a la muestra aleatoria, es tan aleatoria como ORDER BY RAND() que no es perfecto pero debería ser adecuado para esta tarea.

0 votos

@JimmySawczuk ¿No sería mejor simplemente intersecar el "conjunto de trabajo" con "a" directamente, en lugar de "intersect(A0, a)"? Porque "A0" será presumiblemente mayor que el "conjunto de trabajo" actual en el algoritmo después de la primera ejecución... ¿Lo he entendido bien?

3voto

RoMa Puntos 401

Si su conjunto $A_0$ tiene elementos repetidos (es decir, es en realidad un multiconjunto), el tamaño de la intersección será sobrestimado por su procedimiento porque su factor de escala utiliza el número de elementos muestreados y no el número de "tipos" únicos muestreados. Puede corregir la estimación calculando el factor como la relación entre el número de elementos únicos de su muestra aleatoria y el número de elementos únicos del conjunto completo $A_0$ .

0voto

jlh Puntos 71

Como Innuo señala Mi problema era debido a los duplicados en mi conjunto de muestras $A_0$ , lo que provocó factor en mi pseudocódigo fuera demasiado bajo, lo que a su vez provocó que la extrapolación final de z sea demasiado alta porque se generó a través de la inversa de factor . La eliminación de los duplicados solucionó este problema, y ahora el algoritmo genera un gráfico de delta frente al tamaño de la muestra más parecido al que yo esperaría (las líneas indican el margen de error con un nivel de confianza del 95% para ese tamaño de muestra frente a la población total):

Plot

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X