基于社交關系與無監督學習的大數據推薦算法

李淑霞 楊俊成* 蔡增玉

1(河南工業職業技術學院電子信息工程學院 河南 南陽 473000)2(鄭州輕工業學院計算機與通信工程學院 河南 鄭州 450002)

0 引 言

私人定制化的推薦系統已經成為了各大商業網站的必備系統，能夠有效地提高用戶獲取目標信息的效率，并且改善用戶的瀏覽體驗[1]。推薦系統的推薦精度與響應時間均為關鍵指標，目前的大型商業網站中項目與用戶的數據量十分龐大，使得推薦系統的推薦精度與響應時間成為了一個挑戰[2]。

基于協同過濾的推薦算法CF(Collaborative Filtering)是諸多推薦算法中最為普及的一個，然而對于用戶數量不足以及用戶評分不足的情況，存在嚴重的冷啟動問題與稀疏性問題[3-4]。CRSC[5]技術對CF進行了改進，解決了推薦系統的稀疏性問題。其主要思想是對相似上下文的用戶偏好進行分類，從而解決推薦系統的冷啟動問題與稀疏性問題。矩陣分解[6]是一種實現隱語義模型(Latent Factor Model)的方案，通過矩陣分解模型實現用戶對項目的評分。CMFCAR[7]是一種基于卷積矩陣分解的推薦系統，該系統通過卷積矩陣分解技術保留了項目與用戶的細節信息，并且有效地實現了數據降維處理，對推薦系統的推薦精度與計算效率均做出了較大的改進。許多研究人員成功地將張量分解技術應用于推薦系統中，當前的方案主要為用戶的上下文建立張量模型，通過上下文信息解決推薦的稀疏性問題與冷啟動問題，從而提高推薦精度與魯棒性。RBCDR[8]是近期一種交叉域的推薦系統，該系統將附屬結構域的知識融入目標域，該研究中已經證明其有效性。RCATF[9]算法對時間上下文與位置上下文建立了張量模型，并借助時間上下文的知識對位置進行推薦。該算法實現了較高的推薦準確率，但是其中包括了時間上下文的學習算法，需要學習所有的用戶信息，導致時間效率較低，無法實現實時的推送服務。

當前基于張量的推薦系統均將用戶的上下文建模為張量模型，這些方案在一定程度上緩解了推薦系統的冷啟動與稀疏性問題，也有效地提高了推薦的精度與魯棒性，但是也表現出了性能的瓶頸[10-11]。為了解決上述問題，本文引入了用戶的社交關系，將社交網絡引入張量中，本推薦系統考慮了5個因素，分別為：用戶、項目、時間上下文、空間上下文與社交關系。本文的貢獻主要有以下兩點：設計了社交關系的張量模型，實時地完成張量的再生與分解；推薦系統支持多上下文環境的推薦。

1 動機與研究意義

本系統考慮了豐富的上下文環境，不僅能夠緩解稀疏性問題與冷啟動問題，而且能夠提高系統的推薦準確率。以常用的電影場景為例：電影為項目，電影觀眾為用戶，考慮時間上下文與空間上下文。考慮一個電影場景的簡單實例，如圖1所示。

圖1 一個電影場景的簡單實例

根據小明、小剛與小麗的歷史記錄，小明有4個時間與空間域的上下文。從圖1可發現三個依賴關系，如下所示：

(1) 小明晚上獨自在家，偏愛在家看電影。

(2) 小明與小麗看電影，偏愛去電影院看愛情類電影。

(3) 小明與小剛看電影，偏愛在家看動作類電影。

從上述三個依賴關系可看出，用戶的社交關系與時間、空間上下文之間存在互相依賴的情況，為了分析與利用社交關系與上下文之間的依賴關系，首先需要解決以下三個問題：(1) 如何將社交關系與張量模型關聯；(2) 如何通過引入社交關系解決推薦系統的稀疏性問題與冷啟動問題；(3) 如何設置合適的數據結構，提高推薦的性能。

2 格式說明

為了將張量應用于社交關系的分析中，提出了一個關于社交關系-張量的模型。首先，為社交關系-張量的模型提出一些定義。

2.1 定 義

本文的張量模型考慮了上下文信息與社交關系。

定義1(張量) 給定I個用戶，J個項目、K個上下文，組成一個三階張量T，張量的值為ti,j,k，張量T表示第i個用戶在第k個上下文對第j個項目的評分。

