1

我开始尝试使用该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. 浏览 Google 的搜索结果，我注意到有一些算法可以计算凸包的近似值。你推荐他们吗？他们可以在我的情况下工作吗？其中一些是否已经有 Python 实现？
  3. 可能我想计算高维空间的凸包，最多 100,000 维。这是疯狂，还是可以以明智的方式完成？
4

1 回答 1

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

于 2020-09-03T00:20:56.220 回答