基于多維度上下文和雙聚類的個性化推薦算法

李彤巖 蒲江嵐

(成都信息工程大學通信工程學院 四川 成都 610225)

0 引 言

隨著互聯網技術的迅猛發展以及萬維網無障礙的持續性發展，人類產生的數字信息量呈指數增長，人們很難在大量信息中找到真正想要的東西[1]。推薦系統(Recommended System，RS)作為一種信息過濾工具應運而生。RS幫助用戶從不斷增加的在線信息列表中找到所需的服務，其在緩解信息過載問題方面的有效性已被證實，并被應用于互聯網中的許多領域，例如電影、音樂和旅游，用于向用戶推薦合適的產品[2-3]。

RS采用各種過濾方法來提取有意義的信息，如基于內容的過濾(Content-Based filtering，CB)、協同過濾(Collaborative Filtering，CF)和混合過濾(Hybrid Filtration，HF)[4]。其中協同過濾的方法取得了巨大成功，成為個性化推薦系統中的最有前途的核心技術[5]。但是當可用的協作信息(如項目的歷史評分)很少時，基于CF的推薦系統表現不佳，這稱為數據稀疏問題，是許多新推出的推薦系統中最常見和最具挑戰性的問題之一[6]。為了有效地緩解數據稀疏問題，需要利用有限的用戶信息資源，多角度、多維度地進行分析計算和推薦。

CF的缺點之一在于其通常只考慮用戶和項目兩個維度中的一個，其推薦結果往往因為缺乏關聯度而導致精確度下降。用戶和項目這兩個維度是有所關聯的，因此產生了同時利用用戶和項目兩個維度來優化推薦結果的雙聚類(Bi-clustering)的推薦算法[7-9]。研究表明，使用雙聚類技術不僅可以減少利用空間，還能夠有效地處理冷啟動問題并提高推薦質量[8]。

用戶的決策也可能會受到場景或語境的影響，例如：當人們旅行時，某些活動項目在很大程度上取決于當地的天氣，而現有的CF系統通常無法模擬這種復雜的關系，也很難挖掘和利用其中的關聯，所以無論是下雨還是晴天，系統都會將山地路線推薦給喜歡徒步旅行的人，從而產生推薦信息與用戶決策之間的偏差。解決該問題的主要途徑是在CF系統中對場景或語境建模，將用戶的選擇或偏好需要與用戶做出該選擇的上下文相關聯。這意味著系統需要捕獲用戶點擊或購買項目的當前上下文，例如用戶做出選擇的時間、地點等。因為推薦的質量常常隨推薦調用的時間和位置不同而變化，所以時間感知CF[10]和位置感知CF[11]被提出，以提高推薦的準確性。然而，上述方法只能為對象提供客觀的推薦服務，沒有考慮用戶的主觀偏好。針對這一不足，本文研究并提出了一種基于多維度上下文和雙聚類的個性化推薦算法(MCB)，以滿足不同用戶對個性化推薦服務的需求。

1 MCB推薦算法

推薦算法的目標是根據目標用戶興趣相似的其他用戶的信息，做出關于該用戶所偏好的個性化預測。為了向一組用戶提出有成效和高效率的建議，需要解決兩個關鍵問題：(1) 應以非正式和準確的方式表達一個群體的偏好，所提取的偏好表示用戶“興趣”，并且確定哪些項目具有群體成員所接受的高概率。(2) 如何集成多個中間推薦列表以生成的最終結果。中間的推薦列表是針對不同的源生成的，例如不同群體的用戶和上下文信息[3]。

1.1 MCB推薦框架

MCB算法的主要流程如圖1所示，包括四個階段。

圖1 MCB算法流程

1) 建立用戶評分矩陣。與傳統的評分矩陣建立方法不同，MCB算法不僅需要收集用戶評分信息，還要收集其行為的上下文背景，以不同的上下文背景修正歷史評分，建立一個基于多維度上下文的用戶評分矩陣。

2) 雙聚類。采用K-means聚類算法，分別對用戶和項目進行聚類。

3) 評分預測。利用用戶聚類找到鄰居后，選擇在目標用戶的K個最近鄰中搜索該用戶可能感興趣的項目，然后根據用戶間的相似度計算項目的預測評分，再對項目的預測評分進行排序，選擇Top-N個項目作為預推薦項目。

4) 產生推薦。最后將項目聚類集合與預推薦項目集合綜合，生成最終的推薦列表為用戶進行推薦。

1.2 評分矩陣

