一種嵌入項目元數據的跨項目協同過濾推薦算法

王 秀，劉學軍，陳振春，邵 帥

(南京工業大學 計算機科學與技術學院，南京 211816) E-mail： wangxiu@njtech.edu.cn

1 引 言

隨著現代化技術的逐漸普及，人們進入了一個網絡信息時代，在享受網絡帶來便利的同時也陷進了“信息過載”境遇，如何從海量的信息資源中準確而快速地尋找到自己感興趣的事物是一件及其困難的事情.而推薦系統可以有效解決這一問題，其通過收集、挖掘相關信息主動向用戶推薦相關物品.常用的推薦算法可以大致分為如下幾類：協同過濾推薦算法(Collaborative Filtering，CF)、基于內容的推薦算法(Content-based Recommendation，CB)以及混合推薦算法(Hybird Recommendation).

協同過濾是目前應用最成熟的推薦算法之一，根據用戶之間的評分、瀏覽及購買歷史等歷史行為比較，為目標用戶尋找興趣或特征相似的用戶作為鄰居，并為目標用戶推薦其可能喜歡的項目.其又可以分為基于用戶(User-based CF)和基于項目(Item-based CF)的算法兩類.User-based CF算法根據用戶對物品的喜歡情況分析用戶之間的相似性，然后推薦相似用戶喜歡過的物品；Item-based CF算法同理，根據物品被用戶的喜歡情況分析物品的相似度，然后向其推薦相似物品.

傳統的協同過濾推薦算法主要通過余弦、Pearson等方法來計算用戶間的相似度[1]，其核心思想是，將不同的項目視為不同的維度通過利用用戶-項目評分信息，然后根據用戶在相同維度上的評分來計算其相似度.然而用戶的評分數據非常稀疏[2]，用戶之間共同評分的項目因此也更少，使得當根據余弦、Pearson方法來計算用戶間的相似度時，不能準確地得到結果，致使推薦系統的性能急劇下降.

因此，本文提出了一種嵌入項目元數據的跨項目協同過濾推薦算法(A Cross-Item Collaborative Filtering Recommendation Algorithm For Embedded Item Metadata)，即CICF.將原來基于用戶共同評分項目計算相似性，通過嵌入項目元數據(即屬性信息)，利用用戶與項目及其屬性的交互，實現了基于元數據表示的跨項目計算相似性.主要做法是，通過挖掘出用戶在有限的評分數據上表現出來的項目偏好，利用貝葉斯概率將用戶對項目屬性的偏愛程度的差值作為項目的相似性度量，最后再利用推土機距離(EMD)代替常規距離實現跨項目的用戶相似度計算.緩解了推薦的數據稀疏以及冷啟動的問題，更好地支持了具有零或低同時出現的項目推薦.本文的工作也延伸了共現項目的內涵，拓展了共現項目的范圍.

本文第2節主要闡述協同過濾推薦算法的相關工作并系統總結了其優缺點；第3節主要介紹嵌入項目元數據的跨項目協同過濾推薦算法；第4節進行詳細的實驗對比與分析；第5節對研究工作進行了總結與歸納，同時提出了下一步要做的工作.

2 相關工作

為了提高系統推薦精度，國內外研究者展開了一系列的研究，提出了諸多改進的推薦算法.

Zhang等人[3]利用異構網絡嵌入和深度學習嵌入方法，從結構知識、文本知識和視覺知識在知識庫中自動提取語義表示.Rafailidis等人[4]提出了融合信任關系的協同過濾算法，該算法綜合考慮了用戶之間的相似關系與信任關系這2方面因素，確保了推薦結果不受惡意推薦的影響.Sar等人[5]提出一個在現有CF算法上(第一層)的兩層框架來最優化推薦給用戶的列表(第二層)，該方法考慮了列表內部項目的相互影響以及項目疲勞、趨勢、上下文信息等.郭磊等人[6]提出了一種結合推薦項目之間關聯關系的社會化推薦算法，重點研究具有關聯關系的推薦項目.Dong等人[7]研究的是異構社交網絡中的鏈路預測和推薦算法，提出了RFG模型，借助用戶間交朋友的同一性原理，將RFG模型與網絡結構信息相結合，從而向用戶推薦相關信息.高等人[8]通過將用戶在不同類型上下文中的認知水平、認知有用性、認知風險、有效認知行為等認知領域概念引入到偏好獲取過程中，顯著提高了偏好獲取的準確度.

