ch 05 非參數(shù)方法

1、Ch 05. 非參數(shù)方法,Part 2 kn-近鄰估計(jì),Parzen窗估計(jì)的問題,如果p(x)的分布不均勻，在整個(gè)特征空間中采用同樣的窗寬度可能無(wú)法總是得到令人滿意的結(jié)果,,同樣尺寸的窗口,kn-近鄰估計(jì),一種解決Parzen窗估計(jì)單一窗寬問題方法不固定窗寬度，而固定包括在x周圍的某個(gè)區(qū)域中的樣本個(gè)數(shù)k通常k取決于樣本總數(shù)n，所以表示為kn當(dāng)x周圍數(shù)據(jù)密度大時(shí)，窗口變?。ǚ直媛矢撸┊?dāng)x周圍數(shù)據(jù)密度小時(shí)，窗口變大（分辨率低）包括

2、進(jìn)來的kn個(gè)樣本稱為x的kn個(gè)最近鄰,,窗口包含同樣多的樣本,kn-近鄰估計(jì),令 ，則 收斂到真實(shí)分布p(x)的充要條件為滿足此條件的一個(gè)常用選擇,,舉例,一維分布，n=1時(shí)， 時(shí)，,,舉例,,,n=8, k=3或5,舉例,,,K=5,舉例,,,更多非參數(shù)估計(jì)的例子,直方圖估計(jì),更多非參數(shù)估計(jì)的例子,Parzen窗估計(jì),更多非參數(shù)估計(jì)的例子,kn-近鄰

3、估計(jì),更多非參數(shù)估計(jì)的例子,,更多非參數(shù)估計(jì)的例子,,Ch 05. 非參數(shù)方法,Part 3 k-近鄰規(guī)則,模式分類的途徑,途徑1：估計(jì)類條件概率密度通過 和 ，利用貝葉斯規(guī)則計(jì)算后驗(yàn)概率 ，然后通過最大后驗(yàn)概率做出決策兩種方法方法1a：概率密度參數(shù)估計(jì)基于對(duì) 的含參數(shù)的描述方法1b：概率密度非參數(shù)估計(jì)基于對(duì) 的非參數(shù)的

4、描述途徑2：直接估計(jì)后驗(yàn)概率不需要先估計(jì)途徑3：直接計(jì)算判別函數(shù)不需要估計(jì) 或者,,后驗(yàn)概率的非參數(shù)估計(jì),假設(shè)一個(gè)x附近的區(qū)域R，能夠包括進(jìn)k個(gè)樣本，其中ki個(gè)屬于類別 ，則后驗(yàn)概率決策Parzen窗估計(jì)：選擇 最大的類別kn-近鄰估計(jì)：選擇 最大的類別,,最近鄰規(guī)則,k=1時(shí)的k-近鄰決策把x判斷為與其距離最近的訓(xùn)練樣本x’所屬的類別給定訓(xùn)練集

5、 ，其中包括n個(gè)來自c個(gè)不同類別的樣本對(duì)測(cè)試樣本x，如果 是距離x最近（根據(jù)某種距離度量）的訓(xùn)練樣本，則最近鄰（1-NN）規(guī)則為最近鄰規(guī)則是次優(yōu)的方法，通常的誤差率比最小可能的誤差率（即貝葉斯誤差率）要大,最近鄰規(guī)則,直觀理解當(dāng)樣本個(gè)數(shù)非常大時(shí)，可認(rèn)為x’距離x足夠近，以使得即最近鄰規(guī)則是對(duì)真實(shí)后驗(yàn)概率的一個(gè)有效近似,Voronoi網(wǎng)格,最近鄰規(guī)則把特征空間分成一個(gè)個(gè)網(wǎng)格單元結(jié)構(gòu)，稱為Voronoi

6、網(wǎng)格每一個(gè)單元包含一個(gè)訓(xùn)練樣本點(diǎn)x’該單元中任意一點(diǎn)x，到x’的距離均小于到其他訓(xùn)練樣本點(diǎn)的距離該單元中所有樣本點(diǎn)均判別為x’所屬的類別,最近鄰規(guī)則的誤差率,給定訓(xùn)練集 ，其中包括n個(gè)來自c個(gè)不同類別的樣本對(duì)測(cè)試樣本x，設(shè) 是距離x最近的訓(xùn)練樣本x和xk的類別標(biāo)記分別為 和條件誤差概率,最近鄰規(guī)則的誤差率,條件誤差概率（cont’）當(dāng) 時(shí)，假設(shè)D包含

7、的樣本足夠多，使得則當(dāng) 時(shí)，有平均誤差率（ 時(shí)）,最近鄰規(guī)則的誤差界,平均誤差率 的下界平均誤差率 的上界當(dāng) 對(duì)每個(gè)x取最小值時(shí)， 最大設(shè)x的真實(shí)類別為 ，則貝葉斯誤差率表示為,最近鄰規(guī)則的誤差界,平均誤差率 的上界（cont’）給定 （即給定 ）此式當(dāng)?shù)诙?xiàng)最小時(shí)最小，而第二項(xiàng)當(dāng)

