基于神經(jīng)網(wǎng)絡(luò)的可學(xué)習(xí)Kd樹

彭永鑫

（云南大學(xué) 軟件學(xué)院，云南昆明 650000）

近幾十年來(lái)，高維數(shù)據(jù)在數(shù)據(jù)倉(cāng)庫(kù)、信息檢索、數(shù)據(jù)挖掘等方面的應(yīng)用越來(lái)越廣泛。Kd 樹作為一種用于查詢高維鍵值的流行算法，由于其準(zhǔn)確性高、可擴(kuò)展性強(qiáng)、查詢速度較快，通常被用來(lái)進(jìn)行多維空間關(guān)鍵數(shù)據(jù)的檢索。使用Kd樹進(jìn)行k 近鄰搜索，就是對(duì)于給定的一個(gè)查詢點(diǎn)q，需要從一個(gè)構(gòu)成Kd 樹的數(shù)據(jù)集D 里找到距離q 最近的k 個(gè)數(shù)據(jù)。當(dāng)k=1 時(shí)，就是最近鄰搜索。

使用Kd 樹在高維向量空間中進(jìn)行搜索時(shí)，由于高維向量的距離計(jì)算需要花費(fèi)相當(dāng)大的代價(jià)，使得查詢?cè)谝欢ǔ潭壬献優(yōu)榫€性搜索，極大影響了查找效率。為了減少距離的計(jì)算，提高執(zhí)行效率，目前已有很多文獻(xiàn)對(duì)此提出了不同的解決方法。這些方法能夠有效的回答低維和中維空間中的最近鄰查找問(wèn)題[1-4]，但是由于“維度災(zāi)難”[5]，依然不能很好地應(yīng)用于中高維空間的搜索。

隨著大數(shù)據(jù)和gpu 技術(shù)的繁榮，人們能夠探索更高的計(jì)算能力和更靈活的數(shù)據(jù)結(jié)構(gòu)。然而傳統(tǒng)上的數(shù)據(jù)結(jié)構(gòu)更多是為了適應(yīng)cpu 而設(shè)計(jì)的，其特點(diǎn)是按照固定的模式來(lái)組織數(shù)據(jù)，并不考慮數(shù)據(jù)的分布。如何設(shè)計(jì)高效靈活的數(shù)據(jù)結(jié)構(gòu)以降低原有模型的復(fù)雜度成為一個(gè)急需解決的問(wèn)題。神經(jīng)網(wǎng)絡(luò)經(jīng)常被用于實(shí)現(xiàn)各種復(fù)雜的功能，使用Kd 樹進(jìn)行最近鄰查找可以看作是一個(gè)分類問(wèn)題，這與神經(jīng)網(wǎng)絡(luò)完成的工作沒(méi)有本質(zhì)上的區(qū)別。因此，使用神經(jīng)網(wǎng)絡(luò)來(lái)代替Kd 樹應(yīng)該是一種具有可行性的工作。傳統(tǒng)的索引結(jié)構(gòu)是按固定的方式構(gòu)建的，而機(jī)器學(xué)習(xí)模型是在訓(xùn)練數(shù)據(jù)的基礎(chǔ)上建立的，但這兩者本質(zhì)上都是對(duì)空間位置的定位和尋找，潛在來(lái)說(shuō)神經(jīng)網(wǎng)絡(luò)和索引是具有一定聯(lián)系的。文獻(xiàn)[6]提出了一種基于機(jī)器學(xué)習(xí)的可學(xué)習(xí)索引的方法，該方法具有學(xué)習(xí)數(shù)據(jù)分布的能力。它探索了使用神經(jīng)網(wǎng)絡(luò)在一定程度上代替?zhèn)鹘y(tǒng)索引結(jié)構(gòu)的可行性，并進(jìn)一步討論了可學(xué)習(xí)哈希映射索引與傳統(tǒng)哈希映射索引之間的區(qū)別。在之前的工作[7]中，探索利用神經(jīng)網(wǎng)絡(luò)建立倒排索引，表明了無(wú)監(jiān)督的可學(xué)習(xí)索引相比傳統(tǒng)索引有著明顯的優(yōu)勢(shì)。在此基礎(chǔ)上，本文提出了基于神經(jīng)網(wǎng)絡(luò)的可學(xué)習(xí)Kd 樹模型，用于解決中高維空間中的最近鄰搜索問(wèn)題。在本文的方案中，首先構(gòu)建一棵Kd 樹，并對(duì)構(gòu)成Kd 樹的數(shù)據(jù)構(gòu)建索引。隨后通過(guò)Kd 樹找到輸入數(shù)據(jù)的最近鄰點(diǎn)，將最近鄰點(diǎn)所在的分類作為標(biāo)簽進(jìn)行訓(xùn)練。

