Scipy.Spatial.KDTree.query - 大数据集问题

Question

我在玩SciPy.Spatial里的KDQuery函数。遇到一个问题，就是当我的数据量变得非常大时，情况就不太好了。我知道这个算法并不是特别适合处理大数据集，但从源代码来看，数据量的增加应该只会让处理时间变长，而不会影响结果。

这里有一段代码：

sizes = [ 10**i for i in range(5,6) ] #10^5 for this test
data = np.random.random_integers(0,100,(sizes[-1],2))
for size in sizes:
    kd = ps.common.KDTree(data)
    nnq = kd.query(data,k=2+1, p=2)
    info = nnq[1] #This is the indices of the neighbors
    neighbors = {}
    idset = np.arange(len(info)) #Indices of the input point
    for i, row in enumerate(info):
        row = row.tolist()
        row.remove(i)
        neighbors[idset[i]] = list(row)

当我试图从列表中移除一个不在列表里的元素时，就会出现值错误（ValueError list.remove(x): x not in list）。对于小于10^5的数据量，这段代码运行得很正常。

出现这个错误的一个可能原因是递归深度达到了限制。为了检查这个问题，我把递归深度设置到了1,000,000（sys.setrecursionlimit(1000000)）。但这样做并没有解决问题。

Answer 1

这个错误出现在你的代码中，具体是在这行代码row.remove(i)。问题在于，你的随机数据集中可能会有重复的点，有时候同一个点可能会出现超过三次。当数据集很大的时候，这种情况就更常见了。当出现这种情况时，一个点的三个最近邻居可能不包括它自己。这就导致了row.remove(i)出错。