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

Question

我开始使用scipy.spatial.ConvexHull函数进行实验，它(如果我理解正确的话(是qhullC库的包装器。我正在使用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)

我设法将问题缩小到维度。它有 21 个维度的 39 个随机生成的点，可以工作。40分，有时崩溃，有时成功。我不确定，但似乎存在内存分配错误？

1. 有没有办法避免内存问题？700 分对于凸包算法来说太多了吗？
2. 在谷歌中浏览搜索结果时，我注意到有一些算法可以计算凸包的近似值。你推荐他们吗？它们能在我的情况下工作吗？其中一些已经有Python实现了吗？
3. 可能我想计算高维空间的凸包，最多 100,000 维。这是疯狂，还是可以用合理的方式完成？

Answer 1

TLDR：在高维度上挣扎的凸壳

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

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

"何时使用Qhull"也可能有所帮助 http://www.qhull.org/html/index.htm#when