基于社交上下文和神經(jīng)網(wǎng)絡(luò)的增量推薦算法

鄒 鋒

(廣州商學院 信息技術(shù)與工程學院，廣東 廣州 511363)

0 引 言

經(jīng)典的協(xié)同過濾推薦系統(tǒng)通常使用k-近鄰(k-nearest neighbor，k-NN)技術(shù)[1]尋找和目標用戶(或項目)最相似的top-k用戶(或項目)，然后為目標用戶推薦其近鄰用戶偏愛的項目。矩陣分解[2]是一種推薦系統(tǒng)的經(jīng)典方法，大數(shù)據(jù)情況下矩陣運算的效率較低。基于內(nèi)存的推薦系統(tǒng)又分為基于用戶的推薦方式和基于項目的推薦方式[3]，基于項目的推薦方式比基于用戶推薦方式的準確率高，前者傾向于向用戶推薦相似的項目，而這會引起嚴重的“馬太效應(yīng)”[4]。

為了在保證高推薦準確率的前提下，降低推薦項目的馬太效應(yīng)，許多學者設(shè)計了改進算法以提高推薦結(jié)果的多樣性、新穎性以及推薦列表滿意度。文獻[5]需要迭代地尋找推薦列表的帕累托最優(yōu)解，雖然實現(xiàn)了理想的指標，但是其計算效率較低。與文獻[5]屬于同一類型的算法還有：基于多目標粒子群的系統(tǒng)[6]、基于布谷鳥搜索的系統(tǒng)[7]和基于獅群優(yōu)化算法的系統(tǒng)[8]等。另一方面，通過結(jié)合成熟的聚類技術(shù)來提高推薦的多樣性也是一種有效手段，文獻[9]設(shè)計了基于模擬退火的聚類技術(shù)對項目進行精準的分類處理，通過模擬退火的優(yōu)化技術(shù)保證了聚類結(jié)果的多樣性，由此提高推薦結(jié)果的多樣性。與文獻[9]屬于同一類型的算法還有：基于去中心化聚類的推薦系統(tǒng)[10]、基于增量回歸模型的推薦系統(tǒng)[11]、基于關(guān)聯(lián)規(guī)則和聚類處理的推薦系統(tǒng)[12]等。上述推薦系統(tǒng)均能夠有效提高推薦效果，但計算時間較長，每當數(shù)據(jù)發(fā)生較大變動均需要重新訓練全部數(shù)據(jù)集，無法滿足推薦系統(tǒng)的實時性需求。

詞嵌入模型在許多應(yīng)用領(lǐng)域中表現(xiàn)出良好的性能，如詞嵌入在文本情感分類方面的應(yīng)用[13]。神經(jīng)網(wǎng)絡(luò)語言模型(neural network language model，NNLM)是一種性能突出的詞嵌入方法，能夠精確地根據(jù)上下文預測出當前詞。本文將用戶個人檔案、顯式反饋信息和隱式反饋信息作為上下文，利用NNLM預測特定上下文偏愛的項目列表。將NNLM運用于推薦系統(tǒng)需要解決兩個難題：首先，需要建模NNLM的上下文結(jié)構(gòu)，本文設(shè)計了層次用戶檔案模型，并提出相應(yīng)的快速相似性度量方法；再者，神經(jīng)網(wǎng)絡(luò)的訓練計算量較大，為此本文設(shè)計了一種增量學習技術(shù)，加快神經(jīng)網(wǎng)絡(luò)的訓練速度。

1 建立詞嵌入的上下文

1.1 建立用戶檔案序列

每個用戶表示為一個項目集和一個評分集，通過以下步驟為每個用戶建立一個上下文序列：

步驟1 分析用戶評分項目的信息，將這些邊際信息補充到用戶的個人檔案內(nèi)。

為每個項目關(guān)聯(lián)一個函數(shù)e，其返回值是該項目相關(guān)的元素集，表示為函數(shù)e:I×R→I×Tk，k為每個項目相關(guān)的元素數(shù)量，T表示元素。

步驟2 將項目集轉(zhuǎn)化為元組形式。

步驟3 將整型符號排列成序列。

序列生成函數(shù)f視為上述3個函數(shù)的級聯(lián)組合，表示為f=s°t°e。例如：電影《讓子彈飛》的ID為1，用戶u對它評分5分。使用函數(shù)e獲取該電影的類型信息，發(fā)現(xiàn)電影ID=1有兩個類型：類型=7,10，函數(shù)e的輸出為元組(1, {{劇情, 5},{探險, 5}})。使用函數(shù)t獲得這些元組的符號序列，然后將電影類型轉(zhuǎn)換成ID形式，產(chǎn)生新的元組(1, {75, 105})。最終，僅需要分析用戶u評分的項目元組，即(75,105)。