為了簡化分析，考慮一個單一上下文的簡單案例，社交網絡中僅有一個活動用戶，以及該活動用戶相關的社交網絡。圖2是社交張量生成與分解的示意圖。活動用戶ui存在兩種情況：一種是ui已經存在于系統中，另一種是unew為新用戶。活動用戶表示為張量的一個灰色立方體與灰色圓形，新用戶表示為虛線立方體與黑色圓形。

圖2 社交關系張量的產生與分解

定義3(親和力矩陣) 將一個社交網絡表示為一個有向圖，圖中用戶表示為頂點u1,u2,…,uI′，親和力表示為邊A1,2,A2,3,…,AI′-1 ,I′，圖的鄰接矩陣表示為I′×J′的親和力矩陣A，其中(i,j)元素Ai,j表示ui與uj之間的社交親和力。

(1)

通過親和力矩陣將更多有意義的信息引入社交張量中，使用每對項目的特征相似性計算親和力。

2.2 社交張量的建立

根據上述社交張量的定義，設計了社交張量建立的具體流程，圖3所示是社交張量建立與分解的詳細內容。圖3(a)描述了社交網絡與親和力的關系，圖3(b)的張量僅僅反映了張量網絡中的直接連接。本方法動態地生成社交關系張量，因為本文張量模型的規模明顯小于常規的模型，由此解決了冷啟動問題，模型的計算幾乎為實時的。

圖3 建立社交關系張量的實例

為了解決稀疏性問題與冷啟動問題，本方案僅僅考慮了與小明直接連接的社交網絡。然而數據規模的縮小導致張量模型丟失了許多信息。針對該問題，給定一個多跳距離η3，小明的社交張量為6個用戶，如圖3(c)所示。如果小麗作為新用戶的情況，其張量包括4個用戶，此外，小麗與小明、小吳、小剛三者之間存在一個社交張量，因為小麗與小王之間的跳數為4，所以排除小王。根據定義2，小剛的社交親和力高于小明，所以本方案能夠為社交網絡的新用戶也提供一個推薦，這也解決了冷啟動問題。而其他基于張量的方案無法為新用戶產生推薦，原因是此類模型初始化過程中缺少用戶的信息。

2.3 社交張量的分解

設計了新的社交張量分解流程，如圖4所示。圖4(a)所示是小明與小麗的張量模型，使用一個社交網絡與一個關系建立張量的最終結果。在圖4(b)中，將模型分解為一個核心張量與因子矩陣，然后獲得矩陣U″與S″的化簡，U″與S″分別為活動用戶與社交用戶的階。因為基本因子矩陣的維度是不同的，所以將較大的矩陣分解為一個小矩陣，具體方法為刪除矩陣的0值。圖4(c)所示是兩個矩陣的乘法運算，表示了兩個用戶之間的社交關系，因此，將矩陣U″×S″變為親和力矩陣A，如圖4(d)所示，解決張量的稀疏性問題。

圖4 社交關系張量的分解流程

2.4 數據結構

(2)

3 基于社交張量的推薦系統

本方法由4個步驟組成：① 為活動用戶的社交網絡建立張量模型；② 分解張量，獲得項目的上下文；③ 根據上下文生成一個推薦列表；④ 根據用戶的反饋信息學習活動用戶的社交網絡規模。

3.1 張量計算

張量確定之后，在上下文ck與社交用戶sj的背景條件下對用戶ui的社交張量計算為：

(3)

將張量矩陣的乘法運算表示為×U，下標U表示張量矩陣相乘的方向，矩陣U的第i行元素表示為Ui。

S=Si

(4)

S′=C×UU×SS×CC

(5)

A=A

(6)

A′=U″×S″

(7)

最終，社交張量分解的目標函數定義為:

F(S,A,S′,A′,U,S,C)=

(8)

式(8)中社交張量與親和力矩陣的指示函數I與G分別表示為：

(9)

(10)

式中：n表示跳數；ω∈[0,1]表示權重。

式(8)中“‖‖”表示Frobenius 范數；U、S、C是三個最近的上下文因素；dU、dS、dC是三個最近特征的數量；α、β是式中兩項的權重參數。因為通過社交張量已經對用戶維度與社交因素進行了調節，所以無需再調節維度值dU、dS、dC，將關聯性維度dC設為固定值。式(8)包括了3項，第1項為社交張量分解的誤差，第2項為親和力矩陣與最近特征的差異，第3項為正則化懲罰項。

如果將最小化式(8)作為目標函數，那么無法獲得目標函數的閉項解，因此使用梯度下降法對其最小化處理。算法1給出了社交張量分解的偽代碼，其中目標函數的梯度下降法計算為：