一些推薦算法采用了不同的相似度度量方法來確定用戶之間的相似性[9，10].Vasile等人[11]使用產品嵌入，其將產品映射到一組潛在因素，并計算在該新表示上的相似性.Patra等人[12]提出利用Bhattacharrya相似性度量方法來尋找一對已經被評價過的項目之間的相似性.Li等人[13]考慮了用戶的偏好相似性，推薦的信任度以及社會關系來建立新的社會度量公式，以提高推薦精度.Zhang等人[14]考慮到用戶在項目類別上的偏好，計算每個項目上不同類別的排名分數來產生推薦.

但以上研究的用戶間相似性還是通過共同的評分數據來計算的.本文通過嵌入項目元數據，采用貝葉斯概率來計算項目特征的相似性，并結合EMD方法，將項目屬性信息融入到用戶的相似度計算中，這種方法改變了傳統方法中一對一(即只考慮用戶在相同項目上的評分)的相似度計算，實現多對多(即考慮用戶在不同項目上的評分)的相似度計算，在一定程度上緩解評分數據稀疏對用戶相似度計算的影響.該算法能有效解決目前傳統的相似性度量方法存在的問題和不足，提高推薦的準確性.

3 嵌入項目元數據的跨項目協同過濾推薦算法

3.1 傳統的相似性度量方法分析

隨著信息網絡的不斷普及，互聯網中推薦系統的規模逐漸擴大，用戶和商品的數量動輒千百萬計，且兩個用戶間的交叉極少.例如我們研究最平常的MovieLens數據集和Netflix數據集的稀疏度分別是4.5%和1.2%，然而其實這些都是極其密的數據了.下面我們將分析在數據稀疏的情況下，余弦相似性、Jaccard相似性、度量方法相似性還有相關相似性度量方法存在的問題.

這樣做雖然提高了計算性能，但是在數據稀疏的情況下，用戶只對一小部分數據有評分，而對未評分項目，用戶不一定不喜歡，對項目的評分也不一定為0.

在Jaccard相似性度量方法中，僅考慮了項目間的共同評分個數對相似度的影響，而沒有考慮項目間的評分差距.我們定義一個用戶集合U={uk|k∈M}和一個項目集合I={i|i∈N}，N表示項目ID集合，M表示用戶ID集合.如果有10個用戶對項目i，j共同評分，但每個用戶對項目i，j的評分值相差很大，那么這兩個項目并不能認為是相似的.只有當兩個評分比較接近時，我們才認為這兩個項目具有相似性.

在相關相似性度量方法中，根據計算經用戶u1與用戶u2評分的項目集合的交集來得到用戶之間的相似性.然而，用戶只有在比較多的項目上評分才比較相似.在用戶評分數據極端稀疏的情況下，通常只存在一兩個共同評分的項目集合.在這樣小的項目集合上計算的兩個用戶的相似性，存在很大的誤差.因此，相關相似性度量方法在用戶評分數據極端稀疏的情況下也存在一定的弊端.

3.2 嵌入項目元數據相似度計算

項目元數據是指描述項目的一些基本信息、元素，這里指屬性.推薦系統中所涉及到項目的屬性信息，比如電影評價網站會將電影分為愛情片、喜劇片、科幻片、驚悚片等，一個項目可能同時具有多個屬性.我們通過分析用戶對這些項目屬性的偏愛程度，能夠進一步提高推薦精度.我們將用戶的所有評分項目分為喜愛與不喜愛兩種，利用貝葉斯概率計算用戶喜愛的項目集合中出現某一特征的概率，以及用戶不喜愛的項目集合中出現這一特征的概率，以此來計算當項目i出現這一特征時，用戶喜愛項目i的概率，最后再將此概率用來計算項目i與項目j的相似度.

