區(qū)塊鏈環(huán)境中基于局部敏感哈希的協(xié)同過濾推薦研究*

汪 靜，錢曉東

(蘭州交通大學(xué)經(jīng)濟(jì)管理學(xué)院，甘肅 蘭州730070)

1 引言

隨著數(shù)據(jù)的爆發(fā)式增長，數(shù)據(jù)挖掘的難度隨之提高，導(dǎo)致數(shù)據(jù)使用者無法準(zhǔn)確地獲取想要的信息[1]，于是推薦系統(tǒng)RS(Recommendation System)應(yīng)運而生。RS通過分析用戶的歷史數(shù)據(jù)，推斷出用戶的潛在偏好，并據(jù)此進(jìn)行準(zhǔn)確的推薦。然而，推薦系統(tǒng)在某種程度上缺乏對用戶信息的安全控制，違規(guī)違法使用個人信息的問題突出。目前，一個比較熱門的思想是結(jié)合區(qū)塊鏈和星際文件系統(tǒng)IPFS(Inter Planetary File System)來實現(xiàn)隱私保護(hù)，防止數(shù)據(jù)泄露。

IPFS是一種點對點的分布式文件系統(tǒng)，可以提供高吞吐量的內(nèi)容尋址塊存儲模型[2]。Zheng等[3]提出了一種基于IPFS的區(qū)塊鏈數(shù)據(jù)存儲模型，在該模型中，礦工將交易數(shù)據(jù)存儲到IPFS網(wǎng)絡(luò)中，并將返回的交易IPFS哈希打包到區(qū)塊中，大大減少了區(qū)塊鏈數(shù)據(jù)。IPFS和區(qū)塊鏈的結(jié)合，使得用戶可以通過IPFS來處理大量數(shù)據(jù)，而不需要將數(shù)據(jù)本身存放在區(qū)塊鏈中，只需將對應(yīng)的加密哈希存儲到區(qū)塊鏈中并標(biāo)記時間戳，這彌補(bǔ)了現(xiàn)有區(qū)塊鏈系統(tǒng)在文件存儲方面的短板。兩者結(jié)合，可以很好地融合IPFS的永久文件存儲和區(qū)塊鏈的不可篡改、時間戳證明特性，能夠滿足分布式對等網(wǎng)絡(luò)中各種用戶的需求[4]。然而，由于區(qū)塊鏈的開銷隱含在交易和驗證中，而推薦系統(tǒng)需要在對等體之間不斷進(jìn)行交互，從而在分散的環(huán)境中收集數(shù)據(jù)，其開銷體現(xiàn)在實際的計算中，由此導(dǎo)致在區(qū)塊鏈環(huán)境中進(jìn)行推薦的效率較低[5]。同時，IPFS+區(qū)塊鏈的使用也使得數(shù)據(jù)具有維度高、規(guī)模大和類型種類多的特點[6]。傳統(tǒng)的近鄰協(xié)同過濾推薦模型已經(jīng)無法適應(yīng)于這種環(huán)境，推薦效率不盡人意。

為了解決IPFS+區(qū)塊鏈的環(huán)境中，RS效率低下，以及數(shù)據(jù)量大、維度高的問題，本文提出使用基于局部敏感哈希LSH(Locality Sensitive Hashing)進(jìn)行協(xié)同過濾的推薦算法。本文在研究傳統(tǒng)基于近鄰的協(xié)同過濾技術(shù)基礎(chǔ)上，使用優(yōu)化后的LSH算法來獲取用戶的近鄰集合，然后基于近鄰用戶集合的評分預(yù)測實現(xiàn)協(xié)同過濾推薦。該算法能夠有效解決在IPFS+區(qū)塊鏈環(huán)境中用戶評分?jǐn)?shù)據(jù)維度高、規(guī)模大而造成推薦效率低下的問題。

2 相關(guān)研究

2.1 關(guān)于區(qū)塊鏈環(huán)境中的推薦研究

如今，RS的廣泛應(yīng)用在為企業(yè)和用戶帶來利益和便利的同時也缺乏對用戶隱私的保護(hù)。雖然當(dāng)前的一些法律法規(guī)要求服務(wù)提供商正確處理數(shù)據(jù)并確保用戶的隱私，但Alneyadi等[7]通過調(diào)查指出僅靠立法并不能防止數(shù)據(jù)泄露，起到保護(hù)隱私的作用。因此，從推薦系統(tǒng)自身出發(fā)，確保其安全性成為當(dāng)今學(xué)術(shù)界的一個研究熱點。

區(qū)塊鏈在協(xié)同過濾推薦文獻(xiàn)中創(chuàng)建了一個新的范例，由于其固有的匿名、去中心化和不可篡改等特性，使過去無法實現(xiàn)的隱私保護(hù)成為可能?，F(xiàn)有的基于區(qū)塊鏈的RS主要是利用區(qū)塊鏈安全和可驗證存儲的特點，達(dá)到在保持通信的同時降低計算成本的目的。Frey等[8]提出了一種基于區(qū)塊鏈的RS，利用區(qū)塊鏈基礎(chǔ)架構(gòu)解決RS中的隱私問題。作者聲稱他們?yōu)镽S中的客戶隱私提供了加密保證，因為原始數(shù)據(jù)只能被所有者訪問。然而，他們僅是將區(qū)塊鏈用作黑匣子，并沒有進(jìn)行有關(guān)架構(gòu)的實驗。Lisi等[9]提出了一個基于區(qū)塊鏈的智能合約框架，并將該框架用作RS的外部模塊，該方法可在一定程度上提高RS的透明性，防止大規(guī)模的負(fù)面評論攻擊，但并不能防止消費者與商家之間的串通。

