2014, Vol. 31
近年来，数据挖掘在互联网中占据了越来越重要的地位，在各种应用领域中得到足够的重视.数据挖掘出来的有效成果往往能影响一个互联网产品的设计方向和产品的成效.其中，KNN算法能很好地对大规模空间数据进行分类识别，从而影响数据挖掘的成效.
近年来学者们提出许多针对KNN的改进算法，文献[1]提出降低KNN计算量的基于密度KNN训练样本裁剪方法.文献[2]提出提高分类效率的基于特征词缩减的KNN自动分类改进算法.文献[3]提出提高KNN的分类效率的基于基准样本距离的快速构建KNN算法.这些算法主要是通过改进KNN算法，达到提高分类效率的目的.这些方法并没有考虑到从优化空间数据的索引创建方法这个方面进行优化KNN分类查询的效率.目前空间数据的索引主要有Kd-Tree和R-Tree两种.Kd-Tree是一种轴对齐的BSP树，其具有场景自适应划分、低存储消耗和快速遍历等优势[4].Kd-Tree构造的关键步骤是分割平面的确定[5-9].本文通过提出改进Kd-Tree构建的算法——RB算法，对传统的Kd-Tree的分割平面优化成圆形平面，减少平面之间的相交数目，降低回溯节点的数据比较次数，提高KNN算法的查询效率.
1 问题描述和背景知识 1.1 相关定义定义1 欧氏距离[10]主要用于计算多维空间数据点之间的距离，以下是具体的公式.其中，d表示数据点间的距离，K表示维度，两个数据点分别表示为(a1, a2, …, aK)和(y1, y2, …, yK)：
| $ d = \sqrt {\sum\limits_{i = 1}^K {({a_i} - {y_i})({a_i} - {y_i})} } . $ |
定义2 KNN算法可以简单概括为数据点A在训练数据集P中寻找k个最近邻的分类(升序排列)：KNN(A, P, k)={p1, p2, p3, …，pk}, j∉{1, 2, 3, …，k}d(A, pj)≥d(A, pk)≥...≥d(A, p3)≥d(A, p2)≥d(A, p1).
1.2 k近邻查询算法KNN算法的英文全称是K-Nearest Neighbor，KNN算法的主要用途是对大规模的未分类数据进行分类[11].例如，设S为已分类数据的训练集空间，D为未进行分类的大规模数据空间，从D空间中查找出S空间中每个数据样本的k条最近邻数据集，根据S空间的分类属性来决定D空间的分类方法.
例如，如图 1的数据，S空间分为四边形、五边形和六边形3种分类数据，三角形属于D空间的一个未分类数据.当k值等于4时，三角形有2个六边形邻居、1个四边形邻居和1个五边形邻居，根据统计学的原理，三角形归属到六边形分类中.当k值等于9时，三角形有3个六边形邻居、4个四边形邻居和2个五边形邻居，根据统计学的原理，三角形归属到四边形分类中.
|
图 1 KNN算法的聚类例图 Figure 1 KNN clustering algorithm of FIG |
KNN算法中的空间数据点距离计算方法主要有两种：欧氏距离和夹角余弦.
1.3 Kd-Tree索引快速构建算法Kd-Tree主要对K维数据空间进行层次划分[12]，为K维数据构建索引树，以下是构建Kd-Tree索引的算法.
算法1 Kd-Tree索引快速构建算法
输入：K维数据
输出：构建成功的Kd-Tree索引
步骤：
(1) 确定split域：计算K维数据所有维坐标的方差，选择方差最大的那一维作为spilt域.方差是衡量数据点分散程度的标准之一，方差越大数据分辨率越高.
(2) 确定根节点：对K维数据中split域上的坐标值进行升序排列，取中间的数据点作为Kd-Tree的根节点.
(3) 把根节点左边的数据分配到左子树，右边的数据分配到右子树，循环选择K维作为每层子树划分的split域(例如三维数据，根节点的split域是x，则后续每层子树划分的split域顺序是：y, z, x, y, z, …)，然后分别为左右子树重复步骤(2)和(3)，直到每个已分割的空间只剩下一个数据点.
例如把9个二维数据(7, 2)(4, 12)(3, 4)(13, 1)(5, 6)(11, 13)(10, 8)(8, 10)(9, 5)进行Kd-Tree划分，如图 2所示.
|
图 2 二维数据划分Kd-Tree层次空间 Figure 2 Two-dimensional data division of Kd-Tree-level space |
计算方差结果分别为x：9.46，y：12.06，根节点的split域选择y轴，Kd-Tree的构建如图 3所示.
|
图 3 Kd-Tree构建图 Figure 3 Diagram of Kd-Tree construction |
基于Kd-Tree索引的KNN查询主要分成搜索和回溯两个步骤[13].
算法2 基于Kd-Tree索引的KNN查询算法(当k=1)
输入：需要查询最近邻的K维数据点A
输出：测试数据点的最近邻数据点
步骤：
(1) 根据算法1构建成功的Kd-Tree进行搜索查询，从根节点开始，直到得到叶子节点Y.
(2) 使用欧氏距离计算方法算出数据点A和数据点Y的距离
(3) 以数据点A为球心(当K=2时，数据点A为圆心)，距离d为半径圈定范围P，上溯到叶子节点Y的父节点.
① 如果范围P与父节点的分割线相交，则判断父节点的另一个子树的所有数据点与数据点A的距离d，更新最小距离d和范围P.
② 如果范围P与父节点的分割线不相交，回溯到上一级的父节点.
例如图 2中的二维数据Kd-Tree，假设需要查询数据点(7.5, 7)的最近邻数据点，查找过程如图 4所示.
|
图 4 二维数据点根据Kd-Tree索引查找最近邻值 Figure 4 Dimensional data points to find the nearest neighbor value based on Kd-Tree index |
Kd-Tree是Friedman等于1977年提出的一种高维二叉树，在其上可实现对给定目标点的快速最近邻查找[14].Kd-Tree的主要效率瓶颈是需要回溯所有的非叶子节点，这样会耗费大量的时间，导致算法效率的下降[15-16].目前改进Kd-Tree效率的算法主要有BBF算法和球树的算法.BBF算法主要针对减少Kd-Tree的回溯节点数目，球树算法主要针对减少Kd-Tree中P范围与分割平面线的相交数目.
本文针对这两个算法对Kd-Tree进行进一步的改进，提出了RB算法，主要综合BBF算法和球树算法，从回溯节点和分割线相交数目两方面对Kd-Tree进行优化，提高KNN搜索算法的索引效率，以下是构建Kd-Tree索引的RB算法.
2 改进Kd-Tree构建的RB算法输入：测试数据点A和K维数据
输出：数据点A的最近邻数据点Y
步骤：
(1) 为K维数据构建球形层次空间分割的Kd-Tree.
① 当K>2时，使用欧氏距离计算出所有K维数据中距离d最大的K+1个不同平面的数据点，构建一个球空间P，包含所有K维数据点，空间P为根节点；在空间P内继续构建两个球空间(左右子树)，两个空间加起来包含所有数据点，递归建立空间，直到所有的数据点都可以位于某个球空间.
② 当K=2时，使用欧氏距离计算出所有K维数据中距离d最大的3个数据点(不在同一条直线上)，构建一个圆P，包含所有K维数据点，空间P为根节点；在空间P内继续构建两个圆空间(左右子树)，两个空间加起来包含所有数据点，递归建立空间，直到所有的数据点都可以位于某个圆空间.
(2) 搜索步骤1构建的Kd-Tree.
① 先计算数据点A是否在根节点空间内，然后判断A在哪个子树里面，使用堆栈存储该子树的兄弟节点空间
② 逐层搜索(每层都需要使用堆栈存储该子树的兄弟节点空间)直到找到数据点A处在其中一个叶子节点空间内，计算空间内和A距离最近的数据点，最小距离记为min，两个点建立一个距离判断标准空间Q.
③ 遍历堆栈，判断堆栈的空间S是否和标准空间Q相交，如果相交，进一步判断空间S里面的数据点与A的距离，如果计算出来的距离小于min，则更新min和标准空间Q以保持最小值.
|
图 5 RB算法划分空间图 Figure 5 RB algorithm is divided map |
假设需要查询数据点(7.5, 7)的最近邻数据点, 测试数据点遍历如图 6所示.
|
图 6 测试数据点遍历图 Figure 6 Traversal of test data points |
遍历顺序是：(1)-(2)-(4)-(9)-(5)-(3)；
堆栈进栈顺序是：(3)-(5)-(8)-(7)；
堆栈出栈顺序是：(8)-(5)-(3)-(7).
3 实验结果与分析 3.1 实验准备实验在windows7 32位操作系统上，采用java算法程序进行，实验数据来源于加州大学的机器学习和人工智能学习研究中心，数据集可以从http://archive.ics.uci.edu/ml/datasets/Abalone下载.
3.2 实验设计(1) 编写传统的Kd-Tree构建算法，使用测试数据点遍历数据量不同的训练集Kd-Tree，记录遍历结点的数目.
(2) 编写RB算法，使用测试数据点遍历数据量不同的训练集Kd-Tree，记录遍历结点的数目.
3.3 实验分析图 7显示所有的测试训练集近似于正态分布，保证实验数据的随机性和实验结果的准确性.
|
图 7 测试样本训练集分布图 Figure 7 Test sample training set distribution |
图 8显示分别使用传统的Kd-Tree算法和使用改进的RB算法对图 6的所有训练集进行对测试数据点查找k近邻数据点所要遍历的结点数目，通过结点数目的比较，可以得出算法的优化程度.
|
图 8 Kd-Tree算法和RB算法在不同训练集中查找k近邻数据点索遍历的结点数目比较图 Figure 8 Comparison chart of the number of nodes in Kd-Tree algorithm and RB algorithm at different training rope traverse k nearest neighbor data points |
通过图 8可知，在训练集数据比较少的时候，Kd-Tree算法查找k近邻有可能比RB算法更优，但随着训练集数据的增多，RB算法的优势逐渐明显.
4 结束语本文通过改进构建数据索引的Kd-Tree算法，从索引构建方面优化k近邻算法的效率.实验证明，在大规模的具有随机性的不同数据训练集样本中，RB算法在减少分割空间的交集和减少对父节点回溯遍历两方面改进后的效率明显比传统的Kd-Tree算法要高.
| [1] |
李荣陆, 胡运发. 基于密度的KNN文本分类器训练样本裁剪方法[J].
计算机研究与发展, 2004, 41(4): 539-545.
Li R L, Hu Y F. Density-based KNN text classifier training samples cropping methods[J]. Journal of Cornputer Research and Development, 2004, 41(4): 539-545. |
| [2] |
胡燕, 吴虎子, 钟珞. 基于改进的KNN算法的中文网页自动分类方法研究[J].
武汉大学学报:工学版, 2007, 40(4): 141-144.
Hu Y, Wu H Z, Zhong L. Research Of Chinese web classification method based on improved KNN algorithm[J]. Engineering Journal of Wuhon University, 2007, 40(4): 141-144. |
| [3] |
王煜, 白石, 王正欧. 用于Web文本分类的快速KNN算法[J].
情报学报, 2007, 26(1): 60-64.
Wang Y, Bai S, Wang Z B. A fast KNN algonthm appfied to web text categorization[J]. Journal of the China Society for Scientific and Technical Information, 2007, 26(1): 60-64. |
| [4] |
过洁, 徐晓旸, 潘金贵. 虚拟场景的一种快速优化Kd-Tree构造方法[J].
电子学报, 2011, 39(8): 1813-1814.
Guo J, Xu X Y, Pan J G. Build Kd-Tree for virtual scenes in a fast and optimal way[J]. Acta Electronica Sinica, 2011, 39(8): 1813-1814. |
| [5] |
杜振鹏, 李德华. 基于Kd-Tree搜索和SURF特征的图像匹配算法研究[J].
计算机与数字工程, 2012, 40(2): 96-97.
Du Z P, Li D H. Image matching algorithm research based on Kd-Tree search and URF features[J]. Computer and Digital Engineering, 2012, 40(2): 96-97. |
| [6] |
黄忠, 江巨浪, 张佑生, 等. 基于中剖面kd-树的光线跟踪加速算法[J].
计算机工程与应用, 2010, 46(28): 203-204.
Huang Z, Jiang J L, Zhang Y S, et al. Ray-tracing acceleration algorithm based on median-cut Kd-Tree[J]. Computer Engineering and Applications, 2010, 46(28): 203-204. |
| [7] |
包南森, 李正杰, 柴亚辉, 等. 邻居搜索问题在CUDA上基于KD-TRIE方法的优化与实现[J].
上海大学学报:自然科学版, 2012, 18(3): 306-309.
Bao N S, Li Z J, Chai Y H, et al. Optimization of Neighbor Searching Problem on CUDA Based on KD-TRIE and Its Application[J]. Journal of Shanghai University: Natural Science Edition, 2012, 18(3): 306-309. |
| [8] |
刘忠, 刘洋, 建晓. 基于Kd-Tree的KNN文本分类算法[J].
网络安全技术与应用, 2012(5): 38-39.
Liu Z, Liu Y, Jian X. KNN Algorithm for Text Classification Based on Kd-Tree[J]. Network Security Technology and Application, 2012(5): 38-39. |
| [9] |
李晓东, 陈俊健, 曾凡智. 基于KDG-tree的数据库多维索引技术[J].
计算机应用与软件, 2013, 30(6): 163-164.
Li X D, Chen J J, Zeng F Z. Multi-dimensional database index based on KDG-tree[J]. Computer Applications and Software, 2013, 30(6): 163-164. |
| [10] |
杨立, 左春, 王裕国. 基于语义距离的K-最近邻分类方法[J].
软件学报, 2005, 16(12): 2055-2062.
Yang L, Zuo C, Wang Y G. K-Nearest neighbor classification based on semantic distance[J]. Journal of Software, 2005, 16(12): 2055-2062. |
| [11] |
滕少华, 樊继慧, 陈潇, 等. 基于KNN多组合器协同挖掘局域气象数据[J].
广东工业大学学报, 2014, 31(1): 25-31.
Teng S H, Fan J H, Chen X, et al. The application of KNN-based multi-classifiers in mining local area meteorological data[J]. Journal of Guangdong University of Technology, 2014, 31(1): 25-31. |
| [12] |
向阳霞, 王洪艳, 周泽云. Kd-Tree的并行化创建方法分析[J].
电脑知识与技术, 2013(23): 5328-5329.
Xiang Y X, Wang H Y, Zhou Z Y. Analysis of Kd-Tree's parallelizing construction methods[J]. Computer Knowledge and Technology, 2013(23): 5328-5329. |
| [13] |
焦良葆, 陈瑞, 张健. 一个新的线索KD树并行算法[J].
工程图学学报, 2011(5): 47-50.
Jiao L B, Chen R, Zhang J. A novel algorithm of clued Kd-Tree on SIMD architecture[J]. Journal of Engineering Graphics, 2011(5): 47-50. |
| [14] |
陈作平, 叶正麟, 赵红星, 等. 结合K均值聚类和Kd-Tree搜索的快速分形编码方法[J].
计算机辅助设计与图形学学报, 2006, 18(7): 968-969.
Chen Z P, Ye Z L, Zhao H X, et al. Build Kd-Tree for virtual scenes in a fast and optimal way[J]. Journal of Computer-aided Design & Computer Graphics, 2006, 18(7): 968-969. |
| [15] |
刘义, 景宁, 陈荦, 等. MapReduce框架下基于R-树的k-近邻连接算法[J].
软件学报, 2013(8): 1837-1851.
Liu Y, Jing N, Chen L, et al. Algorithm for Processing k-Nearest join based on R-Tree in map reduce[J]. Journal of Software, 2013(8): 1837-1851. |
| [16] |
鲁庆, 余永权. 分析服务组件模型在数据挖掘中的研究与应用[J].
广东工业大学学报, 2005, 22(1): 53-56.
Lu Q, Yu Y Q. Research and application of analysis services component model in data mining[J]. Journal of Guangdong University of Technology, 2005, 22(1): 53-56. |