吳 彪，溫 雯，郝志峰,2，蔡瑞初

(1.廣東工業(yè)大學 計算機學院，廣東 廣州 510000； 2.佛山科學技術大學 數(shù)學與大數(shù)據(jù)學院，廣東 佛山 528225)

0 引 言

現(xiàn)有的推薦算法主要基于用戶的歷史行為，卻沒有充分解決兩個關鍵性的問題：①用戶直接行為的稀疏性以及用戶對于不同項目的喜好之間的差異性；②在模型中融合各方面的信息，拓展用戶的行為模式。相比于用戶的信息而言，獲取項目的信息則顯得更加容易，如商品的屬性。對于用戶而言，喜歡的項目往往具有聯(lián)系。因此，利用項目的信息輔助推薦具有重要意義。不同的項目對于用戶的吸引力存在差異性，如何有效刻畫項目之間的關系以及用戶對其的喜好程度，是一項具有挑戰(zhàn)性的工作。

本文利用用戶-項目的交互記錄和項目的屬性信息，從用戶的相對喜好的角度出發(fā)，設計了一個融合多種復雜共現(xiàn)信息的框架，將傳統(tǒng)的推薦問題轉化為異構網絡的節(jié)點嵌入問題，同時將項目的多種信息轉化為子圖，從子圖內部找出真正具有相近意義的節(jié)點，進而將稀疏的特性替換成連續(xù)的向量表達。根據(jù)子圖節(jié)點的不同組合，關注用戶的多種行為模式，而不局限于關注用戶的點擊行為。對于圖而言，通過不同的節(jié)點跳轉，引入用戶的間接行為，同時刻畫節(jié)點之間相似度的差異，并利用Bayesian personal ranking(BPR)[1]優(yōu)化準則和隨機梯度下降算法進行模型求解。最后，在多個數(shù)據(jù)集的實驗結果表明，本文提出的方法具有更好的推薦效果。

1 相關工作

推薦算法主要包括以下幾個方面的技術：

(1)傳統(tǒng)的基于矩陣分解的方法：早期的推薦系統(tǒng)工作主要是基于直接的用戶-物品交互記錄進行推薦，但由于交互記錄的高度稀疏性，使得推薦的性能受到一定限制。因此，各種不同的降維方法被用來解決這個問題，如非負概率矩陣分解(NMF)[2]、概率矩陣分解(PMF)[3]等，這些方法有助于產生更好的推薦性能，但是它們必須經過復雜的矩陣分解步驟。為增強項目的表示，Liang等[4]提出用項目共現(xiàn)對用戶-項目矩陣的分解進行正則化，其原理相當于在矩陣分解的聯(lián)合目標下學習用戶和項目的向量化表示，雖然該模型利用了用戶-項目的交互信息和項目-項目之間的共現(xiàn)信息，但是其將所有具有共現(xiàn)的項目進行等價對待，無法體現(xiàn)差異性。另一方面，用戶與項目之間的行為還包括間接但更復雜的形式(例如，“購買產品”、“選擇項目標簽”或“回答在線問題”)，這使得用戶的反饋具有多樣化、異構性且未必顯而易見等特征。相對于稀疏的顯式行為而言，用戶的隱式行為則顯得更加稠密。而上述方法僅僅根據(jù)用戶的顯式行為進行學習，并沒有直接利用隱式行為優(yōu)化其排名。

(2)基于個性化排序的方法：基于個性化排序是推薦系統(tǒng)中的一類重要技術，其主要思想是將節(jié)點之間傳統(tǒng)的直接關系轉變?yōu)橄鄬﹃P系。Rendle等[1]提出基于個性化排序的算法，用邏輯回歸算法，將個性化排序融入到推薦系統(tǒng)中，利用隱式反饋解決推薦問題,但其局限于用戶的喜好，沒有利用項目的其它信息。WARP[5]采用權重近似化，對節(jié)點進行排序。由于用戶的直接行為的高度稀疏性，Yang等[6]在圖上進行隨機游走，為每個用戶獲取相鄰項之間的高階信息，引入用戶的間接行為，隨后將其轉化為用戶對項目的喜好程度的差異性，采用個性化排序算法學習其向量表示，但是其僅關注用戶間的行為，使得推薦局限于熱門的項目。于洪等[7]結合多種信息獲得個性化權重得分，提出一種解決新項目冷啟動問題的推薦算法。戴琳等[8]則利用多種信息，將個性化排序用于餐館推薦中，獲得更好的推薦效果。

(3)圖是一種天然的表示用戶-項目交互信息的結構，因此基于圖模型的推薦算法受到廣泛關注?；趫D的推薦方法的主要思想是通過用戶-項目的記錄建立圖的關聯(lián)，然后應用隨機游走技術捕獲潛在的信息和生成項目排序。Ming等[9]提出BiNE網絡，將用戶-項目的交互行為視為二分圖，并在二分圖上進行高階節(jié)點的映射。Cai等[10]在二分圖的基礎上融合用戶的信息，并用隨機游走技術生成用戶-項目對，學習用戶、項目的向量表示。隨著Skip-gram[11]思想的發(fā)展，部分工作將一組項目視為單詞序列，并對用戶-項目交互記錄應用skip-gram negative sampling(SGNS)來學習每個項目的嵌入向量[12,13]。王娜等[14]用SGNS模型分析用戶播放視頻行為，提取視頻的特征，并用聚類算法建模用戶興趣分布矩陣。Vasile等[15]在此基礎上加入異構信息，豐富該模型。其它類似的在異構圖上學習節(jié)點信息的工作還包括Cen等的研究[16-18]。

2 COIR模型

我們著重關注帶有項目信息的場景下，學習用戶/項目的潛在語義表示，從而進行推薦。用戶-項目的直接交互行為能夠提供顯式的信息，而用戶/項目的間接交互行為等其它信息能夠提供隱式的信息。直覺上，相似的項目往往會被同一用戶所喜好，但是，用戶對相似的項目的喜好程度具有一定的差異性，具體體現(xiàn)為用戶是否與該項目具有交互記錄。本節(jié)中，首先給出問題的形式化描述及相關符號約定(如表1所示)，然后給出模型的細節(jié)和優(yōu)化算法。

表1 符號及其定義

2.1 問題定義

給定用戶的點擊信息及項目的屬性信息，如圖1所示，我們的目標是為用戶推薦其可能感興趣的項目。由于項目-項目之間的連接存在多種形式，如通過類別標簽進行連接，或者通過用戶進行連接。由圖1我們可以觀察到：

(1)兩個項目之間具有邊，代表它們具有一定的相似度。如圖1所示，項目1和項目2都具有health這個標簽，即項目1和項目2之間有邊存在，代表它們屬于同種類別。

(2)相關聯(lián)的項目之間，其相似性具有一定的差異性，該差異性在推薦系統(tǒng)中體現(xiàn)為用戶對于不同的項目的喜好程度。如圖1所示，項目1、項目2、項目3都具有共同標簽health，但是通過用戶-項目子圖可以發(fā)現(xiàn)，項目2和項目3被更多的用戶所同時喜愛，因此，相對于項目1、項目2和項目3之間的相似度更好。

(3)在帶項目屬性的行為數(shù)據(jù)中，通過節(jié)點之間的跳轉，用戶可以找到其喜愛的商品的類似商品或者具有相似行為的用戶所喜愛的商品。如圖1所示，僅僅通過用戶-項目的交互記錄(即圖中的實線邊)，由于用戶2沒有和其它用戶具有相似行為，很難對其進行精準推薦，但可以通過“項目-標簽-項目”的連接，能夠找到相似的項目，從而定位用戶2的興趣。

(4)用戶-項目的直接交互行為很稀疏，但是間接的用戶-項目的行為則稠密很多。如圖1所示，用戶-項目之間的二分圖的邊的稀疏性表明了直接交互行為很少。另外一方面，直接相連的用戶-項目之間相近程度明顯高于非直接相連的用戶-項目，而間接相連的用戶-項目的相似度明顯大于完全不相連的用戶-項目之間的相似度。對于用戶3而言，其明顯更加喜愛項目2，而非項目1。

圖1 融合項目屬性信息的u-i圖實例

結合上述觀察，為融合不同的方式，我們通過構建圖網絡來進行描述。對于具有用戶的點擊信息及項目的屬性信息的推薦任務，可以轉化為如下形式化的圖網絡上的節(jié)點嵌入問題。

定義項目子圖GI=，其中I={I1,…,IN}表示項目的節(jié)點，EI表示為項目-項目之間的關聯(lián)邊，具體可體現(xiàn)為具有相同的標簽或與同一用戶具有共同交互記錄。

定義用戶-項目子圖GUI=，其中U=，I={I1,…,IN},EUI表示用戶-項目之間的交互信息。

如圖2所示，對于給定的推薦場景，其包括項目子圖GI以及用戶-項目的子圖GUI，我們的目標是在其共同組成的圖網絡中學習用戶和項目在同一向量空間中的低維向量表示，從而找到用戶的興趣，對用戶推薦其感興趣的項目。

圖2 COIR模型

2.2 模 型

基于用戶-項目之間的交互信息，我們將這兩個子圖構建為一個異構信息網絡，從而在融合各方面的共現(xiàn)信息框架下學習用戶/項目的語義表示，以下簡稱為COIR(co-occurrence information ranking algorithm)。

根據(jù)2.1節(jié)所述的觀察，我們的目標是基于圖網絡的節(jié)點嵌入表達學習，結合Skip-gram模型的思想和個性化排序，分別在兩個子圖上定義其相關的損失函數(shù)，定義為LI，LUI，這兩個損失函數(shù)通過共同的項目進行連接，具體的損失函數(shù)如下

(1)

式中：α是體現(xiàn)每一項重要程度的參數(shù)，θ和φ分別是用戶和項目的特征向量表示，λ為正則化系數(shù)。

對于項目子圖中的損失函數(shù)LI，基于2.1節(jié)觀察(1)，觀察(2)可知：給定項目i，假設項目j是項目i的k階鄰居，則

(2)

式中：wij表示的是該項的置信度。

顯然，根據(jù)前面的觀察可得，項目i與項目j被越多的用戶共同喜歡，置信度越高，且置信度與節(jié)點j距離節(jié)點i的距離相關。因此，我們將其定義為

(3)

式中：Ieui是一個指示器，指示用戶u與項目i是否有交互記錄。

為了將節(jié)點網絡相似度結合到模型中，可以將LI中的條件概率設計為

(4)

顯然，計算p(j|i)是一項十分耗費時間的工作，因此，采用負采樣技術計算上述公式，從而

(5)

對于損失函數(shù)LUI，基于個性化排序的思想以及前面所述的觀察，可得以下?lián)p失函數(shù)

(6)

用戶的間接行為數(shù)量眾多，計算所有的組合顯然是不現(xiàn)實的，因此，根據(jù)隨機游走和負采樣的技術，生成一定比例的樣本組合Dui和Diu，結合上述等式，GUI上的損失函數(shù)為

(7)

式中：wuii′和wiuu′表示的是該項的置信度。根據(jù)前面的觀察可得，當兩個節(jié)點越接近，其置信度越高，為此

(8)

式中：kui表示的是用戶u和項目i的距離。

考慮用戶-項目之間的交互節(jié)點網絡的相似度，對于概率的計算方式為

p(i >ui′|θ,φ)∝σ(θ(u)·φ(i)-θ(u)·φ(i′))

(9)

2.3 算 法

基于上一小節(jié)所述的模型，COIR模型的訓練框架主要包含兩部分的信息，分別是構建子圖，生成訓練樣本和優(yōu)化損失函數(shù)，更新向量，具體處理步驟如下：

步驟1 構建項目子圖GI，用戶項目交互子圖GUI。根據(jù)子圖GI和GUI定義，分別構建對應的子圖。其中，對于項目子圖GI，其邊EI表示為具有相同的標簽或與同一用戶具有共同交互記錄。

步驟2 生成訓練樣本Di、Dui與Diu。訓練樣本的生成算法如算法1所示，其中，Dui與Diu的生成過程與Di相類似，其差異僅在于二者的概率轉移矩陣不同。概率轉移矩陣是根據(jù)對應子圖的鄰接矩陣的行元素做歸一化后獲得的。

步驟3 隨機初始化用戶低維向量表示θ，項目的低維向量表示φ。

步驟4 根據(jù)式(1)計算損失函數(shù)L。

步驟5 使用隨機梯度下降算法優(yōu)化損失函數(shù)，更新θ和φ。

對于訓練樣本的生成算法如算法1所示，其主要思想是對于每個節(jié)點，根據(jù)概率轉移矩陣隨機生成下一節(jié)點，獲取K階鄰居，同時補充一定數(shù)量的負樣本(非鄰居節(jié)點)，從而生成一定數(shù)量節(jié)點對，并根據(jù)式(3)計算相應節(jié)點對的權重。

算法1：生成訓練樣本

輸入：項目子圖GI，項目概率轉移矩陣Ti，最大階數(shù)K，每個節(jié)點重復次數(shù)R，負樣本比例NS

輸出：樣本集Di

(1)初始化Di為空集

(2)for r ← 1 to R do //每個節(jié)點重復R次

(3) for i in GIdo

(4) Cnode = node

(5) for k ← 1 to K do

(7) P(i) = unode ∪ P(i)

(8) Cnode = unode

(9) end for

(10) for n ← 1 to NS do //生成負樣本

(11) Nv ～ NegativeSample(Cnode)

(12) NP(i) = Nv ∪ NP(i)

(13) end for

(14) for nodes in P(i) do //生成節(jié)點對

(15) j ～ P(i)

(16) j’～ P(i)

(17) Calculate wijj’as formulate(3)//根

據(jù)式(3)計算權重

(18) Di ∪

(19) end for

(20) for nv in NP(i) do //生成節(jié)點對

(21) Di ∪

(22) end for

(23) end for

(24) end for

2.4 復雜度分析

由框架流程可知，訓練過程最主要的時間花費包括兩部分：

(1)樣本生成過程

如算法1所述，對于GI中的每個節(jié)點i，生成R個序列，最大階數(shù)為K，假設每個節(jié)點的平均出度為|E|，N為項目的總節(jié)點數(shù)，即總共生成的樣本數(shù)量為|K-1!|×R×N對，而負樣本比例為NS，所以總共生成|NS×K×R×N|個樣本對，在樣本Di生成過程中，花費時間為O(|K-1!|×R×M)+O(|NS×K×R×N|)，由于|E|<

Dui、Diu的生成過程與Di生成過程類似，差異僅在于節(jié)點之間的概率轉移矩陣Tui與Ti不同，意味著Dui、Diu具有更多的節(jié)點集合，因此，樣本Dui與Diu生成過程其時間復雜度為O(|NS×K×R×N×M|)，其中，M為用戶節(jié)點數(shù)。

所以，樣本生成過程的總的時間復雜度為O(|NS×K×R×N2|)+O(|NS×K×R×N×M|)。

(2)訓練優(yōu)化過程

在優(yōu)化的過程中，梯度計算和變量更新的傳播與生成的樣本數(shù)量、變量的維度d相關。因此，該過程的時間復雜度為O(d×NS×K×R×(N+M))。

