第5章-近邻法分析课件.ppt

1、第第5 5章章 近邻法近邻法第第5 5章章 近邻法近邻法返回本章首页返回本章首页第第5 5章章 近邻法近邻法返回本章首页返回本章首页x12,c xxiN( ) min, 1,2,kiiiigkNxx x( ) min( ), 1,2, jiiggic jxxx第第5 5章章 近邻法近邻法返回本章首页返回本章首页第第5 5章章 近邻法近邻法返回本章首页返回本章首页xNxn, 1,2,iic Nlim()()iiNPPNxxx()iPx() max() 1,2,miPPicxx第第5 5章章 近邻法近邻法返回本章首页返回本章首页()mPxmmx123() 0.4 () 0.3 () 0.3PPPx

2、xx1x1() 0.4Px1x11() 0.6Px1x() 1mPx1()mPcx11c第第5 5章章 近邻法近邻法返回本章首页返回本章首页() max() 1,2,miPPicxx( )() ( )P eP epdxxx()P e x( )P e() 1()() ( )mP ePPP epd xxxxx( )NPelim( )NNPPe第第5 5章章 近邻法近邻法返回本章首页返回本章首页21cPP PPc()NPex,xlim()()Npx xxx11() 1(,) 1() ()ccNiiiiiiPePPP x,xx,xxxx x()() ()NNPePepdxx,xx xx x第第5 5章

3、章 近邻法近邻法返回本章首页返回本章首页212121lim()lim() ()lim1()()lim1()1()NNNNciNiciNiciiPePepdPpdPdPxx,xx xxxx xxxxxxx11() 1(,)() ()1cciiiiiiNPePPP x,xx,xxx21lim() 1()cNiNiPeP x,xx第第5 5章章 近邻法近邻法返回本章首页返回本章首页lim()()Npx xxxx()SPpdxSxxx(1)NSPlim(1)0NSNPlim()()Npx xxx第第5 5章章 近邻法近邻法返回本章首页返回本章首页21lim( )lim() ( )1()( )NNNNc

4、iiPPePepdPpdxxxxxx上式即是最近法错误率的计算公式，先看下界的证明，这里指出下上式即是最近法错误率的计算公式，先看下界的证明，这里指出下面的面的 两种特殊情况。两种特殊情况。（1） （2） 21() 1() 0() ( )01()( )1mciiP ePPP epdPPpd xxxxxxxx() 1mPx1() 1,2,iPiccx21() 1() (1)() ( )(1)1()( )(1)mciiP ePc cPP epdc cPPpdc c xxxxxxxxPP第第5 5章章 近邻法近邻法返回本章首页返回本章首页现在在来求最近邻法分类错误率的精确上界。现在在来求最近邻法分类

5、错误率的精确上界。2221222221222122() 1()()()min1()( )()()()()()()()()1()1 2)1)(ciicimimiii mi mccimiii mii mimi mcii mPPpdPPPPPPPPP ePP ePPP ePePc xxxxxxxxxxxxxxxxxx2)()1cPecxx第第5 5章章 近邻法近邻法返回本章首页返回本章首页221221221222() 1 2()()11() 2()()11()( )2()()( )12() ( )() ( )12(2)211()ciiciiciicPP ePeccPP ePeccPPpdP ePep

6、dccP epdPepdcccPPPPPccPe xxxxxxxxxxxxxxxxxxxx2( )pdPxx第第5 5章章 近邻法近邻法返回本章首页返回本章首页第第5 5章章 近邻法近邻法返回本章首页返回本章首页第第5 5章章 近邻法近邻法返回本章首页返回本章首页 1, 01() 1, 110, icrxccrpi x ic x其其它它1()iPcPrPrP P第第5 5章章 近邻法近邻法返回本章首页返回本章首页11() ()() ( )() ()() ()1, 0 1 1, 01() 1, 1 ( )11, 0, 1, 0() 1 1, ciiiiiciiiiimpPPppPpPcrxcrc

7、cxccrPi x ipcccrxPcc xxxxxxxx其其它它其其它它其其它它第第5 5章章 近邻法近邻法返回本章首页返回本章首页1021201111, 0() 1() 1 0, 11() ( )(1) ( ) 111()( )1( ) mcrccrccciiicrxPePccccrPPepdpdrcccPPpdpdPc xxxxxxxxxxxx其其它它课后习题课后习题P160： 6.3 6.4 6.5P81： 3.1 3.4 3.15 第第5 5章章 近邻法近邻法返回本章首页返回本章首页x1xx212kk12kkk(1) 212112120(1) 221201211 212 ()()()

8、() 2kjjkjkjkjjkjkjkkkkkkC PPPPkkCxxxxxx第第5 5章章 近邻法近邻法返回本章首页返回本章首页12,kx xx12(1) 21101(1) 2120(1) 221(1) 20111()()()()()()1()1)()()(1(kNkkjjjkkjjkjkjkjjkjkjkkjjjkjkjC PPC PPPPPPePPPC PC P xxxxxxxxxxxxxxNxxx第第5 5章章 近邻法近邻法返回本章首页返回本章首页(1) 21110111(1) 21111(1) 21211()()()1()1()()1()()1 2 ()()1() min(), ()

9、min(),1()kkjjkjNkjkkjjjkjkkkjjjkjkPePC PPPC PPPPCPePPPPPP xxxxxxxxxxxxxxxx(1) 2)()()()1 21()()kkjjkjNkjkPeCPePePePexxxxx第第5 5章章 近邻法近邻法返回本章首页返回本章首页()kNP E Pex()Pex()kCPex()kNPex()()kNkPeCPexxx()()()()kNkkkP E PeE CPeCE PeCPxxx ()kNkkPCP11()()() 2(1)21kkcPP CPCPC PPP PPcPP第第5 5章章 近邻法近邻法返回本章首页返回本章首页11(

10、)()() 2(1)21kkPP CPCPC PPPcPP PPc第第5 5章章 近邻法近邻法返回本章首页返回本章首页第第5 5章章 近邻法近邻法NTX返回本章首页返回本章首页NXNRNRXNTXNTNR NTN12,NRyyy12,NRx xx()NRXiy xNTXixNRX()iy xixNTXNTEX第第5 5章章 近邻法近邻法返回本章首页返回本章首页 (01)1NTNNR,NTEX()y xxNT NR1()Px2()PxxNTX x xNRXlim()N y xx11lim()()NPPy xxx xx121112()()1 2 () ()PPP xxxx第第5 5章章 近邻法近邻

11、法返回本章首页返回本章首页x122112()() ()() ()2 () ()P ePPPPPPxxxxxxx12x2111221122111111111()() ()() ()() ()() ()() 1()1()()()() 2 () ()EPePPPPPPPP xxxxxxxxxxxxxxxxx第第5 5章章 近邻法近邻法返回本章首页返回本章首页111112211111212212111122()()() 2 () ()()()()2()1 2 () ()1 2 () ()() ()1 2 () ()() 21()()1 2 () ()()EPePPPPPPPPPPPPPPPPeP eP

12、P xxxxxxxxxxxxxxxxxxxxxxx第第5 5章章 近邻法近邻法返回本章首页返回本章首页11111() 2()1()1 2 1()2 () 1()()()()2 1()2 1()1()22 () 1()()()0 2 1()()()( )( )EEEEEP ePeP eP eP ePeP eP eP eP eP eP eP ePeP eP eP ePeP ePeP e xxxxxxxxxxxxxxxxxxx第第5 5章章 近邻法近邻法返回本章首页返回本章首页221112122121()()1 2 () ()()() 1,2()()() 2()1()iiEPPiPPP ePePPP

13、e xxxxxxxxxxxxi第第5 5章章 近邻法近邻法返回本章首页返回本章首页2222 122122122122222122 1222212222212122221()()()()()()()()()()()()()()()()()()()()()iiiiiiiiPPPPPPPPPPPPPPPPPPP xxxxxxxxxxxxxxxxxxxxx22()xxi第第5 5章章 近邻法近邻法返回本章首页返回本章首页21221211121212121122212112()()()()()() ()() ()()() 1()()lim() min(), ()MMMMMMMiMiEMMMEMMPPPP

14、ePPPPPPPePP xxxxxxxxxxxxxxxxxi第第5 5章章 近邻法近邻法返回本章首页返回本章首页122112222122121222112lim()() 1()() 1()lim()()1()()()1()lim1()()min(), ()MMMMMMEMMMMPePPPPPPPPPPPPPP xxxxxxxxxxxxxxx第第5 5章章 近邻法近邻法返回本章首页返回本章首页0第第5 5章章 近邻法近邻法返回本章首页返回本章首页kk1 2kk xkiix112()()()kllk lkl kC PP xxxxk1221120()()()()()kllk lkl kk kllk

15、lklC PPC PP xxxxx第第5 5章章 近邻法近邻法返回本章首页返回本章首页kxk012121201121()1()()1()()()()()()kk kllk lllk lkkl klkllk lkl k kC PPC PPC PP xxxxxxxxx012()()() 1 xxx0() x第第5 5章章 近邻法近邻法返回本章首页返回本章首页x10121()()()kllk lkl k kC PP xxx1221()() ()() ()P ePP xxxxxk1 2kk 第第5 5章章 近邻法近邻法返回本章首页返回本章首页xNX1 2kk jxNXkjxki() (1,2)jBi ix() 0jBxNX() 0jBx() (1,2)jiBi ix() 0jBxjx0NRXNRXx第第5 5章章 近邻法近邻法THANK YOU VERY MUCH ！本章到此结束本章到此结束下一章下一章“返回本章首页返回本章首页结结 束放映束放映