朱桂祥 曹 杰,2

1(南京理工大學(xué)計算機(jī)科學(xué)與工程學(xué)院 南京 210094) 2 (南京財經(jīng)大學(xué)江蘇省電子商務(wù)重點實驗室 南京 210003) (zgx881205@gmail.com)

近年來,推薦系統(tǒng)領(lǐng)域的研究工作發(fā)展迅猛,各種各樣的推薦系統(tǒng)亦隨之在電子商務(wù)、社交網(wǎng)站、電子旅游、互聯(lián)網(wǎng)廣告等大量領(lǐng)域得到了廣泛應(yīng)用,并展示出優(yōu)越的效果與前景[1-3].其中,隨著越來越多的在線旅游網(wǎng)站的興起(如Expedia,Travelzoo、途牛等)能刻畫用戶旅游興趣偏好的在線數(shù)據(jù)越來越豐富,使得旅游產(chǎn)品推薦成為推薦系統(tǒng)研究領(lǐng)域的熱門議題之一[4-6].

目前,針對傳統(tǒng)商品的推薦已有許多成熟的推薦算法得到廣泛應(yīng)用,如協(xié)同過濾算法[7]、基于內(nèi)容的推薦算法[8]和混合型推薦算法[9]等.然而大量已有研究表明[4-6,10-12]:旅游產(chǎn)品推薦與電影、商品等傳統(tǒng)推薦有顯著差異.1)用戶通常不會頻繁或大量購買旅游產(chǎn)品,這導(dǎo)致“用戶-產(chǎn)品”關(guān)聯(lián)矩陣極為稀疏;2)旅游產(chǎn)品描述信息維度多樣復(fù)雜,微小的參數(shù)變化會導(dǎo)致完全不同的旅游產(chǎn)品,如景點參觀線路和日程、酒店和交通工具選擇等因素的變化,然而這類有內(nèi)在關(guān)聯(lián)的不同旅游產(chǎn)品卻指向用戶共同的興趣偏好;3)用戶往往不會長期關(guān)注旅游產(chǎn)品,即在電子旅游網(wǎng)站上留下訪問記錄,而往往是有了旅游目標(biāo)和安排之后,才開始瀏覽旅游產(chǎn)品,這導(dǎo)致在線旅游數(shù)據(jù)中存在大量冷啟動用戶.因此,針對傳統(tǒng)商品的推薦算法很難直接應(yīng)用到旅游推薦領(lǐng)域.

基于上述原因,本文首先從旅游數(shù)據(jù)的特征入手,對旅游數(shù)據(jù)的稀疏性和冷啟動問題進(jìn)行了深入的分析,并從日志會話的相似性角度進(jìn)行了論證,以啟發(fā)研究基于主題序列模式的旅游產(chǎn)品推薦引擎.具體而言,本文首先提出了面向旅游產(chǎn)品的推薦引擎(sequential recommendation engine for travel products, SECT),該引擎通過用戶實時點擊流可以捕捉用戶的興趣偏好,并實時產(chǎn)生旅游產(chǎn)品推薦列表.其次,本文分別從旅游頁面的主題挖掘、訪問序列的模式挖掘和模式庫的存儲、匹配計算等方面對SECT的原理進(jìn)行了詳細(xì)的說明.為了提升在線匹配計算的效率,本文設(shè)計一種新的多叉樹數(shù)據(jù)結(jié)構(gòu)PSC-tree用于存儲歷史模式庫,并與在線計算模塊無縫銜接.最后,本文選取了常用的基準(zhǔn)推薦算法,在真實的旅游數(shù)據(jù)集上進(jìn)行了實驗對比,并從多個評價指標(biāo)上對實驗結(jié)果進(jìn)行分析.實驗結(jié)果表明:SECT推薦引擎不但性能上比傳統(tǒng)推薦算法更有優(yōu)勢,更值得注意的是SECT在對冷啟動用戶和長尾物品推薦方面也具有顯著的優(yōu)勢.

1 相關(guān)工作

本節(jié)主要回顧一些與本文相關(guān)的研究工作,這些工作主要圍繞旅游推薦和基于序列模式的推薦展開.

1) 旅游推薦.從應(yīng)用場景角度看,旅游推薦大致包含2類:①興趣點或路徑推薦;②旅游產(chǎn)品或套餐推薦.第1類應(yīng)用場景吸引了大部分研究者的目光,試圖融合移動終端數(shù)據(jù)與地理信息數(shù)據(jù)為用戶推薦興趣點(points of interest, POI)[13-15]或為旅游者動態(tài)推薦旅游路徑[16-18].如文獻(xiàn)[15]從用戶大量的GPS軌跡數(shù)據(jù)中挖掘興趣點和旅行線路序列,通過協(xié)同過濾方法為用戶推薦景點和線路；文獻(xiàn)[18]從社交網(wǎng)絡(luò)中的旅游圖片信息抽取用戶的特征并根據(jù)旅游地標(biāo)和路徑信息挖掘出頻繁模式,最終構(gòu)建貝葉斯學(xué)習(xí)模型對用戶線路進(jìn)行個性化推薦；面向第2類應(yīng)用場景的研究則相對偏少,已有研究[4-5,12]針對旅游數(shù)據(jù)稀疏性強(qiáng)等特點,大多先從異構(gòu)數(shù)據(jù)中提取描述旅游產(chǎn)品的多維度特征,如從文本中提取的隱含主題、景點與地域的關(guān)系、時間與價格的關(guān)系等,以期加強(qiáng)用戶和產(chǎn)品之間的關(guān)聯(lián),從而設(shè)計出一些新穎的協(xié)同過濾或基于內(nèi)容的推薦方法.比如Liu等人[4-5]的系列研究嘗試從STA Travel*STA Travel, URL: http://www.statravel.com/旅游套餐描述文本中挖掘潛在主題,結(jié)合季節(jié)和價格等因素提出混合協(xié)同過濾推薦方法,該類方法有效地解決了協(xié)同過濾推薦在極其稀疏的旅游數(shù)據(jù)中應(yīng)用的問題.

