作　　者： ; ; ; ;

机构地区： 同济大学电子与信息工程学院计算机科学与技术系

出　　处： 《模式识别与人工智能》 2012年第4期617-623,共7页

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

关 键 词： 最近邻 变精度粗糙集 上下近似

领　　域： [自动化与计算机技术] [自动化与计算机技术] [自动化与计算机技术] [自动化与计算机技术]