一种基于数据空间自适应规则网格划分的Skd-tree最近邻算法

王荣秀，王 波

（1.重庆工商大学 人工智能学院，重庆 400067；2.重庆理工大学 理学院，重庆 400054）

如何查询给定数据在数据集中的最近邻者是数据应用中的一类基本问题。最近邻算法KNN（k-nearest neighbor）能有效地对大规模空间数据进行分类与识别，无需参数训练，简单直观，易于实现，适合多分类问题；其缺点是缺少分类规则，计算量大，导致分类效率较低；同时在样本数量不平衡时，其分类效果不够理想［1－2］。针对KNN算法的不足，近年来不少学者提出了很多改进算法，如引入密度分布参数的样本划分来提高分类效率，或采用可调权重的k最近邻法来改善分类效果等［3－6］。这些算法大多都是对KNN本身的一种调整，因此改进效果有限。从原理上来看，如果能尽量地把KNN的有效搜索空间缩小，并使局部搜索空间中的样本平衡，则可有效提高分类效率和改善分类效果。最常用的方法就是构建优化的空间数据索引，快速收缩查询空间；同时充分利用数据索引结构，简化分类流程，在数据索引得到的局部空间中应用KNN，以达到提高分类效率和分类效果的目的。

树形结构由于表达能力强，无需参数、代价较小等优点，因此被广泛用于构建数据索引，如常见的数据索引kd-tree和R-tree。树形索引的构建实质上是通过对数据空间的分割，将数据集的特征属性，如密度、分布区域、相互位置、维度、均衡性等体现为空间结构与层次，从而把对数据的处理约化为空间关系的计算，因此空间的分割方式及对分割后形成的空间网格的处理方法是决定数据分类效率与分类效果的关键因素。例如，在DBSCAN算法中，对数据空间进行网格划分是一类常用手段。Gunawan等［7］认为合理的网格划分可以有效改善DBSCAN算法的复杂度，通过网格之间的拓朴关系，建立相应的网格索引指数，可以更快地搜索邻近网格；同时通过网格的合并与扩展，可以减少数据空间的冗余。Thapana等［8］研究了在多维数据空间进行规则网格划分的优缺点，认为规则网格的对称性和可移植性使网格的融合更方便、更高效；但在高维空间中使用大小相同的超方体进行分割时，近邻网格的数量呈几何级数增长。为避免高维数据在超方体分割时产生的“近邻爆炸”问题，他采用了一种类似于位图的结构索引（称为HyperGrid Bitmap）来标注非空网格，以达到过滤空网格的目的。

kd-tree采用最简数量的超平面来实现空间的分割，分割属性则为数据在各维度上的中值，每一超平面有且仅有一个数据；其树形结构具有轴对齐、场景自适应划分、低存储消耗和快速遍历等优势；相较于R-tree，kd-tree更适用于在高维数据之间进行相似性检索，如图像搜索、特征点匹配等。将kd-tree与KNN相结合，就得到kd-tree KNN，但由于kd-tree KNN采用超球体来处理邻近网格中的数据，必然需要求解超球面与超平面的相交问题，长方超体在空间维度上的尺度差异也带来了额外的困难，结果导致kd-tree KNN需要回溯至其他非叶子节点来寻找最近邻匹配，从而导致分类效率降低［9－10］；目前对kd-tree KNN算法的改进主要分为2类［9，11－14］，第1类是设计优化的空间网格算法来减少回溯节点数量，如Chen等［15］针对长方超体的空间结构，引入了一种参考网格，研究了参考网格与其周围数据的距离特性，证明了网格之外的任意点到网格的最远距离必然是网格的某个顶点；同时网格外的任意点到网格的最近距离必然是网格边界（超平面）上的点。依据最近最远数据点，可以滤除不必要的计算节点；同时通过修改kd-tree的树形结构，将参考网格作为各节点的索引指标，有效减少了回溯节点数量。由于需要事先计算和存储数据到参考网格的距离信息，这种方法不适用于高维数据，且存储代价相对较大。对kd-tree KNN算法改进的第2类主要是球树算法或采用球状空间来划分数据空间，从而简化或减少超球面与超平面的分割算法或相交数量。球树算法的基本思想是直接采用KNN中的超球体来找替长方超体进行空间分割，如陈晓康等［9］采用由大到小、层层包含的超球体来完成空间的划分，通过空间的递归关系，最终构建出与之相适应的kd-tree。在实现最近邻查询时，只需通过kd-tree索引得到数据所在的超球体，则此球体内的数据可以作为优化的距离估计，再应用KNN计算被查数据到相邻球体中各节点的距离，从而得到最近邻结果。对欧氏空间进行球状分割存在一个基本的矛盾，那就是网格与数据空间形状异构，因此球树算法更适用于数据呈团族分布的情况，且通常需要与聚类算法相结合。综上所述，减少回溯节点往往排除可能的最优匹配数据，增加查询算法难度，影响最终分类的成功率；而采用超球面来划分数据空间则存在区域重叠或划分不完全等问题，同时超球面的计算增加计算负荷，使kd-tree的构建较为复杂，最终影响分类效率与分类效果。

