9

如何以常规密度选择点的子集？更正式地说，

给定

  1. 一组不规则间隔的点A，
  2. 距离度量dist（例如，欧几里得距离），
  3. 和目标密度d，

如何选择满足以下条件的最小子集B ？

  • 对于A中的每个点x，
  • B中有一个点y
  • 满足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 个二维点，这些点均匀分布或按标准正态分布。然后我用他们尝试了我的自上而下和自下而上的方法。这就是我得到的：

自下而上的规范 自上而下的规范

RC 为红色，RE 为蓝色。X 轴是选定点的数量。你认为自下而上可以一样好吗？我是这么看动画的，但似乎自上而下的效果要好得多（看看稀疏区域）。尽管如此，考虑到它的速度要快得多，这并不算太可怕。

在这里，我收拾了所有东西。

http://www.filehosting.org/file/details/352267/density_sampling.tar.gz

4

4 回答 4

3

您可以用图对问题进行建模，将点假设为节点，如果两个节点的距离小于d ，则用边连接两个节点，现在您应该找到最小的顶点数，以使它们的连接顶点覆盖图的所有节点，这是最小顶点覆盖问题（通常是 NP-Hard），但您可以使用快速 2 近似：重复将边的两个端点放入顶点覆盖，然后将它们从图中删除。

PS：确保您应该选择与图表完全断开连接的节点，删除此节点（意味着选择它们）后，您的问题是顶点覆盖。

于 2012-06-11T07:06:04.620 回答
2

这是一个假设曼哈顿距离度量的提案：

  1. 将整个空间划分为粒度为 d 的网格。形式上：分区 A 使得点 (x1,...,xn) 和 (y1,...,yn) 恰好在 (floor(x1/d),...,floor(xn/d) 时位于同一分区中))=(地板(y1/d),...,地板(yn/d))。
  2. 从每个网格空间中选择一个点（任意）——即从步骤 1 中创建的分区中的每个集合中选择一个代表。如果某些网格空间为空，请不要担心！根本不要为这个空间选择代表。

实际上，实现不需要做任何实际工作来完成第一步，而第二步可以使用分区标识符的散列（(floor(x1/d),.. .,floor(xn/d))) 来检查我们是否已经为特定的网格空间选择了一个代表，所以这可以非常非常快。

其他一些距离度量可能能够使用适应的方法。例如，欧几里得度量可以使用 d/sqrt(n) 大小的网格。在这种情况下，您可能需要添加一个后处理步骤，以尝试减少一点覆盖（因为上面描述的网格不再完全是半径-d 球——这些球与相邻的网格有一点重叠），但我我不确定那部分会是什么样子。

于 2012-06-20T08:01:23.960 回答
2

遗传算法在这里可能会产生好的结果。

更新：

我一直在玩这个问题，这些是我的发现：

获得满足所述条件的一组点的简单方法（称为随机选择）如下：

  1. 以 B 开头为空
  2. 从 A 中选择一个随机点 x 并将其放置在 B 中
  3. 从 A 中删除每个点 y 使得 dist(x, y) < d
  4. 当 A 不为空时转到 2

kd-tree 可用于相对快速地执行步骤 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可用于生成具有均匀分布的随机点。

于 2012-06-13T14:29:13.930 回答
0

为了懒惰，这可以转换为集合覆盖问题，可以由混合整数问题求解器/优化器处理。这是 GLPK LP/MIP 求解器的 GNU MathProg 模型。这里C表示哪个点可以“满足”每个点。

param N, integer, > 0;
set C{1..N};

var x{i in 1..N}, binary;
s.t. cover{i in 1..N}: sum{j in C[i]} x[j] >= 1;
minimize goal: sum{i in 1..N} x[i];

对于正态分布的 1000 个点，它没有在 4 分钟内找到最佳子集，但它说它知道真正的最小值，它只选择了一个点。

于 2013-09-26T19:38:18.663 回答