Med: Genau, manchmal genau und fast genau

    Wenn man sich an Kollegen wendet und fragt, wie viele Handys sie haben, stellt sich heraus, dass es im Durchschnitt etwa 2,5 sind, aber die große Mehrheit von ihnen hat nicht mehr als eines. Hier stellen sich sofort viele Fragen, ausgehend davon, warum sie plötzlich keine ganze Zahl sind und wie man dennoch einschätzen kann, wie viele Telefone eine durchschnittliche Person hat.



    Für solche Zwecke ist ein Medianwert geeignet. Das heißt, Statistiken, bei denen die Hälfte der Stichprobenwerte weniger und die Hälfte mehr sind. Formeller: Wir ordnen die Werte des Musters der X = (x_1, ..., x_n)Reihe nach (x _ {[1]}, ..., x _ {[n]})und wählen sie mit einer Seriennummer ausEtage (n / 2). Eine solche Beurteilung hat mehrere Vorteile. Es ist weniger anfällig für den Einfluss fehlerhafter Daten, der Wert wird immer aus dem Satz stammen, der in der Stichprobe gefunden wurde, aber es gibt auch unangenehme Mängel, die Hauptursache ist die Schwierigkeit der Berechnung, selbst für ziemlich häufige Verteilungen gibt es keine allgemeine Berechnungsformel (genauer gesagt, es gibt sie, aber es ist schwierig) in die Praxis umgesetzt, siehe Verteilung der Ordnungszahlen ).




    Für eine bestimmte Stichprobe können wir die Daten immer sortieren und das mittlere Element daraus entnehmen. Das Problem ist jedoch, dass wir dazu alle Werte der Stichprobe gleichzeitig benötigen. In der Arbeit von Munro, Patterson (1980) wird ein Theorem aufgestellt, das besagt, dass nichts Besseres erdacht werden kann und es möglich ist, auseinander zu gehen.


    Aber was ist, wenn wir es uns nicht leisten können, einhundertmillionen Werte zu speichern? Einerseits können Sie die Aufgabe lösen, eine Million Zoll in 2 MB RAM zu sortieren . Andererseits liefert der oben erwähnte Artikel eine einfache Lösung, die mit einigen Annahmen und einer gewissen Wahrscheinlichkeit zur richtigen Lösung führt. Es wird nämlich der folgende Algorithmus vorgeschlagen.

    Munro-Paterson-Methode


    Es gebe einen Datenstrom von Länge N(bei diesem Algorithmus wäre es schön, die Länge des Stroms im Voraus zu kennen), den wir jeweils einzeln auslesen können. Wir haben SSpeicherzellen, S << Nund der Eingabestrom ist so ausgelegt, dass jede Permutation von N Elementen gleich wahrscheinlich ist. In diesem Fall liefert der Algorithmus mit etwas Glück den Medianwert.

    Der Algorithmus ist sehr einfach: Es werden zwei Zähler (l, h)und eine Teilstichprobe gespeichert, die aus nicht mehr als S-2Elementen der Eingabedaten besteht . Der Zähler lspeichert die Anzahl der Elemente, die kleiner als das Minimum im Unterabtastwert Zähler sindh- die Anzahl der Elemente, die größer als das Maximum sind. Das Teilbeispiel selbst enthält eine sortierte Liste, sodass das Finden eines Minimums und Maximums für eine Konstante funktioniert und das Einfügen eines Elements in linear ist S. Ausgeglichene Bäume geben Logarithmen für alle Operationen gegen eine geringe Gebühr für zusätzliches Speicherwachstum. Wenn der Platz für die Liste endet, werden die extremen Elemente herausgedrückt, um die Zähler auszugleichen l, h(wenn h> l, dann wird das minimale Element herausgedrückt und umgekehrt).

    Nach tausend Zufallszahlen bei S = 32können wir also folgendes Bild beobachten.



    Wenn Sie sich die Implementierung genau ansehen, wird die Bedeutung des Verweises auf „Glück, nicht Glück“ deutlich. Der Median sollte in den Wertebereich fallen, der im Speicher gespeichert ist. Der Artikel stellt die Einschätzung , dass es recht häufig , wenn geschieht Sproportional \ sqrt {N}, was wiederum bedeutet , dass wir auf jeden Fall über die Länge des Datenflusses, und auch in diesem Fall sein sollen, können uns sehr weit von dem wahren Wert sein.
    Dieser Algorithmus ist in erster Näherung gut, da nicht klar ist, was zu tun ist, wenn die Berechnung fehlgeschlagen ist, und noch nicht klar ist, wie sie parallelisiert werden soll.

    Weitere Forschungen gingen in Richtung einer ungefähren Berechnung des Medians, und die Idee der Annäherung ist sehr einfach: k-th Ordinalstatistik sind fast k-1Ordinalstatistik oderk + 1oder an die wir uns in der Nähe des gewünschten noch erinnern. Der Fehler bei der Schätzung des Medians wird im Verhältnis der Anzahl der Indizes, die wir „verfehlen“ können, zur nAnzahl der angezeigten Eingabedaten gemessen . Diese Fehler werden aufgerufen \ varepsilon n, wo \ varepsilon- zulässige Fehler behoben: zum Beispiel, \ varepsilon = 0,01wenn n = 1000Mittel , dass , wenn Sie die gesamte Probe halten würden, ist die resultierende mittlere Punktzahl zwischen den 495. und 505. sortierten Werten liegen würden. Wenn wir nur 9 Werte haben, kann das Gruppierungsbild wie folgt aussehen.



    Ungefähre Cannes-Greenwald-Methode


    Diese Methode basiert auf der Idee, SSpeicherzellen zu verwenden, verwendet jedoch den zugewiesenen Speicher, um alle Quantile auf einmal mit einer bestimmten \ varepsilon nGenauigkeit zu bewerten , die von der Größe des zulässigen Speichers abhängt.

    Die Daten werden in einem kartesischen Baum (der bemerkenswerterweise mit einer Reihe von Artikeln beschrieben wird ) gesammelt , der bei Erreichen des Grenzvolumens die Werte herausfiltert, so dass die angegebene Genauigkeit der Approximation erhalten bleibt, indem aggregierte Knoten erstellt werden.

    Der Baumknoten ist ein Tripel: der Wert der ursprünglichen Sequenz, die Anzahl der gruppierten Daten, die Erzeugung des Erscheinungsbilds dieses Werts in der ursprünglichen Stichprobe. Wenn es sich um den kartesischen Baum handelt, müssen wir auch die Funktion des Schlüssels und der Priorität bestimmen: Der Schlüssel ist der Wert selbst und die Priorität ist die Menge der aggregierten Daten in diesem Knoten (mit ein wenig Zufälligkeit, sodass Knoten mit der gleichen Anzahl aggregierter Werte gleichmäßiger auf Teilbäume verteilt sind).

    Die folgenden wichtigen Operationen können für einen solchen Baum definiert werden:
    • Hinzufügen eines neuen Werts für log (S);
    • Berechnungen des Medians und, wie leicht zu bemerken ist, eines beliebigen Quantils für linear in der SZeit;
    • Die Vereinigung der Bäume gleichzeitig wieder linear in der SZeit.

    Der Artikel gibt (ohne Beweis) einen Satz an, dass bei einem zufälligen Datensatz die Anzahl der Baumknoten proportional zunimmt log (S) / \ varepsilon, was bedeutet, dass der Algorithmus sehr kompakt und kontrovers sein muss.

    Beispiele


    Betrachten Sie als kleines Beispiel eine symmetrische und nicht symmetrische Verteilung mit einem bekannten Median. Um nicht zu weit zu gehen, sollten normale und logarithmische Normalverteilungen zu uns passen. Betrachten Sie die folgenden mittleren Schätzungen für eine Stichprobe von einer Million Werten:
    • Werte bestellen
    • Munro-Paterson-Methode mit gleichem Parameter s = \ sqrt {10 ^ 7}
    • Cannes-Greenwald-Methode mit Parameter \ varepsilon = 0,001

    Alle Schätzungen für jede Verteilung basieren auf denselben Datensätzen und werden 100 Mal wiederholt.



    Bei einer Normalverteilung sind der Mittelwert und der Median gleich, bei einer logarithmischen Normalverteilung sind sie sehr unterschiedlich und es macht keinen Sinn, den einen zur Bewertung des anderen zu verwenden (und es ist besser, das nie zu tun). Aus den gepaarten Bildern ist ersichtlich, dass die Ergebnisse der vollständigen Sortierung sehr oft mit der Munro-Paterson-Methode übereinstimmen, und dies ist richtig, aber es gibt immer noch ziemlich viele Fälle, in denen das Munro-Paterson-Ergebnis, wie im Artikel angegeben, vom wahren Ergebnis abweicht . Die Cannes-Greenwald-Methode liefert kein schlechtes, aber dennoch ein ungefähres Ergebnis. Es ist unten zu sehen, dass die Streuung aller Methoden vom wahren Wert ungefähr gleich ist.



    Das Cannes-Greenwald-Verfahren sollte sowohl im Speicher als auch in der Geschwindigkeit sehr sparsam sein, dh die Anzahl der im Baum gespeicherten Elemente ist proportional zum Logarithmus der Länge der Eingabesequenz und umgekehrt proportional zum Fehler \ varepsilon, und die Füllzeit ist proportional logN \ cdot loglogN.

    PS


    Implementierungsbeispiele finden Sie unter dem Link zu bitbucket , dies ist jedoch nicht die optimalste Implementierung.

    Bereits bei der Erstellung des Textes stellte ich fest, dass diese Artikel und Methoden im Verlauf von Algorithmen zur Verarbeitung von Streaming-Daten in POMI erwähnt werden.

    Danke an parpalak für den Editor.

    Jetzt auch beliebt: