Минимизация суммы абсолютного отклонения ( расстояние

У меня есть набор данных и я хочу найти параметр m такой, чтобы он минимизировал сумму k ∑ i = 1 | м - х я | , то есть$x_{1}, x_{2}, \ldots, x_{k}$$m$

Возможно, вы просите доказательства того, что медиана решает проблему? Ну, это можно сделать так:

Цель является кусочно-линейной и, следовательно, дифференцируемой, за исключением точек . Каким наклоном объектива является некоторая точка m ≠ x i ? Ну, наклон - это сумма наклонов отображений m ↦ | м - х J | и это либо + 1 (для m > x j ), либо - 1 (для m < x j ). Следовательно, наклон показывает, сколько x i меньше, чем $m=x_i$$m\neq x_i$$m\mapsto |m-x_j|$$+1$$m>x_j$$-1$$m<x_j$$x_i$$m$ . Вы видите, что наклон равен нулю, если есть одинаково много меньше и больше, чем m (для и четного числа$x_i$$m$ » s). Если есть нечетное число х я «Sто наклон - 1 слева от„middlest“один и + 1 право его, следовательно, middlest один является минимальным.$x_i$$x_i$$-1$$+1$

Обобщение этой задачи на множественные измерения называется геометрической срединной задачей . Как указывает Дэвид, медиана является решением для одномерного случая; там вы могли бы использовать алгоритмы выбора медианного поиска , которые более эффективны, чем сортировка. Сорта а алгоритмы выбора O ( n ) ; сортировки более эффективны, только если необходимо несколько вариантов выбора, и в этом случае вы можете отсортировать (дорого) один раз, а затем повторно выбирать из отсортированного списка.$O(n\log n)$$O(n)$

В ссылке на геометрическую задачу о медиане упоминаются решения для многомерных случаев.

Явное решение с точки зрения медианы является правильным, но в ответ на комментарий Mayenew, вот еще один подход.

$\ell^1$

Следующая формулировка LP подойдет для данного упражнения с неизвестными $z_i,m$

такое, что: z i ≥ m - x i z

Ясно , что должна равняться | х я - $z_i$$|x_i - m|$

Слишком мощный метод выпуклого анализа, чтобы показать это, - просто взять субградиенты. Фактически это эквивалентно рассуждению, используемому в некоторых других ответах, касающихся склонов.

$\left|m-x_i\right|$

$m<x_i$

$m=x_i$

$m>x_i$

$m$$x_1,\ldots x_k$

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

Следует отметить, что medianдискретная группа не определяется однозначно.
Более того, это не обязательно предмет в группе.