一種基于數(shù)據(jù)空間自適應(yīng)規(guī)則網(wǎng)格劃分的Skd-tree最近鄰算法

王榮秀，王 波

（1.重慶工商大學(xué) 人工智能學(xué)院，重慶 400067；2.重慶理工大學(xué) 理學(xué)院，重慶 400054）

如何查詢給定數(shù)據(jù)在數(shù)據(jù)集中的最近鄰者是數(shù)據(jù)應(yīng)用中的一類基本問題。最近鄰算法KNN（k-nearest neighbor）能有效地對(duì)大規(guī)?？臻g數(shù)據(jù)進(jìn)行分類與識(shí)別，無需參數(shù)訓(xùn)練，簡單直觀，易于實(shí)現(xiàn)，適合多分類問題；其缺點(diǎn)是缺少分類規(guī)則，計(jì)算量大，導(dǎo)致分類效率較低；同時(shí)在樣本數(shù)量不平衡時(shí)，其分類效果不夠理想［1－2］。針對(duì)KNN算法的不足，近年來不少學(xué)者提出了很多改進(jìn)算法，如引入密度分布參數(shù)的樣本劃分來提高分類效率，或采用可調(diào)權(quán)重的k最近鄰法來改善分類效果等［3－6］。這些算法大多都是對(duì)KNN本身的一種調(diào)整，因此改進(jìn)效果有限。從原理上來看，如果能盡量地把KNN的有效搜索空間縮小，并使局部搜索空間中的樣本平衡，則可有效提高分類效率和改善分類效果。最常用的方法就是構(gòu)建優(yōu)化的空間數(shù)據(jù)索引，快速收縮查詢空間；同時(shí)充分利用數(shù)據(jù)索引結(jié)構(gòu)，簡化分類流程，在數(shù)據(jù)索引得到的局部空間中應(yīng)用KNN，以達(dá)到提高分類效率和分類效果的目的。

樹形結(jié)構(gòu)由于表達(dá)能力強(qiáng)，無需參數(shù)、代價(jià)較小等優(yōu)點(diǎn)，因此被廣泛用于構(gòu)建數(shù)據(jù)索引，如常見的數(shù)據(jù)索引kd-tree和R-tree。樹形索引的構(gòu)建實(shí)質(zhì)上是通過對(duì)數(shù)據(jù)空間的分割，將數(shù)據(jù)集的特征屬性，如密度、分布區(qū)域、相互位置、維度、均衡性等體現(xiàn)為空間結(jié)構(gòu)與層次，從而把對(duì)數(shù)據(jù)的處理約化為空間關(guān)系的計(jì)算，因此空間的分割方式及對(duì)分割后形成的空間網(wǎng)格的處理方法是決定數(shù)據(jù)分類效率與分類效果的關(guān)鍵因素。例如，在DBSCAN算法中，對(duì)數(shù)據(jù)空間進(jìn)行網(wǎng)格劃分是一類常用手段。Gunawan等［7］認(rèn)為合理的網(wǎng)格劃分可以有效改善DBSCAN算法的復(fù)雜度，通過網(wǎng)格之間的拓樸關(guān)系，建立相應(yīng)的網(wǎng)格索引指數(shù)，可以更快地搜索鄰近網(wǎng)格；同時(shí)通過網(wǎng)格的合并與擴(kuò)展，可以減少數(shù)據(jù)空間的冗余。Thapana等［8］研究了在多維數(shù)據(jù)空間進(jìn)行規(guī)則網(wǎng)格劃分的優(yōu)缺點(diǎn)，認(rèn)為規(guī)則網(wǎng)格的對(duì)稱性和可移植性使網(wǎng)格的融合更方便、更高效；但在高維空間中使用大小相同的超方體進(jìn)行分割時(shí)，近鄰網(wǎng)格的數(shù)量呈幾何級(jí)數(shù)增長。為避免高維數(shù)據(jù)在超方體分割時(shí)產(chǎn)生的“近鄰爆炸”問題，他采用了一種類似于位圖的結(jié)構(gòu)索引（稱為HyperGrid Bitmap）來標(biāo)注非空網(wǎng)格，以達(dá)到過濾空網(wǎng)格的目的。

