1、第六第六章章 近邻法近邻法6.1 最近邻法最近邻法一一.最近邻法的基本思想最近邻法的基本思想此法是一种根据全部样本全部样本提供的信息，绕开概率的估计而直接决策的方法，所以它是非参数决策方法是非参数决策方法的一种。其基本思想基本思想是：设有一组N个样本 =X1,X2,XN其中每个样本都已标以类别标志。如果在这N个样本中与待分样本X相距最近相距最近的一个样本为Xi，则把X分到Xi所在的类别中去。二二.最近邻法的决策规则最近邻法的决策规则设有c类模式样本，1,2,c每类有Ni个样本(i=1,2,c)，则最近邻法的最近邻法的(i类类)判别判别函数为函数为:式中 表示i类中的第k个样本。kiX)N,1,
2、2,.(k min)(ikikiXXXg 对应的决策规则为：对应的决策规则为：如果如果 则决策则决策 即只要将待分样本X与全部与全部N()个已知类别的样本进行欧氏距离欧氏距离之间的比较，然后将X归到离它最近的类别中归到离它最近的类别中。由于这种方法只根据离待分样本X最近的一个样本的类别而决定其类别，所以通常称为1-最近邻法最近邻法(亦称1-NN方法方法)iXciiN1c),1,2,.(j )(gmin)(jXXgji三三.最近邻法的错误率问题最近邻法的错误率问题最近邻法是一种次优次优方法，它的错误率错误率比最小错误概率最小错误概率的的Bayes决策规则决策规则下的错误率要大要大，但是，当样本数
3、目无限无限时，它的错误率不会超过Bayes错误率的一倍一倍。定性分析：定性分析：若将X的最近邻Xj的类别看成是一个随机变量随机变量 ，于是 的概率就是后验概率 .当样本数目很多样本数目很多时，可以认为X的最近邻Xj 离它很近离它很近，从而近似的近似的认为j)(jjXPjj)()(XPXPjjj这时最近邻法可看成是如下的随机化决策如下的随机化决策：按照概率按照概率 来决定来决定X的类别的类别。故最近邻法可看成是用后验概率后验概率来对X进行分类的。再进一步说，就是如果有下式成立如果有下式成立：则依Bayes决策，应取 作为X的类别。而在最近邻法最近邻法中，最近邻的类别为 的概率为 ，所以X分到分到
4、 类去的概率为 ，而不分到不分到 类去的概率为：)(XPi)(XPj)(max)(XPXPjjiii)(XPii)(1XPii这也就是说：这也就是说：按Bayes决策决策的话：以概率为1，而得决策 按最近邻法决策最近邻法决策的话：以概率为，而得决策 显然，当接近于当接近于1时，最近邻法与最小错误率下的Bayes法的结果结果就几乎相同几乎相同了。也就是说，当最小错误概率较小时，最近邻法的错误概率也是较小的，这两种方法同样同样“好好”。而当各类的都接近于当各类的都接近于 时时(即所有类别是等可能的)，最近邻法与Bayes法的结果就不一样了。这时两者的错两者的错误率都接近于误率都接近于iX)(XPi
5、iX)(XPi)(XPic1c11 定量描述：定量描述：式中：p为最近邻法的渐近平均错误率 为 Bayes错误率 c 为类别数 一般较小 )12(PccPPPPP PPP2 6.2 k-近邻法近邻法(k-NN法法)为了克服单个样本类别的偶然性偶然性以增加分类的可靠性可靠性，可将最近邻法则最近邻法则进行改进，一个简单的方法就是k-近邻法近邻法。此法就是考察待分样本考察待分样本X的的k个最近邻样本个最近邻样本，这这k个最近邻个最近邻元素中元素中哪一类哪一类的样本最多的样本最多，就将X判属哪一类。或者说，就是在在N个已知类别个已知类别的样本中，找出的样本中，找出X的的k个近邻个近邻，这，这k个近邻中
6、个近邻中多多数属于的那一类数属于的那一类 ，就是 。具体就是：具体就是：设k1,k2,.,kc分别为X的的k个最近邻样本个最近邻样本中属于属于 类的样本数类的样本数，iiXc,.,21则定义定义 类的判别函数为：类的判别函数为：决策规则为：决策规则为：如果如果 则判则判最近邻法和k-近邻法的共同优点是简单简单，而且结果是比较好结果是比较好的的，但是它们也存在下述问题存在下述问题：需要将全部样本全部样本存入机器中，每次决策都要计算X与全部样本间的距离并进行比较。所以要求的存储容量存储容量和和计算量都很大计算量都很大。没有考虑到决策的没有考虑到决策的风险风险，所以如果决策的错误代价很大时，会产生很
7、大的风险。上述分析是建立在样本数建立在样本数 的假定上的的假定上的，这在实际实际应用中是无法实现的无法实现的。),.,2,1(ciiiikXg)()(max)(XgXgiijjXN6.3 近邻法的改进算法近邻法的改进算法共同特点是如何尽快地找出尽快地找出最近邻可能存在的小的空间，减少搜索的范围减少搜索的范围，从而达到减少减少近邻法中的计算量计算量和存储量存储量的问题。一一.快速近邻算法快速近邻算法该算法对最近邻法对最近邻法和k-近邻法近邻法都适用都适用。下面以最近邻法为例来讨论。1.基本思想基本思想将全部已知样本按级分成全部已知样本按级分成一些不相交的子集不相交的子集，并在子集的基础上进行搜索
8、。也就是说，该算法由两个阶段组成：第一阶段：第一阶段：将样本集按级分解按级分解，形成树状结构。第二阶段：第二阶段：用搜索算法搜索算法找出待识样本的最近邻。2.涉及的规则涉及的规则设=X1,X2,XN表示全部样本集全部样本集；P表示节点P对应的样本子集样本子集，即P；NP表示P中的样本数中的样本数；MP表示P中的样本均值中的样本均值(即“类心类心”)；rP ：表示从从MP到到Xi p 的最大距离的最大距离；B表示除除p中的样本之外的样本中的样本之外的样本到待分样本X的最近距离最近距离。B的初值设为，以后再不断修正不断修正。规则规则1如果存在如果存在 则Xi p不可不可能是能是X的最近邻的最近邻。
9、),(ppMXDrB),(maxpiXMXDpi证明：证明：对任意 ，据三角不等式有 而据 rp定义有 由上两式可得 即得则则 不可能是不可能是X的最近邻的最近邻。piX),(),(),(pPiiMXDMXDXXDppirMXD),(BrMXDXXDpPi),(),(),(ppMXDrBpiX的近邻iMp rP规则规则2.如果存在则 不可能是X的最近邻。证明：证明：比较规则比较规则1与规则与规则2，并参图，可知 故得证。),(),(ppiMXDMXDBpiXppirMXD),(3.快速近邻算法快速近邻算法第一阶段：第一阶段：将样本集样本集按级分解按级分解。首先将将分为l个子集个子集，每个子集再
10、分成每个子集再分成l个子子集个子子集，依次分下去，图图6.3为l=3的情况。这时每个节点上对应一群样本。第二阶段：第二阶段：搜索搜索树搜索算法：step1：设置设置B=，L=0，P=0.(L是当前水平，P是当前节点)。step2：将当前节点当前节点P的所有直接后继节点所有直接后继节点(即子节点)放入一个目录表中，并对这些节点节点X计算计算),(pMXD二二.剪辑近邻法剪辑近邻法此类方法的基本思想是基本思想是：剪掉剪掉(清理)两类间的边界两类间的边界，取掉类别混杂的样本混杂的样本，使两类边界更清晰。1.两分剪辑近邻法两分剪辑近邻法(亦称剪辑最近邻法剪辑最近邻法)基本过程为：基本过程为：设N个样本
11、分成c类 =,(N1+N2+,+Nc=N)step1：剪辑。剪辑。利用已知样本集 中的样本进行预分预分 类，类，并剪辑掉被错分类的样本剪辑掉被错分类的样本，留下的样本构成 剪辑样本集剪辑样本集step2：分类。分类。利用 和近邻规则对未知样本X进行 分类。NN11N22NccNENNE下面以两类情况以两类情况进行具体介绍：设将已知类别的样本集N分成测试集测试集NT和参照集参照集NR两个独立的独立的部分(即这两部分没有公共元素没有公共元素)，它们的样本数各为NR和NT，且NR+NT=N。剪辑步：剪辑步：利用参照集参照集NR中的样本 对测试集对测试集NT 中的每个样本每个样本采用最近邻法进行分类，并剪辑掉剪辑掉NT中被错误中被错误分类的样本分类的样本。或者说，若 的最近邻样本最近邻样本，则剪辑掉与与Y(X)不同类的样本不同类的样本X，然后将NT中余下的样本构成剪辑样本集剪辑样本集NTE。分类步：分类步：利用剪辑样本集剪辑样本集NTE 采用最近邻规则最近邻规则对待识样本X作分类决策。NTNR)(XXY是NRYYY,.,21
