更高尺寸的凸壳,找到多面体的顶点

Question

假设我在6维空间中给出了一个点云,我可以根据需要进行密集.这些点变成位于低维多面体的表面上(即点矢量(x1,x2,... x6)看起来是共面的).

我想找到这个未知多面体的顶点,我当前的尝试通过Python中的scipy接口使用qhull算法.在开始时,我只会得到错误消息,显然是由较低维度输入和/或许多退化点引起的.我尝试了几种蛮力方法来消除退化点,但不是很成功,所以最后,我想所有这些点都必须位于凸壳上.

这个问题非常有用,因为它建议通过主成分分析减少尺寸.如果我将点投影到4D超平面,则qhull算法运行时没有错误(对于任何更高的维度,它不会运行).

from scipy.spatial import ConvexHull
from sklearn.decomposition import PCA

model = PCA(n_components=4).fit(initial_points)
proj_points = model.transform(initial_points)
hull = ConvexHull(proj_points, qhull_options = "Qx")

上述问题的答案提到,在计算出投影点的凸包后,需要将单纯形变换回来.但是qhull输出只包含索引,为什么这些索引与初始点的索引不匹配？

现在我的问题是我不知道使用哪种精度来实际获得正确的顶点.无论我对点云的密集程度如何,所获得的顶点随着精度的不同而不同.例如,对于(10000,6)数组中的初始点,我得到(其中E0.03是其工作的最大值):

hull1 = ConvexHull(proj_points, qhull_options = "Qx, E0.03")
print len(hull1.vertices)
print hull1.vertices

5
[ 437 2116 3978 7519 9381]

并将其绘制在轴0,1,2(其中蓝点代表初始点云的选择)的某些(非信息丰富的)投影中:

但是为了获得更高的精度(当然),我会得到一个不同的集合:

hull2 = ConvexHull(proj_points, qhull_options = "Qx, E0.003")
print len(hull2.vertices)
print hull2.vertices

29
[  74   75  436  437  756 1117 2116 2366 2618 2937 3297 3615 3616 3978 3979
 4340 4561 4657 4659 4924 5338 5797 6336 7519 7882 8200 9381 9427 9470]

相同的投影(角度略有不同):

我怀疑第一张图片没有足够的顶点,第二张图片可能有太多.虽然我当然无法从这些情节中提取严谨的信息.但有没有一种很好的方法可以找出使用哪种精度？或许对这个问题采取完全不同的方法(我已尝试了几个)？

Answer 1

在这个答案中，我假设您已经使用 PCA 将数据近乎无损地压缩为 4 维数据，其中减少的数据位于概念上很少面的 4 维多面体中。我将描述一种解决该多面体面的方法，这反过来会给您顶点。

\n\n

令R ⁴中的x _i (i = 1, ..., m) 为 PCA 缩减的数据点。

\n\n

令 F = (a, b) 为一个面，其中 a 在 R ⁴中，且 a • a = 1 并且 b 在 R 中。

\n\n

我们将面损失函数 L 定义如下，其中 λ ⁺、 λ ^- > 0 是您选择的参数。λ ⁺应该是一个非常小的正数。λ ^-应该是一个非常大的正数。

\n\n

L(F) = sum _i (λ ⁺ • max(0, a • x _i + b) - λ ^- • min(0, a • x _i + b))

\n\n

我们想要找到关于损失函数 L 的最小面 F。所有最小面的小集合将描述你的多面体。_{您可以通过随机初始化 F 然后使用偏导数 \xe2\x88\x82L / \xe2\x88\x82a j}、 j = 1, 2, 3, 4 和 \xe2\x88\执行梯度下降来求解最小面x82L / \xe2\x88\x82b。在梯度下降的每一步，通过归一化将a • a 约束为1。

\n\n

\xe2\x88\x82L / \xe2\x88\x82a _j = sum _i (λ ⁺ • x _j • [a • x _i + b > 0] - λ ^- • x _j • [a • x _i + b < 0 ]) 对于 j = 1, 2, 3, 4

\n\n

\xe2\x88\x82L / \xe2\x88\x82b = sum _i (λ ⁺ • [a • x _i + b > 0] - λ ^- • [a • x _i + b < 0])

\n\n

注意艾弗森括号：如果 P 为真，则 [P] = 1；如果 P 为假，则 [P] = 0。

\n