针对目前kd-tree KNN算法的不足，本文提出了一种改进的Skd-tree KNN最近邻算法，采用均匀的超方体空间划分策略来构建kd-tree索引结构，将数据置于网格内部，网格大小可适应邻近数据的分布特点，从而得到局部均衡的样本并有效缩小搜索空间；结合KNN最近邻匹配算法，无需节点回溯就可实现数据的快速分类。为充分利用规则方体对空间的分割优势，文中引入了查询超体以适应规则的空间结构；同时为避免相应的“近邻爆炸”问题，通过建立非空网格的索引路径指数，过滤空的近邻网格，从而排除无关近邻数据。数字实验的结果证明了Skd-tree KNN比kd-tree KNN具备更好的索引定位精度、更少的无关数据回溯和计算，更短的查询时间，尤其适用于数据样本较大或维度较高数据的最近邻查询。

1 kd-tree与KNN算法原理

kd-tree指k dimensional tree，是Friedman等人于1977年提出的针对高维数据建立二叉索引树的一种方法；通过对高维数据的层次划分，从而构建出索引树，基本算法如下：

算法 kd-tree索引树的构建

输入：k维数据

输出：kd-tree索引树

步骤1 确定出分裂属性。先计算出各数据分布在k个维度上的方差，方差最大者说明数据相应维度上的分散程度最大，数据划分得到的分辨率最高。设数据在第i维上的方差最大，则选取数据第i维作为分裂属性。

步骤2以具有第i维中值的数据作为根节点，将第i维值小于此中值的数据划分至左子树，第i维值大于此中值的数据划分至右子树。

步骤3 分别以左子树和右子树为新的数据集，重复进行步骤1和步骤2。不同的是，在选择分裂属性时，不再考虑第i维。

步骤4由此不断递归分叉，直至每个节点只剩下一个数据。

作为简单的例子，以k＝2的输入数据（x，y）来说明kd-tree的构建方法。设输入数据分别为：（7.467 9，8.462 2）、（4.659 9，6.721 4）、（4.451 0，5.251 5）、（0.1527 4，4.186 5）以及（9.318 1，2.026 5）。其中数据在x维和y维的方差为3.479 6和2.448 1，因此选x作为第一分裂属性。数据在x维上的中位数为4.659 9，因此将数值（4.659 9，6.721 4）作为根结点。然后，依据数据在x维上的大小，把小于4.659 9的数据划分至左边子树；把大于4.659 9的数据划分至右边子树。在左子树中，有2个数据（4.451 0，5.251 5）和（0.1527 4，4.186 5），此时只能选取y为分裂属性，任取一数，如5.251 5，作为新的子节点，再分裂为左右子树，并以些类推。最后得到的树型结构如图1（a）所示。

图1 kd-tree的树型索引结构及其对空间的划分

从数据的空间结构来看，kd-tree的构建过程实质上就是利用数据的空间分布，用不同的超平面把数据空间分割成形状不一的超长方体结构，而每一个超平面上有且仅有一个数据位于其中，因此每一个超平面对应着索引树中的一个节点。

