python - 使用SciKit-learn和SciPy进行K最近邻构建/搜索的速度

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

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

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

问题:

结果:尽管它们对于非常大的N越来越近，
SciKit学习似乎在构建时间和查询时间上都胜过SciPy。
其他人找到了吗？

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

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

实用性:SciPy KDTree不会腌制。据报道
this post，出现以下错误“PicklingError:无法
泡菜:找不到
scipy.spatial.kdtree.innernode”-我认为这是由于它是一个
嵌套结构。根据this post中报告的答案，
嵌套的结构可以用莳萝腌制。但是，莳萝给了我
同样的错误-这是为什么呢？

最佳答案

在获得答案之前，我想指出，当您的程序使用大量数字时，应始终使用numpy library中的numpy.array来存储此类数据。我不知道您使用的是哪个版本的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。 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多少，查询时间都保持不变(这意味着N = 1000和N = 1000000时scipy.spatial.KDTree的查询时间相同，而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的子类型。在所有空间划分方法(仅基于Wikipedia页面的用于快速最近邻搜索的快速精确方法)中，在低维欧几里德空间用于静态上下文中用于最近邻搜索的情况下，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)。因此，我们可以得到的最好结果就是k(d-k)树方法所具有的O(NlogN)的构建复杂度和O(logN)的查询复杂度。因此，根据我的研究，我会说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版本是什么，重现此错误的确切代码以及完整的错误消息？)

关于python - 使用SciKit-learn和SciPy进行K最近邻构建/搜索的速度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30447355/

KdTree

python - 使用SciKit-learn和SciPy进行K最近邻构建/搜索的速度