基于变精度粗糙集的KNN分类改进算法

传统KNN算法具有简单、稳定和高效的特点，在实际领域得到广泛应用。但算法的时间复杂度与样本规模成正比，大规模或高维数据会降低KNN分类效率。文中通过引入变精度粗糙集模型，提出一种改进的KNN分类算法。算法运用变精度粗糙集上下近似概念，将各类训练样本划分为核心和边界区域，分类过程计算新样本与各类的近似程度，获取新样本的归属区域，减小分类代价，增强算法的鲁棒性。实验表明，与传统KNN算法相比，文中算法保持较高的分类精度并有效提高分类效率，具有一定的理论与实际价值。

An Improved KNN Algorithm Based on Variable Precision Rough Sets

K Nearest Neighbor(KNN) is a simple,stable and effective supervised classification algorithm in machine learning and is used in many practical applications.Its complexity increases with the number of instances,and thus it is not practicable for large-scale or high dimensional data.In this paper,an improved KNN algorithm based on variable parameter rough set model(RSKNN) is proposed.By introducing the concept of upper and lower approximations in variable precision rough set model,the instances of each class are classified into core and boundary areas,and the distribution of the training set is obtained.For a new instance,RSKNN firstly computes the area it belongs to.Then,according to the area information,the algorithm determines the category directly or searches k-nearest neighbors among the related areas instead of all areas.In this way,the computing cost is reduced and the robustness is enhanced.The experimental results for selected UCI datasets show that the proposed method is more effective than the traditional KNN with high classification accuracy.