python - 更高维度的凸包，找到多面体的顶点

Question

假设我有一个在 6 维空间中给出的点云，我可以根据需要使其变得尽可能密集。这些点原来位于低维多面体的表面上(即点向量 (x1, x2, ... x6) 似乎是共面的)。

我想找到这个未知多胞形的顶点，我目前的尝试是通过 Python 中的 scipy 接口(interface)使用 qhull 算法。一开始我只会收到错误消息，显然是由低维输入和/或许多退化点引起的。我尝试了几种强力方法来消除退化点，但不是很成功，所以最后我认为所有这些点都必须位于凸包上。

This question 非常有帮助，因为它建议通过主成分分析进行降维。如果我将这些点投影到 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 维多胞形中。我将描述一种解决此多胞体的面的方法，这反过来会为您提供顶点。

令 R⁴ 中的 x_i, i = 1, ..., m 为 PCA 缩减的数据点。

设 F = (a, b) 是一张脸，其中 a 在 R⁴ 中，a • a = 1，b 在 R 中。

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

L(F) = sum_i(λ⁺ • max(0, a • x_i + b) - λ^- • min(0, a • x_i + b))

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

∂L/∂a_j = sum_i(λ⁺ • x_j • [a • x_i + b > 0] - λ^- • x_j • [a • x_i + b < 0]) 对于 j = 1, 2, 3, 4

∂L/∂b = sum_i(λ⁺ • [a • x_i + b > 0] - λ^- • [a • x_i + b < 0])

备注Iverson brackets : 如果 P 为真，[P] = 1，如果 P 为假，则 [P] = 0。