[發明專利]一種基于因子圖模型的社交網絡多任務預測方法

在審

• 申請號: 201710770816.6
• 申請日: 2017-08-31
• 公開（公告）號: CN107451703A
• 公開（公告）日: 2017-12-08
• 發明（設計）人: 張子柯;林松;劉闖
• 申請（專利權）人: 杭州師范大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06Q30/02;G06Q30/06;G06Q50/00;G06F17/30
• 代理公司: 杭州天正專利事務所有限公司33201
• 代理人: 王兵,黃美娟

1.一種基于因子圖模型的社交網絡多任務預測方法，包括以下步驟：

第一步，網絡數據獲取：通過網絡爬蟲收集用戶社交信息和行為信息，并對爬取的數據進行清理，方便后續計算，主要包括網絡數據爬取和數據預處理。

(11)網絡數據爬取：爬取用戶社交行為信息和用戶對商品的行為信息，每條信息包括：用戶UserID和用戶UserID，用戶UserID和商品ItemID。

(12)數據預處理：為了方便后續計算，需要清理數據中冗余、不完整的數據，形成模型所需要的統一的用戶和用戶社交行為矩陣w₁，用戶和商品評分行為矩陣w₂。在矩陣w₁中，矩陣中元素w₁^ij表示用戶i和用戶j之間的好友、關注關系，在矩陣w₂中，矩陣中元素w₂^ij表示用戶i和商品j之間的收藏、購買、評價關系。

第二步，建立多任務因子圖模型：

(21)網絡特征提取：因子圖模型是一個監督學習模型，需要利用網絡中的異構信息為社交鏈接和評分鏈接提取特征。在社交網絡中對于一個特定的節點i，提取節點的特征，包括度k(v_i)，出度k_out(v_i)，入度k_in(v_i)，聚類系數c_i。對于社交網絡節點對i和j，相似性指標是預測其在網絡中是否連接的最相關的特征。因此，提取了一些傳統的相似性指標作為特征。

交叉網絡(用戶和商品的評分關系)也隱藏著社交網絡節點對的信息，兩名用戶共同評論的商品越多，則他們是朋友的可能性越大。基于此，根據交叉網絡提取一些相似性指標。類似的，對于交叉網絡目標節點對用戶i和商品a，根據上述相似性指標來提取特征。

(22)網絡遷移結構構建：遷移結構是因子圖模型中重要的因子，邊的標簽信息可以在結構上可以發生遷移。在這項工作中用三角形來構建遷移結構，使得信息可以在社交網絡內部，社交網絡和交叉網絡之間發生傳播。

(23)因子圖模型構建：耦合網絡G＝(G^s，G^C)可以分為一個社交網絡G^s和一個交叉網絡G^C，目標是學習一個模型同時預測潛在的社交鏈接和評分鏈接

對于網絡中的節點對e_ij，用標簽y_e代表其狀態，當y_e＝1表示節點對之間存在一條邊，當y_e＝0表示節點對之間不存在邊。最終模型輸出的標簽y_e＝1的概率P(y_e＝1)。

(a)聯合概率分布

對于耦合社交網絡G＝(V，E，X)，V＝{v_i}代表節點集，E＝{e_ij}代表節點對集合，是一個屬性矩陣，每一行代表節點對e_ij對應的屬性向量，目標是估計每條未知鏈路形成的概率P(y_e|x_e)。用P(Y|X，G)代表網絡的聯合概率分布，G代表網絡的所有信息。這種聯合概率分布表明鏈路的標簽不僅與節點對的局部屬性有關還和網絡的結構有關，聯合概率分布可實例化為：

P(Y|X,G)=Πe∈ESΠi=1dP(yes|xeis)Πe∈ECΠi=1d′P(yec|xeic)Ππ∈ΠΠϵ∈πP(Yϵ)---(1)]]>

其中，d和d′分別表示社交網絡和交叉網絡的特征維度，x_ei表示節點對e的第i個屬性值，E^S代表社交網絡中的節點對集合，E^C代表交叉網絡上的節點對集合表示社交網絡中在屬性條件下的概率，表示交叉網絡中在屬性條件下的概率，P(Y_ε)表示遷移結構的影響，Π代表遷移結構的種類，π代表一種類型的遷移結構，ε代表其中的一個遷移結構。

(b)實例化因子

原則上，屬性關聯特征函數和社會關聯特征函數可以通過不同的方式實例化。這里采用馬爾科夫隨機場中的Hammersley-Clifford理論來對其進行建模：

P(yes|xeis)=1Z1exp{αifi(xeis,yes)}---(2)]]>

P(yec|xeic)=1Z2exp{βigi(xeic,yec)}---(3)]]>

P(Yϵ)=1Z3exp{γϵhϵ(Yϵ)}---(4)]]>

f_i(*)、g_i(*)h_ε(*)分別為社交網絡、交叉網絡、遷移結構的特征函數，α_i、β_i、γ_ε是對應其權重，Z₁、Z₂、Z₃為歸一化因子。

(c)目標函數優化

結合上述公式，最后得到目標函數：

其中，Z＝Z₁Z₂Z₃為歸一化因子。

用隨機梯度下降的方法，可以得到每個參數的梯度：

和E[h_ε(Y_ε)]分別表示數據分布的函數h_ε(Y_ε)的期望，和是根據估計模型在P_α，β，γ(Y|X，G)分布下的期望。

第三步，預測結果評估：

衡量本方法有效性的指標有AUC、Precision和Ranking Score共3種。它們對預測精確度衡量的側重點不同：AUC(area under the receiver operating characteristic curve)從整體上衡量算法的精確度。Precision只考慮對排在前L位的邊是否預測準確。而Ranking Score更多考慮對所預測的邊的排序。

AUC可以理解為在測試集中的邊的分數值有比隨機選擇的一個不存在的邊的分數值高的概率，也就是說，每次隨機從測試集中選取一條邊與隨機選擇的不存在的邊進行比較，如果測試集中的邊的分數值大于不存在的邊的分數值，就加1分；如果兩個分數值相等，就加0.5分。獨立地比較n次，如果有n′次測試集中的邊的分數值大于不存在的邊的分數，有n″次兩分數值相等，則AUC定義為：

AUC=n′+0.5n′′n]]>

顯然，如果所有分數都是隨機產生的，AUC＝0.5。因此AUC大于0.5的程度衡量了算法在多大程度上比隨機選擇的方法精確。

Precision定義為在前L個預測邊中被預測準確的比例。如果有m個預測準確，即排在前L的邊中有m個在測試集中，則Precision定義為：

Precision=mL]]>

顯然，Precision越大預測越準確。如果兩個算法AUC相同，而算法1的Precision大于算法2，說明算法1更好，因為其傾向于把真正連邊的節點對排在前面。

Ranking Score主要考慮測試集中的邊在最終排序中的位置。令H＝U-E^T為未知邊的集合(相當于測試集中的邊和不存在的邊的集合)，r_i表示未知邊i∈E在排序中的排名。則該條未知邊的Ranking Score值為RS_i＝r_i/|H|，其中|H|表示集合H中元素的個數遍歷所有在測試集中的邊，得到系統的Ranking Score值為：

RS=1|EP|Σi∈EPRSi=1|EP|Σi∈EPri|H|.]]> 3