這種基于神經(jīng)網(wǎng)絡(luò)的可學(xué)習(xí)的Kd 樹方案新穎而且可擴(kuò)展，為最近鄰查找提供了一種全新的思路。該方案使用神經(jīng)網(wǎng)絡(luò)，能夠并行的解決搜索問(wèn)題，能在更短的時(shí)間內(nèi)進(jìn)行較為精確的查找，運(yùn)行時(shí)間更具優(yōu)勢(shì)。

1 傳統(tǒng)Kd樹

傳統(tǒng)上研究人員使用Kd 樹進(jìn)行最近鄰搜索。Kd 樹是每個(gè)節(jié)點(diǎn)為一個(gè)k 維向量的二叉樹。每個(gè)非葉子節(jié)點(diǎn)可以看作一個(gè)超平面, 而這個(gè)超平面將多維空間分割為兩個(gè)子平面。在這個(gè)超平面左側(cè)的點(diǎn)被分為左子樹, 右側(cè)的點(diǎn)則被分為右子樹。決定這個(gè)超平面方向的方式如下：每個(gè) Kd 樹中的點(diǎn)都與k 維向量中的一個(gè)特定維度相關(guān)聯(lián)，而這個(gè)維度正是垂直于分割空間的超平面的軸的維度。舉個(gè)例子，如果這個(gè)軸是X 軸，那么x 的值小于決定這個(gè)超平面的點(diǎn)的剩余點(diǎn)被分到左子樹，所有x 的值大于這個(gè)點(diǎn)的被分到右子樹。

使用Kd 樹進(jìn)行最近鄰搜索方法如下：假設(shè)有一棵已經(jīng)構(gòu)建好的維度為d 的Kd 樹，對(duì)這個(gè)數(shù)據(jù)集進(jìn)行最近鄰搜索，首先，給定查詢點(diǎn)q。需要做的是從樹上找到一個(gè)節(jié)點(diǎn)o，使得點(diǎn)o 到查詢點(diǎn)q 之間的歐式距離，小于這棵樹上除點(diǎn)o 之外任意一點(diǎn)oi到q 的距離。具體做法是比較查詢點(diǎn)q 和分裂節(jié)點(diǎn)的分裂維的值，小于等于就進(jìn)入左子樹分支，等于就進(jìn)入右子樹分支直到葉子結(jié)點(diǎn)。順著二叉樹的搜索路徑進(jìn)行搜索。然后再回溯搜索路徑，并判斷搜索路徑上的結(jié)點(diǎn)的其他子結(jié)點(diǎn)空間中是否可能有距離查詢點(diǎn)更近的數(shù)據(jù)點(diǎn)，如果有可能，則需要跳到其他子結(jié)點(diǎn)空間中去搜索（將其他子結(jié)點(diǎn)加入到搜索路徑）。重復(fù)這個(gè)過(guò)程直到搜索路徑為空。其中，空間中兩個(gè)點(diǎn) x1(x11,x12,…,x1k)與 x2(x21,x22,…,x2k)間的歐氏距離 d（x1,x2）定義為：

使用傳統(tǒng)Kd 樹進(jìn)行最近鄰查找存在諸多問(wèn)題，例如占用存儲(chǔ)空間大，需要進(jìn)行大量的回溯操作等。尤其是當(dāng)數(shù)據(jù)的維度很高時(shí)，Kd樹的查找效率變得特別低，性能甚至不如線性掃描，產(chǎn)生了“維度災(zāi)難”。其他用于k 近鄰查詢的樹形結(jié)構(gòu)例如R 樹[8]，采用了空間分割的理念，其核心思想是聚合距離相近的節(jié)點(diǎn)并在樹結(jié)構(gòu)的上一層將其表示為這些節(jié)點(diǎn)的最小外接矩形，這個(gè)最小外接矩形就成為上一層的一個(gè)節(jié)點(diǎn)。因?yàn)樗泄?jié)點(diǎn)都在它們的最小外接矩形中，所以跟某個(gè)矩形不相交的查詢就一定跟這個(gè)矩形中的所有節(jié)點(diǎn)都不相交。在此基礎(chǔ)上，R* 樹[1]作為 R 樹的一種變體，提升了 R樹的性能。然而，隨著維度的升高，這些索引技術(shù)的效率會(huì)變得較低，線性掃描成為唯一可行的解決方案。在一些實(shí)際應(yīng)用中，由于并不需要嚴(yán)格查找到完全準(zhǔn)確的k 近鄰點(diǎn)，因此可以犧牲一定的搜索精度來(lái)實(shí)現(xiàn)實(shí)際的運(yùn)行時(shí)間[9-11]。在這種情況下，NN（Nearest neighbor）和 kNN 問(wèn)題分別被轉(zhuǎn)化為 ANN（Approximate nearest neighbor）和kANN 問(wèn)題。作為一種流行的 kNN 查詢方法，局部敏感哈希（LSH）[12]被廣泛使用。