2) 基于時間序列的推薦.本文的研究立足于第2類應(yīng)用場景,試圖從用戶點擊旅游網(wǎng)站頁面留下的日志數(shù)據(jù)出發(fā)挖掘用戶行為模式,從而根據(jù)用戶實時點擊流推薦旅游產(chǎn)品.因此,與本文研究相關(guān)的另一系列研究工作是基于時間序列或軌跡數(shù)據(jù)的推薦系統(tǒng).文獻(xiàn)[19-20]基于出租車GPS軌跡數(shù)據(jù)的挖掘推薦最近載客點及避擁堵行駛路徑；文獻(xiàn)[21]通過挖掘播放列表預(yù)測用戶喜歡的音樂標(biāo)簽；文獻(xiàn)[22]則研究了時間序列數(shù)據(jù)中的事件預(yù)測問題；文獻(xiàn)[23]提出了一種排序?qū)W習(xí)模型,它通過融合潛在因子和行為序列的效用函數(shù)來提升購買預(yù)測的精度.由于時間序列數(shù)據(jù)的復(fù)雜性及應(yīng)用問題的多樣性,基于時間序列數(shù)據(jù)的推薦問題仍然呈現(xiàn)出開放性[24-25]；同時,從日志數(shù)據(jù)角度切入研究旅游產(chǎn)品推薦問題雖然已經(jīng)有一定的研究成果,但是此類工作[11,26-27]的日志數(shù)據(jù)大多是基于用戶分享的地理位置標(biāo)簽或者發(fā)表的游記,該類日志數(shù)據(jù)類型單一,可以用于刻化旅游產(chǎn)品的特征比較少,也很難精確地表征用戶的興趣偏好；如文獻(xiàn)[11]從游記文本中抽取地理信息并構(gòu)建了一個“Location-Topic”主題模型進(jìn)行景點或者旅游目的地推薦.

總的來說,以上已有的相關(guān)推薦技術(shù)在某種程度上解決了旅游推薦問題.但是這類推薦技術(shù)只適應(yīng)于數(shù)據(jù)結(jié)構(gòu)相對簡單的旅游數(shù)據(jù)或者依賴于地理信息數(shù)據(jù),且很難全面地捕捉用戶的實時興趣偏好.而本文使用的數(shù)據(jù)為旅游企業(yè)真實的Web服務(wù)器日志,該日志蘊(yùn)含了豐富的旅游產(chǎn)品相關(guān)信息和大量的用戶行為的點擊記錄,通過構(gòu)建推薦引擎能夠根據(jù)用戶實時的點擊流精確地捕捉用戶即時的興趣并對站內(nèi)旅游產(chǎn)品進(jìn)行個性化推薦.

2 數(shù)據(jù)描述

2.1 數(shù)據(jù)來源與規(guī)模

本文所使用的旅游產(chǎn)品數(shù)據(jù)集來自于途牛旅游網(wǎng)*http://www.tuniu.com/,包含用戶訪問Web服務(wù)器日志和用戶訂單記錄.每條服務(wù)器日志記錄表示為一個五元組:由User_ID,Page_ID,Page_Name,Time,Session_ID字段構(gòu)成.其中User_ID用于跟蹤用戶,為用戶匿名標(biāo)識,由瀏覽器Cookie生成;Page_ID和Page_Name分別表示途牛頁面標(biāo)識及相應(yīng)代表頁面的語義文本描述;Time為用戶訪問時間;Session_ID用于標(biāo)識該條記錄所屬的用戶會話.用戶訂單記錄則由User_ID,Item_ID,Time構(gòu)成,其中User_ID代表下單的用戶;Item_ID為用戶購買的旅游產(chǎn)品標(biāo)識;Time代表為用戶下單時間.

旅游產(chǎn)品數(shù)據(jù)集的時間跨度為2個月(即2013年7-8月).本文實驗以7月份用戶訪問日志為訓(xùn)練集,用于挖掘用戶興趣偏好;8月份訂單記錄及其所屬會話為測試集,用于驗證推薦引擎的效果.我們對訓(xùn)練數(shù)據(jù)做了必要的預(yù)處理,包括:1)刪除了大量重復(fù)出現(xiàn)的首頁;2)刪除了會員登錄后訪問留下的重定向登錄頁面.表1展示了預(yù)處理后訓(xùn)練集的規(guī)模,其中#Session,#Record,#User,#Page分別表示會話、記錄、用戶和頁面的數(shù)量,#L表示會話平均長度.頁面包含產(chǎn)品頁面和非產(chǎn)品頁面,產(chǎn)品頁面又進(jìn)一步細(xì)分為出境簽證、旅游線路及景點門票,這些產(chǎn)品不僅能體現(xiàn)出用戶的興趣偏好,同時也是推薦的目標(biāo)對象.與其不同的是,非產(chǎn)品頁面包含分類頁面和攻略頁面2類,分類頁面是包含用戶選定的旅游目的地或旅游主題的所有產(chǎn)品頁面的匯總,例如西藏旅游、歐洲旅游、名山勝水、游樂園、海邊海島等;攻略頁面介紹了目的地的旅游景點、線路、美食、住宿、地圖、游記等.這2類頁面的主題有助于推薦引擎刻畫用戶的興趣偏好.表2展示了訓(xùn)練集頁面的分類及規(guī)模,其中#Visa,#Route,#Ticket,#Category,#Guide分別代表出境簽證、旅游線路、景點門票、分類和攻略頁面的數(shù)量.可以看出,非產(chǎn)品頁面數(shù)量甚至超過了產(chǎn)品頁面數(shù)量,這意味著基于“用戶-項目”矩陣的傳統(tǒng)產(chǎn)品推薦方法將不能利用非產(chǎn)品頁面中蘊(yùn)含的豐富信息.

Table 1 Statistic of the Training Set表1 訓(xùn)練集日志數(shù)據(jù)特征

Table 2 Category and Sizes of Web Pages表2 頁面分類及規(guī)模

2.2 數(shù)據(jù)特點

本節(jié)通過分析旅游數(shù)據(jù)集的特點,以闡明提出本文方法的動機(jī).

特點1.“用戶-項目”購買矩陣極度稀疏.

