如何选择具有定期密度的点

Question

我该如何以规则的密度选择一个子集点？更正式地说，

给定：

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

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

- 对于A中的每个点x， - 存在一个点y在B中， - 满足dist（x，y）<= d

我目前最好的方法是：

- 从A本身开始 - 选择最接近（或非常接近）的一对点 - 随机排除其中一个 - 只要条件成立就重复

并且为了最佳运气重复整个过程。但是有更好的方法吗？

我正在尝试使用280,000个18-D点做到这一点，但我的问题是关于一般策略的。因此，我也希望知道如何使用2-D点来完成它。我并不需要保证最小子集。任何有用的方法都欢迎。谢谢。

底部向上方法：

- 选择一个随机点 - 从未选中的y中选择“min（selected中的x的d（x，y））”最大的y - 继续！

我将其称为自下而上，我最初发布的是自上而下。这样一开始速度就快得多，因此对于稀疏采样应该更好？

性能度量：

如果不需要保证最优性，我认为这两个指标可能有用：

- 覆盖半径：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

- h2kyeong

---

我看不出你提供的代码如何满足所述条件（“对于A中的每个x，都存在B中的y，使得dist（x，y）<d”）。我也找不到你使用的Python“h2”包。 - salva

我的小方法反其道而行之——它创建适用于某些 d 的有效选择。很抱歉，“h2”是我可重用代码块的集合……我没有意识到我使用了它。 - h2kyeong

Answer 1

你可以用图形来模拟你的问题，将点看作节点，并在它们之间连接边，如果它们之间的距离小于d。现在你需要找到最小数量的顶点，使得它们与它们所连接的顶点覆盖图中的所有节点，这就是最小顶点覆盖问题（通常是NP-Hard），但你可以使用快速的2近似算法：重复地将一条边的两个端点加入顶点覆盖，然后从图中删除它们。

附注：当然你应该选择与图完全断开连接的节点，在移除这些节点（即选择它们）后，你的问题就变成了顶点覆盖问题。

- Saeed Amiri

---

是的，这个问题属于集合覆盖问题。但在这个问题中，我们有一个普遍的特性，即如果A和B接近，B和C接近，则A和C往往也接近。这就是为什么我认为可能会有更好的方法。谢谢。 - h2kyeong

@h2kyeong，你是如何得到这个性质的？“如果A和B很接近，B和C也很接近，那么A和C也倾向于很接近”？假设A、B、C在同一条直线上（首先是A，第二个是B，然后是C），并且||A-B||=d, ||B-C||=d，但是||A-C|| = 2d。因此，除非你明确提到它并且在这种情况下问题太简单，否则你不能假设你有这个属性。 - Saeed Amiri

是的，例如欧几里得距离，上限是2 d，下限是零。我并不是说它仅限于 d；但是2 d 仍然是比例上较小的。同时，距离函数可以为所有点对分配任意值，但仍将是顶点覆盖问题的子问题。 - h2kyeong

@h2kyeong，我不明白你的意思，如果你将限制设置为d，那么你怎么说2d是可以的呢？ - Saeed Amiri

我只是在说许多距离函数与随机远不相同。因此，我们比那些处理顶点覆盖问题的算法更有希望找到更快的解决方案。可惜的是，我发现即使在高维度中挑选出最接近的一对也并不容易... - h2kyeong

Answer 2

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

更新：

我已经尝试了这个问题，并得出以下结论：

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

1. 从空集B开始 2. 从A中随机选择一个点x并将其放入B中 3. 从A中删除每个距离x小于d的点y 4. 如果A不为空，则返回步骤2

可以使用kd-tree相对快速地执行步骤3中的查找。

在二维实验中运行的结果显示，生成的子集大约是你自上而下方法生成的子集的一半大小。

然后，我使用这个随机选择算法来启动一个遗传算法，进一步减少了25%的子集大小。

对于突变，给定代表子集B的染色体，我随机选择一个超球体，在覆盖所有A中的点的最小轴对齐超立方体内移除B中也在超球体中的所有点，然后再使用随机选择来补全。

对于交叉，我采用类似的方法，使用一个随机的超球体来分割母体和父体染色体。

我使用Perl实现了所有内容，使用我的包装器来调用GAUL库（可以从这里获取GAUL）。

脚本在这里：https://github.com/salva/p5-AI-GAUL/blob/master/examples/point_density.pl 它接受来自stdin的n维点列表，并生成一系列图片，显示遗传算法每次迭代的最佳解决方案。配套脚本https://github.com/salva/p5-AI-GAUL/blob/master/examples/point_gen.pl可用于使用均匀分布生成随机点。

- salva

---

你能再详细解释一下吗？当然，如果对问题领域一无所知，那么使用遗传算法是一个选择。 - Christian Rau

@Christian，是的，您可以使用位图来表示覆盖子集。作为加权函数，您可以使用位计数（覆盖子集中点的数量），例如，对于繁殖，您可以随机选择两个位图的子字符串并将它们修复以确保它们是覆盖子集。 - salva

@Christian，实际上，我正在尝试编写一个完整的解决方案 :-) - salva

所以你可以将其视为集合覆盖问题。我希望你能找到好的繁殖/变异方法...尤其是繁殖。 - h2kyeong

Answer 3

这里提出了一个假设曼哈顿距离度量的方案：

1. 将整个空间划分为粒度为d的网格。形式化地说：将A分区，使得点(x1,...,xn)和(y1,...,yn)在同一分区中当且仅当(floor(x1/d),...,floor(xn/d))=(floor(y1/d),...,floor(yn/d))。
2. 从每个网格空间中任意选择一个点作为代表--也就是，在步骤1中创建的分区中，从每个集合中选择一个代表。如果有些网格空间为空，不用担心！只需不为该空间选择代表即可。

实际上，实现过程不需要执行任何真正的工作来完成第一步，而第二步可以通过对分区标识符（即(floor(x1/d),...,floor(xn/d)))的哈希进行一次遍历来完成，以检查我们是否已经为特定的网格空间选择了代表，因此这可以非常快速。

一些其他的距离度量方法可能能够使用适应性方法。例如，欧几里得距离可以使用d/sqrt(n)-size网格。在这种情况下，您可能希望添加后处理步骤，试图稍微减少覆盖范围（因为上述网格不再是完全半径d球--球有点重叠相邻网格），但我不确定那部分看起来会如何。

- Daniel Wagner

---

这种方法的一个简单改进是使用三角形网格而不是正方形网格。这样，球之间的重叠会更少。 - salva

@salva 嗯，对于二维欧几里得度量来说，那可能更好，不过六边形对于这个也更好。但是OP似乎想要一个更高维度的东西 - 你碰巧知道18维铺砖形状是什么吗？=) - Daniel Wagner

一个六边形网格和一个三角形网格是同一几何结构的两个视图。只需绘制一个六边形网格，然后连接相邻六边形的中心以找到其三角形等效物。关于更高维度，三角形/四面体的概括是单纯形。 - salva

Answer 4

懒惰一点，这可以转化为一个集合覆盖问题，可以通过混合整数问题求解器/优化器来处理。这里是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分钟内没有找到最佳子集，但它表示它知道真正的最小值，并且只选择了一个额外的点。

- h2kyeong