KNN是k nearest neighbor的缩写，意指在一组给定的数据中查询一个新数据的k个最近邻数据。当数据的远近被定义为欧氏距离时，KNN就意味着寻找与新数据欧氏距离最近的前k个数据点。为了挑选出k个最近邻数据，往往需要计算每一个数据到被查询数据的距离。当数据量很大时，其计算与存储的代价很高。另一种替换的方法是，以被查询数据为中心，以一定的参考距离为半径作一圆周，然后判断圆周内的数据个数。如果小于k个，则增加半径；如果大于k个，则减小半径，直到所作圆周中刚好有k个数据。这种方法不需要计算每一个数据到被查询数据的距离，较适合海量数据下的k最近邻查询，但初始半径不好确定；同时在数据密度较大时，半径的增／减幅度不好控制，常常需要多次增减才能找到合适的值，这也增加了计算代价。

将kd-tree与KNN相结合是一种很好的思路，kd-tree可以快速定位被查询数据的空间位置，从而避免了在KNN中对大量无关数据的计算，极大地提高了查询效率。

以图1所示的kd-tree为例来说明KNN的实现方法，设被查询数据为（3.203 3，3.502 2）。容易看出，从根节点开始，数据（3.20 33，3.502 2）的查询路径为（4.659 9，6.721 4）→（4.451 0，5.251 5）→（0.152 74，4.186 5）；然后计算出节点（0.152 74，4.186 5）与（3.203 3，3.502 2）的距离，设为d，并以（3.203 3，3.502 2）为圆心，d为半径做圆Cd，如图2所示；接下来判断圆Cd是否与其他数据点所在的直线相交；首先判断是否与（0.152 74，4.186 5）的根节点（4.451 0，5.251 5）所在直线相交，如果相交，则计算出（3.203 3，3.502 2）与（4.451 0，5.251 5）的距离d′，若d′＜d，则更新d为d′并用新的距离为半径画圆Cd′；采用新圆，再判断是否与根节点（4.659 9，6.721 4）对应直线相交；如果与根节点直线相交，还需要进一步判断根节点右子树中各直线相交的情况。每次判断出相交后，要比较距离与原有半径的大小，在需要时候更新圆的半径。在本例中，因为｜3.502 2－5.251 5｜＜d，所以Cd与（0.152 74，4.186 5）的父节点（4.451 0，5.251 5）所在直线相交；由于（3.203 3，3.502 2）点到（4.451 0，5.251 5）的距离d′小于d，则更新圆为Cd′（图中虚线）。再回溯至节点（4.659 9，6.721 4），因｜3.203 3－4.659 9｜＜d′，Cd′与根节点（4.659 9，6.721 4）对应的直线也相交，但不需更新圆Cd′；进一步可判断出Cd′与右子树中的节点（9.318 1，2.026 5）相交而与节点（7.467 9，8.462 2）不相交，且与（9.318 1，2.026 5）的距离大于d′，因此也无需更新。经过上述的回溯及更新过程，最终可以确定，与被查询点（3.203 3，3.502 2）最近的数据点就是（4.451 0，5.251 5）。

图2 基于kd-tree的最近邻数据查询

根据圆与各直线相交的情况，除了点（7.467 9，8.462 2），均需计算其他各数据到被查询点的距离。虽然采用回溯且不断更新的计算策略，一定程度上得到了较好的查询效率，但仍然避免不了对部分无关数据的计算。产生这种不足的原因是数据空间的不规则划分，且数据位于超平面之上，虽能快速定位被查询数据所在空间区域，但没有为其提供与其他数据相对的位置信息，因此查询得到的节点数据常常不是最合理的距离参考点；另外，KNN的方法是采用超球面来寻找最近邻数据，而球面与平面是二种性质不同的空间曲面，因此基于超平面的不规则空间划分无法为超球面提供足够有效的信息。