kd-tree采用最簡數(shù)量的超平面來實(shí)現(xiàn)空間的分割，分割屬性則為數(shù)據(jù)在各維度上的中值，每一超平面有且僅有一個(gè)數(shù)據(jù)；其樹形結(jié)構(gòu)具有軸對(duì)齊、場景自適應(yīng)劃分、低存儲(chǔ)消耗和快速遍歷等優(yōu)勢；相較于R-tree，kd-tree更適用于在高維數(shù)據(jù)之間進(jìn)行相似性檢索，如圖像搜索、特征點(diǎn)匹配等。將kd-tree與KNN相結(jié)合，就得到kd-tree KNN，但由于kd-tree KNN采用超球體來處理鄰近網(wǎng)格中的數(shù)據(jù)，必然需要求解超球面與超平面的相交問題，長方超體在空間維度上的尺度差異也帶來了額外的困難，結(jié)果導(dǎo)致kd-tree KNN需要回溯至其他非葉子節(jié)點(diǎn)來尋找最近鄰匹配，從而導(dǎo)致分類效率降低［9－10］；目前對(duì)kd-tree KNN算法的改進(jìn)主要分為2類［9，11－14］，第1類是設(shè)計(jì)優(yōu)化的空間網(wǎng)格算法來減少回溯節(jié)點(diǎn)數(shù)量，如Chen等［15］針對(duì)長方超體的空間結(jié)構(gòu)，引入了一種參考網(wǎng)格，研究了參考網(wǎng)格與其周圍數(shù)據(jù)的距離特性，證明了網(wǎng)格之外的任意點(diǎn)到網(wǎng)格的最遠(yuǎn)距離必然是網(wǎng)格的某個(gè)頂點(diǎn)；同時(shí)網(wǎng)格外的任意點(diǎn)到網(wǎng)格的最近距離必然是網(wǎng)格邊界（超平面）上的點(diǎn)。依據(jù)最近最遠(yuǎn)數(shù)據(jù)點(diǎn)，可以濾除不必要的計(jì)算節(jié)點(diǎn)；同時(shí)通過修改kd-tree的樹形結(jié)構(gòu)，將參考網(wǎng)格作為各節(jié)點(diǎn)的索引指標(biāo)，有效減少了回溯節(jié)點(diǎn)數(shù)量。由于需要事先計(jì)算和存儲(chǔ)數(shù)據(jù)到參考網(wǎng)格的距離信息，這種方法不適用于高維數(shù)據(jù)，且存儲(chǔ)代價(jià)相對(duì)較大。對(duì)kd-tree KNN算法改進(jìn)的第2類主要是球樹算法或采用球狀空間來劃分?jǐn)?shù)據(jù)空間，從而簡化或減少超球面與超平面的分割算法或相交數(shù)量。球樹算法的基本思想是直接采用KNN中的超球體來找替長方超體進(jìn)行空間分割，如陳曉康等［9］采用由大到小、層層包含的超球體來完成空間的劃分，通過空間的遞歸關(guān)系，最終構(gòu)建出與之相適應(yīng)的kd-tree。在實(shí)現(xiàn)最近鄰查詢時(shí)，只需通過kd-tree索引得到數(shù)據(jù)所在的超球體，則此球體內(nèi)的數(shù)據(jù)可以作為優(yōu)化的距離估計(jì)，再應(yīng)用KNN計(jì)算被查數(shù)據(jù)到相鄰球體中各節(jié)點(diǎn)的距離，從而得到最近鄰結(jié)果。對(duì)歐氏空間進(jìn)行球狀分割存在一個(gè)基本的矛盾，那就是網(wǎng)格與數(shù)據(jù)空間形狀異構(gòu)，因此球樹算法更適用于數(shù)據(jù)呈團(tuán)族分布的情況，且通常需要與聚類算法相結(jié)合。綜上所述，減少回溯節(jié)點(diǎn)往往排除可能的最優(yōu)匹配數(shù)據(jù)，增加查詢算法難度，影響最終分類的成功率；而采用超球面來劃分?jǐn)?shù)據(jù)空間則存在區(qū)域重疊或劃分不完全等問題，同時(shí)超球面的計(jì)算增加計(jì)算負(fù)荷，使kd-tree的構(gòu)建較為復(fù)雜，最終影響分類效率與分類效果。

針對(duì)目前kd-tree KNN算法的不足，本文提出了一種改進(jìn)的Skd-tree KNN最近鄰算法，采用均勻的超方體空間劃分策略來構(gòu)建kd-tree索引結(jié)構(gòu)，將數(shù)據(jù)置于網(wǎng)格內(nèi)部，網(wǎng)格大小可適應(yīng)鄰近數(shù)據(jù)的分布特點(diǎn)，從而得到局部均衡的樣本并有效縮小搜索空間；結(jié)合KNN最近鄰匹配算法，無需節(jié)點(diǎn)回溯就可實(shí)現(xiàn)數(shù)據(jù)的快速分類。為充分利用規(guī)則方體對(duì)空間的分割優(yōu)勢，文中引入了查詢超體以適應(yīng)規(guī)則的空間結(jié)構(gòu)；同時(shí)為避免相應(yīng)的“近鄰爆炸”問題，通過建立非空網(wǎng)格的索引路徑指數(shù)，過濾空的近鄰網(wǎng)格，從而排除無關(guān)近鄰數(shù)據(jù)。數(shù)字實(shí)驗(yàn)的結(jié)果證明了Skd-tree KNN比kd-tree KNN具備更好的索引定位精度、更少的無關(guān)數(shù)據(jù)回溯和計(jì)算，更短的查詢時(shí)間，尤其適用于數(shù)據(jù)樣本較大或維度較高數(shù)據(jù)的最近鄰查詢。

1 kd-tree與KNN算法原理