總體來說，目前針對區(qū)塊鏈環(huán)境中的推薦研究還十分有限，大多都僅僅是提出了一些思路或運用了區(qū)塊鏈的某一個特性，未進(jìn)行深入研究，且都未解決在區(qū)塊鏈環(huán)境中進(jìn)行推薦所面臨的效率低下以及數(shù)據(jù)規(guī)模大、維度高的問題。

2.2 關(guān)于局部敏感哈希的推薦研究

局部敏感哈希[10]是一種用于解決高維空間中近似近鄰搜索的算法。Matsushita等[11]指出近似近鄰搜索策略和最近鄰策略相比，可以在保證一定準(zhǔn)確性的情況下及時提供查詢結(jié)果，避免大量資源的浪費，而LSH可以維護(hù)數(shù)據(jù)的局部性并支持近似近鄰搜索。利用LSH來進(jìn)行區(qū)塊鏈環(huán)境中的近似近鄰搜索具有很多優(yōu)勢。區(qū)塊鏈環(huán)境中的項目數(shù)和用戶數(shù)的快速增長以及數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系，使得RS所需要的數(shù)據(jù)維數(shù)增加。而基于LSH的方法處理高維數(shù)據(jù)具有較好的性能，同時該方法不需要維護(hù)全局信息，便于在分布式環(huán)境中實現(xiàn),可以很好地適應(yīng)區(qū)塊鏈環(huán)境。

基于LSH面向區(qū)塊鏈環(huán)境中的數(shù)據(jù)進(jìn)行協(xié)同過濾推薦的關(guān)鍵點在于如何在降低額外的計算和存儲開銷的情況下，保證近似近鄰搜索的高性能。在以往的研究中，Datar等[12]在局部靈敏哈希索引方法的基礎(chǔ)上改進(jìn)哈希計算的運行時間，從而可以無需嵌入即可在歐氏空間中的點上計算。Andoni等[13]提出了一種用于高維歐氏空間的近似近鄰搜索算法，減少了查詢時間和索引空間的開銷。上述算法可以快速生成哈希函數(shù)，但是這些算法的哈希編碼具有概率性，且分辨能力較低。He等[14]提出了一種可擴(kuò)展哈希算法，為具有任何相似性函數(shù)的數(shù)據(jù)生成緊湊的哈希編碼，嘗試在保持?jǐn)?shù)據(jù)相似性的同時，減少冗余的投影，從而優(yōu)化搜索時間。以上算法都表明，要高效地獲取近鄰集合重點在加強(qiáng)LSH中哈希函數(shù)的相似度保持能力和獨立性。此外，還有很多從不同角度提高LSH搜索性能的算法，如多比特[15]、多哈希表[16]和多探針[17]等算法。

以上算法從各個角度出發(fā)，都在不同程度上提高了LSH的搜索性能，但據(jù)了解目前還沒有文獻(xiàn)針對區(qū)塊鏈環(huán)境中的LSH作出研究。區(qū)塊鏈環(huán)境對LSH近似近鄰搜索的效率和性能提出了更高的要求，并且其數(shù)據(jù)的高維特性也對協(xié)同過濾推薦算法提出了挑戰(zhàn)。在傳統(tǒng)LSH算法中，哈希函數(shù)的參數(shù)往往隨機(jī)設(shè)置，從而需要使用大量的哈希表以保證查詢的準(zhǔn)確性，在區(qū)塊鏈環(huán)境中便會增加存儲和計算的開銷。因此，本文在LSH的基礎(chǔ)上，研究區(qū)塊鏈環(huán)境中基于LSH的協(xié)同過濾推薦，將數(shù)據(jù)分布的主成分作為LSH機(jī)制中哈希函數(shù)的投影向量，量化每個哈希函數(shù)的權(quán)重；通過對哈希桶的間隔進(jìn)行調(diào)整，并且根據(jù)沖突次數(shù)的大小進(jìn)一步細(xì)化查詢結(jié)果集，從而提高空間效率并在較少查詢時延的同時保證查詢準(zhǔn)確性，然后采用加權(quán)方法預(yù)測評分，進(jìn)而產(chǎn)生推薦結(jié)果。

3 基于LSH的近似近鄰搜索分析

3.1 LSH近似近鄰搜索算法

LSH是當(dāng)前備受關(guān)注的近似近鄰搜索技術(shù)，可以較好地解決傳統(tǒng)近鄰搜索存在的“維災(zāi)”問題，同時在很大程度上降低了近鄰協(xié)同過濾的計算量。LSH的思想是將相似的對象以較大的概率哈希到同一個“桶”中，從而快速獲取近鄰對象。給定檢索半徑r和近似比例c(c=1+ε)，ε為松弛變量且ε>0，假設(shè)U是哈希值的集合，O是數(shù)據(jù)對象的集合，且O?RD(RD為歐氏空間)，u,v∈O，D(u,v)表示數(shù)據(jù)對象u和v之間的距離，H={h:O→U}是哈希函數(shù)的集合，對于?u,v∈O有：