(1)

定義項目屬性集合A={ap|p∈L}，L表示屬性ID集合，ap為兩個用戶所喜歡項目的共同屬性.根據貝葉斯概率，則項目集合具有屬性ap時，用戶uk喜歡的概率為

(2)

由公式(1)可知，項目集合具有屬性ap時，用戶u1喜歡的概率為

定義D={di，j|i，j∈N}表示用戶u2在項目i上的偏好與用戶u2在項目j上的偏好之間的距離，那么用戶u1在項目i上的偏好與用戶u2在項目j上的偏好之間的距離為

(3)

那么最終基于項目的相似度為

Si，j=1-di，j

(4)

di，j越小，說明用戶u1對項目i的偏好與用戶u2對項目j的偏好程度越一致，即項目i與項目j對于用戶u1與用戶u2來說相似性就越高.為了更好的理解公式(2)與公式(3)，我們可以表示為用戶-項目-屬性三分圖，如圖1所示.

圖1 用戶-項目-屬性三分圖Fig.1 User-item-attribute tripartite graph

對任意的項目i，如果用戶對項目i沒有評分，我們使用如下方法預測用戶q對項目i的評分：

·利用公式(3)與公式(4)計算項目i與其他項目的相似性.

·將相似度最高的k個項目作為項目i的最近鄰居集合IiNB={inb1，inb2，…，inbk}，使得i?IiNB，并且相似性逐漸遞減.

·預測用戶q對項目i的評分：

(5)

這里的rq，j表示用戶q對項目i相似項目j的評分，Si，j表示項目i與項目j的相似性.

通過上述方法處理后，對于任意的項目i，用戶q對項目i的評分為

(6)

然后，我們利用嵌入項目元數據來計算用戶的相似性.

3.3 基于跨項目的用戶相似性計算

用戶的相似性計算，這里我們使用推土機距離(earth mover′s distance，簡稱EMD)方法，這種方法主要用來衡量簽名(分布、特征量集合)之間的不相似性[15]，和歐式距離一樣，它們都是一種距離量的定義，可以測量某兩個分布之間的距離.這里我們將EMD方法與推薦系統相結合，改變了傳統協同過濾推薦系統中只針對相同評分項目進行用戶相似度計算.傳統的協同過濾推薦的用戶相似度計算利用余弦、Pearson 等用戶相似度計算方法基于用戶在相同評分項目上的偏好進行計算，忽略了項目與項目之間的關聯.在數據極其稀疏的情況下，用戶很可能沒有共同評分項目，便很難計算出用戶之間的相似度.在本文中，我們根據計算出的相似項目，用戶在相似項目上的評分也能表現出用戶之間的相似性.

我們首先定義一個偏好流量F={fi，j}，其中fi，j表示用戶u1在項目i和用戶u2在項目j之間的偏好轉移量，這時候最小化總的轉移代價W：

W=∑i∈Iu1∑j∈Iu2fi，jdi，j→min

(7)

偏好轉移量必須滿足以下的線性約束：

fi，j≥0，i，j∈N

(8)

∑j∈Iu2fi，j≤ω(θu1，i)，i∈Iu1

(9)

∑i∈Iu1fi，j≤ω(θu2，j)，j∈Iu2

(10)

∑i∈Iu1∑j∈Iu2fi，j=min(wu1，wu2)

(11)

這里wu1、wu2分別表示用戶u1、u2對項目i、j的偏好總和，即wu1=∑i∈Iu1ω(θu1，i) ，wu2=∑j∈Iu2ω(θu2，j) ，其中ω(θu1，i)、ω(θu2，j)由公式(1)計算得到.Iu1、Iu2分別表示用戶u1、u2評分的項目集合.di，j表示為用戶u1在項目i上的偏好與用戶u2在項目j上的偏好之間的距離，由公式(3)計算得到.公式(8)表示用戶能夠選擇性的轉移偏好.公式(9)和公式(10)表示用戶u1(u2)在項目上i(j)能提供的偏好轉移總量不能超過用戶u1(u2)對項目上i(j)的偏好.公式(11)表示用戶u1與u2在所有項目上的偏好轉移總量.

