使用SciKitlearn和SciPy构建/搜索knearstneighbour的速度

Question

我有一个很大的二维点集，并希望能够快速地查询该集合中二维空间中任何点的k近邻。由于它是低维的，KD树似乎是一种很好的方法。我的初始数据集只会很少更新，所以查询一个点的时间对我来说应该比构建时间更重要。但是，每次运行程序时，我都需要重新加载对象，因此我还需要一个可以快速保存和重新加载的结构。在

两个现成的选择是SciPy和scikitlearn中的KDTree结构。下面，我将介绍这两种方法在很大范围的列表长度上的构建速度和查询速度。我还pickle SciKit学习结构并显示从pickle重新加载对象的时间。它们在一个图形中进行比较，用于生成计时的代码如下所示。在

正如我在图中所示，对于大N，从pickle加载比从头构建要快半个数量级，这表明KDTree适合我的用例（即频繁的重新加载，但很少重新构建）。在

用于比较生成时间的代码：

# Profiling the building time for the two KD-tree structures and re-loading from a pickle
import math, timeit, pickle, sklearn.neighbors

the_lengths = [100, 1000, 10000, 100000, 1000000]

theSciPyBuildTime = []
theSklBuildTime = []
theRebuildTime = []

for length in the_lengths:
    dim = 5*int(math.sqrt(length))
    nTimes = 50
    from random import randint
    listOfRandom2DPoints = [ [randint(0,dim),randint(0,dim)] for x in range(length)]

    setup = """import scipy.spatial
import sklearn.neighbors
length = """ + str(length) + """
dim = """ + str(dim) + """
from random import randint
listOfRandom2DPoints = [ [randint(0,dim),randint(0,dim)] for x in range(length)]"""

    theSciPyBuildTime.append( timeit.timeit('scipy.spatial.KDTree(listOfRandom2DPoints, leafsize=20)', setup=setup, number=nTimes)/nTimes )
    theSklBuildTime.append( timeit.timeit('sklearn.neighbors.KDTree(listOfRandom2DPoints, leaf_size=20)', setup=setup, number=nTimes)/nTimes )

    theTreeSkl = sklearn.neighbors.KDTree(listOfRandom2DPoints, leaf_size=20, metric='euclidean')
    f = open('temp.pkl','w')
    temp = pickle.dumps(theTreeSkl)

    theRebuildTime.append( timeit.timeit('pickle.loads(temp)', 'from __main__ import pickle,temp', number=nTimes)/nTimes )

比较查询时间的代码：

^{pr2}$

在

问题：

1. 结果：虽然它们在非常大的N下越来越接近， scikitlearn似乎在构建时间和查询时间上都胜过SciPy。 其他人找到这个了吗？

2. 数学：是否有更好的结构可用于此？ 我只在二维空间工作（虽然数据将相当 有没有更好的结构 低维kNN搜索？

3. 速度：看起来这两种方法的构建时间是 越来越接近大N，但我的电脑放弃了我-谁能 为我验证一下这个更大的N？！谢谢！！重新构建时间 继续大致线性增长？

4. 实用性：SciPy KDTree不会被pickle。如中所述 this post，我得到了以下错误“PicklingError:Can't” 皮克：它不是 scipy.space.kdtree.innernode“-我想这是因为它是一个 嵌套结构。根据this post中的一个回答， 嵌套结构可以用莳萝来腌制。但是，迪尔给了我 同样的错误-为什么会这样？

Answer 1

我建议尝试使用SciKit learn中的Gaussian Mixture Models来解决此类问题。既然你的数据是二维的，它应该能正常工作。在