1.2 提取用戶間相同子序列

不同用戶的檔案序列之間可能存在大量重復的元素，因此從n個給定的序列中提取出最長的相同子序列∑=(σ1,…,σs)。設(shè)序列α的子序列為β，β由α的元素[1, |β|]構(gòu)成。采用動態(tài)規(guī)劃求解該問題，如算法1所示，該算法逐漸填充(m+1)×(n+1)矩陣的元素，m和n分別為序列x和序列y的長度，其計算式為

(1)

式中：L[m,n]記錄了兩個序列間的最大相同子序列長度。原序列的時間復雜度和空間復雜度為O(mn)，提取子序列后的空間復雜度降至O(m)或者O(n)。根據(jù)兩個序列的最長相同子序列評價兩個用戶的相似性。

算法1：基于序列的相似性度量算法(SSM)。

輸入：序列x, 序列y。

輸出：L[m,n]

(1)L[0…m, 0…n]=0；

(2)fori={1…m} do

(3) forj= {1…n} do

(4) ifxi==yithen

(5)L{i,j} =L[i-1,j-1]+1；

(6) else

(7)L[i,j]=max(L[i,j-1],L[i-1,j])；

(8) endif

(9) endfor

(10)endfor

為了運用SSM算法度量推薦系統(tǒng)的相似性，提出了基于SSM的上下文正則化算法，如算法2所示。算法2對算法1進行了兩點修改：引入變換函數(shù)f和匹配閾值δ。其中，δ越高說明相似用戶的差異越大，該閾值根據(jù)具體應(yīng)用場景設(shè)定；變換函數(shù)則為1.1小節(jié)介紹的f函數(shù)。

算法2：推薦系統(tǒng)的SSM計算算法。

輸入：用戶u, 用戶v, 變換函數(shù)f，閾值δ

輸出：L[m,n]

(1) (x,y)←(f(u),f(v))

(2)L[0…m, 0…n]←0；

(3)fori={1…m} do

(4) forj={1…n} do

(5) ifmatch(xi，yi,δ) then

(6)L{i,j} =L[i-1,j-1]+1；

(7) else

(8)L[i,j]=max(L[i,j-1],L[i-1,j])；

(9) endif

(10) endfor

(11)endfor

1.3 相似性歸一化處理

SSM相似性的范圍為[0, min(|f(u),f(v)|)]，但協(xié)同過濾系統(tǒng)的相似性指標取值范圍一般為[-1, 1]或[0, 1]。通過式(3)的歸一化技術(shù)處理SSM相似性值

simf,δ(u,v)=SSM(u,v,f,δ)

(2)

(3)

SSM算法的計算成本較高，在推薦之前離線計算SSM相似性，推薦系統(tǒng)可以透明地利用這些相似性值。

2 Top-N推薦系統(tǒng)

2.1 Top-N推薦系統(tǒng)的模型

假設(shè)u為用戶集U中的一個用戶，推薦系統(tǒng)的目標是從項目集I中選出推薦給u的列表。協(xié)同過濾推薦系統(tǒng)利用用戶-項目的交互數(shù)據(jù)，如評分、評論和瀏覽時間等。將用戶u對項目i的評分設(shè)為rui，未評分的情況rui記為0。Iu表示用戶u評分的項目集，Ui表示對項目i評分的用戶集。Top-N推薦的目標是為用戶提供N個項目的列表。

2.2 基于內(nèi)存的推薦系統(tǒng)

協(xié)同過濾技術(shù)依賴相似的用戶集或項目集，常用k-近鄰(k-NN)技術(shù)尋找和目標用戶(或項目)最相似的top-k用戶(或項目)。基于用戶(或項目)推薦系統(tǒng)的輸出定義為

(4)

(5)

式中：s表示用戶(或項目)之間的相似性，即第1小節(jié)的SSM，rui和ruj分別表示用戶u對項目i和j的評分。

3 基于詞嵌入的推薦系統(tǒng)模型

3.1 詞嵌入表示