(12)

如圖1中，用戶u1與用戶u2只有共同評分項目i2，使用余弦或者Person方法計算用戶相似度只能基于共同的評分項目i2上，并不能很好的反應用戶的偏好.而EMD方法具有跨項目特性，能夠利用項目元數據將共同項目外的其他評分項目融入到相似度計算中.

由EMD定義及公式(12)可知，用戶u1與用戶u2的相似度為

sim(u1，u2)=1-EMD(u1，u2)

(13)

3.4 產生推薦

傳統的基于用戶的協同過濾算法通常使用閾值或top-N等方法來選擇最相似的用戶作為最近鄰居集合.本文通過提出的嵌入項目元數據的跨項目相似性度量方法，得到待預測用戶的最近鄰居集合，然后對用戶產生相應的推薦列表.定義用戶u的最近鄰居集合為UuNB，則用戶u對項目i的預測評分Ru，i的計算方法如下：

(14)

3.5 算法描述

綜合3.1～3.4節中的計算步驟，可以得到嵌入項目元數據的跨項目協同過濾推薦算法如下：

輸入：用戶-項目的評分矩陣以及項目-屬性列表.

輸出：用戶的推薦項目列表.

Begin

1)Foreach∈I

2)CalculateSi，j

4)Endfor

5)Foreach∈U

6)Calculatesim(ua，uk)

7)Endfor

8)PredictRu，i

9)構造推薦列表，根據用戶對未評價項目的預測評分Ru，i，選擇預測值的前top-N項目推薦給用戶

End

3.6 算法復雜度分析

整個算法分為嵌入項目元數據相似度計算，基于跨項目的用戶相似性計算以及預測計算三個部分.假設用戶數目為M，項目集合數量為N.其中相似度計算的復雜度是O(MN)，預測部分的計算復雜度是O(MN).EMD距離計算復雜度主要表現在求解優化公式的Orlin算法上，算法復雜度為O(M3logM).在文獻[17]中，通過小波變換將EMD距離計算復雜度降為線性，可以通過得到近似EMD距離的值來進一步降低復雜度.

4 實驗結果及分析

4.1 數據集

本文的實驗數據采用了Movie Lens數據集[18].該數據集被廣泛應用于推薦系統的文獻，包括四個增加大小的數據集.實驗中選取了該數據集的約10萬條評分記錄，包括850個用戶關于1529部電影的打分記錄，大小為100k，稀疏度為93.7%.

為了驗證推薦算法的準確性，將實驗數據的評分矩陣進一步劃分為訓練集和測試集，訓練集數據用來學習或訓練推薦方法中的相關參數，測試集數據用來驗證推薦算法的準確性.為了保證實驗的準確性，我們采用交叉驗證(Cross-Validation)進行算法性能的評估.本文采用5折交叉驗證，取5次結果的均值作為算法的性能度量.

4.2 推薦質量的度量標準

本實驗采用平均絕對誤差MAE(Mean Absolute Error)作為度量標準.MAE衡量預測準確性的標準是計算預測評分與實際評分之間的偏差值.MAE越小，算法的推薦結果越準確.

現在給出如下定義：用戶預測評分集合為{p1，p2，…，pm}，用戶實際評分集合為{q1，q2，…，qm}，m表示預測的次數，則MAE的計算公式如下：

4.3 實驗結果與分析

本文設計了三組實驗，分別從與傳統相似度方法比較、基于相似項目的評分預測以及數據稀疏度比較這三個方面來探索CICF方法的推薦算法的性能.

實驗1.不同相似度算法的比較

該實驗主要比較本文提出的CICF方法與余弦、PMFUI[6]、BCF[12]方法的評分預測準確度.PMFUI方法重點關注推薦項目間的關聯關系，其認為用戶應該更關注具有關聯關系的推薦項目，提出利用此關系提高推薦效果.BCF是一個基于鄰居的協同過濾方法，主要利用Bhattacharrya相似性度量來發現一個積極用戶的鄰居.實驗結果如圖2所示.

