Czy są jakieś algorytmy lub struktury danych, które muszą znaleźć medianę wartości zbioru?

14

Czytałem tę książkę dla mojej klasy, Randomized Algorytmy. W tej książce znajduje się cała sekcja poświęcona znalezieniu mediany tablicy za pomocą losowego wyboru, co prowadzi do bardziej wydajnego algorytmu. Teraz chciałem wiedzieć, czy istnieją jakieś praktyczne zastosowania tego algorytmu w dziedzinie informatyki, oprócz teoretycznej poprawy. Czy są jakieś algorytmy lub struktury danych, które muszą znaleźć medianę tablicy?

runtime-analysis randomized-algorithms Sharan Duggirala
źródło

3

Możesz rzucić okiem na Quicksort: Wybierając medianę jako oś przestawną, można uniknąć jego najgorszego przypadku (najgorszy przypadek = O (n log n) zamiast O (n ^ 2)), a głębokość rekurencji będzie wynosić zminimalizowane (log2 (n)).

hoffmale,

1

@hoffmale: Ale to nie wymaga znalezienia mediany. Wymaga to znalezienia wartości zbliżonej do mediany. Na przykład znalezienie punktu obrotu, który nie mieści się w górnej 5% lub dolnej 5%, gwarantuje O (n log n).

gnasher729,

1

@ gnasher729: ale to nie zminimalizuje głębokości rekurencji. Obie właściwości są ważne, np. W środowisku ograniczonym zasobami w czasie rzeczywistym.

hoffmale

@ hoffmale, nawiasem mówiąc, zwykłą notacją dla logarytmu podstawowego 2 (szczególnie wśród informatyków) jest po prostu „lg” jak w (lg (n)).

Wildcard

@ gnasher729 Ponieważ tematem są algorytmy stochastyczne, to (= rozsądnie blisko) jest prawdopodobnie dokładnie tym, co robią te algorytmy.

Konrad Rudolph

17

czy istnieją jakieś praktyczne zastosowania tego algorytmu w dziedzinie informatyki, oprócz tego, że jest to poprawa teoretyczna

Zastosowanie tego algorytmu jest trywialne - używasz go, gdy chcesz obliczyć medianę zbioru danych (innymi słowy tablica). Dane te mogą pochodzić z różnych dziedzin: obserwacje astronomiczne, nauki społeczne, dane biologiczne itp.

Warto jednak wspomnieć, kiedy należy preferować medianę (lub tryb). Zasadniczo, w statystykach opisowych, gdy nasze dane są całkowicie normalnie rozłożone, wówczas średnia, tryb i mediana są równe, tzn. Pokrywają się. Z drugiej strony, gdy nasze dane są przekrzywione, tj. Rozkład częstotliwości dla naszych danych jest (skręcony w lewo / w prawo), średnia nie zapewnia najlepszej centralnej lokalizacji, ponieważ skośność odciąga ją od typowej wartości w lewo lub w prawo , podczas gdy skośne dane nie mają tak silnego wpływu na medianę, dlatego najlepiej zachować tę pozycję wskazując na typową wartość. Dlatego obliczenie mediany może być preferowane w przypadku wypaczonych danych.

Ponadto, uczenie maszynowe, gdzie są mocno wykorzystywane metody statystyczne, na przykład -medians klastrów $k$ .

fade2black
źródło

Dziękuję Ci! To jest bardzo pomocne! Jakieś inne algorytmy lub techniki, które mogą wymagać znalezienia mediany?

Sharan Duggirala

5

Chociaż jest to wystarczająca prawda (+1), najczęściej w statystyce stosowanej dane byłyby sortowane przed znalezieniem mediany, ponieważ w wielu, a nawet w większości kontekstów, w których mediana jest pożądana, podobnie jest z niektórymi innymi porządkami Statystyka.

John Coleman

1

Ciekawy. Słyszałem o grupowaniu

