徐 國 天

(中國刑事警察學(xué)院 網(wǎng)絡(luò)犯罪偵查系，沈陽 110854)

1 引 言

K近鄰(K Nearest Neighbor，KNN) 算法是指給定一個(gè)待查點(diǎn)，在多維向量空間樣本點(diǎn)集合內(nèi)查找與待查點(diǎn)最接近的K個(gè)樣本點(diǎn)，如果這K個(gè)樣本點(diǎn)中的大多數(shù)屬于某一類別，則待查點(diǎn)也屬于這一類別[1].K近鄰搜索在很多數(shù)據(jù)分析問題中得到廣泛應(yīng)用，例如機(jī)器學(xué)習(xí)、地理信息系統(tǒng)、人工智能，等領(lǐng)域.在面對(duì)高維、海量樣本集合時(shí)，因需要與大量樣本點(diǎn)計(jì)算和比較空間距離，造成計(jì)算量大，查詢速度慢的問題，影響了KNN算法的實(shí)踐應(yīng)用.

針對(duì)KNN算法計(jì)算量大、查詢效率低的問題，目前主要有以下改進(jìn)方向：1)對(duì)樣本集進(jìn)行裁剪.例如文獻(xiàn)[2]通過對(duì)樣本集進(jìn)行分析，從中剔除冗余元素，縮小樣本集合，進(jìn)而減少K近鄰搜索階段的計(jì)算量.但在面向高維、海量樣本集時(shí)，樣本集合縮減規(guī)模有限，仍面臨計(jì)算量大的缺陷；2)采用并行計(jì)算架構(gòu)提升K近鄰查詢速度.文獻(xiàn)[3]提出一種基于CUDA模型的并行KNN算法，采用通用矩陣乘提升距離計(jì)算速度，根據(jù)K值大小，分別采用兩種方法對(duì)距離進(jìn)行比較，這一并行計(jì)算方法有效提高了K近鄰查詢效率；3)采用空間分區(qū)數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)K近鄰快速搜索.對(duì)樣本點(diǎn)集合按照特定的幾何形態(tài)進(jìn)行劃分，同時(shí)構(gòu)造搜索二叉樹，在K近鄰查找階段，通過比較空間距離，對(duì)二叉樹進(jìn)行剪枝處理，減少需要計(jì)算和比較距離的樣本點(diǎn)數(shù)量，進(jìn)而加快K近鄰查詢速度.常見的空間分區(qū)數(shù)據(jù)結(jié)構(gòu)包括Metric-tree，Ball-tree，Cover-tree，VP-tree，MVP-tree，R-tree和KD-tree[4].各種空間分區(qū)數(shù)據(jù)結(jié)構(gòu)主要在以下三個(gè)方面存在區(qū)別，第一：分區(qū)的幾何形狀；第二：建立搜索樹的空間劃分策略；第三：利用數(shù)據(jù)結(jié)構(gòu)進(jìn)行搜索的策略[5].Ball-tree結(jié)構(gòu)采用超球體對(duì)數(shù)據(jù)集進(jìn)行劃分，在K近鄰查詢方面有更多的優(yōu)勢(shì)，因此得到廣泛應(yīng)用.但是基于Ball-tree結(jié)構(gòu)的K近鄰算法初始K個(gè)近鄰點(diǎn)位置固定，即Ball-tree結(jié)構(gòu)最左側(cè)K個(gè)葉節(jié)點(diǎn)，如待查點(diǎn)距離初始K個(gè)近鄰點(diǎn)空間距離較近，則剪枝效果好，會(huì)有更多的數(shù)據(jù)點(diǎn)被剪枝濾除，進(jìn)而獲得更快的K近鄰查詢速度.但當(dāng)待查點(diǎn)距離初始K個(gè)近鄰點(diǎn)較遠(yuǎn)時(shí)，剪枝半徑過大，剪枝效果差，僅有少量數(shù)據(jù)點(diǎn)被剪枝濾除，K近鄰查詢速度降低，在面對(duì)高維、海量樣本集時(shí)，這一缺點(diǎn)尤為明顯.