kd-tree指k dimensional tree，是Friedman等人于1977年提出的針對(duì)高維數(shù)據(jù)建立二叉索引樹的一種方法；通過對(duì)高維數(shù)據(jù)的層次劃分，從而構(gòu)建出索引樹，基本算法如下：

算法 kd-tree索引樹的構(gòu)建

輸入：k維數(shù)據(jù)

輸出：kd-tree索引樹

步驟1 確定出分裂屬性。先計(jì)算出各數(shù)據(jù)分布在k個(gè)維度上的方差，方差最大者說明數(shù)據(jù)相應(yīng)維度上的分散程度最大，數(shù)據(jù)劃分得到的分辨率最高。設(shè)數(shù)據(jù)在第i維上的方差最大，則選取數(shù)據(jù)第i維作為分裂屬性。

步驟2以具有第i維中值的數(shù)據(jù)作為根節(jié)點(diǎn)，將第i維值小于此中值的數(shù)據(jù)劃分至左子樹，第i維值大于此中值的數(shù)據(jù)劃分至右子樹。

步驟3 分別以左子樹和右子樹為新的數(shù)據(jù)集，重復(fù)進(jìn)行步驟1和步驟2。不同的是，在選擇分裂屬性時(shí)，不再考慮第i維。

步驟4由此不斷遞歸分叉，直至每個(gè)節(jié)點(diǎn)只剩下一個(gè)數(shù)據(jù)。

作為簡單的例子，以k＝2的輸入數(shù)據(jù)（x，y）來說明kd-tree的構(gòu)建方法。設(shè)輸入數(shù)據(jù)分別為：（7.467 9，8.462 2）、（4.659 9，6.721 4）、（4.451 0，5.251 5）、（0.1527 4，4.186 5）以及（9.318 1，2.026 5）。其中數(shù)據(jù)在x維和y維的方差為3.479 6和2.448 1，因此選x作為第一分裂屬性。數(shù)據(jù)在x維上的中位數(shù)為4.659 9，因此將數(shù)值（4.659 9，6.721 4）作為根結(jié)點(diǎn)。然后，依據(jù)數(shù)據(jù)在x維上的大小，把小于4.659 9的數(shù)據(jù)劃分至左邊子樹；把大于4.659 9的數(shù)據(jù)劃分至右邊子樹。在左子樹中，有2個(gè)數(shù)據(jù)（4.451 0，5.251 5）和（0.1527 4，4.186 5），此時(shí)只能選取y為分裂屬性，任取一數(shù)，如5.251 5，作為新的子節(jié)點(diǎn)，再分裂為左右子樹，并以些類推。最后得到的樹型結(jié)構(gòu)如圖1（a）所示。

圖1 kd-tree的樹型索引結(jié)構(gòu)及其對(duì)空間的劃分

從數(shù)據(jù)的空間結(jié)構(gòu)來看，kd-tree的構(gòu)建過程實(shí)質(zhì)上就是利用數(shù)據(jù)的空間分布，用不同的超平面把數(shù)據(jù)空間分割成形狀不一的超長方體結(jié)構(gòu)，而每一個(gè)超平面上有且僅有一個(gè)數(shù)據(jù)位于其中，因此每一個(gè)超平面對(duì)應(yīng)著索引樹中的一個(gè)節(jié)點(diǎn)。

KNN是k nearest neighbor的縮寫，意指在一組給定的數(shù)據(jù)中查詢一個(gè)新數(shù)據(jù)的k個(gè)最近鄰數(shù)據(jù)。當(dāng)數(shù)據(jù)的遠(yuǎn)近被定義為歐氏距離時(shí)，KNN就意味著尋找與新數(shù)據(jù)歐氏距離最近的前k個(gè)數(shù)據(jù)點(diǎn)。為了挑選出k個(gè)最近鄰數(shù)據(jù)，往往需要計(jì)算每一個(gè)數(shù)據(jù)到被查詢數(shù)據(jù)的距離。當(dāng)數(shù)據(jù)量很大時(shí)，其計(jì)算與存儲(chǔ)的代價(jià)很高。另一種替換的方法是，以被查詢數(shù)據(jù)為中心，以一定的參考距離為半徑作一圓周，然后判斷圓周內(nèi)的數(shù)據(jù)個(gè)數(shù)。如果小于k個(gè)，則增加半徑；如果大于k個(gè)，則減小半徑，直到所作圓周中剛好有k個(gè)數(shù)據(jù)。這種方法不需要計(jì)算每一個(gè)數(shù)據(jù)到被查詢數(shù)據(jù)的距離，較適合海量數(shù)據(jù)下的k最近鄰查詢，但初始半徑不好確定；同時(shí)在數(shù)據(jù)密度較大時(shí)，半徑的增／減幅度不好控制，常常需要多次增減才能找到合適的值，這也增加了計(jì)算代價(jià)。

將kd-tree與KNN相結(jié)合是一種很好的思路，kd-tree可以快速定位被查詢數(shù)據(jù)的空間位置，從而避免了在KNN中對(duì)大量無關(guān)數(shù)據(jù)的計(jì)算，極大地提高了查詢效率。

以圖1所示的kd-tree為例來說明KNN的實(shí)現(xiàn)方法，設(shè)被查詢數(shù)據(jù)為（3.203 3，3.502 2）。容易看出，從根節(jié)點(diǎn)開始，數(shù)據(jù)（3.20 33，3.502 2）的查詢路徑為（4.659 9，6.721 4）→（4.451 0，5.251 5）→（0.152 74，4.186 5）；然后計(jì)算出節(jié)點(diǎn)（0.152 74，4.186 5）與（3.203 3，3.502 2）的距離，設(shè)為d，并以（3.203 3，3.502 2）為圓心，d為半徑做圓Cd，如圖2所示；接下來判斷圓Cd是否與其他數(shù)據(jù)點(diǎn)所在的直線相交；首先判斷是否與（0.152 74，4.186 5）的根節(jié)點(diǎn)（4.451 0，5.251 5）所在直線相交，如果相交，則計(jì)算出（3.203 3，3.502 2）與（4.451 0，5.251 5）的距離d′，若d′＜d，則更新d為d′并用新的距離為半徑畫圓Cd′；采用新圓，再判斷是否與根節(jié)點(diǎn)（4.659 9，6.721 4）對(duì)應(yīng)直線相交；如果與根節(jié)點(diǎn)直線相交，還需要進(jìn)一步判斷根節(jié)點(diǎn)右子樹中各直線相交的情況。每次判斷出相交后，要比較距離與原有半徑的大小，在需要時(shí)候更新圓的半徑。在本例中，因?yàn)椋?.502 2－5.251 5｜＜d，所以Cd與（0.152 74，4.186 5）的父節(jié)點(diǎn)（4.451 0，5.251 5）所在直線相交；由于（3.203 3，3.502 2）點(diǎn)到（4.451 0，5.251 5）的距離d′小于d，則更新圓為Cd′（圖中虛線）。再回溯至節(jié)點(diǎn)（4.659 9，6.721 4），因｜3.203 3－4.659 9｜＜d′，Cd′與根節(jié)點(diǎn)（4.659 9，6.721 4）對(duì)應(yīng)的直線也相交，但不需更新圓Cd′；進(jìn)一步可判斷出Cd′與右子樹中的節(jié)點(diǎn)（9.318 1，2.026 5）相交而與節(jié)點(diǎn)（7.467 9，8.462 2）不相交，且與（9.318 1，2.026 5）的距離大于d′，因此也無需更新。經(jīng)過上述的回溯及更新過程，最終可以確定，與被查詢點(diǎn)（3.203 3，3.502 2）最近的數(shù)據(jù)點(diǎn)就是（4.451 0，5.251 5）。

圖2 基于kd-tree的最近鄰數(shù)據(jù)查詢

根據(jù)圓與各直線相交的情況，除了點(diǎn)（7.467 9，8.462 2），均需計(jì)算其他各數(shù)據(jù)到被查詢點(diǎn)的距離。雖然采用回溯且不斷更新的計(jì)算策略，一定程度上得到了較好的查詢效率，但仍然避免不了對(duì)部分無關(guān)數(shù)據(jù)的計(jì)算。產(chǎn)生這種不足的原因是數(shù)據(jù)空間的不規(guī)則劃分，且數(shù)據(jù)位于超平面之上，雖能快速定位被查詢數(shù)據(jù)所在空間區(qū)域，但沒有為其提供與其他數(shù)據(jù)相對(duì)的位置信息，因此查詢得到的節(jié)點(diǎn)數(shù)據(jù)常常不是最合理的距離參考點(diǎn)；另外，KNN的方法是采用超球面來尋找最近鄰數(shù)據(jù)，而球面與平面是二種性質(zhì)不同的空間曲面，因此基于超平面的不規(guī)則空間劃分無法為超球面提供足夠有效的信息。

單純地從數(shù)據(jù)空間的劃分來看，采用VORONOI的空間結(jié)構(gòu)是較為理想的，其特點(diǎn)是每個(gè)數(shù)據(jù)位于自身所在區(qū)域的中心，邊界則由平分其相鄰數(shù)據(jù)距離的超平面構(gòu)成，因此落入某一區(qū)域的數(shù)據(jù)必然與位于此區(qū)域中心點(diǎn)的數(shù)據(jù)距離最近。雖然如此，但VORONOI空間結(jié)構(gòu)不適合建立數(shù)據(jù)索引，無法快速定位被查詢數(shù)據(jù)所處區(qū)域。若能在構(gòu)建索引樹的時(shí)候，把各數(shù)據(jù)置于區(qū)域內(nèi)而不是位于邊界的超平面上，且區(qū)域的劃分較為規(guī)則，則一方面可快速定位被查詢數(shù)據(jù)，同時(shí)規(guī)則的空間劃分也可反映各區(qū)域的分布關(guān)系，這為下一步尋找最近鄰數(shù)據(jù)提供了幫助。

2 規(guī)則網(wǎng)格下的kd-tree KNN算法

2.1 基本思想與查詢超體

規(guī)則網(wǎng)格的基本思想來源于坐標(biāo)系對(duì)空間的劃分方式，實(shí)際上坐標(biāo)系可看成是網(wǎng)格無限小的系統(tǒng)，當(dāng)需要對(duì)數(shù)據(jù)進(jìn)行查詢時(shí)，只需找到其相應(yīng)的網(wǎng)格（坐標(biāo)大?。┚托辛?。在工程實(shí)際中，網(wǎng)格的大小不可能做到無限小，但這種定位數(shù)據(jù)的思想?yún)s可以應(yīng)用在數(shù)據(jù)的最近鄰查找中。

對(duì)于一組給定的數(shù)據(jù)，在確定坐標(biāo)中心后（通常取數(shù)據(jù)分布的中心點(diǎn)），可利用規(guī)則網(wǎng)格的方式將數(shù)據(jù)劃分至不同的區(qū)域，數(shù)據(jù)分布稀疏的地方網(wǎng)格較大，數(shù)據(jù)較密集之處網(wǎng)格較小，直至每一個(gè)網(wǎng)格最多僅包含一個(gè)數(shù)據(jù)，如圖3所示。當(dāng)被查詢數(shù)據(jù)落入某一網(wǎng)格時(shí)，則在較大概率上與該網(wǎng)格中的數(shù)據(jù)有較近鄰的距離，同時(shí)該網(wǎng)格周圍的8個(gè)區(qū)域中也可能存在最近鄰數(shù)據(jù)。如果每次都同等地考查與這8個(gè)數(shù)據(jù)的距離，則查詢效率不高。被查詢數(shù)據(jù)與鄰近網(wǎng)格中數(shù)據(jù)的距離不但與數(shù)據(jù)的分布形態(tài)有關(guān)，還與被查詢數(shù)據(jù)在網(wǎng)格中的位置有關(guān)。因此可以根據(jù)數(shù)據(jù)之間的相對(duì)位置來盡可能排除那些距離明顯較大的數(shù)據(jù)。實(shí)現(xiàn)這一思想的簡單方法就是將以被查數(shù)據(jù)為中心的較小的局部數(shù)據(jù)空間單獨(dú)分割出來，從而提高查詢效率。

圖3 數(shù)據(jù)的網(wǎng)格劃分（三角形是已知數(shù)據(jù)，圓形為被查詢數(shù)據(jù)）

假設(shè)被查數(shù)據(jù)落入某一網(wǎng)格，若網(wǎng)格中已有數(shù)據(jù)（設(shè)為xΩ），則可計(jì)算被查數(shù)據(jù)與xΩ的歐氏距離d，并以被查詢數(shù)據(jù)為中心，2d為邊做正方超體（稱之為查詢超體），并比較位于正方超體內(nèi)的其他數(shù)據(jù)的距離，如圖3中所示虛線方框；若網(wǎng)格中無數(shù)據(jù)，則被查數(shù)據(jù)所在父節(jié)點(diǎn)網(wǎng)格中必有數(shù)據(jù)，如圖4所示；優(yōu)先選擇與被查數(shù)據(jù)位于同一網(wǎng)格的數(shù)據(jù)，并計(jì)算最近歐氏距離d，再做邊長為2d的查詢超體。

圖4 被查數(shù)據(jù)落入空網(wǎng)格時(shí)的近鄰查詢

采用正方超體而不是超球體的優(yōu)點(diǎn)是無需判斷超方體與網(wǎng)格超平面是否相交，且容易判斷鄰近網(wǎng)格中的數(shù)據(jù)是否位于查詢超體中。設(shè)n維被查數(shù)據(jù)為xs，則對(duì)查詢超體之內(nèi)的數(shù)據(jù)必有x∈［xs－d，xs＋d］。因此當(dāng)d和查詢超體確定后，可快速查詢出最近鄰數(shù)據(jù)；d的大小可保證查詢體是一個(gè)合理的空間分割，且主要包含了與已知數(shù)據(jù)xΩ空間對(duì)稱網(wǎng)格中可能存在的數(shù)據(jù)。

2.2 數(shù)據(jù)空間的方體化

要快速定位被查數(shù)據(jù)并確定出較合理的查詢超體就有必要構(gòu)建適用于規(guī)則網(wǎng)格情形下的檢索樹結(jié)構(gòu)。雖然數(shù)據(jù)不再位于超平面上，而是在超方體中，但kd-tree的建立方法仍然適用，只是不再單純地依賴于數(shù)據(jù)，而是需要考慮整體數(shù)據(jù)構(gòu)成的空間；同時(shí)樹的各個(gè)節(jié)點(diǎn)也不再是數(shù)據(jù)，而是各個(gè)不同的網(wǎng)格區(qū)域，根節(jié)點(diǎn)就是整個(gè)數(shù)據(jù)的空間域，葉子節(jié)點(diǎn)就是最多僅包括一個(gè)數(shù)據(jù)的空間網(wǎng)格，稱此種樹為Skd-tree。

理想的網(wǎng)格形狀是超方體或近似的超方體，但由于數(shù)據(jù)在各個(gè)維度上分布的尺度不同，因此按kd-tree方法進(jìn)行劃分的網(wǎng)格將是長方超體。長方超體的一個(gè)主要不足是數(shù)據(jù)在空間某些維度的定位不夠精細(xì)，容易導(dǎo)致查詢超體過大，從而引入不必要的比較數(shù)據(jù)。方法1是引入加權(quán)歐氏距離，使各維度對(duì)總體距離的貢獻(xiàn)占有不同的比例，實(shí)際上是將數(shù)據(jù)所在的空間沿各個(gè)維度進(jìn)行縮放，使最終的空間呈正方超體。當(dāng)數(shù)據(jù)在各維度上同等重要時(shí)，則不能使用加權(quán)歐氏距離。方法2是按數(shù)據(jù)空間在各維度的大小預(yù)先分塊，使分塊后的數(shù)據(jù)占據(jù)一個(gè)超方體。這種方法的缺點(diǎn)是當(dāng)數(shù)據(jù)維度較高時(shí)且各維度尺度差異較大時(shí)，則分塊較多，易導(dǎo)致Skd-tree結(jié)構(gòu)復(fù)雜。方法3是以最大尺度的空間維度為準(zhǔn)，在較小尺度的維度上添加空白空間，使其一致。該方法的不足是可能使空白網(wǎng)格較多，因此需要在近鄰搜索時(shí)濾除。以2維數(shù)據(jù)為例，圖5給出了這3種方法的示意圖。

圖5 原始數(shù)據(jù)空間的方體化

2.3 Skd-tree KNN算法

依據(jù)前述Skd-tree及基于查詢超體的基本思想，可以總結(jié)出規(guī)則網(wǎng)格劃分下的Skd-tree KNN算法（Skd-tree KNN）如下：

輸入：n個(gè)k維數(shù)據(jù)｛xi｝，i＝1，2，…，n，xi＝［xi1，xi2，…，xik］；一個(gè)待查數(shù)據(jù)xs＝［xs1，xs2，…，xsk］。

輸出：SKd-tree索引樹及與xs距離最近的數(shù)據(jù)xl，l∈｛1，2，…，n｝。

步驟1數(shù)據(jù)空間的方體化。如采用增加空白空間的方法，則處理如下：先計(jì)算出各維度的尺度Dj＝｜maxxmj－minxgj｜，j＝1，2，…，k；并取D＝max｛Dj｝；則數(shù)據(jù)可認(rèn)為是存在于k維空間中一個(gè)邊長為D的超方體中，其中心為｛（maxxmj＋minxgj）／2｝。

步驟2將整個(gè)超方體看成根節(jié)點(diǎn)，按維度順序，以超體中心坐標(biāo)大小為分裂屬性，把小于此值和大于此值的數(shù)據(jù)分開，同時(shí)也是將整個(gè)超方體在各個(gè)維度上進(jìn)行平分；這樣可得到k2個(gè)包含數(shù)據(jù)的網(wǎng)格空間，每個(gè)網(wǎng)格是一個(gè)節(jié)點(diǎn)。

步驟3 判斷由步驟2得到的各節(jié)點(diǎn)中是否包含數(shù)據(jù)，若為空或僅有一個(gè)數(shù)據(jù)，則作為葉子節(jié)點(diǎn)；若含有1個(gè)以上數(shù)據(jù)，則重復(fù)步驟2，但劃分條件為當(dāng)前網(wǎng)格空間的中心坐標(biāo)值。

步驟4 重復(fù)步驟3，并不斷遞歸，直至得到全部葉子節(jié)點(diǎn)（劃分的停止標(biāo)準(zhǔn)也可以是網(wǎng)格大小，若網(wǎng)格達(dá)到預(yù)定的大小時(shí)，則可停止分割，此時(shí)一個(gè)葉子節(jié)點(diǎn)可能包含多個(gè)數(shù)據(jù)。通常，當(dāng)數(shù)據(jù)較為密集時(shí)，為了避免樹的復(fù)雜性可采用此法）。

由步驟2～4可得到Skd-tree索引樹；需要注意的是，空間雖然只是針對(duì)超方體，但索引樹對(duì)超方體外的被查數(shù)據(jù)也有效，步驟1的超體化只是提供一個(gè)參考的劃分框架。

步驟5為每一個(gè)葉子節(jié)點(diǎn)建立空間方位指數(shù)。將超方體中心看作原點(diǎn)，可得到每個(gè)節(jié)點(diǎn)所表示的空間網(wǎng)格中心處的坐標(biāo)向量r；以劃分時(shí)“小于”為負(fù)，“大于”為正，并將各維度按順序進(jìn)行的一次循環(huán)劃分視為一次，則經(jīng)過l次劃分后的網(wǎng)格中心處坐標(biāo)向量r各分量為，相應(yīng)網(wǎng)格的邊長L則為。

步驟6 依據(jù)Skd-tree樹的索引，找到被查數(shù)據(jù)xs所處網(wǎng)格，記為Ωs。

步驟7 若Ωs中已有數(shù)據(jù)xΩ，則計(jì)算d＝，并以xs為中心，2d為邊長做查詢超體；若Ωs中無數(shù)據(jù)，其父節(jié)點(diǎn)網(wǎng)格必含有至少2個(gè)以上數(shù)據(jù)，則只需在其同一父節(jié)點(diǎn)下的各網(wǎng)格中找到與Ωs最近鄰的非空網(wǎng)格中的數(shù)據(jù)，從而得到歐氏距離d，再做邊長為2d的查詢超體。

步驟8由條件xs－d≤xi≤xs＋d確定位于查詢超體內(nèi)的數(shù)據(jù)。由于d是Ωs或其父節(jié)點(diǎn)中與xs的最小距離，因此，當(dāng)Ωs中無數(shù)據(jù)時(shí)，查詢超體中的數(shù)據(jù)應(yīng)當(dāng)排除Ωs父節(jié)點(diǎn)中的所有其他數(shù)據(jù)。位于查詢超體中的數(shù)據(jù)均來自于其相鄰網(wǎng)格或父節(jié)點(diǎn)網(wǎng)格，由于各網(wǎng)格的位置是固定的，因此只需存儲(chǔ)其相鄰的非空網(wǎng)格的編號(hào)，即可快速獲得位于超體內(nèi)的數(shù)據(jù)，而付出的存儲(chǔ)代價(jià)很少。

步驟9以循環(huán)更新法得到xs的最近鄰數(shù)據(jù)xl。具體做法是：依次計(jì)算被查數(shù)據(jù)xs與查詢超體內(nèi)其他數(shù)據(jù)的距離d′，若d′＞d，則計(jì)算與下一個(gè)數(shù)據(jù)的距離；若d′＜d，則更新查詢超體大小并判斷原查詢超體中未計(jì)算數(shù)據(jù)是否在新超體中，然后在新超體中繼續(xù)循環(huán)更新，直至超體內(nèi)僅有一個(gè)數(shù)據(jù)。

一般情況下，查詢超體中的數(shù)據(jù)較少，因?yàn)槊恳粋€(gè)網(wǎng)格僅包含一個(gè)數(shù)據(jù)。如果被查數(shù)據(jù)xs落入數(shù)據(jù)密集區(qū)，則網(wǎng)格較小，從而d小，查詢超體也??；而當(dāng)落入稀疏區(qū)，d雖較大，但查詢超體覆蓋的網(wǎng)格也大，從而所含數(shù)據(jù)少。當(dāng)查詢超體中包含的數(shù)據(jù)較少時(shí)，也可不用更新算法，直接計(jì)算每一個(gè)數(shù)據(jù)，然后得到最小值即可。

3 算法實(shí)例分析

實(shí)驗(yàn)環(huán)境：所有實(shí)驗(yàn)在一臺(tái)I7-4700／2.4GHz／16GB的電腦上進(jìn)行；所用軟件為Windows 8.0及Matlab 2018a。

實(shí)驗(yàn)的基本過程：

①隨機(jī)生成N＋M個(gè)k維數(shù)據(jù)｛xi｝，i＝1，2，…，N＋M，xi＝［xi1，xi2，…，xik］，xij～U（0，αj），αj～N（εj，σ2），j＝1，2，…，k，其中U、N表示均勻分布和正態(tài)分布；εj及σj為可調(diào)參數(shù)，由它們決定隨機(jī)數(shù)據(jù)在第i維上的分布范圍。

②隨機(jī)選擇N個(gè)數(shù)據(jù)作為訓(xùn)練樣本集，余下的M個(gè)數(shù)據(jù)作為測試集。

③依據(jù)訓(xùn)練集生成kd-tree及Skd-tree。

④將M個(gè)測試數(shù)據(jù)看成被查詢數(shù)據(jù)，依次進(jìn)行測試。

⑤分別記錄下索引得到的初始?xì)W氏距離d，為得到最近鄰數(shù)據(jù)時(shí)，kd-tree中的回溯節(jié)點(diǎn)數(shù)據(jù)，查詢超體中包含的數(shù)據(jù)個(gè)數(shù)，計(jì)算出相應(yīng)的平均值作為對(duì)比；同時(shí)記錄下由查詢開始至得出最近鄰數(shù)據(jù)所需時(shí)間。

⑥同時(shí)采用KNN計(jì)算最近鄰結(jié)果作為參照。

由于數(shù)據(jù)量N與數(shù)據(jù)維度k是影響查詢效率的2個(gè)重要因素，因此實(shí)驗(yàn)中重點(diǎn)比較kd-tree KNN、Skd-tree KNN 2種算法在不同數(shù)據(jù)規(guī)模和維度時(shí)的查詢效率與效果。為了減少數(shù)據(jù)隨機(jī)性對(duì)結(jié)果的影響，可選擇較大的M值，本文中統(tǒng)一取M＝100。

圖6表示了在低維和高維數(shù)據(jù)（k＝3和k＝20）條件下，由kd-tree和Skd-tree索引得到的初始距離d隨數(shù)據(jù)量N的變化情況。可以看到，在樣本數(shù)量較少時(shí)，二者效果難分高下，但在較大數(shù)據(jù)量時(shí)，Skd-tree的索引能得到更小、更接近KNN給出的實(shí)際最近鄰距離。這主要?dú)w功于Skd-tree以數(shù)據(jù)分布為依據(jù)對(duì)空間的規(guī)則劃分，從而獲得更小的網(wǎng)格單元。

圖6 經(jīng)kd-tree與Skd-tree索引得到的初始距離d隨樣本數(shù)據(jù)量的變化及與KNN最近鄰結(jié)果曲線

回溯節(jié)點(diǎn)數(shù)量與查詢超體內(nèi)的數(shù)據(jù)點(diǎn)是影響查詢效率的另一個(gè)重要指標(biāo)，對(duì)計(jì)算速度起著主要的作用。隨著數(shù)據(jù)分布密度的增加，kd-ree的回溯節(jié)點(diǎn)數(shù)量也呈現(xiàn)出快速增長的趨勢；而Skd-tree由于能較精確地定位被查數(shù)據(jù)，其查詢超體中包含的數(shù)據(jù)點(diǎn)隨數(shù)據(jù)密度的增加則較為緩慢。圖7給出了低維度數(shù)據(jù)時(shí)回溯節(jié)點(diǎn)數(shù)量與超體內(nèi)數(shù)據(jù)隨訓(xùn)練樣規(guī)模增加的變化情況，這一結(jié)論也適用于高維度數(shù)據(jù)的情形。圖8比較了數(shù)據(jù)維度的變化對(duì)回溯節(jié)點(diǎn)數(shù)與超體內(nèi)數(shù)據(jù)點(diǎn)，說明維度的總體影響較小，特別是對(duì)超體內(nèi)數(shù)據(jù)點(diǎn)的多少?zèng)]有體現(xiàn)出明顯的作用。

圖7 kd-tree回溯節(jié)點(diǎn)數(shù)與查詢超體內(nèi)數(shù)據(jù)點(diǎn)量隨訓(xùn)練集大小變化曲線（k＝3）

圖8 kd-tree回溯節(jié)點(diǎn)數(shù)與查詢超體內(nèi)數(shù)據(jù)點(diǎn)量隨數(shù)據(jù)維度的變化曲線（N＝100）

由于被查數(shù)據(jù)經(jīng)由Skd-tree索引后可獲得更小的查詢超體，包含較少的數(shù)據(jù)點(diǎn)，因此Skd-tree KNN體現(xiàn)出更好的查詢效率。圖9給出了kd-tree與Skd-tree方法查詢最近鄰數(shù)據(jù)所需時(shí)間隨樣本量的變化，表明Skd-tree有更優(yōu)良的查詢效果；Skd-tree索引樹具有更深的結(jié)構(gòu)，因此在少量樣本的時(shí)候并沒有優(yōu)勢，其查詢時(shí)間比kd-tree長，但隨著數(shù)據(jù)維度及量的增加，Skd-tree的索引優(yōu)勢則變得明顯。雖然Skd-tree隨著數(shù)據(jù)量及數(shù)據(jù)維度的增加會(huì)變得比相應(yīng)的kd-tree復(fù)雜，使得索引速度降低，但由于后繼計(jì)算量小，因此總體查詢效率更高。

圖9 kd-tree與Skd-tree方法查詢最近鄰數(shù)據(jù)所需時(shí)間隨樣本量的變化曲線（k＝3）

4 結(jié)論

針對(duì)在已有數(shù)據(jù)集中快速定位被查數(shù)據(jù)并獲取其最近鄰數(shù)據(jù)點(diǎn)的計(jì)算策略，在kd-tree的基礎(chǔ)上，研究了一種基于規(guī)則數(shù)據(jù)空間網(wǎng)格劃分的Skd-tree樹形結(jié)構(gòu)的最近鄰算法。該樹形結(jié)構(gòu)把數(shù)據(jù)置于空間網(wǎng)格內(nèi)部，能更好地利用數(shù)據(jù)的空間分布特性，可以在更小范圍內(nèi)對(duì)被查詢數(shù)據(jù)定位，有效避免對(duì)部分無關(guān)數(shù)據(jù)的計(jì)算或回溯，提高查詢效率與效果；為了適應(yīng)網(wǎng)格空間的規(guī)則性，算法中采用了正方形超體而非超球體來查詢局域空間中的最優(yōu)結(jié)果，有效避免了空間異構(gòu)帶來的不足。雖然Skd-tree較之kd-tree略顯復(fù)雜，但這一代價(jià)是值得的。數(shù)字實(shí)驗(yàn)的結(jié)果證明：Skd-tree無論在索引定位結(jié)果，還是后繼所需計(jì)算的數(shù)據(jù)點(diǎn)數(shù)量及最終查詢時(shí)間上都優(yōu)于kd-tree的結(jié)果，且尤其適用于數(shù)據(jù)樣本較大或高維度數(shù)據(jù)的最近鄰查詢。