王荣秀，王 波

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

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

树形结构由于表达能力强，无需参数、代价较小等优点，因此被广泛用于构建数据索引，如常见的数据索引kd-tree和R-tree。树形索引的构建实质上是通过对数据空间的分割，将数据集的特征属性，如密度、分布区域、相互位置、维度、均衡性等体现为空间结构与层次，从而把对数据的处理约化为空间关系的计算，因此空间的分割方式及对分割后形成的空间网格的处理方法是决定数据分类效率与分类效果的关键因素。……