劉江冬，梁剛，楊進(jìn)（.四川大學(xué)計(jì)算機(jī)學(xué)院，成都　60065；.樂山師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院，樂山　64000）

基于時(shí)效性的冷啟動(dòng)解決算法

劉江冬1，梁剛1，楊進(jìn)2
（1.四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065；2.樂山師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院，樂山614000）

0　引言

隨著Web 2.0時(shí)代的到來,社交媒體、電子商務(wù)等越來越普及和流行,網(wǎng)上用戶行為發(fā)生了巨大的變化。在線用戶不僅僅消費(fèi)信息,而且每個(gè)用戶還會(huì)生產(chǎn)信息，信息量以指數(shù)規(guī)律迅猛地增長(zhǎng)和擴(kuò)展，造成了信息過載問題。信息過濾的一種重要解決方法是推薦系統(tǒng)[1]技術(shù)，已經(jīng)成為Web 2.0時(shí)代的電子商務(wù)、社交媒體場(chǎng)景中一種重要的個(gè)性化信息服務(wù)形式。目前推薦系統(tǒng)主要采用的是協(xié)同過濾算法[2]，由于其簡(jiǎn)單有效的實(shí)際應(yīng)用效果，已經(jīng)被廣泛的研究和應(yīng)用，其基本原理是相似用戶也具有相似的偏好，它首先通過相似性計(jì)算獲取當(dāng)前用戶的KNN最近鄰，然后根據(jù)鄰居用戶的評(píng)分記錄計(jì)算目標(biāo)用戶對(duì)還未產(chǎn)生過評(píng)分的項(xiàng)目的預(yù)測(cè)評(píng)分。但協(xié)同過濾技術(shù)由于僅僅是利用評(píng)分?jǐn)?shù)據(jù)產(chǎn)生推薦，因而存在稀疏性問題、冷啟動(dòng)問題、擴(kuò)展性問題等[2]。任何推薦系統(tǒng)在使用過程中都無法避免冷啟動(dòng)問題，因?yàn)閯偼度霊?yīng)用或正在使用的推薦系統(tǒng)都會(huì)有隨時(shí)加入的新用戶和新項(xiàng)目，如果為新用戶和新項(xiàng)目進(jìn)行有效推薦，則能有效地保留客戶和挖掘潛在用戶。

1　相關(guān)工作

為解決協(xié)同過濾中的冷啟動(dòng)問題，相關(guān)學(xué)者專家進(jìn)行了大量的研究和嘗試，現(xiàn)有的研究方向主要分為兩類：一類是直接利用評(píng)分?jǐn)?shù)據(jù)而不考慮新用戶或新項(xiàng)目?jī)?nèi)容屬性信息，主要有隨機(jī)推薦的方法、平均值法、眾數(shù)法、相似度度量改進(jìn)法；第二類是將新用戶或新項(xiàng)目的內(nèi)容屬性信息與評(píng)分?jǐn)?shù)據(jù)相結(jié)合的方法，主要有基于原始評(píng)分矩陣擴(kuò)充的方法、構(gòu)建概率統(tǒng)計(jì)模型的方法、與機(jī)器學(xué)習(xí)相結(jié)合的方法。

隨機(jī)推薦法是最簡(jiǎn)單最直觀的方法，系統(tǒng)隨機(jī)地推薦項(xiàng)目給新用戶，這是比較冒險(xiǎn)的方式，能為新用戶推薦滿意的項(xiàng)目的概率不會(huì)很高。平均值法[3]首先將新用戶對(duì)未評(píng)分項(xiàng)目的預(yù)測(cè)值用所有項(xiàng)目的評(píng)分均值進(jìn)行填充，然后在填充之后的評(píng)分矩陣上計(jì)算目標(biāo)用戶的KNN最近鄰，最后采用協(xié)同過濾為目標(biāo)用戶產(chǎn)生推薦，這也是一種非常簡(jiǎn)單的方法。眾數(shù)法[4]依據(jù)用戶一般都有從眾心理，采用所有用戶對(duì)項(xiàng)目的評(píng)分個(gè)數(shù)最多的那個(gè)值作為新用戶對(duì)未評(píng)分項(xiàng)目的預(yù)測(cè)評(píng)分值。相似度度量改進(jìn)法[5]解決的是兩個(gè)用戶共同評(píng)分個(gè)數(shù)較少，相似度計(jì)算精確度不高的問題，對(duì)于沒有評(píng)分的冷啟動(dòng)問題無能為力。冷啟動(dòng)問題產(chǎn)生是由于評(píng)分信息不足造成的，第一類方法都只是單一地考慮了評(píng)分信息，沒有能夠更進(jìn)一步地挖掘評(píng)分?jǐn)?shù)據(jù)的上下文信息。

