Mengambil lebar minimum yang berisi fraksi tertentu dari semua nilai

Saya ingin menemukan batas min / max dari jendela geser ukuran minimum yang berisi fraksi tertentu dari jumlah elemen dalam array atau kumpulan angka.

Contoh: mengambil bilangan bulat untuk memudahkan menjelaskan, katakanlah proporsi elemen yang kami cari adalah 50% pada array ini:

[1,1,2,3,3,3,3,3,3,4,5,6,7,8,9,10]

Fungsi misteri akan mengembalikan sesuatu seperti (2, 4), yang berarti bahwa nilai minimum adalah 2 dan nilai maks adalah 4 (mari kita asumsikan itu inklusif dan perhatikan bahwa ini adalah VALUES, bukan indeks). Jendela kecil itu berisi 8 dari 16 nilai dan lebarnya hanya 2 unit, jendela tersempit yang mengandung setengah jumlah nilai.

Catatan: kuartilnya adalah [1,1,2,3], [3,3,3,3], [3,4,5,6], [7,8,9,10] sehingga mereka BUKAN apa yang saya sedang mencari.

Saya dapat mengkodekannya ... mungkin memerlukan waktu untuk membuatnya menyenangkan. Mudah-mudahan seseorang telah menemukan sebelumnya. Apakah itu mempunyai nama? Apakah ada metode yang sudah ada yang diketahui seseorang?

Saya tertarik dengan implementasi Python.

MEMPERBARUI:

Berkat Glen_b yang memberi nama 'short-half' dan 'interval terpendek' saya dapat menemukan ini: Temukan interval kerapatan probabilitas

Berita utama:

• Kata kunci singkat .

• Untuk implementasi R dan tautan ke proyek saat ini dengan publikasi, lihat halaman Günther Sawitzki di http://www.statlab.uni-heidelberg.de/people/gs/

• Ada implementasi Stata, yang dapat diinstal oleh ssc inst shorth.

Lebih lambat, dan tanpa berusaha melakukan keadilan terhadap pekerjaan Sawitzki:

Statistik urutan sampel$n$ nilai dari$x$ didefinisikan oleh

$x_{(1)} \le x_{(2)} \le \cdots \le x_{(n-1)} \le x_{(n)}.$

Membiarkan $h = \lfloor n / 2\rfloor$. Kemudian separuh data terpendek dari peringkat$k$ ke peringkat $k + h$ diidentifikasi untuk meminimalkan $x_{(k + h)} - x_{(k)}$ lebih $k = 1, \cdots, n - h$. Interval ini kita sebut panjang setengah terpendek.

Tulisan pendek itu dinamai oleh JW Tukey dan diperkenalkan dalam studi kekokohan Princeton tentang penduga lokasi oleh Andrews, Bickel, Hampel, Huber, Rogers dan Tukey (1972, p.26) sebagai mean dari $x_{(k)}, \cdots, x_{(k + h)}$. Ini menarik perhatian untuk sifat asimptotik yang tidak biasa (hal.50-52): pada mereka, lihat juga akun kemudian dari Shorack dan Wellner (1986, hal.767-771) dan Kim dan Pollard (1990). Kalau tidak cepat menghilang dari pandangan selama sekitar satu dekade. Secara kebetulan, Hampel (1997) menunjukkan bahwa hasil yang tersedia untuk studi Princeton pada situasi asimetris, tetapi tidak sepenuhnya dianalisis pada saat itu, menempatkan cahaya lebih baik daripada yang dihargai.

Minat dihidupkan kembali dalam ide-ide seperti ketika Rousseeuw (1984), membangun saran oleh Hampel (1975), menunjukkan bahwa titik tengah dari setengah terpendek $(x_{(k)} + x_{(k + h)}) / 2$ adalah penduga lokasi median kuadrat (LMS) terkecil untuk $x$. Lihat Rousseeuw (1984) dan Rousseeuw dan Leroy (1987) untuk aplikasi LMS dan ide-ide terkait untuk regresi dan masalah lainnya. Perhatikan bahwa titik tengah LMS ini juga disebut sebagai singkatan dalam beberapa literatur terbaru (misalnya David dan Nagaraja 2003, hal.223; Maronna, Martin dan Yohai 2006, hal.48). Selanjutnya, bagian terpendek itu sendiri juga kadang-kadang disebut singkatan, seperti yang ditunjukkan oleh judul Grübel (1988).

Panjang bagian terpendek adalah ukuran yang kuat untuk skala atau penyebaran: lihat Rousseeuw dan Leroy (1988), Grübel (1988), Rousseeuw dan Croux (1993) dan Martin and Zamar (1993) untuk analisis dan diskusi lebih lanjut.

Panjang setengah terpendek dalam Gaussian (normal) dengan rata-rata 0 dan standar deviasi 1 adalah 1,349 hingga 3 dp Dengan demikian untuk memperkirakan standar deviasi dari panjang yang diamati, bagi dengan panjang Gaussian ini.

