以更高的尺寸凸出船体，找到多面体的顶点 [英] Convex hull in higher dimensions, finding the vertices of a polytope

问题描述

假设我有一个在6维空间中给出的点云，可以根据需要将该点云密度提高.这些点位于低维多面体的表面上(即，点向量(x1，x2，... x6)看起来是共面的).

Suppose I have a point cloud given in 6-dimensional space, which I can make as dense as needed. These points turn out to lie on the surface of a lower-dimensional polytope (i.e. the point vectors (x1, x2, ... x6) appear to be coplanar).

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

I would like to find the vertices of this unknown polytope and my current attempt makes use of the qhull algorithm, via the scipy interface in Python. In the beginning I would only get error messages, apparently caused by the lower dimensional input and/or the many degenerate points. I have tried a couple of brute-force methods to eliminate the degenerate points, but not very successful and so in the end, I suppose that all these points must lie on the convex hull.

此问题很有帮助，因为它建议通过主成分分析来减小尺寸.如果将这些点投影到4D超平面，则qhull算法将运行而不会出错(对于任何更高维度，它均不会运行).

This question has been very helpful, as it suggests a dimension-reduction via Principal Component Analysis. If I project the points to a 4D hyperplane, the qhull algorithm runs without errors (for any higher dimension it does not run).

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输出仅包含索引，为什么这些索引不匹配初始点的索引?

The answer in above question mentions that the simplices need to be transformed back after one computes the convex hull of the projected points. But the qhull output consists of only the indices, and why would these not match the indices of the initial points?

现在，我的问题是，我不知道要使用哪种精度来实际获得适当的顶点.无论我使点云有多密集，获得的顶点都以不同的精度而不同.例如，对于(10000，6)数组中的初始点，我得到了(其中E0.03是它可以工作的最大值):

Now my problem is that I do not know which precision to use to actually obtain the proper vertices. Regardless of how dense I make the point cloud, the obtained vertices differ with different precisions. For instance, for initial points in a (10000, 6) array I get (where E0.03 is the maximum for which this works):

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的某些(不是十分有用的)投影中(蓝色点代表对初始点云的选择):

And plotting it in some (not terribly informative) projection of axes 0,1,2 (where the blue points represent a selection of the initial point cloud):

但是，为了获得更高的精度(当然)，我得到了另一个设置:

But for a higher precision (of course) I get a different set:

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]

相同的投影(只是稍微不同的角度):

Same projection (just slightly different angle):

我怀疑第一张图片的顶点不够，第二张图片的顶点可能太多.虽然我当然不能从这些地块中提取出严格的信息.但是找到一种使用哪种精度的好方法吗?也许是完全不同的方法来解决这个问题(我已经尝试了一些)?

I would suspect that the first picture has not enough vertices and that the second picture possibly has too many. Though of course I cannot extract rigorous information from these plots. But is there a good way of finding out which precision to use? Or perhaps a completely different approach to this problem (I tried a few already)?

推荐答案

在此答案中，我将假定您已经使用PCA几乎无损地将数据压缩为4维数据，其中精简数据位于4位.上几乎没有面孔的三维多面体.我将描述一种解决该多面体的面孔的方法，该方法将为您提供顶点.

In this answer, I will assume you have already used PCA to near-losslessly compress the data to 4-dimensional data, where the reduced data lies in a 4-dimensional polytope with conceptually few faces. I will describe an approach to solve for the faces of this polytope, which will in turn give you the vertices.

让R ⁴ 中的x _i (i = 1，...，m)成为PCA减少的数据点.

Let x_i in R⁴, i = 1, ..., m, be the PCA-reduced data points.

让F =(a，b)为 face ，其中a在R ⁴ 中并带有• a = 1，b在R中.

Let F = (a, b) be a face, where a is in R⁴ with a • a = 1 and b is in R.

我们如下定义面部 loss 函数L，其中λ ⁺ ，λ ^-> 0是您选择的参数. λ ⁺ 应该是一个很小的正数. λ ^-应该是一个非常大的正数.

We define the face loss function L as follows, where λ⁺, λ^- > 0 are parameters you choose. λ⁺ should be a very small positive number. λ^- should be a very large positive number.

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

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设为1.

We want to find minimal faces F with respect to the loss function L. The small set of all minimal faces will describe your polytope. You can solve for minimal faces by randomly initializing F and then performing gradient descent using the partial derivatives ∂L / ∂a_j, j = 1, 2, 3, 4, and ∂L / ∂b. At each step of gradient descent, constrain a • a to be 1 by normalizing.

∂L/∂a _j = sum _i (λ ⁺ • x _j • [a• x _i + b> 0]-λ ^-• x _j • [a• x _i + b< 0])for j = 1，2，3，4

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

∂L/∂b= sum _i (λ ⁺ • [a• x _i + b> 0]- λ ^-• [a• x _i + b< 0])

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

请注意艾弗森括号:如果P为真，则[P] = 1，而[P] =如果P为假，则为0.

Note Iverson brackets: [P] = 1 if P is true and [P] = 0 if P is false.

这篇关于以更高的尺寸凸出船体，找到多面体的顶点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！