圖2中，橫坐標表示不同數量的最近鄰居，分別取K=10，15，20，25，30，縱坐標表示MAE值.由圖可以看出，隨著最近鄰居數的增加，MAE值逐漸變小.與此同時，我們可以發現本文提出的CICF方法的MAE值明顯小于余弦、BCF和PM-FUI方法，這意味著CICF方法的推薦精度優于其它兩種方法.這是因為CICF方法在計算用戶相似度時充分考慮了項目之間的相似度，能夠通過項目屬性實現跨項目推薦，充分利用了共同評分項目以外的其它評分項目，可以更加準確的計算出用戶之間的相似度，從而提高了預測的準確度.

圖2 不同推薦算法計算的MAE比較Fig.2 MAE comparison of different recommendation algorithms

實驗2.基于相似項目的評分預測

該實驗將余弦、BCF、PMFUI方法使用本文提出的基于相似項目的評分預測公式與CICF方法做預測準確度比較.選擇相似項目時，我們將從鄰居用戶的評價項目中選擇與待預測項目的相似度不低于0.8的項目作為相似項目以確保相似項目與待預測項目的相關性.試驗結果如圖3所示.此外，為了驗證基于相似項目的評分預測公式與基于傳統的評分預測公式的準確度，我們取K=10做了圖4所示的對比.

圖3 不同相似度算法基于相似項目的MAE比較Fig.3 MAE comparison of different similarity algorithms based on similar items

圖4 兩種評分預測公式的對比Fig.4 Comparison of two different rating prediction

由圖3和圖4可以看出，不管是基于傳統的評分預測公式還是基于相似項目的評分預測公式，CICF方法總是優于余弦、BCF和PMFUI方法.與此同時，我們還可以發現，基于相似項目的評分預測要優于傳統的評分預測公式.這是因為基于相似項目的評分預測公式充分考慮了相似項目對評分預測的影響.當最近鄰居集合中沒有對待預測項目進行評分時，傳統的評分預測公式則認為該鄰居用戶對預測項目沒有影響，降低的預測的準確度.因此，基于相似項目的評分預測更有效.

實驗3.數據稀疏度對相似度算法的影響

該實驗主要通過改變訓練集與測試集數據占評分數據的比例，觀察在不同稀疏性情況下的推薦精度.該實驗分別選取20%、40%、60%以及80%的評分數據作為訓練集，相應的80%、60%、40%以及20%的評分數據作為測試集，最近鄰居數取K=10.實驗結果如圖5所示.

圖5 不同稀疏性比較Fig.5 Comparison of different sparseness

圖5中，橫坐標表示為訓練數據所占的百分比，及不同稀疏度的數據集，縱坐標表示MAE值.由圖可知，當訓練數據集所占比例不斷提高，這幾種算法的推薦效果也在不斷變好.圖中PMFUI方法的效果要比余弦方法好，而CICF方法比余弦和PMFUI方法更準確.并且在評分預測公式中，使用基于相似項目的各個算法要比只使用傳統的評分預測公式更加準確.另外，在評分數據稀疏的情況下，基于相似項目的評分預測方法更加有效，并且CICF方法能夠達到較好的評分預測精度.這是因為，在評分數據稀疏的情況下，用戶之間的共同評分項目減小，CICF方法在計算用戶相似度時充分考慮了項目之間的相似度，能夠通過項目屬性實現跨項目推薦，充分利用了共同評分項目以外的其它評分項目，可以更加準確的計算出用戶之間的相似度，從而提高了預測的準確度.

5 總 結

本文提出了一種嵌入項目元數據的跨項目協同過濾推薦算法.這是對傳統的協同過濾推薦算法中只能根據用戶在相同項目上的評分來進行推薦的改進.本文通過嵌入項目元數據，首先挖掘出用戶在有限的評分數據上表現出來的項目偏好，利用貝葉斯概率將用戶對項目屬性的偏愛程度的差值作為項目的相似性度量，最后再利用推土機距離代替常規距離實現跨項目的用戶相似度計算.在進行評分預測時，將相似項目融入到評分預測公式中，能更有效的提高預測精度.一系列的實驗證明，本文提出的算法與其它算法相比能進一步提高推薦效果.在未來的工作中，我們將進一步對算法優化改進，考慮如何將文本內容與視覺內容融合到本文提出的算法中，以便進一步改善推薦的效果.

