Min Value: So schätzt du die Anzahl eindeutiger Werte

Im letzten Artikel über Linear Counting haben wir die grundlegenden Algorithmen zur Berechnung und Schätzung der Anzahl eindeutiger Werte in einem Datensatz besprochen. Heute kommt ein weiterer probabilistischer Algorithmus an die Reihe, der mit ordentlicher Genauigkeit und kleinem Speicherbedarf die Anzahl der eindeutigen Werte schätzen kann.

Min Value

In diesem Artikel arbeiten wir nur mit reellen Zahlen aus dem Einheitsintervall ]0; 1[. Stellen wir uns eine gleichmäßig verteilte Menge von Zahlen aus diesem Intervall vor, zum Beispiel die Menge {0,25; 0,5; 0,75}. Benachbarte Zahlen sind immer genau 0,25 voneinander entfernt (ebenso von null und von eins). Wie hilft uns das, die Anzahl der eindeutigen Elemente zu bestimmen?

Wenn ich dir sage, dass wir so eine gleichmäßig verteilte Menge von Zahlen aus dem Einheitsintervall haben und dass die Zahlen untereinander genau den Abstand 0,2 haben – kannst du berechnen, wie viele Elemente die Menge hat? Natürlich handelt es sich um die Menge {0,2; 0,4; 0,6; 0,8}, deren Mächtigkeit gleich vier ist. Haben wir als Eingabe gleichmäßig verteilte Zahlen aus dem Einheitsintervall und kennen wir den Abstand benachbarter Zahlen, können wir die Anzahl der Elemente leicht berechnen.

Der Abstand zwischen benachbarten Zahlen ist dabei gleich dem kleinsten Element der Menge – der Abstand benachbarter Elemente der Menge {0,25; 0,5; 0,75} ist 0,25 usw. Um die Anzahl gleichmäßig verteilter Zahlen zu berechnen, genügt es also, irgendwie das kleinste Element zu finden. Dann können wir die Anzahl der Elemente p mit einer einfachen Formel berechnen:

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

wobei m das kleinste Element ist.

Und wieder werden wir hashen…

Na gut, aber wie nutzen wir das, wenn wir als Eingabe Zeichenketten oder andere Werte haben, die die Bedingung der gleichmäßigen Verteilung im Einheitsintervall gerade nicht erfüllen? Wir helfen uns wieder mit der guten alten Hashfunktion, die uns für eine beliebige Eingabe eine rationale Zahl aus dem Einheitsintervall liefern kann. So eine Hashfunktion zu konstruieren ist leicht.

Damit hätten wir aus den Daten rationale Zahlen, aber wie sorgen wir dafür, dass diese Zahlen gleichmäßig verteilt sind? Das geht zwar nicht, aber wir können uns anders behelfen. Eine Hashfunktion verhält sich aus unserer Sicht nämlich ziemlich „zufällig“. Für sehr ähnliche Wörter wie „ahoj“, „ahok“ und „ahol“ liefert die Hashfunktion sehr wahrscheinlich völlig verschiedene Prüfsummen. Mit anderen Worten: Wenn wir tausend verschiedene Werte ins Einheitsintervall hashen, ist es sehr unwahrscheinlich, dass die deutliche Mehrheit der Zahlen zum Beispiel kleiner als ein Halb ist. Sehr wahrscheinlich sind diese Zahlen dagegen mehr oder weniger regelmäßig verteilt. Je mehr Daten wir hashen, desto regelmäßiger wird die Verteilung.

Aus dieser Idee erhalten wir einen einfachen Algorithmus: Wir gehen die Eingabedaten durch, hashen jedes Element ins Einheitsintervall und merken uns das kleinste Element. Die Anzahl der eindeutigen Elemente schätzen wir mit der vorherigen Formel. Die Implementierung in Python:

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 liefert uns eine Dezimalzahl aus dem Intervall ]0; 1]. Die Funktion count_unique_using_minimum wandelt zuerst jeden Eingabewert in eine solche Zahl um, findet das Minimum und liefert 1 / minimum - 1. Beachte, dass es überhaupt nicht darauf ankommt, wie viele gleiche Werte im Datensatz sind – für zwei gleiche Werte liefert die Hashfunktion dieselbe rationale Zahl, was das resultierende Minimum in keiner Weise beeinflusst. Deshalb zählen wir mit diesem Algorithmus die eindeutigen Elemente.

