一種基于LSH技術的鏈路預測方法

黃壽孟，夏王霞

（三亞學院信息與智能工程學院 海南 三亞 572022）

1 引言

社交網絡可以用來描述現實社會中的實際網絡，它包括人與人之間的社會關系，物種之間的捕食關系，科學研究中的合作關系等[1]。大量研究已經表明，在真實世界中各種不同社交網絡具有許多共同的結構特征，例如小世界性質[2]、無標度性[3]、社團結構等[4-6]。網絡中的鏈路預測是指如何通過已知的網絡結構等信息，預測網絡中尚未產生連接的兩個節點之間產生連接的可能性。網絡中的頂點代表用戶，邊代表用戶關系，鏈路預測問題正是對用戶未來關系的分析。

2 相關工作

2.1 局部敏感HASH技術

LSH即Locality Sensitive hash，用來解決在海量數據中進行相似性查找的問題，以圖片搜索為例，用戶向百度圖搜提交待搜索圖片，百度圖搜將相似的圖片返回展示。要實現這樣一個應用，需要考慮以下幾個步驟。

（1）提取用戶提交的圖片特征，即將提交圖片轉換成一個特征向量；

（2）預先將所有收集到的圖片進行特征提取；

（3）把步驟（1）中提取的特征與步驟（2）中的特征集合，進行比對，并記錄比對的相似值；

（4）對相似值由大到小排序，返回相似度最高的作為檢索結果。

步驟（1）（2）是一個圖片特征提取的問題，與LSH無關。LSH主要解決步驟（3）（4），在海量特征集中找到相似特征。那么，局部敏感HASH函數必須滿足如下條件。

（1）進行相似性搜索時，在概率上可以保證返回值的相似性；

（2）函數族中的各函數，返回值在概率上相互獨立，概率獨立可以帶來統計獨立，滿足疊加多個函數，提高查準率和通過組合能夠避免偽正例、偽反例的好處；

（3）搜索效率：hash比對比線性查詢快。

既然是在概率意義下相似性度量，必然會存在著相近樣本被hash到不同的hash值情況，同時也必然會存在不相近的樣本被hash到相同的hash值情況，前者稱為偽反例，后者稱為偽正例。偽正例通過與構造解決，即通過多個hash函數，計算同一個特征的多個hash值，只有當多個hash函數均相同時，才認為特征相似。這有效避免了不相似的特征被判定為相似特征的情況。偽反例通過或構造解決，即通過多個hash函數，計算同一個特征的多個hash值，只有多個hash函數有一個hash值相同時，即認為特征相似。這有效避免了相似的特征被判定為不相似特征的情況。

結合與構造與或構造2種方案，可以生成r*b個函數，每r個hash函數代表一組與構造，每b組hash函數族代表一組或構造，當滿足一個或構造后特征判定為相似。設一組特征hash的相似概率為s，則通過hash函數與/或構造后的相似概率如下。

1-（1-s^r）^b

在這個概率函數中，s與hash函數的精度相關，屬于不可調節參數。當r越大時，相似概率越小，當b越大時，相似概率越大。r與b作為LSH的超參數可以根據實際情況進行相應的調節。

2.2 鏈路預測指標

衡量鏈路預測算法精確度的指標有三種：AUC、Precision、Ranking Score。其中，三個指標主要以AUC為主，在AUC基本相同的情況下，可以再以Precision作為標準衡量算法精確度，因此這里只介紹前兩個指標。

定義(G,V,E) 為一個無向網絡，其中V為節點集合，E為邊集合。網絡總的節點數為N，邊數為M。該網絡共有N(N-1)/2個節點對，即全集U。

將已知的連邊E分為訓練集ET和測試集EP兩部分。從數據集中選取一部分邊作為測試集EP，并將這部分邊從數據集中刪去，由數據集中剩余部分的邊作為訓練集ET。顯然有E=ET ∪ EP，且ET ∩ EP=?。同時，網絡中還有一些節點之間并沒有邊相連，將這些邊稱為不存在的邊。

2.2.1 AUC（area under the receiver operating characteristic curve）

AUC從整體上衡量算法的準確性。鏈路預測算法在經過訓練后可以得到網絡中每一對節點的相似值（即邊的相似值）。AUC指標即是基于測試集中邊的相似值和不存在的邊的相似值的比較（即以不存在的邊作為基準）。