prod2vec[14]是一種基于項目嵌入的產(chǎn)品推薦模型，該模型利用了矩陣分解技術(shù)，無法運用于基于內(nèi)存的推薦系統(tǒng)。本文設(shè)計了新的詞嵌入推薦系統(tǒng)，同一個用戶評分的項目之間具有一定的相關(guān)性，而對同一個項目評分的用戶之間也存在一定的共性。下文以基于項目的協(xié)同過濾系統(tǒng)為例，基于用戶的推薦系統(tǒng)與之相似。本文將連續(xù)詞袋模型(CBOW)[14]和協(xié)同過濾top-N推薦系統(tǒng)結(jié)合，將推薦系統(tǒng)項目作為CBOW的詞，用戶個人檔案(以及顯式、隱式反饋信息)作為CBOW的上下文，CBOW根據(jù)上下文預測其偏好的詞。利用CBOW模型主要出于兩點考慮：①其計算效率較高，高于Skip-gram等模型；②推薦系統(tǒng)存在稀疏性問題和冷啟動問題，CBOW模型對輸入上下文平均化處理，產(chǎn)生平滑的概率估計，能夠緩解評分信息不足的情況。

圖1所示是本文推薦系統(tǒng)的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)。網(wǎng)絡(luò)隱層學習訓練樣本集，每個訓練樣本是一個目標項目和上下文數(shù)據(jù)，上下文是對該項目評分的用戶相關(guān)信息。每個用戶的訓練樣本數(shù)量設(shè)為|Iu|，輸入層由上下文向量{x1,…,xi,xi+1,…,x|Iu|}組成。

圖1 嵌入?yún)f(xié)同過濾系統(tǒng)的主要結(jié)構(gòu)

隱層神經(jīng)元數(shù)量設(shè)為d，隱層采用線性激活函數(shù)。輸入層和隱層間的連接權(quán)重表示為矩陣W∈|I|×d，矩陣每一行vj表示項目j第d維的輸入向量。項目i的隱層輸出設(shè)為hi，hi的計算式為

(6)

輸出層的神經(jīng)元數(shù)量為|I|，輸出層采用softmax激活函數(shù)。隱層和輸出層間的權(quán)重設(shè)為W′∈d×|I|，權(quán)重每一列v′i是項目i的d維輸出向量。輸出層的輸入為v′iTh，輸出值y是目標上下文的后驗分布。采用softmax激活函數(shù)計算后驗分布的概率，softmax激活函數(shù)的計算式為

(7)

通過最小化以下的損失函數(shù)來訓練神經(jīng)網(wǎng)絡(luò)

(8)

(9)

3.2 正則化處理

單隱層網(wǎng)絡(luò)中失活正則比L2正則的效果好，因此采用失活處理解決過擬合問題。在訓練階段，運用失活機制，隨機失活一定數(shù)量的單元，失活概率為p。因為本文主要學習矩陣W的權(quán)重，因此在測試階段無需正則處理。

3.3 推薦系統(tǒng)的實現(xiàn)方法

(1)失活機制在推薦系統(tǒng)的實現(xiàn)

原CBOW模型的輸入是文本語料庫，輸出是詞向量，窗口參數(shù)w控制上下文的詞數(shù)量。本文建立一個上下文文檔表示每個用戶的信息，為了將全部用戶的信息作為上下文，窗口w設(shè)為wmax來覆蓋全部的用戶信息。因為將全部用戶檔案的平均值作為輸入，所以無需考慮檔案的順序。

本文修改超參數(shù)w，在輸入層增加失活處理。如果w小于用戶檔案序列的最大長度，那么系統(tǒng)將一部分信息作為上下文，將其它信息失活。該w參數(shù)和失活率p成比例關(guān)系。

(2)推薦系統(tǒng)的相似性度量

使用式(3)計算用戶(或項目)間的相似性，采用k-NN尋找用戶(或項目)的近鄰。本文采用NN-descent[15]代替?zhèn)鹘y(tǒng)的k-NN算法，NN-descent的計算效率遠高于經(jīng)典的k-NN算法。

3.4 神經(jīng)網(wǎng)絡(luò)的增量訓練方法

推薦系統(tǒng)首先使用后向傳播技術(shù)隨機初始化矩陣W和W′，學習這兩個矩陣的參數(shù)。這不是凸優(yōu)化問題，因此通過梯度下降法尋找其局部最優(yōu)解。實際應(yīng)用中數(shù)據(jù)連續(xù)不斷地發(fā)生變化，隨時可能加入新的評分信息、新的用戶或者新的項目，本文設(shè)計了增量的系統(tǒng)更新方法，從而避免重新訓練神經(jīng)網(wǎng)絡(luò)。當加入新項目的時候，在W中增加行，在W′中增加列，隨機初始化新加入的行和列，因為矩陣內(nèi)其它的向量接近局部最優(yōu)解，所以系統(tǒng)的收斂速度較快。

4 實驗與結(jié)果分析

