Implementieren des Alon-Matias-Szegedy-Algorithmus für die Approximation des zweiten Momentstroms

Question

Ich versuche eine Funktion in Python für eine Schätzung des zweiten Moments eines Datenstroms neu zu erstellen.

Wie das Ullman Buch angegeben, "Mining Massive Datasets", ein Trägheitsmoment:

Ist die Summe der Quadrate der m_i ‚s. Es ist etwas mal die Überraschung Nummer, da es misst, wie ungleich die Verteilung der Elemente im Stream ist.

Die Elemente m_i sind die eindeutigen Elemente in einem Stream.

Zum Beispiel dieses Spielzeug Problem \ Datenstroms mit:

a, b, c, b, d, a, c, d, a, b, d, c, a, a, b 

Wir berechnen die zweite Moment wie folgt aus:

5^2 + 4^2 + 3^2 + 3^2 = 59 

(da 'a' kommt 5mal in dem Datenstrom, 'b' 4 mal, und so weiter)

Da wir nicht den gesamten Datenstrom im Speicher speichern können, können wir einen Algorithmus für die Schätzung des zweiten Moments verwenden:

Der Alon-Matias-Szegedy Algorithm (AMS-Algorithmus), dass der zweiten Moment mit dieser Formel ermitteln:

E(n *(2 * X.value − 1)) 

, in denen X ein Element univocal des Stroms ist, randomically ausgewählt und X. value ist ein counter, der, wenn wir den Stream lesen, 1 zu jedem Mal hinzufügt, dass wir auf ein anderes Vorkommen des x-Elements von der Zeit stoßen, als wir es ausgewählt haben.

n steht für die Länge des Datenstroms und "E" für die mittlere Schreibweise.

Nehmen wir ein Beispiel mit dem vorherigen Datenstrom, nehmen wir an, wir haben "a" an der 13. Stelle des Datenstroms, "d" am 8. und "c" am 3. gewählt. Wir haben nicht "b" ausgewählt.

a, b, c, b, d, a, c, d, a, b, d, c, a, a, b 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
     x    x    x 

wie dies Ausgewählte, haben wir:

X.element = "a" X.value = 2 
X.element = "c" X.value = 3 
X.element = "d" X.value = 2 

Die Schätzung des AMS-Algorithmus ist:

(15*(2 * 2 - 1) + 15*(2 * 3 - 1) + 15*(2 * 2 - 1))/3 = 55 

die ziemlich in der Nähe von dem wahren Wert des zweiten Moment, bevor berechnet ist (59).

nun auf meinem Code konzentrieren, habe ich diese Funktion für die Berechnung des „wahren“ Second Moment geschrieben, um den Datenstrom durch den Vektor (1d Array) simuliert und ein für:

def secondMoment(vector): 
    mydict = dict() 
    for el in vector: 
     if el not in mydict: 
      mydict[el] = 1 
     else: 
      mydict[el] += 1 
    return (sum([pow(value, 2) for key, value in mydict.items()])) 

und das AMS Funktion, die eine Schätzung des zweiten Moment berechnen:

def AMSestimate(vector): 
    lenvect = len(vector) 
    elements = dict() 
    for el in vector: 
     if el in elements: 
      elements[el] += 1 
     elif random.choice(range(0, 10)) == 0: 
      elements[el] = 1 
    # E(n * (2 * x.value - 1)) 
    lendict = len(elements) 
    estimateM2 = 0 
    for key, value in elements.items(): 
     estimateM2 += lenvect * ((2 * value) - 1) 
    print(lendict) 
    if lendict > 0: 
     return estimateM2/lendict 

Das Problem ist, dass, wenn ich versuche, die Wertschätzung eines kleinen Spielzeug-Problem (wie die oben) sind die Werte etwas richtig zu berechnen, aber wenn ich versuche, um den Vektor beispielsweise auf 10000 Elemente zu erweitern, die Werte true Zweiter Moment und Wertschätzung sind ziemlich unterschiedlich.

Ich denke, dass das Problem an der Art und Weise gebunden ist, in der ich den Datenstrom erzeuge, und an der Art und Weise, in der ich mich entscheide, das X.element auszuwählen.

Das heißt:

[random.choice(string.ascii_letters) for x in range(size)] 

Für die Erzeugung eines Zufallsvektors \ Datenstrom

Und

elif random.choice(range(0, 10)) == 0: 
    elements[el] = 1 

Für die X.element Auswahl (oben in dem Code getan, in die AMS-Funktion)

Für die Generierung eines zufälligen Vektors \ Datenstrom, ein Gedanke, dass th Das Problem kann auf das Fehlen der "Variabilität" des Vektors zurückzuführen sein (string.ascii_letters hat nur 52 Elemente).

Answer 1

Dies ist eine interessante Frage.

Sagen wir mit

import random 
import string 

size = 100000 
seq = [random.choice(string.ascii_letters) for x in range(size)] 

Dann wird die erste Implementierung ist ähnlich wie bei Ihnen (beachten Sie die Verwendung von collections.Counter, obwohl) beginnen:

from collections import Counter 

def secondMoment(seq): 
    c = Counter(seq) 
    return sum(v**2 for v in c.values()) 

>>> secondMoment(seq) 
192436972 

Die zweite Implementierung unterscheidet deutlicher als bei Ihnen, wenn . Beachten Sie, dass zuerst die zufälligen Indizes gefunden werden. Dann wird ein Element nur nach seinem ersten Auftreten (falls vorhanden) an einer der Indizes gezählt:

from collections import defaultdict 

def AMSestimate(seq, num_samples=10): 
    inds = list(range(len(seq))) 
    random.shuffle(inds) 
    inds = sorted(inds[: num_samples]) 

    d = {} 
    for i, c in enumerate(seq): 
     if i in inds and c not in d: 
      d[c] = 0 
     if c in d: 
      d[c] += 1 
    return int(len(seq)/float(len(d)) * sum((2 * v - 1) for v in d.values())) 

>>> AMSestimate(seq) 
171020000 

---

bearbeiten In Bezug auf den ursprünglichen Code in der Frage

Im Code in der Frage, betrachten sie Ihre Schleife

for el in vector: 
    if el in elements: 
     elements[el] += 1 
    elif random.choice(range(0, 10)) == 0: 
     elements[el] = 1 

(Minor) Die Probenahme ist problematisch: es hartcodierte probabilistischen bei 0,1

01 ist

Sehen Sie sich auch:

estimateM2 += lenvect * ((2 * value) - 1) 

Dies fehlt eine Division durch die Anzahl der abgetasteten Elemente.