[发明专利]一种快速精确的粒球近邻分类算法

摘要

本发明涉及一种快速精确的粒球近邻分类算法，属于计算机技术领域。该算法使用被查询点到少量粒球的距离来替代样本点之间的距离的直接计算，使得该算法的时间复杂度可以保持在近邻线性，即O(n)，远小于现有的精确k最近邻算法。粒球近邻分类算法不需要进行k值的选择，这是现有k近邻算法所没有的特点。粒球近邻分类算法能够保留产生分类边界，从而有效地处理现有k最近邻算法在不平衡数据集精度失效的问题，获得了比现有k最近邻算法更好的精度。另外，相比现有基于树的精确最近邻算法，GBkNN算法不依赖任何树索引结构，所以能够更高效地处理高维数据，并且仍然保留了现有最近邻查询算法的优势在线,多分类，不依赖训练等。

主权项

本发明涉及一种快速精确近邻分类算法，其特征在于：该算法使用被查询点到少量的粒球的距离来替代样本点之间的距离的直接计算，使得该算法的算法效率远高于现有的精确k最近算法，并且还能够获得更好的算法分类精度，算法给定数据集D∈Rd，基于实验经验，如果算法在三次迭代后也没有得到一个更好的精度，则算法收敛。这也是本算法的收敛条件。算法具体步骤为：1)选取两类样本点作为两个粒球；2)计算所有粒球的标签；3)计算每个样本点到各粒球的距离；4)每个样本的标签等于其距离最近的粒球的标签；5)如果训练精度达到截至条件则算法终止；否则转向步骤6；6)生成更多的粒球数，并转向步骤2。