模式识别课件(第六章NO1)(最近邻法).ppt

,绕开概率的估计而直接决策的方法,所以它是非参数决策方法的一种。其基本思想是:设有一组N个样本æ={X1,X2,……,XN} 其中每个样本都已标以类别标志。如果在这N个样本中与待分样本X相距最近的一个样本为Xiæ,则把X分到Xi所在的类别中去。, ω1,ω2,……,ωc 每类有Ni个样本(i=1,2,……,c),则最近邻法的(ωi类)判别函数为: 式中表示ωi类中的第k个样本。对应的决策规则为: 如果则决策即只要将待分样本X与全部N()个已知类别的样本进行欧氏距离之间的比较,然后将X归到离它最近的类别中。由于这种方法只根据离待分样本X最近的一个样本的类别而决定其类别,所以通常称为1-最近邻法(亦称1-NN方法),它的错误率比最小错误概率的Bayes决策规则下的错误率要大,但是,当样本数目无限时,它的错误率不会超过Bayes错误率的一倍。定性分析:若将X的最近邻Xj的类别看成是一个随机变量,于是的概率就是后验概率. 当样本数目很多时,可以认为X的最近邻Xj离它很近,从而近似的认为这时最近邻法可看成是如下的随机化决策: 按照概率来决定X的类别。故最近邻法可看成是用后验概率来对X进行分类的。再进一步说,就是如果有下式成立: 则依Bayes决策,应取作为X的类别。而在最近邻法中,最近邻的类别为的概率为,所以X分到类去的概率为,而不分到类去的概率为:这也就是说: 按Bayes决策的话:以概率为1,而得决策按最近邻法决策的话:以概率为,而得决策显然,当接近于1时,最近邻法与最小错误率下的Bayes法的结果就几乎相同了。也就是说,当最小错误概率较小时,最近邻法的错误概率也是较小的,这两种方法同样“好”。而当各类的都接近于时(即所有类别是等可能的),最近邻法与Bayes法的结果就不一样了。这时两者的错误率都接近于定量描述:式中:-近邻法(k-NN法) 为了克服单个样本类别的偶然性以增加分类的可靠性,可将最近邻法则进行改进,一个简单的方法就是k-近邻法。此法就是考察待分样本X的k个最近邻样本,这k个最近邻元素中哪一类的样本最多,就将X判属哪一类。或者说,就是在N个已知类别的样本中,找出X的k个近邻,这k个近邻中多数属于的那一类,就是。具体就是:设k1,k2,......,kc分别为X的k个最近邻样本中属于类的样本数,则定义类的判别函数为:决策规则为: 如果则判最近邻法和k-近邻法的共同优点是简单,而且结果是比较好的,但是它们也存在下述问题:①需要将全部样本存入机器中,每次决策都要计算X与全部样本间的距离并进行比较。所以要求的存储容量和计算量都很大。②没有考虑到决策的风险,所以如果决策的错误代价很大时,会产生很大的风险。③上述分析是建立在样本数的假定上的,这在实际应用中是无法实现的。,减少搜索的范围,从而达到减少近邻法中的计算量和存储量的问题。-近邻法都适用。下面以最近邻法为例来讨论。,并在子集的基础上进行搜索。也就是说,该算法由两个阶段组成:第一阶段:将样本集按级分解,形成树状结构。第二阶段:用搜索算法找出待识样本的最近邻。