一种基于欧氏距离改进的kNN近邻查找方法

摘要

本发明公开了一种基于欧氏距离改进的kNN近邻查找方法。本发明利用欧式空间的特性，通过加减运算替换传统kNN方法中较为复杂的乘方运算，减少计算开销，在不降低查询准确率的条件下，实现对待分类样本的k近邻查找。本发明可有效减少部分样本点的计算量，降低kNN方法的时间复杂度；同时借助简化过程引入的临时变量，规避对全局集中式索引结构的依赖，将传统kNN方法由串行单线程处理模式，非常方便地扩展为多线程处理模式，提升处理器利用率并适应大数据处理的需求。

主权项

一种基于欧氏距离改进的kNN近邻查找方法，其特征在于：假定由n(n>0)个样本构成样本集合S＝{s₀,s₁,…,s_n‑1}，同时共有t(t>0)个线程TD₀、TD₁、…、TD_t‑1进行处理，在S中查找与待分类样本v₀最相似的k个近邻，则本方法具体可以分为3个主要步骤：步骤1，线程初始化处理；对任一线程TD_j(0≤j≤t‑1)，令其中为取下整符号，则TD_j首先在S_j中随机取k个样本，构成TD_j关于待分类样本v₀的初始k‑近邻集合再计算中各样本与v₀的欧氏距离，并选择其中距离最大值，不妨记为dmax_j，假定与它对应的样本为s_max；同时令并且令样本集合步骤2，单个线程求k‑近邻；对任一线程TD_j(0≤j≤t‑1)，从中逐个选取每一样本s；首先，计算s各个维度与v₀对应维度的距离，并将其与radius进行比较：只要其中有一个维度的距离大于radius，则直接丢弃s；否则，计算s与v₀的欧氏距离d；将计算所得d与dmax_j进行比较，如果d大于dmax_j，则直接丢弃s；否则令并再在所得新的中选择距离v₀最远的样本(仍用s_max表示)，v₀和样本s_max的距离仍用dmax_j表示，同时更新当中所有样本处理完后，则得到线程TD_j的k‑近邻集合计算并记录中各样本与v₀的欧氏距离；步骤3，多线程归并求k‑近邻；将t个线程的k‑近邻集合进行归并，得到该集合中共有t*k个样本，并对应t*k个欧氏距离；通过在t*k个欧氏距离中选取k个最小值，很容易得到全局样本集合S中关于待分类样本v₀的k个近邻。