基于原始評(píng)分矩陣擴(kuò)充[6]的基本思想是在原始用戶-項(xiàng)目評(píng)分矩陣中添加用戶的人口統(tǒng)計(jì)信息和項(xiàng)目的內(nèi)容特征信息，在擴(kuò)充后的矩陣上再利用協(xié)同過濾算法進(jìn)行推薦。構(gòu)建概率統(tǒng)計(jì)模型的方法[7]是利用用戶、項(xiàng)目、評(píng)分構(gòu)建相應(yīng)概率分布，利用期望最大化迭代算法獲得用戶在評(píng)分給定的情況下某項(xiàng)目出現(xiàn)的概率，然后將概率大于給定閾值或前TopN的項(xiàng)目推薦給用戶。與機(jī)器學(xué)習(xí)相結(jié)合方法[8]的基本原理是挖掘評(píng)分和內(nèi)容的隱含關(guān)系，在用戶或項(xiàng)目的內(nèi)容信息數(shù)據(jù)基礎(chǔ)之上訓(xùn)練出學(xué)習(xí)模型，給新用戶產(chǎn)生相應(yīng)的推薦。因?yàn)榭紤]了用戶或項(xiàng)目的內(nèi)容屬性信息，第二類方法提高了推薦精度而且改善了冷啟動(dòng)問題，一定程度上緩解了第一類方法中由于信息單一而推薦精度不高的問題。但是在實(shí)際應(yīng)用中，由于隱私問題，獲取用戶的屬性信息存在一定難度，而且對(duì)于非結(jié)構(gòu)化的項(xiàng)目，獲取內(nèi)容屬性信息也不是一件容易的事情。

針對(duì)于以上問題，本文提出了基于項(xiàng)目時(shí)效性模型的冷啟動(dòng)解決方法，充分利用評(píng)分?jǐn)?shù)據(jù)上下文信息，利用系統(tǒng)中過往的點(diǎn)擊記錄，建立項(xiàng)目的時(shí)效性評(píng)價(jià)模型，在為新用戶產(chǎn)生推薦的過程中，選擇時(shí)效性高的項(xiàng)目推薦給新用戶，既充分利用了已有的評(píng)分?jǐn)?shù)據(jù)信息，又避免了用戶的屬性信息難以獲取的問題。

2　項(xiàng)目時(shí)效性模型

本文利用評(píng)分?jǐn)?shù)據(jù)上下文信息構(gòu)建項(xiàng)目時(shí)效性模型，將所有用戶對(duì)項(xiàng)目的評(píng)分記錄作為考察集S，把集合S以項(xiàng)目為單位進(jìn)行子集劃分，從而將集合S劃分成一系列的子集s。對(duì)于項(xiàng)目i，si={t1，t2，t3，…，tk，…，tq}，其中q表示系統(tǒng)中對(duì)項(xiàng)目i產(chǎn)生過評(píng)分行為的用戶數(shù)，tk表示某用戶對(duì)項(xiàng)目i產(chǎn)生評(píng)分行為的具體時(shí)刻，在t時(shí)刻項(xiàng)目i的時(shí)效性表示為Ci（t）。由于推薦系統(tǒng)中的項(xiàng)目評(píng)分等信息屬于廣義上信息的一種，所以也滿足信息價(jià)值老化的經(jīng)典模型[9]，如式（1）所示：

