針對(duì)基于Ball-tree結(jié)構(gòu)的KNN算法初始K個(gè)近鄰點(diǎn)位置固定,導(dǎo)致剪枝半徑過大,剪枝效果差,查詢效率低的問題,本文提出一種基于"雙樹"結(jié)構(gòu)的高維向量空間K近鄰快速搜索方法.在訓(xùn)練階段,將原始數(shù)據(jù)集按照8∶2比例劃分為訓(xùn)練集和測(cè)試集,利用隨機(jī)選擇方法共生成10組訓(xùn)練和測(cè)試集合,通過統(tǒng)計(jì)分析,得到最優(yōu)"雙樹"構(gòu)造參數(shù).利用最優(yōu)參數(shù)從原始數(shù)據(jù)點(diǎn)集合中過濾出極少量數(shù)據(jù)點(diǎn)構(gòu)成剪枝樹,過濾剩余數(shù)據(jù)點(diǎn)構(gòu)成被刪樹,剪枝樹需要最大限度地保留原始數(shù)據(jù)點(diǎn)集合在高維空間的分布形態(tài).在查詢階段,由于剪枝樹內(nèi)數(shù)據(jù)點(diǎn)個(gè)數(shù)很少,可以快速定位最近鄰點(diǎn),再利用這個(gè)近鄰點(diǎn)作為被刪樹的初始近鄰點(diǎn),在被刪樹內(nèi)搜索K近鄰.實(shí)驗(yàn)結(jié)果表明,由于初始近鄰點(diǎn)位置不再固定,而是位于待查點(diǎn)附近,有效縮小了剪枝半徑,改善了剪枝效果,提升了K近鄰查詢效率. 

【文章來源】：小型微型計(jì)算機(jī)系統(tǒng). 2020,41(11)北大核心CSCD

【文章頁(yè)數(shù)】：8 頁(yè)

【部分圖文】：

Node節(jié)點(diǎn)分裂過程及最短距離計(jì)算方法

根據(jù)KNN搜索算法1可知，無論待查點(diǎn)在多維空間什么位置，KNN＿result數(shù)組的初始值均為Ball-tree結(jié)構(gòu)最左側(cè)K個(gè)葉節(jié)點(diǎn)．這導(dǎo)致當(dāng)待查點(diǎn)距離初始K個(gè)葉節(jié)點(diǎn)較近時(shí)，剪枝效果好，查詢效率高，反之剪枝效果差，查詢效率低，下面通過實(shí)例分析．圖2顯示的是二維空間內(nèi)44個(gè)樣本點(diǎn)構(gòu)成的一棵Balltree結(jié)構(gòu)，待查點(diǎn)target在二維空間內(nèi)的坐標(biāo)位置為(80,400)，表1顯示的是target在二維空間內(nèi)5近鄰搜索過程．初始條件下Ball-tree最左側(cè)5個(gè)葉節(jié)點(diǎn)(即20,8,39,41,44)被填入KNN＿result數(shù)組，數(shù)組元素按照distance值降序排列．之后算法從左至右，逐個(gè)計(jì)算葉節(jié)點(diǎn)與target的空間距離，并與KNN＿result數(shù)組首個(gè)元素的distance值比較大小關(guān)系，動(dòng)態(tài)更新KNN＿result數(shù)組元素值，使其始終保存當(dāng)前的5個(gè)最近鄰．由于target距離初始5近鄰空間距離較近，剪枝效果好，查詢過程中Ball-tree整個(gè)右分枝子樹被剪枝，其包含33個(gè)樣本點(diǎn)．整個(gè)查詢過程只比較了11個(gè)樣本點(diǎn)與target的距離值即完成5近鄰搜索，查詢效率較高．

整數(shù)變量max＿points用于限定剪枝力度，增大該值將有更多的數(shù)據(jù)點(diǎn)被剪枝刪除，這一數(shù)值的確定需要經(jīng)過精確計(jì)算，以達(dá)到最佳效果，算法4用于確定這個(gè)變量的具體值．圖3顯示了對(duì)二維空間內(nèi)3960個(gè)樣本點(diǎn)進(jìn)行剪枝處理，調(diào)整剪枝數(shù)max＿points的剪枝效果比較，可見剪枝剩余樣本點(diǎn)密度不同，但均最大限度保留原始樣本點(diǎn)的基本形態(tài)，且離群點(diǎn)得到最大限度地保留．剪枝樹和被刪樹構(gòu)造算法2:reduce＿and＿pruned＿tree(node＿density,data,max＿points):

【參考文獻(xiàn)】：
期刊論文
[1]基于改進(jìn)K-modes聚類的KNN分類算法[J]. 王志華,劉紹廷,羅齊.  計(jì)算機(jī)工程與設(shè)計(jì). 2019(08)
[2]基于CUDA的KNN算法并行化研究[J]. 劉端陽(yáng),鄭江帆,劉志.  小型微型計(jì)算機(jī)系統(tǒng). 2019(06)
[3]基于改進(jìn)K最近鄰算法的中文文本分類[J]. 黃超,陳軍華.  上海師范大學(xué)學(xué)報(bào)(自然科學(xué)版). 2019(01)
[4]基于拉普拉斯機(jī)制的差分隱私保護(hù)k-means++聚類算法研究[J]. 傅彥銘,李振鐸.  信息網(wǎng)絡(luò)安全. 2019(02)
[5]基于BP神經(jīng)網(wǎng)絡(luò)決策的KNN改進(jìn)算法[J]. 路敦利,寧芊,臧軍.  計(jì)算機(jī)應(yīng)用. 2017(S2)
[6]粗糙集近似集的KNN文本分類算法研究[J]. 楊帥華,張清華.  小型微型計(jì)算機(jī)系統(tǒng). 2017(10)
[7]基于超球區(qū)域劃分的改進(jìn)KNN算法[J]. 郝衛(wèi)杰,王艷飛,胡敬偉,張公敬.  青島大學(xué)學(xué)報(bào)(自然科學(xué)版). 2017(01)
[8]基于訓(xùn)練集裁剪的加權(quán)K近鄰文本分類算法[J]. 孫新,歐陽(yáng)童,嚴(yán)西敏,尚煜茗,郭文浩.  情報(bào)工程. 2016(06)
[9]基于聚類改進(jìn)的KNN文本分類算法[J]. 周慶平,譚長(zhǎng)庚,王宏君,湛淼湘.  計(jì)算機(jī)應(yīng)用研究. 2016(11)
[10]基于密度的kNN文本分類器訓(xùn)練樣本裁剪方法[J]. 李榮陸,胡運(yùn)發(fā).  計(jì)算機(jī)研究與發(fā)展. 2004(04)



本文編號(hào)：3500432