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