其中t表示當(dāng)前時(shí)間，tf表示項(xiàng)目s發(fā)布的時(shí)間，Cs（t）表示項(xiàng)目在t時(shí)刻的時(shí)效性大小，a代表的是信息老化率系數(shù)。在推薦系統(tǒng)中，本文引入項(xiàng)目的生命周期、半衰期兩個(gè)概念，以便于更好地描述。項(xiàng)目從發(fā)布的時(shí)刻tf到項(xiàng)目不再被點(diǎn)擊或評(píng)論為止的時(shí)刻tf+Ta之間的時(shí)間段為項(xiàng)目生命周期Ta。項(xiàng)目自發(fā)布的時(shí)刻tf開始到項(xiàng)目的影響力降為一半的時(shí)刻tf+Th之間的時(shí)間段為項(xiàng)目的半衰期Th。

公式（1）從數(shù)學(xué)角度定量地描述了項(xiàng)目在生命周期Ta中的每個(gè)時(shí)刻的時(shí)效性大小，本文設(shè)計(jì)的冷啟動(dòng)解決算法結(jié)合了信息老化的模型，對(duì)項(xiàng)目的時(shí)效性做如下的定義：

定義1項(xiàng)目s在t時(shí)刻的時(shí)效性CS（t）為：項(xiàng)目在時(shí)間段（t，tf+Ta）內(nèi)被點(diǎn)擊或評(píng)論的數(shù)量R（t，tf+Ta）與在生命周期Ta內(nèi)被點(diǎn)擊的數(shù)量R（Ta）之比，如公式（2）所示。

為了能夠由公式（1）快速計(jì)算出項(xiàng)目在當(dāng)前時(shí)刻t的時(shí)效性大小，須求得系統(tǒng)中的信息老化率系數(shù)a，通過公式（1）化簡(jiǎn)可得：

其中T=t-tf，根據(jù)公式（2），首先計(jì)算一個(gè)項(xiàng)目s在經(jīng)過時(shí)間段T后還擁有的時(shí)效性Cs（t）值，然后代入公式（3）得到項(xiàng)目的老化率系數(shù)a。我們由公式（2）計(jì)算出項(xiàng)目在時(shí)刻t擁有的時(shí)效性的大小Cs（t），但公式（2）考察的目標(biāo)是單個(gè)項(xiàng)目s，無法表達(dá)出整個(gè)數(shù)據(jù)集的統(tǒng)計(jì)特性，本文通過公式（4）計(jì)算S中的子集s對(duì)應(yīng)T=t-tf的平均值，記為T。

其中|S|為考察集合S中子集的個(gè)數(shù)，把公式（3）和（4）結(jié)合得到公式（5）:

在公式（5）中，我們選擇Cs（t）=1/2，即T=t-tf實(shí)際上是s的半衰期Th，則T為所有項(xiàng)目半衰期的平均值Th，公式（5）簡(jiǎn)化為：

通過公式（6），得到每個(gè)子集s的半衰期Th就計(jì)算出了系統(tǒng)中信息老化率系數(shù)a。本文有單個(gè)項(xiàng)目評(píng)分量的集合si={t1，t2，t3，…，tk，…，tq}，在其中找出中間的評(píng)分時(shí)刻tm，則Th=tm-tf，根據(jù)公式（6）計(jì)算出系統(tǒng)中項(xiàng)目的老化率a。得到老化率a之后利用公式（4）計(jì)算出在當(dāng)前時(shí)刻項(xiàng)目i的時(shí)效性Ci（T），最后選擇時(shí)效性最高的TopN個(gè)項(xiàng)目推薦給新用戶，N由交叉驗(yàn)證確定。

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

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

本文采用的實(shí)驗(yàn)數(shù)據(jù)集為明尼蘇達(dá)大學(xué)（University of Minnesota）GroupLens研究院小組的MovieLens （1M）數(shù)據(jù)集[10]，該數(shù)據(jù)集包含6040名用戶對(duì)3900部電影的1000209次1～5分的評(píng)分?jǐn)?shù)據(jù)，每位用戶至少對(duì)20部電影進(jìn)行過評(píng)分。用戶評(píng)分表（rating.dat）由用戶ID、項(xiàng)目ID、項(xiàng)目評(píng)分值與評(píng)分時(shí)間4個(gè)字段構(gòu)成。本文將數(shù)據(jù)集隨機(jī)分為訓(xùn)練集和測(cè)試集，其中訓(xùn)練集所占比例為80%，測(cè)試集所占的比例為20%。

3.2評(píng)價(jià)指標(biāo)

本文采用TopN推薦準(zhǔn)確度（precision）作為度量標(biāo)準(zhǔn)，驗(yàn)證本文提出算法的有效性。TopN推薦準(zhǔn)確度指取前N個(gè)（TopN）推薦給目標(biāo)用戶，根據(jù)TopN推薦列表中某個(gè)被推薦項(xiàng)目是否出現(xiàn)在了目標(biāo)用戶的測(cè)試集中，判斷是否生成了一個(gè)正確推薦[11]，計(jì)算公式如（7）式：

其中Ut表示測(cè)試集中的用戶集合，Ru（N）表示推薦給用戶u的項(xiàng)目集合，Tu表示測(cè)試集中用戶u的項(xiàng)目集合。

3.3實(shí)驗(yàn)步驟

為了驗(yàn)證本文提出的基于項(xiàng)目時(shí)效性的冷啟動(dòng)解決算法（Timeliness-based Algorithm for Cold Start，TACS）的有效性，將TACS算法和文獻(xiàn)[4]中的眾數(shù)法（Mode-based Algorithm for Cold Start，MACS），以及文獻(xiàn)[7]中的概率統(tǒng)計(jì)模型解決方法（Probability Statistical Model for Cold Start，PSMCS）進(jìn)行對(duì)比實(shí)驗(yàn)。首先在測(cè)試集中隨機(jī)抽取6組不同個(gè)數(shù)的用戶作為新用戶，6組取值依次為 100個(gè)、200個(gè)、300個(gè)、500個(gè)、700個(gè)、1000，然后訓(xùn)練集中對(duì)應(yīng)的用戶的評(píng)分信息依次置為0。然后分別將TACS算法、MACS算法、PSMCS算法在處理后的訓(xùn)練集和測(cè)試集中進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表1所示：

表1　對(duì)比實(shí)驗(yàn)結(jié)果

由表1可知，在不同新用戶數(shù)目情況下，本文提出的TACS算法的準(zhǔn)確度均為最高，這說明了TACS算法解決新用戶冷啟動(dòng)問題的有效性。同時(shí)，隨著新用戶數(shù)目的增加，三個(gè)算法的準(zhǔn)確度都會(huì)下降，這是因?yàn)樾掠脩舻脑黾訉?dǎo)致了測(cè)試集中新用戶類別的增加，而三個(gè)算法在解決冷啟動(dòng)問題方面都存在一定的局限性，不可能為所有類別的新用戶都產(chǎn)生準(zhǔn)確的推薦。

4　結(jié)語

冷啟動(dòng)問題是協(xié)同過濾推薦算法中一個(gè)重要的研究方向，本文提出了基于項(xiàng)目時(shí)效性的解決算法，為新用戶推薦時(shí)效性高的項(xiàng)目，從而緩解新用戶冷啟動(dòng)問題，最后的對(duì)比實(shí)驗(yàn)驗(yàn)證了該算法的有效性。時(shí)效性是衡量推薦系統(tǒng)中項(xiàng)目的一個(gè)重要屬性，但是為了進(jìn)一步提高為新用戶推薦的準(zhǔn)確度，可將時(shí)效性與用戶或項(xiàng)目的內(nèi)容屬性信息相結(jié)合，充分利用已知信息解決新用戶或新項(xiàng)目的冷啟動(dòng)問題，這也是下一步的研究方向。

[1]XU HL,WU X,LI XD,et al.Comparison Study of Internet Recommendation System[J].Journal of Software,2009,20(2):350-362.

[2]BASILICO J，HOFMANN T.A Joint Framework for Collaborative and Content Filtering[C.ACM SIGIR 2004:2004Association of Computing Machinery and Special Interest Group on Information Retrieval.New York,NY,USA,2004:550-551.

[3]郭艷紅.推薦系統(tǒng)的協(xié)同過濾算法與應(yīng)用研究［D］.大連:大連理工大學(xué)，2008.

[4]Ahn H J.A New Similarity Measure for Collaborative Filtering to Alleviate the New User Cold-Starting Problem[J].Information Sci-ences，2008，178(1):37-51．

[5]孫少華.協(xié)同過濾系統(tǒng)的稀疏性與冷啟動(dòng)問題研究［D］.杭州:浙江大學(xué),2005．

[6]Balabanovic M，Shoham Y．Fab:Content-base，Collaborative Recommendation［J］．Communications of the ACM，1997,40(3):66-72．

[7]Lam X N，Vu T，Le T D，et al．Addressing Cold-Start Problem in Recommendation Systems［C］.ICUIMC'08.New York,USA，2008: 208-211．

[8]Park S T，Pennock D M，Madani O，et al．Nave Filterbots for Robust Cold-Start Recommendations［C］.KDD'06，2006:699-705．

[9]YIN G,CUI X,MA Z,et al.Web Services Evaluation Model based on Variant Time Utility[J].Journal of Southwest Jiaotong University, 2012,47(4):652-661.

[10]MovieLens 1M Dataset.http://grouplens.org/datasets/movielens/1m/.

[11]Music Recommendation Using Content and Context Information Mining[J].IEEE Intelligent Systems,2010,25(1):16-26.

Recommender System;Collaborative Filtering;Cold Start;Timeliness

Timeliness-Based Algorithm for Cold Start

LIU Jiang-dong1，LIANG Gang1，YANG Jin2

（1.College of Computer Science,Sichuan University,Chengdu 610065；2.College of Computer Science,Leshan Normal University,Leshan 614000）

1007-1423（2016）05-0003-04

10.3969/j.issn.1007-1423.2016.05.001

劉江冬（1989-），男，湖北荊門人，碩士研究生，研究方向?yàn)闄C(jī)器學(xué)習(xí)、推薦系統(tǒng)

梁剛（1976-），男，四川成都人，博士，講師，研究方向?yàn)闄C(jī)器學(xué)習(xí)、智能計(jì)算、網(wǎng)絡(luò)安全

楊進(jìn)（1980-），男，四川成都人，博士，講師，研究方向?yàn)闄C(jī)器學(xué)習(xí)、網(wǎng)絡(luò)安全

2016-01-07

2016-01-25

在推薦系統(tǒng)研究領(lǐng)域，協(xié)同過濾推薦技術(shù)是一種重要的技術(shù)方法，但新用戶和新項(xiàng)目等冷啟動(dòng)問題是該技術(shù)方法所面對(duì)的一個(gè)重要問題。為解決新用戶冷啟動(dòng)問題，充分利用評(píng)分?jǐn)?shù)據(jù)上下文信息，提出一種基于項(xiàng)目時(shí)效性模型的解決算法，把時(shí)效性高的項(xiàng)目推薦給剛加入系統(tǒng)的新用戶，從而緩解新用戶冷啟動(dòng)問題。實(shí)驗(yàn)結(jié)果驗(yàn)證所提出的算法在保證推薦精度的情況下能為新用戶產(chǎn)生有效的推薦。

推薦系統(tǒng)；協(xié)同過濾；冷啟動(dòng)；時(shí)效性

四川省科技廳項(xiàng)目（No.2014JY0036）、四川省教育廳創(chuàng)新團(tuán)隊(duì)基金（No.13TD0014）

Collaborative filtering recommendation technology is the most important technology in recommender systems,but the technology is facing new users and new items cold start problem.To solve the new users cold start problem,proposes a solution algorithm based on item timeliness model by making full use of the context information of rating data,and recommends high timeliness items for new users.The experimental results verify that the algorithm proposed produces effective recommendation for new users.