(1)如果D(u,v)≤r1，那么Pr[h(u)=h(v)]≥p1；

(2)如果D(u,v)≥r2，那么Pr[h(u)=h(v)]≤p2；

其中，Pr[·]是概率函數(shù)，表示u,v哈希值相等的概率，r1(r1=r)p2，則這個LSH函數(shù)集被稱為(r1,r2,p1,p2)-敏感的LSH。

為了直接處理歐氏距離，研究者提出了基于p-穩(wěn)態(tài)分布(p-stable Distribution)的LSH[12]。

基于p-穩(wěn)態(tài)分布的哈希函數(shù)族的定義如式(1)所示：

(1)

設(shè)fp(t)代表p-穩(wěn)態(tài)分布的概率密度函數(shù)的絕對值，定義d=‖v1-v2‖p,那么向量v1,v2被映射到一個隨機(jī)向量a上的距離是|a·v1-a·v2|

p(d)=Pr[ha,b(v1)=ha,b(v2)]=

(2)

根據(jù)式(2)可以看出,對于固定的W，2個向量的沖突概率隨著距離d的增加而減小。

LSH將數(shù)據(jù)集從高維空間投影到低維空間，認(rèn)為在高維空間中相近的點在隨機(jī)投影中的位置也相近。但是，由圖1可以看出，u為隨機(jī)投影方向，將數(shù)據(jù)點從二維空間投影到一維空間，查詢點o1的最近鄰點由o3變成了o2。因此，在實際應(yīng)用中，需要考慮使用一組函數(shù)而非單個函數(shù)進(jìn)行比較。G={g:RD→Uk}是一組復(fù)合LSH函數(shù)，其中?gi∈G由H中隨機(jī)選擇的k個哈希函數(shù)序列組成，即：

gi(o)={hi1(o),hi2(o),…,hik(o)}

(3)

其中，hij都是從H中獨立且隨機(jī)地選取的。

Figure 1 A point set in a bad projection direction

3.2 算法分析

傳統(tǒng)近鄰搜索的主要方法是基于空間劃分的算法，如R樹、k-d樹(k-dimensional樹)。這些算法雖然可以得到精確的查詢結(jié)果，但在高維數(shù)據(jù)集上的效率卻尤其低下。Weber等[18]通過實驗證明，在維度高于10之后，基于空間劃分的搜索技術(shù)都退化為線性搜索。傳統(tǒng)近鄰搜索方法通常無法適應(yīng)區(qū)塊鏈環(huán)境中的數(shù)據(jù)維數(shù)高、規(guī)模大的特點，而近似近鄰搜索可以很好地解決這一問題。雖然近似近鄰搜索犧牲了一部分精確度，但其通常能在很小的時間復(fù)雜度下得到近似精確甚至精確的搜索結(jié)果，這更能滿足區(qū)塊鏈環(huán)境的實際需求。

Dater等[12]通過實驗證明了處理高維數(shù)據(jù)集時，LSH算法相對于傳統(tǒng)近鄰搜索算法所展示出來的優(yōu)越性，為本文研究區(qū)塊鏈環(huán)境中的協(xié)同過濾推薦提供了思路。

3.3 在區(qū)塊鏈環(huán)境中存在的不足

在實際應(yīng)用中，LSH算法包含哈希表的個數(shù)和哈希函數(shù)的個數(shù)這2個主要參數(shù)。為了保證查詢的準(zhǔn)確性，往往使用過多的哈希函數(shù)和哈希表，從而使得空間和時間效率變得低效。

當(dāng)在區(qū)塊鏈環(huán)境中使用LSH進(jìn)行近似近鄰搜索時，為了維護(hù)數(shù)據(jù)局部性并保證查詢準(zhǔn)確性，LSH算法不得不使用大量哈希表和哈希函數(shù)，這無疑增加了區(qū)塊鏈環(huán)境中近似近鄰搜索的計算開銷，導(dǎo)致系統(tǒng)的空間效率低下。同時，傳統(tǒng)LSH算法及其改進(jìn)算法大多并未考慮數(shù)據(jù)分布，直接隨機(jī)選擇哈希函數(shù)的投影向量。在理想情況下，數(shù)據(jù)點均勻分布，它們被散列到哈希桶中的概率相同，因此桶中的點是均勻的。然而，在區(qū)塊鏈環(huán)境中數(shù)據(jù)的分布很大概率并不均勻[19]。因此，通過隨機(jī)選擇的投影向量對不均勻分布的數(shù)據(jù)點進(jìn)行哈希會導(dǎo)致許多不相關(guān)的數(shù)據(jù)點聚集在相同哈希桶中，從而降低查詢結(jié)果的準(zhǔn)確性。

4 基于數(shù)據(jù)分布的LSH優(yōu)化及分析