針對(duì)Ball-tree結(jié)構(gòu)K近鄰搜索算法初始K個(gè)近鄰點(diǎn)位置固定導(dǎo)致的查詢效率較低問題，本文提出一種基于“雙樹”結(jié)構(gòu)的K近鄰搜索方法.這種方法從原始數(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近鄰.由于初始近鄰點(diǎn)位置不再固定，而是位于待查點(diǎn)附近，有效縮小了剪枝半徑，改善了剪枝效果，提升了K近鄰查詢效率.

2 基于Ball-tree結(jié)構(gòu)的K近鄰搜索方法

Ball-tree是多維向量空間內(nèi)全部樣本點(diǎn)按照一定規(guī)則構(gòu)成的一棵二叉樹，每棵子樹對(duì)應(yīng)一個(gè)子超球體，包含若干個(gè)樣本點(diǎn).在K近鄰查詢階段，從根節(jié)點(diǎn)開始對(duì)Ball-tree進(jìn)行遍歷搜索，通過計(jì)算待查點(diǎn)和每棵子樹超球體質(zhì)心的空間距離，實(shí)現(xiàn)對(duì)子樹的快速剪枝，進(jìn)而加快檢索進(jìn)程.

2.1 Ball-tree構(gòu)造方法

本文研究的Ball-tree結(jié)構(gòu)由Moore提出.Ball-tree的構(gòu)造過程如下，初始條件下，多維向量空間內(nèi)全部樣本點(diǎn)構(gòu)成一個(gè)最小超球體(對(duì)于二維空間，即是最小圓)，這個(gè)超球體就是Ball-tree的根節(jié)點(diǎn)root.之后按照一定原則將全部樣本點(diǎn)劃分為兩部分，構(gòu)造成兩個(gè)最小子超球體，這兩個(gè)子超球體分別是root節(jié)點(diǎn)的左右子樹根節(jié)點(diǎn)，這個(gè)分裂過程持續(xù)進(jìn)行下去，直至每個(gè)子超球體內(nèi)只包含1個(gè)樣本點(diǎn)或半徑極小時(shí)停止分裂，Ball-tree構(gòu)建成功.本文采用加權(quán)空間歐氏距離作為多維向量空間內(nèi)樣本點(diǎn)之間的距離計(jì)算公式.

Ball-tree內(nèi)每個(gè)Node點(diǎn)包括五個(gè)重要屬性，質(zhì)心pivot(即子超球體的圓心)；半徑radius，滿足公式(1)；樣本點(diǎn)集合points(即子超球體內(nèi)全部樣本點(diǎn)數(shù)據(jù)集)；Child1和Child2分別是Node節(jié)點(diǎn)的左右子樹根節(jié)點(diǎn)，如果Node是非葉節(jié)點(diǎn)，則滿足公式(2)和公式(3).

(1)

(Node.Child1.points)∩(Node.Child2.points)=?

(2)

Node.Child1.points∪Node.Child2.points=Node.points

(3)

Ball-tree內(nèi)每個(gè)Node節(jié)點(diǎn)的分裂原則如下：首先計(jì)算子超球體內(nèi)距離質(zhì)心最遠(yuǎn)的樣本點(diǎn)point1，再計(jì)算距離point1最遠(yuǎn)的樣本點(diǎn)point2，將全部樣本點(diǎn)集合points劃分為兩個(gè)子集Child1和Child2，其中距離point1更近的樣本點(diǎn)被劃分到Child1集合，距離point2更近的樣本點(diǎn)被劃分到Child2集合[6]，節(jié)點(diǎn)分裂原則可用公式(4)描述.

x∈Node.Child1.points|x-point1|<|x-point2|
x∈Node.Child2.points|x-point2|≤|x-point1|

(4)

圖1展示了Node1節(jié)點(diǎn)的分裂過程，二維空間內(nèi)7個(gè)樣本點(diǎn)A-G構(gòu)成一個(gè)最小圓，即Ball-tree中的Node1節(jié)點(diǎn).距離質(zhì)心最遠(yuǎn)的是A點(diǎn)，距離A最遠(yuǎn)的是B點(diǎn)，A和B點(diǎn)之間的超平面將全部7個(gè)樣本點(diǎn)劃分為兩個(gè)子集Child1和Child2，這兩個(gè)子集又構(gòu)成兩個(gè)最小子圓，即Node1節(jié)點(diǎn)的左右子樹根節(jié)點(diǎn).

圖1 Node節(jié)點(diǎn)分裂過程及最短距離計(jì)算方法Fig.1 Node splitting and shortest distance calculation

2.2 K近鄰搜索算法

多維空間內(nèi)待查點(diǎn)p與Node節(jié)點(diǎn)內(nèi)任意樣本點(diǎn)x的空間距離滿足公式(5)和公式(6).下面進(jìn)行簡(jiǎn)單證明，根據(jù)三角不等式可以得到|x-p|≥|p-Node.pivot|-|x-Node.pivot|,給定x∈Node.points，滿足|x-Node.pivot|≤Node.radius，因此可證明公式(5)成立，同理可證明公式(6)成立[7].

|x-p|≥|p-Node.pivot|-Node.radius

(5)

|x-p|≤|p-Node.pivot|+Node.radius

(6)

公式(7)中root為Ball-tree結(jié)構(gòu)根節(jié)點(diǎn)，Dmin pChild1為待查點(diǎn)p與Child1節(jié)點(diǎn)最小可能空間距離計(jì)算公式，這是根據(jù)公式(5)給出的邊界限定以及子節(jié)點(diǎn)內(nèi)所有樣本點(diǎn)必須被其父節(jié)點(diǎn)覆蓋這一事實(shí)得出的.這個(gè)性質(zhì)意味著Dmin pChild1永遠(yuǎn)不會(huì)小于其祖先的最小距離Dmin pNode.圖1顯示了Dmin pNode1.Child1的計(jì)算過程，經(jīng)過比較確定待查點(diǎn)p到Node1節(jié)點(diǎn)的最小距離Dmin pNode1作為p到Node1.Child1節(jié)點(diǎn)的最小距離值[8].

(7)

在查詢階段，利用公式(7)可實(shí)現(xiàn)對(duì)子樹的快速剪枝，加快檢索進(jìn)程.如圖1所示，當(dāng)前距離待查點(diǎn)p的最近鄰點(diǎn)是H，由于Dmin pNode1>|p-H|[9]，因此Node1節(jié)點(diǎn)內(nèi)的全部7個(gè)樣本點(diǎn)均被剪枝過濾，不需要逐個(gè)計(jì)算與p點(diǎn)的空間距離，并比較與|p-H|的大小關(guān)系[10]，因此可以加快檢索進(jìn)程.由于Dmin pNode2<|p-H|,因此需要對(duì)Node2節(jié)點(diǎn)內(nèi)的3個(gè)樣本點(diǎn)逐一計(jì)算與p的空間距離，比較與|p-H|大小關(guān)系[11]，經(jīng)過三次比較，確定樣本點(diǎn)M為待查點(diǎn)p的最新近鄰點(diǎn).

基于Ball-tree結(jié)構(gòu)的K近鄰遞歸搜索算法1：search_KNN(KNN_result,node,target,K)[12].

輸入?yún)?shù)：當(dāng)前最近鄰數(shù)組KNN_result，首次調(diào)用時(shí)為空數(shù)組；當(dāng)前處理節(jié)點(diǎn)node，首次調(diào)用時(shí)為Ball-tree根節(jié)點(diǎn)；待查點(diǎn)target；待查最近鄰個(gè)數(shù)K.

