一种改进的k近邻法在模式识别中的应用

《一种改进的k近邻法在模式识别中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第25卷　第4期沈阳师范大学学报(自然科学版)Vol125,No.42007年10月JournalofShenyangNormalUniversity(NaturalScience)Oct.2007文章编号:1673-5862(2007)04-0475-04一种改进的K近邻法在模式识别中的应用周而重,逄玉俊(沈阳化工学院计算机科学与技术学院,辽宁沈阳　110142)摘　　　要:针对传统K近邻法的缺陷,改进的K近邻法首先对训练样本进行聚类,将样本的特征空间划分成若干满足一定条件的小超球体,然后依据最近间隔值在这些小超球体内搜索待分类样本的K个近邻点·算法通过特征选取,选出反映样本模式重要信息的

2、特征,从而确保了聚类的质量·同时K近邻算法中引入的最近间隔值,既确定了近邻点的搜索半径,又保障了搜索的准确性·通过实验证实,该方法不但节省时间,还有较高的识别率·关　键　词:K近邻法;聚类;特征选取中图分类号:TP391.4文献标识码:A0　引　　言K近邻法是一种应用广泛的非参数分类方法,可用于线性不可分的多类样本识别·它的优点是事先并不要求知道待分样本的分布函数·目前广泛使用的K近邻法是以待分类样本为中心做超球体,逐渐扩大超球半径直至超球内包含K个已知模式样本为止,判断这K个近邻样本中多数属于哪一类,就[1]把待分类样本归为哪一类·分类算法描述如下:假设有c个类别w1,w2,⋯,wc,i=

3、1,2,⋯,c·测试样本x和与其最近的样本之间的距离为gi(x)kk=minx-xi,k=1,2,⋯,ni,其中xi的下标i表示wi类,上标k表示wi类ni个样本中第k个样本·k在超球半径r≥mingi(x)的前提下,求L=argmaxki,ki(0

4、为K值的选取是根据每类样本的数目和分散程度选取的,对不同的应用[2]选取的K值也不同·为此本文采用的设计思想是在K值选定的情况下,对近邻点的搜索区域进行合理的定位,即全局到局部,同时还要保障分类结果的准确性·方法是首先将样本空间的样本点进行小规模有目的性的聚类,聚类后样本空间中样本分布的区域被划分成,若干个半径一定的小超球体·如果能保证超球体内主体类样本数远远大于杂质类样本数,那么搜索时就可根据其条件将搜索范围缩小到某些超球体内,在这些超球体内寻找待分样本点的K个近邻点·1聚　　类聚类技术可以把无标识数据对象自动划分为不同的类,并且可以不受人的先验知识的约束和干扰,[3]从而获取属于数据集合

5、中原本存在的信息·将观测样本聚类到同类中的标准是相似性指标,欧式距[4]离是目前比较常用的相似性指标·欧式距离公式如下:收稿日期:2006211228作者简介:周而重(1981-),男,辽宁辽阳人,沈阳化工学院硕士研究生;逄玉俊(1954-),男,辽宁丹东人,沈阳化工学院教授,硕士研究生导师·476沈阳师范大学学报(自然科学版)　　　　　　　　　　　　　　第25卷m1(x)22(1)d=6ik-xjk·k=1由于计算机只能处理数值型数据,而训练数据往往是由代表不同物理意义的属性值组成的记录,因此需对训练数据进行量化处理,生成特征矢量·在量纲取定的条件下,两个矢量越相似,欧式距离就越小·但在使

6、用欧式距离描述具体对象时,量纲选取的不同会改变某些特征的判断依据性,严重的可造成错误聚类·这是因为改变特征矢量某分量的量纲后,两个特征矢量相应的分量值也将改变·若两个分量的数值变小,则其发挥的作用将变小;反之将增大,这样就不能很好地反映事实·归一化处理虽然可以在一定程度上解决上述问题,但归一化的结果往往使特征矢量的各分量都处于平等地位·为提高聚类的质量,本文在聚类前要滤去那些发挥作用不大的特征分量·1.1　特征选取当训练样本较好时,n个样本在每一维上都应近似呈高斯分布,每个样本的同一维特征聚集在其均值附近的一定范围内,偏差越小则说明该维特征越典型,反之偏差越大,其代表性也越差,该维特征对分[

7、5]类就越不利,属于无关特征·特征选取的方法是在训练样本集中,计算出训练样本同一维上的特征方差,若方差很小则保留该特征项·1.2　聚类方法设计定义c(x)表示x所在类的中心,d(x,y)表示点x与y间的欧式距离·聚类后两点x1和x2在同一个聚类中的条件为d(x1,x2)≤2r,r为聚类后的类半径·在同一聚类中,无论x1和x2是否属于同一类别都应满足下列条件:d(x1,x2)≤d(x1,c(x2))+r·(2)