李淑霞 楊俊成* 蔡增玉

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

0 引 言

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

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

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

1 動機與研究意義

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

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

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

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

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

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

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

2 格式說明

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

2.1 定 義

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

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

為了簡化分析，考慮一個單一上下文的簡單案例，社交網(wǎng)絡中僅有一個活動用戶，以及該活動用戶相關的社交網(wǎng)絡。圖2是社交張量生成與分解的示意圖?；顒佑脩魎i存在兩種情況：一種是ui已經(jīng)存在于系統(tǒng)中，另一種是unew為新用戶?；顒佑脩舯硎緸閺埩康囊粋€灰色立方體與灰色圓形，新用戶表示為虛線立方體與黑色圓形。

圖2 社交關系張量的產(chǎn)生與分解

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

(1)

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

2.2 社交張量的建立

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

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

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

2.3 社交張量的分解

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

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

2.4 數(shù)據(jù)結構

(2)

3 基于社交張量的推薦系統(tǒng)

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

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)

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

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

(8)

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

(9)

(10)

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

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

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

(11)

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

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

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

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. 計算成本函數(shù)式(8)；

3.2 學習社交張量

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

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

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

(12)

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

將ui+ηi轉(zhuǎn)化為ni，式(12)變?yōu)槭?13)，式(13)的函數(shù)形狀不受第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)可得出結論，函數(shù)的形狀獨立于推薦的精度hi/mi。圖5所示是精度與跳數(shù)的關系曲線，圖中未對結果做四舍五入取整數(shù)處理，圖中hi/mi=1的精度最高，其次為hi/mi=0.5，hi/mi=0的精度最差。圖中ni的范圍為[1,5]。因為本方法的社交張量中不包含項目信息，所以需要基于張量分解的結果尋找合適的項目。算法2所示是本推薦系統(tǒng)的具體步驟：

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

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

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

圖5 精度與跳數(shù)的關系曲線

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

算法2推薦算法的偽代碼

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

1. 式(12)計算社交關系的范圍，獲得跳數(shù)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 實驗與結果討論

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

4.1 實驗數(shù)據(jù)集

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

表1 實驗數(shù)據(jù)集的統(tǒng)計信息

續(xù)表1

4.2 算法參數(shù)實驗

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

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

表2 不同??參數(shù)值的推薦性能結果

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

表3 不同λ參數(shù)值的推薦性能結果

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

表4 不同μ參數(shù)值的推薦性能結果

4.3 算法性能實驗

4.3.1稀疏性問題的實驗

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

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

4.3.2冷啟動問題的實驗

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

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

4.3.3響應時間

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

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

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

5 結 語

為了解決大數(shù)據(jù)推薦系統(tǒng)的冷啟動問題與稀疏性問題，引入了用戶的社交關系信息，將社交網(wǎng)絡引入張量模型中，本推薦系統(tǒng)考慮了活動用戶、項目信息、時間上下文、空間上下文與社交關系等因素。本文設計了社交關系的張量模型，實時地完成張量的再生與分解，并且推薦系統(tǒng)支持多上下文環(huán)境的推薦?；谡鎸崝?shù)據(jù)集的實驗結果證明，本算法提高了推薦系統(tǒng)的推薦精度，有效地緩解了稀疏性問題與冷啟動問題，并且實現(xiàn)了較短的響應時間。