針對上述問題，本文提出運用數(shù)據(jù)分布的主成分來分配LSH算法中的投影向量，從而使用少量哈希表在區(qū)塊鏈環(huán)境中實現(xiàn)近似近鄰搜索，降低空間開銷。同時，為了提高查詢準(zhǔn)確率并減少距離計算的時間開銷，優(yōu)化后的LSH量化了哈希表中每個哈希函數(shù)的權(quán)值并調(diào)整哈希桶的間隔值，在沒有任何精度損失的情況下進(jìn)一步記錄候選點的沖突頻率，以減小查詢結(jié)果集的大小。

4.1 主成分分析

主成分分析已經(jīng)成為了一種應(yīng)用廣泛的降維方法，其主要思想是用少數(shù)幾個新的變量代替原有變量，在減少需要分析的數(shù)據(jù)的同時，盡量減少原始數(shù)據(jù)所包含的信息的丟失。具體到本文的應(yīng)用中即通過主成分分析，在降低數(shù)據(jù)維度的情況下，保持投影向量的最大標(biāo)準(zhǔn)差。利用數(shù)據(jù)集的協(xié)方差矩陣得到投影向量的特征向量和特征值，將體現(xiàn)數(shù)據(jù)分布的前幾個特征向量作為LSH中的投影向量并構(gòu)造哈希表，有效地減少空間開銷。

假設(shè)高維特征數(shù)據(jù)集R中的τ個元素均為n維向量，用矩陣表示如式(4)所示：

(4)

其中，ui表示用戶i的評分向量，rij表示用戶i對項目j的評分。

為了保證所有維度上的偏移都是以零為基點的，將樣本去中心化,如式(5)所示：

(5)

(6)

對協(xié)方差矩陣S進(jìn)行特征值分解得到特征向量集合P和特征值集合N，選取最大的m(m=kl,其中，k表示每個哈希表中哈希函數(shù)的個數(shù)，l表示哈希表個數(shù)。)個特征值對應(yīng)的特征向量作為數(shù)據(jù)集的主成分組P′，通過P′映射將高維特征數(shù)據(jù)集R表示為數(shù)據(jù)集R′，且R′=RP′。由于特征值越大，其所對應(yīng)的特征向量攜帶的信息越多，所以將前幾個特征向量作為LSH近似近鄰搜索中的投影向量，可以有效地減少空間開銷。

4.1.1 基于特征值優(yōu)化的投影向量權(quán)重

傳統(tǒng)LSH算法中數(shù)據(jù)點在哈希表中的哈希值是通過給哈希函數(shù)賦予一個隨機(jī)權(quán)重值并進(jìn)行加權(quán)計算得來的。根據(jù)式(3)，對于?v∈O，該點在第i個哈希表中的哈希值如式(7)所示：

gi(v)=ai1hi1(v)+ai2hi2(v)+…+aikhik(v)

(7)

其中,aij是一個(0,1)隨機(jī)選擇的常數(shù)且服從p-穩(wěn)定分布，同時1

傳統(tǒng)LSH算法通常為哈希函數(shù)隨機(jī)分配權(quán)重值，這會影響查詢的效率及性能，為了獲得更好的搜索結(jié)果，算法應(yīng)該為具有更好投影向量的哈希函數(shù)分配更大的權(quán)重。本文算法將特征值進(jìn)行排序，利用排序靠前的特征向量作為投影向量，這樣可以更好地反映不同向量在方向上的貢獻(xiàn)。

4.1.2 基于特征值優(yōu)化的桶間隔

在傳統(tǒng)LSH算法中，W是一個常數(shù)，因而很容易被忽略。然而實驗證明，W的大小會影響整個近鄰搜索系統(tǒng)的性能。當(dāng)W較大時，相鄰的點有更大的概率被哈希到同一個桶中，但同時也增大了將相距較遠(yuǎn)的點哈希到同一桶中的概率；當(dāng)W較小時，雖然相隔較遠(yuǎn)的點很難被哈希到同一個桶中，但也增大了2個相鄰的點被哈希到不同桶中的概率。

優(yōu)化后的LSH將特征值按大小排序，并將其對應(yīng)的特征向量按順序選為投影向量。第1個特征向量方差最大，其余依次減小，方差越大的特征向量可以以較大的概率將距離較遠(yuǎn)的點哈希到不同的桶中。為了使方差較小的主成分也保持這一屬性，優(yōu)化后的LSH調(diào)整并減小方差較小的主成分所在哈希函數(shù)的間隔值W。同一哈希表中的哈希函數(shù)間隔值W相同，并且相鄰2個哈希表中哈希函數(shù)的間隔之比與特征值之比相等。也就是說，對于第i(i=1,2,…,l)個哈希表，其哈希函數(shù)的間隔值Wi如式(8)所示：

(8)

其中，W0為初始默認(rèn)值，大量實驗表明，當(dāng)W0=4時，檢索效果較好[20];λ1代表最大特征值。

4.1.3 基于沖突次數(shù)的結(jié)果集優(yōu)化

在LSH中，2個相距較遠(yuǎn)的點也有很大概率會在某個哈希表中發(fā)生沖突。因此，如果結(jié)果集中包含了所有與查詢點q沖突的點，在進(jìn)行距離計算時，由于大量與查詢點q沖突次數(shù)較少的無關(guān)點的存在，會增加計算開銷并降低查詢的精度。

