使用 SciKit-learn 和 SciPy 的 K 最近邻的速度 build/search

Question

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

现成的两个选择是 SciPy 和 SciKit-learn 中的 KDTree 结构。下面我将针对大范围列表长度的构建速度和查询速度对其中两个进行分析。我还 pickle SciKit-learn 结构并显示从 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 )

比较查询时间的代码：

# 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 space 中工作（尽管数据会很密集所以蛮力出来了），有没有更好的结构低维 kNN 搜索？
The Speed：看起来这两种方法的构建时间是在大 N 越来越近，但我的电脑放弃了我 - 任何人都可以为我验证这个更大的 N？！谢谢！！是否重建时间继续大致呈线性增长？
实用性：SciPy KDTree 不会 pickle。据报道 this post，我收到以下错误“PicklingError: Can't 泡菜：找不到 scipy.spatial.kdtree.innernode" - 我认为这是因为它是嵌套结构。根据 this post 中报告的答案，嵌套结构可以用莳萝腌制。然而，莳萝给了我同样的错误 - 这是为什么？

Answer 1

在我得到答案之前，我想指出，当你有一个使用大量数字的程序时，你应该始终使用 numpy library to store that kind of data. I don't know what version of Python, scikit-learn, and SciPy are you using, but I am using Python 3.7.3, scikit-learn 0.21.3, and SciPy 1.3.0. When I ran your code to compare build-times, I got AttributeError: 'list' object has no attribute 'size'. This error is saying that list listOfRandom2DPoints has no attribute size. The problem is that sklearn.neighbors.KDTree expects numpy.array which has attribute size. Class scipy.spatial.KDTree works with Python lists but as you can see in the source code of __init__ method of class scipy.spatial.KDTree 中的 numpy.array，第一行是 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), and scipy.spatial.KDTree is written in pure Python code (link to source code).
中实现的
（如果你不知道什么是 Cython，一个过于简单的解释会是 Cython 使得在 Python 和 main 中编写 C 代码成为可能这样做的原因是 C 比 Python)
快得多
SciPy 库在 Cython scipy.spatial.cKDTree (link to source code) 中也有实现，它的工作原理与 scipy.spatial.KDTree 相同，如果你比较 [=17= 的构建时间] 和 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的构建算法（class的__init__方法）的时间复杂度为O(KNlogN)(about scikit-learn Nearest Neighbor Algorithms) so in your case it would be O(2NlogN) which is practically O(NlogN). Based on very similar build times of sklearn.neighbors.KDTree and scipy.spatial.cKDTree I assume that the build algorithm of scipy.spatial.cKDTree also has time complexity of O(NlogN). I am no expert on nearest neighbor search algorithms, but based on some online search, I would say that for low-dimensional nearest neighbor search algorithms this as fast as it can be. If you go to nearest neighbor search Wikipedia page you will see that there are exact methods and approximation methods. k-d tree is exact method, it is subtype of space partitioning methods. Of all space partitioning methods (only fast exact methods for nearest neighbor search based on Wikipedia page), k-d tree is the best method in the case of low-dimensional Euclidean space for nearest neighbor search in static context (there isn't a lot of insertions and deletions). Also if you look at approximation methods under greedy search in proximity neighborhood graphs you will see "Proximity graph methods are considered the current state-of-the-art for the approximate nearest neighbors search." When you look at the research article that is cited for this method (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 比 [ 慢大约 10 倍=17=] 并且对于 N = 1000000，scipy.spatial.KDTree 大约是 sklearn.neighbors.KDTree 的两倍。我不确定为什么会这样，但我怀疑对于大 N，内存成为比操作数更大的问题。

我检查了重建时间也高达 1000000，它确实线性增加，这是因为函数的持续时间 pickle.loads 与加载对象的大小成线性比例。
对我来说，sklearn.neighbors.KDTree、scipy.spatial.KDTree 和 scipy.spatial.cKDTree 的 pickling 有效，所以我无法重现您的错误。我猜问题是你有一个旧版本的 SciPy 所以更新 SciPy 到最新版本应该可以解决这个问题。

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

使用 SciKit-learn 和 SciPy 的 K 最近邻的速度 build/search

Speed of K-Nearest-Neighbour build/search with SciKit-learn and SciPy

python

scipy

scikit-learn

nearest-neighbor

kdtree