若Sim測試＞Sim不存在，則數值的分子加1（此時證明預測效果良好）；

若Sim測試=Sim不存在，則數值的分子加0.5（此時相當于隨機選擇）；

若Sim測試＜Sim不存在，則數值的分子加0。

Sim表示相似值，數值的分母則是測試集中的邊的相似值與不存在的邊的相似值比較的次數。

AUC指標即為數值分子與數值分母的比值，AUC大于0.5的程度衡量了算法在多大程度上優于隨機選擇的算法。

2.2.2 Precision

Precision只考慮前L位的邊是否預測準確。鏈路預測算法經過訓練后會得到節點對之間的相似值，去除訓練集ET中的邊，僅將測試集EP和不存在的邊集合中的邊的相似值進行排序，排序后取前L個。假設L個中有N個屬于測試集，那么Precision值為N/L。

3 預測方法

3.1 定義

LSH技術是從海量高維數據中查詢與某個數據最相似的一個數據或數據集，常用于人臉檢索。它的基本思想是基于原始數據空間中相鄰的數據經過同一個映射變換之后，處于相鄰區域的概率仍然較大的理念；人為地選取一些具有上述性質的函數來作為哈希函數，使得相鄰的數據映射后處在哈希表的同一個位置，這樣就可以輕松地找到與該數據相似的數據集。即通過選取的哈希函數的映射變換，能夠將原始的數據集劃分為若干較小的子集，且每個子集中的元素個數較小且相鄰。偏好向量RD，即xRD，y為社交網絡用戶向量Rd，即y

對于任意用戶有兩個特征值:x,y，其中x為用戶訪問Rd，存在一個哈希函數H(x)滿足以下兩個條件，則稱為敏感哈希函數，記作H(S1,S2,p1,p2）:

(1)如果sim(x,y)≥S1，則P(h(x)=h(y))≥p1

(2)如果sim(x,y)≤S2，則P( h(x)=h(y))≤p2

其中，S1,S2是近鄰搜索的興趣閾值，S1＞S2,p1,p2是概率值且p1＞p2,sim()是相似度函數。

LSH算法重點在于如何將數據映射成二進制編碼的概率最大化，即將用戶特定向量表示二值化（僅有0和1的表示）。

3.2 預測方案設計

將社交網絡的用戶數據進行數據清洗，產生構建用戶位置簽到頻率矩陣和用戶關系連通子圖，接著將前者進行矩陣分解出用戶訪問偏好向量，將后者細分為網絡表示學習得到社交網絡用戶向量、并構建訓練集與測試集。然后，將用戶訪問偏好向量與社交網絡用戶向量進行錨鏈接映射融合，得到融合后的用戶向量表示，并引入LSH技術將輸入訓練集和測試集將其轉換為點對關系融合，最后進行模型訓練和測試評估性能，這就是基于LSH技術的預測模型LSH-P，見圖1。

圖1 LSH-P預測方案

3.2 預測算法

預測算法如圖2所示。

圖2 預測算法

4 實驗分析

4.1 實驗準備工作

本實驗采用Gowalla和Foursquare兩種開源數據集[7]其中@NY表示紐約，@TY表示東京，@WHG表示華盛頓，@CCG表示芝加哥，本實驗對照基準模型有walk2friends[8]和DeepWalk[9]，評估指標有AUC、精度、查全率和F1值（精度與查全率的平均）[10]。AUC評估指標實驗結果見表1，說明在不同的數據集中，LSH-P模型的AUC值都優于walk2friends和DeepWalk。

表1 LSH-P的AUC預測結果

對評估指標精度、查全率、F1值的衡量實驗，如表2、表3所示，從兩表中可以得到在鏈路預測任務中，LSH-P預測效果是最佳的，這是因為LSH-P模型加入LHS技術。

表2 Foursquare數據集的預測結果

表3 Gowalla數據集的預測結果

5 結語

為了提升鏈路預測的效果，本文提出一種LSH技術的數據融合訓練，通過用戶向量點對關系訓練與測試，從而進一步提升鏈路預測的綜合性能。鏈路預測是網絡信息挖掘中最基礎最本質的問題，通過對已經觀察到的網絡結構和其他外部信息的分析，挖掘缺失的連接和預測未來可能出現的連接。鏈路預測算法在生物網絡分析、朋友及關注對象推薦、個性化推薦、網絡演化模型評價、標簽分類、網絡重構等問題上有著廣泛的應用。