20220410-cKDTree

发表于 阅读次数： 本文字数： 1.7k 阅读时长 ≈ 2 分钟

cKDTree

  • KDTree：是查找大数据的最近邻居的快速方法；
  • 作用：快速将GPS点位根据最邻近距离投影到最近路网（两千万点位在2min内完成匹配）；

0. 基本基础

  • ARCGIS
  • 空间索引：指依据空间对象的位置和形状或空间对象之间的某种空间关系按照一定顺序排列的一种数据结构，其中包含空间对象的概要信息，如对象的标识、外界矩形以及指向空间对象实体的指针。作为一种辅助性的空间数据结构，空间索引介于空间操作算法和空间对象之间，通过筛选，排除大量与特定操作无关的空间对象，从而提高空间操作的速度和效率。
  • 研究历程：当前数据搜索的一个关键问题是速度。提高速度的核心技术是空间索引。空间索引是由空间位置到空间对象的映射关系。但空间索引技术并不单是为了提高显示速度。其技术核心是：根据搜索条件，比如一个矩阵，迅速找到与该矩形相交的所有空间对象集合。当数据量巨大，矩形框相对于全图很小时，这个集合相对于全图数据集大为缩小，从而减少了后续的处理复杂度。
  • 传统的空间索引一般是指对连续的地图进行网格化，从而将地图信息转化为矩阵信息进行有序存储，但网格化的问题是，如果网格分得过大，一个网格内会包含多条路段，因此即使可以快速定位到网格，依然还需要进行二次运算来判断最终的路段。考虑到目前计算机硬件能力足够，我们在进行网格化的时候可以进一步精细化，以存储换速度。因此，在此我们不再对路网进行网格索引，而直接对路段进行等距拆分为点。拆分完毕之后，一个路段便对应着多个点位，并共同构成了一个固定的路网空间索引表（路段ID，路段点经纬度，路段信息等）。而我们接下来要做的，就是找出每个GPS点位距离最近的路网空间点位，然后再将路网信息一并merge过来，即可完成路网的临近匹配了。之后我们的问题就转变为：给出A，B两个坐标矩阵，如何以最快的速度从A中找出距离B内每一个点最近的点位索引。

1. KDTree

  • KDTree是一个非常高效的最邻近搜索算法，通过建立索引树来提高检索速度。在Python中使用也非常简单，直接调用scipy.spatial即可。但KDTree包的问题在于，其本身是不支持以经纬度球面距离为metric来进行搜索的。而如果我们不进行经纬度转化，直接调用KDTree的话，会由于计算出的距离误差而导致我们的搜索出现偏差。
  • 参考矩阵：相当于我们的路网空间索引矩阵；
  • 对比矩阵：相当于我们的GPS点位矩阵；

2. 具体示例

给定数据集A（包含1,000,000条数据），求集合X（包含10,000个点）中的每个点的最邻近点，返回应该是10,000个索引。

  • cdist代码

    1
    2
    3
    4
    5
    6
    7
    8
    t = time.time()
    nn = np.array([])
    jump = 1000
    nloop = np.ceil(A.shape[0]/jump).astypr(int)
    for ii in range(nloop):
        temp = cdist(X, A[ii*jump : (ii+1)*jump])
        nn = np.append(nn, np.argmin(temp, axis = 0))
    print('Elapsed time: ', time.time() - t)

  • cKDTree代码

    1
    2
    3
    4
    t = time.time()
    tree = cKDTree(X)
    nn = tree.query(A, 1, n_jobs=4)[1]
    print('Elapsed time: ', time.time() - t)

3. KD-Tree

  • 应用举例：SIFT算法中做特征点匹配时利用到KDTree。特征点匹配实际上就是通过距离函数在高维矢量之间进行相似性检索的问题。
  • 索引结构中相似性查询：
    • 范围查询：给定查询点和查询距离的阈值，从数据集中找出所有与查询点距离小于阈值的数据；
    • K近邻查询：给定查询点和正整数K，从数据集中找出距离查询点最近的K个数据；
  • 特征匹配算子：
    • 线性扫描法：将数据集中的点与查询点逐一进行距离比较；
    • 建立数据索引，然后再进行快速匹配：实际数据一般都会呈现出簇状的聚类形态，通过设计有效的索引结构可以大大加快检索的速度。

Reference