(11)

本算法線性地控制活動用戶、社交用戶與上下文因素的維度，因此本算法的復雜度為O(I′J′K)，其中I′與J′數量相等。本算法通過社交關系僅僅提取了一部分用戶，因此社交張量模型的大小遠小于一般的張量模型。此外，本模型中也不包含項目。

算法1社交關系張量的計算算法

輸入：歷史記錄H, 社交張量S, 步長η, 參數α，β

1. 初始化U,A,S,C,S為0;

2. foreach (用戶ui, 社交用戶uj,上下文ck)

4. thenSi,j,k=|shi,j,k|; elseSi,j,k=0。

5. endfor

5. foreach (活動用戶ui, 社交用戶uj)

7. then Ai,j=sai,j；elseAi,j=1；

8. endfor

9.l=0;t=t0;

10. while (未達到收斂條件) do

12. foreachSTi,j,k≠0 do

13. Ui*←Ui*-η?Ui*Fl;

Sj*←Sj*-η?Sj*Fl;

Ck*←Ck*-η?Ck*Fl++;

14. 計算成本函數式(8)；

3.2 學習社交張量

因為本模型不包含項目信息，將活動用戶歷史記錄的電影列表與社交用戶的列表進行比較，獲得一個候選集。跳數?對社交張量與電影列表具有影響，如果考慮一個小規模的社交網絡即可發現合適的項目，那么無需對于全部社交網絡進行計算，這樣能夠大幅度地降低計算時間。因此設計了一個自適應算法發現活動用戶ui合適的跳數，目標函數定義為：

ni=4/π·tan-1((ui-hi)/λ)+

1/π·cot-1((ui+hi)/μ)+??-1/4

(12)

式中：λ與μ均為采樣頻率相關的參數，ui與ηi分別為命中與未命中的推薦數量。反余切的取值范圍為-π/2～π/2，將活動用戶ui的跳數范圍四舍五入為||ni||。式(12)由以下4項組成：(1) 第1項控制hop的方向，對應于命中與未命中推薦之間的差異。(2) 第2項調節推薦數量的變化速度。(3) 第3項表示默認的跳數，根據實驗結果本文設為3。(4) 第4項將范圍值四舍五入為最終跳數。

將ui+ηi轉化為ni，式(12)變為式(13)，式(13)的函數形狀不受第3項影響，第1項也獨立于ni與ηi。將ni-2ηi除以ni，如下所示：

ni=4/π·tan-1((mi-2hi)/λ)+

1/π·cot-1((mi)/μ)+??-1/4

(13)

ni=4/π·tan-1((mi(1-2·hi/mi))/λ)+

1/π·cot-1((mi)/μ)+??-1/4

(14)

從式(14)可得出結論，函數的形狀獨立于推薦的精度hi/mi。圖5所示是精度與跳數的關系曲線，圖中未對結果做四舍五入取整數處理，圖中hi/mi=1的精度最高，其次為hi/mi=0.5，hi/mi=0的精度最差。圖中ni的范圍為[1,5]。因為本方法的社交張量中不包含項目信息，所以需要基于張量分解的結果尋找合適的項目。算法2所示是本推薦系統的具體步驟：

步驟1初始化社交范圍為缺省值3跳。

步驟2建立社交張量、分解社交張量來獲得最優上下文與社交用戶。

步驟3基于上下文與社交用戶產生一個項目推薦列表。

圖5 精度與跳數的關系曲線

本文中基于重疊聯合算法實現兩個電影之間的相似性度量，sim(mi,mj)表示兩個電影mi與mj之間的相似性。

算法2推薦算法的偽代碼

輸出：用戶ui在ck上下文與uj社交用戶的K部電影列表CM

1. 式(12)計算社交關系的范圍，獲得跳數ni；

2. 社交張量分解(H,S,η,α,β)；

3. forl=0 toK-1 do

5.Ci=Ci∪{Cl};

6. forl=0 tok-1 do

7. foreachui的社交關系用戶ujdo

8.Mi,k=∑?jmi,k，

9.mi,j,k∈H，

11.cml=max?cmj∈(CM-CM′)1/|Mk*|

∑?mk ∈Mk*sim(mk,cmj)

12.CM′=CM′∪{cml}；

13. returnCM′

4 實驗與結果討論