為了精煉結(jié)果集C(q)，提高計算效率，優(yōu)化后的LSH在執(zhí)行哈希計算時記錄候選點與查詢點q在l個哈希表中的沖突次數(shù)。一般來說，候選點q與查詢點的沖突次數(shù)越多，該候選點是查詢點q的近似近鄰的概率也越大，將候選點p與查詢點p的沖突次數(shù)用conf(p)表示,其計算方式如式(9)所示:

(9)

假設(shè)t為沖突閾值，如果候選點p的沖突次數(shù)conf(p)≥t，則稱點p為頻繁沖突點。由于第1個哈希表中的哈希函數(shù)是特征值較大的主成分，那么表中與查詢點q發(fā)生沖突的候選點很大概率上屬于查詢點q的近似近鄰，因此算法將第1個哈希表中與查詢點q發(fā)生沖突的點都保存在其候選集C(q)中。在其余哈希表中，只有conf(p)≥t時，才將點保存在C(q)中。如果存在某個頻繁沖突點p與q的距離小于或等于距離閾值M,則可以提前終止檢索。

4.2 參數(shù)設(shè)置分析

給定p1=p(r),p2=p(cr)，令α,β,δ分別為沖突閾值的百分比形式、誤判率和錯誤率。對于p2<α

(10)

p(s)的定義如式(11)所示：

(11)

(12)

將式(12)代入l1，可得：

(13)

根據(jù)α和l的取值，可以確定沖突閾值t的取值如式(14)所示：

(14)

根據(jù)以上分析，優(yōu)化后的近似近鄰搜索算法的精確率由誤判率β、近似比例c和錯誤率δ決定，這3個參數(shù)均為用戶自定義的常量。其中δ決定了所有基于LSH近似近鄰搜索算法的成功率。c越小，精確率越高；β越大，進(jìn)入候選集的頻繁候選點就越多，搜索質(zhì)量也隨之越高，但同時也會帶來更大的距離計算開銷。本文依據(jù)現(xiàn)有方案設(shè)置δ=1/e，β=100/s(其中s為數(shù)據(jù)點的數(shù)量)。

4.3 優(yōu)化后的LSH算法的理論保證

4.3.1 查詢精確度

哈希表的數(shù)目是一個LSH算法中非常重要的參數(shù)，需要選取一個合適的值使得以下2個性質(zhì)同時成立：

P1：如果存在一個對象o使得它與q的距離小于或等于r，則o是一個頻繁沖突對象。

P2：誤判對象的總數(shù)目小于βs，其中每個誤判對象都是一個與q的距離大于cr的對象。

本文算法可以保證選取的l能以至少(1/2-δ)的概率使得以下2個性質(zhì)同時成立。

證明假設(shè)S1表示那些與查詢點q的距離小于或等于r的頻繁沖突的對象，即S1={p|conf(p)≥αl∧‖p-q‖≤r}。對于?p∈S1有：

Pr[P1]=Pr[conf(p)≥αl]=

其中，pconf=Pr[|haj(p)-haj(q)|≤Wr/2]，Yi～B(l,1-pconf)，j∈{1,2,…,l}，pconf≥p1>α。

設(shè)有l(wèi)個伯努利隨機(jī)變量Yi，1≤i≤l。若2個對象之間沒有發(fā)生沖突，則令Yi=1，即Pr[Yi=1]=1-pconf；若2個對象發(fā)生沖突，則Pr[Yi=0]=pconf。綜上，隨機(jī)變量Yi的期望E[Yi]=1-pconf。

Pr[Y-E[Y]≥γl]=Pr[Y≥(1-α)l]≤

因為conf(p)≥αl,即p和q發(fā)生沖突的概率小于或等于(1-α)l，所以：

Pr[P1]=Pr[Y≤(1-α)l]=

1-Pr[Y>(1-α)l]≥1-

Pr[Y≥(1-α)l]≥1-e-2l(p1-α)2≥1-δ

假設(shè)S2表示那些與查詢點q的距離大于或等于cr的頻繁沖突對象，即S2={p|conf(p)≥αl∧‖p-q‖≥cr}，同理可得：

Pr[P2]=Pr[|S2|<βs]=1-

由于優(yōu)化后的算法只有在滿足P1或P2其中之一時才停止，那么，

Pr[P1∩P2]=Pr[P1]+Pr[P2]-

由此得證。

□

4.3.2 時間復(fù)雜度

在建立索引階段，根據(jù)哈希表個數(shù)，需要進(jìn)行y次運算，每次循環(huán)分別需要計算k次、k-ky次、k-1次，因此總的復(fù)雜度為O(y)*O(k+(k-ky)+(k-1))=O(l)*O(3k-ky-1)，其中，k表示每個哈希表中哈希函數(shù)的個數(shù)，y表示哈希表個數(shù)。優(yōu)化后的算法復(fù)雜度相對較低，可以使用較少的哈希表和哈希函數(shù)找到查詢點的近鄰節(jié)點，在第6節(jié)的實驗分析中，將對此進(jìn)行驗證說明。

5 協(xié)同過濾推薦算法

基于以上分析，本文提出的基于優(yōu)化后的LSH的協(xié)同過濾推薦算法的具體步驟如下所示。