单纯地从数据空间的划分来看，采用VORONOI的空间结构是较为理想的，其特点是每个数据位于自身所在区域的中心，边界则由平分其相邻数据距离的超平面构成，因此落入某一区域的数据必然与位于此区域中心点的数据距离最近。虽然如此，但VORONOI空间结构不适合建立数据索引，无法快速定位被查询数据所处区域。若能在构建索引树的时候，把各数据置于区域内而不是位于边界的超平面上，且区域的划分较为规则，则一方面可快速定位被查询数据，同时规则的空间划分也可反映各区域的分布关系，这为下一步寻找最近邻数据提供了帮助。

2 规则网格下的kd-tree KNN算法

2.1 基本思想与查询超体

规则网格的基本思想来源于坐标系对空间的划分方式，实际上坐标系可看成是网格无限小的系统，当需要对数据进行查询时，只需找到其相应的网格（坐标大小）就行了。在工程实际中，网格的大小不可能做到无限小，但这种定位数据的思想却可以应用在数据的最近邻查找中。

对于一组给定的数据，在确定坐标中心后（通常取数据分布的中心点），可利用规则网格的方式将数据划分至不同的区域，数据分布稀疏的地方网格较大，数据较密集之处网格较小，直至每一个网格最多仅包含一个数据，如图3所示。当被查询数据落入某一网格时，则在较大概率上与该网格中的数据有较近邻的距离，同时该网格周围的8个区域中也可能存在最近邻数据。如果每次都同等地考查与这8个数据的距离，则查询效率不高。被查询数据与邻近网格中数据的距离不但与数据的分布形态有关，还与被查询数据在网格中的位置有关。因此可以根据数据之间的相对位置来尽可能排除那些距离明显较大的数据。实现这一思想的简单方法就是将以被查数据为中心的较小的局部数据空间单独分割出来，从而提高查询效率。

图3 数据的网格划分（三角形是已知数据，圆形为被查询数据）

假设被查数据落入某一网格，若网格中已有数据（设为xΩ），则可计算被查数据与xΩ的欧氏距离d，并以被查询数据为中心，2d为边做正方超体（称之为查询超体），并比较位于正方超体内的其他数据的距离，如图3中所示虚线方框；若网格中无数据，则被查数据所在父节点网格中必有数据，如图4所示；优先选择与被查数据位于同一网格的数据，并计算最近欧氏距离d，再做边长为2d的查询超体。

图4 被查数据落入空网格时的近邻查询

采用正方超体而不是超球体的优点是无需判断超方体与网格超平面是否相交，且容易判断邻近网格中的数据是否位于查询超体中。设n维被查数据为xs，则对查询超体之内的数据必有x∈［xs－d，xs＋d］。因此当d和查询超体确定后，可快速查询出最近邻数据；d的大小可保证查询体是一个合理的空间分割，且主要包含了与已知数据xΩ空间对称网格中可能存在的数据。

2.2 数据空间的方体化

要快速定位被查数据并确定出较合理的查询超体就有必要构建适用于规则网格情形下的检索树结构。虽然数据不再位于超平面上，而是在超方体中，但kd-tree的建立方法仍然适用，只是不再单纯地依赖于数据，而是需要考虑整体数据构成的空间；同时树的各个节点也不再是数据，而是各个不同的网格区域，根节点就是整个数据的空间域，叶子节点就是最多仅包括一个数据的空间网格，称此种树为Skd-tree。

理想的网格形状是超方体或近似的超方体，但由于数据在各个维度上分布的尺度不同，因此按kd-tree方法进行划分的网格将是长方超体。长方超体的一个主要不足是数据在空间某些维度的定位不够精细，容易导致查询超体过大，从而引入不必要的比较数据。方法1是引入加权欧氏距离，使各维度对总体距离的贡献占有不同的比例，实际上是将数据所在的空间沿各个维度进行缩放，使最终的空间呈正方超体。当数据在各维度上同等重要时，则不能使用加权欧氏距离。方法2是按数据空间在各维度的大小预先分块，使分块后的数据占据一个超方体。这种方法的缺点是当数据维度较高时且各维度尺度差异较大时，则分块较多，易导致Skd-tree结构复杂。方法3是以最大尺度的空间维度为准，在较小尺度的维度上添加空白空间，使其一致。该方法的不足是可能使空白网格较多，因此需要在近邻搜索时滤除。以2维数据为例，图5给出了这3种方法的示意图。