[1] Wang L，Meng X，Zhang Y.A heuristic approach to social network-based and context-aware mobile services recommendation[J].Journal of Convergence Information Technology，2011，6(10)：339-346.

[2] Abbas A，Zhang L，Khan S U.A survey on context-aware recommender systems based on computational intelligence techniques[J].Computing，2015，97(7)：1-24.

[3] Zhang F，Yuan N J，Lian D，et al.Collaborative knowledge base embedding for recommender systems[C].ACM SIGKDD International Conference,ACM，2016：353-362.

[4] Rafailidis D，Crestani F.Collaborative ranking with social relationships for Top-N recommendations[C].ACM SIGIR Conference on Research and Development in Information Retrieval,ACM，2016：785-788.

[5] Sar Shalom O，Koenigstein N，Paquet U，et al.Beyond collaborative filtering： the list recommendation problem[C].International Conference on World Wide Web.International World Wide Web Conferences Steering Committee，2016：63-72.

[6] Guo Lei，Ma Jun，Chen Zhu-min，et al.Incorporating item relations for social recommendation[J].Chinese Journal of Computers，2014，37(1)：219-228.

[7] Dong Y X，Tang J，Wu S，et al.Link prediction and recommendation across heterogeneous social networks[C].Proceedings of the ICMD.Washington： IEEE Computer Society，2012：181-190.

[8] Gao Quan-li，Gao Ling，Yang Jian-feng，et al.A preference elicitation method based on Users′ cognitive behavior for context-aware recommender system[J].Chinese Journal of Computers，2015，38(9)：1767-1776.

[9] Bobadilla J，Ortega F，Hernando A.A collaborative filtering similarity measure based on singularities[J].Information Processing & Management，2012，48(2)：204-217.

[10] Hu Y C.Recommendation using neighborhood methods with preference-relation-based similarity[J].Information Sciences，2014，284(6)：18-30.

[11] Vasile F，Smirnova E，Conneau A.Meta-Prod2Vec：product embed

dings using side-information for recommendation[C].ACM Conference on Recommender Systems，ACM，2016：225-232.

[12] Patra B K，Launonen R，Ollikainen V，et al.A new similarity measure using Bhattacharyya coefficient for collaborative filtering in sparse data[J].Knowledge-Based Systems，2015，82(2)：163-177.

[13] Li Y M，Wu C T，Lai C Y.A social recommender mechanism for e-commerce： Combining similarity，trust，and relationship[J].Decision Support Systems，2013，55(3)：740-752.

[14] Zhang L，Xu J，Li C.A random-walk based recommendation algorithm considering item categories[J].Neurocomputing，2013，120(10)：391-396.

[15] Pele O，Werman M.Fast and robust earth Mover′s distances[C].In：Proc.of the Int′l Conf.on Computer Vision,Piscataway： IEEE Computer Society，2009：460-467.

[16] Korte B H，Vygen J.Combinatorial optimization： theory and algorithms[M].Springer Publishing Company，2007.

[17] Applegate D，Dasu T，Krishnan S，et al.Unsupervised clustering of multidimensional distributions using earth mover distance[C].ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，San Diego，Ca，Usa，August.DBLP，2011：636-644.

[18] Harper F M，Konstan J A.The movie lens datasets： history and context[M].ACM，2015.

附中文參考文獻：

[6] 郭 磊，馬 軍，陳竹敏，等.一種結合推薦對象間關聯關系的社會化推薦算法[J].計算機學報，2014，37(1)：219-228.

[8] 高全力，高 嶺，楊建鋒，等.上下文感知推薦系統中基于用戶認知行為的偏好獲取方法[J].計算機學報，2015，38(9)：1767-1776.