Beberapa komentar umum mengikuti keuntungan dan kerugian dari setengah ide terpendek, dari sudut pandang analis data praktis, seperti halnya ahli statistik matematika atau teoretis. Apa pun proyeknya, akan selalu bijaksana untuk membandingkan hasil singkat dengan ukuran ringkasan standar (termasuk cara lain, terutama cara geometris dan harmonik) dan untuk menghubungkan hasil dengan grafik distribusi. Selain itu, jika minat Anda adalah pada keberadaan atau tingkat bimodality atau multimodality, akan lebih baik untuk melihat langsung pada estimasi fungsi kepadatan yang dihaluskan.

• Kesederhanaan Gagasan setengah terpendek adalah sederhana dan mudah dijelaskan kepada siswa dan peneliti yang tidak menganggap diri mereka sebagai spesialis statistik. Ini mengarah langsung ke dua ukuran lokasi dan satu penyebaran yang cukup intuitif. Hal ini juga relatif setuju untuk perhitungan tangan dengan alat primitif (pensil dan kertas, kalkulator, spreadsheet).

• Koneksi Persamaan dan perbedaan antara panjang bagian terpendek, kisaran interkuartil dan deviasi absolut median dari median (MAD) (atau dalam hal ini kemungkinan kesalahan) bersifat langsung. Dengan demikian, setengah ide terpendek terkait dengan ide statistik lain yang seharusnya sudah akrab bagi banyak analis data.

• Interpretasi grafis Setengah terpendek dapat dengan mudah dihubungkan dengan tampilan distribusi standar seperti distribusi kumulatif dan plot kuantil, histogram, dan plot batang dan daun.

• Mode Dengan rata-rata di mana data terpadat, garis pendek dan juga titik tengah LMS memperkenalkan rasa mode ke ringkasan lokasi. Ketika diterapkan pada distribusi yang kira-kira simetris, garis pendek akan dekat dengan rata-rata dan median, tetapi lebih tahan daripada rata-rata untuk outlier di kedua ekor dan lebih efisien daripada median untuk distribusi dekat Gaussian (normal) dalam bentuk. Ketika diterapkan pada distribusi yang unimodal dan asimetris, singkatan dan LMS biasanya akan lebih dekat ke mode daripada rata-rata atau median. Perhatikan bahwa gagasan memperkirakan mode sebagai titik tengah interval terpendek yang berisi jumlah pengamatan tetap kembali setidaknya ke Dalenius (1965). Lihat juga Robertson dan Cryer (1974), Bickel (2002) dan Bickel dan Frühwirth (2006) tentang penduga lain mode. Pengukur mode setengah-sampel Bickel dan Frühwirth sangat menarik sebagai pilihan rekursif dari setengah terpendek. Pengguna stata dapat mengunduh implementasi Stata olehssc inst hsmode.

• Identifikasi outlier Standardisasi yang tahan seperti (nilai - pendek) / panjang dapat membantu dalam mengidentifikasi outlier. Untuk diskusi tentang ide-ide terkait, lihat Carey et al. (1997) dan termasuk referensi.

• Generalisasi ke fraksi terpendek Idenya dapat digeneralisasi ke proporsi selain dari setengah.

Pada saat yang sama, perhatikan itu

• Tidak berguna untuk semua distribusi Ketika diterapkan pada distribusi yang kira-kira berbentuk-J, singkatan akan mendekati rata-rata dari bagian bawah data dan titik tengah LMS akan lebih tinggi. Ketika diterapkan pada distribusi yang kira-kira berbentuk U, garis pendek dan titik tengah LMS akan berada di dalam setengah dari distribusi yang memiliki kepadatan rata-rata yang lebih tinggi. Tidak ada perilaku yang tampak sangat menarik atau berguna, tetapi sama-sama ada sedikit panggilan untuk ringkasan seperti mode tunggal untuk distribusi berbentuk-J atau berbentuk-U; untuk bentuk J, mode adalah, atau seharusnya, minimum dan untuk bentuk U, bimodality membuat gagasan tentang mode moot tunggal, jika tidak valid.

• Dasi Setengah terpendek mungkin tidak didefinisikan secara unik. Bahkan dengan data yang diukur, pembulatan nilai yang dilaporkan sering kali dapat menimbulkan ikatan. Apa yang harus dilakukan dengan dua atau lebih bagian terpendek telah sedikit dibahas dalam literatur. Perhatikan bahwa belahan yang diikat dapat tumpang tindih atau terpisah. Implementasi yang berbeda dapat mengatasi ini dengan cara yang sedikit berbeda.

