ch 05 非參數(shù)方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、ski距離,d維空間中的Minkowski距離又稱為Lk范數(shù)L2范數(shù)——?dú)W幾里德距離L1范數(shù)——Manhattan距離（街區(qū)距離） 范數(shù)——a和b在d個坐標(biāo)軸上投影距離的最大值,Minkowski距離,到原點(diǎn)的等距離面,Mahalanobis距離,Mahalanobis距離（馬氏距離）在計算距離時考慮特征之間的協(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中的元素個數(shù)n12為兩個集合交集中的元素個數(shù)應(yīng)用場景兩個模式（特征）之間要么相同，要么不同，無法計算某種分級的相似度例如如兩個單詞之間的Tanimoto距離，可以將每個單詞看作一

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

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

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

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

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