步驟1生成用戶-項評分矩陣Dm×n。

依據(jù)用戶評分的多條記錄，將其轉(zhuǎn)變?yōu)橛脩?項目評分矩陣Dg×h。該矩陣的行表示g個用戶，列表示h個項目，矩陣分量Dij表示用戶i對項目j的評分。若未評分，則Dij=0。

步驟2產(chǎn)生用戶近鄰集合。

(1)建立LSH索引。

(2)近似近鄰查找。

遍歷待查詢高維數(shù)據(jù)點x所在的所有哈希桶，并獲得其所有的近似近鄰。首先在第1個哈希表中查找查詢點x所在哈希桶，將桶內(nèi)所有數(shù)據(jù)點存儲在結(jié)果集中。然后從第2個哈希表開始，利用式(9)記錄與數(shù)據(jù)點x沖突次數(shù)達(dá)到t次以上的點，并將該點存儲在數(shù)據(jù)集中。最后將得到的結(jié)果集中的點x′與查詢點x進(jìn)行比較，如果距離大于r即D(x,x′)>r，則將該點從結(jié)果集中刪除，從而獲得數(shù)據(jù)點x的所有近似近鄰結(jié)果集。

步驟3預(yù)測用戶評分，并產(chǎn)生推薦。

首先，根據(jù)上述算法得到的最近鄰用戶集合，利用式(15)計算目標(biāo)用戶與近鄰用戶之間相似度，通過式(16)的加權(quán)平均策略進(jìn)行評分預(yù)測，得到用戶對未評分項目的預(yù)測評分；然后，依據(jù)用戶評分的高低，產(chǎn)生項目推薦列表。

(15)

其中，ζ為常數(shù)1，當(dāng)用戶u和用戶υ的歐氏距離為0時，用戶間的相似系數(shù)為1。

(16)

6 實驗?zāi)M分析

6.1 優(yōu)化后的LSH近似近鄰搜索算法實驗分析

為了評估優(yōu)化后的近似近鄰搜索算法的性能，本文進(jìn)行了如下實驗。

6.1.1 實驗設(shè)置

實驗仿真環(huán)境的計算機(jī)配置為：Windows 10操作系統(tǒng)，8 GB內(nèi)存,Intel(R)Core(TM)i5-8265U,CPU為主頻3.90 GHz。

為了更加貼合區(qū)塊鏈環(huán)境中數(shù)據(jù)高維、非均勻分布等特點，本文選用數(shù)據(jù)非均勻分布的LabelMe數(shù)據(jù)集進(jìn)行實驗，從該數(shù)據(jù)集的圖像中提取了20 000個512維的特征點，且將前1 000個特征點用于查詢。

近似近鄰搜索的性能與其距離閾值相關(guān)聯(lián)，但由于LSH的不確定性和概率性質(zhì)，很難確定近似近鄰查詢中的最優(yōu)距離閾值。為此，Dater等[12]提出利用采樣機(jī)制來獲取適當(dāng)?shù)木嚯x閾值。在實驗中分別選取300,400,500,600來測試優(yōu)化后的LSH性能，從查詢精確率和平均查詢時間兩方面，通過與將PCA(Principal Component Analysis)和LSH結(jié)合的PCH(Principal Component analysis locality sensitive Hashing)進(jìn)行對比，來衡量優(yōu)化后的LSH算法的性能。

6.1.2 實驗結(jié)果及分析

(1)精確率。

精確率是評價查詢結(jié)果精確性的指標(biāo)，它表示預(yù)測為正的結(jié)果中有多少是正確的。點q的近似近鄰查詢結(jié)果的精確率由式(17)計算而來:

(17)

其中，TP和FP分別表示預(yù)測正確和預(yù)測錯誤的樣本數(shù)量。

與傳統(tǒng)的LSH算法相比，本文所提出的優(yōu)化算法通過考慮數(shù)據(jù)分布的主成分，可以使用較少的哈希函數(shù)就能以較大概率將相近的點映射到同一桶中。同時為了精煉查詢的結(jié)果集，本文的優(yōu)化算法對桶間隔進(jìn)行了優(yōu)化，并通過對候選點的沖突次數(shù)進(jìn)行統(tǒng)計，顯著減少不相關(guān)點的數(shù)量，從而達(dá)到提高查詢精確率的目的。本節(jié)中M均表示距離閾值。

圖2反映了當(dāng)k=4和k=8時，即每個哈希表中有4個和8個哈希函數(shù)時，在LabelMe數(shù)據(jù)集測試中各方案的查詢精確率?？梢钥闯?，當(dāng)k=4時本文優(yōu)化后的LSH的查詢精確率相比于PCH提高了大概30%；PCH算法在k=8時的查詢精確率甚至不如優(yōu)化后的算法在k=4時的精確率；當(dāng)k=8時，優(yōu)化后的LSH算法就已經(jīng)能夠獲得較高的查詢精確率了。

Figure 2 Comparison of query precision

(2)平均查詢時間。

