Szacowanie rozmiaru przecięcia wielu zestawów za pomocą próbki jednego zestawu

Pracuję nad algorytmem, który musi obliczyć rozmiar zestawu wygenerowanego przez przecięcie co najmniej 2 zestawów. Dokładniej:

z = | A_{0} \cap \dots \cap A_{n} |

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

Przecinane zestawy są generowane przez zapytania SQL i starając się utrzymać szybkość, otrzymuję z wyprzedzeniem liczbę każdego zapytania, a następnie biorę zestaw o najniższej liczbie ( $A_0$ ) i używaj tych identyfikatorów jako granic w pozostałych dużych zapytaniach, aby skrzyżowanie skutecznie stało się:

z = | (A_{0} \cap A_{1}) \cap \dots \cap (A_{0} \cap A_{n}) |

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

Od tej pory nawet ta strategia pozostawia mi dość duże zapytania $\left | A_0 \right |$ czasami może być duży. Moim pomysłem na poradzenie sobie z tym jest pobranie losowej próbki $A_0$ i przecinając go z resztą zbiorów przed ekstrapolacją z powrotem do właściwego oszacowania $z$ . Moje pytanie brzmi: jaki jest najlepszy sposób na próbkowanie, a następnie ekstrapolację, aby wrócić do wartości $z$ to znaczy, jeśli nie do końca dokładny, ma przewidywalny zakres błędów?

Oto, co próbowałem do tej pory (w pseudokodzie, w pewnym sensie):

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)

Ten kod działa, ale wydaje się, że konsekwentnie przecenia z, przy czym mniejsza próbka daje wyższe oszacowania. Ponadto nie jestem pewien, jak to się skaluje przy więcej niż dwóch zestawach do przecięcia.

Mam nadzieję, że to pytanie ma sens, daj mi znać, czy mogę coś wyjaśnić. Ponadto, jeśli to pytanie jest nie na temat lub należy do kogoś innego, proszę dać mi znać i chętnie je przeniesie.

Zgodnie z komentarzem Billa przeprowadziłem kilka szybkich prób, aby pokazać wielkość próby w porównaniu do błędu. Każde wiadro wielkości próby było uruchamiane 20 razy i jak widać, istnieje dość wyraźny trend:

Wątek

error sample

— Jimmy Sawczuk
źródło

Myślę, że proste losowe próbkowanie bez zamiany powinno działać. Jestem zaskoczony, że przeceniasz się. Wygląda na to, że dokładnie odwzorowuje oszacowanie średniej populacji przy użyciu średniej próby z próby losowej. Próbujesz oszacować prawdopodobieństwo populacji tego elementu

A_{0}

$A_0$ jest na przecięciu drugiego

A

$A$ s. Mam prosty przykład i działa dobrze. Czy jesteś pewien, że konsekwentnie przeceniasz? Czy zdarzyło się to 15 razy na 20 lub 150 razy na 200? Czy próbka jest naprawdę losowa?

— Bill

@Bill Dodałem wykres wielkości próby w porównaniu do błędu, który ilustruje to, co widzę. To więcej niż 20 razy na 20. Jeśli chodzi o próbkę losową, jest ona tak losowa, jak ORDER BY RAND()nie jest idealna, ale powinna być odpowiednia do tego zadania.

— Jimmy Sawczuk

@ JimmySawczuk Czy nie lepiej byłoby po prostu przeciąć „zestaw roboczy” bezpośrednio „a” zamiast „przecinać (A0, a)”? Ponieważ „A0” przypuszczalnie będzie większy niż obecny „zestaw roboczy” w algorytmie po pierwszym uruchomieniu ... Czy rozumiem to poprawnie?

Czy możesz potwierdzić, że faktycznie masz na myśli zestawy, a nie multisety (tj. Że nie ma duplikatów w zestawach)? Ponieważ, jeśli tak, łatwo jest przecenić rozmiar „skrzyżowania” za pomocą metody. (Rozważ przypadek, w którym

A_{0}

$A_0$ to tylko 100 kopii tego samego elementu, a próbkowałeś ich połowę.)

— Innuo

Czy mogę również zapytać, czy rozmiar przecięcia, w stosunku do rozmiaru oryginalnych zestawów, jest wyjątkowo mały? Jeśli tak, wydaje mi się, że to by wyjaśniało twój problem. Przeprowadziłem kilka symulacji (z mniejszymi zestawami), a także dostaję dość spójne, choć niewielkie, przeszacowanie.

Jeśli twój zestaw $A_0$ ma powtarzające się elementy (tzn. faktycznie jest to zbiór wielosetowy), rozmiar przecięcia zostanie przeceniony przez twoją procedurę, ponieważ twój współczynnik skalowania wykorzystuje liczbę próbkowanych elementów, a nie liczbę unikalnych „typów” próbkowanych. Możesz skorygować oszacowanie, obliczając współczynnik jako stosunek liczby unikalnych elementów w losowej próbce do liczby unikalnych elementów w pełnym zestawie $A_0$ .

— Innuo
źródło

Jak zauważa Innuo , mój problem był spowodowany duplikatami w moim próbkowanym zestawie $A_0$ , co spowodowało, że factormój pseudokod zbył zbyt niski, co z kolei spowodowało, że końcowa ekstrapolacja była zbyt wysoka, ponieważ została wygenerowana przez odwrotność factor. Usunięcie duplikatów rozwiązało ten problem, a teraz algorytm generuje wykres delta względem wielkości próby bardziej zgodny z tym, czego się spodziewałem (linie wskazują margines błędu przy 95% poziomie ufności dla tej wielkości próby w stosunku do całej populacji ):

Wątek

— Jimmy Sawczuk
źródło