• Dasar pemikiran untuk panjang jendela Mengapa setengah berarti$1 + \lfloor n / 2\rfloor$juga tampaknya tidak dibahas. Jelas kita membutuhkan aturan yang menghasilkan panjang jendela untuk ganjil dan genap$n$; lebih disukai aturannya sederhana; dan biasanya ada sedikit kesewenang-wenangan dalam memilih aturan semacam ini. Penting juga bahwa aturan apa pun berlaku wajar untuk yang kecil$n$: bahkan jika suatu program tidak sengaja dipanggil untuk ukuran sampel yang sangat kecil, prosedur yang digunakan harus masuk akal untuk semua ukuran yang mungkin. Perhatikan bahwa, dengan aturan ini, diberikan$n = 1$ singkat hanya nilai sampel tunggal, dan diberikan $n = 2$singkatan adalah rata-rata dari dua nilai sampel. Rincian lebih lanjut tentang aturan ini adalah bahwa ia selalu mendefinisikan sedikit mayoritas, sehingga menegakkan keputusan demokratis tentang data. Namun, sepertinya tidak ada alasan kuat untuk tidak menggunakannya$\lceil n / 2\rceil$ sebagai aturan yang bahkan lebih sederhana, kecuali bahwa semua penulis pada singkatan tampaknya telah mengikuti $1 + \lfloor n / 2\rfloor$.

• Gunakan dengan data terbobot. Identifikasi setengah terpendek tampaknya akan memperpanjang hanya agak berantakan untuk situasi di mana pengamatan terkait dengan bobot yang tidak sama.

• Panjang ketika sebagian besar nilai identik Ketika setidaknya setengah dari nilai dalam sampel sama dengan beberapa konstanta, panjang setengah terpendek adalah 0. Jadi, misalnya, jika sebagian besar nilai 0 dan beberapa lebih besar, panjang terpendek setengahnya tidak terlalu berguna sebagai ukuran skala atau penyebaran.

Andrews, DF, PJ Bickel, FR Hampel, PJ Huber, WH Rogers dan JW Tukey. 1972. Perkiraan lokasi yang kuat: survei dan uang muka. Princeton, NJ: Princeton University Press.

Bickel, DR 2002. Penduga kuat mode dan kecenderungan data kontinu. Statistik Komputasi & Analisis Data 39: 153-163.

Bickel, DR dan R. Frühwirth. 2006. Tentang penaksir mode yang cepat dan tangguh: perbandingan dengan penaksir lainnya dengan aplikasi. Statistik Komputasi & Analisis Data 50: 3500-3530.

Carey, VJ, EE Walters, Taruhan CG dan BA Rosner. 1997. Penolakan outlier yang tahan dan berbasis tes: efek pada Gaussian satu dan dua sampel inferensi. Technometrics 39: 320-330.

Christmann, A., U. Gather dan G. Scholz. 1994. Beberapa properti dengan panjang setengah terpendek. Statistica Neerlandica 48: 209-213.

Dalenius, T. 1965. Mode - Parameter statistik yang diabaikan. Jurnal, Royal Statistics Society A 128: 110-117.

Grübel, R. 1988. Panjang tulisan singkat. Annals of Statistics 16: 619-628.

Hampel, FR 1975. Di luar parameter lokasi: konsep dan metode yang kuat. Buletin, Institut Statistik Internasional 46: 375-382.

Hampel, FR 1997. Beberapa catatan tambahan tentang "tahun ketahanan Princeton". Dalam Brillinger, DR, LT Fernholz dan S. Morgenthaler (eds) Praktik analisis data: esai untuk menghormati John W. Tukey. Princeton, NJ: Princeton University Press, 133-153.

Kim, J. dan D. Pollard. 1990. Asimptotik akar kubus. Annals of Statistics 18: 191-219.

Maronna, RA, RD Martin dan VJ Yohai. 2006. Statistik yang kuat: teori dan metode. Chichester: John Wiley.

Martin, RD dan RH Zamar. 1993. Bias estimasi skala yang kuat. Annals of Statistics 21: 991-1017.

Robertson, T. dan JD Cryer. 1974. Prosedur berulang untuk memperkirakan mode. Jurnal, Asosiasi Statistik Amerika 69: 1012-1016.

Rousseeuw, PJ 1984. Setidaknya median regresi kotak. Jurnal, Asosiasi Statistik Amerika 79: 871-880.

Rousseeuw, PJ dan C. Croux. 1993. Alternatif untuk median deviasi absolut. Jurnal, Asosiasi Statistik Amerika 88: 1273-1283.

Rousseeuw, PJ dan AM Leroy. 1987. Regresi yang kuat dan deteksi outlier. New York: John Wiley.

Rousseeuw, PJ dan AM Leroy. 1988. Estimator skala kuat berdasarkan setengah terpendek. Statistica Neerlandica 42: 103-116.

Shorack, GR dan JA Wellner. 1986. Proses empiris dengan aplikasi ke statistik. New York: John Wiley.