武漢大學(xué)電子信息學(xué)院(編輯修改稿)
2025-08-15 20:51 本頁面
【文章內(nèi)容簡(jiǎn)介】 既減少計(jì)算量，又減少存儲(chǔ)量的雙重效果。 第五章 近鄰法 9 快速搜索近鄰法 ? 快速搜索近鄰法，包括兩個(gè)階段： 1. 樣本集的分級(jí)分解 2. 搜索 ? 其基本思想是將樣本集按鄰近關(guān)系 分解成組 ，給出每組的 質(zhì)心 所在，以及組內(nèi)樣本至該質(zhì)心的 最大距離 。這些組又可形成層次結(jié)構(gòu)，即組又分子組，因而待識(shí)別樣本可將搜索近鄰的范圍從某一大組，逐漸深入到其中的子組，直至樹的葉結(jié)點(diǎn)所代表的組，確定其相鄰關(guān)系。這種方法著眼于只解決減少計(jì)算量，但沒有達(dá)到減少存儲(chǔ)量的要求。 改進(jìn) 方法 第五章 近鄰法 10 樣本集的層次結(jié)構(gòu) ? 用樹結(jié)構(gòu)表示樣本分級(jí) : ? p: 樹中的一個(gè)結(jié)點(diǎn)，對(duì)應(yīng)一個(gè)樣本子集 Kp ? Np : Kp中的樣本數(shù) ? Mp : Kp中的樣本均值 ? rp : 從 Kp中任一樣本到 Mp的最大距離 第五章 近鄰法 11 減少計(jì)算的規(guī)則 ? 規(guī)則 1： 如果滿足： 則 Kp中的樣本都不可能是x的最近鄰， B是算法執(zhí)行中當(dāng)前到 x的最近距離 改進(jìn) 方法 ( , )ppD B r??xM( , ) ( , )p i pD B D??x M x M? 規(guī)則 2： 如果滿足： 則 xi不是 x的最近鄰 第五章 近鄰法 12 樹搜索算法 1. 置 B=∞， L=0， p=0 2. 將當(dāng)前結(jié)點(diǎn)的所有直接后繼結(jié)點(diǎn)放入一個(gè)目錄表中，并對(duì)這些結(jié)點(diǎn)計(jì)算 D(x,Mp) 3. 根據(jù)規(guī)則 1從目錄表中去掉 step2中的某些結(jié)點(diǎn) 4. 如果目錄表已無結(jié)點(diǎn)則置 L=L1， 如果 L=0則停止，否則轉(zhuǎn)
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1