羅 弦，丁 箐，王 禹

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

0 引言

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

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

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

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

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

1.1 問題描述

為簡(jiǎn)化問題，僅就基于用戶的CF來繼續(xù)以下的討論?；陧?xiàng)目的CF在原理上與之十分類似，不再贅述。

1.2 最近鄰查詢

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

(1)

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

1.3 產(chǎn)生推薦

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

(2)

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

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

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

一首流行歌曲，幾乎人人都聽過，并且通常做出非個(gè)性化的評(píng)價(jià)?！肮ㄌ亍眴栴}闡明了熱門項(xiàng)目對(duì)相似度的貢獻(xiàn)較小。針對(duì)于此，相關(guān)文獻(xiàn)[10]提出對(duì)Pearson相關(guān)系數(shù)作以下修正:

(3)

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

(4)

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

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

(5)

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

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

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

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

(6)

(7)

(8)

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

2.3 改進(jìn)后算法的描述

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

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

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

圖1 改進(jìn)后算法的流程示意

3 實(shí)驗(yàn)

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

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

3.2 實(shí)驗(yàn)度量標(biāo)準(zhǔn)

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

(9)

3.3 實(shí)驗(yàn)方案和結(jié)果

本文通過三個(gè)實(shí)驗(yàn)方案驗(yàn)證改進(jìn)后的結(jié)合用戶聚類和項(xiàng)目聚類的協(xié)同過濾算法的可行性。

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

圖2 實(shí)驗(yàn)一的實(shí)驗(yàn)結(jié)果折線圖

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

圖3 實(shí)驗(yàn)二的實(shí)驗(yàn)結(jié)果折線圖

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

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

圖4 實(shí)驗(yàn)三的實(shí)驗(yàn)結(jié)果對(duì)比折線圖

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

4 結(jié)束語

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

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