2 LK模型

2.1 LK模型架構(gòu)及執(zhí)行過(guò)程

可學(xué)習(xí)的Kd 樹，本質(zhì)上是利用訓(xùn)練好的深度學(xué)習(xí)模型替換掉傳統(tǒng)Kd 樹中的搜索部分，并且，訓(xùn)練好的深度學(xué)習(xí)模型可以仍保持原有數(shù)據(jù)的局部空間不變性。所以，如何訓(xùn)練這個(gè)深度學(xué)習(xí)模型，將是模型中最重要的研究部分（如圖1 所示）。

圖1 LK 基本架構(gòu)

首先，生成一棵維度為d 的Kd 樹，這棵Kd樹由n 條數(shù)據(jù)構(gòu)成。隨后，隨機(jī)為構(gòu)成這棵Kd樹的數(shù)據(jù)從0 開始打上標(biāo)簽，則可以得到對(duì)應(yīng)的從0 開始直到n-1 一共n 個(gè)類別。訓(xùn)練的時(shí)候，將訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)輸入Kd 樹，得到最近鄰點(diǎn)，根據(jù)最近鄰點(diǎn)得到相應(yīng)的類別。最后，將這n 個(gè)類中最近鄰點(diǎn)的索引值的位置為1，其余置為0，作為訓(xùn)練集和測(cè)試集的標(biāo)簽。由于神經(jīng)網(wǎng)絡(luò)能夠?qū)臻g進(jìn)行定位和尋找，因此使用神經(jīng)網(wǎng)絡(luò)來(lái)構(gòu)建模型，用來(lái)模擬Kd 樹的結(jié)構(gòu)。神經(jīng)網(wǎng)絡(luò)的輸出值是預(yù)測(cè)到的索引值所在的位置。

模型分為五個(gè)部分：輸入階段、映射階段、標(biāo)簽階段、索引階段、計(jì)算階段。如圖2 所示。

圖2 LK 框架和執(zhí)行過(guò)程

輸入階段：輸入的數(shù)據(jù)要求具有相同的維度。一般來(lái)說(shuō)，輸入的數(shù)據(jù)不應(yīng)和構(gòu)成Kd 樹的任何一條數(shù)據(jù)相同。這些數(shù)據(jù)可以直接輸入神經(jīng)網(wǎng)絡(luò)而不需要進(jìn)行額外的處理。如果是圖片或者音頻，則需要進(jìn)行數(shù)據(jù)的轉(zhuǎn)化才能輸入神經(jīng)網(wǎng)絡(luò)。一條輸入數(shù)據(jù)為 I=（i1,…,id），其中 d 為輸入數(shù)據(jù)的維度。則整個(gè)輸入數(shù)據(jù)為I*=I1,...,Ix，其中x 為輸入數(shù)據(jù)的尺寸，I1，…，Ix中 d 值都相同。

映射階段：這個(gè)階段實(shí)現(xiàn)了傳統(tǒng)Kd 樹的查找功能。將輸入數(shù)據(jù)（假設(shè)為m 條）輸入神經(jīng)網(wǎng)絡(luò)之后，由神經(jīng)網(wǎng)絡(luò)進(jìn)行運(yùn)算處理。這是整個(gè)模型最為重要的一個(gè)階段, 由多層神經(jīng)網(wǎng)絡(luò)構(gòu)成。神經(jīng)網(wǎng)絡(luò)的層數(shù)和每一層神經(jīng)網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)會(huì)根據(jù)實(shí)驗(yàn)的結(jié)果不斷的調(diào)整，使得神經(jīng)網(wǎng)絡(luò)能夠輸出預(yù)期的結(jié)果，每一層神經(jīng)網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)可能不相同。每條數(shù)據(jù)都會(huì)輸出一個(gè)1*n 的向量。因此，整個(gè)神經(jīng)網(wǎng)絡(luò)會(huì)輸出一個(gè)m*n 的矩陣，矩陣中每個(gè)值都為一個(gè)0 到1 之間的數(shù)。