用戶的評分數據是基于CF的推薦系統的基礎資源，這意味著用戶的參與對于推薦的成功至關重要。但實際上，可供推薦的總項目數比用戶所經歷的項目數要大得多，因此評分矩陣是稀疏的。針對這一問題，本文采用多維度上下文的算法[12]對原始評分進行修飾。

假設系統有d個上下文維度C={C1,C2,…,Cd},上下文維度之間的相似度計算式為：

(1)

由于上下文的影響，用戶的評分記錄源自不同的上下文環境，可能和目標用戶當前的背景存在差異，所以不同上下文背景下的評分記錄與當前上下文下的用戶相關程度不同。為了更好地表達用戶在當前上下文下對項目的喜好，可以利用上下文維度之間的相似度來修正原始的評分數據，得到在上下文c下用戶u對項目i的評分：

(2)

式中：c是目標用戶所處的上下文；x是某評分記錄所處的上下文；simt(c,x,i)表示項目i上下文c和x在t維度下相似度；ru,i,x是用戶u在上下文條件x下對項目i的評分；k是歸一化權重因子。

通過上下文的修飾計算后，建立評分矩陣：

(3)

式中：m是推薦系統中的用戶總數；n是系統中的項目總數；ru,i,c是用戶u在上下文c下對項目i的評分。

1.3 雙聚類

尋找最為相似的鄰居是CF的關鍵，有幾種相似度量方法(余弦相似度、Pearson相關系數等)成功地解決了這一問題，但大多數相似性度量方法在尋找相似用戶時往往沒有考慮到用戶偏好的變化結果，計算出的鄰居集合在任何給定時間點不能總是反映最優鄰域。無監督學習的聚類方法給尋找最優鄰域帶來了希望。本文采用K-means聚類算法，分別對用戶和項目進行雙聚類，如圖2所示。雙聚類算法如算法1所示。

圖2 雙聚類示意圖

算法1雙聚類算法

輸入：用戶評分樣本集U={x1,x2,…,xm}；項目評分樣本集I={y1,y2,…,ym}；簇數k。

輸出：用戶聚類集合Uc={Uc1,Uc2,…,Uck}，項目聚類集合Ic={Ic1,Ic2,…,Ick}。

1. 隨機初始化U的k個質心向量{u1,u2,…,uk},I的k個質心向量{i1,i2,…,ik}；

//用戶聚類

2. Repeat

3. For eachxi∈U

4. 計算xi與各個質心uj(j=1,2,…,k)的歐氏距離，將xi劃分到距離最近的質心un中，更新對應的簇Ucn；

5. End for

6. For eachUcj∈Uc

8. End for

9. Until聚類簇中元素不再分離或者達到設定的迭代次數

//項目聚類

10. Repeat

11. For eachyi∈I

12. 計算yi與各個質心ij(j=1,2,…,k)的歐氏距離，將yi劃分到距離最近的質心in中，更新對應的簇Icn；

13. End for

14. For eachIcj∈Ic

16. End for

17. Until聚類簇中元素不再分離或者達到設定的迭代次數

1.4 多維度的個性化評分預測(MPRP)

傳統的項目評分預測算法以目標用戶的平均項目歷史評分為參考中心，再利用與相似鄰居間的相似度和相似鄰居的評分計算得出項目評分預測。當用戶數據稀疏的情況下，如用戶對許多項目都未做出評分，傳統的項目評分預測算法的預測結果誤差增大，精確率降低。本文以多維度上下文為基礎，增加考慮用戶評分的權重問題，并引入基于統計學習的系統誤差因子，提出了一種多維度的個性化評分預測算法(MPRP)。

MPRP算法用式(4)來計算用戶u對項目i預測的評分pu,i，引入用戶評分的權重因子a，并為項目的評分分配(1-a)的權重。

(4)

(5)

式中：ru,i表示用戶u對項目i的實際評分；pu,i表示系統產生的用戶u對項目i的預測評分；NI(u)表示目標用戶u采納推薦結果的項目集合I(u)的項目個數。

系統針對目標用戶生成一個用戶可能感興趣的項目評分預測列表，在對目標用戶推薦時對得到的項目評分預測列表中的項目評分進行排序，選取N個預測評分最高的項目為目標用戶u進行推薦。

2 實 驗

2.1 實驗數據集及環境