輸出參數(shù)：待查點(diǎn)target的K個(gè)最近鄰數(shù)據(jù)點(diǎn).

Step 1.如果當(dāng)前處理節(jié)點(diǎn)node為空，則執(zhí)行Step 7，否則執(zhí)行Step 2.

Step 2.如果當(dāng)前處理節(jié)點(diǎn)node為葉子節(jié)點(diǎn)，則執(zhí)行Step 3，否則執(zhí)行Step 4.

Step 3.令node節(jié)點(diǎn)的全部n個(gè)數(shù)據(jù)點(diǎn)組成集合S，S={S1,S2,…,Sn}，其中Si為node節(jié)點(diǎn)的第i個(gè)數(shù)據(jù)點(diǎn).依次取出集合S中的每個(gè)數(shù)據(jù)點(diǎn)Si，計(jì)算待查點(diǎn)target與數(shù)據(jù)點(diǎn)Si之間的空間距離distance；令整數(shù)變量len為最近鄰數(shù)組KNN_result的元素個(gè)數(shù)，如果len=K，則比較distance與KNN_result[0][1]的大小，KNN_result[0][1]為KNN_result數(shù)組首個(gè)元組的distance值，如果distance=KNN_result[0][1]，則不更新KNN_result數(shù)組.

Step 4.令當(dāng)前處理node節(jié)點(diǎn)對(duì)應(yīng)的球半徑為radius，對(duì)應(yīng)的質(zhì)心點(diǎn)為center，質(zhì)心點(diǎn)center與待查點(diǎn)target的空間距離為distance_c，如果|distance_c|>radius+KNN_result[0][1]，則執(zhí)行Step 7，即當(dāng)前節(jié)點(diǎn)內(nèi)不可能存在待查點(diǎn)target的K近鄰數(shù)據(jù)點(diǎn)，當(dāng)前節(jié)點(diǎn)node對(duì)應(yīng)的整棵子樹被剪枝過濾.如果|distance_c|<=radius+KNN_result[0][1]，則執(zhí)行Step 5，即當(dāng)前節(jié)點(diǎn)內(nèi)可能存在待查點(diǎn)target的K近鄰數(shù)據(jù)點(diǎn)，需要分別處理node節(jié)點(diǎn)的左右子樹.

Step 5.令當(dāng)前節(jié)點(diǎn)node的左子樹根節(jié)點(diǎn)為node.child1，遞歸調(diào)用K近鄰搜索算法search_KNN(KNN_result,node.child1,target,K)處理node節(jié)點(diǎn)的左子樹.

Step 6.令當(dāng)前節(jié)點(diǎn)node的右子樹根節(jié)點(diǎn)為node.child2，遞歸調(diào)用K近鄰搜索算法search_KNN(KNN_result,node.child2,target,K)處理node節(jié)點(diǎn)的右子樹.

Step 7.算法結(jié)束，返回當(dāng)前KNN_result.

2.3 查詢效率分析