標(biāo)簽階段：在這個(gè)階段，需要對(duì)神經(jīng)網(wǎng)絡(luò)的輸出進(jìn)行處理，并不是直接輸出最近鄰點(diǎn)的位置，而是輸出可能是最近鄰點(diǎn)的位置，從而能夠從這些潛在的最近鄰中找到真正的最近鄰。不同的輸入數(shù)據(jù)，可能是最近鄰點(diǎn)的數(shù)量也不相同。本文規(guī)定，如果某個(gè)位置輸出值為1，則這個(gè)位置在Kd 樹中所對(duì)應(yīng)的點(diǎn)，就是潛在的最近鄰點(diǎn)；如果這個(gè)位置輸出值為0，這個(gè)位置就不是最近鄰點(diǎn)，在接下來(lái)的階段不需要對(duì)這個(gè)位置進(jìn)行處理。由于使用了sigmoid 激活函數(shù)，因此需要一個(gè)閾值，將分布在0 到1 之間的數(shù)轉(zhuǎn)換為0 或者1。這個(gè)階段的輸出也是一個(gè)m*n 的矩陣，矩陣中的每個(gè)值，要么為0，要么為1。

索引階段：在構(gòu)建Kd 樹的標(biāo)簽時(shí)，構(gòu)成Kd樹的每一個(gè)節(jié)點(diǎn)，都被劃分為 0，1，…，n-1 中的某個(gè)類別。因此，為了直觀展示和便于計(jì)算，可以將上個(gè)階段所輸出的值為1 的位置，轉(zhuǎn)化成與之對(duì)應(yīng)的實(shí)際的類別，即根據(jù)值為1 的位置，得到潛在最近鄰點(diǎn)的索引值。對(duì)于每一條數(shù)據(jù)I，值為1 的個(gè)數(shù)可能不同，因此得到索引值的數(shù)量也不同。這表示神經(jīng)網(wǎng)絡(luò)對(duì)于不同的輸入數(shù)據(jù)，會(huì)做出誤差不同的預(yù)測(cè)。輸出值為1 的個(gè)數(shù)越多，表示需要進(jìn)行更多次的計(jì)算，才能從潛在的最近鄰點(diǎn)中找到真實(shí)的最近鄰點(diǎn)。

計(jì)算階段：實(shí)際上，神經(jīng)網(wǎng)絡(luò)輸出的不會(huì)總是完美的得到滿足條件的最近鄰點(diǎn)，大多數(shù)情況下，需要在輸出的所有可能是最近鄰點(diǎn)的幾個(gè)點(diǎn)中，通過(guò)計(jì)算，找到真實(shí)的最近鄰點(diǎn)。因此，需要根據(jù)輸出的索引值，通過(guò)Kd 樹，得到其原本表示的數(shù)據(jù)。最后，將輸入數(shù)據(jù)I 和這幾個(gè)點(diǎn)所代表的存在于Kd 樹中的每一條數(shù)據(jù)，依次計(jì)算歐氏距離并排序，便能得到真實(shí)的最近鄰點(diǎn)。

本文中，準(zhǔn)確率是這樣定義的：假設(shè)待查詢的數(shù)據(jù)有M 條，其中有N（N≤M）條查找到了正確的最近鄰點(diǎn)，則準(zhǔn)確率為N/M×100%。

2.2 調(diào)整參數(shù)

本文中使用sigmoid 函數(shù)作為神經(jīng)網(wǎng)絡(luò)最后一層的激活函數(shù)。由于需要將所有的輸出值映射成0 或者1，而sigmoid 函數(shù)的輸出值都在0 和1 之間，所以需要確定一個(gè)閾值，將輸出劃分為0 或者1。實(shí)驗(yàn)結(jié)果表明，閾值選取的越小，準(zhǔn)確率會(huì)越高，但需要進(jìn)行查詢比較的時(shí)間就會(huì)越長(zhǎng)。極端情況下，當(dāng)閾值為0 時(shí)，幾乎所有的輸出都被置為1，這意味著基本需要將輸入數(shù)據(jù)和所有構(gòu)成Kd 樹的點(diǎn)進(jìn)行一一對(duì)比，雖然能夠達(dá)到接近百分之百的準(zhǔn)確率，但查找所耗費(fèi)的時(shí)間遠(yuǎn)超Kd 樹和線性查找沒(méi)有區(qū)別。

