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

李彤巖 蒲江嵐

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

0 引 言

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

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

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

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

1 MCB推薦算法

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

1.1 MCB推薦框架

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

圖1 MCB算法流程

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

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

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

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

1.2 評分矩陣

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

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

(1)

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

(2)

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

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

(3)

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

1.3 雙聚類

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

圖2 雙聚類示意圖

算法1雙聚類算法

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

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

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

//用戶聚類

2. Repeat

3. For eachxi∈U

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

5. End for

6. For eachUcj∈Uc

8. End for

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

//項目聚類

10. Repeat

11. For eachyi∈I

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

13. End for

14. For eachIcj∈Ic

16. End for

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

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

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

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

(4)

(5)

式中：ru,i表示用戶u對項目i的實際評分；pu,i表示系統(tǒng)產(chǎn)生的用戶u對項目i的預(yù)測評分；NI(u)表示目標用戶u采納推薦結(jié)果的項目集合I(u)的項目個數(shù)。

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

2 實 驗

2.1 實驗數(shù)據(jù)集及環(huán)境

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

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

2.2 評價指標

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

(6)

(7)

式中：pi是系統(tǒng)對項目i的預(yù)測評分；ri是項目i的真實評分；m是觀測次數(shù)。

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

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

(8)

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

覆蓋率越高，說明系統(tǒng)對物品長尾的發(fā)掘能力越強。

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

(9)

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

平均流行度越小，說明系統(tǒng)的推薦結(jié)果越新穎。

2.3 算法參數(shù)實驗

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

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

(a)

(b)

(c)

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

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

(a)

(b)

(c)

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

2.4 對比實驗

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

(a)

(b)

(c)

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

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

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

3 結(jié) 語

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