根據(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 Ball-tree實(shí)例Fig.2 Ball-tree instance

圖2顯示的是二維空間內(nèi)44個(gè)樣本點(diǎn)構(gòu)成的一棵Ball-tree結(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近鄰搜索，查詢效率較高.

表1 理想情況下，基于Ball-tree結(jié)構(gòu)的KNN搜索實(shí)例Table 1 Best KNN search case based on Ball-tree

表2所示例子中，待查點(diǎn)target在二維空間的位置為[66,212]，這個(gè)位置距離Ball-tree結(jié)構(gòu)最左側(cè)5個(gè)葉節(jié)點(diǎn)，即初始5近鄰較遠(yuǎn)，整個(gè)查詢過程中剪枝效果較差，只進(jìn)行了兩次剪枝操作，共包括10個(gè)樣本點(diǎn).經(jīng)過與34個(gè)葉節(jié)點(diǎn)比較空間距離，完成5近鄰搜索，查詢效率較低.

造成原始Ball-tree結(jié)構(gòu)K近鄰搜索算法查詢效率較低的原因如下：當(dāng)KNN_result數(shù)組中元素個(gè)數(shù)不足K個(gè)時(shí)，將最先處理的葉節(jié)點(diǎn)存入KNN_result數(shù)組，使其元素個(gè)數(shù)盡快達(dá)到K個(gè)，之后不斷用更優(yōu)的近鄰點(diǎn)更新KNN_result數(shù)組，直至算法結(jié)束.這個(gè)原始算法的主要缺點(diǎn)在于不論待查點(diǎn)target位于多維空間什么位置，KNN_result數(shù)組中初始K個(gè)數(shù)據(jù)點(diǎn)均是固定的，即Ball-tree結(jié)構(gòu)最左側(cè)K個(gè)葉子節(jié)點(diǎn).在多維空間內(nèi)，待查點(diǎn)target的位置是隨機(jī)變化的，而每個(gè)target點(diǎn)的初始K個(gè)近鄰點(diǎn)均是固定的，這K個(gè)初始近鄰點(diǎn)很可能距離目標(biāo)target較遠(yuǎn)，使用這K個(gè)初始近鄰點(diǎn)對(duì)Ball-tree進(jìn)行剪枝，因剪枝距離過大，很難達(dá)到理想的剪枝效果.如果能在待查點(diǎn)target附近快速找到一組相對(duì)近鄰點(diǎn)，并用這組數(shù)據(jù)點(diǎn)作為初始近鄰點(diǎn)對(duì)Ball-tree進(jìn)行剪枝，因剪枝距離縮短，將有更多的子樹被剪枝濾除，減少空間距離計(jì)算和大小比較次數(shù)，進(jìn)而提高整體查詢效率.

表2 非理想情況下，基于Ball-tree結(jié)構(gòu)的KNN搜索實(shí)例Table 2 Worst KNN search case based on Ball-tree

3 基于“雙樹”結(jié)構(gòu)的K近鄰搜索方法

針對(duì)原始Ball-tree結(jié)構(gòu)初始K近鄰點(diǎn)位置固定帶來的查詢效率較低問題，本文提出一種基于“雙樹”結(jié)構(gòu)的K近鄰搜索方法，首先從原始數(shù)據(jù)點(diǎn)集合中過濾出極少量數(shù)據(jù)點(diǎn)組成剪枝點(diǎn)集合，過濾剩余數(shù)據(jù)點(diǎn)組成被刪點(diǎn)集合.過濾原則是剪枝點(diǎn)集合中數(shù)據(jù)點(diǎn)需要最大限度地保留原始數(shù)據(jù)點(diǎn)集合在多維空間中的分布形態(tài)，這樣待查點(diǎn)在剪枝點(diǎn)集合中的最近鄰點(diǎn)與待查點(diǎn)在完整集合中的第K個(gè)近鄰點(diǎn)非常接近.利用剪枝點(diǎn)集合構(gòu)成剪枝樹(reduce-tree)，利用被刪點(diǎn)集合構(gòu)成被刪樹(pruned-tree)，由于剪枝點(diǎn)集合中數(shù)據(jù)點(diǎn)個(gè)數(shù)很少，因此可以在剪枝樹(reduce-tree)內(nèi)快速定位最近鄰點(diǎn)，再利用這個(gè)近鄰點(diǎn)作為初始近鄰點(diǎn)，在被刪樹(pruned-tree)和完整樹(Ball-tree)內(nèi)搜索K近鄰，由于不同的待查點(diǎn)target，初始近鄰點(diǎn)均在target附近，因此可以加快剪枝速度，提升整體查詢效率.

3.1 剪枝樹reduce-tree和被刪樹pruned-tree構(gòu)造方法

在原始Ball-tree構(gòu)造算法中增加一步處理，對(duì)每棵子樹信息進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)結(jié)果存入node_density數(shù)組.node_density數(shù)組中每個(gè)元素對(duì)應(yīng)一棵子樹的統(tǒng)計(jì)信息，統(tǒng)計(jì)信息包括這棵子樹內(nèi)數(shù)據(jù)點(diǎn)個(gè)數(shù)，即葉節(jié)點(diǎn)個(gè)數(shù)point_num，這棵子樹對(duì)應(yīng)的超球體半徑radius，這棵子樹對(duì)應(yīng)的數(shù)據(jù)點(diǎn)集合points.數(shù)組元素按照每棵子樹內(nèi)數(shù)據(jù)點(diǎn)個(gè)數(shù)point_num降序排列，point_num值相同的元素，按照半徑radius升序排列.

“雙樹”構(gòu)造算法2的基本思想是對(duì)數(shù)據(jù)點(diǎn)個(gè)數(shù)point_num

整數(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)得到最大限度地保留.

圖3 max_points值對(duì)剪枝效果的影響Fig.3 Effect of max_points on pruning effect

剪枝樹和被刪樹構(gòu)造算法2：reduce_and_pruned_tree(node_density,data,max_points)：

輸入?yún)?shù)：待剪枝的數(shù)據(jù)點(diǎn)集合data；存儲(chǔ)每棵子樹統(tǒng)計(jì)信息的node_density數(shù)組，數(shù)組元素按照每棵子樹內(nèi)數(shù)據(jù)點(diǎn)個(gè)數(shù)point_num降序排列，point_num值相同的元素，按照半徑radius升序排列；整數(shù)變量max_points表示最大剪枝點(diǎn)數(shù)，其初始值由算法4確定；

輸出參數(shù)：一棵由被刪除數(shù)據(jù)點(diǎn)構(gòu)造的被刪樹pruned_tree，一棵由剪枝剩余數(shù)據(jù)點(diǎn)構(gòu)造的剪枝樹reduce_tree.

Step 1.令pruned_tree數(shù)組存儲(chǔ)被刪除數(shù)據(jù)點(diǎn)，初值為空；令reduce_tree數(shù)組存儲(chǔ)剪枝剩余數(shù)據(jù)點(diǎn)，初值為空；

Step 2.將node_density數(shù)組中數(shù)據(jù)點(diǎn)個(gè)數(shù)point_num>=max_points的全部元素構(gòu)成集合T，T={T1,T2,…,Tn}.按照數(shù)據(jù)點(diǎn)個(gè)數(shù)將子樹分類，定義實(shí)數(shù)變量avg_max_radius表示已經(jīng)剪枝的每棵子樹的最大半徑平均值，初值為T1.radius；定義整數(shù)變量current_point_num表示當(dāng)前處理的這類子樹數(shù)據(jù)點(diǎn)個(gè)數(shù)，初值為T1.point_num.定義實(shí)數(shù)變量previous_radius表示前一棵子樹對(duì)應(yīng)球體的半徑，初值為T1.radius.定義整數(shù)變量i，初值為2.

Step 3.從集合T中取出元組Ti，如果Ti.point_num!=current_point_num，即當(dāng)前這類子樹處理完畢，則執(zhí)行Step 6，否則執(zhí)行Step 4.

Step 4.如果abs(Ti.radius-previous_radius)<=2或者Ti.radius

Step 5.令center為數(shù)據(jù)點(diǎn)集Ti.points的質(zhì)心，min_dist_point為點(diǎn)集Ti.points中距離質(zhì)心center最近的點(diǎn)，令pruned_tree=pruned_tree∪(Ti.points-min_dist_point)，即將Ti.points中除min_dist_point之外的其它數(shù)據(jù)點(diǎn)并入pruned_tree數(shù)組.令previous_radius=Ti.radius，同時(shí)更新avg_max_radius值.令i=i+1，如果i<=len(T)，則執(zhí)行Step 3，否則執(zhí)行Step 7.

