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