隨著維度的增加,使用傳統(tǒng)Kd樹(shù)進(jìn)行最近鄰搜索時(shí)效率變低,查詢(xún)時(shí)間變長(zhǎng)。為了解決這個(gè)問(wèn)題,采用可學(xué)習(xí)的Kd樹(shù)(LK)方法,將待搜索的點(diǎn)輸入神經(jīng)網(wǎng)絡(luò),通過(guò)神經(jīng)網(wǎng)絡(luò)進(jìn)行定位和查找,最終輸出最近鄰點(diǎn)的索引值,從而找到最近鄰點(diǎn)。結(jié)果表明,可使用神經(jīng)網(wǎng)絡(luò)代替?zhèn)鹘y(tǒng)Kd樹(shù)進(jìn)行最近鄰查找,該方案是有效的、高效的。

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

【部分圖文】：

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

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

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

模型分為五個(gè)部分：輸入階段、映射階段、標(biāo)簽階段、索引階段、計(jì)算階段。如圖2所示。輸入階段：輸入的數(shù)據(jù)要求具有相同的維度。一般來(lái)說(shuō)，輸入的數(shù)據(jù)不應(yīng)和構(gòu)成Kd樹(shù)的任何一條數(shù)據(jù)相同。這些數(shù)據(jù)可以直接輸入神經(jīng)網(wǎng)絡(luò)而不需要進(jìn)行額外的處理。如果是圖片或者音頻，則需要進(jìn)行數(shù)據(jù)的轉(zhuǎn)化才能輸入神經(jīng)....

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

在進(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，在1000條數(shù)據(jù)和10000條數(shù)據(jù)的情況下來(lái)進(jìn)行實(shí)驗(yàn)觀察（都為符合正態(tài)分布的隨機(jī)數(shù)）。首先在神經(jīng)網(wǎng)絡(luò)層數(shù)相同，維度分別為10,15,20,....

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

圖4展示了搜索時(shí)間和維度、閾值的關(guān)系。其中圖4(a)，圖4(b)，圖4(c)分別是神經(jīng)網(wǎng)絡(luò)層數(shù)為5,n為10000，維度分別為10,20,30維的結(jié)果。橫坐標(biāo)為不同的閾值，縱坐標(biāo)為所用的時(shí)間。觀察相同維度下運(yùn)行時(shí)間的變化，可以發(fā)現(xiàn)，運(yùn)行時(shí)間隨著閾值的變大而減少。閾值設(shè)置的越小，....

本文編號(hào)：3936310