閾值決定了輸出中值為1 的個(gè)數(shù)，也就決定了需要進(jìn)行計(jì)算比較的次數(shù)，而計(jì)算比較的次數(shù)又決定了查找時(shí)間的長(zhǎng)短。在第3 部分中進(jìn)行了相關(guān)的實(shí)驗(yàn)，展示了閾值的選取和其他指標(biāo)的關(guān)系。

2.3 時(shí)間復(fù)雜度

Kd 樹在進(jìn)行最近鄰搜索時(shí)，首先由根結(jié)點(diǎn)從上到下找到對(duì)應(yīng)包含查詢點(diǎn)的葉子結(jié)點(diǎn)，其中要計(jì)算該區(qū)域內(nèi)的點(diǎn)到查詢點(diǎn)的最小距離（若是k 近鄰搜索，需要計(jì)算最小的k 個(gè)距離）。對(duì)于一個(gè)具有n 個(gè)節(jié)點(diǎn)的d 維Kd 樹，最近鄰查找的時(shí)間復(fù)雜度為tworst=O(d*n1-1/d)。

使用神經(jīng)網(wǎng)絡(luò)進(jìn)行最近鄰搜索是一個(gè)三次索引加上一次計(jì)算的過(guò)程，第一次是數(shù)據(jù)輸入神經(jīng)網(wǎng)絡(luò)后得到的輸出值，即Kd 樹上的點(diǎn)所對(duì)應(yīng)的索引值的位置；第二次是根據(jù)這個(gè)位置得到Kd 樹中點(diǎn)的索引值；第三次是根據(jù)這些索引值得到Kd 樹中的點(diǎn)。索引完成后，將輸入的點(diǎn)和查找到的點(diǎn)進(jìn)行一一比較，得到最近鄰。因此，時(shí)間復(fù)雜度為O(1)+O(2)+O(3)+O(4)，分別對(duì)應(yīng)了三次索引過(guò)程和計(jì)算過(guò)程。在進(jìn)行最近鄰搜索時(shí)，相對(duì)于Kd 樹需要進(jìn)行多次的計(jì)算和回溯操作，模型只需要進(jìn)行少量的計(jì)算。使用Kd 樹進(jìn)行最近鄰查詢會(huì)在計(jì)算和回溯的過(guò)程中消耗大量的時(shí)間，而使用神經(jīng)網(wǎng)絡(luò)在一定程度上代替了這個(gè)過(guò)程。當(dāng)構(gòu)成Kd 樹的數(shù)量和維度數(shù)變大時(shí)，此模型應(yīng)該會(huì)表現(xiàn)出更明顯的優(yōu)勢(shì)。

3 結(jié)果與分析

所有的實(shí)驗(yàn)均使用python 編寫的代碼在Intel（R）Core（TM）i7-4770 上完成，該機(jī)器具有3.4GHz CPU，32GB RAM 和運(yùn)行 Linux Ubuntu 12.04 的2TB 外部磁盤空間。

本文從準(zhǔn)確率和運(yùn)行時(shí)間兩個(gè)方面來(lái)評(píng)估模型。一方面將神經(jīng)網(wǎng)絡(luò)查找到的結(jié)果和傳統(tǒng)Kd 樹找到的結(jié)果進(jìn)行對(duì)比；另一方面比較兩者查找到最近鄰所需的時(shí)間。本文所使用的最近鄰點(diǎn)，都是通過(guò)傳統(tǒng)Kd 樹得到的，可以認(rèn)為使用Kd 樹進(jìn)行查找的準(zhǔn)確率為100%。

在進(jìn)行設(shè)計(jì)和分析的過(guò)程中，發(fā)現(xiàn)閾值和維度的選取會(huì)對(duì)實(shí)驗(yàn)結(jié)果產(chǎn)生較大的影響。在實(shí)驗(yàn)中，分別使用了 3 個(gè)閾值：0.001，0.005，0.01，在1 000 條數(shù)據(jù)和10 000 條數(shù)據(jù)的情況下來(lái)進(jìn)行實(shí)驗(yàn)觀察（都為符合正態(tài)分布的隨機(jī)數(shù)）。

圖3 閾值和維度對(duì)準(zhǔn)確率的影響