图5 原始数据空间的方体化

2.3 Skd-tree KNN算法

依据前述Skd-tree及基于查询超体的基本思想，可以总结出规则网格划分下的Skd-tree KNN算法（Skd-tree KNN）如下：

输入：n个k维数据｛xi｝，i＝1，2，…，n，xi＝［xi1，xi2，…，xik］；一个待查数据xs＝［xs1，xs2，…，xsk］。

输出：SKd-tree索引树及与xs距离最近的数据xl，l∈｛1，2，…，n｝。

步骤1数据空间的方体化。如采用增加空白空间的方法，则处理如下：先计算出各维度的尺度Dj＝｜maxxmj－minxgj｜，j＝1，2，…，k；并取D＝max｛Dj｝；则数据可认为是存在于k维空间中一个边长为D的超方体中，其中心为｛（maxxmj＋minxgj）／2｝。

步骤2将整个超方体看成根节点，按维度顺序，以超体中心坐标大小为分裂属性，把小于此值和大于此值的数据分开，同时也是将整个超方体在各个维度上进行平分；这样可得到k2个包含数据的网格空间，每个网格是一个节点。

步骤3 判断由步骤2得到的各节点中是否包含数据，若为空或仅有一个数据，则作为叶子节点；若含有1个以上数据，则重复步骤2，但划分条件为当前网格空间的中心坐标值。

步骤4 重复步骤3，并不断递归，直至得到全部叶子节点（划分的停止标准也可以是网格大小，若网格达到预定的大小时，则可停止分割，此时一个叶子节点可能包含多个数据。通常，当数据较为密集时，为了避免树的复杂性可采用此法）。

由步骤2～4可得到Skd-tree索引树；需要注意的是，空间虽然只是针对超方体，但索引树对超方体外的被查数据也有效，步骤1的超体化只是提供一个参考的划分框架。

步骤5为每一个叶子节点建立空间方位指数。将超方体中心看作原点，可得到每个节点所表示的空间网格中心处的坐标向量r；以划分时“小于”为负，“大于”为正，并将各维度按顺序进行的一次循环划分视为一次，则经过l次划分后的网格中心处坐标向量r各分量为，相应网格的边长L则为。

步骤6 依据Skd-tree树的索引，找到被查数据xs所处网格，记为Ωs。

步骤7 若Ωs中已有数据xΩ，则计算d＝，并以xs为中心，2d为边长做查询超体；若Ωs中无数据，其父节点网格必含有至少2个以上数据，则只需在其同一父节点下的各网格中找到与Ωs最近邻的非空网格中的数据，从而得到欧氏距离d，再做边长为2d的查询超体。

步骤8由条件xs－d≤xi≤xs＋d确定位于查询超体内的数据。由于d是Ωs或其父节点中与xs的最小距离，因此，当Ωs中无数据时，查询超体中的数据应当排除Ωs父节点中的所有其他数据。位于查询超体中的数据均来自于其相邻网格或父节点网格，由于各网格的位置是固定的，因此只需存储其相邻的非空网格的编号，即可快速获得位于超体内的数据，而付出的存储代价很少。

步骤9以循环更新法得到xs的最近邻数据xl。具体做法是：依次计算被查数据xs与查询超体内其他数据的距离d′，若d′＞d，则计算与下一个数据的距离；若d′＜d，则更新查询超体大小并判断原查询超体中未计算数据是否在新超体中，然后在新超体中继续循环更新，直至超体内仅有一个数据。

一般情况下，查询超体中的数据较少，因为每一个网格仅包含一个数据。如果被查数据xs落入数据密集区，则网格较小，从而d小，查询超体也小；而当落入稀疏区，d虽较大，但查询超体覆盖的网格也大，从而所含数据少。当查询超体中包含的数据较少时，也可不用更新算法，直接计算每一个数据，然后得到最小值即可。

3 算法实例分析

实验环境：所有实验在一台I7-4700／2.4GHz／16GB的电脑上进行；所用软件为Windows 8.0及Matlab 2018a。

实验的基本过程：

