CICF：一種基于上下文信息的協(xié)同過濾推薦算法

魯凱，張冠元，王斌

（中國科學(xué)院計(jì)算技術(shù)研究所，北京100190）

1 引言

近些年來，隨著互聯(lián)網(wǎng)的快速發(fā)展，互聯(lián)網(wǎng)上的信息量越來越大，使得用戶面臨著嚴(yán)重的信息過載（Information Overload）問題。推薦系統(tǒng)通過在用戶和信息之間建立聯(lián)系，過濾掉大量無關(guān)的信息，然后將有用的信息提供給用戶，是解決信息過載問題的有效手段。

推薦系統(tǒng)的研究產(chǎn)生于20世紀(jì)90年代，隨著互聯(lián)網(wǎng)中信息量的迅猛增長，推薦系統(tǒng)的研究得到了快速的發(fā)展，并且很多技術(shù)已經(jīng)應(yīng)用在實(shí)際系統(tǒng)中。例如，在電子商務(wù)中，Amazon，eBay等都部署了商品推薦并取得了巨大的成功；Netflix，Youtube等推出了電影及視頻推薦；Yahoo！Music，Pandora及Last.fm等也提供了音樂推薦引擎。推薦系統(tǒng)使得互聯(lián)網(wǎng)發(fā)生非常顯著的變化。一方面，提高了用戶的做事效率。通過給用戶推薦其喜歡的物品（item），大大縮短用戶的選擇時間，提高了用戶體驗(yàn)；另一方面，推薦系統(tǒng)可以直接給服務(wù)提供商帶來實(shí)際的經(jīng)濟(jì)效益。因此推薦系統(tǒng)的研究是一件非常有意義的事情。

在推薦系統(tǒng)中，基于協(xié)同過濾（CF）的推薦技術(shù)可以滿足用戶的個性化需求，為用戶提供更加精確的推薦，因此受到更多的關(guān)注?；趨f(xié)同過濾的算法主要是對用戶和物品之間的交互數(shù)據(jù)進(jìn)行建模，然而目前大多數(shù)推薦系統(tǒng)所面臨的問題是用戶的反饋歷史數(shù)據(jù)太少，稀疏的數(shù)據(jù)嚴(yán)重影響推薦算法的效果。因此研究如何有效地克服數(shù)據(jù)稀疏性的負(fù)面影響，對提高推薦效果有著非常重要的意義。

在用戶反饋歷史中具有豐富的上下文信息，因此本文主要基于兩種上下文信息，提出了一種新的協(xié)同過濾算法CICF。通過在大規(guī)模評分?jǐn)?shù)據(jù)集Yahoo！Music上的實(shí)驗(yàn)結(jié)果表明，CICF推薦效果明顯優(yōu)于傳統(tǒng)的協(xié)同過濾算法，并且能夠有效地緩解評分稀疏性問題。

本文后續(xù)內(nèi)容組織如下：第2節(jié)介紹相關(guān)工作；第3節(jié)詳細(xì)地介紹本文提出的CICF的算法；第4節(jié)給出實(shí)驗(yàn)和結(jié)論；第5節(jié)對全文進(jìn)行總結(jié)和展望。

2 相關(guān)工作

CF方法主要包括兩種：基于內(nèi)存的CF和基于模型的CF［1］?；趦?nèi)存的方法主要利用相似用戶（物品）之間具有相似的喜好這一特點(diǎn)進(jìn)行推薦，比較簡單直觀；基于模型的方法主要是學(xué)習(xí)在訓(xùn)練數(shù)據(jù)集中的復(fù)雜模式，相比基于內(nèi)存的方法具有更強(qiáng)克服稀疏性的能力［2］；其中效果比較好的方法有基于用戶物品偏差的隱參數(shù)模型（RSVD）以及在此基礎(chǔ)上考慮隱式反饋（Implicit Feedback）的SVD＋＋模型［2］。

