一種結(jié)合用戶和項目聚類的協(xié)同過濾算法

羅 弦，丁 箐，王 禹

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

0 引言

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

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

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

本文基于上述研究背景，在傳統(tǒng)的協(xié)同過濾基礎(chǔ)上，結(jié)合用戶聚類和項目聚類，重新構(gòu)成相似度的度量方法和預(yù)測評分的計算方式，提出一種改進的協(xié)同過濾算法。

1 傳統(tǒng)的協(xié)同過濾算法

1.1 問題描述

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

1.2 最近鄰查詢

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

(1)

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

1.3 產(chǎn)生推薦

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

(2)

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

2 改進的協(xié)同過濾算法

2.1 針對相似度的優(yōu)化

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

(3)

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

(4)

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

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

(5)

2.2 結(jié)合用戶聚類和項目聚類的協(xié)同過濾

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

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

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

(6)

(7)

(8)

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

2.3 改進后算法的描述

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

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

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

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

3 實驗

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

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

3.2 實驗度量標準

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

(9)

3.3 實驗方案和結(jié)果

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

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

圖2 實驗一的實驗結(jié)果折線圖

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

圖3 實驗二的實驗結(jié)果折線圖

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

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

圖4 實驗三的實驗結(jié)果對比折線圖

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

4 結(jié)束語

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

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