綜上所述，本文的算法的總復雜度為O(|NS×K×R×N2|)+O(|NS×K×R×N×M|)+O(d×NS×K×R×(N+M))，由于維度d遠遠小于用戶和項目的節(jié)點數(shù)目，從而，總體時間復雜度為O(|NS×K×R×N2|)+ O(|NS×K×R×N×M|)。

一般而言，傳統(tǒng)的矩陣分解算法，其時間復雜度為O(|M×N|)。對于BPR算法，其時間復雜度與訓練樣本數(shù)、節(jié)點數(shù)相關，且其算法包括采樣部分，具體可概括為O(|NS×R×N×M|)。對于HopRec算法，同樣包括高階行為的樣本產生過程且該過程與本文類似，即算法復雜度為O(|NS×K×R×N×M|)。由于N、K、R一般數(shù)值較小，因此以上幾類算法時間復雜度差異較小，而上述幾類算法被廣泛用于實際的推薦系統(tǒng)中，包括大規(guī)模數(shù)據(jù)集。因此，本文的算法與上述幾類算法具有同樣的適用性。

3 實驗與結果分析

3.1 數(shù)據(jù)集

本文使用了QAR數(shù)據(jù)集和Citation數(shù)據(jù)集，具體數(shù)據(jù)集的情況見表2，其基本特征如下：

表2 數(shù)據(jù)集情況