傳統(tǒng)的LSH通過隨機(jī)選擇投影向量對數(shù)據(jù)點進(jìn)行映射，從而導(dǎo)致哈希桶中增加了許多無關(guān)數(shù)據(jù)點，使得候選結(jié)果集較大，增加了后續(xù)的計算開銷。PCH雖然縮減了候選結(jié)果集的大小，但其由于主成分分析所帶來的正交性約束問題仍然存在。本文所優(yōu)化的算法不僅解決了該問題，并且通過對沖突次數(shù)的統(tǒng)計，進(jìn)一步精煉了候選結(jié)果集，從而在很大程度上降低了計算開銷。

各個算法執(zhí)行1 000次近似近鄰搜索的平均時間開銷結(jié)果如圖3所示。

Figure 3 Comparison of average query time per 1 000 queries

從圖3可以看出，無論在k=4還是k=8的情況下，優(yōu)化后的LSH算法的查詢時間都遠(yuǎn)遠(yuǎn)低于PCH算法的。當(dāng)k=4時，在每1 000次查詢中，本文優(yōu)化后的LSH算法與PCH算法相比，其查詢時間幾乎減少了80%。本文算法和PCH算法在進(jìn)行近似近鄰搜索時，都需要進(jìn)行哈希計算和距離計算，與PCH算法不同的是，本文的LSH通過調(diào)整每個哈希函數(shù)的權(quán)重和桶間隔，可以在很大程度上減少哈希計算量，從而降低整個查詢過程的時間開銷。

6.2 優(yōu)化后的協(xié)同過濾算法實驗分析

6.2.1 數(shù)據(jù)集與評價指標(biāo)

本文數(shù)據(jù)集采用MovieLens 1M電影評價數(shù)據(jù)集，仿真前對數(shù)據(jù)集進(jìn)行預(yù)處理，剔除了部分?jǐn)?shù)據(jù)，最終包含6 040位用戶對3 900部電影的744 398個評分?jǐn)?shù)據(jù)，評分分值為1～5。

為了解決區(qū)塊鏈數(shù)據(jù)的存儲問題，在應(yīng)用場景中，可以使用分布式存儲(如IPFS)將數(shù)據(jù)的哈希值錄入?yún)^(qū)塊，該方案可以將用戶的評級有效存儲在數(shù)據(jù)庫中。在存儲于區(qū)塊鏈的每項事務(wù)中，用戶附加了一些元數(shù)據(jù)，這些元數(shù)據(jù)即他們評級的哈希值。一旦用戶想要獲取推薦，他就會收集相應(yīng)的事務(wù)并提取元數(shù)據(jù)。Casino等[5]的研究表明，通過運用該方案的數(shù)據(jù)整合，可以在區(qū)塊鏈環(huán)境中使用MovieLens數(shù)據(jù)集進(jìn)行實驗仿真。

本文實驗結(jié)果主要包含推薦精度與推薦效率2部分。在推薦效率方面，本文通過不同鄰居數(shù)量時的算法運行時間來展示本文推薦算法的效率，運行時間能夠反映算法的時間復(fù)雜度和實效性。此外，本文將均方根誤差(RMSE)作為推薦質(zhì)量的評價指標(biāo)，利用算法預(yù)測出的評分和用戶的真實評分之間平方差異平均值的平方根來衡量推薦的精確度，該值越小，說明算法推薦質(zhì)量越好。RMSE計算如式(18)所示：

(18)

6.2.2 實驗結(jié)果與分析

(1)參數(shù)分析。

本文算法是一種針對區(qū)塊鏈環(huán)境中高維大規(guī)模數(shù)據(jù)的推薦算法,而LSH中哈希表個數(shù)l和哈希函數(shù)個數(shù)k可以限制或放寬對近鄰用戶的搜索條件，影響用戶數(shù)據(jù)映射的哈希值,從而影響相似用戶集合，進(jìn)而影響協(xié)同過濾推薦算法的性能。本實驗研究了l,k取值對算法性能的影響，l和k的取值都從2到10不等，其結(jié)果如圖4所示。

Figure 4 Impact of l-k on recommendation quality

從圖4中可以看出，隨著l的增大，RMSE總體呈現(xiàn)增長的趨勢；隨著k的增大，RMSE逐漸減小。這是因為在本文算法中，近鄰用戶集合是不同哈希表中近鄰用戶集合的并集,隨著l的增大,不相似的用戶進(jìn)入集合的概率也隨之增大,而這些不相似的用戶會干擾預(yù)測的準(zhǔn)確度,因此為提高預(yù)測準(zhǔn)確度,在實際應(yīng)用中應(yīng)該適當(dāng)選取較小的哈希表個數(shù)。隨著k的增大,減小了不相似用戶被映射到同一哈希桶的概率,這樣就保證了基于這些大概率上的相似用戶推薦結(jié)果的準(zhǔn)確性。在后面的實驗中，考慮到數(shù)據(jù)集大小以及實際運行內(nèi)存大小，本文設(shè)定參數(shù)k=10，l=10，并且選取均方根誤差(RMSE)作為推薦質(zhì)量的評價指標(biāo)，以查找不同鄰居數(shù)目時算法的運行時間作為運行效率的評價指標(biāo)，然后對不同推薦算法的推薦質(zhì)量和運行效率進(jìn)行比較。

(2)不同推薦算法運行效率對比。