實驗的硬件環(huán)境為：Intel 酷睿i7 9700 K，CPU主頻為3.6 GHz，8個核心，16 GB內(nèi)存。軟件環(huán)境為：Window 10操作系統(tǒng)，基于Python編程實現(xiàn)推薦算法的算法。

4.1 實驗方法

(1)實驗數(shù)據(jù)集和預處理

采用從GroupLens網(wǎng)站獲取的MovieLens數(shù)據(jù)集進行實驗驗證，Movielens_20M數(shù)據(jù)集由20 000 263個評分構(gòu)成，評分范圍從0.5星到5星。為了支持半星的評分，本文將項目的ID乘以100，評分值乘以10，例如：用戶u對項目1的評分為3.5星，那么語句預處理的結(jié)果為1×100+3.5×10=135。表1所示是實驗數(shù)據(jù)集的基本信息，隨機劃分80%的子數(shù)據(jù)集作為訓練集，剩下的20%作為測試集，分別獨立劃分5次，完成5折交叉驗證。推薦列表的數(shù)量設(shè)為5，即top-5推薦系統(tǒng)。

表1 實驗數(shù)據(jù)集的基本信息

(2)性能評價指標

本文考慮了多個指標全面地評價推薦系統(tǒng)多個方面的性能。

1)排列質(zhì)量和推薦準確率

采用4個指標評價推薦系統(tǒng)的推薦準確率，分別為歸一化折損累計增益nDCG[16]、精度P[16]、召回率R[15]和平均精度均值MAP[16]。nDCG用來衡量排序質(zhì)量，精度P和召回率R分別用來衡量推薦項目的命中率和查全率。

2)新穎性：

EPC(expected popularity complement)[17]：定義為期望的新出現(xiàn)推薦項目數(shù)量。

EPD(expected profile distance)[17]：推薦項目和用戶偏愛項目間的距離。

3)多樣性：

α-nDCG[18]：多樣性感知的排列指標。

EILD(expected intra-list diversity)[18]：期望的列表內(nèi)多樣性。

4.2 神經(jīng)網(wǎng)絡(luò)超參數(shù)的選取

通過5折交叉驗證訓練本文神經(jīng)網(wǎng)絡(luò)模型，訓練以最大化nDCG為目標，每組實驗完成100次迭代。因為w是本文網(wǎng)絡(luò)的關(guān)鍵超參數(shù)，通過試錯法調(diào)節(jié)w，將神經(jīng)網(wǎng)絡(luò)對Movielens_20M數(shù)據(jù)集進行實驗，結(jié)果如圖2所示。圖中顯示隨著w值的升高，每次迭代所需的時間升高，且nDCG收斂曲線的質(zhì)量也提高，當w=50之后，nDCG收斂曲線質(zhì)量的提升幅度較小，但處理時間升高明顯，所以選取w=50為最佳參數(shù)。

圖2 神經(jīng)網(wǎng)絡(luò)w參數(shù)的實驗

最終獲得神經(jīng)網(wǎng)絡(luò)對于Movielens_20M數(shù)據(jù)集的最佳超參數(shù)值，見表2。

表2 神經(jīng)網(wǎng)絡(luò)超參數(shù)設(shè)置

4.3 SSM相似性驗證實驗

本文提出了新的SSM相似性度量指標，一方面該指標的計算效率較快，另一方面該指標的精度也較好。采用經(jīng)典基于內(nèi)存的協(xié)同過濾推薦算法和不同的相似性度量指標集成為不同的推薦系統(tǒng)，采用每個推薦系統(tǒng)獨立地完成實驗。本文SSM的參數(shù)δ設(shè)為5和10，將兩種參數(shù)的指標分別簡記為SSM1和SSM2，γ參數(shù)統(tǒng)一設(shè)為10。選擇3個常用相似性度量指標和本文方法比較，分別為余弦相似性Cosine、Jaccard相關(guān)性和JMSD[19]。

圖3所示是每個相似性度量指標對推薦系統(tǒng)的影響實驗結(jié)果。圖中可見余弦相似性和Jaccard的效果十分接近，且明顯好于JMSD指標。本文指標受所選取參數(shù)的影響較大，總體而言，SSM2的效果好于SSM1，且略好于Cosine指標和Jaccard指標，Cosine指標和Jaccard指標均為廣義的距離度量方法，難以對推薦系統(tǒng)所需的細節(jié)信息做深度開發(fā)，因此在推薦系統(tǒng)的應(yīng)用效果差于本文的相似性度量方法。SSM2引入了匹配閾值δ，δ越高說明相似用戶的差異越大，由于Movielens_20M數(shù)據(jù)集的數(shù)據(jù)量較大，δ=10的效果好于δ=5。本文將選用SSM2作為相似度度量方法。

