汪 靜，錢曉東

(蘭州交通大學經濟管理學院，甘肅 蘭州730070)

1 引言

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

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

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

2 相關研究

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

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

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

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

2.2 關于局部敏感哈希的推薦研究

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

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

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

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

3.1 LSH近似近鄰搜索算法

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

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

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

(1)

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

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

(2)

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

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

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

(3)

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

Figure 1 A point set in a bad projection direction

3.2 算法分析

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

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

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

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

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

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

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

4.1 主成分分析

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

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

(4)

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

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

(5)

(6)

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

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

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

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

(7)

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

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

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

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

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

(8)

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

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

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

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

(9)

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

4.2 參數設置分析

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

(10)

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

(11)

(12)

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

(13)

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

(14)

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

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

4.3.1 查詢精確度

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

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

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

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

證明假設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>α。

設有l(wèi)個伯努利隨機變量Yi，1≤i≤l。若2個對象之間沒有發(fā)生沖突，則令Yi=1，即Pr[Yi=1]=1-pconf；若2個對象發(fā)生沖突，則Pr[Yi=0]=pconf。綜上，隨機變量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-δ

假設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 時間復雜度

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

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

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

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

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

步驟2產生用戶近鄰集合。

(1)建立LSH索引。

(2)近似近鄰查找。

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

步驟3預測用戶評分，并產生推薦。

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

(15)

其中，ζ為常數1，當用戶u和用戶υ的歐氏距離為0時，用戶間的相似系數為1。

(16)

6 實驗模擬分析

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

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

6.1.1 實驗設置

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

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

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

6.1.2 實驗結果及分析

(1)精確率。

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

(17)

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

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

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

Figure 2 Comparison of query precision

(2)平均查詢時間。

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

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

Figure 3 Comparison of average query time per 1 000 queries

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

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

6.2.1 數據集與評價指標

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

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

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

(18)

6.2.2 實驗結果與分析

(1)參數分析。

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

Figure 4 Impact of l-k on recommendation quality

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

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

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

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

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

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

(3)不同推薦算法預測準確度對比。

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

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

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

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

7 結束語

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

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