KNN原理及应用

4.3.4KNN分类器K近邻法也就是K·NeaurestNeighbor方法，又称为KNN分类法。它是一个理论上比较成熟的方法，是由Cover和Hart（1967）提出的。此算法的思想简单直观：若一个样本在特征空间中的k个最相似（也就是特征空间中最邻近）的样本中的大多数都属于某一个类别，则此样本也属于这个类别。此方法在分类决策上仅依据最邻近的一个或几个样本的类别来最终决定待分样本所属的类别。最近邻法是在己知类别的训练样本条件下，按最近距离原则对待识模式分类。KNN分类方法思想直观，效果较好，方法简单，其中某些技术在理论上能够实现先验知识完备的贝叶斯决策的分类效果，可以适应类域分布较复杂的情况之中，是最重要的模式识别技术之一，而且在生物信息学等多个科学领域有着非常重要的应用。假设数据集：ijy，i=1，2，…，c，j=1，2，…，iN，此ciiNN1个数据分别属于c种不同类别，其中iN是第i个分类iw的样本个数。分类思想是：对一个待测数据x分别计算它与这N个已知类别的样本ijy的距离，将其判为距离最近的那个样本所属的类。基于此分类思想iw类的判决函数是：)(2,1min)(dijiNjiyxx，i=1,2，…，c（4.48）判决规则为：))((minargx,2,1xdmicim，（4.49）因为上述的方法仅根据离待识模式最近的一个样本的类别所决定其类别，所以一般称为最近邻法或1-近邻方法。为了克服单个样本类别的偶然性，从而增加分类的可靠性，考察待测数据的k个最近邻样本，这k个最近邻中哪一类的样本最多，就将x判属给哪一类，也就是说如果假设样本最多就将x判属为哪一类。例如设ckkk，，，21分别是x的k个最近邻样本属c，，，21的样本数，定义iw类的判决函数是：iikd）（x，i=1,2，…,c（4.50）判决规则为：))((axx,2,1xdmmicim，（4.51）该方法通常称k近邻算法，也就是KNN。KNN算法的误判概率在样本数有限的情况下和具体距离的测度是有直接关系的。所以利用适当的距离函数，在此基础上选择最近样本数能够提高分类的正确率。目前在k近邻算法中有多种距离函数能够用于运算，例如Euclidean距离定义是：2112)(),(niiiyxyxd（4.52）其中),,,(,),,,(2121nnyyyyxxxx，n为输入特征的维数。Manhattan距离定义为：n1),(iiiyxyxd（4.53）Mahalanobis距离定义为：)()(),(d1yxVyxyx（4.54）其中V为x和y所在数据集的协方差函数。KNN方法虽然从原理上依赖极限定理，但在类别决策时仅和极少量相邻样本有关。所以利用此方法能够较好地避免样本不平衡问题，另外因为KNN方法主要依靠周围有限的邻近的样本，并不是依靠判别类域的方法确定所属类别，所以对类域的交叉或重叠较多的待分样本集来说，KNN方法相对于其他方法更为合适。此方法的不足是计算量较大，由于对每一个待分类的样本均要计算它到全部已知样本的距离，才可以求出它的K个最近邻点。通常的解决方法是先对已知样本点剪辑，除去对分类作用不是很大的样本。此算法较适用样本容量较大的类域的分类。K-NN(K-NearestNeighbor)能够看作是贝叶斯分类器的一种特殊的情况。本研究利用一种改进的K-NN方法：在每类的训练集中各找K个和测试向量距离最近的点，再分别取每类K个距离的平均值代表测试向量和类间的距离，得到测试向量被分类到与其具有最小平均距离的那个类中。k近邻分类器是模式识别领域中一种广泛应用的直推式方法。使用KNN设计样本奇异度函数简单直观，并不需要构建和保存模型，但它需要保存所有的历史数据，计算代价放在了每次的预测过程中，而且频繁访问与寻找近邻；并且依赖采用的距离度量，因为缺少数据的分布信息，实际应用中通常利用欧氏距离。利用KNN设计的样本奇异度函数是：kjyijkjyijidd11ijni,,2,1（4.55）值相对某一类训练样本的奇异值越高，则待测样本隶属该类的置信度就越低。式中kjyijd1表示类别不为y的所有样本中，欧式空间中与样本i最近的k个样本与其邻近度之和；kjyijd1表示类别为y的所有样本中，与样本i最近的k个样本与其邻近度之和。K近邻分类器在实际应用中是一种比较常用的分类方法。近邻规则算法：给定一个未知特征向量x和一种距离测量方法，在N个训练向量之外不考虑类的标签确定K近邻。在两类的情况下，k选为奇数，通常不是类别数M的倍数。在K个样本中确定属于iw，i=1，2…，M类的向量的个数ik知道kkii。x属于有最大ik值的那一类iw。能够利用不同的距离测量方法，包括Mahalanobis距离和欧几里德距离。此算法最简单的情况为k=1，即是近邻规则，也就是特征向量x被归到最近邻的类中。在训练样本数量较大时此简单规则能够有良好的性能。当N→∞时，近邻规则的分类错误率NNP满足如下式：BBBNNBPPMMPPP212（4.56）其中BP为最优贝叶斯理论错误率，对于贝叶斯理论误差小的情况，下面的近似值是比较有效的：BNNPP223)(3BBNNPPP（4.57）因此对N足够的大且贝叶斯理论误差足够的小的情况，k近邻分类器和贝叶斯分类器的性能非常的接近。当k值更大时，则相似度也有所增加。此算法的优势是并没有太多的数学计算的影响。当N足够的大的情况下，以x为中心包括k个点的超球面半径（欧几里德距离）趋向于零，期望空间也就被样本浓密地填充了起来。因此x的k近邻会距离它非常的近，且x周围超球面内所有点的条件概率近似等于p(i|x)（假设为是连续的）。此外k足够的大时，区域内大多数的点属于最大条件概率所对应的类。所以，k近邻规则趋向于贝叶斯分类器。最近邻分类器采用的是各类中的全部样本都作为代表点，将未知样本X判别为与离它最近的样本同类。因此最近邻分类器能够在一定程度上克服因为各类样本均值向量的偏差而造成的影响。KNN算法特征之间的相关性度量利用的是最大信息压缩指数。此算法先计算特征集中每个特征和第K个相近特征之间的λ值，选λ值最小的特征则保留此特征，删除K个相近的特征。在此过程中需要设置一个门限值ε，设其值是上一次循环中被删除的第K个近邻的λ值。在接下来的循环中，对第K个近邻的λ值进行比较，是否大于ε值，若大于就减小K值。所以在循环过程中K值是逐渐减小的。令原始特征集是O={Fi,i=1,,,D}；原始特征的数目是D；消除冗余的特征子集是R；λ（jiFF，）用来标识特征jiFF，间的不相关性，也就是λ越大，特征就越不相关；k为特征F和R中第K个相近特征不相关性的体现。具体步骤如下：(1)选择初始K值且K≤D，初始化R使得R=O；(2)每个特征F∈R，计算k；(3)找出使k最小的特征F，保留F且删除F的K个最相近的特征，ε=r；(4)如果Kcardinality(R)-1，得出K=cardinality(R)-1；(5)如果K=1，则转到步骤(8)；(6)K会不断的减1，直到第K个近邻的λ值至少有一个小于ε；如果K=1转到步骤(8)(如果R中并没有特征以及其近邻的λ值比ε小，则选择R中所有的特征)；(7)如果r≤ε，则转到步骤(2)；(8)输出R。流程如图4.2所示：对每个特征iF选K≤D，R←O开始is是图4.2KNN算法流程图KNN算法的难度较低，耗时比搜索性算法小，并且能将冗余的特征有效去除。做为分类器的选择，以分类器对样本分类的准确率作为参考，确定选择的特征对于肺裂特征样本和正常样本的分类确实是有效的。分类器种类较多,针对分类器的性能并没有统一的评价标准。KNN分类器能够比较好地避免样本不平衡问题；对于重复较多的待分样本集来说，KNN方法相对于其他的方法（例如肺裂特征样本集）更为适合。它适用于样本容量较大的分类。