最近鄰搜索作為一個基礎(chǔ)性問題,廣泛出現(xiàn)在數(shù)據(jù)庫、機(jī)器學(xué)習(xí)、計算機(jī)視覺和信息檢索等領(lǐng)域。最近鄰搜索問題可以被簡單定義為,給定查詢向量和n個同維的候選向量,要求返回某種距離度量方式下距離查詢向量最近的一個或多個候選向量。在許多現(xiàn)實應(yīng)用中,精確算法往往需要高昂的時間和空間代價,而近似最近鄰搜索則以犧牲一定的準(zhǔn)確率為代價,顯著地降低了對存儲空間和查詢時間的要求。近似最近鄰搜索因其實用性,受到了廣泛關(guān)注,許多算法相繼被提出,包括基于空間分割、基于哈希、基于向量量化和基于近鄰圖四類算法。然而目前還沒有通用的亞線性時間復(fù)雜度的近似最近鄰搜索算法。在大數(shù)據(jù)時代,設(shè)計高質(zhì)、高效的近似最近鄰搜索算法具有重要的理論意義和實用價值�；冢ń疲﹌-近鄰圖（k-NX圖）的近似最近鄰搜索算法是當(dāng)前的主流算法,一般包括兩個步驟:一是對候選向量離線構(gòu)造k-NN圖,二是基于k-NN圖采用某種搜索策略返回查詢結(jié)果。k-NN圖的質(zhì)量和搜索策略極大地影響了算法的效果和效率。本文對k-NN圖的構(gòu)造,以及爬山搜索（GNNS）算法做了改進(jìn)。主要結(jié)果有:（1）發(fā)現(xiàn)爬山搜索算法存在冗余計算、收斂速度慢,提出一種改進(jìn)的爬山搜索（E-GN... 

【文章來源】：廈門大學(xué)福建省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：75 頁

【學(xué)位級別】：碩士

【部分圖文】：

圖２．１隨機(jī)Ｋ－Ｄ樹

圖２．２?ｋ－ｍｅａｎｓ樹

⑷??Ｇ在二維情況下的一個例子，距離最近的兩個鄰居是〃３和棄ｆｌ４，而將點６加入到ｐ的近鄰列表。（參考文獻(xiàn)Ｉ５１］）??個子集里，點對之間的平均角度是最大的。然而，這是一ＤＰＧ中提出了一個更簡單的貪心啟發(fā)式方法。開始的時候中選擇的最近的ｆ?zhèn)�點。在接下來的次迭代中，當(dāng)中，能夠使得Ｓ中的點的平均角度相似性更小時，就移動的每一個點《，在差異化相似圖中加入邊（ＰＡ）和（《，ｐ）。差＇


本文編號：2968432