表3描述了測試集中訂單數(shù)據(jù)的基本特征,其中#Order,#User,#Item分別代表訂單、用戶、項目數(shù)量,Density代表密度.如果構(gòu)建“用戶-項目”購買矩陣使用協(xié)同過濾算法[28]進(jìn)行推薦,矩陣中非零值比例僅為0.0155%,而常用的MovieLens100K*http://grouplens.org/datasets/movielens/100k/“用戶-項目”評分矩陣的密度為6.3%.我們再觀察用戶購買旅游產(chǎn)品的次數(shù)分布,如圖1所示,有27 551(94.8%)的用戶僅購買1種旅游產(chǎn)品,僅有0.07%的用戶購買了5種以上的旅游產(chǎn)品.因此,傳統(tǒng)協(xié)同過濾算法難以直接運行于“用戶-項目”購買矩陣.

Table 3 Statistic of Purchase Record in Test Data表3 測試集訂單數(shù)據(jù)特征

Fig. 1 The distribution of user-item purchasing matrix圖1 用戶購買旅游產(chǎn)品次數(shù)分布

特點2. 冷啟動用戶比例極高.

在測試集的訂單數(shù)據(jù)中,有20 990個用戶為冷啟動用戶,比例達(dá)到63.7%,即存在大量用戶在訓(xùn)練數(shù)據(jù)中沒有任何訪問記錄.當(dāng)然,部分冷啟動用戶可能使用不同終端訪問網(wǎng)站,利用Cookie標(biāo)識用戶容易引起冷啟動用戶比例偏高.圖2展示了剩余的8 067個用戶在訓(xùn)練集中的訪問網(wǎng)頁數(shù)量,可以看出,接近半數(shù)的用戶在上個月訪問網(wǎng)頁數(shù)量不足10個.因此,冷啟動用戶比例高是基于日志數(shù)據(jù)推薦所面臨的挑戰(zhàn)性問題之一,即如果構(gòu)造“用戶-項目”訪問頻率矩陣同樣面臨數(shù)據(jù)稀疏性問題,傳統(tǒng)協(xié)同過濾算法仍然難以奏效.

Fig. 2 The distribution of user-item visiting matrix圖2 用戶瀏覽頁面的數(shù)量分布

特點3. 購買同種產(chǎn)品的會話相似性高.

從測試集的訂單數(shù)據(jù)中,我們首先提取被購買超過10次的熱門旅游產(chǎn)品688個,再抽取不同用戶購買每個產(chǎn)品的訪問會話22 584條,該會話包含下訂單操作.動態(tài)時間規(guī)劃(dynamic time warping, DTW)定義了序列之間的最佳對齊匹配關(guān)系,支持不同長度時間序列的相似性度量[29],被廣泛用于衡量時間序列的相似性.我們計算購買同種產(chǎn)品會話的DTW距離(標(biāo)記為Intra-Sessions),為便于比較,我們再計算每個會話與其他所有會話的DTW距離(標(biāo)記為Inter-Sessions),圖3展示了上述2種情況的DTW距離分布.

Fig. 3 The DTW distribution among sessions purchasing the same product圖3 購買同種產(chǎn)品的會話DTW距離分布

從圖3可以看出,在最小DTW區(qū)間[0,3)上,Intra-Sessions比例遠(yuǎn)遠(yuǎn)高于基準(zhǔn)線,而在較大的DTW距離區(qū)間上(如[6,9),[9,12),[12,15),[18,21]),Intra-Sessions比例卻低于基準(zhǔn)線.因此,盡管用戶興趣迥異,購買同個旅游產(chǎn)品的訪問序列(即會話)卻有較高的相似性,這啟發(fā)著本文利用頻繁序列模式作為推薦引擎的計算依據(jù).

3 推薦引擎總體框架

本節(jié)簡要介紹SECT推薦引擎的總體框架,如圖4所示,主要分為離線批處理和在線計算兩大模塊,其功能簡述:

1) 離線批處理.①從頁面語義文本描述中挖掘主題,將相似度高的線路產(chǎn)品映射到同一泛化主題,以期擴(kuò)大匹配范圍,技術(shù)細(xì)節(jié)將在4.1節(jié)中介紹;②將經(jīng)主題泛化后會話集合看作時間序列事務(wù)數(shù)據(jù)集,從中挖掘序列頻繁模式,形成點擊模式庫,并為每個模式尋找相關(guān)聯(lián)的候選產(chǎn)品,技術(shù)方案將在4.2節(jié)中闡述.

2) 在線計算.該模塊的任務(wù)主要是根據(jù)用戶最新的訪問會話,基于由離線批處理所產(chǎn)生的模式庫進(jìn)行匹配計算和推薦分值計算,最終依據(jù)推薦分值的排序,產(chǎn)生一個Top-k的推薦列表,技術(shù)細(xì)節(jié)將在4.3節(jié)中予以介紹.

Fig. 4 The framework of SECT engine圖4 SECT推薦引擎總體框架

SECT推薦引擎具有較好的可擴(kuò)展性,離線批處理在空閑時間周期性執(zhí)行,承擔(dān)計算繁重的主題挖掘與序列頻繁模式挖掘任務(wù);而在線計算模塊則負(fù)責(zé)輕量級的匹配和分值計算任務(wù).

4 基于主題序列模式的推薦方法

4.1 頁面主題泛化

頁面主題泛化試圖將內(nèi)容相似的不同頁面投影到同一個主題,進(jìn)而將主題相同的訪問序列合并成一個主題序列.圖5給出了一個說明性例子,從Page_ID上看,2個用戶訪問序列差異甚大.但是,從頁面描述文本上看,2個訪問序列均反映出用戶計劃去北京旅游的興趣偏好.此外,訪問序列中的分類頁面和攻略頁面也同樣反映出用戶的興趣偏好.

