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

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

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

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

【部分圖文】：

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

圖２．２?ｋ－ｍｅａｎｓ樹(shù)

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


本文編號(hào)：2968432