Apakah ada algoritma atau struktur data yang perlu menemukan nilai median dari suatu set?

14

Saya telah membaca buku ini untuk kelas saya, Randomized Algorithms. Dalam buku khusus ini, ada seluruh bagian yang didedikasikan untuk menemukan median array menggunakan seleksi acak, yang mengarah ke algoritma yang lebih efisien. Sekarang, saya ingin tahu apakah ada aplikasi praktis dari algoritma ini, dalam domain ilmu komputer, selain peningkatan teoritis. Apakah ada algoritma atau struktur data yang perlu menemukan median array?

runtime-analysis randomized-algorithms Sharan Duggirala
sumber

3

Anda mungkin ingin melihat quicksort: Dengan memilih median sebagai poros, kasus terburuknya dapat dihindari (runtime kasus terburuk = O (n log n) alih-alih O (n ^ 2)) dan kedalaman rekursi akan menjadi diminimalkan (log2 (n)).

hoffmale

1

@offmale: Tapi itu tidak mengharuskan Anda untuk menemukan median. Ini mengharuskan Anda untuk menemukan nilai yang cukup dekat dengan median. Misalnya, menemukan pivot yang tidak dalam jaminan 5% atas atau bawah 5% O (n log n).

gnasher729

1

@ gnasher729: tapi itu tidak akan meminimalkan kedalaman rekursi. Kedua sifat itu penting, misalnya dalam lingkungan waktu nyata terbatas sumber daya.

hoffmale

@offmale, kebetulan, notasi yang biasa untuk logaritma basis 2 (khususnya di kalangan ilmuwan komputer) hanyalah "lg" seperti pada (lg (n)).

Wildcard

@ gnasher729 Karena topiknya adalah algoritma stokastik, ini (= cukup dekat) mungkin tepat apa yang dilakukan algoritma ini.

Konrad Rudolph

17

jika ada aplikasi praktis dari algoritma ini dalam domain ilmu komputer selain menjadi perbaikan teoritis

Aplikasi dari algoritma ini sepele - Anda menggunakannya kapan pun Anda ingin menghitung a median dari set data (array dengan kata lain). Data ini dapat berasal dari domain yang berbeda: pengamatan astronomi, ilmu sosial, data biologis, dll.

Namun, perlu disebutkan kapan lebih suka median berarti (atau mode). Pada dasarnya, dalam statistik deskriptif, ketika data kami terdistribusi normal maka mean, mode, dan median adalah sama, yaitu bertepatan. Di sisi lain, ketika data kami condong, yaitu distribusi frekuensi untuk data kami (kiri / kanan) condong, berarti gagal memberikan lokasi pusat terbaik karena kemiringan menyeretnya menjauh dari nilai khas ke kiri atau kanan , sementara median tidak begitu kuat dipengaruhi oleh data yang miring, dan dengan demikian mempertahankan posisi ini dengan menunjuk pada nilai yang khas. Dengan demikian menghitung median mungkin lebih disukai ketika Anda berurusan dengan data yang miring.

Juga, pembelajaran mesin adalah tempat metode statistik banyak digunakan, misalnya pengelompokan median $k$ .

fade2black
sumber

Terima kasih! Itu sangat membantu! Adakah algoritma atau teknik lain yang mungkin perlu mencari median?

Sharan Duggirala

5

Meskipun ini cukup benar (+1), lebih sering daripada tidak dalam statistik terapan data akan disortir sebelum menemukan median, karena dalam banyak atau bahkan sebagian besar konteks di mana median diinginkan, jadi setidaknya beberapa dari urutan lain statistik.

John Coleman

1

Menarik. Saya telah mendengar tentang

berarti pengelompokan, tetapi bukan tentang pengelompokan

median.

k

$k$

k

$k$

svick

13

Pemfilteran median umum terjadi dalam pengurangan jenis noise tertentu dalam pemrosesan gambar. Terutama suara garam dan merica. Ini bekerja dengan memilih nilai median di setiap saluran warna di setiap lingkungan lokal gambar dan menggantinya. Seberapa besar lingkungan ini dapat bervariasi. Ukuran filter populer (lingkungan) misalnya 3x3 dan 5x5 piksel.

pembaca matematika
sumber

1

Median berlaku tidak hanya untuk noise dalam gambar tetapi noise pada hampir semua pembacaan sensor, di mana kamera hanyalah satu jenis sensor. Buku Pelajaran Sekolah menunjukkan bentuk gelombang sinusoidal dan persegi yang bagus untuk digunakan. Di dunia nyata data bersih seperti itu hampir tidak pernah terjadi. Jika ya, itu hampir selalu karena orang lain mengurus kelancaran data sebelum Anda mendapatkannya. mis. dari data pembacaan sensor yang lebih tipikal dimana Anda perlu memilih nilai "benar": (1, 3, 5, 65, 68, 70, 75, 80, 82, 85, 540, 555). Saya mengurutkan data untuk membuatnya lebih jelas.

Dunk

1

Ya kamu benar. Tapi itu akan membuat jawaban yang sangat panjang dan membosankan jika kita menuliskan semua hal kecil dalam pemrosesan sinyal di mana ia dapat digunakan.

mathreadler

1

Median dalam pemrosesan gambar juga dapat digunakan per piksel dengan urutan 5 atau lebih foto, yang merupakan cara untuk menghilangkan suara sementara (alias turis yang menghalangi pandangan)

Hagen von Eitzen

@HagenvonEitzen Anda benar! Sebenarnya saya memikirkan sesuatu yang sangat mirip hanya beberapa hari yang lalu. Banyak turis di sekitar ...

mathreadler

10

Komputasi median sangat penting dalam algoritma acak.

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

$2^n$ $n$ ke waktu berjalan.

David Richerby
sumber

5

The median median memiliki beberapa aplikasi:

Menemukan pivot untuk quicksort, yang membawa kompleksitas waktu terburuknya ke $O(n \log n)$ .
Menemukan pivot untuk pemilihan cepat, menjadikannya kompleksitas waktu terburuk $O(n)$ dari $O(n^2)$ .

Odo Frodo
sumber

1

Sebenarnya menggunakan median-of-median untuk memilih pivot untuk quicksort tampaknya sangat mungkin memperlambat algoritma dalam praktek, karena itu benar-benar membunuh lokalitas cache, yang merupakan kontribusi utama untuk kecepatan quicksort. Tetapi komentar Anda tentang kompleksitas kasus terburuk tentu saja benar.

wchargin

@wchargin Apa alternatif yang Anda sarankan? Tidak ada implementasi quicksort praktis yang saya tahu menggunakan pivot yang sensitif terhadap cache, karena melakukan hal itu memperdagangkan runtime terburuk yang mengerikan. Makalah “Rekayasa fungsi pengurutan” membahas alternatif, dan tidak satu pun dari mereka yang sadar cache (dan tetap mengungguli pemilihan pivot naif).

Konrad Rudolph

1

@wchargin … answering my own question: Java 7 switched to a new dual-pivot procedure that I was unaware of. This is intriguing and might render median pivot algorithms obsolete.

Konrad Rudolph

Apakah ada algoritma atau struktur data yang perlu menemukan nilai median dari suatu set?

Jawaban: