基于時效性的冷啟動解決算法

劉江冬，梁剛，楊進（.四川大學計算機學院，成都　60065；.樂山師范學院計算機科學學院，樂山　64000）

基于時效性的冷啟動解決算法

劉江冬1，梁剛1，楊進2
（1.四川大學計算機學院，成都610065；2.樂山師范學院計算機科學學院，樂山614000）

0　引言

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

1　相關(guān)工作

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

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

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

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

2　項目時效性模型

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

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

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

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

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

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

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

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

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

3　實驗結(jié)果及分析

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

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

3.2評價指標

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

其中Ut表示測試集中的用戶集合，Ru（N）表示推薦給用戶u的項目集合，Tu表示測試集中用戶u的項目集合。

3.3實驗步驟

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

表1　對比實驗結(jié)果

由表1可知，在不同新用戶數(shù)目情況下，本文提出的TACS算法的準確度均為最高，這說明了TACS算法解決新用戶冷啟動問題的有效性。同時，隨著新用戶數(shù)目的增加，三個算法的準確度都會下降，這是因為新用戶的增加導致了測試集中新用戶類別的增加，而三個算法在解決冷啟動問題方面都存在一定的局限性，不可能為所有類別的新用戶都產(chǎn)生準確的推薦。

4　結(jié)語

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

[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é)同過濾算法與應用研究［D］.大連:大連理工大學，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］.杭州:浙江大學,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-），男，湖北荊門人，碩士研究生，研究方向為機器學習、推薦系統(tǒng)

梁剛（1976-），男，四川成都人，博士，講師，研究方向為機器學習、智能計算、網(wǎng)絡(luò)安全

楊進（1980-），男，四川成都人，博士，講師，研究方向為機器學習、網(wǎng)絡(luò)安全

2016-01-07

2016-01-25

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

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

四川省科技廳項目（No.2014JY0036）、四川省教育廳創(chuàng)新團隊基金（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.