Minimalwert: Wie man die Anzahl der eindeutigen Werte schätzt

Im letzten Artikel über lineares Zählen haben wir die grundlegenden Algorithmen zur Berechnung und Schätzung der Anzahl eindeutiger Werte in einem Datensatz besprochen. Heute haben wir einen weiteren probabilistischen Algorithmus, mit dem wir die Anzahl der eindeutigen Werte mit angemessener Genauigkeit und geringem Speicherbedarf schätzen können.

Min-Wert

In diesem Artikel werden wir nur mit reellen Zahlen aus dem Einheitsintervall (0; 1) arbeiten. Betrachten wir eine gleichmäßig verteilte Menge von Zahlen aus diesem Intervall, z. B. die Zahlenmenge {0,25; 0,5; 0,75}. Benachbarte Zahlen sind immer genau 0,25 voneinander entfernt (und von Null und Eins). Wie hilft uns das beim Zählen der Anzahl eindeutiger Elemente?

Wenn ich Ihnen sage, dass wir eine solche gleichmäßig verteilte Menge von Zahlen aus dem Einheitsintervall haben, und diese Zahlen haben einen Abstand von nur 0,2 - können Sie berechnen, wie viele Elemente eine solche Menge hat? Natürlich ist es eine Menge {0,2; 0,4; 0,6; 0,8}, deren Kardinalität gleich vier ist. Wenn wir gleichmäßig verteilte Zahlen aus dem Einheitsintervall als Eingabe haben und den Abstand zwischen benachbarten Zahlen kennen, können wir die Anzahl der Elemente leicht berechnen.

Der Abstand zwischen benachbarten Zahlen ist gleich dem kleinsten Element der Menge - der Abstand zwischen benachbarten Elementen der Menge {0.25; 0.5; 0.75} ist 0.25, usw. Wenn wir die Anzahl der Elemente von gleichmäßig verteilten Zahlen berechnen, müssen wir nur irgendwie das minimale Element finden. Dann können wir die Anzahl der Elemente p mit einer einfachen Formel berechnen:

$$\Large p=\frac{1}{m}-1$$

wobei m das minimale Element ist.

Und wieder werden wir hashen...

Nun, ja, aber wie können wir das nutzen, wenn wir einige Zeichenketten oder andere Werte in der Eingabe haben, die nicht genau die Bedingung der Gleichverteilung im Einheitsintervall erfüllen? Auch hier hilft die gute alte Hash-Funktion, die für jede Eingabe eine rationale Zahl aus dem Einheitsintervall zurückgeben kann. Es wird einfach sein, eine solche Hash-Funktion zu konstruieren.

Diese würde uns rationale Zahlen aus den Daten liefern, aber wie machen wir diese Zahlen gleichmäßig verteilt? Das können wir nicht, aber wir können uns auf andere Weise helfen. In der Tat verhält sich die Hash-Funktion aus unserer Sicht eher "zufällig". Für sehr ähnliche Wörter wie "hallo", "ahok" und "ahol" wird die Hash-Funktion wahrscheinlich sehr unterschiedliche Prüfsummen liefern. Mit anderen Worten: Wenn wir tausend verschiedene Werte in ein Einheitsintervall hacken, ist es sehr unwahrscheinlich, dass eine signifikante Mehrheit der Zahlen weniger als die Hälfte beträgt. Umgekehrt ist es sehr wahrscheinlich, dass diese Zahlen mehr oder weniger gleichmäßig verteilt sind. Je mehr Daten wir hacken, desto regelmäßiger wird die Verteilung sein.

Aus dieser Idee ergibt sich ein einfacher Algorithmus: Wir gehen die Eingabedaten durch, hacken jedes Element in ein Einheitsintervall und merken uns das kleinste Element. Wir schätzen die Anzahl der eindeutigen Elemente mit Hilfe der vorherigen Formel. Python-Implementierung:

from uuid import uuid4 def nhash(item, n): return hash(item) % (2 ** n) def unit_interval_hash(item, n): integer_hash = nhash(item, n) + 1 return integer_hash / float(2 ** n) def count_unique_using_minimum(values, n):
    numbers_from_unit_interval = (unit_interval_hash(item, n) for item in values) minimum = min(numbers_from_unit_interval) return int(1 / minimum) - 1 for _ in xrange(10): print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

Die Funktion unit_interval_hash gibt eine Dezimalzahl aus dem Intervall (0, 1>) zurück . Die Funktion count_unique_using_minimum konvertiert zunächst alle Eingabewerte in genau diese Zahl, findet das Minimum und gibt 1 / minimum - 1 zurück. Beachten Sie, dass es keine Rolle spielt, wie viele identische Werte der Datensatz enthält - für zwei identische Werte gibt die Hash-Funktion dieselbe rationale Zahl zurück, was keinen Einfluss auf das resultierende Minimum hat. Daher verwenden wir diesen Algorithmus, um die Anzahl der eindeutigen Elemente zu zählen.

