Minimalizowanie sumy absolutnego odchylenia (odległość

15

Mam zestaw danych $x_{1}, x_{2}, \ldots, x_{k}$ i chcę znaleźć parametr $m$ taki, aby minimalizował sumę

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

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

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

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

optimization convex-optimization

— Mayenew
źródło

2

Czy mógłbyś trochę rozwinąć?

— Geoff Oxberry

Czy w takim przypadku rozwiązaniem nie byłby środek między wartościami maksymalnymi i minimalnymi?

— Paweł

@Paul mediana może zminimalizować sumę, ale chce wiedzieć, jak można to zrobić analitycznie, szczególnie minimalizację

— L1

@kadu to prawda, mediana jest rozwiązaniem. Obliczenie mediany analitycznie jest trywialne; wystarczy posortować, a następnie przyjąć średnią wartość.

— David Ketcheson

22

Prawdopodobnie poprosisz o dowód, że mediana rozwiązuje problem? Cóż, można to zrobić w następujący sposób:

Celem jest odcinkowo liniowy i tym samym różniczkowalną wyjątkiem punktów . Jakie nachylenie celu ma jakiś punkt ? Cóż, nachylenie jest sumą nachyleń odwzorowań i jest to (dla ) lub (dla ). Stąd nachylenie wskazuje, ile jest mniejsze niż $m=x_i$ $m\neq x_i$ $m\mapsto |m-x_j|$ $+1$ $m>x_j$ $-1$ $m<x_j$ $x_i$ $m$ . Widzisz, że nachylenie wynosi zero, jeśli istnieje równie wiele mniejszych i większych niż (dla i parzystej liczby ). Jeśli jest nieparzysta liczba , to nachylenie wynosi lewo od „środkowego” i prawo od niego, stąd środkowa jest minimalna. $x_i$ $m$ $x_i$ $x_i$ $-1$ $+1$

— Sztylet
źródło

16

Uogólnienie tego problemu na wiele wymiarów nazywa się problemem geometrycznej mediany . Jak zauważa David, mediana jest rozwiązaniem dla przypadku 1-D; tam można użyć algorytmów wyboru wyszukiwania mediany , które są bardziej wydajne niż sortowanie. Sortowanie to podczas gdy algorytmy wyboru to ; sortowanie jest bardziej wydajne tylko wtedy, gdy potrzebnych jest wiele selekcji, w którym to przypadku można sortować (kosztownie) jeden raz, a następnie wielokrotnie wybierać z posortowanej listy. $O(n\log n)$ $O(n)$

Link do problemu geometrycznej mediany wspomina o rozwiązaniach dla przypadków wielowymiarowych.

— Geoff Oxberry
źródło

6

Wyraźne rozwiązanie w zakresie mediany jest poprawne, ale w odpowiedzi na komentarz Mayenew oto inne podejście.

Powszechnie wiadomo, że problemów minimalizacji ogólnie, a pisał problemem w szczególności, może być rozwiązany przez programowania liniowego. $\ell^1$

Poniższe sformułowanie LP wykona dla danego ćwiczenia z niewiadomymi : $z_i,m$

takie, że:

m ja n \sum z_{ja}

$min \sum z_i$

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

$z_i \ge m - x_i$

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

$z_i \ge x_i - m$

Wyraźnie musi równać co najmniej, więc wymaga to zminimalizowania sumy bezwzględnych wartości błędów. $z_i$ $|x_i - m|$

— matematyka
źródło

2

Nadmiernie zasilony wypukły sposób analizy, aby to pokazać, wystarczy wziąć podgrupy. W rzeczywistości jest to równoważne z rozumowaniem zastosowanym w niektórych innych odpowiedziach dotyczących zboczy.

$\left|m-x_i\right|$

$m<x_i$

$m=x_i$

$m>x_i$

$m$ $x_1,\ldots x_k$

— cjordan1
źródło

0

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

$\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\}$

Należy zauważyć, że mediangrupa dyskretna nie jest jednoznacznie zdefiniowana.
Co więcej, niekoniecznie jest to element w grupie.

— Royi
źródło