Step 6.令current_point_num=Ti.point_num，更新當(dāng)前處理的這類子樹的數(shù)據(jù)點(diǎn)計(jì)數(shù)current_point_num，執(zhí)行Step 5.

Step 7.令reduce_tree=data-pruned_tree，執(zhí)行Ball_tree(pruned_tree)構(gòu)建全部被刪數(shù)據(jù)點(diǎn)構(gòu)成的被刪樹，執(zhí)行Ball_tree(reduce_tree)構(gòu)建全部剪枝剩余數(shù)據(jù)點(diǎn)構(gòu)成的剪枝樹，算法結(jié)束.

圖4顯示的是圖2所示44個(gè)樣本點(diǎn)按照算法2構(gòu)造成的reduce-tree結(jié)構(gòu)，max_points值設(shè)置為10，剪枝剩余16個(gè)樣本點(diǎn)，圖5是按照算法2構(gòu)造的pruned-tree結(jié)構(gòu).表3顯示的是一段局部剪枝過程，前三棵子樹均有五個(gè)葉節(jié)點(diǎn)，且都符合剪枝條件，每棵子樹只保留距離子球體質(zhì)心最近的數(shù)據(jù)點(diǎn)，其余四個(gè)數(shù)據(jù)點(diǎn)被刪除.第四棵子樹與前一棵子樹球體半徑差為6.258964，大于臨界值，且球體半徑大于全部已剪枝子樹球體半徑均值，因此不予剪枝處理，這棵子樹全部5個(gè)葉節(jié)點(diǎn)(2,4,10,11,33)予以保留.但在后面處理過程中，這棵子樹的左右孩子，即葉節(jié)點(diǎn)數(shù)分別為3和2的兩棵子子樹符合剪枝處理?xiàng)l件，最終只有(11，2)兩個(gè)葉節(jié)點(diǎn)予以保留，其余三個(gè)葉節(jié)點(diǎn)(4,10,33)被剪枝刪除.這個(gè)過程體現(xiàn)了最大限度保留原始樣本點(diǎn)空間形態(tài)這一思想.

圖4 Reduce-tree實(shí)例Fig.4 Reduce-tree instance

圖5 Pruned-tree實(shí)例Fig.5 Pruned-tree instance

表3 剪枝處理過程實(shí)例Table 3 Examples of pruning process

3.2 利用“雙樹”結(jié)構(gòu)查找K近鄰

本文提出的“雙樹”結(jié)構(gòu)K近鄰搜索方法需要調(diào)用原始Ball-tree結(jié)構(gòu)K近鄰搜索算法，但是需要對(duì)原始算法進(jìn)行兩點(diǎn)改進(jìn)，改進(jìn)算法名為search_KNN_Improve，傳入?yún)?shù)與原始算法相同.第一點(diǎn)改進(jìn)是原始算法中KNN_result數(shù)組初始值為空，改進(jìn)算法的KNN_result數(shù)組初始預(yù)置一個(gè)近鄰值，這個(gè)近鄰值是待查點(diǎn)target在剪枝樹中定位的一個(gè)近鄰值.第二點(diǎn)是對(duì)原始算法的Step 3進(jìn)行了改造，原始算法是當(dāng)KNN_result數(shù)組元素個(gè)數(shù)不足K個(gè)時(shí)，會(huì)盡快將其補(bǔ)充為K個(gè)，這容易導(dǎo)致KNN_result數(shù)組初始K個(gè)元素值過大，剪枝效果差.改造之后不再強(qiáng)制要求KNN_result數(shù)組必須達(dá)到K個(gè)元素，由于KNN_result數(shù)組元素按照空間距離值distance降序排列，只要當(dāng)前處理樣本點(diǎn)與待查點(diǎn)target的空間距離值小于KNN_result[0].distance，即將當(dāng)前數(shù)據(jù)點(diǎn)加入KNN_result數(shù)組，當(dāng)數(shù)組元素個(gè)數(shù)大于K時(shí)，將KNN_result[0]元素刪除，更新之后仍然保證KNN_result數(shù)組元素按照distance值降序排列.如果KNN_result數(shù)組中初始近鄰值略大于待查點(diǎn)的第K個(gè)近鄰值，將產(chǎn)生最佳的剪枝效果，如果初始近鄰值設(shè)置過小，算法最終運(yùn)行之后，KNN_result中元素個(gè)數(shù)可能不足K個(gè).因此如何確定KNN_result數(shù)組中的初始近鄰值以產(chǎn)生最佳的剪枝效果是一個(gè)關(guān)鍵問題.

基于“雙樹”結(jié)構(gòu)的K近鄰搜索算法3的基本思想是先在剪枝樹內(nèi)調(diào)用原始K近鄰算法search_KNN()查找待查點(diǎn)target的K_g個(gè)近鄰點(diǎn)，其中1≤K_g≤K.之后分別用第1個(gè)和第K_g個(gè)近鄰點(diǎn)作為被刪樹的初始近鄰點(diǎn)，調(diào)用改進(jìn)算法search_KNN_improve()在被刪樹內(nèi)查找target的K個(gè)近鄰點(diǎn)，如找到的近鄰個(gè)數(shù)不足K個(gè)，則將最近鄰數(shù)組置空，調(diào)用原始算法search_KNN()在Ball-tree結(jié)構(gòu)內(nèi)查找target的K個(gè)近鄰點(diǎn).通過算法4確定K_g的最佳值，使得絕大部分待查點(diǎn)在剪枝樹和被刪樹內(nèi)即可找到K個(gè)最近鄰，同時(shí)由于設(shè)置了初始近鄰點(diǎn)，查詢過程中，將有更多分枝被剪枝過濾，查詢速度進(jìn)一步提高.