QAR(https://biendata.com/competition/bytecup2016)：該數(shù)據(jù)集來自一個數(shù)據(jù)競賽，其包括應答者-問題交互記錄、應答者/問題標簽。該數(shù)據(jù)集中共有28 745個用戶，8090個問題和33 981條回答記錄。此外，還有143個用戶標簽和20個問題標簽。每個用戶平均有兩個回答記錄，每個問題有一個問題標簽。

Citation(https://www.aminer.cn/citation)：該數(shù)據(jù)集是一個廣泛使用的數(shù)據(jù)集，用于評估社交網絡上的各種數(shù)據(jù)挖掘任務。該數(shù)據(jù)集包括學術論文及其引用關系。通過刪除沒有任何標記的作者/文章，選擇17 959名作者和8074篇文章進行評估。引用關系被視為評價作者是否真的對某篇論文感興趣的依據(jù)。

CiteULike(http://www.wanghao.in/CDL.htm)：該數(shù)據(jù)集來自CiteULike和谷歌Scholar，主要用于評估推薦任務。其包括7947個用戶，25 975個項目。

以上所有的數(shù)據(jù)集均采用隨機抽樣的方式，隨機抽取80%的用戶-項目交互記錄作為訓練樣本，剩余的20%作為測試樣本。

3.2 評價指標

對于每個待評測的用戶，選擇與其最接近的Top-K個項目作為候選列表，本文用HR(hit ratio)、NDCG(normalized discounted cumulative gain)和MAP(mean average precision)作為推薦質量的評價指標。這些指標被廣泛用于信息檢索和推薦系統(tǒng)中。

3.3 模型對比

以下幾類算法被用于作為基礎模型進行對比實驗，選擇這些算法的原因是：它們與本文的模型密切相關，并且被廣泛用于各種推薦系統(tǒng)。

(1)PMF[3]：矩陣分解的模型，根據(jù)用戶-項目的交互行為進行矩陣分解。

(2)WARP[5]：一種有效估計排序函數(shù)的近似方法，其主要思想是根據(jù)節(jié)點對在排名列表中的位置，衡量它們的差異性。

(3)BPR[1]：基于矩陣分解的模型，將推薦問題轉化為排序問題。根據(jù)可觀測到的正樣本，從未觀測到的數(shù)據(jù)中隨機抽取與其對應的實例作為負樣本，最后用于隱式反饋推薦。

(4)HopRec[6]：基于用戶-項目的直接行為，同時考慮用戶-項目的間接行為，利用隨機游走技術生成一定比例的間接行為，最后轉化為矩陣分解進行求解。

(5)Meta-Prod2vec[15]：基于用戶-項目交互信息，融入額外的項目信息構成異構圖，并在此異構圖上采用Skip-Gram的思想進行求解。

3.4 參數(shù)設置

模型涉及了主要參數(shù)包括權重α，階數(shù)K。在本次實驗中，α設置為1，階數(shù)K為2。隨機梯度下降算法使用的是ADAM[19]算法。在對比方法的設置中，采用了網格搜索的形式，展示其在較優(yōu)參數(shù)設置下的結果。

3.5 結果與分析

本文將從以下2個角度分析COIR模型：①將COIR模型與現(xiàn)有的基準模型進行對比，比較它們在不同的評價指標下的效果；②討論參數(shù)敏感度對結果的影響。

3.5.1 總體實驗結果

在3個數(shù)據(jù)集上的實驗結果分別見表3～表5。顯然，我們的方法在各個數(shù)據(jù)集上有突出的作用，也驗證了我們的設置是有效的。相較于傳統(tǒng)的矩陣分解方法PMF，BPR模型利用用戶的顯式行為和隱式行為之間的排名，效果相對突出。HopRec算法增加了用戶的間接行為，并對其進行排序，其比直接的帶權排序算法WARP的效果有所提升，由此可見用戶的間接行為也是有效的。Meta-Prod2vec通過額外的項目信息，增加了項目之間的連接，其結果比只用用戶-項目交互行為的PMF模型更好，驗證了項目-項目的共現(xiàn)信息是有用的。相比于Meta-Prod2vec模型，我們的模型增加了用戶間接行為的個性化排序信息，在3個數(shù)據(jù)集上各項指標都有所提高，而且具有更加穩(wěn)定的效果，由此表明間接的行為的個性化排序是有效的。相比于個性化排序模型，我們的COIR模型融合了項目的信息，對比效果最好的個性化排序模型，在3個數(shù)據(jù)集上HR值分別提高了10%、12%和24%，NDCG值分別提高了15%、17%和30%，MAP值分別提高了18%、19%和16%，實驗結果表明了前面所述的假設的正確性，即項目的信息對于推薦的效果的提高是有意義的。

表3 QAR數(shù)據(jù)集上Top10的實驗結果

表4 Citation數(shù)據(jù)集上Top10的實驗結果

表5 CiteULike數(shù)據(jù)集上Top10的實驗結果

3.5.2 參數(shù)敏感度

該部分將重點討論包括本文方法在內的幾種方法共有的參數(shù)，即維度d對于實驗效果的影響，并用MAP值(平均精度均值)展示實驗的效果。設置維度d的范圍為{50,100,200,300,400,500}，其效果如圖3所示。顯然，COIR模型的效果隨著維度的增加而上升，當d≥300時，效果趨向穩(wěn)定，由此可見，COIR模型能夠有效融合多種復雜的信息。

圖3 維度對比

4 結束語

本文將傳統(tǒng)的推薦問題轉化為圖的表示學習問題，利用不同的信息構建不同的子圖，通過子圖節(jié)點的跳轉，刻畫用戶的不同行為喜好。同時為了解決數(shù)據(jù)稀疏性，引入了項目的信息和用戶的間接行為并對其進行個性化排序，最終將多種復雜的信息融合在一個模型中進行用戶、項目的向量化表示學習。實驗結果表明，COIR方法是有效的。顯然，引入項目的信息和用戶的間接行為，一定程度上能夠處理數(shù)據(jù)稀疏性問題，并通過用戶行為相似度的排序，進行更精準的推薦。然而，兩個組成部分的作用在適應性上有一定的局限性，下一步將引入注意力機制，使得框架自己學習各個部分的權重，從而具有更好的可拓展性。另外，該模型僅僅是一個不考慮時效性的模型，下一步的研究工作將拓展到在線學習方面的工作，并應用到具有時序信息的用戶行為。