8、 對(duì)所有除m以外的i取值相同時(shí)最小，即,最近鄰規(guī)則的誤差界,平均誤差率 的上界（cont’）所以或所以當(dāng)P*較小時(shí)，最近鄰規(guī)則的平均誤差率上界：,最近鄰規(guī)則的誤差界,,,,k-近鄰規(guī)則,k-近鄰（k-NN）規(guī)則是對(duì)最近鄰（1-NN）規(guī)則的擴(kuò)展，即考慮多個(gè)最近的鄰居給定訓(xùn)練集 ，其中包括n個(gè)來自c個(gè)不同類別的樣本對(duì)測(cè)試樣本x，設(shè)集合 包含距離x最近

9、的k個(gè)訓(xùn)練樣本k-近鄰規(guī)則,如果 是在S中出現(xiàn)頻率最高的類，則判斷x的類別為,,k-近鄰規(guī)則,,k-近鄰規(guī)則的誤差界,平均誤差率 的下界貝葉斯誤差率平均誤差率 的上界當(dāng) ，并且 時(shí)，當(dāng)k足夠大，但是相對(duì)于n又足夠小時(shí)，在大樣本數(shù)上應(yīng)用k-NN規(guī)則近似于最優(yōu)決策,k-近鄰規(guī)則的誤差界,,k的選擇,k-近鄰規(guī)則可被看作直接從樣本中估計(jì)后驗(yàn)概率 的方法為了得到可靠

10、的估計(jì)（誤差率低），k越大越好為了使 盡可能逼近 ，x的近鄰x’距離x越近越好，即k越小越好根據(jù)實(shí)際問題，折中選取k的值當(dāng)n趨向于無(wú)窮大，并且k以較慢的速度同樣趨向于無(wú)窮大時(shí)，k-近鄰規(guī)則是最優(yōu)分類規(guī)則,例子,k = 3 (奇數(shù))， x = (0.10, 0.25)x的k個(gè)近鄰:{(0.10, 0.28, ?2); (0.09, 0.30, ?5); (0.12, 0.2

11、0,?2)}根據(jù)k-近鄰規(guī)則，判斷x的類別為?2,計(jì)算復(fù)雜度,直接方法假設(shè)訓(xùn)練集D包括n個(gè)d維樣本給定一個(gè)測(cè)試樣本x，它與訓(xùn)練集中所有的樣本xi之間都要計(jì)算距離，計(jì)算復(fù)雜度為O(dn)當(dāng)n很大時(shí)，時(shí)間和空間復(fù)雜度都將很高！降低計(jì)算復(fù)雜度的方法計(jì)算部分距離預(yù)建立結(jié)構(gòu)對(duì)訓(xùn)練樣本加以剪輯,計(jì)算部分距離,在計(jì)算距離時(shí)，只使用d個(gè)維度中的一個(gè)子集r逐步加進(jìn)更多的維數(shù)時(shí)，部分距離的值嚴(yán)格非遞減計(jì)算測(cè)試樣本x的最近鄰時(shí)如何節(jié)

12、省計(jì)算量？計(jì)算x的最近鄰時(shí)，每考察一個(gè)訓(xùn)練樣本，可以更新當(dāng)前的x的最近鄰。如果x到某個(gè)訓(xùn)練樣本的在子集r上的部分距離已經(jīng)大于其到當(dāng)前最近鄰的距離，則計(jì)算可以立即停止，舍棄該訓(xùn)練樣本，繼續(xù)考察下一個(gè)。當(dāng)計(jì)算距離時(shí)，如果方差大的維度先計(jì)算，此技術(shù)尤其有用,預(yù)建立結(jié)構(gòu),預(yù)先建立某種形式的搜索樹，根據(jù)訓(xùn)練樣本點(diǎn)之間的相對(duì)距離將它們組織起來搜索樹建立好之后，尋找x的最近鄰只需訪問整個(gè)樹的一部分，因此可以節(jié)省計(jì)算量例子假設(shè)樣本服從單位正

13、方形內(nèi)的均勻分布選擇4個(gè)根節(jié)點(diǎn) 和對(duì)測(cè)試點(diǎn)x，首先計(jì)算其到4個(gè)根節(jié)點(diǎn)的距離，選擇最近的一個(gè)，接下來的搜索就僅局限于這個(gè)根節(jié)點(diǎn)所代表的象限了，而剩下的3/4訓(xùn)練樣本沒有必要訪問。不能保證找到x的真正最近鄰,訓(xùn)練樣本剪輯,消去那些“無(wú)用”的訓(xùn)練樣本哪些樣本“無(wú)用”？被同類別樣本包圍的樣本！,無(wú)用的樣本,訓(xùn)練樣本剪輯,最近鄰剪輯算法,Ch 05. 非參數(shù)方法,Part 4 距離度量,距離度量

14、,最近鄰規(guī)則或k-近鄰規(guī)則以衡量模式（樣本）之間的距離的度量為基礎(chǔ)距離度量是模式識(shí)別領(lǐng)域的核心問題之一度量（metric）的一般化表示度量必須滿足的性質(zhì)非負(fù)性：自反性：對(duì)稱性：三角不等式：,歐幾里德距離,d維空間中的歐幾里德距離特征尺度的變換會(huì)嚴(yán)重影響以歐幾里德距離計(jì)算的近鄰關(guān)系,歐幾里德距離,解決方案對(duì)每一個(gè)維度（特征）分布進(jìn)行尺度均衡化，使得每一維上的變化范圍都相等，如全部歸一化成[0, 1]區(qū)間,Minkow

15、ski距離,d維空間中的Minkowski距離又稱為L(zhǎng)k范數(shù)L2范數(shù)——?dú)W幾里德距離L1范數(shù)——Manhattan距離（街區(qū)距離） 范數(shù)——a和b在d個(gè)坐標(biāo)軸上投影距離的最大值,Minkowski距離,到原點(diǎn)的等距離面,Mahalanobis距離,Mahalanobis距離（馬氏距離）在計(jì)算距離時(shí)考慮特征之間的協(xié)方差Mahalanobis距離與多元正態(tài)分布的關(guān)系,Mahalanobis距離,例子a：[0

16、.8, 0.2]t，b： [0.1, 0.5]t從正態(tài)分布 抽取，其中 ，求a和b之間的馬氏距離解：,集合之間的距離度量,Tanimoto距離n1，n2分別為集合S1和S2中的元素個(gè)數(shù)n12為兩個(gè)集合交集中的元素個(gè)數(shù)應(yīng)用場(chǎng)景兩個(gè)模式（特征）之間要么相同，要么不同，無(wú)法計(jì)算某種分級(jí)的相似度例如如兩個(gè)單詞之間的Tanimoto距離，可以將每個(gè)單詞看作一

17、個(gè)字母的集合,集合之間的距離度量,Tanimoto距離例子根據(jù)Tanimoto距離，判斷下列單詞中哪個(gè)與‘pat’最為接近：‘cat’，‘pots’，‘pattern’解所以‘cat’與‘pat’最為接近,集合之間的距離度量,Hausdorff距離“一個(gè)集合中的點(diǎn)到另一個(gè)集合中的點(diǎn)的最小距離的最大值” 為某種衡量?jī)牲c(diǎn)a和b之間距離的度量歐幾里德距離Manhattan距離Mahala

18、nobis距離……,集合之間的距離度量,Hausdorff距離例子計(jì)算集合 與 之間的Hausdorff距離解,集合之間的距離度量,Hausdorff距離練習(xí)計(jì)算集合 與 之間的Hausd

19、orff距離,切空間距離,很多實(shí)際問題中，任意選擇距離度量（如最常用的歐幾里德距離）會(huì)帶來糟糕的結(jié)果,切空間距離,不變量（invariance）問題平移旋轉(zhuǎn)尺度變換線條粗細(xì)……解決方案預(yù)處理使用更加一般化（具有**不變性）的距離度量,切空間距離,切空間距離具有任意變換不變性假設(shè)問題可能會(huì)涉及r種變換對(duì)每一個(gè)訓(xùn)練樣本x’進(jìn)行所有可能的變換，表示為 ，i=1,2,…,r，其中 為第i個(gè)變

20、換的參數(shù)，如平移距離，旋轉(zhuǎn)角度等對(duì)每一種變換，可以構(gòu)造一個(gè)切向量（tangent vector）：所有變換的切向量張成x’的一個(gè)切空間（tangent space），該切空間是對(duì)x’可能發(fā)生的所有變換的一個(gè)線性逼近，其中每個(gè)點(diǎn)對(duì)應(yīng)一種可能的變換測(cè)試點(diǎn)x到x’的切空間距離即x到x’的切空間的最小距離，因此可認(rèn)為具有任意變換不變性,切空間距離,例：旋轉(zhuǎn)與細(xì)化的切空間,切空間距離,求x到x’的切空間距離,切空間距離,基于切空間距離的最近

21、鄰分類器通常具有很高的準(zhǔn)確率但是，切空間距離的計(jì)算要求設(shè)計(jì)者預(yù)先知道所有可能的變換，并且能夠在每個(gè)原型點(diǎn)（訓(xùn)練樣本點(diǎn)）上應(yīng)用這些變換，這一要求在實(shí)踐中有時(shí)無(wú)法滿足切空間距離的計(jì)算復(fù)雜度較高，在數(shù)據(jù)量較大時(shí)計(jì)算量可能無(wú)法忍受,小結(jié),kn-近鄰估計(jì),小結(jié),最近鄰規(guī)則直接估計(jì)后驗(yàn)概率誤差率誤差界,小結(jié),k-近鄰規(guī)則誤差界降低k-近鄰計(jì)算復(fù)雜度的方法計(jì)算部分距離預(yù)建立結(jié)構(gòu)對(duì)訓(xùn)練樣本加以剪輯,,如果 是在S中出現(xiàn)