圖3 SSM相似性實驗

4.4 推薦系統(tǒng)的性能

測試本文推薦系統(tǒng)在靜態(tài)完全訓練下的推薦性能。將本文推薦系統(tǒng)與下面的算法進行比較，評估各算法的性能：

SocialMF[20]：結(jié)合用戶之間的信任關(guān)系，學習用戶和項目的潛在特征向量，是一種基于矩陣分解的方法。

SocialSVD[21]：根據(jù)人際關(guān)系中的六度分隔理論計算用戶之間信任度，填充用戶信任矩陣，是一種基于奇異值分解的方法。

MIF[22]：根據(jù)互信息評價相似性，是一種基于內(nèi)存的協(xié)同過濾推薦算法。

RNNN[23]：通過循環(huán)神經(jīng)網(wǎng)絡(luò)根據(jù)過去的交互信息預測用戶未來的偏好項目，是一種基于會話相似性的協(xié)同過濾算法。

TIUII[24]：通過分析隱式反饋信息建立信任模型，并且設(shè)計了信任傳播機制，是一種基于內(nèi)存的協(xié)同過濾推薦算法。

圖4所示是各個推薦系統(tǒng)對于Movielens_20M數(shù)據(jù)集的實驗結(jié)果。MIF和RNNN均實現(xiàn)了較好的排列質(zhì)量和推薦準確率，本文算法略高于這兩個算法。SocialMF和SocialSVD是兩個以分析社交關(guān)系為核心的推薦系統(tǒng)，由于Movielens_20M數(shù)據(jù)集中包含的社交關(guān)系極少，所以這兩個算法并未獲得理想的效果。觀察新穎性實驗結(jié)果和多樣性實驗結(jié)果，本文算法的新穎性和多樣性均實現(xiàn)了顯著的提高，將圖4和圖3比較，可以發(fā)現(xiàn)本文詞嵌入模型有效地提高了基于內(nèi)存推薦系統(tǒng)的新穎性和多樣性。

圖4 靜態(tài)推薦系統(tǒng)實驗

4.5 增量推薦實驗

支持增量地更新神經(jīng)網(wǎng)絡(luò)模型是本文算法的一個特色，因此通過實驗評估本文增量推薦系統(tǒng)的性能。將數(shù)據(jù)集隨機劃分為4個大小相等的分區(qū)，首先對第1個分區(qū)進行完全訓練，并且對模型進行驗證實驗。然后將第2個分區(qū)和第1個分區(qū)結(jié)合，進行重新訓練(重新訓練的迭代次數(shù)為400次)，該模型的測試結(jié)果記為“重新訓練”模型；另外以第1個分區(qū)訓練的網(wǎng)絡(luò)為基礎(chǔ)，采用增量訓練技術(shù)訓練第2個分區(qū)的模型，分別對增量學習20次、40次、60次迭代的網(wǎng)絡(luò)進行了測試實驗。第3個分區(qū)、第4個分區(qū)采用和第2個分區(qū)相似的方式完成增量訓練實驗，結(jié)果如圖5所示。

圖5 增量推薦實驗

圖5中可看出，隨著訓練數(shù)據(jù)分區(qū)的增加，系統(tǒng)的性能逐漸提高；隨著迭代次數(shù)的增加，神經(jīng)網(wǎng)絡(luò)的性能也明顯提高。比較不同迭代次數(shù)的nDCG值，可發(fā)現(xiàn)增量訓練的模型在40次迭代已經(jīng)和重新訓練的模型十分接近，而重新訓練需要300次迭代，因此本文的增量訓練方法能夠節(jié)約巨大的時間開銷。

5 結(jié)束語

本文在離線預處理階段，將用戶的個人檔案、顯式反饋信息和隱式反饋信息建模為序列格式的上下文，并設(shè)計了基于序列的相似性度量方法。將用戶個人檔案、顯式反饋信息和隱式反饋信息作為上下文，利用NNLM預測特定上下文偏愛的項目列表。本文的增量訓練能夠通過較少的迭代次數(shù)即可達到局部最優(yōu)解，在犧牲少量推薦性能的情況下，大幅度地降低了訓練時間，能夠較好地解決用戶和項目變化劇烈的推薦問題。本文系統(tǒng)目前僅考慮了基本的反饋信息，未來將重點研究時域信息、社交關(guān)系信息等和本文推薦系統(tǒng)的集成方法。