更高维度的凸包，找到多面体的顶点
Convex hull in higher dimensions, finding the vertices of a polytope
假设我有一个 6 维 space 的点云，我可以根据需要将其制作得尽可能密集。结果这些点位于 lower-dimensional 多面体的表面上（即点向量 (x1, x2, ... x6) 似乎是共面的）。
我想找到这个未知多胞形的顶点，我目前的尝试是通过 Python 中的 scipy 接口使用 qhull 算法。一开始我只会收到错误消息，显然是由于低维输入 and/or 许多退化点引起的。我尝试了几个brute-force方法来消除退化点，但不是很成功，所以最后，我想所有这些点都必须在凸包上。
This question 非常有帮助，因为它通过主成分分析建议 dimension-reduction。如果我将点投影到 4D 超平面，qhull 算法 运行s 没有错误（对于任何更高的维度，它不会 运行）。
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]
相同的投影（只是角度略有不同）：
我怀疑第一张图片没有足够的顶点，第二张图片可能太多了。当然，我无法从这些图中提取严格的信息。但是有没有一种好方法可以找出要使用的精度？或者也许是一个完全不同的方法来解决这个问题（我已经尝试了一些）？
在这个答案中，我假设您已经使用 PCA 将数据近乎无损地压缩为 4 维数据，其中缩减后的数据位于概念上面较少的 4 维多胞形中。我将描述一种解决此多面体的面的方法，这将反过来为您提供顶点。
设 R4 中的 xi, i = 1, ..., m 为 PCA 缩减数据点。
设 F = (a, b) 为 face，其中 a 在 R4 中，带有 • a = 1 和 b 在 R.
我们定义人脸loss函数L如下，其中λ+，λ- > 0 是您选择的参数。 λ+ 应该是一个很小的正数。 λ-应该是一个非常大的正数。
L(F) = sumi(λ+ • max(0, a • x i + b) - λ- • min(0, a • xi + b))
我们想找到 minimal 相对于损失函数 L 的面 F。所有最小面的小集合将描述你的多面体。您可以通过随机初始化 F 然后使用偏导数 ∂L / ∂aj、j = 1、2、3、4 和 ∂L / 执行梯度下降来求解最小人脸∂b。在梯度下降的每一步，约束一个 • a通过归一化为1。
∂L / ∂aj = sumi(λ+ • x j • [a • xi + b > 0] - λ- • x j • [a • xi + b < 0]) 对于 j = 1, 2, 3, 4
∂L / ∂b = sumi(λ+ • [a • xi + b > 0] - λ- • [a • xi + b < 0])
注意 Iverson brackets：如果 P 为真，则 [P] = 1，如果 P 为假，则 [P] = 0。
假设我有一个 6 维 space 的点云，我可以根据需要将其制作得尽可能密集。结果这些点位于 lower-dimensional 多面体的表面上（即点向量 (x1, x2, ... x6) 似乎是共面的）。
我想找到这个未知多胞形的顶点，我目前的尝试是通过 Python 中的 scipy 接口使用 qhull 算法。一开始我只会收到错误消息，显然是由于低维输入 and/or 许多退化点引起的。我尝试了几个brute-force方法来消除退化点，但不是很成功，所以最后，我想所有这些点都必须在凸包上。
This question 非常有帮助，因为它通过主成分分析建议 dimension-reduction。如果我将点投影到 4D 超平面，qhull 算法 运行s 没有错误（对于任何更高的维度，它不会 运行）。
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]
相同的投影（只是角度略有不同）：
我怀疑第一张图片没有足够的顶点，第二张图片可能太多了。当然，我无法从这些图中提取严格的信息。但是有没有一种好方法可以找出要使用的精度？或者也许是一个完全不同的方法来解决这个问题（我已经尝试了一些）？
在这个答案中，我假设您已经使用 PCA 将数据近乎无损地压缩为 4 维数据，其中缩减后的数据位于概念上面较少的 4 维多胞形中。我将描述一种解决此多面体的面的方法，这将反过来为您提供顶点。
设 R4 中的 xi, i = 1, ..., m 为 PCA 缩减数据点。
设 F = (a, b) 为 face，其中 a 在 R4 中，带有 • a = 1 和 b 在 R.
我们定义人脸loss函数L如下，其中λ+，λ- > 0 是您选择的参数。 λ+ 应该是一个很小的正数。 λ-应该是一个非常大的正数。
L(F) = sumi(λ+ • max(0, a • x i + b) - λ- • min(0, a • xi + b))
我们想找到 minimal 相对于损失函数 L 的面 F。所有最小面的小集合将描述你的多面体。您可以通过随机初始化 F 然后使用偏导数 ∂L / ∂aj、j = 1、2、3、4 和 ∂L / 执行梯度下降来求解最小人脸∂b。在梯度下降的每一步，约束一个 • a通过归一化为1。
∂L / ∂aj = sumi(λ+ • x j • [a • xi + b > 0] - λ- • x j • [a • xi + b < 0]) 对于 j = 1, 2, 3, 4
∂L / ∂b = sumi(λ+ • [a • xi + b > 0] - λ- • [a • xi + b < 0])
注意 Iverson brackets：如果 P 为真，则 [P] = 1，如果 P 为假，则 [P] = 0。