Wie sind die Ergebnisse? (In jeder Zeile steht die geschätzte Kardinalität, die richtige Kardinalität ist dabei 10.000.)

5957
16384
13107
9362
65536
8192
21845
13107
21845
8192

Nicht gerade toll, oder? Der Algorithmus hat zehn verschiedene Mengen von IDs durchlaufen, in denen jeweils zehntausend eindeutige Werte waren. Die berechneten Schätzungen liegen meistens ziemlich daneben. Wenn wir sie mitteln, erhalten wir den Wert 18.352. Der ist immer noch ziemlich daneben, aber dafür schau dir den Speicherbedarf an – er ist konstant! Um das Minimum zu finden, musst du dir im Speicher immer nur eine Variable merken, in der das aktuelle Minimum liegt, und das ist alles. Die Schätzung taugt also nichts, kostet aber auch fast nichts.

Wir verbessern den Algorithmus

Wir sehen, dass der Algorithmus vor allem instabil ist – einmal liefert er eine recht gute Schätzung (9362), ein andermal eine, die völlig danebenliegt (65536). Wie kommen wir da heraus? Wir können uns helfen, indem wir die Eingabedaten in mehrere Teile aufteilen, für jeden Teil die Anzahl der eindeutigen Elemente berechnen und am Ende alles schön mitteln. Wir könnten uns nach dem ersten Zeichen unserer ID richten. Wir berechnen also getrennt die Anzahl der eindeutigen Werte für die IDs, die mit dem Buchstaben „a“ beginnen, dann für die mit dem Buchstaben „b“ usw. Der 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 stecken in der Funktion count_unique_using_minimum. In der Variablen min_values speichern wir die Minima für jede Gruppe. Am Ende addieren wir alle Minima und teilen sie durch die Anzahl aller gespeicherten Werte – wir erhalten das durchschnittliche Minimum. Mit dem Ausdruck 1/average_minimum finden wir heraus, wie viele eindeutige Werte im Durchschnitt in jeder Gruppe liegen – diesen Wert multiplizieren wir noch mit der Anzahl der Gruppen und erhalten die geschätzte Anzahl eindeutiger Werte im übergebenen Datensatz. Und wie funktioniert dieses angepasste Vorgehen?

11312
7504
10560
8160
9344
12688
10976
11616
16240
6832

Na ja, noch immer nicht gut, aber auf jeden Fall 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 zum Beispiel nach den ersten beiden Zeichen der ID, also so:

first_char = str(item)[0:2] # ToDo: choose better name for variable

Die Ergebnisse wären dann diese:

9728
9728
9984
10240
8960
10752
9728
9472
11264
9472

Nooo, das ist schon nicht mehr ganz schlecht, oder? Wenn wir noch hunderttausend eindeutige Werte, die ersten zwei Zeichen und n = 24 ausprobieren, erhalten wir diese Ergebnisse:

103936
110080
102656
101120
101376
108288
97536
97024
107776
92416

Das geht ganz gut. Aber es gibt noch bessere Algorithmen, keine Sorge.

Und wie sieht es mit dem Speicherbedarf aus? Wir müssen das Minimum für jede Gruppe speichern, mehr nicht. Wenn wir die IDs im Hex-Format haben, bedeutet das, dass wir uns höchstens 16^x Minima merken müssen, wobei x die Anzahl der Zeichen ist, aus denen wir den Gruppenschlüssel bilden. Ein Minimum ist eine rationale Zahl, also irgendein Typ double oder float.

Eine Anmerkung zum Schluss: Die Aufteilung der Eingabe in mehrere Gruppen konnten wir uns leisten, weil wir als Eingabe IDs hatten, die sich wie eine Zufallszeichenkette verhielten. Hätten wir keine Zufallszeichenkette, sondern Daten in einem bestimmten Format, müssten wir die Aufteilung anders vornehmen. Würde zum Beispiel jede ID mit dem Präfix userid- beginnen, würde die Aufteilung in Gruppen nach dem ersten Zeichen wohl nicht besonders gut funktionieren, nicht wahr?