使用SciKit-learn和SciPy进行K-Nearest-Neighbor构建/搜索的速度

Question

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

现有的两个选择是SciPy和SciKit-learn中的KDTree结构.下面我分析了这两个中的两个,用于在大量列表长度上构建速度和查询速度.我还挑选了SciKit-learn结构并显示了从pickle重新加载对象的时间.这些在图中进行比较,下面包括用于生成时序的代码.

正如我在图中所示,从酸洗中加载比从头开始加载大N的半个数量级更快,这表明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 )

用于比较查询时间的代码:

# Profiling the query time for the two KD-tree structures
import scipy.spatial, sklearn.neighbors

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

theSciPyQueryTime = []
theSklQueryTime = []

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

    setup = """from __main__ import sciPiTree,sklTree
from random import randint
length = """ + str(length) + """
randPoint = [randint(0,""" + str(dim) + """),randint(0,""" + str(dim) + """)]""" 

    sciPiTree = scipy.spatial.KDTree(listOfRandom2DPoints, leafsize=20)
    sklTree = sklearn.neighbors.KDTree(listOfRandom2DPoints, leaf_size=20)

    theSciPyQueryTime.append( timeit.timeit('sciPiTree.query(randPoint,10)', setup=setup, number=nTimes)/nTimes )
    theSklQueryTime.append( timeit.timeit('sklTree.query(randPoint,10)', setup=setup, number=nTimes)/nTimes )

 

问题:

1. 结果:虽然他们越来越接近非常大的N,但SciKit-learn似乎在构建时间和查询时间方面都超过了SciPy.还有其他人发现了这个吗？

2. 数学:有没有更好的结构？我只是在2D空间工作(尽管数据非常密集,因此蛮力不足),是否有更好的低维kNN搜索结构？

3. 速度:看起来两种方法的构建时间越来越接近N但是我的电脑放弃了我 - 任何人都可以为我验证更大的N吗？谢谢!!重建时间是否继续大致线性增加？

4. 实用性:SciPy KDTree不会腌制.正如 本文所述,我收到以下错误"PicklingError:不能发现:它没有被发现为scipy.spatial.kdtree.innernode" - 我认为这是因为它是一个嵌套结构.根据这篇文章中的回答,嵌套结构可以用莳萝腌制.但是,莳萝给了我同样的错误 - 这是为什么？

Answer 1

之前，我要的答案，我想指出的是，当你有一个使用大集数的程序，你应该总是使用numpy.array从numpy的库来存储数据的类型。我不知道您使用的是什么版本的 Python、scikit-learn和SciPy，但我使用的是 Python 3.7.3、scikit-learn 0.21.3 和 SciPy 1.3.0。当我运行你的代码来比较构建时间时，我得到了AttributeError: 'list' object has no attribute 'size'. 这个错误是说 listlistOfRandom2DPoints没有属性size。问题是sklearn.neighbors.KDTree期望numpy.array具有属性size. 类scipy.spatial.KDTree与 Python 列表一起使用，但正如您在类的__init__方法scipy.spatial.KDTree的源代码中所见，第一行是self.data = np.asarray(data)，这意味着数据将被转换为numpy.array.

因此，我更改了您的台词：

from random import randint
listOfRandom2DPoints = [ [randint(0,dim),randint(0,dim)] for x in range(length)]

到：

import numpy as np
ListOfRandom2DPoints = np.random.randint(0, dim, size=(length, 2))

（此更改不会影响速度比较，因为在设置代码中进行了更改。）

现在回答您的问题：

1. 就像你说的 scikit-learn 似乎在构建时间里让 SciPy 变得更好。发生这种情况的原因不是 scikit-learn 有更快的算法，而是sklearn.neighbors.KDTree在Cython 中实现（链接到源代码），并且scipy.spatial.KDTree是用纯 Python 代码编写的（链接到源代码）。

   （如果你不知道 Cython 是什么，一个过于简单的解释是 Cython 使用 Python 编写 C 代码成为可能，这样做的主要原因是 C 比 Python 快得多）

   SciPy的图书馆也有在用Cython实现scipy.spatial.cKDTree（链接到源代码），它的工作原理相同scipy.spatial.KDTree，如果你比较构建时间sklearn.neighbors.KDTree和scipy.spatial.cKDTree：

   timeit.timeit('scipy.spatial.cKDTree(npListOfRandom2DPoints, leafsize=20)', setup=setup, number=nTimes)
   timeit.timeit('sklearn.neighbors.KDTree(npListOfRandom2DPoints, leaf_size=20)', setup=setup, number=nTimes)
   

   构建时间非常相似，当我运行代码时，scipy.spatial.cKDTree速度快了一点（大约 20%）。

   随着查询时间情况非常相似，scipy.spatial.KDTree（纯Python实现）是十倍左右比较慢sklearn.neighbors.KDTree（用Cython实现）和scipy.spatial.cKDTree（用Cython实现）是aproximatly一样快sklearn.neighbors.KDTree。我已经测试了最多 N = 10000000 的查询时间，并得到了与您相同的结果。查询时间保持不变而不管N（意味着查询时间scipy.spatial.KDTree是相同的，对于N = 1000和N = 1000000，以及用于查询时间同样的事情sklearn.neighbors.KDTree和scipy.spatial.cKDTree）。那是因为查询（搜索）时间复杂度是 O(logN) 并且即使对于 N = 1000000，logN 也非常小，因此差异太小而无法衡量。

2. sklearn.neighbors.KDTree(__init__类方法) 的构建算法的时间复杂度为 O(KNlogN) （关于 scikit-learn 最近邻算法），因此在您的情况下它将是 O(2NlogN)，实际上是 O(NlogN)。基于非常类似的编译时间sklearn.neighbors.KDTree和scipy.spatial.cKDTree我认为的生成算法scipy.spatial.cKDTree也有时间O（NlogN）的复杂性。我不是最近邻搜索算法的专家，但基于一些在线搜索，我会说对于低维最近邻搜索算法，这尽可能快。如果你去 最近邻搜索维基百科页面，你会看到有精确方法和近似方法。kd树是精确方法，它是空间分区方法的子类型。在所有空间划分方法中（仅基于维基百科页面的最近邻搜索的快速精确方法），kd 树是静态上下文中最近邻搜索的低维欧几里德空间的最佳方法（没有很多插入和删除）。此外，如果您查看邻近邻域图中贪婪搜索下的近似方法，您将看到“邻近图方法被认为是近似最近邻搜索的最新技术水平”。当您查看针对此方法引用的研究文章时（使用分层导航小世界图进行有效且稳健的近似最近邻搜索）) 可以看出该方法的时间复杂度为 O(NlogN)。这意味着对于低维空间 kd 树（精确方法）与近似方法一样快。目前，我们已经比较了用于最近邻搜索的结构的构建（构造）时间复杂度。所有这些算法的搜索（查询）时间复杂度为 O(logN)。所以我们能得到的最好的是构建 O(NlogN) 的复杂度和 O(logN) 的查询复杂度，这就是我们在 kd 树方法中所拥有的。所以根据我的研究，我会说 kd 树是低维最近邻搜索的最佳结构。

   （我认为如果有比 scikit-learn 和 SciPy 更好（更快）的方法来进行最近邻搜索，就会实现该方法。同样从理论的角度来看，知道最快的排序算法的时间复杂度为 O(NlogN)，使用时间复杂度小于 O(NlogN) 的最近邻搜索构建算法将是非常令人惊讶的。）

3. 就像我说的，您正在sklearn.neighbors.KDTree与 Cython 实现和scipy.spatial.KDTree纯 Python 实现进行比较。理论上sklearn.neighbors.KDTree应该比 快scipy.spatial.KDTree，我将它们与 1000000 进行比较，它们似乎在大 N 处更接近。对于 N = 100，scipy.spatial.KDTree比 慢约 10 倍sklearn.neighbors.KDTree，对于 N = 1000000，scipy.spatial.KDTree大约是 慢的两倍sklearn.neighbors.KDTree。我不确定为什么会发生这种情况，但我怀疑对于大 N，内存成为比操作次数更大的问题。

   我检查了重建时间也高达 1000000 并且它确实线性增加，这是因为函数的持续时间pickle.loads与加载对象的大小成线性比例。

4. 对我来说，酸洗sklearn.neighbors.KDTree，scipy.spatial.KDTree和scipy.spatial.cKDTree作品，所以我不能重现你的错误。我猜问题是你有一个旧版本的 SciPy，所以将 SciPy 更新到最新版本应该可以解决这个问题。

   （如果您需要有关此问题的更多帮助，则应在问题中添加更多信息。您的 Python 和 SciPy 版本是什么，重现此错误的确切代码以及完整的错误消息？）