[发明专利]一种基于参考点的快速精确近邻分类算法

摘要

本发明涉及一种基于参考点的快速精确近邻分类算法，属于计算机技术领域。该算法用参考点的距离来替代样本点之间的距离的进行直接计算，找到了比最近邻样本更加适合分类的样本点，以提高算法的分类精度。本RPkN算法通过选择参考点和子序列长度来选择用于分类的近邻样本，而现有的k近邻算法总是查找最近邻样本来用于分类。RPkN通过计算样本点的RPF值避免了样本间距离的直接计算，将算法的时间复杂度降低到了(O(nlogn))，这种时间复杂度的降低不依赖任何维度的树结构，所以相比现有的精确的依赖树索引的k最近邻分类算法，其能够更好的适应高维数据集。

主权项

一种基于参考点的快速精确近邻分类算法，其特征在于：该算法用参考点的距离来替代样本点之间的距离的进行直接计算，找到了比最近邻样本更加适合分类的样本点，以提高算法的分类精度，算法给定数据集D∈Rd，k是近邻算法中要搜索的近邻数，A是D中的一个样本点，ε为关系近邻搜索算法时间复杂度的常量；表示候选参考点设置为单位向量及其反向量，定义变量ExistingNeighbors＝NULL，j＝1，具体步骤包括：1)设置子序列的长度为2j*k*ε，并选择第i个候选参考点为当前的参考点；2)计算所有样本点的参考点因子值，即RPF值，并对所有样本点按照其RPF值进行排序并生成一个有序序列；3)在由ExistingNeighbors和以A为中心且长度为2j*k*ε的子序列构成的集合中，找到与到A最近的k的样本点；4)计算所有样本点的近邻样本及整个数据集的分类精度；5)i＝i+1，将第i个候选参考点设置为下一个参考点；并计算加入新参考点后的分类精度；6)如果所有候选参考点被加入且精度增加，用所有样本的k近邻样本替代ExistingNeighbors，转向步骤7)；如果还有候选参考点未被加入且精度增加，用所有样本的k近邻样本替代ExistingNeighbors，转向步骤5)；7)如果子序列长度增加后算法的分类精度降低，算法终止；否则，转向步骤8)；8)通过j＝j+1将子序列的长度增加1并转向步骤1)。