首先評估三個參數對本系統的影響，分別為：??、λ、μ，然后測試了系統的稀疏性問題、冷啟動問題與響應時間。實驗環境為PC機：Intel core i7-4790，3.6 GHz CPU，16 GB內存。操作系統為Window 10，采用Python編程語言實現所有的算法，采用MySQL作為數據庫。

4.1 實驗數據集

因為本文的推薦系統考慮了時間與空間上下文環境以及社交關系，所以許多公開的benchmark數據集(例如：MovieLens數據集)[14]無法滿足本系統的實驗要求。使用爬蟲工具從“豆瓣電影”網站抓取239 503部電影信息，2015年之后注冊的221個用戶信息，然后，從221個用戶中選出歷史記錄達到5部電影的用戶，最終，篩選出滿足條件的198個用戶與1 683部電影。表1是實驗數據集的統計信息。

表1 實驗數據集的統計信息

續表1

4.2 算法參數實驗

為了研究算法中參數對推薦精度[15]的影響，設置了3組預處理實驗，分別測試??、λ、μ三個參數對推薦精度的影響，??為社交張量的跳數，λ為稀疏性問題的采樣頻率，μ與新用戶的采樣頻率有關。

本方法使用活動用戶的社交網絡及其歷史記錄解決推薦系統的稀疏性與冷啟動問題，因此，本方法獨立于缺省值??。采用五-折交叉檢驗對不同的??參數值進行了實驗，取值范圍為2～4，最小值設為??=2，所以最優情況是本算法收斂至0。本實驗采用三個固定值，如表2所示，??=3為最優值。

表2 不同??參數值的推薦性能結果

λ通過增加推薦數量來控制跳數，采用不同的λ參數值進行推薦實驗，其中??設為定值3。表3是不同λ參數值的推薦性能結果，表中可看出，當λ=10，推薦系統的性能最優。

表3 不同λ參數值的推薦性能結果

最終，測試不同μ參數值評估推薦系統的性能，表4所示是不同μ參數值的top-n推薦精度。表中可看出，μ=10獲得了最優的性能。

表4 不同μ參數值的推薦性能結果

4.3 算法性能實驗

4.3.1稀疏性問題的實驗

采用精度指標評估推薦系統的性能，圖6所示是不同推薦算法對于全部benchmark數據集的精度結果。本系統的性能明顯高于CMFCAR[7]、RCATF[9]兩個算法，CMFCAR與RCATF均為用戶上下文的張量模型，因此可得出結論，社交關系的張量模型有效地緩解了稀疏性問題，取得了更好的推薦精度。

圖6 稀疏性問題的推薦結果

4.3.2冷啟動問題的實驗

在冷啟動實驗中，本系統明顯地提高了推薦的質量，如圖7所示。CMFCAR算法中也包含了社交親和力的處理，其推薦精度略高于RCATF，可見社交親和力能夠緩解冷啟動問題。此外,CRSC[5]也能夠為新用戶生成推薦，而本系統明顯高于其他三個算法，一方面是社交親和力的效果，另一方面用戶上下文也提供了有力的推薦依據。

圖7 冷啟動實驗的推薦結果

4.3.3響應時間

響應時間是推薦系統的一個重要指標，直接決定了推薦系統的實用性。數據集包括2 621個歷史記錄、198個用戶與1 683部電影，因此，CMFCAR矩陣大小為198×1683，RCATF算法的四階張量包含1 683部電影、198個用戶、13個時間上下文與3個空間上下文。本系統僅使用一部分社交網絡數據集建立社交張量，由此大幅度降低了處理時間。

圖8所示是4個推薦算法的平均響應時間，RCATF的推薦時間最長響應時間超過20 s，CMFCAR的響應時間略低于RCATF，但是也超過了20 s，具有較高的研究意義，但是實用性不足。本推薦系統的張量中并未包含所有的項目信息，并且也僅僅篩選出一部分的社交關系作為張量的元素，因此計算復雜度為O(I′J′K)，其中I′與J′數量相等，響應時間約為3 s。

圖8 四個推薦算法的平均響應時間

5 結 語

為了解決大數據推薦系統的冷啟動問題與稀疏性問題，引入了用戶的社交關系信息，將社交網絡引入張量模型中，本推薦系統考慮了活動用戶、項目信息、時間上下文、空間上下文與社交關系等因素。本文設計了社交關系的張量模型，實時地完成張量的再生與分解，并且推薦系統支持多上下文環境的推薦。基于真實數據集的實驗結果證明，本算法提高了推薦系統的推薦精度，有效地緩解了稀疏性問題與冷啟動問題，并且實現了較短的響應時間。