一種結合用戶和項目聚類的協同過濾算法

羅 弦，丁 箐，王 禹

(中國科學技術大學 軟件學院，安徽省合肥市 235000)

0 引言

推薦系統是解決“信息超載”現象的最有力的措施[1]。在推薦系統中，系統的推薦策略和工作方式是核心組成部分，它是由推薦算法決定的，因此關于推薦算法的研究成為該領域的焦點。根據使用的數據源和領域知識不同，推薦算法分為基于內容的(Content-Based)、基于人口統計學的(Demographic-Based)、協同過濾(Collaborative Filtering，CF)以及其他推薦方法。

目前研究最深且應用最廣的推薦算法是協同過濾算法[2]，其原理依據是“人以群分，物以類聚”。本文研究的是基于內存(Memory-Based)的CF，它無需預先訓練模型，是一種啟發式的算法。它利用用戶和項目的鄰居信息計算相似度并預測目標用戶對項目的評分[3]，從而獲得推薦。

基于用戶的推薦[4]和基于項目的推薦[5]是CF的兩大思路。基于用戶的CF依據其他相似用戶的評分為目標用戶產生推薦，隨著用戶數量增大，評分矩陣稀疏和算法復雜度增高是顯而易見的問題，且推薦結果的可解釋較差。基于項目的CF根據項目之間的相似度來計算預測值，它存在可拓展性差、忽略項目屬性等問題。鑒于二者存在的諸如數據稀疏性[6]、冷啟動(實際上是數據稀疏的極端表現)[7]、可拓展性[8]等問題，多位研究者提出包括BP神經網絡、Naive Bayesian分類方法、基于內容預測的矩陣填充和矩陣降維等方法。同時為了提高協同過濾推薦速度及實時性，多位研究者提出包括K-Means聚類算法、Gibbs Sampling方法等方法。經典的相似度度量方法對數據稀疏性的表現較差，有研究者提出改進的相似度度量策略，比如定義社交網絡中用戶屬性相似和互動相似度，并將兩部分線性擬合重新構造總體的相似度。

本文基于上述研究背景，在傳統的協同過濾基礎上，結合用戶聚類和項目聚類，重新構成相似度的度量方法和預測評分的計算方式，提出一種改進的協同過濾算法。

1 傳統的協同過濾算法

1.1 問題描述

為簡化問題，僅就基于用戶的CF來繼續以下的討論。基于項目的CF在原理上與之十分類似，不再贅述。

1.2 最近鄰查詢

最近鄰集合的查詢是CF最重要的步驟，相似度的計算方式直接影響最近鄰選取的效果和效率。要計算用戶對之間的相似度大小，首先得到該用戶對共同評價過的所有項目集合，然后根據選取的相似度度量方法計算二者之間的相似度。常用的相似度度量方法有Jaccard系數、Minkowski距離、Cosine相似度、Pearson相關系數[9]等。其中Pearson相關系數對數據作了歸一化處理，在實際應用的大多數時候有著更好的表現。用Iij表示i用戶和j用戶共同評價的所有項目集合，x是屬于該集合的一個項目，Sim(i，j)為這兩個用戶之間的Pearson相關系數，公式如下所示：

(1)

最近鄰查詢是利用用戶對項目的評分信息，計算出需要推薦服務的用戶u和別的用戶的相似度Sim(u，Ni)，最后得到與u相似度最高的若干用戶形成最近鄰集合N(u)。最近鄰居集合N(u)的選取是下一步預測評分并產生推薦的重要前提，具體方法有閾值法、Top-N法等。

1.3 產生推薦

得到最近鄰集合N(u)后，下一步就是計算預測的評分結果，并排序產生推薦列表。通過以下公式來計算出用戶u對項目i的預測的評分Pu,i：

(2)

在得到用戶對未知項目的預測評分之后進行排序，選取由高到低序數靠前的若干個項目作為推薦內容呈現給目標用戶。

2 改進的協同過濾算法

2.1 針對相似度的優化

一首流行歌曲，幾乎人人都聽過，并且通常做出非個性化的評價。“哈利波特”問題闡明了熱門項目對相似度的貢獻較小。針對于此，相關文獻[10]提出對Pearson相關系數作以下修正:

(3)

其中N(c)表示項目c在用戶-項目評分矩陣中被評價的總次數。在實際應用中發現單純憑借Pearson相關系數并不可以解決數據稀疏帶來的一些問題，比如用戶之間相關聯的項目數量過少(共同評價項目過少)。為了降低這一現象帶來的影響，相關文獻[11]引入顯著性加權因子α，即共同評價的物品數量占各自全部評價數量的比重：

(4)

其中Iu表示用戶u評分的全部項目，Iv表示用戶v評分的全部項目，Iu,v表示用戶u和用戶v共同評分的全部項目。從公式中可以清晰地看出用戶間的相似度隨著共同評價物品數量減少而減少。本文將用戶間相似度的計算方法改進為：

Sim′(u,v)=α×Sim(u,v)

(5)

2.2 結合用戶聚類和項目聚類的協同過濾

如果用戶集合大小為M，項目集合大小為N，傳統的協同過濾算法的時間復雜度為O(N*M*M)[12]，伴隨項目規模和用戶規模的激增，計算開銷也隨之增高。為了改善算法的性能，提高系統的可拓展性，利用聚類對數據進行預處理是經常采用的策略。

