一种基于检索树的改进计数最近邻分类新算法  

New Improved k-Nearest Neighbours by Counting Based on Index Tree

作　　者：廖志芳[1] 樊晓平[1] 刘皛[1] 

机构地区：[1]中南大学信息科学与工程学院,湖南长沙410075

出　　处：《小型微型计算机系统》2008年第2期283-287,共5页Journal of Chinese Computer Systems

基　　金：国家“八六三”计划项目(2005AA1Z2140)资助

摘　　要：计数最近邻分类算法是一种以数据格论为理论依据的新分类算法,其优越性在于能不经转换地处理各种混合数据.本文在阐述和分析该算法的基本原理后,发现该算法的计算效率及存储效率有待改进提高,因此我们提出了一种基于检索树的改进计数最近邻分类新算法,其主要思想是通过构建检索树以减少重复数据的计算量,并以此提高算法的计算效率和存储效率.通过利用国家863项目数据集和多个UCI公共数据集的综合测试,结果表明该新算法在具有大量重复数据的应用环境中效果明显,具有较高的计算和存储空间效率.k-nearest neighbours by counting （kNN by counting） is a novel classification algorithm based on Lattice machine, which can be applied to both ordinal and nominal data without transition. After describing and analyzing the principle of this kind of algorithm, the computation complexity and storage efficiency are found that should be improved, so this paper presents a new improved classification algorithm of k-nearest neighbours by counting based on index tree. The main idea behind the new algorithm is to decrease computation amount with repetition data by index tree so as to enhance the efficiency of kNN by counting. Some comprehensive tests are carried out with the dataset from the national 863 project and several datasets from UCI, and the test results demonstrate that the new algorithm could achieve higher efficiency both on computation and storage amount ,especially in the application with large scale repetition data.

关 键 词：格论 基于计数的kNN 分类算法 检索树 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]