基于区域划分的改进KNN分类算法

摘要

数据分类是数据挖掘的重要组成部分，主要用来提取用于判定数据对象类型的模型。数据分类的目标是构造一个分类器，来预测数据对象的类别。KNN是一种比较常用的分类算法，准确率高，原理简单，实现起来方便，并且能够对超维数据空间建模。但是直接在训练集上使用KNN算法，计算量较大，并且随着数据对象数量和维数的增加，计算量呈指数增长。
　　为了提高KNN算法的效率，针对不同的应用场景，本文提出了基于超球区域划分和基于超长方体区域划分两种不同的KNN改进算法。在训练阶段，根据训练样本的分布情况，使用某种区域划分方法将训练样本空间划分成若干个区域，并在划分区域的基础上构造基于区域划分的初级分类器；在测试分类阶段，利用初级分类器确定待测样本的新训练集，然后在新训练集上使用KNN算法确定待测样本的类别。由于新训练集中样本数量小于原始训练集中的样本数量，因此测试分类阶段KNN算法的计算量会大大下降。在基于超球区域划分的改进算法中，使用模拟退火算法来控制初级分类器中超球的数量，从而降低算法的计算量；在基于超长方体区域划分的改进算法中，通过降维，来控制超长方体的数量，从而降低算法的计算量和存储开销。
　　在七个数据集上进行实验，使用本文所提出的算法对待测样本进行分类，并与经典KNN分类算法在准确率与分类时间方面进行了比较。实验证明，本文所提的改进KNN分类算法是高效的。