Gibt es Algorithmen oder Datenstrukturen, die den Medianwert einer Menge ermitteln müssen?

14

Ich habe dieses Buch für meine Klasse Randomized Algorithms gelesen . In diesem Buch gibt es einen ganzen Abschnitt, der sich mit der Ermittlung des Medians eines Arrays durch Zufallsauswahl befasst und zu einem effizienteren Algorithmus führt. Jetzt wollte ich wissen, ob es neben einer theoretischen Verbesserung auch praktische Anwendungen dieses Algorithmus auf dem Gebiet der Informatik gibt. Gibt es Algorithmen oder Datenstrukturen, die den Median eines Arrays ermitteln müssen?

runtime-analysis randomized-algorithms Sharan Duggirala
quelle

3

Vielleicht möchten Sie einen Blick auf Quicksort werfen: Wenn Sie den Median als Pivot wählen, kann der ungünstigste Fall vermieden werden (Laufzeit im ungünstigsten Fall = O (n log n) anstelle von O (n ^ 2)) und die Rekursionstiefe beträgt minimiert (log2 (n)).

Hoffmale

1

@hoffmale: Aber das erfordert nicht, dass Sie den Median finden. Sie müssen einen Wert finden, der dem Median angemessen nahe kommt. Wenn Sie beispielsweise einen Drehpunkt finden, der nicht innerhalb der oberen 5% oder unteren 5% liegt, ist O (n log n) garantiert.

gnasher729

1

@ gnasher729: aber das minimiert nicht die Rekursionstiefe. Beide Eigenschaften sind wichtig, z. B. in einer ressourcenbeschränkten Echtzeitumgebung.

Hoffmale

@hoffmale übrigens ist die übliche Notation für den Logarithmus zur Basis 2 (insbesondere unter Informatikern) einfach "lg" wie in (lg (n)).

Wildcard

@ gnasher729 Da es sich um stochastische Algorithmen handelt, ist dies (= ziemlich nahe) wahrscheinlich genau das, was diese Algorithmen tun.

Konrad Rudolph

17

ob es neben einer theoretischen Verbesserung praktische Anwendungen dieses Algorithmus auf dem Gebiet der Informatik gibt

Die Anwendung dieses Algorithmus ist trivial - Sie verwenden ihn immer dann, wenn Sie einen Median eines Datensatzes (also eines Arrays) berechnen möchten . Diese Daten können aus verschiedenen Bereichen stammen: astronomische Beobachtungen, Sozialwissenschaften, biologische Daten usw.

Es ist jedoch erwähnenswert, wann der Median dem Mittelwert (oder Modus) vorzuziehen ist. Grundsätzlich sind in der deskriptiven Statistik Mittelwert, Modus und Median gleich, dh sie stimmen überein, wenn unsere Daten vollkommen normalverteilt sind. Wenn andererseits unsere Daten verzerrt sind, dh die Häufigkeitsverteilung für unsere Daten ist (links / rechts) verzerrt, liefert der Mittelwert nicht den besten zentralen Ort, weil die Verzerrung ihn vom typischen Wert nach links oder rechts wegzieht Während der Median nicht so stark von den verzerrten Daten beeinflusst wird, behält er diese Position am besten bei und zeigt auf einen typischen Wert. Daher ist es möglicherweise besser, einen Median zu berechnen, wenn Sie mit verzerrten Daten arbeiten.

Auch beim maschinellen Lernen werden häufig statistische Methoden eingesetzt, zum Beispiel $k$ -medians-Clustering .

fade2black
quelle

Vielen Dank! Das ist sehr hilfreich! Gibt es noch andere Algorithmen oder Techniken, die zum Finden eines Medians erforderlich sind?

Sharan Duggirala

5

Obwohl dies ausreichend ist (+1), werden die Daten in der angewandten Statistik häufig vor dem Auffinden des Medians sortiert, da in vielen oder sogar den meisten Kontexten, in denen der Median gewünscht wird, zumindest einige der anderen Ordnungen vorhanden sind Statistiken.