średnich, ale nie o grupowaniu

średnich.

k

$k$

k

$k$

svick

13

Mediana filtrowania jest powszechna w redukcji niektórych rodzajów szumów podczas przetwarzania obrazu. Szczególnie hałas solny i pieprzowy. Działa poprzez wybranie wartości mediany w każdym kanale kolorów w każdym lokalnym sąsiedztwie obrazu i zastąpienie go nią. Jak duże są te dzielnice, mogą się różnić. Popularne rozmiary filtrów (dzielnice) to na przykład 3x3 i 5x5 pikseli.

matematyk
źródło

1

Mediana dotyczy nie tylko szumu na obrazie, ale szumu w prawie wszystkich odczytach czujnika, z których kamery są tylko jednym rodzajem czujnika. Podręczniki szkolne pokazują ładne sinusoidalne i kwadratowe kształty fali do pracy. W prawdziwym świecie takie czyste dane prawie nigdy się nie zdarzają. Jeśli tak, prawie zawsze dzieje się tak, ponieważ ktoś inny zajął się wygładzeniem danych, zanim je uzyskasz. np. bardziej typowych danych odczytu czujnika, których należy wybrać „prawidłową” wartość: (1, 3, 5, 65, 68, 70, 75, 80, 82, 85, 540, 555). Posortowałem dane, aby było bardziej oczywiste.

Dunk

1

Tak masz rację. Byłoby to jednak bardzo długą i nudną odpowiedzią, gdybyśmy zapisali wszystkie małe rzeczy w przetwarzaniu sygnału, gdzie można go użyć.

mathreadler

1

Mediany w przetwarzaniu obrazu mogą być również stosowane na piksel z sekwencjami około 5 zdjęć, co jest sposobem na pozbycie się szumów czasowych (czyli turystów blokujących widok)

Hagen von Eitzen

@HagenvonEitzen Masz rację! Właściwie kilka dni temu myślałem o czymś podobnym. Wielu turystów wokół ...

matematyk

10

Obliczanie median jest szczególnie ważne w algorytmach losowych.

Dość często mamy algorytm aproksymacyjny, który przynajmniej z prawdopodobieństwem $\tfrac34$ $1\pm\epsilon$ $A$ $\tfrac34$ $k$ $A(1\pm\epsilon)$ $k$ $A(1-\epsilon)$ $A(1+\epsilon)$ $k$

$2^n$ $n$ do czasu pracy.

David Richerby
źródło

5

The Mediana median ma pewne wnioski:

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

Odo Frodo
źródło

1

W rzeczywistości użycie median-median do wybrania elementu przestawnego do szybkiego sortowania wydaje się bardzo prawdopodobne, że w praktyce spowolni algorytm, ponieważ całkowicie zabija lokalizację pamięci podręcznej, co jest głównym czynnikiem przyczyniającym się do szybkości szybkiego sortowania. Ale twój komentarz na temat złożoności najgorszego przypadku jest oczywiście poprawny.

wchargin

@wchargin Jakie alternatywy sugerujesz? Żadna praktyczna implementacja Quicksort, o której wiem, nie wykorzystuje przestawnej pamięci podręcznej, ponieważ powoduje to okropne działanie w najgorszym przypadku. Przełomowy artykuł „Inżynieria funkcji sortowania” omawia alternatywy, a żadna z nich nie uwzględnia pamięci podręcznej (a jednak przewyższa naiwny wybór osi przestawnych).

Konrad Rudolph

1

@wchargin… odpowiadając na moje pytanie: Java 7 przeszła na nową procedurę podwójnego obrotu, o której nie wiedziałem. Jest to intrygujące i może spowodować, że średnie algorytmy przestawne stają się przestarzałe.

Konrad Rudolph

Czy są jakieś algorytmy lub struktury danych, które muszą znaleźć medianę wartości zbioru?

Odpowiedzi: