python - 使用 SciKit-learn 和 SciPy 构建/搜索 K-Nearest-Neighbour 的速度

Question

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

两种现成的选择是 SciPy 和 SciKit-learn 中的 KDTree 结构。下面我将在大范围的列表长度上对其中两个的构建速度和查询速度进行概要分析。我还对 SciKit-learn 结构进行了腌制，并显示了从腌制中重新加载对象的时间。这些在图表中进行了比较，用于生成时序的代码包含在下面。

正如我在图中所示，对于大 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 )

比较查询时间的代码:

# 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 )

问题:

结果 :虽然它们越来越接近非常大的 N，
SciKit-learn 似乎在构建时间和查询时间上都击败了 SciPy。
其他人有没有发现这个？

数学 : 有没有更好的结构可用于此？
我只在 2D 空间中工作(虽然数据会很
密集所以蛮力消失了)，是否有更好的结构
低维 kNN 搜索？

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

实用性 :SciPy KDTree 不会腌制。如报道
this post ，我收到以下错误“PicklingError:不能
泡菜:它没有被发现
scipy.spatial.kdtree.innernode” - 我认为这是因为它是一个
嵌套结构。根据 this post 中报告的答案,
嵌套结构可以用莳萝腌制。然而，莳萝给了我
同样的错误 - 为什么会这样？

Answer 1

在我回答之前，我想指出，当您的程序使用大量数字时，您应该始终使用 numpy.array来自 numpy library来存储这种数据。不知道是什么版本的Python，scikit-learn , 和 SciPy您在使用吗，但我使用的是 Python 3.7.3、scikit-learn 0.21.3 和 SciPy 1.3.0。当我运行你的代码来比较构建时间时，我得到了 AttributeError: 'list' object has no attribute 'size' .这个错误是说列表 listOfRandom2DPoints没有属性 size .问题是sklearn.neighbors.KDTree预计 numpy.array具有属性 size .类(class)scipy.spatial.KDTree适用于 Python 列表，但正如您在 source code of __init__ method of class 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))

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

现在回答您的问题:

就像你说的 scikit-learn 似乎在构建时间里让 SciPy 变得更好。发生这种情况的原因不是 scikit-learn 有更快的算法，而是 sklearn.neighbors.KDTree在 Cython 中实现( link to source code ) 和 scipy.spatial.KDTree是用纯 Python 代码编写的 ( link to source code )。

(如果你不知道 Cython 是什么，一个过于简单的解释会
Cython 使在 Python 和 main 中编写 C 代码成为可能
这样做的原因是 C 比 Python 快得多)

SciPy 库在 Cython 中也有实现 scipy.spatial.cKDTree ( link to source code )，它的作用与 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 实现)大约与 sklearn.neighbors.KDTree 一样快.我已经测试了最多 N = 10000000 的查询时间，并得到了与您相同的结果。查询时间与 N 无关(意味着 scipy.spatial.KDTree 的查询时间对于 N = 1000 和 N = 1000000 是相同的，对于 sklearn.neighbors.KDTree 和 scipy.spatial.cKDTree 的查询时间是相同的)。那是因为查询(搜索)时间复杂度是 O(logN) 并且即使对于 N = 1000000，logN 也非常小，因此差异太小而无法衡量。

sklearn.neighbors.KDTree的构建算法( __init__ 类的方法) 的时间复杂度为 O(KNlogN) ( about scikit-learn Nearest Neighbor Algorithms ) 所以在你的情况下它是 O(2NlogN) ，实际上是 O(NlogN)。基于非常相似的构建时间 sklearn.neighbors.KDTree和 scipy.spatial.cKDTree我假设 scipy.spatial.cKDTree 的构建算法也有 O(NlogN) 的时间复杂度。我不是最近邻搜索算法的专家，但基于一些在线搜索，我会说对于低维最近邻搜索算法，这尽可能快。如果你去nearest neighbor search Wikipedia page你会看到有 exact methods和 approximation methods . k-d tree是精确方法，它是 space partitioning methods 的子类型.在所有空间划分方法中(仅基于维基百科页面的最近邻搜索的快速精确方法)，kd 树是静态上下文中最近邻搜索的低维欧几里德空间的最佳方法(没有很多插入和删除)。另外，如果您查看 greedy search in proximity neighborhood graphs 下的近似方法您将看到“接近图方法​​被认为是近似最近邻搜索的最新技术。”当您查看为此方法引用的研究文章 ( Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs ) 时，您会发现此方法的时间复杂度为 O(NlogN)。这意味着对于低维空间 k-d 树(精确方法)与近似方法一样快。目前，我们已经比较了用于最近邻搜索的结构的构建(构造)时间复杂度。所有这些算法的搜索(查询)时间复杂度为 O(logN)。所以我们能得到的最好的是构建 O(NlogN) 的复杂度和 O(logN) 的查询复杂度，这就是我们在 k-d 树方法中所拥有的。所以根据我的研究，我会说 k-d 树是低维最近邻搜索的最佳结构。

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

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

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

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

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