“雙樹”結(jié)構(gòu)K近鄰遞歸搜索算法3：search_KNN_IN_double_tree(ball_tree,pruned_tree,reduce_tree,target,K,K_g)：

輸入?yún)?shù)：原始ball_tree根節(jié)點(diǎn)；被刪樹pruned_tree根節(jié)點(diǎn)；剪枝樹reduce_tree根節(jié)點(diǎn)；待查點(diǎn)target；待查最近鄰個(gè)數(shù)K；剪枝樹內(nèi)待查最近鄰個(gè)數(shù)K_g.

輸出參數(shù)：待查點(diǎn)的K個(gè)最近鄰數(shù)據(jù)點(diǎn).

Step 1.調(diào)用原始單樹結(jié)構(gòu)K近鄰搜索算法reduce_tree.search_KNN()，確定待查點(diǎn)target在剪枝樹內(nèi)的K_g個(gè)近鄰點(diǎn)，找到的K_g個(gè)近鄰點(diǎn)存儲(chǔ)在reduce_tree.KNN_result數(shù)組內(nèi).

Step 2.將待查點(diǎn)在剪枝樹內(nèi)的最近鄰點(diǎn)預(yù)置到被刪除樹的K近鄰數(shù)組內(nèi)，即執(zhí)行pruned_tree.KNN_result[0]=reduce_tree.KNN_result[K_g-1].調(diào)用改進(jìn)的單樹結(jié)構(gòu)K近鄰搜索算法pruned_tree.search_KNN_improve()，確定待查點(diǎn)target在被刪樹內(nèi)的K個(gè)近鄰點(diǎn).此時(shí)的剪枝約束條件較為嚴(yán)格，如果定位的近鄰點(diǎn)個(gè)數(shù)num>=K，則算法結(jié)束，否則執(zhí)行Step 3.

Step 3.將待查點(diǎn)在剪枝樹內(nèi)的“最遠(yuǎn)”近鄰點(diǎn)預(yù)置到被刪樹的K近鄰數(shù)組內(nèi)，即執(zhí)行pruned_tree.KNN_result[0]=reduce_tree.KNN_result[0].調(diào)用改進(jìn)的單樹結(jié)構(gòu)K近鄰搜索算法pruned_tree.search_KNN_improve()，確定待查點(diǎn)target在被刪樹內(nèi)的K個(gè)近鄰點(diǎn).此時(shí)的剪枝約束條件較為寬松，如果定位的近鄰點(diǎn)個(gè)數(shù)num>=K，則算法結(jié)束，否則執(zhí)行Step 4.

Step 4.將完整樹的K近鄰數(shù)組預(yù)置為空，使用原始的單樹結(jié)構(gòu)K近鄰搜索算法在完整樹內(nèi)查找K近鄰點(diǎn)ball_tree.search_KNN()，算法結(jié)束.

表4 基于“雙樹”的K近鄰搜索實(shí)例Table 4 KNN search instance based on “double tree”

表4顯示了在圖4、圖5所示“雙樹”結(jié)構(gòu)內(nèi)的5近鄰搜索實(shí)例.待查點(diǎn)target在二維空間內(nèi)的位置是(66,212),采用原始Ball-tree結(jié)構(gòu)K近鄰算法時(shí)，僅有10個(gè)葉節(jié)點(diǎn)被剪枝過濾，經(jīng)過與34個(gè)葉節(jié)點(diǎn)計(jì)算比較空間距離，才完成5近鄰搜索，查詢效率較低.采用“雙樹”結(jié)構(gòu)K近鄰算法后，在剪枝樹內(nèi)經(jīng)過與10個(gè)葉節(jié)點(diǎn)比較空間距離，確定剪枝樹內(nèi)的3個(gè)近鄰點(diǎn)，將待查點(diǎn)與編號(hào)36葉節(jié)點(diǎn)的空間距離24.08設(shè)置為被刪樹的初始近鄰值，而原始算法的初始近鄰值為238.13(見表2)，“雙樹”結(jié)構(gòu)的初始近鄰值更接近待查點(diǎn)的第5個(gè)近鄰點(diǎn)，有更好的剪枝效果，在被刪樹內(nèi)經(jīng)過7次比較，即確定5近鄰點(diǎn).整個(gè)查詢過程計(jì)算比較了17個(gè)葉節(jié)點(diǎn)的空間距離，共有27個(gè)葉節(jié)點(diǎn)被剪枝濾除，與原始算法相比，查詢效率得到明顯提升.實(shí)驗(yàn)結(jié)果表明剪枝數(shù)max_points和剪枝樹內(nèi)近鄰點(diǎn)個(gè)數(shù)K_g對(duì)整體查詢效率影響很大，例如max_points取值區(qū)間為[2,11]，K_g的取值區(qū)間為[2,5]，則共可得到10×10=100組可選參數(shù)，不同參數(shù)的查詢效率差別很大，算法4用于確定最優(yōu)查詢參數(shù).

3.3 確定最優(yōu)查詢參數(shù)

將原始數(shù)據(jù)集按照8∶2比例劃分，隨機(jī)選擇20%數(shù)據(jù)點(diǎn)作為測(cè)試集，隨機(jī)性保證測(cè)試數(shù)據(jù)點(diǎn)分布比較均勻，其余80%數(shù)據(jù)點(diǎn)作為訓(xùn)練集.利用隨機(jī)算法，共生成10組測(cè)試和訓(xùn)練數(shù)據(jù)集，對(duì)每組數(shù)據(jù)集得到的最優(yōu)參數(shù)計(jì)算平均值，作為最終的最優(yōu)參數(shù)值.

確定最優(yōu)查詢參數(shù)算法4：determine_optimal_parameters(node_density,train_data,test_data,K,max_len)：