為了驗證優(yōu)化后的推薦算法在實際運行中的高效性，實驗選取基于PCH和基于E2LSH(Exact Euclidean LSH)的協(xié)同過濾算法進(jìn)行了對比研究。圖5為3種推薦算法在不同鄰居數(shù)目時的運行時間的對比情況。

Figure 5 Comparison of the running time of the algorithm in this paper and other collaborative filtering algorithms

如圖5所示，隨著鄰居數(shù)目的增加，3種推薦算法的運行時間都有不同程度的增加，但總體來說本文算法的運行時間更為穩(wěn)定，并且遠(yuǎn)遠(yuǎn)低于其他2種協(xié)同過濾推薦算法的，表明了本文算法的高效性和穩(wěn)定性。從整體走勢來看，3種推薦算法均出現(xiàn)了較大程度的起伏，這主要是因為LSH是一個概率算法,相似度用戶集合中的用戶只是極大概率的相似用戶,并不能保證是準(zhǔn)確的相似用戶,所以會導(dǎo)致預(yù)測準(zhǔn)確度的變化。

本文算法通過對數(shù)據(jù)的降維，有效降低了高維數(shù)據(jù)集上由于索引結(jié)構(gòu)導(dǎo)致的數(shù)據(jù)挖掘算法的性能下降問題，并且利用數(shù)據(jù)分布的主成分選取投影向量，并重新分配投影向量的權(quán)重，這樣能夠在很大程度上減少需要使用的哈希函數(shù)的個數(shù)，從而減少計算開銷。基于E2LSH的協(xié)同過濾算法利用隨機(jī)投影向量來映射數(shù)據(jù)點，使得在近鄰搜索過程中，候選集中增加了額外的無關(guān)數(shù)據(jù)點，從而使后續(xù)的距離計算增加了時間開銷。基于PCH的協(xié)同過濾算法雖然也利用了數(shù)據(jù)分布的特性，但傳統(tǒng)主成分分析的正交性約束使其無法獲取連續(xù)的投影向量，也無法對不相關(guān)點進(jìn)行有效的消除。因此，本文算法提出利用主成分相應(yīng)的特征值對哈希函數(shù)的權(quán)重進(jìn)行量化，并調(diào)整桶間隔，通過對沖突頻率的統(tǒng)計精煉結(jié)果集，在很大程度上減少了相似度的計算，降低了算法的時間復(fù)雜度。相較于以往的推薦算法，本文算法能夠更好地適用于高維以及不同規(guī)模的數(shù)據(jù)集，能夠在較短的時間內(nèi)作出推薦。

(3)不同推薦算法預(yù)測準(zhǔn)確度對比。

為了測試本文推薦算法的推薦質(zhì)量，本文將基于優(yōu)化后的局部敏感哈希的協(xié)同過濾算法與其他協(xié)同過濾算法進(jìn)行了對比分析，主要比較不同的鄰居數(shù)目的推薦效果，對比結(jié)果如圖6所示。

Figure 6 Comparison of recommendation quality between this algorithm and other collaborative filtering algorithms

如圖6所示，隨著鄰居節(jié)點數(shù)目的增加，3種算法的推薦質(zhì)量都有所提高，但本文算法的RMSE一直處于較低的位置，并且隨著鄰居數(shù)目的增加逐漸趨于穩(wěn)定。這意味著相比于另外2種協(xié)同過濾算法而言,本文算法具有更高的推薦精度，表明本文算法在減少計算開銷的同時，很好地維護(hù)了數(shù)據(jù)的局部性，通過考慮數(shù)據(jù)分布的特性，在使用少數(shù)哈希表的情況下就能得到近鄰結(jié)果，從而保證了推薦結(jié)果的準(zhǔn)確性。

綜合考慮時間消耗和預(yù)測準(zhǔn)確度,在處理高維大規(guī)模的數(shù)據(jù)時，本文算法是一個既可以快速響應(yīng)用戶需求,又可以提供較好預(yù)測結(jié)果的算法。

7 結(jié)束語

針對在區(qū)塊鏈環(huán)境中進(jìn)行協(xié)同過濾推薦時，由于數(shù)據(jù)規(guī)模大、維數(shù)高對推薦質(zhì)量產(chǎn)生的影響，提出了局部敏感哈希的協(xié)同過濾推薦算法，利用優(yōu)化后的LSH獲得用戶近鄰集合，進(jìn)而形成推薦結(jié)果。

實驗結(jié)果表明，優(yōu)化后的LSH僅需要少量的哈希表和哈希函數(shù)就可以獲得較為精確的近鄰搜索結(jié)果，且搜索效率有很大的提高。將優(yōu)化后的LSH應(yīng)用到區(qū)塊鏈環(huán)境中的協(xié)同過濾推薦時，可以很好地應(yīng)對區(qū)塊鏈中數(shù)據(jù)特點所造成的問題，緩解了高維大規(guī)模數(shù)據(jù)對推薦性能的影響，在一定程度上提高了推薦質(zhì)量和效率。由于該算法性能主要依賴于關(guān)鍵參數(shù)的選取，且對參數(shù)比較敏感，部分人為設(shè)置的經(jīng)驗值在不同程度上對推薦效果都有影響，因此如何調(diào)整參數(shù)的最優(yōu)配置，是下一步工作的研究方向。