如何选择常规密度的点
h2k*_*ong 9 algorithm geometry subset selection sampling
如何选择常规密度的点子集？更正式的,
特定
- 一组甲的不规则隔开的点,
- 距离度量
dist(例如欧几里德距离), - 和目标密度d,
如何选择满足以下条件的最小子集B？
- 每一个点X在一个,
- 存在一个点ÿ在乙
- 满足
dist(x,y) <= d
我目前的最佳镜头是
- 从A本身开始
- 选出最接近(或者只是特别接近)的几个点
- 随机排除其中一个
- 只要条件成立,就重复
并重复整个过程,以获得最好的运气.但有更好的方法吗？
我试图用280,000个18-D点来做到这一点,但我的问题是一般策略.所以我也想知道如何用二维点做到这一点.我并不需要保证最小的子集.欢迎任何有用的方法.谢谢.
自下而上的方法
- 选择一个随机点
- 选择未选中
y的min(d(x,y) for x in selected)最大值 - 继续!
我会把它称为自下而上和我最初自上而下发布的那个.这在开始时要快得多,所以对于稀疏采样,这应该更好吗？
性能指标
如果不要求保证最优性,我认为这两个指标可能有用:
- 覆盖半径:
max {y in unselected} min(d(x,y) for x in selected) - 经济半径:
min {y in selected != x} min(d(x,y) for x in selected)
RC是最小允许d,并且这两者之间没有绝对的不等式.但RC <= RE更可取.
我的小方法
为了对"性能测量"进行一点演示,我生成了256个均匀分布的2-D点或标准正态分布.然后我用它们尝试了自上而下和自下而上的方法.这就是我得到的:
RC是红色,RE是蓝色.X轴是所选点的数量.你认为自下而上可以做得好吗？我是这么看动画,但似乎自上而下明显更好(看看稀疏区域).尽管如此,并不是太可怕,因为它更快.
在这里,我收拾了一切
http://www.filehosting.org/file/details/352267/density_sampling.tar.gz
遗传算法在这里可能会产生良好的结果。
更新：
我一直在研究这个问题，这些是我的发现：
获取满足指定条件的点集的简单方法（称为随机选择）如下：
- 从 B 开始为空
- 从A中随机选择一个点x并将其放置在B中
- 从 A 中删除每个点 y 使得 dist(x, y) < d
- 当A不为空时转到2
kd 树可用于相对快速地执行步骤 3 中的查找。
我在 2D 中运行的实验表明，生成的子集大小大约是自上而下方法生成的子集大小的一半。
然后，我使用这种随机选择算法来播种遗传算法，该算法使子集的大小进一步减少了 25%。
对于突变，给定代表子集 B 的染色体，我在覆盖 A 中所有点的最小轴对齐超盒内随机选择一个超球。然后，我从 B 中删除也在超球中的所有点，并使用随机-选择再次完成。
对于交叉，我采用了类似的方法，使用随机超球来划分母亲和父亲染色体。
我已经使用GAUL库的包装器在 Perl 中实现了所有内容（GAUL 可以从这里获得。
脚本在这里： https://github.com/salva/p5-AI-GAUL/blob/master/examples/point_ Density.pl
它接受来自标准输入的 n 维点列表，并生成一组图片，显示遗传算法每次迭代的最佳解决方案。配套脚本https://github.com/salva/p5-AI-GAUL/blob/master/examples/point_gen.pl可用于生成均匀分布的随机点。