輸入?yún)?shù)：用于訓(xùn)練的數(shù)據(jù)點(diǎn)集合train_data；用于測(cè)試的數(shù)據(jù)點(diǎn)集合test_data；存儲(chǔ)每棵子樹統(tǒng)計(jì)信息的node_density數(shù)組；待查最近鄰個(gè)數(shù)K；max_len定義剪枝數(shù)上限值.

輸出參數(shù)：最佳剪枝數(shù)max_points；最佳剪枝樹的近鄰點(diǎn)個(gè)數(shù)K_g；起始近鄰點(diǎn)begin_point；結(jié)束近鄰點(diǎn)end_point；

Step 1.按照train_data集合構(gòu)成Ball-tree結(jié)構(gòu)；定義實(shí)數(shù)變量T1、T2，初值均為0，這兩個(gè)變量用于時(shí)間統(tǒng)計(jì)；定義整數(shù)變量Len，初值為2.

Step 2.按照train_data集合，調(diào)用算法2構(gòu)造剪枝樹(reduce-tree)和被刪樹(pruned-tree)，剪枝數(shù)設(shè)定為Len.定義整數(shù)變量i，初值為1.

Step 3.如果i<=len(test_data)，執(zhí)行Step 4，否則，令Len=Len+ 1，如果Len

Step 4.定義整數(shù)變量j，初值為2.如果j<=K，執(zhí)行Step 5，否則令i=i+1，執(zhí)行Step 3.

Step 5.調(diào)用search_KNN_Improve(KNN_result,reduce-tree,test_data[i],j)，查詢test_data[i]在剪枝樹中的j個(gè)近鄰點(diǎn)，T1為查詢消耗的時(shí)間.

Step 6.定義整數(shù)變量n，初值為1.如果n<=j-1，執(zhí)行Step 7，否則，令j=j+1，如果j<=K，執(zhí)行Step 5，否則令i=i+1，執(zhí)行Step 3.

Step 7.令begin_point_=n，end_point_=j，調(diào)用算法3查詢test_data[i]在“雙樹”結(jié)構(gòu)內(nèi)的K近鄰點(diǎn)，限定剪枝樹內(nèi)查詢的近鄰點(diǎn)個(gè)數(shù)K_g=j，限定被刪樹的兩個(gè)初始近鄰點(diǎn)為reduce_tree.KNN_result[j-1]和reduce_tree.KNN_result[n-1]，T2為這步查詢所消耗的時(shí)間.調(diào)用update_into_result(Len,j,begin_pos,end_pos,T1+T2);統(tǒng)計(jì)每種查詢參數(shù)消耗的查詢時(shí)間，result數(shù)組元素結(jié)構(gòu)為[max_points_,K_g_,begin_point_,end_point_,T_]，其中前四項(xiàng)為主關(guān)鍵字字段，如果result數(shù)組中沒有對(duì)應(yīng)的記錄，則新增，否則將T1+T2值追加到相應(yīng)記錄.令n=n+1，如果n<=j-1，執(zhí)行Step 7，否則，令j=j+1，如果j<=K，執(zhí)行Step 5，否則令i=i+1，執(zhí)行Step 3.

Step 8.調(diào)用Sort_result_by_desc(result,T);按照時(shí)間統(tǒng)計(jì)結(jié)果，升序排列result數(shù)組元素，排序之后result[0]元素各字段值即為最優(yōu)參數(shù)值.

圖6 最佳查詢參數(shù)統(tǒng)計(jì)Fig.6 Best query parameter statistics

對(duì)圖3(a)所示二維空間內(nèi)3960個(gè)樣本點(diǎn)按照8∶2比例劃分訓(xùn)練和測(cè)試集，待查找的近鄰數(shù)K為5，將剪枝數(shù)范圍限定為[6,29]，將剪枝樹近鄰點(diǎn)個(gè)數(shù)K_g限定為[2,5]，利用算法4得到的最優(yōu)參數(shù)如圖6所示，對(duì)10組訓(xùn)練和測(cè)試結(jié)果計(jì)算均值后，得到最優(yōu)max_points=14，最優(yōu)K_g=2，在這組參數(shù)作用下，全部測(cè)試點(diǎn)平均查詢時(shí)間為3.2秒；同時(shí)得到最差參數(shù)為max_points=6，最差K_g=2，使用這組參數(shù)，平均查詢時(shí)間為10.8秒.

圖7顯示的是在最佳參數(shù)和最差參數(shù)作用下，對(duì)400個(gè)測(cè)試點(diǎn)與剪枝樹起始近鄰點(diǎn)距離reduce_min_radius，結(jié)束近鄰點(diǎn)距離reduce_max_radius和完整樹第K個(gè)近鄰點(diǎn)距離all_max_radius進(jìn)行了統(tǒng)計(jì)分析.圖7(a)是按照reduce_min_radius降序排列的最佳參數(shù)測(cè)試結(jié)果，可見在最佳參數(shù)作用下，絕大部分測(cè)試點(diǎn)與第K個(gè)近鄰點(diǎn)的距離值all_max_radius小于reduce_min_radius，可在被刪樹內(nèi)進(jìn)行一次檢索即可命中K近鄰點(diǎn)，只有極少量測(cè)試點(diǎn)的all_max_radius大于reduce_max_radius，因此整體查詢效率最高.圖7(b)是按照all_max_radius降序排列的最差參數(shù)測(cè)試結(jié)果，可見在最差參數(shù)作用下，絕大部分測(cè)試點(diǎn)與第K個(gè)近鄰點(diǎn)的距離值all_max_radius大于reduce_min_radius，但是小于reduce_max_radius，即需要兩次檢索被刪樹才能確定K近鄰點(diǎn)，極個(gè)別測(cè)試點(diǎn)需要檢索完整樹才能確定K近鄰.

圖7 400個(gè)查詢點(diǎn)近鄰距離統(tǒng)計(jì)Fig.7 Neighbor distance of 400 query points

4 實(shí)驗(yàn)測(cè)試分析

實(shí)驗(yàn)測(cè)試采用的軟、硬件配置如下，設(shè)備型號(hào)：ThinkPad P1隱士，CPU：i7-9850H，運(yùn)行內(nèi)存：32GB，硬盤容量2TB，操作系統(tǒng)：Windows 10.全部實(shí)驗(yàn)數(shù)據(jù)來自UCI數(shù)據(jù)集，UCI數(shù)據(jù)集目前共有507個(gè)樣本集合，被廣泛應(yīng)用于各類機(jī)器學(xué)習(xí)研究工作.本文選取8個(gè)樣本集合，如表5所示，樣本集涵蓋了多種特征維度和樣本數(shù)量，將每個(gè)樣本集中非數(shù)值型字段(例如月份、星期)，統(tǒng)一轉(zhuǎn)換為數(shù)值型字段，并對(duì)數(shù)據(jù)進(jìn)行歸一化處理，即將全部屬性值映射到[0,1]區(qū)間.對(duì)每個(gè)樣本集合按照8∶2的比例劃分訓(xùn)練和測(cè)試集.為了保證數(shù)據(jù)分布比較均勻，采用隨機(jī)方式選取數(shù)據(jù)，對(duì)每個(gè)樣本集進(jìn)10次實(shí)驗(yàn)，將10次測(cè)試結(jié)果的均值作為最終實(shí)驗(yàn)數(shù)據(jù)，搜索的最近鄰個(gè)數(shù)統(tǒng)一設(shè)置為5.

表5顯示在8個(gè)樣本集上，分別應(yīng)用基于Ball-tree結(jié)構(gòu)的原始KNN算法和基于“雙樹”結(jié)構(gòu)的改進(jìn)KNN算法進(jìn)行測(cè)試.實(shí)驗(yàn)結(jié)果表明，原始KNN算法在維度較低、樣本數(shù)較少情況下，表現(xiàn)良好.隨著特征維度和樣本數(shù)增加，查詢所消耗時(shí)間顯著增長，針對(duì)維度為10、樣本數(shù)為58000的Shuttle集合，查詢時(shí)間達(dá)到13271.605秒，針對(duì)維度為2400，樣本數(shù)為8320的Swarm集合，處理時(shí)間也達(dá)到1203.062秒.這樣的處理速度很難滿足實(shí)時(shí)性要求高的任務(wù)需求，如網(wǎng)絡(luò)攻擊在線實(shí)時(shí)檢測(cè).

表5 實(shí)驗(yàn)結(jié)果比較Table 5 Comparison of experimental results

使用基于“雙樹”的改進(jìn)KNN算法對(duì)8個(gè)樣本集進(jìn)行查詢處理，在特征維度和樣本數(shù)量顯著增加條件下，查詢時(shí)間并未急速增長.針對(duì)Shuttle集合，改進(jìn)算法查詢時(shí)間為836.057秒，比原始算法節(jié)省12435.548秒，增速達(dá)到93.7%.針對(duì)Harus集合，改進(jìn)算法用時(shí)18.796秒，增速達(dá)93.2%.分析如下，在改進(jìn)算法中，通過統(tǒng)計(jì)分析得到最優(yōu)“雙樹”構(gòu)造參數(shù)，利用最優(yōu)參數(shù)構(gòu)建剪枝樹和被刪樹具有最小的剪枝半徑，可以達(dá)到最佳剪枝效果，有更多的數(shù)據(jù)點(diǎn)在查詢過程中被剪枝刪除，整體計(jì)算量減少，查詢效率顯著提高.同時(shí)由于最優(yōu)參數(shù)也是基于原始樣本集按照8∶2比例劃分訓(xùn)練和測(cè)試集統(tǒng)計(jì)得出，因此在此基礎(chǔ)上得到的查詢統(tǒng)計(jì)時(shí)間整體表現(xiàn)良好，當(dāng)測(cè)試集來自不同集合時(shí)，即測(cè)試集不從樣本集中選擇時(shí)，整體查詢性能略有下降，但仍維持較高增速.

5 結(jié) 語

本文提出一種“雙樹”構(gòu)造方法，可以從原始樣本集構(gòu)建剪枝樹和被刪樹.由于對(duì)原始樣本集內(nèi)高密度區(qū)域和離群點(diǎn)區(qū)域進(jìn)行了區(qū)分處理，構(gòu)建的剪枝樹包含盡可能少的樣本點(diǎn)，且最大限度地保留了原始樣本集在高維空間的分布形態(tài).與基于Ball-tree結(jié)構(gòu)的K近鄰查找算法相比，本文提出的“雙樹”結(jié)構(gòu)K近鄰搜索算法解決了因初始近鄰點(diǎn)位置固定，導(dǎo)致的剪枝半徑過大，查詢效率較低問題.改進(jìn)算法的初始近鄰點(diǎn)動(dòng)態(tài)分布于待查點(diǎn)附近，有效縮短了剪枝距離，在查詢過程中，有更多的樣本點(diǎn)被剪枝濾除，計(jì)算量顯著減少，查詢效率明顯提高.實(shí)驗(yàn)結(jié)果表明，與原始算法相比，改進(jìn)算法在處理高維、海量樣本集時(shí)仍維持較高增速比.

受樣本集在多維空間分布形態(tài)影響，構(gòu)建的剪枝樹和被刪樹可能存在不平衡問題.下一步計(jì)劃研究基于PCA(Principal Component Analysis)的空間劃分方法，以構(gòu)建相對(duì)平衡的二叉樹結(jié)構(gòu)，進(jìn)一步改進(jìn)、提升K近鄰查詢效率.