旅游線路頁面的文本描述信息復(fù)雜多樣化,且具有顯著的領(lǐng)域特色.抽取主題本質(zhì)上是文本聚類問題,通常,最樸素直觀的思路是將文本形成詞袋模型,然后通過不同的聚類算法進(jìn)行文本聚類操作,從而實現(xiàn)主題抽取.但是這種方法對數(shù)據(jù)噪音比較敏感,在實際應(yīng)用中文本聚類難以獲得良好效果,因此我們提出用主題模型(latent Dirichlet allocation, LDA)[30]模型降維并過濾噪音,再通過K-Means[31]進(jìn)行文本聚類實現(xiàn)主題抽取.首先,對線路頁面文本信息進(jìn)行分詞、去停用詞等預(yù)處理操作得到文本向量矩陣.其次,借助LDA模型對所有文本向量矩陣進(jìn)行主題建模,并采用Gibbs抽樣法對建模后的文本向量矩陣進(jìn)行求解,得到線路頁面的隱含主題概率分布矩陣,進(jìn)而將該矩陣作為K-Means的輸入.最終聚類后的每個類簇分別代表線路頁面的不同主題.

與線路頁面不同的是簽證和門票頁面的文本描述信息為明確的結(jié)構(gòu)化數(shù)據(jù),其中簽證頁面包含簽證國家和簽證類型,門票頁面包含景點名稱和景點所在地,我們分別依據(jù)簽證國家和景點所在地對簽證和門票頁面進(jìn)行主題泛化.在分類頁面和攻略頁面中,考慮到這些頁面的文本描述特點,我們直接依據(jù)旅游目的地或者旅游主題對這2類頁面進(jìn)行主題泛化.

設(shè)I={i1,i2,…,iM}為訓(xùn)練集中所有的頁面集合,Т={t1,t2,…,tK}為所有頁面泛化后的主題集合,頁面主題泛化可以抽象為函數(shù):

φ(ip)→tk，

(1)

其中,1≤p≤M,1≤k≤K,M表示頁面的數(shù)量,設(shè)K為頁面泛化的主題數(shù)量,tk表示為頁面ip經(jīng)泛化后的主題.

Fig. 5 An example of two different sessions which can reflect the same preferences to travel around Beijing圖5 體現(xiàn)出北京旅游偏好的2個不同會話的舉例

4.2 序列模式挖掘及存儲結(jié)構(gòu)

由2.2節(jié)中旅游數(shù)據(jù)特點可知,購買同個旅游產(chǎn)品的訪問序列具有較高的相似性,而且用戶當(dāng)前的興趣偏好能夠通過訪問序列的頁面主題來刻畫.因此,挖掘用戶訪問主題序列的模式對于刻畫用戶興趣偏好顯得尤為重要.每一個主題模式代表不同用戶訪問旅游頁面的興趣偏好.

定義1. 主題訪問序列事務(wù)集.主題訪問序列事務(wù)集由訓(xùn)練集中所有主題訪問序列組成,記為D={D1,D2,…,DU},1≤u≤U.其中,U為用戶數(shù)量,Du表示由連續(xù)訪問頁面組成的訪問序列Xu通過式(1)泛化后得到的主題訪問序列.因此,Xu包含的項集都是I的子集,Du包含的項集都是T的子集.

定義2. 主題頻繁時序模式.令P為主題時序模式,模式P的支持度計數(shù)與支持度分別表示成σ(P)和supp(P),設(shè)min_supp為最小支持度閾值,若σ(P)≥min_supp,則稱P為主題頻繁時序模式.

本文采用Eclat (equivalence class transformation)算法[32]對主題序列模式進(jìn)行挖掘.Eclat算法是采用垂直數(shù)據(jù)表示的頻繁項集挖掘方法,在序列模式挖掘中應(yīng)用廣泛.將主題訪問序列事務(wù)集D作為Eclat的輸入,設(shè)置min_supp,通過運行Eclat程序得到挖掘出的主題頻繁時序模式項集,記為P={P1,P2,…,PS},其中S為模式的數(shù)量.

在基于關(guān)聯(lián)規(guī)則的推薦算法里候選項目取之于關(guān)聯(lián)規(guī)則右邊的項目[33],即候選項目被頻繁模式所包含.由于每個頻繁模式里的項目都是頻繁的,這極大地限制了候選項集的質(zhì)量和多樣性.為了解決這個難題,我們抽取了每個頻繁模式在原始會話中緊跟著的旅游產(chǎn)品頁面作為候選項集,方法如算法1所示,其中模式Ps(1≤s≤S)對應(yīng)的候選集記為CPs,每個模式對應(yīng)的候選集都是I的子集.最終所有模式對應(yīng)的候選集記為C={CP1,CP2,…,CPs}.

算法1. SECT產(chǎn)品候選集提取算法.

輸入:模式項集P、主題序列事務(wù)集合D；

輸出:產(chǎn)品候選集C.

① fors=1 toSdo

② for eachDu∈Ddo

③ ifPsinDuthen

④ 返回Ps在主題訪問序列Du中的末尾位置l并從訪問序列Xu中提取第l+1個訪問頁面it;

⑤ ifit為產(chǎn)品頁面then

⑥CPs←CPs∪{it};

⑦ end if

⑧ end if

⑨ end for

⑩C←C∪CPs;

測試集中用戶的主題序列與模式庫中模式項集的匹配對于推薦引擎的效率而言是極大的挑戰(zhàn),通常一種蠻力的做法是將主題序列與模式庫中的模式一一匹配,但是考慮到模式庫中模式的數(shù)量,這種做法不但影響推薦引擎的效率,而且還增加推薦引擎的運行負(fù)擔(dān).為了使SECT推薦引擎能夠根據(jù)用戶訪問會話快速匹配到模式庫中的主題模式,我們提出了一個多叉樹數(shù)據(jù)結(jié)構(gòu)PSC-tree (pattern support candidate-tree)用于存儲歷史模式庫,并與匹配計算模塊無縫銜接.

定義3. PSC-tree.PSC-tree是一個多叉樹:

1) 包含一個名為Root的根節(jié)點,其余節(jié)點為Root節(jié)點的孩子節(jié)點;

2) 每個節(jié)點都有2個域,第1個域存儲模式的支持度計數(shù),第2個域存儲產(chǎn)品候選集;

3) 從PSC-tree第2層的每個節(jié)點開始,每一個遍歷到孩子節(jié)點的路徑分別代表對應(yīng)的主題序列模式.

圖6展示了PSC-tree的構(gòu)造示例:1)將主題頻繁時序模式項集中的模式按照頁面標(biāo)識進(jìn)行排序,形成如圖6(a)中的列表;2)初始的PSC-tree只有一個根節(jié)點,按照以下方法依據(jù)圖6(a)中的模式列表依次構(gòu)造孩子節(jié)點:①讀取第1個主題頻繁時序模式T1,T2,構(gòu)造節(jié)點T1和T2,增加路徑Root→T1→T2,支持度計數(shù)σ(T1,T2)=20存儲在節(jié)點T2的第1個域中,推薦候選集CT1,T2={i3,i5,i6}存儲在第2個域中;②第2個模式T1,T2,T3與第1個模式具有公共的前綴T1,T2,因此,節(jié)點T3增加在路徑Root→T1→T2的終點,節(jié)點T3的2個域也存儲對應(yīng)的信息;3)以上過程直到每一個模式映射到PSC-tree中的其中一條路徑為止.按照圖6(a)中的模式項集,構(gòu)造PSC-tree的最終結(jié)果如圖6(b)所示.

Fig. 6 An illustration of PSC-tree圖6 PSC-tree的示例說明

4.3 基于n-gram模型的推薦計算

不失一般性,設(shè)用戶u的實時頁面訪問會話為:Xu=i1,i2,…,ip,ip為最晚訪問的頁面.初始設(shè)待推薦的目標(biāo)產(chǎn)品為it,我們將會話Xu中每個產(chǎn)品映射到對應(yīng)的主題,即Xu=T1,T2,…,Tp,Tq=φ(iq),1≤q≤p.為了更簡明地表示,我們將T1,T2,…,Tp標(biāo)記為Tp1.我們用條件概率Pr(it|Tp1)表示給定會話Xu時,用戶u對產(chǎn)品it的偏好程度,即:Pr(it|Tp1)越大表明用戶u購買該目標(biāo)產(chǎn)品的概率越高.理論上,Pr(it|Tp1)由Xu的所有子序列所決定:

(2)

(3)

在Markovn-gram獨立性假設(shè)之下,求解式(3)可以簡化為

① http://mahout.apache.org/

(4)

(5)

其中,β為懲罰因子,衡量的是平滑處理后的n-2項子序列和處理前n-1項序列之間的條件概率衰減,可計算為

(6)

算法2展示了基于主題序列模式的推薦算法.對于給定的用戶u的實時會話Xu,首先將其映射為主題序列,我們再重復(fù)執(zhí)行以上的back-off models流程直到生成一個推薦分值集合R為止.對于任意一個給定的目標(biāo)產(chǎn)品it,其對應(yīng)的分值集合記為R(it),我們將目標(biāo)產(chǎn)品分值集合按照降序排列,最終取分值最高的k個產(chǎn)品作為推薦列表,記為Top-k.

算法2. 基于n-gram的推薦算法.

輸出:推薦列表Top-k.

② forj=p-n+2 topdo

③ 在PSC-tree中尋找路徑Root→Tj→…→Tp,從路徑終點Tp讀取σ(Ps)和CPs;*Ps=*

④ if (σ(Ps)>0) then

⑤ for eachit∈CPsdo

⑥Tt=φ(it),沿著路徑Root→Tj→…→

⑦R←R∪R(it);

⑧ end for

⑨ break;

⑩ end if

5 實驗結(jié)果和分析

本節(jié)展示在實際旅游數(shù)據(jù)集(如第2節(jié)所述)上的實驗結(jié)果及比較分析.

5.1 實驗設(shè)置

1) 基準(zhǔn)推薦算法.我們選擇4種最常見的推薦算法作為比較對象:

① 基于用戶的協(xié)同過濾算法(user-based coll-aborative filtering, UCF)[38],選擇余弦為相似度度量,近鄰用戶數(shù)量設(shè)為10.

② 基于矩陣分解模型的協(xié)同過濾(singular value decomposition, SVD)[39],潛變量維度設(shè)為100.UCF和SVD均借助開源項目Mahout①實現(xiàn),同時,由于2.2節(jié)的研究已經(jīng)表明旅游數(shù)據(jù)中“用戶-項目”購買矩陣極度稀疏,因此我們構(gòu)造“用戶-項目”訪問頻率矩陣作為協(xié)同過濾的輸入,矩陣中的元素表示用戶點擊線路頁面的次數(shù).

③ 流行推薦算法Popular,按照購買次數(shù)直接排序,取最熱門的Top-k種產(chǎn)品作為推薦列表;

④ 基于關(guān)聯(lián)規(guī)則挖掘的推薦算法(max confi-dence algorithm, MCA)[33],從訓(xùn)練數(shù)據(jù)中挖掘頻繁項集,以置信度作為推薦分值計算依據(jù).SECT和MCA中的min_supp均默認(rèn)設(shè)置為15,主題數(shù)量K均設(shè)為80.由于訓(xùn)練集中會話平均長度為5.64,因此當(dāng)測試集中會話長度大于6時,推薦算法中n取5,否則n即為會話長度.

2) 評價指標(biāo).我們選擇3類指標(biāo)從不同角度衡量推薦引擎的性能,其中,F-measure是體現(xiàn)推薦引擎準(zhǔn)確率的綜合指標(biāo)[40],Coverage是反映推薦列表多樣性的指標(biāo)[41],NDCG@k(normalized discounted cumulative gain)則用于衡量推薦列表的排序優(yōu)劣[42].具體地,假設(shè)為用戶u推薦生成的Top-k列表記為Ru,Ru(j)代表為用戶u產(chǎn)生的推薦列表在位置j上的產(chǎn)品,測試集中用戶u真正購買的產(chǎn)品列表為Gu,上述3種評價指標(biāo)的計算方法如下:

①F-measure是準(zhǔn)確率(Precision)和召回率(Recall)的調(diào)和平均值,值越高則表明推薦系統(tǒng)的精度越好.

(7)

②Coverage指的是推薦結(jié)果里的物品占全部物品的比例,比例越高代表推薦系統(tǒng)推薦的產(chǎn)品覆蓋范圍越廣.

(8)

③NDCG@k是一個考慮推薦項目次序的指標(biāo),該指標(biāo)衡量了推薦項目的排名,值越高代表排序推薦效果越好:

(9)

NDCG@k計算的是位置j從1到k總的NDCG值;Rel是一個指示函數(shù),計算的是推薦項目出現(xiàn)在位置j的增益,在本文中,如果列表中位置為j的推薦產(chǎn)品為用戶下單的產(chǎn)品,則Rel的值為1,否則為0;IDCG為規(guī)格化因子,代表最理想情況下的DCG值[43],在本文中,最理想的DCG情況為用戶實際下單產(chǎn)品在推薦列表中排名第一,即IDCG=1.

5.2 總體性能比較分析

圖7分別展示了SECT和另外4種基準(zhǔn)算法在3類評價指標(biāo)上的對比結(jié)果,x軸為Top-k推薦列表長度,分別設(shè)為3,5,10,20.總體上看,SECT推薦引擎在不同指標(biāo)上均明顯優(yōu)于其他基準(zhǔn)推薦算法,其中Popular流行推薦效果最差,這說明用戶在購買旅游產(chǎn)品時具有明顯的個性化偏好,排行榜式的推薦難以取得良好效果.

Fig. 7 Performance comparison on different evaluation metrics圖7 在不同評價指標(biāo)上的比較

從圖7(a)可以看出,當(dāng)k值分別取10和20時,SECT的F-measure超過30%,比排名第2的UCF算法高出至少10%.從平均意義上,SECT每推薦10種旅游產(chǎn)品將會帶來3次的實際購買.

從圖7(b)可以看出,SECT在Coverage指標(biāo)上的性能最好,且隨著k的增大,優(yōu)勢變得更加顯著,當(dāng)k=20時,Coverage達(dá)到40%,這表明SECT推薦結(jié)果能覆蓋更多的產(chǎn)品;UCF和SVD通過“用戶-項目”訪問頻率矩陣能夠找到的相似用戶的數(shù)量比較少,因此,推薦的產(chǎn)品覆蓋范圍有限;Popular針對所有用戶都是推薦同樣的流行產(chǎn)品,因此,Coverage值最低,接近于0.

從圖7(c)可以看出,SECT的推薦列表排序效果最好,UCF其次,MCA僅次于UCF,當(dāng)k值逐漸增大到20,MCA和UCF的推薦產(chǎn)品的排序性能接近.當(dāng)k值分別取10和20時,SECT要比UCF和MCA高出至少5%,比SVD高出至少10%.這充分說明SECT推薦的正確的產(chǎn)品位置比較靠前,排序性能較好.

5.3 冷啟動用戶推薦效果

旅游數(shù)據(jù)冷啟動問題是影響旅游推薦的一個難題.正如2.2節(jié)中所提及,本文旅游數(shù)據(jù)集中的冷啟動用戶比例較高,測試集中冷啟動用戶數(shù)量達(dá)到20 090.因此,針對冷啟動用戶的推薦性能評估顯得尤為重要.我們選擇了5.2節(jié)中推薦效果相對不錯的UCF和SVD作為基準(zhǔn)算法,考察針對冷啟動用戶的推薦性能.

圖8展示了SECT與基準(zhǔn)算法在產(chǎn)生推薦的冷啟動用戶比例方面的對比,可以看出SECT能夠為93.1%的冷啟動用戶產(chǎn)生推薦列表.從平均意義來看,每10個冷啟動用戶就有9個能夠被SECT產(chǎn)生推薦.而SVD要比SECT要低10.9%.此外,UCF產(chǎn)生推薦的冷啟動用戶比例最低,僅為67.7%.

Fig. 8 Cold-start users with successful recommendations圖8 產(chǎn)生推薦的冷啟動用戶

圖9展示了SECT與基準(zhǔn)算法針對冷啟動用戶推薦準(zhǔn)確率的對比,可以看出SECT性能最出色.當(dāng)k值分別取3和5時,UCF與SECT在推薦準(zhǔn)確率方面接近,而隨著k值增加,SECT的優(yōu)勢越來越顯著.當(dāng)k=20時,準(zhǔn)確推薦的冷啟動用戶占產(chǎn)生推薦的冷啟動用戶的比例高達(dá)44.3%,分別比UCF和SVD的勝出5%和32%.盡管UCF在產(chǎn)生推薦的冷啟動用戶的性能方面要差于SVD,但是在冷啟動用戶推薦準(zhǔn)確率方面要更勝一籌.

Fig. 9 Cold-start users with accurate recommendations圖9 準(zhǔn)確推薦的冷啟動用戶

表4進(jìn)一步將SECT對測試集中冷啟動用戶和全局用戶的推薦結(jié)果進(jìn)行了對比,可以看出冷啟動用戶的會話并沒有降低SECT的推薦性能,與全局用戶上的推薦性能基本一致.因此,相比于協(xié)同過濾算法,SECT在解決冷啟動問題上優(yōu)勢顯著.

Table4PerformanceComparisonamongCold-startUsersandGlobalUsersinTermsofF-measureResults

表4 冷啟動用戶和全局用戶在F-measure上的比較

從以上實驗分析可知,相比于傳統(tǒng)推薦算法,SECT推薦引擎不但性能具有明顯優(yōu)勢,而且針對冷啟動用戶的推薦率和準(zhǔn)確率方面也提高顯著.這是由于SECT根據(jù)用戶實時會話從主題泛化的層面捕捉用戶興趣,且不受冷啟動問題的困擾,而UCF和SVD借助的“用戶-項目”訪問頻率矩陣比較稀疏,因此,在冷啟動用戶的方面表現(xiàn)都不如SECT.

5.4 長尾物品的推薦

眾所周知,對于推薦系統(tǒng)而言推薦流行的商品較為容易也微不足道,而推薦長尾物品增加了推薦商品的新穎性,同時也是一個挑戰(zhàn)[44].

圖10展示了訓(xùn)練集中所有產(chǎn)品的訪問頻率分布,可以看出長尾現(xiàn)象尤其顯著.具體而言,訓(xùn)練集中所有產(chǎn)品的平均訪問頻率為17,此外,低于平均訪問頻率的產(chǎn)品比例高達(dá)80.7%,這意味著大多數(shù)的訪問集中于少數(shù)的流行產(chǎn)品.我們同樣選擇UCF和SVD作為基準(zhǔn)算法來考察SECT挖掘長尾物品的能力.

Fig. 10 Visiting distribution over items in the training set圖10 訓(xùn)練集中產(chǎn)品的訪問頻率分布

圖11展示了3種算法在旅游數(shù)據(jù)集上推薦產(chǎn)品的平均流行度(即產(chǎn)品在訓(xùn)練集中的訪問頻率).總體來看,SECT推薦的產(chǎn)品的流行度要低于UCF和SVD,其中UCF最高,SVD其次.當(dāng)k分別取值3和5時,SECT和SVD接近,而UCF的流行度明顯偏高.相比于UCF和SVD,隨著k的不斷增大SECT推薦的產(chǎn)品的流行度下降趨勢更加顯著,當(dāng)k=20時,SECT的流行度為221,而UCF和SVD分別高達(dá)319和278.

Fig. 11 Average frequency of recommended items圖11 推薦商品的平均流行度

我們將訓(xùn)練集中所有物品根據(jù)訪問頻率進(jìn)行倒序排序,分別將排在前60%,70%,80%,90%的產(chǎn)品標(biāo)記為長尾物品.圖12分別展示了SECT與基準(zhǔn)算法在Top-20推薦列表中準(zhǔn)確推薦的長尾產(chǎn)品的比例.從圖12可以看出,在長尾產(chǎn)品閾值從0.6～0.9之間SECT性能要優(yōu)于UCF和SVD,且隨著閾值增加,SECT優(yōu)勢越來越顯著.當(dāng)閾值設(shè)為0.9時,SECT推薦準(zhǔn)確的長尾產(chǎn)品比例為22.8%,分別比UCF和SVD的性能高出9%和12%.因此,相比于傳統(tǒng)的協(xié)同過濾算法,SECT的推薦列表更具有新穎性,能夠準(zhǔn)確推薦更多的長尾物品,這得益于SECT能夠從歷史會話中挖掘出很多有趣的模式.

Fig. 12 Niche items with accurate recommendations圖12 準(zhǔn)確推薦的長尾產(chǎn)品

6 總 結(jié)

本文研究了基于主題序列模式的旅游產(chǎn)品推薦問題.首先,本文提出了SECT推薦引擎,離線批處理階段,SECT利用已有的LDA和K-Means算法從頁面語義描述文本中挖掘旅游主題,并通過ECLAT算法對在線旅游網(wǎng)站點擊日志進(jìn)行挖掘產(chǎn)生頻繁序列模式,最后依據(jù)本文提出的算法從模式庫和日志會話中產(chǎn)生候選產(chǎn)品集;在線計算階段,提出了基于Markovn-gram的推薦算法,依據(jù)用戶實時點擊流進(jìn)行模式匹配和推薦產(chǎn)品的分值計算,最終產(chǎn)生旅游產(chǎn)品推薦列表.同時,設(shè)計了一種新的多叉樹數(shù)據(jù)結(jié)構(gòu)PSC-tree以存儲模式庫并提升在線匹配計算的效率.為了驗證SECT的優(yōu)勢,本文在真實旅游數(shù)據(jù)集上進(jìn)行了實驗,實驗結(jié)果表明:SECT推薦引擎不但在性能上比傳統(tǒng)推薦算法更有優(yōu)勢,而且能有效提升冷啟動用戶和長尾物品的推薦率和準(zhǔn)確率.

[1]Guo Hongyi, Liu Gongshen, Su Bo, et al. Collaborative filtering recommendation algorithms combining community structure and interest clusters[J]. Journal of Computer Research and Development, 2016, 53(8): 1664-1672 (in Chinese)

(郭弘毅, 劉功申, 蘇波, 等. 融合社區(qū)結(jié)構(gòu)和興趣聚類的協(xié)同過濾推薦算法[J]. 計算機(jī)研究與發(fā)展, 2016, 53(8): 1664-1672)

[2]Ge Yong, Xiong Hui, Tuzhilin A, et al. An energy-efficient mobile recommender system[C] //Proc of the 16th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2010: 899-908

[3]Adomavicius G, Tuzhilin A. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions[J]. IEEE Trans on Knowledge and Data Engineering, 2005, 17(6): 734-749

[4]Liu Qi, Ge Yong, Li Zhongmou, et al. Personalized travel package recommendation[C] //Proc of the 11th Int Conf on Data Mining. Los Alamitos, CA: IEEE Computer Society, 2011: 407-416

[5]Liu Qi, Chen Enhong, Xiong Hui, et al. A cocktail approach for travel package recommendation[J]. IEEE Trans on Knowledge and Data Engineering, 2014, 26(2): 278-293

[6]Ge Yong, Liu Qi, Xiong Hui, et al. Cost-aware travel tour recommendation[C] //Proc of the 17th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2011: 983-991

[7]Ge Yong, Xiong Hui, Tuzhilin A, et al. Collaborative filtering with collective training[C] //Proc of the 5th ACM Int Conf on Recommender Systems. New York: ACM, 2011: 281-284

[8]Pazzani M J, Billsus D. Content-Based Recommendation Systems[M]. Berlin: Springer, 2007: 325-341

[9]Burke R. Hybrid Web Recommender Systems[M]. Berlin: Springer, 2007: 377-408

[10]Jannach D, Zanker M, Fuchs M. Constraint-based recommendation in tourism: A multiperspective case study[J]. Information Technology & Tourism, 2009, 11(2): 139-155

[11]Hao Qiang, Cai Rui, Wang Changhu, et al. Equip tourists with knowledge mined from travelogues[C] //Proc of the 19th Int Conf on World Wide Web. New York: ACM, 2010: 401-410

[12]Tan Chang, Liu Qi, Chen Enhong, et al. Object-oriented travel package recommendation[J].ACM Trans on Intelligent Systems and Technology, 2014, 5(3): 43:1-43:26

[13]Baltrunas L, Ludwig B, Peer S, et al. Context-aware places of interest recommendations for mobile users[C] //Proc of the 14th Int Conf of Design, User Experience, and Usability. Berlin: Springer, 2011: 531-540

[14]Gavalas D, Konstantopoulos C, Mastakas K, et al. Mobile recommender systems in tourism[J]. Journal of Network and Computer Applications, 2014, 39: 319-333

[15]Zheng Yu, Xie Xing. Learning travel recommendations from user-generated GPS traces[J]. ACM Trans on Intelligent Systems and Technology, 2011, 2(1): 9:1-9:29

[16]Cao Xin, Cong Gao, Jensen C S. Mining significant semantic locations from GPS data[J]. Proceedings of the VLDB Endowment, 2010, 3(1): 1009-1020

[17]Drosatos G, Efraimidis P S, Arampatzis A, et al. Pythia: A privacy-enhanced personalized contextual suggestion system for tourism[C] //Proc of the 39th Annual Int Conf Computers, Software & Applications. Los Alamitos, CA: IEEE Computer Society, 2015: 822-827

[18]Cheng Anjung, Chen Yanying, Huang Yenta, et al. Personalized travel recommendation by mining people attributes from community-contributed photos[C] //Proc of the 19th ACM Int Conf on Multimedia. New York: ACM, 2011: 83-92

[19]Ge Yong, Liu Chuanren, Xiong Hui, et al. A taxi business intelligence system[C] //Proc of the 17th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2011: 735-738

[20]Yuan Jing, Zheng Yu, Zhang Chengyang, et al. T-drive: Driving directions based on taxi trajectories[C] //Proc of the 18th SIGSPATIAL Int Conf on Advances in Geographic Information Systems. New York: ACM, 2010: 99-108

[21]Hariri N, Mobasher B, Burke R. Context-aware music recommendation based on latenttopic sequential patterns[C] //Proc of the 6th ACM Conf on Recommender Systems. New York: ACM, 2012: 131-138

[22]Letham B, Rudin C, Madigan D. Sequential event prediction[J]. Machine Learning, 2013, 93(2): 357-380

[23]Zeng Xianyu, Liu Qi, Zhao Hongke, et at. Online consumptions prediction via modeling user behaviors and choices[J]. Journal of Computer Research and Development, 2016, 53(8): 1673-1683 (in Chinese)

(曾憲宇, 劉淇, 趙洪科, 等. 用戶在線購買預(yù)測: 一種基于用戶操作序列和選擇模型的方法[J]. 計算機(jī)研究與發(fā)展, 2016, 53(8): 1673-1683)

[24]Chen Wei, Niu Zhendong, Zhao Xiangyu, et al. A hybrid recommendation algorithm adapted in e-learning environments[J]. World Wide Web, 2014, 17(2): 271-284

[25]Wright A P, Wright A T, McCoy A B, et al. The use of sequential pattern mining to predict next prescribed medications[J]. Journal of Biomedical Informatics, 2015, 53(C): 73-80

[26]Kennedy L S, Naaman M. Generating diverse and representative image search results for landmarks[C] //Proc of the 17th Int Conf on World Wide Web. New York: ACM, 2008: 297-306

[27]Mei Qiaozhu, Liu Chao, Su Hang, et al. A probabilistic approach to spatiotemporal theme pattern mining on weblogs[C] //Proc of the 15th Int Conf on World Wide Web. New York: ACM, 2006: 533-542

[28]Schafer J B, Frankowski D, Herlocker J, et al. Collaborative Filtering Recommender Systems[M]. Berlin: Springer, 2007: 291-324

[29]Fu A W C, Keogh E, Lau L Y, et al. Scaling and time warping in time series querying[J]. The VLDB Journal, 2008, 17(4): 899-921

[30]Blei D M, Ng A Y, Jordan M I. Latent Dirichlet allocation[J]. Journal of machine Learning research, 2003, 3(Jan): 993-1022

[31]Kanungo T, Mount D M, Netanyahu N S, et al. An efficientk-means clustering algorithm: Analysis and implementation[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2002, 24(7): 881-892

[32]Zaki M J. Scalable algorithms for association mining[J]. IEEE Trans on Knowledge & Data Engineering, 2000, 12(3): 372-390

[33]Rudin C, Letham B, et al. Sequential event prediction with association rules[C] //Proc of the 24th Annual Conf on Learning Theory. New York: ACM, 2011: 615-63

[34]Peng Fuchun, Schuurmans D, Wang Shaojun. Augmenting naive bayes classifiers with statistical language models[J]. Information Retrieval, 2004, 7(3): 317-345

[35]Fakhraei S, Foulds J, Shashanka M, et al. Collective spammer detection in evolving multi-relational social networks[C] //Proc of the 21st ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2015: 1769-1778

[36]Ney H, Essen U, Kneser R. On structuring probabilistic dependences in stochastic language modelling[J]. Computer Speech & Language, 1994, 8(1): 1-38

[37]Chen S F, Goodman J. An empirical study of smoothing techniques for language modeling[C] //Proc of the 34th Annual Meeting on Association for Computational Linguistics. New York: ACM, 1996: 310-318

[38]Resnick P, Iacovou N, Suchak M, et al. GroupLens: An open architecture for collaborative filtering of netnews[C] //Proc of the 1994 ACM Conf on Computer Supported Cooperative Work. New York: ACM, 1994: 175-186

[39]Koren Y. Factorization meets the neighborhood: A multifaceted collaborative filtering model[C] //Proc of the 14th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2008: 426-434

[40]Powers D M. Evaluation: From precision, recall andF-measure to ROC, informedness, markedness and correlation[J]. Journal of Machine Learning Technologies, 2011, 2(1): 37-63

[41]Ge Mouzhi, Delgado-Battenfeld C, Jannach D. Beyond accuracy: Evaluating recommender systems by coverage and serendipity[C] //Proc of the 4th ACM Conf on Recommender Systems. New York: ACM, 2010: 257-260

[42]J?rvelin K, Kek?l?inen J. IR evaluation methods for retrieving highly relevant documents[C] //Proc of the 23rd Annual Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2000: 41-48

[43]Hu Meiqun, Lim Eepeng, Sun Aixin, et al. Measuring article quality in Wikipedia: Models and evaluation[C] //Proc of the 16th ACM Conf on Information and Knowledge Management. New York: ACM, 2007: 243-252

[44]Yin Hongzhi, Cui Bin, Li Jing, et al. Challenging the long tail recommendation[J]. Proceedings of the VLDB Endowment, 2012, 5(9): 896-907