一种高维向量空间K近邻快速搜索方法
发布时间：2021-11-17 07:01
针对基于Ball-tree结构的KNN算法初始K个近邻点位置固定,导致剪枝半径过大,剪枝效果差,查询效率低的问题,本文提出一种基于"双树"结构的高维向量空间K近邻快速搜索方法.在训练阶段,将原始数据集按照8∶2比例划分为训练集和测试集,利用随机选择方法共生成10组训练和测试集合,通过统计分析,得到最优"双树"构造参数.利用最优参数从原始数据点集合中过滤出极少量数据点构成剪枝树,过滤剩余数据点构成被删树,剪枝树需要最大限度地保留原始数据点集合在高维空间的分布形态.在查询阶段,由于剪枝树内数据点个数很少,可以快速定位最近邻点,再利用这个近邻点作为被删树的初始近邻点,在被删树内搜索K近邻.实验结果表明,由于初始近邻点位置不再固定,而是位于待查点附近,有效缩小了剪枝半径,改善了剪枝效果,提升了K近邻查询效率.
【文章来源】：小型微型计算机系统. 2020,41(11)北大核心CSCD
【文章页数】：8 页
【部分图文】：
Node节点分裂过程及最短距离计算方法
根据KNN搜索算法1可知，无论待查点在多维空间什么位置，KNN＿result数组的初始值均为Ball-tree结构最左侧K个叶节点．这导致当待查点距离初始K个叶节点较近时，剪枝效果好，查询效率高，反之剪枝效果差，查询效率低，下面通过实例分析．图2显示的是二维空间内44个样本点构成的一棵Balltree结构，待查点target在二维空间内的坐标位置为(80,400)，表1显示的是target在二维空间内5近邻搜索过程．初始条件下Ball-tree最左侧5个叶节点(即20,8,39,41,44)被填入KNN＿result数组，数组元素按照distance值降序排列．之后算法从左至右，逐个计算叶节点与target的空间距离，并与KNN＿result数组首个元素的distance值比较大小关系，动态更新KNN＿result数组元素值，使其始终保存当前的5个最近邻．由于target距离初始5近邻空间距离较近，剪枝效果好，查询过程中Ball-tree整个右分枝子树被剪枝，其包含33个样本点．整个查询过程只比较了11个样本点与target的距离值即完成5近邻搜索，查询效率较高．
整数变量max＿points用于限定剪枝力度，增大该值将有更多的数据点被剪枝删除，这一数值的确定需要经过精确计算，以达到最佳效果，算法4用于确定这个变量的具体值．图3显示了对二维空间内3960个样本点进行剪枝处理，调整剪枝数max＿points的剪枝效果比较，可见剪枝剩余样本点密度不同，但均最大限度保留原始样本点的基本形态，且离群点得到最大限度地保留．剪枝树和被删树构造算法2:reduce＿and＿pruned＿tree(node＿density,data,max＿points):
【参考文献】：
期刊论文
[1]基于改进K-modes聚类的KNN分类算法[J]. 王志华,刘绍廷,罗齐. 计算机工程与设计. 2019(08)
[2]基于CUDA的KNN算法并行化研究[J]. 刘端阳,郑江帆,刘志. 小型微型计算机系统. 2019(06)
[3]基于改进K最近邻算法的中文文本分类[J]. 黄超,陈军华. 上海师范大学学报(自然科学版). 2019(01)
[4]基于拉普拉斯机制的差分隐私保护k-means++聚类算法研究[J]. 傅彦铭,李振铎. 信息网络安全. 2019(02)
[5]基于BP神经网络决策的KNN改进算法[J]. 路敦利,宁芊,臧军. 计算机应用. 2017(S2)
[6]粗糙集近似集的KNN文本分类算法研究[J]. 杨帅华,张清华. 小型微型计算机系统. 2017(10)
[7]基于超球区域划分的改进KNN算法[J]. 郝卫杰,王艳飞,胡敬伟,张公敬. 青岛大学学报(自然科学版). 2017(01)
[8]基于训练集裁剪的加权K近邻文本分类算法[J]. 孙新,欧阳童,严西敏,尚煜茗,郭文浩. 情报工程. 2016(06)
[9]基于聚类改进的KNN文本分类算法[J]. 周庆平,谭长庚,王宏君,湛淼湘. 计算机应用研究. 2016(11)
[10]基于密度的kNN文本分类器训练样本裁剪方法[J]. 李荣陆,胡运发. 计算机研究与发展. 2004(04)
本文编号：3500432
【文章来源】：小型微型计算机系统. 2020,41(11)北大核心CSCD
【文章页数】：8 页
【部分图文】：
Node节点分裂过程及最短距离计算方法
根据KNN搜索算法1可知，无论待查点在多维空间什么位置，KNN＿result数组的初始值均为Ball-tree结构最左侧K个叶节点．这导致当待查点距离初始K个叶节点较近时，剪枝效果好，查询效率高，反之剪枝效果差，查询效率低，下面通过实例分析．图2显示的是二维空间内44个样本点构成的一棵Balltree结构，待查点target在二维空间内的坐标位置为(80,400)，表1显示的是target在二维空间内5近邻搜索过程．初始条件下Ball-tree最左侧5个叶节点(即20,8,39,41,44)被填入KNN＿result数组，数组元素按照distance值降序排列．之后算法从左至右，逐个计算叶节点与target的空间距离，并与KNN＿result数组首个元素的distance值比较大小关系，动态更新KNN＿result数组元素值，使其始终保存当前的5个最近邻．由于target距离初始5近邻空间距离较近，剪枝效果好，查询过程中Ball-tree整个右分枝子树被剪枝，其包含33个样本点．整个查询过程只比较了11个样本点与target的距离值即完成5近邻搜索，查询效率较高．
整数变量max＿points用于限定剪枝力度，增大该值将有更多的数据点被剪枝删除，这一数值的确定需要经过精确计算，以达到最佳效果，算法4用于确定这个变量的具体值．图3显示了对二维空间内3960个样本点进行剪枝处理，调整剪枝数max＿points的剪枝效果比较，可见剪枝剩余样本点密度不同，但均最大限度保留原始样本点的基本形态，且离群点得到最大限度地保留．剪枝树和被删树构造算法2:reduce＿and＿pruned＿tree(node＿density,data,max＿points):
【参考文献】：
期刊论文
[1]基于改进K-modes聚类的KNN分类算法[J]. 王志华,刘绍廷,罗齐. 计算机工程与设计. 2019(08)
[2]基于CUDA的KNN算法并行化研究[J]. 刘端阳,郑江帆,刘志. 小型微型计算机系统. 2019(06)
[3]基于改进K最近邻算法的中文文本分类[J]. 黄超,陈军华. 上海师范大学学报(自然科学版). 2019(01)
[4]基于拉普拉斯机制的差分隐私保护k-means++聚类算法研究[J]. 傅彦铭,李振铎. 信息网络安全. 2019(02)
[5]基于BP神经网络决策的KNN改进算法[J]. 路敦利,宁芊,臧军. 计算机应用. 2017(S2)
[6]粗糙集近似集的KNN文本分类算法研究[J]. 杨帅华,张清华. 小型微型计算机系统. 2017(10)
[7]基于超球区域划分的改进KNN算法[J]. 郝卫杰,王艳飞,胡敬伟,张公敬. 青岛大学学报(自然科学版). 2017(01)
[8]基于训练集裁剪的加权K近邻文本分类算法[J]. 孙新,欧阳童,严西敏,尚煜茗,郭文浩. 情报工程. 2016(06)
[9]基于聚类改进的KNN文本分类算法[J]. 周庆平,谭长庚,王宏君,湛淼湘. 计算机应用研究. 2016(11)
[10]基于密度的kNN文本分类器训练样本裁剪方法[J]. 李荣陆,胡运发. 计算机研究与发展. 2004(04)
本文编号：3500432
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3500432.html