Was sind die Ergebnisse? (In jeder Zeile ist eine geschätzte Kardinalität angegeben, aber die richtige Kardinalität ist 10.000).

5957 16384 13107 9362 65536 8192 21845 13107 21845 8192

Das ist nicht viel, oder? Der Algorithmus durchlief zehn verschiedene Sätze von IDs mit jeweils zehntausend eindeutigen Werten. Die berechneten Schätzungen liegen also meist weit daneben. Würde man den Durchschnitt bilden, käme man auf einen Wert von 18.352. Andererseits ist der Speicherbedarf immer noch ziemlich hoch - er ist konstant! Um das Minimum zu finden, muss man nur immer eine Variable im Speicher behalten, die das aktuelle Minimum speichert, und das war's. Also ja, die Schätzung ist ätzend, aber andererseits kostet sie fast nichts.

Verbesserung von

Wir sehen, dass der Algorithmus größtenteils instabil ist - einmal liefert er eine ziemlich gute Schätzung (9362), das zweite Mal eine völlig falsche Schätzung (65536). Wie kommen wir aus dieser Situation heraus? Wir können uns helfen, indem wir die Eingabedaten in mehrere Teile aufteilen und die Anzahl der eindeutigen Elemente für jeden Teil zählen und schließlich alles schön mitteln. Wir könnten nach dem ersten Zeichen in unserer ID entscheiden. Wir zählen also die Anzahl der Unikate getrennt für IDs, die mit dem Buchstaben "a" beginnen, dann für solche, die mit dem Buchstaben "b" beginnen, usw. Code:

from uuid import uuid4 def nhash(item, n): return hash(item) % (2 ** n) def unit_interval_hash(item, n): integer_hash = nhash(item, n) + 1 return integer_hash / float(2 ** n) def count_unique_using_minimum(values, n):
    min_values = {} for item in values: first_char = str(item)[0] hashed_value = unit_interval_hash(item, n) min_values[first_char] = min(min_values.get(first_char, 1), hashed_value) average_minimum = sum(min_values.values()) / len(min_values) return (int(1 / average_minimum) - 1) * len(min_values) for _ in xrange(10): print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

Die Änderungen befinden sich in der Funktion count_unique_using_minimum. In der Variablen min_values werden die Minima für jede Gruppe gespeichert. Am Ende addieren wir alle Minima und teilen sie durch die Anzahl aller gespeicherten Werte - wir erhalten das durchschnittliche Minimum. Wir verwenden den Ausdruck 1/average_minimum, um die durchschnittliche Anzahl der eindeutigen Werte in jeder Gruppe zu ermitteln - diesen Wert multiplizieren wir dann mit der Anzahl der Gruppen, um die geschätzte Anzahl der eindeutigen Werte in dem übergebenen Datensatz zu erhalten. Und wie funktioniert dieses geänderte Verfahren?

11312 7504 10560 8160 9344 12688 10976 11616 16240 6832

Nun, es ist immer noch nicht gut, aber es ist sicherlich besser. Der Algorithmus ist stabiler. Wir können versuchen, die Funktion so zu ändern, dass die Gruppen nicht nach dem ersten Zeichen gebildet werden, sondern z. B. nach den ersten beiden Zeichen der ID, d. h. wie folgt:

first_char = str(item)[0:2] # ToDo: besseren Namen für Variable wählen

Die Ergebnisse würden dann so aussehen:

9728 9728 9984 10240 8960 10752 9728 9472 11264 9472

Das ist doch gar nicht so schlecht, oder? Wenn wir noch hunderttausend eindeutige Werte, die ersten beiden Zeichen und n = 24 ausprobieren, erhalten wir diese Ergebnisse:

103936 110080 102656 101120 101376 108288 97536 97024 107776 92416

Nicht schlecht. Aber es gibt immer noch bessere Algorithmen, keine Sorge.

Und wie sieht es mit dem Speicherbedarf aus? Wir müssen für jede Gruppe ein Minimum einhalten, mehr nicht. Wenn unsere IDs im Hex-Format vorliegen, bedeutet das, dass wir uns höchstens ^16x Minimalwerte merken müssen, wobei x die Anzahl der Zeichen ist, aus denen der Gruppenschlüssel besteht. Ein Minimum ist eine rationale Zahl, d. h. eine Art Double oder Float.

Ein letzter Hinweis: Wir konnten es uns leisten, die Eingabe in mehrere Gruppen aufzuteilen, weil wir IDs in der Eingabe hatten, die sich wie eine zufällige Zeichenfolge verhielten. Hätten wir keine zufällige Zeichenkette in der Eingabe, sondern Daten in einem bestimmten Format, müssten wir die Aufteilung anders vornehmen. Wenn zum Beispiel jede ID mit dem Präfix userid- beginnt, würde die Gruppierung nach dem ersten Zeichen wahrscheinlich nicht sehr gut funktionieren.