数学研发论坛

 找回密码
 欢迎注册
查看: 517|回复: 7

[求助] 平面点集的平均距离估算方法

[复制链接]
发表于 2018-10-12 20:24:24 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
平面上有$n$个点,

它们的坐标分别是$(x_1,y_1),(x_2,y_2),...,(x_n,y_n)$,

它们的平均距离等于$\sum_{i=1}^{n-1}\sum_{j=i+1}^n\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}/{{n(n-1)}/2}$。

当$n$很大的时候,例如:$n=10^8$,

上述式子需要花很长时间($O(n^2)$)计算。

我现在有$2$种快速计算方法。

方法$1$:

在$n$个点里等概率地随机抽取的$k$个点,

然后以这$k$个点的平均距离来估算$n$个点的平均距离,

于是这个估算结果只需要$O(k^2)$的时间就能得到。

问题$1$:

这个估算结果是不是无偏估计(期望值与真实结果相同)?

如果是无偏估计,那么它的方差是多少?

方法$2$:

在$C_n^2$对点里等概率地随机抽取$k$对点,

然后对这$k$对点分别求距离,一共求出$k$个距离,

然后以这$k$个距离的平均值来估算$n$个点的平均距离,

于是这个估算结果只需要$O(k)$的时间就能得到。

问题$2$:

这个估算结果是不是无偏估计(期望值与真实结果相同)?

如果是无偏估计,那么它的方差是多少?

问题$3$:

在$k$个单位时间内(假设取点不花时间,求$1$次距离花$1$个单位时间),

有没有方差更小的无偏估计方法?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-10-15 09:22:46 | 显示全部楼层
--
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

发表于 2018-10-15 11:22:10 | 显示全部楼层
这些点怎么分布?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-10-15 12:55:09 | 显示全部楼层
楼上说的有道理,点的分布的数学模型 直接决定了 估算方法的模型。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-10-15 16:41:12 | 显示全部楼层
无偏估计是显然的,但是方差会很难算。
比如第一种方案,实际上n个点里面选择k个点有$C_n^k$中选择方案,而这$C_n^k$种选择方案都是等概率选择的。
而这$C_n^k$种方案计算出来的结果在求平均显然还是原先的平均值。第二种方案也类似。
从直觉上看,方案二显然优于方案一

点评

方案二每次选择会使用更多的点,而方案一只使用了部分的点之间的信息,由于不同的点集之间产生的距离信息会完全不同,所以方案一会更差  发表于 2018-10-18 16:31
我的直觉也是方案二的方差小。但方案一的方差具体是多少,为什么大就不得而知了。  发表于 2018-10-18 08:26
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-10-15 16:49:00 | 显示全部楼层
第二种方案相对比较好评估,我们只需要直到任意选择两个点,假设两点之间距离的平均值为a,均方差为b,那么取k对数据求平均后均值还是a,而均方差会变为$b/{\sqrt{k}}$,所以在对所有数据的范围有个大概了解的情况下面,可以非常容易估算出大概需要挑选多少对数据就可以达到需要的精度
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-3-22 20:00 , Processed in 0.073031 second(s), 18 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表