①随机生成N＋M个k维数据｛xi｝，i＝1，2，…，N＋M，xi＝［xi1，xi2，…，xik］，xij～U（0，αj），αj～N（εj，σ2），j＝1，2，…，k，其中U、N表示均匀分布和正态分布；εj及σj为可调参数，由它们决定随机数据在第i维上的分布范围。

②随机选择N个数据作为训练样本集，余下的M个数据作为测试集。

③依据训练集生成kd-tree及Skd-tree。

④将M个测试数据看成被查询数据，依次进行测试。

⑤分别记录下索引得到的初始欧氏距离d，为得到最近邻数据时，kd-tree中的回溯节点数据，查询超体中包含的数据个数，计算出相应的平均值作为对比；同时记录下由查询开始至得出最近邻数据所需时间。

⑥同时采用KNN计算最近邻结果作为参照。

由于数据量N与数据维度k是影响查询效率的2个重要因素，因此实验中重点比较kd-tree KNN、Skd-tree KNN 2种算法在不同数据规模和维度时的查询效率与效果。为了减少数据随机性对结果的影响，可选择较大的M值，本文中统一取M＝100。

图6表示了在低维和高维数据（k＝3和k＝20）条件下，由kd-tree和Skd-tree索引得到的初始距离d随数据量N的变化情况。可以看到，在样本数量较少时，二者效果难分高下，但在较大数据量时，Skd-tree的索引能得到更小、更接近KNN给出的实际最近邻距离。这主要归功于Skd-tree以数据分布为依据对空间的规则划分，从而获得更小的网格单元。

图6 经kd-tree与Skd-tree索引得到的初始距离d随样本数据量的变化及与KNN最近邻结果曲线

回溯节点数量与查询超体内的数据点是影响查询效率的另一个重要指标，对计算速度起着主要的作用。随着数据分布密度的增加，kd-ree的回溯节点数量也呈现出快速增长的趋势；而Skd-tree由于能较精确地定位被查数据，其查询超体中包含的数据点随数据密度的增加则较为缓慢。图7给出了低维度数据时回溯节点数量与超体内数据随训练样规模增加的变化情况，这一结论也适用于高维度数据的情形。图8比较了数据维度的变化对回溯节点数与超体内数据点，说明维度的总体影响较小，特别是对超体内数据点的多少没有体现出明显的作用。

图7 kd-tree回溯节点数与查询超体内数据点量随训练集大小变化曲线（k＝3）

图8 kd-tree回溯节点数与查询超体内数据点量随数据维度的变化曲线（N＝100）

由于被查数据经由Skd-tree索引后可获得更小的查询超体，包含较少的数据点，因此Skd-tree KNN体现出更好的查询效率。图9给出了kd-tree与Skd-tree方法查询最近邻数据所需时间随样本量的变化，表明Skd-tree有更优良的查询效果；Skd-tree索引树具有更深的结构，因此在少量样本的时候并没有优势，其查询时间比kd-tree长，但随着数据维度及量的增加，Skd-tree的索引优势则变得明显。虽然Skd-tree随着数据量及数据维度的增加会变得比相应的kd-tree复杂，使得索引速度降低，但由于后继计算量小，因此总体查询效率更高。

图9 kd-tree与Skd-tree方法查询最近邻数据所需时间随样本量的变化曲线（k＝3）

4 结论

针对在已有数据集中快速定位被查数据并获取其最近邻数据点的计算策略，在kd-tree的基础上，研究了一种基于规则数据空间网格划分的Skd-tree树形结构的最近邻算法。该树形结构把数据置于空间网格内部，能更好地利用数据的空间分布特性，可以在更小范围内对被查询数据定位，有效避免对部分无关数据的计算或回溯，提高查询效率与效果；为了适应网格空间的规则性，算法中采用了正方形超体而非超球体来查询局域空间中的最优结果，有效避免了空间异构带来的不足。虽然Skd-tree较之kd-tree略显复杂，但这一代价是值得的。数字实验的结果证明：Skd-tree无论在索引定位结果，还是后继所需计算的数据点数量及最终查询时间上都优于kd-tree的结果，且尤其适用于数据样本较大或高维度数据的最近邻查询。