為了克服基于內(nèi)存的CF方法中用戶—物品評分信息的數(shù)據(jù)稀疏性問題，國內(nèi)外研究者進(jìn)行了一系列研究，提出了多種解決方法。早期研究較多的是預(yù)測填充技術(shù)。文獻(xiàn)［3］采用BP神經(jīng)網(wǎng)絡(luò)進(jìn)行評分預(yù)測。這種方法克服噪聲數(shù)據(jù)能力較強(qiáng)，可以有效降低評分矩陣稀疏性。然而，BP算法會導(dǎo)致近鄰查找時間的延長。文獻(xiàn)［4］采用相似度傳播的思想尋找到更多、更可靠的鄰居，能夠較好提高推薦效果，然而該方法計(jì)算時間較長，臨時空間較大。此外，填充方法通常會帶來歸罪［5］，使得算法效率隨著數(shù)據(jù)增長變得非常低，并且效果不穩(wěn)定。

限于矩陣填充的缺點(diǎn)，更多的研究者從數(shù)據(jù)本身特性進(jìn)行解決稀疏性問題。一方面，由于推薦系統(tǒng)是動態(tài)的，很多研究者研究時間信息對用戶興趣的影響，Ding［6］提出，用戶未來的興趣主要受用戶近期興趣的影響，所以推薦系統(tǒng)側(cè)重對用戶近期行為建模來提高推薦的有效性。Lu［7］在傳統(tǒng)的矩陣分解模型中，將用戶和物品的特征向量看作是一個隨著時間變化的動態(tài)特征向量，從而將時間作為新的一維加入到推薦模型中。Koren［8］從用戶，物品等角度考慮各種時間效應(yīng)，對提升推薦效果起到顯著地作用。

另一方面，研究者利用數(shù)據(jù)中的物品屬性及其它資源解決稀疏性問題。文獻(xiàn)［9］研究利用人口統(tǒng)計(jì)學(xué)特征和用戶行為數(shù)據(jù)構(gòu)建用戶的興趣模型；然而該方法的缺點(diǎn)是粒度太粗。文獻(xiàn)［10］使用物品的文字屬性、社會化標(biāo)簽以及其他標(biāo)簽來緩解用戶反饋數(shù)據(jù)的不足；該方法的缺點(diǎn)沒有考慮用戶的個性化偏好。文獻(xiàn)［11］使用物品的分類信息對用戶以及物品的偏好進(jìn)行建模，然而沒有考慮物品之間的關(guān)聯(lián)關(guān)系對用戶潛在喜好的影響。

根據(jù)上述不足，本文主要考慮用戶評分的短期時間效應(yīng)以及物品中的層次關(guān)聯(lián)關(guān)系對用戶潛在喜好的影響，從而緩解評分稀疏性的負(fù)面效應(yīng)，提高算法的推薦效果。

3 本文工作

3.1 基于層次信息的隱參數(shù)模型

在推薦系統(tǒng)中，物品通常是多類別的。例如，在電子商務(wù)中物品按照不同用途可以分為圖書、影視、電子產(chǎn)品、食品、生活用品等；對于電影可以分為影片、導(dǎo)演、演員、電影類型等；音樂可以分為歌曲（track）、專輯（album）、流派（genre）、演唱家（artist）等。對于不同類型的物品之間可能存在層次關(guān)系，例如給定專輯名字，我們能夠確定它包含的歌曲集合，發(fā)布該專輯的演唱家等；具有關(guān)聯(lián)關(guān)系的物品，可能會影響用戶的潛在喜好，如喜歡一首專輯的用戶，可能會喜歡該專輯中的代表歌曲以及該專輯所屬的演唱家。因此，可以利用物品間的層次信息來挖掘用戶的潛在喜好。