John Coleman

1

Interessant. Ich habe von

means clustering gehört, aber nicht von

-medians clustering.

k

$k$

k

$k$

Svick

13

Medianfilterung ist bei der Reduzierung bestimmter Arten von Bildrauschen in der Bildverarbeitung üblich. Besonders Salz- und Pfeffergeräusche. Dies funktioniert, indem der Medianwert in jedem Farbkanal in jeder lokalen Umgebung des Bildes ausgewählt und durch diesen ersetzt wird. Wie groß diese Nachbarschaften sind, kann variieren. Beliebte Filtergrößen (Nachbarschaften) sind beispielsweise 3x3 und 5x5 Pixel.

mathreadler
quelle

1

Median bezieht sich nicht nur auf Bildrauschen, sondern auch auf Rauschen bei nahezu allen Sensormessungen, von denen Kameras nur eine Art von Sensor sind. Schulbücher zeigen schöne Sinus- und Rechteckwellenformen, mit denen man arbeiten kann. In der realen Welt kommen solche sauberen Daten so gut wie nie vor. Wenn dies der Fall ist, liegt dies fast immer daran, dass sich jemand anderes um das Glätten der Daten gekümmert hat, bevor Sie darauf zugreifen konnten. B. von typischeren Sensorlesedaten, für die Sie den "richtigen" Wert auswählen müssen: (1, 3, 5, 65, 68, 70, 75, 80, 82, 85, 540, 555). Ich habe die Daten sortiert, um sie verständlicher zu machen.

Dunk

1

Ja, du hast recht. Aber es wäre eine sehr lange und langweilige Antwort, wenn wir alle kleinen Dinge in der Signalverarbeitung aufschreiben würden, wo sie verwendet werden können.

mathreadler

1

Mediane in der Bildverarbeitung können auch pro Pixel mit Sequenzen von 5 oder mehr Fotos verwendet werden. Dies ist eine Möglichkeit, das zeitliche Rauschen (auch bekannt als Touristen, die die Sicht blockieren) zu

beseitigen

@HagenvonEitzen Du hast recht! Eigentlich habe ich vor ein paar Tagen an etwas ganz Ähnliches gedacht. Viele Touristen rund um ...

mathreadler

10

Bei randomisierten Algorithmen ist die Berechnung des Medians besonders wichtig.

$\tfrac34$ $1\pm\epsilon$ $A$ $\tfrac34$ $k$ $A(1\pm\epsilon)$ $k$ $A(1-\epsilon)$ $A(1+\epsilon)$ $k$

$2^n$ $n$

David Richerby
quelle

5

Der Median der Mediane hat einige Anwendungen:

$O(n \log n)$
$O(n)$ $O(n^2)$

Odo Frodo
quelle

1

Die Verwendung des Median-of-Medians zur Auswahl eines Pivots für Quicksort verlangsamt den Algorithmus in der Praxis sehr wahrscheinlich, da die Cache-Lokalität vollständig zerstört wird, was der Hauptbeitrag zur Schnelligkeit von Quicksort ist. Aber Ihr Kommentar zur Worst-Case-Komplexität ist natürlich richtig.

wchargin

@wchargin Welche Alternativen schlagen Sie vor? Keine praktische QuickSort-Implementierung, von der ich weiß, verwendet einen cachesensitiven Pivot, da dies mit einer fürchterlichen Worst-Case-Laufzeit zu tun hat. In dem wegweisenden Artikel „Engineering a sort function“ werden Alternativen erörtert, von denen keine Cache-fähig ist (und die dennoch die naive Pivot-Auswahl übertreffen).

Konrad Rudolph

1

@wchargin… Beantwortung meiner eigenen Frage: Java 7 hat auf ein neues Dual-Pivot-Verfahren umgestellt, das mir nicht bekannt war. Das ist faszinierend und könnte Median-Pivot-Algorithmen überflüssig machen.

Konrad Rudolph

Gibt es Algorithmen oder Datenstrukturen, die den Medianwert einer Menge ermitteln müssen?

Antworten: