一種基于數據空間自適應規則網格劃分的Skd-tree最近鄰算法

王榮秀，王 波

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

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

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

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

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

1 kd-tree與KNN算法原理

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

算法 kd-tree索引樹的構建

輸入：k維數據

輸出：kd-tree索引樹

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

步驟2以具有第i維中值的數據作為根節點，將第i維值小于此中值的數據劃分至左子樹，第i維值大于此中值的數據劃分至右子樹。

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

步驟4由此不斷遞歸分叉，直至每個節點只剩下一個數據。

作為簡單的例子，以k＝2的輸入數據（x，y）來說明kd-tree的構建方法。設輸入數據分別為：（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）。其中數據在x維和y維的方差為3.479 6和2.448 1，因此選x作為第一分裂屬性。數據在x維上的中位數為4.659 9，因此將數值（4.659 9，6.721 4）作為根結點。然后，依據數據在x維上的大小，把小于4.659 9的數據劃分至左邊子樹；把大于4.659 9的數據劃分至右邊子樹。在左子樹中，有2個數據（4.451 0，5.251 5）和（0.1527 4，4.186 5），此時只能選取y為分裂屬性，任取一數，如5.251 5，作為新的子節點，再分裂為左右子樹，并以些類推。最后得到的樹型結構如圖1（a）所示。

圖1 kd-tree的樹型索引結構及其對空間的劃分

從數據的空間結構來看，kd-tree的構建過程實質上就是利用數據的空間分布，用不同的超平面把數據空間分割成形狀不一的超長方體結構，而每一個超平面上有且僅有一個數據位于其中，因此每一個超平面對應著索引樹中的一個節點。

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

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

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

圖2 基于kd-tree的最近鄰數據查詢

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

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

2 規則網格下的kd-tree KNN算法

2.1 基本思想與查詢超體

規則網格的基本思想來源于坐標系對空間的劃分方式，實際上坐標系可看成是網格無限小的系統，當需要對數據進行查詢時，只需找到其相應的網格（坐標大?。┚托辛恕Ｔ诠こ虒嶋H中，網格的大小不可能做到無限小，但這種定位數據的思想卻可以應用在數據的最近鄰查找中。

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

圖3 數據的網格劃分（三角形是已知數據，圓形為被查詢數據）

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

圖4 被查數據落入空網格時的近鄰查詢

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

2.2 數據空間的方體化

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

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

圖5 原始數據空間的方體化

2.3 Skd-tree KNN算法

依據前述Skd-tree及基于查詢超體的基本思想，可以總結出規則網格劃分下的Skd-tree KNN算法（Skd-tree KNN）如下：

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

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

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

步驟2將整個超方體看成根節點，按維度順序，以超體中心坐標大小為分裂屬性，把小于此值和大于此值的數據分開，同時也是將整個超方體在各個維度上進行平分；這樣可得到k2個包含數據的網格空間，每個網格是一個節點。

步驟3 判斷由步驟2得到的各節點中是否包含數據，若為空或僅有一個數據，則作為葉子節點；若含有1個以上數據，則重復步驟2，但劃分條件為當前網格空間的中心坐標值。

步驟4 重復步驟3，并不斷遞歸，直至得到全部葉子節點（劃分的停止標準也可以是網格大小，若網格達到預定的大小時，則可停止分割，此時一個葉子節點可能包含多個數據。通常，當數據較為密集時，為了避免樹的復雜性可采用此法）。

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

步驟5為每一個葉子節點建立空間方位指數。將超方體中心看作原點，可得到每個節點所表示的空間網格中心處的坐標向量r；以劃分時“小于”為負，“大于”為正，并將各維度按順序進行的一次循環劃分視為一次，則經過l次劃分后的網格中心處坐標向量r各分量為，相應網格的邊長L則為。

步驟6 依據Skd-tree樹的索引，找到被查數據xs所處網格，記為Ωs。

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

步驟8由條件xs－d≤xi≤xs＋d確定位于查詢超體內的數據。由于d是Ωs或其父節點中與xs的最小距離，因此，當Ωs中無數據時，查詢超體中的數據應當排除Ωs父節點中的所有其他數據。位于查詢超體中的數據均來自于其相鄰網格或父節點網格，由于各網格的位置是固定的，因此只需存儲其相鄰的非空網格的編號，即可快速獲得位于超體內的數據，而付出的存儲代價很少。

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

一般情況下，查詢超體中的數據較少，因為每一個網格僅包含一個數據。如果被查數據xs落入數據密集區，則網格較小，從而d小，查詢超體也??；而當落入稀疏區，d雖較大，但查詢超體覆蓋的網格也大，從而所含數據少。當查詢超體中包含的數據較少時，也可不用更新算法，直接計算每一個數據，然后得到最小值即可。

3 算法實例分析

實驗環境：所有實驗在一臺I7-4700／2.4GHz／16GB的電腦上進行；所用軟件為Windows 8.0及Matlab 2018a。

實驗的基本過程：

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

②隨機選擇N個數據作為訓練樣本集，余下的M個數據作為測試集。

③依據訓練集生成kd-tree及Skd-tree。

④將M個測試數據看成被查詢數據，依次進行測試。

⑤分別記錄下索引得到的初始歐氏距離d，為得到最近鄰數據時，kd-tree中的回溯節點數據，查詢超體中包含的數據個數，計算出相應的平均值作為對比；同時記錄下由查詢開始至得出最近鄰數據所需時間。

⑥同時采用KNN計算最近鄰結果作為參照。

由于數據量N與數據維度k是影響查詢效率的2個重要因素，因此實驗中重點比較kd-tree KNN、Skd-tree KNN 2種算法在不同數據規模和維度時的查詢效率與效果。為了減少數據隨機性對結果的影響，可選擇較大的M值，本文中統一取M＝100。

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

圖6 經kd-tree與Skd-tree索引得到的初始距離d隨樣本數據量的變化及與KNN最近鄰結果曲線

回溯節點數量與查詢超體內的數據點是影響查詢效率的另一個重要指標，對計算速度起著主要的作用。隨著數據分布密度的增加，kd-ree的回溯節點數量也呈現出快速增長的趨勢；而Skd-tree由于能較精確地定位被查數據，其查詢超體中包含的數據點隨數據密度的增加則較為緩慢。圖7給出了低維度數據時回溯節點數量與超體內數據隨訓練樣規模增加的變化情況，這一結論也適用于高維度數據的情形。圖8比較了數據維度的變化對回溯節點數與超體內數據點，說明維度的總體影響較小，特別是對超體內數據點的多少沒有體現出明顯的作用。

圖7 kd-tree回溯節點數與查詢超體內數據點量隨訓練集大小變化曲線（k＝3）

圖8 kd-tree回溯節點數與查詢超體內數據點量隨數據維度的變化曲線（N＝100）

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

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

4 結論

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