本論文重點(diǎn)研究音樂中的層次信息，但是需要注意的是本論文中的模型同樣適用于其他領(lǐng)域。根據(jù)以上分析，音樂中的層次信息如圖1所示。對于每一個用戶u，我們可以根據(jù)其評分歷史利用層次信息找到更多其潛在的物品。具體地，我們考慮以專輯、演唱家、流派為中心的三種關(guān)聯(lián)關(guān)系：即對于每個專輯，我們考慮它包含的唱片，所屬的演唱家及相關(guān)的流派；對于每個演唱家，我們考慮他包含的唱片、專輯以及和這些唱片、專輯相關(guān)的流派；對于每個流派，我們考慮其相關(guān)的唱片、專輯以及這些唱片專輯所屬的演唱家。

圖1 音樂中的層次信息

我們在隱參數(shù)模型（RSVD）上進(jìn)行改進(jìn)，改進(jìn)后的模型（HierSVD）如式（1）所示。

H（u）由三部分構(gòu)成：H（u）＝album（u）∪artist（u）∪genre（u），分別表示由于u對于專輯、演唱家、流派等的喜好產(chǎn)生的對相關(guān)物品感興趣的集合。對于album（u）的生成過程如下：對于u評分的每個專輯i，我們?nèi)∑湎嚓P(guān)的評分?jǐn)?shù)最多的top－k歌曲，同時統(tǒng)計(jì)i相關(guān)的演唱家和流派的關(guān)聯(lián)次數(shù)，取關(guān)聯(lián)次數(shù)不小于閾值threshold的演唱家和流派。對于artist（u）和genre（u）的生成過程可以類似求出。

進(jìn)一步地，可以在式（1）中加入用戶評分集合同時忽略具體值，模型（HierSVD＋＋）如式（2）所示。

其中R（u）為用戶u的評分集合，y（j）為其相關(guān)的變量。

3.2 基于用戶短期時間段的隱參數(shù)模型

推薦系統(tǒng)是動態(tài)的，用戶的興趣以及物品的受歡迎程度都隨著時間的推移而動態(tài)變化。例如，一首流行歌曲剛推出時非常受歡迎，但是經(jīng)過一段時間之后，可能流行度下降，導(dǎo)致用戶評分降低。相比物品來說，時間效應(yīng)對用戶的影響更大，并且用戶更多的是受短期時間效應(yīng)影響。比如用戶在連續(xù)一段時間內(nèi)評分，前面的評分可能導(dǎo)致其后面評分的變化，同時可能受當(dāng)時心情以及環(huán)境等因素影響。因此本文重點(diǎn)考慮兩種用戶短期時間效應(yīng)。

首先，我們觀察到用戶每天在不同時間段具有不同的評分傾向。例如，用戶白天可能比較忙碌，心情比較緊張，此時評分值相對比較低；而在夜晚，相對比較清閑，心情比較輕松，打的分值稍微較高。因此，我們考慮特定時段信息對用戶評分偏差及特征向量的影響，模型（PeriodSVD）如式（3）所示。

其中t表示用戶每天評分的具體時間，period（t）表示t所處的時間段，為整數(shù)值。bu，period（t），pu，period（t）分別表示時間段效應(yīng)對用戶評分偏差及用戶興趣的影響。

另外，我們注意到用戶在連續(xù)一段評分時間內(nèi)具有明顯的動態(tài)性。首先是用戶前面的評分高低會影響用戶后面的評分，假如用戶非常喜歡聽的第一首歌曲，評分非常高，那么之后的音樂他可能感覺都沒有第一首歌曲好，評分都沒有第一首歌曲高；此外，用戶的評分還會受到當(dāng)時心情的影響。因此，我們通過定義空閑時間段對用戶的評分進(jìn)行分割為連續(xù)的評分時間段，并考慮對用戶偏差以及特征向量的影響，模型（TsliceSVD）如式（4）所示。

其中Tslice（u，i，t）表示評分信息（u，i，t）所處的連續(xù)時間段。

