一种基于信息增益的K-NN改进算法  

Enhancement of K-Nearest Neighbour algorithm using information gain

作　　者：魏孝章[1] 豆增发[2] 

机构地区：[1]陕西教育学院数理工程系,西安710061 [2]西安电子科技大学计算机学院,西安710071

出　　处：《计算机工程与应用》2007年第19期188-191,共4页Computer Engineering and Applications

基　　金：陕西教育学院科研基金项目(No.06kj007)

摘　　要：针对传统K-NN算法易受单个属性干扰和时间效率较低的问题,提出了利用信息增益和可拓关联度对其进行改进。通过计算属性的信息增益来确定属性的权重系数,根据权重系数将属性划分为关键属性、次要属性和无关属性,在计算欧氏距离时引入权重系数,使各个属性的作用受其重要性的约束,有效地提高了K-NN算法的抗干扰能力和精确性。将属性空间划分为若干个子空间,利用可拓关联度将待测样本映射到某个子空间中,由这个子空间组成搜索空间,减少计算量,提高时间效率;测试结果表明,改进后的算法可行有效。Because the conventional K-NN algorithm has the disadvantages that the result is easily disturbed by single attribute of record and the time efficiency is very low,a novel K-NN algorithm is proposed which is an enhanced K-NN algorithm using information gain and extension relativity.Get the role coefficient of attribute,by which the attributes can be classified into primary attribute,secondary attribute and redundant attribute ,through computing the information gain of attribute.The role coefficient is introduced to the Euler＇s distance equation so that the effect of every attribute is controled by weightiness of it,by that,the antijamming ability and accuracy of the K-NN algorithm are improved highly.Partition the attribute space into several sub-paces, and map the record,which will be recognized,to a sub-space which a searching space is comprised of.So,the computing time is decreased and the time efficiency is improved greatly.The test results show the novel K-NN algorithm is feasible and effective.

关 键 词：K—NN算法 信息增益 信息熵 可拓关联度 

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