將基于k均值的聚類算法[13]應用到協同過濾中算法中。首先對用戶-項目評分矩陣進行聚類分析，距離函數采用余弦相似性，將用戶集合劃分為p個簇，將項目集合劃分為q個簇。又將目標用戶劃分到與其聚類質心最近的一個簇，然后在該簇中進行最近鄰查詢并預測評分。前文已經提到基于用戶的CF和基于項目的CF各有各自的片面性和局限性，在預測未評分的時候如果只是基于用戶的預測方法或者基于項目的預測方法，都將會忽略其他有用的信息，所以采用以下公式對二者進行聚類分析后的結合：

Pu,i=mPu(u,i)+nPi(u,i)

(6)

(7)

(8)

從公式(7)和(8)中注意到m+n=1。也就是說，在改進的算法中，用戶維度和項目維度的預測評分的貢獻度是由目標用戶和項目與各自的聚類質心的余弦相似性得到的。

2.3 改進后算法的描述

首先使用k均值聚類算法，距離函數采用余弦相似性，對用戶和項目進行兩個維度的聚類分析。這一步驟可以離線進行，對于用戶數量和項目數量變化穩定的系統大大降低了計算復雜度、節省了時間。

然后針對目標用戶和項目劃分到距離聚類質心最近的簇。其中計算Pu(u,i)采用針對流行項目、共同評分過少而優化的相似度計算方法計算相似度，在簇類選取top-K個最近鄰；計算Pi(u,i)則使用傳統的Pearson相關系數在項目所屬簇類中取top-K個最近鄰。

最后使用公式(7)和公式(8)對二者按照參數m和n進行配比，產生最終預測評分Pu,i，選取評分最高的若干項產生推薦。具體的流程圖如圖1所示。

圖1 改進后算法的流程示意

3 實驗

3.1 數據集

為評估改進后的協同過濾算法實驗效果，本文使用MovieLens數據集中的第二個版本中的數據(ml-1M)，包括了6 040個用戶對3 900部電影的1 000 209個評分記錄。其中評分在1～5分之間。對其中部分數據進行預處理后的評分密度為8.2%，稀疏度為91.8%，可以看出評分矩陣相當稀疏。

3.2 實驗度量標準

評分預測系統一般采用平均絕對誤差MAE[14]或是均方根誤差RMSE來評估算法的預測準確度。本文選擇MAE作為評估改進后算法的推薦精度的衡量指標。公式如下：

(9)

3.3 實驗方案和結果

本文通過三個實驗方案驗證改進后的結合用戶聚類和項目聚類的協同過濾算法的可行性。

實驗一：固定用戶聚類數目p=10，不同項目聚類數目q下的MAE的變化值。q從4到20，步長為4。為控制變量，將用戶和項目最近鄰查詢步驟中的k都設為20。實驗結果如圖2所示。

圖2 實驗一的實驗結果折線圖

實驗二：固定項目聚類數目q=10，不同用戶聚類數目p下的MAE的變化值。p從4到20，步長為4。為控制變量，將用戶和項目最近鄰查詢步驟中的k都設為20。實驗結果如圖3所示。

圖3 實驗二的實驗結果折線圖

實驗一和二說明聚類數目會影響預測評分的準確性。聚類數目過大時，相似對象之間的相似成分所致的影響降低，簇信息過于個性化；聚類數目過小時，不相似對象之間的相似成分所致的影響降低，簇信息過于大眾化。取適中的聚類數目才會有較好的預測準確度。

實驗三：固定用戶聚類數目p=10和項目聚類數目q=10，不同最近鄰k的選擇下傳統協同過濾和本文提出的算法的MAE值比較。實驗結果如圖4所示。

圖4 實驗三的實驗結果對比折線圖

由實驗三可見采用改進后的基于聚類的協同過濾算法對比傳統的協同過濾算法有著較高的預測準確度。

4 結束語

本文首先討論了協同過濾的算法在實踐過程中遇到的問題，面對諸如數據稀疏性和可拓展性等情況，傳統的協同過濾算法并沒有展示出上佳的表現。針對于此提出一種改良的協同過濾算法。新算法在相似度計算和預測評分計算上利用了聚類分析結果，結合用戶聚類和項目聚類減小了最近鄰查詢空間，降低用戶相似度和項目相似度單方面造成的誤差。并通過實驗，在MovieLens數據集上驗證該算法相較于傳統的協同過濾算法在預測準確度上的優越性。

雖然本文對傳統協同過濾算法進行了一定程度的改良和優化，但是仍然存在一些亟待解決的問題，比如數據來源單一化，本文僅涉及用戶評分和物品屬性信息，像用戶人口統計學信息、社交網絡信息、隱性和顯性的知識等，均可以加入算法中；由于時間和實驗條件的限制，本文僅僅采用單一的離線的數據集進行離線預測，讀者可以利用其他數據集驗證本算法的魯棒性，并且具體的評價指標也不單是預測準確度中的MAE，還有驚喜度、信任度、多樣性、滿意度等評價準則都未進行針對性評測；本文是基于內存的算法，利用用戶和物品的最近鄰信息獲得推薦，還有一類基于模型的算法，這一類算法可以使用機器學習中的分類、聚類、半監督學習、神經網絡等方法利用已有的信息訓練出一個預測模型，然后調整參數至收斂。使用預測模型獲得推薦結果也有很大的研究空間。