進(jìn)一步，我們可以很容易地結(jié)合模型（3）、（4）同時考慮兩種用戶短期時間效應(yīng)，定義為Short－TempSVD。

3.3 最終模型

在上面兩節(jié)我們分別討論了基于兩種上下文信息的模型，由于兩種方法都基于隱參數(shù)模型進(jìn)行擴(kuò)展，因此我們可以將兩種信息融合在一起進(jìn)行考慮，定義為CICF模型，如式（5）所示。

我們通過采用嶺回歸的方法，最小化在訓(xùn)練數(shù)據(jù)集上的預(yù)測誤差，優(yōu)化目標(biāo)如式（6）所示。

其中R為訓(xùn)練集，λ為正規(guī)化因子。對于該模型，可以很容易地采用梯度下降法求解。

4 實(shí)驗(yàn)和結(jié)論

4.1 實(shí)驗(yàn)數(shù)據(jù)

本論文主要使用Yahoo！Music音樂評分?jǐn)?shù)據(jù)集評估相關(guān)模型。該數(shù)據(jù)集公開在2011年KDDCup比賽中，數(shù)據(jù)集經(jīng)過11年9個月的時間搜集得到，其中評分值為［0－100］內(nèi)的整數(shù)值，每個用戶的打分?jǐn)?shù)都在20以上。用戶和物品id是連續(xù)的整數(shù)，評分日期是經(jīng)過轉(zhuǎn)化的整數(shù)，表示從起始日期到評分日期的天數(shù)，評分時間精確到秒。數(shù)據(jù)集主要包括三部分：訓(xùn)練集、驗(yàn)證集、測試集。數(shù)據(jù)詳細(xì)信息如表1所示。

表1 Yahoo音樂評分?jǐn)?shù)據(jù)集組成

通過表1可以看出整個數(shù)據(jù)集包含將近300M的評分?jǐn)?shù)，是目前公開的規(guī)模最大評分?jǐn)?shù)據(jù)集。通過計(jì)算，該數(shù)據(jù)集的稀疏度為99.6%，比Netflix電影評分?jǐn)?shù)據(jù)集（98.9%）更加稀疏。另外該數(shù)據(jù)集評分值在［0－100］范圍，因此異常稀疏的數(shù)據(jù)和較大的評分范圍使得在Yahoo！Music上進(jìn)行預(yù)測非常具有挑戰(zhàn)性。

此外，該數(shù)據(jù)集中物品是多類別的：歌曲數(shù)目為507 172，專輯數(shù)目為88 909，演唱家數(shù)目為27 888，專輯數(shù)目為992。我們對Yahoo！Music中物品的各類別信息在不同用戶評分?jǐn)?shù)的分布以及評分時間效應(yīng)統(tǒng)計(jì)結(jié)果如圖2（a）～2（b）所示。

通過圖2（a），我們可以看到在評分較少的用戶中，演唱家和專輯的評分比重較多，通過用戶對演唱家、專輯的評分更能準(zhǔn)確地反映出用戶的興趣；用戶評分?jǐn)?shù)較多時，盡管用戶對歌曲的評分占大多數(shù)，此時仍然能夠利用各類別之間的層次關(guān)聯(lián)關(guān)系對用戶的潛在喜好進(jìn)行建模。

從圖2（b）中可以看出，用戶在Yahoo！Music評分?jǐn)?shù)據(jù)集中表現(xiàn)出每天在不同的時間段具有不同的評分傾向；在白天的評分比較低，晚上的評分比較高，而凌晨之后評分有下降的趨勢。因此我們可以有效利用這一信息進(jìn)行建模。

4.2 實(shí)驗(yàn)數(shù)據(jù)

在本文中采用均方誤差（RMSE）來評價評分預(yù)測的準(zhǔn)確度。RMSE對于較大的誤差值賦予了較大的權(quán)重，近年來用得較多。RMSE值越小說明算法效果越好，計(jì)算公式如式（7）所示。