首先在神經(jīng)網(wǎng)絡(luò)層數(shù)相同，維度分別為10，15，20，25，30 維的情況下進(jìn)行了實(shí)驗(yàn)。最終結(jié)果為10 次實(shí)驗(yàn)結(jié)果的平均值（實(shí)驗(yàn)結(jié)果如圖3）。結(jié)果表明，當(dāng)n 為1 000 時(shí)，在相同的維度下，閾值越低，準(zhǔn)確率越高。隨著維度的升高，不管閾值如何，準(zhǔn)確率都在持續(xù)下降；而當(dāng)n 為10 000時(shí)，除了在維度為10 的情況下出現(xiàn)了異常，相同維度下，閾值越低，準(zhǔn)確率越高。同時(shí)，隨著維度的增加，準(zhǔn)確率出現(xiàn)了一定程度的波動(dòng)。當(dāng)維度為10，閾值為0.001 時(shí)，兩者的準(zhǔn)確率甚至達(dá)到了99%以上；當(dāng)維度為30 維時(shí)，可以看到，極端情況下，當(dāng)閾值為0.01 時(shí)，準(zhǔn)確率甚至?xí)陀?0%。由于只需要查找最近鄰點(diǎn)（k=1），k 的值遠(yuǎn)遠(yuǎn)小于構(gòu)成Kd 樹本身的數(shù)據(jù)量n，因此最終的預(yù)測(cè)值，值為1 的個(gè)數(shù)遠(yuǎn)遠(yuǎn)少于值為0 的個(gè)數(shù)。在神經(jīng)網(wǎng)絡(luò)的輸出中，只要輸出值不為0，便傾向于這個(gè)位置是可能的最近鄰點(diǎn)。閾值設(shè)置的越小，就會(huì)把更多潛在的最近鄰點(diǎn)包含其中，使得準(zhǔn)確率升高。一般來(lái)說(shuō)，隨著維度的升高，準(zhǔn)確率會(huì)降低；相同維度下，閾值越小，準(zhǔn)確率越高。

圖4 展示了搜索時(shí)間和維度、閾值的關(guān)系。其中圖4(a)，圖4(b)，圖4(c)分別是神經(jīng)網(wǎng)絡(luò)層數(shù)為 5，n 為 10 000，維度分別為 10，20，30 維的結(jié)果。橫坐標(biāo)為不同的閾值，縱坐標(biāo)為所用的時(shí)間。觀察相同維度下運(yùn)行時(shí)間的變化，可以發(fā)現(xiàn)，運(yùn)行時(shí)間隨著閾值的變大而減少。閾值設(shè)置的越小，就會(huì)把更多潛在的最近鄰點(diǎn)包含其中，會(huì)導(dǎo)致需要進(jìn)行更多次的計(jì)算。

圖4 閾值和維度對(duì)搜索時(shí)間的影響

本文將使用神經(jīng)網(wǎng)絡(luò)進(jìn)行最近鄰搜索的時(shí)間和使用傳統(tǒng)Kd 樹進(jìn)行最近鄰搜索所花費(fèi)的時(shí)間，在n 為10 000，閾值為0.005 的情況下進(jìn)行了對(duì)比，此時(shí)，由圖3b 可知，模型的準(zhǔn)確率均在90%以上。兩者的運(yùn)行時(shí)間如表1。從表1 可以看出，相比于傳統(tǒng)的Kd 樹，LK 模型在運(yùn)行時(shí)間上更具優(yōu)勢(shì)。

表1 運(yùn)行時(shí)間對(duì)比

4 結(jié)論

本文解決了在實(shí)際計(jì)算時(shí)間內(nèi)的最鄰搜索的問(wèn)題，同時(shí)表現(xiàn)出了較高的質(zhì)量。總的來(lái)說(shuō)，在應(yīng)用中，根據(jù)不同的需求，需要在準(zhǔn)確率和運(yùn)行時(shí)間上做出取舍?？梢缘玫剑耗Ｐ偷臏?zhǔn)確率隨著閾值的增加而降低，但與此同時(shí)，運(yùn)行時(shí)間也在減少。在搜索中，如果需要更高的準(zhǔn)確率，那么就需要花費(fèi)更多的時(shí)間，但在一定的情況下，所用的時(shí)間也會(huì)比傳統(tǒng)的Kd 樹花費(fèi)的時(shí)間更少；如果對(duì)結(jié)果要求不是非常精確，那么此模型就會(huì)具有更大的時(shí)間優(yōu)勢(shì)。未來(lái)，將繼續(xù)研究如何在更高的維度、更多的數(shù)據(jù)量上取得更好的實(shí)驗(yàn)效果。