Meminimalkan Jumlah Deviasi Absolut ( Jarak

15

Saya memiliki kumpulan data $x_{1}, x_{2}, \ldots, x_{k}$ dan ingin mencari parameter $m$ sedemikian sehingga meminimalkan jumlah

\sum_{saya = 1}^{k} | m - x_{saya} | .

$\sum_{i=1}^{k}\big|m-x_i\big|.$ itu adalah

min_{m} \sum_{saya = 1}^{k} | m - x_{saya} | .

$\min_{m}\sum_{i=1}^{k}\big|m-x_i\big|.$

optimization convex-optimization mayenew
sumber

2

Bisakah Anda menguraikan sedikit?

Geoff Oxberry

Dalam hal itu, bukankah solusinya akan menjadi titik tengah antara nilai maksimum dan minimum?

Paul

@ Paul median dapat meminimalkan jumlah tetapi ingin tahu bagaimana hal itu dapat dilakukan secara analitis, khususnya l1-minimisasi

mayenew

@adu itu benar, median adalah solusinya. Menghitung median secara analitik adalah sepele; hanya mengurutkan dan kemudian mengambil nilai tengah.

David Ketcheson

22

Mungkin Anda meminta bukti bahwa median memecahkan masalah? Nah, ini bisa dilakukan seperti ini:

Tujuannya adalah linear sedikit demi sedikit dan karenanya dapat dibedakan kecuali untuk poin . Apa kemiringan tujuan adalah beberapa titik ? Nah, kemiringan adalah jumlah dari lereng pemetaan dan ini adalah baik (untuk ) atau (untuk ). Oleh karena itu, kemiringan menunjukkan berapa lebih kecil dari $m=x_i$ $m\neq x_i$ $m\mapsto |m-x_j|$ $+1$ $m>x_j$ $-1$ $m<x_j$ $x_i$ $m$ . Anda melihat bahwa kemiringan adalah nol jika ada banyak lebih kecil dan lebih besar dari (untuk dan bahkan jumlah ). Jika ada ganjil 's maka lereng adalah kiri 'middlest' satu dan kanan itu, maka middlest satu adalah minimum. $x_i$ $m$ $x_i$ $x_i$ $-1$ $+1$

Beladau
sumber

16

Generalisasi masalah ini ke beberapa dimensi disebut masalah median geometris . Seperti yang ditunjukkan David, median adalah solusi untuk kasus 1-D; di sana, Anda bisa menggunakan algoritme seleksi penemuan-median , yang lebih efisien daripada penyortiran. Mengurutkan adalah sedangkan algoritma seleksi adalah ; pengurutan hanya lebih efisien jika beberapa pilihan diperlukan, dalam hal ini Anda dapat mengurutkan (mahal) satu kali, dan kemudian berulang kali memilih dari daftar yang diurutkan. $O(n\log n)$ $O(n)$

Tautan ke masalah median geometris menyebutkan solusi untuk kasus multidimensi.

Geoff Oxberry
sumber

6

Solusi eksplisit dalam hal median benar, tetapi dalam menanggapi komentar oleh mayenew, berikut adalah pendekatan lain.

Telah diketahui bahwa masalah minimalisasi secara umum, dan masalah yang diposting khususnya, dapat diselesaikan dengan pemrograman linier. $\ell^1$

Formulasi LP berikut akan dilakukan untuk latihan yang diberikan dengan tidak diketahui : $z_i,m$

sedemikian rupa sehingga:

m i n \sum z_{i}

$min \sum z_i$

z_{i} \geq m - x_{i}

$z_i \ge m - x_i$

z_{i} \geq x_{i} - m

$z_i \ge x_i - m$

Jelas harus sama minimal, jadi ini meminta jumlah nilai absolut kesalahan untuk diminimalkan. $z_i$ $|x_i - m|$

hardmath
sumber

2

Cara analisis cembung bertenaga lebih untuk menunjukkan ini hanya mengambil subgradien. Sebenarnya ini setara dengan alasan yang digunakan dalam beberapa jawaban lain yang melibatkan lereng.

$\left|m-x_i\right|$

$m<x_i$

$m=x_i$

$m>x_i$

$m$ $x_1,\ldots x_k$

cjordan1
sumber

0

\arg min_{m} \sum_{saya = 1}^{N} | m - x_{saya} |

$\arg \min_{m} \sum_{i = 1}^{N} \left| m - {x}_{i} \right|$

$\frac{\mathrm{d} \left | x \right | }{\mathrm{d} x} = \operatorname{sign} \left( x \right)$ ${L}_{1}$
$\sum_{i = 1}^{N} \operatorname{sign} \left( m - {x}_{i} \right)$
$m = \operatorname{median} \left\{ {x}_{1}, {x}_{2}, \cdots, {x}_{N} \right\}$

Orang harus memperhatikan bahwa mediankelompok diskrit tidak didefinisikan secara unik.
Selain itu, tidak harus item dalam grup.

Royi
sumber

Meminimalkan Jumlah Deviasi Absolut ( Jarak

Jawaban: