【正文】 好平衡。 ? 缺點 – 要求樣本足夠多，才能有較好的估計。因此使計算量，存儲量增大。 – 窗寬在整個樣本空間固定不變，難以獲得區(qū)域自適應的密度估計。 識別方法 1. 保存每個類別所有的訓練樣本； 2. 選擇窗函數(shù)的形式，根據(jù)訓練樣本數(shù) n選擇窗函數(shù)的 h寬度； 3. 識別時，利用每個類別的訓練樣本計算待識別樣本 x的類條件概率密度： 4. 采用 Bayes判別準則進行分類。 ? ?111 i in jnijinp n V h??????????? x xx在 Parzen窗口法中存在一個問題是對 hN的選擇問題 。 若 hN選太小 ， 則大部分體積將是空的 （ 即不包含樣本 ）， 從而使 PN(x)估計不穩(wěn)定 。 若 hN選太大 ， 則 PN(x)估計較平坦 ， 反映不出總體分布的變化 ， 而 KN近鄰法的思想是以 x為中心建立空胞 ， 使 v↑， 直到捕捉到 KN個樣本為止 。 ∴ 稱 KN近鄰估計 v的改進 ， 樣本密度大 ， VN ↓。 樣本密度小 ， VN ↑。 ∴ P(x)的估計為： Nk N ?? 取,VNk( x)PNNNKN nearestneighbourhood approach 2) 在 x點周圍選擇一個體積 VN 3) 讓 VN不斷增長直至捕獲 kN個樣本為止 (這些樣本為 x的 kN個近鄰 ) ? 注意事項 : 1) kN不要增長太快 ,以使隨 N的增加捕獲 kN個樣本的體積 VN不致于縮小到 0 2) k1的選取要使 kN ≥ 1 ?kN近鄰法的基本估計公式 : NNN VNkxp ?)(?Nkk N 1??基本思想 : 1)讓 kN為 N的函數(shù) (例如 : , k1為大于 0的常數(shù) ) 使 PN(x)收斂于 P(x)的充分必要條件： ① ， N與 KN同向變化 ② ， KN的變化遠小于 N的變化 ③ ???? K NNlim0lim ??? NK NN))(11)()(( 111| VxPVV NKxPxP NNNN ????? ，所以因為V1為 N=1時的 VN值 NVNxPxPNNxPNKxPNKVNK NNNN N1)(1)()()( ?????時，＝當∴ KN近鄰估計對 KN和 VN都作了限制 ???????NVVNKNN1 N個樣本中有 KN個落入 VN內， KN個樣本內有 Ki個樣本屬于 ωi類 VNkxPNNN ?)()()|(),( ??? iiNiiN PxPvNkxP ??KN近鄰法作后驗概率的估計 由 KN近鄰估計知 :“ N個已知類別樣本中有 KN個落入 VN內” 的概率密度估計為： 則聯(lián)合概率密度： 根據(jù) Bayes公式可求出后驗概率： ????????MjjNiNNiiiiiiNxPxPPxPPxPxP11),(),()()|()()|()|(???????VNkxPxPNNMjjN ?? ?? 1),()( ?V NkxPNiiN ?),( ?kkxPNiiN ?)|( ?后驗概率的估計：∴ ∵ 類別為 ωi的后驗概率就是落在 VN內屬于 ωi的樣 本 ki與 VN內總樣本數(shù) KN的比值 K近鄰分類準則 ：對于待分樣本 x， 找出它的 k個近鄰，檢查它的類別，把 x歸于樣本最多的那個類別。 K近鄰分類的錯誤率隨 K↑ ， Pk↓, 最低的錯誤率為Bayes分類 。 P* PK 最近鄰分類準則 ：待分樣本 x， 找一個離它最近的樣本 ， 把 x歸于最近的樣本一類 。 Bayes MM 1?MM 1?P P(e) K近鄰 最近鄰 最近鄰分類法則的錯誤率 P比 K近鄰錯誤率還大 ，但最大不會超過貝葉斯分類器錯誤率的二倍。 M為類別數(shù) ,P(e)為 Bayes估計的錯誤率 )(2)](12)[()( ePePM MePPeP ?????錯誤率： References 1. Yingquan Wu―Improved knearest neighbor classification‖ Pattern Recognition 35 (2022) 2311–2318() 2. Marco Ramoni ‖Robust Bayes classifiers‖ Artificial Intelligence 125 (2022) 209~226() 多類分類器的設計 ?分段線性判別函數(shù)法（分段 LDA法） 第五章 非線性判別函數(shù) 分段線性判別函數(shù)法 利用線性判別函數(shù)設計 多類分類器有多種方法 . 例如，可以把 c類問題化 為 c1個兩類問題，其中 第 i個問題是用線性判別 函數(shù)把屬于類的點同不屬 于類的點分開， 見圖 (a)． ?問題的提出 多類分類器的設計 再麻煩一些的方法是用 c(c1)／ 2個線性判別函數(shù)，把樣本分為 c個類別，每個線性判別函數(shù)只對其中的兩個類別分類，如圖 (b)所示。 這兩種方法都會產(chǎn)生如圖中的陰影區(qū)域，對這個陰影區(qū)域中的點，無法確定其類別。 ?分段線性判別函數(shù)的基本概念 多類分類器的設計 ?用分段線性判別函數(shù)解決問題的思路 1) 在各類中取 若干 個代表點（例 wi類就取 li個代表點），代表點可以是 wi類樣本的均值，也可以是屬于 wi類的樣本 2) 將 wi類劃分為 li個子類 ,每個 子類包含 1個代表點 3) 每個 子類定義一個判別函數(shù) 多類分類器的設計 4) 定義 wi類判別函數(shù) 5) 決策規(guī)則： 6) 決策面方程： 多類分類器的設計 ?解決問題的關鍵 1. 如何確定各類的子類數(shù)目 li? 2. 如何求各子類的判別函數(shù) ? ? ?xgki多類分類器的設計 多類分類器的設計 多類分類器的設計 分段線性分類器設計的一般考慮 設計線性分類器，就是確定權向量 ω 和閥值權 或廣義權向量 α 。 而設計分段線性分類器，則是利用樣本集確定一組 和 1) 已知樣本的子類劃分情況 : 把子類看作獨立的類，然后利用線性判別函數(shù)算法把各個子類分開，自然也就把各類分開了．這種方法必須以已知子類劃分 為前提．劃分子類的一種方法是根據(jù)先驗知識直觀判定 . 如字符識別中，可把同一字符看作一類，而把其中不同的字體看作它的不同于類．另一種方法則借助于聚類分析方法來解決。 ?0?li ?li0多類分類器的設計 2) 已知子類數(shù)目 li ，但不知子類劃分情況時 3) 未知子類數(shù)目 (這是一般的情況 ) 在這種情況下 ,設計分段線性分類器的方法很多 ,在這里我們僅舉一例 :樹狀分段線性分類器 . 對于圖 情況 ,先用兩類線性判別函數(shù)算法找一個權向量 α 1，它所對應的超平面 H1把整個樣本集分成兩部分 ,我們稱之為樣本子集 .由于樣本集不是線性可分的 ,因而每一部分仍然包含兩類樣本 .接著 ,再利用算法找出第二個權向量 α 2,第三個權向量 α 3 超平面 H2 ,H3分別把相應的樣本子集分成兩部分 .若每一部分仍然包含兩類樣本 ,則繼續(xù)上述過程 ,直到某一權向量 (如圖中 α 4 )把兩類樣本完全分開為止 .這樣得到的分類器顯然也是分段線性的，其決策面如圖中粗線所示 . 表示權向量 α i方向 ,它指向超平面Hi的正側 .它的識別過程是一個樹狀結構 ,如圖 .圖中用虛線顯示了對未知樣本 y的決策過程，經(jīng)過三步，判斷 y∈ w1。 多類分類器的設計 需要指出 ,這種方法對初始權向量的選擇很敏感，其結果隨初始權向量的不同而大不相同 .此外，在每個節(jié)點上所用的尋找權向量 αi的方法不同 .結果也將各異 .通?？梢赃x擇 分屬兩類的歐氏距離最小的一對樣本 ，取其垂直平分面的法向量作為 α1的初始值．然后求得局部最憂解 α1*作為第一段超平面的法向量．對包含兩類樣本的各子類的劃分也可以采用同樣的方法 ． 凹函數(shù)的并 的分段線性判別函數(shù)（針對多峰情況 ） 設 Li為線性判別函數(shù)， i=1,2,… ..r則： ?(a)： L1,L2,…… Lr都是分段線性判別函數(shù) ?(b)： 若 A,B都是分段線性判別函數(shù)，則： A∧B ， A∨B 也是分段線性判別函數(shù)。 A∧B 取最小 ， A∨B 取最大。 ?(c)： 對任何分段線性函數(shù)都可以表示成如下二種形式： 1)、析取范式 (這是經(jīng)常采用的形式 ) P=(L11∧L 12∧…∧L 1m)∨…∨(L q1∧L q2∧…∧L qm) 2)、 合取范式 Q=(L11∨L 12∨…∨L 1m)∧…∧(L q1∨L q2∨…∨L qm) 每個 (Li1 ∧ Li2 ∧ … ∧ Lim) 都稱為凹函數(shù)。 ??????????。每個子類的判別函數(shù)數(shù)子類。mjxqixxwL ijij, . . . ,2,1,0, . . . ,2,1,021???對于多峰二類問題：設第一類有 q個峰，則有 q個凹函數(shù)。 ?即 P=P1∨ P2∨ …… ∨ Pq ?每個凹函數(shù) Pi由 m 個線性判別函數(shù)來構成。 ?∴ Pi=Li1∧ Li2∧ … ∧ Lim ?假設對于每個子類線性判別函數(shù) Lij都設計成： ???????21,0,0??xPxP則則判別規(guī)則：?例、設如圖 個分段判別函數(shù)有判別函數(shù)個數(shù)：這樣它有三個子類。分三個峰，1344533211??????????mmmq?? ?。則。若則若 2134312421151211,0,0),...,m i n (),...,m i n (),...,m i n (m ax?? ??????xPxPlllllllP15l11l12l13l14l22l24l23l21l34l33l32l31l11?21?31?2??∴ P=(L11∧ L12∧ L13 ∧ L14 ∧ L15) ∨ (L21∧ L22∧ L23 ∧ L24) ∨ (L31∧ L32∧ L33 ∧ L34) 用交遇區(qū)的樣本設計分段線性分類器 一種實現(xiàn)最少分段線性分類器的方法 ? 交遇區(qū) 當兩類樣本非線性可分時 ,貝葉 斯分界面一般通過兩類樣本十分 靠近或相互交迭的區(qū)域 ,我們稱 之為 “ 交遇區(qū) ” ,如圖 . 其中 a,c是交迭區(qū) ,b是靠近區(qū) ? 局部訓練法 把這些區(qū)域找出來，利用這些 區(qū)域中的樣本作為新的樣本集 設計線性判別函數(shù)，然后把它 們連在一起，就構成了一個分 段線性判別函數(shù) . 這種方法稱 為 “ 局部訓練法 ” 多類分類器的設計 (1)如何從樣本集中找出 “ 交遇區(qū) ” ； (2)如何利用 “ 交遇區(qū) ” 中的樣本設計線性分類 器； (3)如何進行分類決策。 多類分類器的設計 需要解決的問題 : prototype 出來類中各取一個和 p r o t o t y p eji ??相距最近的一對?；υ蛯现?， 二次判別函數(shù) ?二次判別函數(shù)一般可表示成： 計算量很大）非常復雜的系數(shù)一共有維權向量為維的權向量。是其中：,(1)3(21)(n2)(11 1 10120???????????? ? ???? ?? ??nnlxgWnnWWxwxxwxwWXWXWXxgnj