楊鳳麗,李 娜,劉仁芬
(石家莊鐵道大學(xué)四方學(xué)院,河北 石家莊051132)
當(dāng)前網(wǎng)絡(luò)平臺(tái)上的文本、視頻等多媒體數(shù)據(jù)量持續(xù)上升,例如雅虎網(wǎng)站的日交換信息量高達(dá)30億條,某相簿共享網(wǎng)站包含超過50億張的圖片,且每日仍保持較高的圖片上傳速率。這些數(shù)據(jù)包含很多具有科學(xué)價(jià)值與應(yīng)用價(jià)值的信息。在此背景下,網(wǎng)絡(luò)海量數(shù)據(jù)的安全維護(hù)極為重要。但是由于此類數(shù)據(jù)具有高維、異構(gòu)等特點(diǎn),使數(shù)據(jù)的最近鄰查詢成為難點(diǎn)問題[1,2]。
關(guān)于高維數(shù)據(jù)近似最近鄰搜索,很多專家學(xué)者已經(jīng)得到了一些研究成果,例如劉恒等人[3]通過量化編碼實(shí)現(xiàn)高維數(shù)據(jù)近似最近鄰搜索,該算法搜索性能優(yōu)越,且時(shí)間成本低,但內(nèi)存消耗較大;劉晨赫等人[4]通過動(dòng)態(tài)網(wǎng)格子空間實(shí)現(xiàn)高維數(shù)據(jù)近似最近鄰搜索,該算法復(fù)雜度較低,能有效避免有效數(shù)據(jù)丟失,但數(shù)據(jù)維數(shù)較高時(shí)的搜索性能仍不夠理想。
哈希搜索的精確、高效性,使其逐步發(fā)展為近似最近鄰查詢問題的有效方法之一,對(duì)于高維數(shù)據(jù)近似最近鄰搜索,距離敏感哈希算法運(yùn)用廣泛,為優(yōu)化該算法存在的搜索穩(wěn)定性較差問題,引入能將若干索引方法組合使用的多級(jí)索引方法,提出基于多級(jí)索引的高維數(shù)據(jù)近似最近鄰搜索算法,通過二級(jí)距離敏感哈希,實(shí)現(xiàn)高維數(shù)據(jù)近似最近鄰搜索。
近似最近鄰查詢?cè)诟呔S數(shù)據(jù)處理中運(yùn)用廣泛,數(shù)據(jù)集和查詢點(diǎn)定義同上,近似比率用c描述,且c大于1,該查詢將向量p∈D作為返回結(jié)果,可使dist(p,q)≤c×dist(p*,q)成立,q的最近鄰用p*描述。
距離敏感哈希(Locality-Sensitive Hashing,LSH)算法是高維數(shù)據(jù)近似最近鄰搜索方面極具代表性的算法,若要檢測(cè)出相似數(shù)據(jù)點(diǎn),可通過任意哈希函數(shù)值使其以極高的幾率出現(xiàn)沖突[5,6]。
哈希函數(shù)在該算法中符合式(1)所示條件,它屬于單向映射函數(shù)
Prh∈H[h(u)=h(v)]=sim(u,v)
(1)
式中,相似度函數(shù)用sim(u,v)∈[0,1]描述;哈希函數(shù)簇用H描述;哈希函數(shù)用h描述,其以均勻方式自H內(nèi)選擇;兩個(gè)不同數(shù)據(jù)點(diǎn)用u、v描述;
式(2)描述了利用隨機(jī)投影法獲得的哈希函數(shù)表達(dá)式
(2)
式內(nèi),矢量用r描述,其各元素符合正態(tài)分布[7],在超平面內(nèi),數(shù)據(jù)點(diǎn)u的位置決定著哈希函數(shù)取值,設(shè)定u1、u2表示數(shù)據(jù)點(diǎn),兩者滿足式(3)所示表達(dá)式
(3)
任意方向矢量用ai描述,以p平穩(wěn)分布為基礎(chǔ)的哈希函數(shù)用{h:Rd→Z}描述,關(guān)于數(shù)據(jù)庫(kù)內(nèi)矢量點(diǎn),通過該哈希函數(shù)將其投影至ai上,該矢量的各元素符合p平穩(wěn)分布,其中,若呈現(xiàn)柯西分布,那么p值為1,若呈現(xiàn)標(biāo)準(zhǔn)高斯分布,那么p值為2。對(duì)于兩個(gè)變量,如果其線性組合滿足p平穩(wěn)分布,則是在兩者均滿足p平穩(wěn)分布的條件下。{h:Rd→Z}的計(jì)算過程用式(4)描述
(4)
式內(nèi),位于ai上,數(shù)據(jù)點(diǎn)v的投影用ai·v描述;投影窗口的量化寬度用w描述;參數(shù)用b描述,其值符合[0,w]的均勻分布,能極大地提高哈希函數(shù)的隨機(jī)性[8];取整處理用? 」描述。設(shè)定v1、v2表示數(shù)據(jù)點(diǎn),兩者滿足式(5)所示表達(dá)式
p(c)=Pr(ha,b(v1)=ha,b(v2))
(5)
設(shè)定hi為單個(gè)哈希函數(shù),由于hi不具備較強(qiáng)的區(qū)分能力,建立如式(6)描述的第二級(jí)哈希函數(shù):
gj(v)={hj,1(v),…,hj,k(v)}j=1,…,l
(6)
式內(nèi),對(duì)于數(shù)據(jù)點(diǎn)v,其哈希碼為利用k個(gè)整數(shù)組建的矢量,LSH函數(shù)簇用G={g:Rd→Zk}描述。
處理分布不均勻的高維數(shù)據(jù)時(shí),易造成索引文件中的哈希桶所存儲(chǔ)的數(shù)據(jù)出現(xiàn)數(shù)量不均衡現(xiàn)象,導(dǎo)致返回結(jié)果個(gè)數(shù)過多或過少,從而影響LSH算法的搜索穩(wěn)定性,因此使用二級(jí)距離敏感哈希(M2LSH)實(shí)現(xiàn)高維數(shù)據(jù)近似最近鄰搜索,使候選集盡量減少,提升算法的搜索精度和效率。
將索引創(chuàng)建在單個(gè)哈希表內(nèi)的步驟用圖1描述。
圖1 創(chuàng)建索引過程
組合哈希向量代表哈希桶,用于放置原始高維數(shù)據(jù),設(shè)定對(duì)象o,對(duì)其實(shí)施組合哈希處理,并放進(jìn)與gi(o)=〈h1(o),h2(o),…,hk1(o)〉匹配的哈希桶內(nèi)。桶寬用w描述,其值較小,將計(jì)數(shù)器Counter設(shè)定于各組合哈希桶內(nèi),能對(duì)桶內(nèi)對(duì)象數(shù)量進(jìn)行記錄[9,10]。
1)索引創(chuàng)建。
(a)使用哈希桶存儲(chǔ)高維數(shù)據(jù),以(h1(o),h2(o),…,hk1(o),1)描述各數(shù)據(jù)對(duì)象o完成gi(·)操作的形式,通過AND過程,對(duì)象o需放置的組合哈希桶號(hào)用o′描述,表示為(h1(o),h1(o),…,hk1(o)),計(jì)數(shù)器用1描述。
(b)若想為合并上步中獲取的組合哈希桶號(hào)做準(zhǔn)備,可以通過二次哈希對(duì)其進(jìn)行處理并投影至一條線上,利用該操作,能夠重新排列桶號(hào),分配鄰近的哈希桶號(hào)至鄰近地點(diǎn)。
關(guān)于索引創(chuàng)建過程,需構(gòu)建的g(·)數(shù)量用i描述,且i=1,2,…,L,各g(·)和索引文件相匹配。
以下為桶合并實(shí)現(xiàn)過程:
Input Line (the second hashes)
Compute the AC
Set flag=0
Foreach i=1,…,k2
For j=1,…,length of Sortedlinei
If((count+=getCount(bucketID of linei))/(average count)<ρ&&dist(bucketID of current bucketID) Flagi[bucketID]=flag Else 在上述桶合并過程中,AC為高維數(shù)據(jù)總數(shù)與組合哈希桶數(shù)量的比值;待合并桶數(shù)量和AC的比值用ρ描述,通常取值為1.5;待合并桶距離限制用cs描述;二級(jí)哈希內(nèi)各線的桶號(hào)標(biāo)記用Flagi描述;在0-1范圍中,flag的變動(dòng)形式用flag描述。 2)搜索階段。 搜索對(duì)象用q描述,組合哈希向量用q′描述,可通過一次哈希形成,q′投影到直線的地點(diǎn),可在實(shí)現(xiàn)二次哈希的基礎(chǔ)上獲得,查找直線中和q′擁有同樣標(biāo)記的桶號(hào),并將桶內(nèi)數(shù)據(jù)當(dāng)作搜索對(duì)象的候選搜索集合[12]。 (b)桶號(hào)o′(〈5,7,3,1〉,100),表示通過AND過程后q的所得結(jié)果,則無(wú)須實(shí)現(xiàn)二次哈希,可將該桶內(nèi)數(shù)據(jù)直接當(dāng)作搜索對(duì)象的候選集。 (c)如果搜索對(duì)象完成一次哈希后,所得桶號(hào)內(nèi)僅存在極少的數(shù)據(jù),且實(shí)現(xiàn)二次哈希后,未找到擁有同樣標(biāo)記的其余桶,則是哈希函數(shù)出現(xiàn)問題,利用OR過程即可彌補(bǔ)。 高維數(shù)據(jù)一般由視頻、圖片等非結(jié)構(gòu)化數(shù)據(jù)生成,選擇五個(gè)大小與維度均存在差異的實(shí)際高維數(shù)據(jù)集,以及一個(gè)人造數(shù)據(jù)集作為實(shí)驗(yàn)對(duì)象,使用本文算法實(shí)現(xiàn)高維數(shù)據(jù)近似最近鄰搜索,以驗(yàn)證該算法的搜索性能,數(shù)據(jù)集詳情用表1描述。 表1 數(shù)據(jù)集詳情 使用近似比率(Ratio)評(píng)價(jià)搜索算法的性能,它表示近似和真實(shí)最近鄰的比值,其值與1越貼近,表明算法的搜索性能越優(yōu)異。 將合并哈希桶數(shù)量設(shè)定成5,哈希桶寬設(shè)定成1,測(cè)試不同相鄰?fù)熬嚯x(閾值ρ)下,傳統(tǒng)LSH算法和改進(jìn)的M2LSH算法的高維數(shù)據(jù)近似最近鄰搜索效果,所得Ratio結(jié)果用圖2描述。 分析圖2可以看出,LSH算法和M2LSH算法的近似比率均隨著相鄰?fù)熬嚯x增加而降低;LSH算法的近似比率下降趨勢(shì)明顯,最大近似比率約為0.75,當(dāng)相鄰?fù)熬嚯x增加至20時(shí),近似比率已降低至0.21;當(dāng)相鄰?fù)熬嚯x小于等于16時(shí),M2LSH算法的近似比率保持在1左右,當(dāng)相鄰?fù)熬嚯x增加至20時(shí),其最小近似比率與LSH算法的最大近似比率較為接近。對(duì)比以上結(jié)果可得,相鄰?fù)熬嚯x對(duì)算法的搜索性能影響較大,本文算法優(yōu)化后的高維數(shù)據(jù)近似最近鄰搜索效果大幅度提升,且穩(wěn)定性較好。 選取報(bào)表數(shù)據(jù)集完成搜索測(cè)試,將其規(guī)模設(shè)定為100,哈希桶寬度設(shè)置為1、2、3、4,分析不同哈希函數(shù)數(shù)量下,各哈希桶寬度對(duì)數(shù)據(jù)集搜索近似比率的影響,結(jié)果如圖3。 圖3 哈希函數(shù)數(shù)量和哈希桶寬度對(duì)搜索近似比率的影響 分析圖3可以看出,隨著哈希函數(shù)數(shù)量增加,不同哈希桶寬度對(duì)應(yīng)的近似比率均呈上升趨勢(shì);在哈希函數(shù)數(shù)量小于12的情況下,近似比率上升速率較快,在超過12后逐漸趨于固定值;當(dāng)哈希函數(shù)數(shù)量為2時(shí),不同哈希桶寬度的近似比率較為接近,當(dāng)哈希函數(shù)數(shù)量小于8時(shí),哈希桶寬度為1的近似比率始終保持最高,當(dāng)哈希函數(shù)數(shù)量大于8時(shí),哈希桶寬度為3的近似比率處于最高數(shù)值,且仍有上升跡象。對(duì)比這些數(shù)據(jù)表明,哈希函數(shù)數(shù)量和哈希桶寬度對(duì)高維數(shù)據(jù)近似最近鄰搜索具有較大影響,將兩參數(shù)分別設(shè)置為12、3,不僅能獲得更優(yōu)異的搜索效果,還能極大地節(jié)省時(shí)間開銷,無(wú)需持續(xù)增加哈希函數(shù)數(shù)量。 引入實(shí)際搜索代價(jià)評(píng)價(jià)本文算法的搜索能力,其值越低,表明算法的搜索效果越理想。將哈希表數(shù)量分別設(shè)定成2、4、6、8,測(cè)試本文算法搜索表1中不同數(shù)據(jù)集獲得的實(shí)際搜索代價(jià),結(jié)果用圖4描述。 圖4 不同數(shù)據(jù)集的實(shí)際搜索代價(jià) 分析圖4可以發(fā)現(xiàn),在哈希表數(shù)量不斷增長(zhǎng)的情況下,使用本文算法搜索不同數(shù)據(jù)集獲得的實(shí)際搜索代價(jià)均隨之降低,表明增加哈希表數(shù)量能夠提升高維數(shù)據(jù)近似最近鄰搜索效果;當(dāng)哈希表數(shù)量從2增長(zhǎng)至6時(shí),各數(shù)據(jù)集對(duì)應(yīng)的實(shí)際搜索代價(jià)下降幅度較大,當(dāng)哈希表數(shù)量從6增長(zhǎng)至8時(shí),實(shí)際搜索代價(jià)下降速率顯著減緩,表明在哈希表數(shù)量增長(zhǎng)至一定程度后,對(duì)本文算法搜索效果的促進(jìn)作用會(huì)逐步減小。 研究基于多級(jí)索引的高維數(shù)據(jù)近似最近鄰搜索算法,在原有距離敏感哈希算法的基礎(chǔ)上,提出二級(jí)距離敏感哈希算法,實(shí)現(xiàn)高維數(shù)據(jù)近似最近鄰精確、穩(wěn)定搜索。 為驗(yàn)證所提算法的有效性,設(shè)計(jì)仿真驗(yàn)證其應(yīng)用有效性。通過不同參數(shù)的設(shè)定,驗(yàn)證該算法的搜索效果,以便采取針對(duì)性方案優(yōu)化算法整體性能。根據(jù)所得的實(shí)驗(yàn)結(jié)果可知,該算法優(yōu)化后的搜索效果大幅度提升,且穩(wěn)定性較高。且該算法適用性極強(qiáng),可為各類檢測(cè)、辨識(shí)、預(yù)警等技術(shù)領(lǐng)域提供借鑒。3 結(jié)果分析
4 結(jié)論