Minimierung der Summe der absoluten Abweichung (

15

Ich habe einen Datensatz $x_{1}, x_{2}, \ldots, x_{k}$ und möchte den Parameter $m$ so finden, dass er die Summe minimiert

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

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

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

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

optimization convex-optimization mayenew
quelle

2

Könnten Sie etwas näher darauf eingehen?

Geoff Oxberry

Wäre die Lösung dann nicht der Mittelpunkt zwischen Maximal- und Minimalwert?

Paul

@Paul der Median kann die Summe minimieren, möchte aber wissen, wie dies analytisch erfolgen kann, insbesondere die l1-Minimierung

möglicherweise am

@kadu das stimmt, der Median ist die Lösung. Das analytische Berechnen des Medians ist trivial; Einfach sortieren und dann den mittleren Wert nehmen.

David Ketcheson

22

Möglicherweise fragen Sie nach einem Beweis, dass der Median das Problem löst? Nun, das kann so gemacht werden:

Das Objektiv ist stückweise linear und daher mit Ausnahme der Punkte differenzierbar . Was ist die Steigung des Objektivs ist ein Punkt ? Nun, die Steigung ist die Summe der Steigungen der Abbildungen und dies ist entweder (für ) oder (für ). Daher gibt die Steigung an, wie viele kleiner als $m=x_i$ $m\neq x_i$ $m\mapsto |m-x_j|$ $+1$ $m>x_j$ $-1$ $m<x_j$ $x_i$ $m$ . Sie sehen, dass die Steigung Null ist, wenn es gleich viele kleinere und größere als (für und gerade Anzahl von ). Wenn es eine ungerade Anzahl von gibt, ist die Steigung links von der "mittelsten" und rechts davon, daher ist die mittelste die minimale. $x_i$ $m$ $x_i$ $x_i$ $-1$ $+1$

Dolch
quelle

16

Eine Verallgemeinerung dieses Problems auf mehrere Dimensionen wird als geometrisches Medianproblem bezeichnet . Wie David betont, ist der Median die Lösung für den 1-D-Fall; Dort könnten Sie Median-Finding- Auswahlalgorithmen verwenden , die effizienter sind als das Sortieren. Sortierungen sind während Auswahlalgorithmen ; Sortierungen sind nur dann effizienter, wenn mehrere Auswahlen erforderlich sind. In diesem Fall können Sie einmal (teuer) sortieren und dann wiederholt aus der sortierten Liste auswählen. $O(n\log n)$ $O(n)$

Der Link zum geometrischen Medianproblem nennt Lösungen für mehrdimensionale Fälle.

Geoff Oxberry
quelle

6

Die explizite Lösung in Bezug auf den Median ist korrekt, aber als Reaktion auf einen Kommentar von mayenew ist hier ein anderer Ansatz.

Es ist bekannt , dass Minimierungsprobleme im Allgemeinen und das entsandte Problem kann insbesondere durch lineare Programmierung gelöst werden. $\ell^1$

Die folgende LP-Formulierung reicht für die gegebene Übung mit Unbekannten : $z_i,m$

so dass:

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$

Klar muss gleich sein im Minimum, so dass dies die Summe der absoluten Werte von Fehlern zu minimieren fordert. $z_i$ $|x_i - m|$

Hardmath
quelle

2

Die überlastete konvexe Analyse, mit der dies gezeigt werden kann, erfordert lediglich Subgradienten. Tatsächlich entspricht dies der Argumentation, die in einigen anderen Antworten verwendet wurde, die Steigungen betrafen.

Das Optimierungsproblem ist konvex (da das Ziel konvex ist und keine Einschränkungen bestehen). Außerdem ist der Subgradient von ist $\left|m-x_i\right|$

-1 wenn $m<x_i$

[-1,1] wenn $m=x_i$

+1 wenn . $m>x_i$

$m$ $x_1,\ldots x_k$

cjordan1
quelle

0

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

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

Man sollte beachten, dass die medianeiner diskreten Gruppe nicht eindeutig definiert ist.
Darüber hinaus ist es nicht unbedingt ein Element innerhalb der Gruppe.

Royi
quelle

Minimierung der Summe der absoluten Abweichung (

Antworten: