解决距离问题的最佳方法

我相信,如果我们希望最小化绝对距离之和,中位数是正确的答案,这是显而易见的解释。如果我们希望最小化平方距离之和,则平均值是正确的。对于y=0和x=0,1,2,101的点,平均值为26,我们可以取中值为1.5。与均值的绝对距离之和为149,与中位数的绝对距离之和为102。

在中位数处,左侧的点数与右侧的点数相同。少量向左移动会增加到右侧点的所有距离,并以相同的量减少到左侧点的所有距离-不变。如果距离中间带一点或更多,可以通过向有更多点的区域移动来减少绝对距离之和。这减少了从点多的区域开始的距离之和,而不是增加了从点少的区域开始的距离之和-因此,如果你不在中间带,你可以通过向中间带移动来改善情况。这是一个相当标准的统计结果。

在不丧失一般性的情况下,我们可以说这些点位于y=0的直线上,而中心点位于(0,0)。这是因为像旋转和平移这样的仿射变换不会影响相对距离。

将与点X的距离定义为总和(P=>| P-X |)

引理1 :中心点必须沿y=0的直线。假设中心点位于(x,y)和y!=0考虑点(x,0)。

sum(P - (x,y)) = sum( sqrt( (p-x)*(p-x) + (0-y)*(0-y) ) )
               = sum( sqrt( p*p - 2xp + x*x + y*y ) )
               > sum( sqrt( p*p - 2xp + x*x + (0-0)*(0-0) ) )
               = sum(P - (x,0))

这是一个矛盾,因此y=0必须为真。

:它是奇数个元素,因此请选择它:(0,0)。假设有一个点X=(X,0),使得X更接近。那么这意味着| x-0 |<(0-0)或| x |<0,这是不可能的。因此(0,0)是中心点。

3个元素的基本情况 :这是奇数个元素,因此请选择中间点:(0,0)。在不丧失一般性的情况下,将其他两点设为(a<0,0)和(b>0,0)。假设有一个更接近的点X=(X,0)。这意味着:

|x-0 |+| x-a |+| x-b |<|0-0 |+| 0-a |+| 0-b|

<=>

|x |+| x-a |+| x-b |<|a |+| b|

然而:

|x |+| x-a |+| x-b |>=|x |+| a |+| b |>=|a |+| b |,这与假设相矛盾,因此(0,0)是中心点。

包含N个元素(N个奇数)的情况 . 假设所有奇数点集满足上述条件。设P为N个元素的集合,并按如下方式排列:

{(a,0),Q={N-2元素的集合,中心在(0,0)},(b,0)}

sum(P - X) = |x-a| + |x-b| + sum(Q - X)
           > |x-a| + |x-b| + sum(Q - (0,0))
           >= |a| + |b| + sum(Q - (0,0))
           = sum(P - (0,0))

这意味着假设是矛盾的,所以(0,0)必须是中心点。

http://en.wikipedia.org/wiki/Geometric_median

以下不是最好的解决方案。但给出了正确的值。

1. 首先找到直线的角度,将所有点旋转到与该角度相反的位置,使其成为水平线
2. 对所有X点进行排序,因为旋转后Y将保持不变
3. 设它为X(1),X(2),X(3)。。。X(N)
5. 得到最小的D(R)。
6. 将X(R)、Y旋转回原始角度。
7. 这是你的期望值。
8. 如属D(R)及;D(R+1)相同,则X(R)、Y和;X(R+1),Y将是您的期望值。
9. 有趣的是,若R是中间值,那个么答案将是最小的,因为加法的数量[X(1)+…X(R)]和[X(R+1)+…X(N)]几乎相等,那个么差是最小的,否则若一侧的加法数较高,那个么差总是会高于相等加法数。同样,如果有偶数个点,则(N)/2到(N/2)+1之间的所有点将具有相同的相等距离。。
10. 因此,中位数是正确的答案。

希望这对你有用。

有趣的问题!

首先,由于所有点都是共线的,我们可以很容易地将它们分割为X分量和Y分量。然后我们独立地解决X和Y的问题。假设我们得到了值 V[0] to V[n-1] n是点数。

现在问题变成了计算x,这样 SUM( (V[0 ... n-1] - x)^2 ) 2*n*x - 2*SUM( V[0 ... n-1] ) .

这将变为0 -n * x + SUM( V[0 ... n-1] ) . 照着 x = SUM( V[0 ... n-1] ) / n .

所以只要把所有的值加起来,再除以n,就可以得到正确的最小解。对x和y进行此操作后,您将获得所需的点。

这也等于我第一次考虑你的问题时所做的假设,它适用于我测试的一些值。希望这有帮助。:)

设n为直线上的点数。设点为p(1),…,p(n),从左到右标记。

案例n=1。符合事实的

案例n=2。符合事实的您可以在这两点之间选择任意一点。

案例n>=3.引入x-y坐标系。旋转飞机,使其旋转 这些点位于x轴上。

设D为从x到其他点的距离之和。

有三个子类。

子类别1:x是中值。因此,L=R。如果我们向左移动x一小量e,距离之和变成D-Le+Re+e=D+e>D.类似地,为了向右移动。所以中位数给出了一个局部最小值。

子类别2:x位于中间带的左侧。类似于下面的子类。

将x向左移动e。我们可以让x变成p(i)。距离和变成D-Le+Re=D-(L-R)e<=也就是说,我们可能会减少,但不会增加。

嗯,你当然不需要对它们进行分类。只要取它们的x和y坐标的平均值。这将在N维中工作,只要它们是共线的。

证明(ish):你找到了一个正确的答案,但对于偶数的分数有多重性。

对于任意两点,这些点之间线段上的任何点到两个点的距离之和都是相同的。该线段外的任何点的距离都将大于线段上的距离。

因此,要找到与所有共线点之间距离最小的点,需要将问题分解为包含两个点的集合,即完全包含在其他线段中的线段。然后,只取最小的线段(或奇数点情况下的点)并在该线段上拾取一个点。该线段上的所有点与该特定配置的所有点之间的距离最小。

如果要绘制此图形,所有与点的距离图形将具有相同的形状:/ 对于线段,距离图如下所示:_/