Minimiser la somme de l'écart absolu ( distance

15

J'ai un ensemble de données x1,x2,,xk et je veux trouver le paramètre m tel qu'il minimise la somme

i=1k|mxi|.
C'est

minmi=1k|mxi|.
mai nouveau
la source
2
Pourriez-vous développer un peu?
Geoff Oxberry
Dans ce cas, la solution ne serait-elle pas alors le milieu entre les valeurs maximales et minimales?
Paul
@Paul la médiane peut minimiser la somme mais veut savoir comment cela peut être fait analytiquement, en particulier la minimisation l1
mai
@kadu c'est vrai, la médiane est la solution. Le calcul analytique de la médiane est trivial; il suffit de trier puis de prendre la valeur moyenne.
David Ketcheson

Réponses:

22

Vous demandez probablement une preuve que la médiane résout le problème? Eh bien, cela peut être fait comme ceci:

L'objectif est linéaire par morceaux et donc différenciable sauf pour les points . Quelle est la pente de l'objectif est un certain point m x i ? Eh bien, la pente est la somme des pentes des mappages m | m - x j | et c'est soit + 1 (pour m > x j ) ou - 1 (pour m < x j ). Par conséquent, la pente indique combien de x i sont plus petits que mm=ximxim|mxj|+1m>xj1m<xjxim . Vous voyez que la pente est nulle s'il y a autant de plus petits et plus grands que m (pour et nombre pair de x i ). S'il y a un nombre impair de x i , alors la pente est de - 1 à gauche de la "plus moyenne" et + 1 à droite de celle-ci, donc la plus moyenne est la minimale.ximxixi1+1

Poignard
la source
16

Une généralisation de ce problème à plusieurs dimensions est appelée le problème de la médiane géométrique . Comme le souligne David, la médiane est la solution pour le cas 1-D; là, vous pourriez utiliser des algorithmes de sélection de recherche médiane , qui sont plus efficaces que le tri. Les tris sont tandis que les algorithmes de sélection sont O ( n ) ; les tris ne sont plus efficaces que si plusieurs sélections sont nécessaires, auquel cas vous pouvez trier (de manière coûteuse) une fois, puis effectuer des sélections répétées dans la liste triée.O(nlogn)O(n)

Le lien avec le problème géométrique médian mentionne des solutions pour des cas multidimensionnels.

Geoff Oxberry
la source
6

La solution explicite en termes de médiane est correcte, mais en réponse à un commentaire de mayenew, voici une autre approche.

Il est bien connu que les problèmes de minimisation de général, et le problème affiché en particulier, peuvent être résolus par programmation linéaire.1

La formulation LP suivante fera l'affaire pour l'exercice donné avec des inconnues :zi,m

tel que: z im - x i z ix i - m

minzi
zimxi
zixim

zi|xim|

hardmath
la source
2

La méthode d'analyse convexe surpuissante pour le montrer est de prendre des sous-gradients. En fait, cela équivaut au raisonnement utilisé dans certaines des autres réponses concernant les pentes.

|mxi|

m<xi

m=xi

m>xi

mx1,xk

cjordan1
la source
0

Nous sommes essentiellement après:

argminmje=1N|m-Xje|

Il faut remarquer que d|x|dx=sign(x) (Being more rigorous would say it is a Sub Gradient of the non smooth L1 Norm function).
Hence, deriving the sum above yields i=1Nsign(mxi).
This equals to zero only when the number of positive items equals the number of negative which happens when m=median{x1,x2,,xN}.

One should notice that the median of a discrete group is not uniquely defined.
Moreover, it is not necessarily an item within the group.

Royi
la source