其中T是測試集合，rui是測試集中的真實(shí)評分值，是算法的預(yù)測值。

圖 2

4.3 實(shí)驗(yàn)結(jié)果及分析

對于隱參數(shù)模型在訓(xùn)練時需要學(xué)習(xí)相關(guān)的正規(guī)化因子以及學(xué)習(xí)速率，本文采用自動參數(shù)學(xué)習(xí)方法［12］在驗(yàn)證集上進(jìn)行學(xué)習(xí)相關(guān)參數(shù)，然后在測試集上進(jìn)行評估算法的優(yōu)劣。

首先，我們評估基于層次信息的模型（HierS－VD），在該模型中首先需要計(jì)算artist（u），album（u）和genre（u），計(jì)算時需要設(shè)定top－k及threshold的值，這兩個值是依賴于數(shù)據(jù)集的。通過在驗(yàn)證集上的訓(xùn)練，設(shè)置為：top－k＝10，threshold＝0.3。HierSVD等模型在測試集上的結(jié)果如圖3所示。

圖3 基于層次信息的隱參數(shù)模型

圖3中橫坐標(biāo)表示模型中的特征向量大小，縱坐標(biāo)為在測試集上的誤差。通過在不同向量維度上的實(shí)驗(yàn)結(jié)果表明，相比傳統(tǒng)的RSVD，考慮物品中層次信息的模型HierSVD能夠明顯地提高預(yù)測效果；同時，通過層次信息發(fā)掘用戶的潛在興趣，比使用用戶評過分的物品集合的隱式反饋模型SVD＋＋的作用更有效果，表明使用層次信息能夠更有效地發(fā)掘用戶的潛在喜好；從HierSVD＋＋的效果可以看出，考慮層次信息和隱式反饋的模型能夠同時結(jié)合兩方面的優(yōu)勢，進(jìn)一步地提高預(yù)測精度。

其次，我們評價基于用戶短期時間效應(yīng)的相關(guān)模型。對于TSliceSVD，我們設(shè)定空閑時間段長為5小時；在PeriodSVD中需要設(shè)定Period（t）的取值范圍，根據(jù)圖2（b）所示，我們設(shè)置Period（t）如下：

對于時間效應(yīng)相關(guān)的模型在測試集上的實(shí)驗(yàn)結(jié)果如圖4所示。

從圖4中我們可以發(fā)現(xiàn)相比RSVD，基于用戶特定評分時段的動態(tài)模型（PeriodSVD）以及連續(xù)評分時間的動態(tài)模型（TSliceSVD）都可以有效地提高RSVD的預(yù)測效果，從而證明這兩種時間信息的有效性；另外通過實(shí)驗(yàn)結(jié)果的比較，我們可以發(fā)現(xiàn)將兩種時間效應(yīng)與其他時間信息結(jié)合起來，能夠更加顯著地降低預(yù)測誤差；同時通過圖3和圖4的比較，可以發(fā)現(xiàn)考慮時間效應(yīng)稍微強(qiáng)于基于層次信息的模型。

進(jìn)一步地，我們給出本文中最好模型CICF在測試集上的效果，實(shí)驗(yàn)結(jié)果如表2所示。

圖4 短期時間效應(yīng)模型的實(shí)驗(yàn)效果

表2 CICF在測試集上的實(shí)驗(yàn)效果

從表2中可以看出，CICF能夠充分利用物品間的層次信息以及用戶時間效應(yīng)兩方面的優(yōu)勢，非常顯著地降低了預(yù)測誤差，將RMSE值降低了0.93（3.92%），從而說明了利用音樂數(shù)據(jù)集本身的上下文信息能夠克服評分稀疏性，提高算法的推薦性能。

最后，為了驗(yàn)證本文中算法能夠有效緩解評分稀疏性帶來的負(fù)面效應(yīng)，我們在不同稀疏度的訓(xùn)練集上進(jìn)行了相關(guān)實(shí)驗(yàn)。對于每個用戶按照時間先后順序分別取前K個評分作為新的訓(xùn)練數(shù)據(jù)，保持驗(yàn)證集和測試集不變，并取特征向量大小為50，評測結(jié)果如表3所示。

表3 在不同稀疏度訓(xùn)練集上的結(jié)果對比

從表3中可以看出，隨著訓(xùn)練數(shù)據(jù)變得越稀疏，兩種算法的預(yù)測效果都變得越差，說明評分稀疏性問題對推薦算法的效果影響很大；相比SVD，CICF算法在訓(xùn)練數(shù)據(jù)非常稀疏時的優(yōu)勢更加明顯，當(dāng)K＝50時推薦效果提升了8.01%。由此可以充分說明CICF能夠有效地克服稀疏評分?jǐn)?shù)據(jù)帶來的負(fù)面影響，提高算法的推薦效果。

5 總結(jié)和展望

本文主要介紹了一種融合兩種上下文信息的協(xié)同過濾算法CICF，該算法一方面利用物品的層次信息找到更多用戶可能感興趣但是還沒有評分的物品，另一方面通過對用戶評分的短期時間效應(yīng)建模來挖掘用戶的動態(tài)偏好，進(jìn)而提高預(yù)測的精確性。實(shí)驗(yàn)結(jié)果驗(yàn)證了CICF方法的有效性。

未來工作主要包括：利用物品的層次信息找到有關(guān)物品的更多更可靠的鄰居集合；考慮數(shù)據(jù)中物品的時間效應(yīng)；并將這些上下文信息統(tǒng)一融合在本文提到的模型中。

［1］ Badrul Sarwar，George Karypis，Joseph Konstan，et al.Item Based Collaborative Filtering Recommendation Algorithms［C］／／Proceedings of WWW10，2001：285－295.

［2］ Yahoo！Music dataset［DB／OL］.http：／／kddcup.yahoo.com／.

［3］ FZhang，C H Y.A Collaborative Filtering Algorithm Embedded BP Network to Ameliorate Aparsity Issue［C］／／Proceedings of International Conference on Machine Learning and Cybernetics.2005.

［4］ 趙琴琴，魯凱，王斌.SPCF：一種基于內(nèi)存的傳播式協(xié)同過濾推薦算法［C］／／CCIR 2011.

［5］ B M Sarwar，G Karypis，J A K，Riedl J.Application of Dimensionality Reduction in Recommender System Case Study［R］.2000.

［6］ Y Ding，X Li.Time weight collaborative filtering［C］／／Proceedings of 14th ACM International Conference on Information and Knowledge Management（CIKM'04），2004：485－492.

［7］ Z Lu，D Agarwal，and S Dhillon.A Spatio－temporal Approach to Collaborative Filtering［C］／／Proceedings of 3rd ACM Conference on Recommender Systems，RecSys'09，NY，USA，2009：13－20.

［8］ Y Koren.Collaborative Filtering with Temporal Dynamics［C］／／Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.KDD09，NY，2009：89－97.

［9］ M Montaner，B Lopez，Josep.A Taxonomy of Recommender Agents on the Internet［J］.Artif.Intell.Rev.，2003，19：285－330.

［10］ Lamere P.Social Tagging and Music Information Retrieval［J］.Journal of New Music Research，2008，37（2）：101－114.

［11］ Dror G，Koenigstein N，Koren Y.Yahoo！Music Recommendations：Modeling Music Ratings with Temporal Dynamics and Item Taxonomy［C］／／Proceedings 5th ACM Conference on Recommender Systems.RecSys'11，2011.

［12］ Toscher A，Jahrer M，Bell R.The Bigchaos Solution to the Netflix Grand Prize［R］.2009.

［13］ Koren Y.Factorization Meets the Neighborhood：A Multifaceted Collaborative Filtering Model［C］／／Proceeding of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，ACM 2008：426－434.