CARSKit(https://github.com/irecsys/CARSKit/)，是一個基于Java的開源上下文感知推薦引擎。實驗采用其中的DePaulMovie數據集，該數據集包含了97位用戶對79部電影的5 043條評分數據，評分等級為1到5，數據集的稀疏度約為1×5 043/(97×79)=34.2%。將數據集隨機分為訓練集和測試集兩個部分，其中：70%的評分數據作為用戶的歷史評分數據，即作為訓練集；另外30%的評分數據作為用戶在后期的評分數據，即作為測試集。該數據集共涉及如下三個上下文維度：① 時間：Weekday、Weekend；② 位置：Cinema、Home；③ 同伴：Alone、Family、Partner。

實驗采用的計算機為Windows 10 64位操作系統，內存8.00 GB，Intel?CoreTMi5-4200U CPU @1.60 GHz 2.30 GHz，集成開發環境為JetBrains PyCharm Professional 2018.2.5，開發語言主要是Python。

2.2 評價指標

1) 預測準確度。推薦的預測準確度用平均絕對誤差(MAE)和均方根誤差(RMSE)來衡量，計算方式如下：

(6)

(7)

式中：pi是系統對項目i的預測評分；ri是項目i的真實評分；m是觀測次數。

MAE和RMSE值越小，說明算法的推薦準確度越高。

2) 覆蓋率。覆蓋率(Coverage)描述一個推薦系統對物品長尾的發掘能力，計算方式如下：

(8)

式中：n是系統所有的項目數目；U是所有接受系統推薦的用戶；R(u)表示所有被推薦給用戶的商品。

覆蓋率越高，說明系統對物品長尾的發掘能力越強。

3) 新穎性。評估新穎性最簡單的方法是計算推薦列表中物品的平均流行度(Popularity)：

(9)

式中：I是產生的推薦列表；p(i)是項目i獲得評分的數目；log[1+p(i)]則表示項目i的流行度；N是系統推薦的總項目數。

平均流行度越小，說明系統的推薦結果越新穎。

2.3 算法參數實驗

為了研究MCB算法中參數對推薦性能的影響，設置兩組預處理實驗，分別測試用戶評分權重因子a和K-means聚類的簇的數目k對推薦性能的影響。

參數a的性能測試結果如圖3所示。當a取0.7和0.8時，MAE和RMSE較小，推薦結果較為準確；當a取1和0.9時，Coverage較大，系統挖掘長尾物的能力更強；當a取1和0.9時，Popularity較小，推薦的新穎度更高。

(a)

(b)

(c)

(d)圖3 不同a值下的推薦性能比較

參數k的性能測試結果如圖4所示。當k取6時，MAE和RMSE較小；而k在不同的最近鄰數K下呈現出了不同的推薦覆蓋效果，當K為4和12時，k取6的Coverage較高，當K為6、8、10時，k取8的Coverage較高；對于Popularity而言，k的取值對其并無顯著影響。

(a)

(b)

(c)

(d)圖4 不同k值下的推薦性能比較

2.4 對比實驗

為了驗證多維度上下文、用戶評分權重等因素對推薦結果的影響，驗證本文提出的MCB算法的推薦效果，與MFUC[5]、UICF[7]、CCF[12]三種算法進行對比實驗。為了保證實驗的客觀可比性，項目推薦數目N定為20，即為每位目標用戶推薦20個項目。為每位目標用戶選擇的最為相似的鄰居數目K為變量，K∈{4,6,8,10,12}。為了讓MCB算法性能最優，結合算法參數實驗，將用戶評分權重因子a設置為0.8，K-means聚類算法簇的數目k定為6。實驗結果如圖5所示。

(a)

(b)

(c)

(d)圖5 不同K值下四種算法推薦性能比較

可以看出，隨著K值的增大，推薦算法產生的誤差會降低，推薦準確性提高，但同時推薦結果的覆蓋率也會有所降低。而K的取值對推薦的新穎性影響很小，這說明如果要求更加新穎的推薦服務，則需要選擇推薦流行度較低的推薦算法，如MCB和MFUC[5]。從總體性能上來說，MCB優于另外三種算法，CCF[12]則最差。

此外，結合參數實驗，可以看出選擇正確的參數也是提高推薦準確性的關鍵。對于目標用戶的鄰居數目K、用戶評分權重因子a等參數，在實際應用時，需要推薦系統在測試階段進行對比選擇合適的值。

3 結 語

本文探索了協同過濾、雙聚類、多維度上下文等有關推薦系統的一些算法，研究并提出了一種基于多維度上下文和雙聚類的個性化推薦算法(MCB)。MCB利用評分和上下文信息來提取用戶的偏好，采用雙聚類算法表達群體的偏好，有效地解決了數據稀疏問題，最后用一種多維度的個性化評分預測(MPRP)算法來生成推薦列表，提高了推薦的準確性。與傳統的算法相比，MCB不僅預測更加準確，而且挖掘長尾物品的能力更強，推薦結果更加新穎。