用qhull/SciPy计算大型数据集凸包时的问题

Question

我开始使用scipy.spatial.ConvexHull函数进行实验，如果我理解正确的话，它是qhull C库的包装器。我使用的是SciPy 0.19.1和Python3。

我第一次使用的是一个真实的数据集，其中包含了21个维度的700个点，以及scipy.spatial.ConvexHull崩溃，其中有一个错误：scipy.spatial.qhull.QhullError: QH6235 qhull error (qh_memalloc): negative request size (-2003053336). Did int overflow due to high-D?。

经过几次使用以下示例Python3代码的尝试：

import numpy as np
X = np.random.randn(40,21)
print("Computing convex hull of X (shape: " + str(X.shape) + ")...")
from scipy.spatial import ConvexHull
hull = ConvexHull(X)

我设法把这个问题缩小到维度。与39个随机产生的点在21个维度，它工作。有40分，有时失败，有时成功。我不确定，但似乎有内存分配错误？

1. 有办法避免记忆问题吗？对于凸包算法来说，700点太多了吗？
2. 在Google中浏览搜索结果时，我注意到有一些算法可以计算凸包的近似。你推荐他们吗？他们能在我的情况下工作吗？其中一些已经有Python实现了吗？
3. 我可能想要计算高维空间的凸壳，高达100,000维。这是疯了，还是能以一种明智的方式进行呢？

Answer 1

TLDR:高维斗争的ConvexHull

ConvexHull使用qhull。由于需要大量内存，我在matlab (也使用qhull)中处理了一个高维问题的等效实现。我联系了那些确认这是个问题的开发人员。

有关监视Qhull内存性能的帮助，请参阅Qhull“http://www.qhull.org/html/qh-code.htm#performance的性能”

“何时使用Qhull”也可能有助于http://www.qhull.org/html/index.htm#when。