基于組合類別空間的隨機(jī)游走推薦算法

樊瑋 謝聰 肖春景 曹淑燕

摘 要：傳統(tǒng)的類別驅(qū)動(dòng)方法只考慮類別間的關(guān)聯(lián)或是將其組織成扁平或?qū)哟谓Y(jié)構(gòu)，而項(xiàng)目和類別對(duì)應(yīng)關(guān)系復(fù)雜，其他信息容易被忽略。針對(duì)這個(gè)問題提出基于組合類別空間的隨機(jī)游走推薦算法，更好地組織了項(xiàng)目類別信息、緩解了數(shù)據(jù)稀疏。首先，建立一個(gè)用哈斯圖表示的項(xiàng)目組合類別空間，將項(xiàng)目和類別復(fù)雜的一對(duì)多關(guān)系映射成一對(duì)一的簡(jiǎn)單關(guān)系，并表示用戶上下層次、同層次及跨層次的項(xiàng)目類別間的跳轉(zhuǎn);接著，定義組合類別空間的語義關(guān)系及鏈接、偏好兩種語義距離，更好地定性、定量描述用戶動(dòng)態(tài)偏好的變化;然后，結(jié)合組合類別空間上用戶瀏覽圖的語義關(guān)系、語義距離、用戶行為跳轉(zhuǎn)、跳轉(zhuǎn)次數(shù)、時(shí)序、評(píng)分等各種信息，利用隨機(jī)游走建立用戶個(gè)性化類別偏好模型;最后，根據(jù)用戶個(gè)性化偏好完成基于用戶的協(xié)同過濾項(xiàng)目推薦。在MovieLens數(shù)據(jù)集上的實(shí)驗(yàn)顯示，與基于用戶的協(xié)同過濾（UCF）、基于類別關(guān)聯(lián)的推薦模型（UBGC和GENC）相比，所提算法推薦的F1-score提高了6～9個(gè)百分點(diǎn)，平均絕對(duì)誤差（MAE）減小了20%～30%;與基于類別層次潛在因子模型（CHLF）相比，所提算法推薦的F1-score提高了10%。實(shí)驗(yàn)結(jié)果表明，所提算法在排序推薦上優(yōu)于傳統(tǒng)基于類別的推薦算法。

關(guān)鍵詞：偏好相似度;梯度下降;隨機(jī)游走;協(xié)同過濾;推薦算法

中圖分類號(hào)：TP301.6

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-9081（2019）04-0984-05

Abstract： The traditional category-driven approaches only consider the association between categories or organize them into flat or hierarchical structure， but the relationships between items and categories are complex， making other information be ignored. Aiming at this problem， a random walk recommendation algorithm based on combinational category space was proposed to better organize the category information of items and alleviate data sparsity. Firstly， a combinational category space of items represented by Hasse diagrams was constructed to map the one-to-many relationship between items and categories into one-to-one simple relationships， and represent the user's jumps between items in higher and lower levels， the same level and the cross-levels. Then the semantic relationships and two types of semantic distances — the links and the preferences were defined to better describe the changes of the user's dynamic preferences qualitatively and quantitatively. Afterwards，the user personalized category preference model was constructed based on random walking and combination of the semantic relationship， semantic distance， user behavior jumping， jumping times， time sequence and scores of the user's browsing graph in the combinatorial category space. Finally， the items were recommended to users by collaborative filtering based on the user's personalized category preference. Experimental results on MovieLens dataset show that compared with User-based Collaborative Filtering （UCF） model and category-based recommendation models （UBGC and GENC）， the recommended F1-score was improved by 6 to 9 percentage points， the Mean Absolute Error （MAE） was reduced by 20% to 30%; compared with Category Hierarchy Latent Factor （CHLF） model， the recommended F1-score was improved by 10%. Therefore， the proposed algorithm has advantage in ranking recommendation and is superior to other category-based recommendation algorithms.

Key words： preference similarity; gradient descent; random walk; collaborative filtering; recommendation algorithm

0?引言

協(xié)同過濾是目前推薦系統(tǒng)中最成功的推薦算法，它認(rèn)為具有相似偏好的用戶應(yīng)該喜歡相似的項(xiàng)目，因此它的核心是為用戶尋找最相似近鄰。它利用用戶與項(xiàng)目的交互信息，將用戶項(xiàng)目評(píng)分看成向量，利用余弦、皮爾遜相關(guān)系數(shù)等相似性度量來發(fā)現(xiàn)近鄰，通過近鄰對(duì)項(xiàng)目評(píng)分預(yù)測(cè)目標(biāo)用戶的喜好。但是一方面計(jì)算相似性時(shí)的評(píng)分向量維度和系統(tǒng)中的項(xiàng)目數(shù)一致，向量維度較高;另一方面由于用戶自身特點(diǎn)，將產(chǎn)生很多相同評(píng)分，由此得到的評(píng)分向量信息冗余且不全面，它的性能在數(shù)據(jù)稀疏或冷啟動(dòng)的情況下受到嚴(yán)重制約。

當(dāng)游走步數(shù)趨于無窮大時(shí)，基于圖的隨機(jī)游走算法能夠返回圖中節(jié)點(diǎn)重要性的排序。它能從全局挖掘用戶/項(xiàng)目關(guān)系，已被廣泛應(yīng)用到推薦過程中緩解數(shù)據(jù)稀疏問題[1-6]。由于項(xiàng)目類別（類型）作為附加信息時(shí)，屬性值相對(duì)穩(wěn)定、與項(xiàng)目?jī)?nèi)容相關(guān)性強(qiáng)，同時(shí)一個(gè)項(xiàng)目往往與多個(gè)類別相關(guān)等特性，項(xiàng)目類別作為重要附加信息引入推薦系統(tǒng)能夠有效緩解數(shù)據(jù)稀疏、解決冷啟動(dòng)問題。

目前基于類別的推薦系統(tǒng)主要分為四類：一類是直接將項(xiàng)目信息加入到傳統(tǒng)協(xié)同過濾中[7]。

二是挖掘用戶偏好和項(xiàng)目類別間的關(guān)聯(lián)，如：Ren等[8]利用項(xiàng)目類別信息，建立用戶動(dòng)態(tài)偏好模型，但是計(jì)算量較大;Manzato等[9]分解用戶類型矩陣得到類別的隱向量解決冷啟動(dòng)問題。

三是計(jì)算項(xiàng)目類別間的關(guān)聯(lián)，根據(jù)用戶偏好類別完成項(xiàng)目推薦[10-11]，但此類方法要求系統(tǒng)必須輸入用戶喜好類別。

最后一類是利用矩陣分解等潛語義模型根據(jù)項(xiàng)目類別的扁平或?qū)哟谓Y(jié)構(gòu)，建立用戶和項(xiàng)目k維向量表示的潛語義模型，來完成項(xiàng)目推薦的過程[12-14]。Sun等[15]根據(jù)類別層次建立用戶和項(xiàng)目隱語義模型并以線性復(fù)雜度自動(dòng)學(xué)習(xí)不同類別的權(quán)值。但它們僅用到項(xiàng)目類別的扁平結(jié)構(gòu)或上下層次關(guān)系，并不能應(yīng)用同層次類別間的關(guān)系;而且用戶和項(xiàng)目的k維向量的維度往往是隨機(jī)設(shè)定的，并沒有明確的語義含義。

針對(duì)以上問題，本文提出基于類別組合空間的隨機(jī)游走推薦算法CCSRank（Combinational Category Space Rank）。

首先，提出組合類別空間來組織項(xiàng)目類別信息，它是一種哈斯圖表示結(jié)構(gòu)，能將一對(duì)多的項(xiàng)目類別映射到一對(duì)一組合類別空間，它比層次結(jié)構(gòu)具有更豐富的信息;其次在組合類別空間上給出用戶瀏覽圖，并定義了描述用戶動(dòng)態(tài)偏好的五種語義關(guān)系及鏈接和偏好距離，更好地描述了用戶偏好的動(dòng)態(tài)變化過程及變化程度;然后在用戶瀏覽圖上根據(jù)用戶瀏覽序列、跳轉(zhuǎn)語義關(guān)系、鏈接距離和偏好距離、跳轉(zhuǎn)次數(shù)及時(shí)序等信息，利用隨機(jī)游走得到組合類別空間上的用戶類別偏好，表示為具有實(shí)際含義的用戶偏好向量;最后根據(jù)用戶的類別偏好計(jì)算用戶間相似性，并完成基于用戶的協(xié)同過濾推薦。通過在真實(shí)數(shù)據(jù)集上進(jìn)行大量實(shí)驗(yàn)結(jié)果表明，本文方法效果優(yōu)于傳統(tǒng)基于類別推薦的方法。

1?組合類別空間

項(xiàng)目類別（類型）屬性是非常重要且不同于其他屬性的附加信息，同一類別的項(xiàng)目往往具有相似內(nèi)容。如，對(duì)于電影推薦系統(tǒng)，電影類型（動(dòng)作、浪漫、喜劇等）一般是由專家來進(jìn)行分配、指定的，同一類型的電影中能找到一定的相似性，用戶可以通過電影類型猜測(cè)電影的故事情節(jié)、氛圍、場(chǎng)景等，決定是否去觀看電影，因此可以吸引具有相同偏好的用戶。此外，一個(gè)電影能屬于多個(gè)類型，每個(gè)項(xiàng)目類別表示一個(gè)特定的主題。也即項(xiàng)目和類別是一對(duì)多的關(guān)系，對(duì)應(yīng)關(guān)系復(fù)雜，關(guān)系不易被挖掘。為了更好地組織項(xiàng)目類別信息，提出組合類別空間，它把項(xiàng)目所屬的多個(gè)類別看成一個(gè)類別集合，將項(xiàng)目和類別間一對(duì)多的關(guān)系通過哈斯圖表示結(jié)構(gòu)映射成一對(duì)一的關(guān)系，它能表示項(xiàng)目類別間上下、同層、跳躍關(guān)系，豐富了項(xiàng)目的信息密度，使項(xiàng)目和類別間的關(guān)系更容易表示，更容易挖掘用戶偏好。

2?組合類別空間上的五種語義關(guān)系及距離

每個(gè)用戶的消費(fèi)行為表示成在組合類別空間的節(jié)點(diǎn)上的跳轉(zhuǎn)序列，它暗含著用戶的動(dòng)態(tài)偏好，為了挖掘用戶的偏好變化，從跳轉(zhuǎn)節(jié)點(diǎn)間的語義關(guān)系及語義距離兩個(gè)角度描述用戶的偏好變化劇烈程度。

2.1?五種語義關(guān)系

定義2?瀏覽行為語義關(guān)系。

2.2?語義距離

五種關(guān)系定性描述了用戶行為在CCS上的跳轉(zhuǎn)，及它表示的興趣偏好變化。要利用這種跳轉(zhuǎn)行為建模用戶的動(dòng)態(tài)偏好，還必須能定量衡量它。

在組合類別空間上用戶瀏覽行為的跳轉(zhuǎn)可由兩個(gè)方面衡量：1）組合類別在哈斯圖上跳轉(zhuǎn)的實(shí)際物理距離大小，可用在哈斯圖上的層次距離表示，層次跨度小的兩個(gè)組合類別表示用戶興趣變化小，興趣越趨于穩(wěn)定，距離越小;2）組合類別包含基本類別元素的差別，可從包含基本類別元素的個(gè)數(shù)和公共元素的個(gè)數(shù)兩個(gè)角度考慮。包含基本類別元素越多、公共基本類別越少的組合類別表示的興趣變化越大，距離也應(yīng)大。

基于上述的考慮，分別定義鏈接距離和偏好距離表示組合類別間的距離大小。

定義3?鏈接距離。

它表示兩個(gè)組合類別在組合空間哈斯圖上實(shí)際的物理距離大小。

兩個(gè)組合類別包含的元素越多，相同的基本類別數(shù)目越少，則鏈接距離越大，說明組合類別復(fù)雜、差異度大;

每個(gè)類型組包含類別數(shù)少，相同類別數(shù)越多，則鏈接距離越小，表明類型組合自身簡(jiǎn)單且差異小;

如果兩個(gè)組合類別完全一致時(shí)，鏈接距離為0。

按照偏好距離的定義可知，當(dāng)用戶跳轉(zhuǎn)的組合類別沒有變化時(shí)，也即興趣穩(wěn)定時(shí)，偏好距離最小為0。其次為興趣縮小的情況，接著是興趣擴(kuò)張的情況，而興趣不可比較時(shí)，用戶偏好變化最為劇烈，偏好距離最大。

3?基于隨機(jī)游走的個(gè)性化類別偏好建模

為了更好地對(duì)用戶組合類別偏好進(jìn)行建模，首先定義了用戶瀏覽圖，融合了語義關(guān)系、鏈接與偏好距離、跳轉(zhuǎn)次數(shù)、評(píng)分、時(shí)序等信息;利用PageRank對(duì)用戶組合類別的偏好進(jìn)行建模，并優(yōu)化求解得到用戶對(duì)組合類別的個(gè)性化偏好。

3.1?用戶瀏覽圖

根據(jù)用戶歷史瀏覽行為來定義用戶瀏覽圖，并建模用戶個(gè)性化組合類別偏好。

迭代優(yōu)化得到用戶對(duì)所有組合類別的評(píng)分向量π=（π1，π2，…，πn）T，也即用戶的個(gè)性化類別偏好向量，它是一種低維的用戶偏好向量的表示，但相對(duì)于潛語義類模型，個(gè)性化類別偏好向量的每個(gè)維度都具有很清楚的含義。

4?項(xiàng)目推薦

得到用戶對(duì)組合類別的個(gè)性化偏好矢量，利用余弦相似性度量用戶間相似性（式（9）），并選擇與用戶ui最相似的k個(gè)用戶來預(yù)測(cè)評(píng)分，如式（10）所示。

本文所提出的基于組合類別空間的隨機(jī)游走推薦算法具體如算法1所示。

算法1?基于組合類別空間的隨機(jī)游走推薦算法。

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

5.1?實(shí)驗(yàn)數(shù)據(jù)及評(píng)估標(biāo)準(zhǔn)

實(shí)驗(yàn)中采用MovieLens提供的1M數(shù)據(jù)集，包括6040個(gè)用戶，3952個(gè)電影項(xiàng)目，共1000209條有效評(píng)論，時(shí)間區(qū)間從2000年05月26日至2003年03月01日，數(shù)據(jù)稀疏度為95.8%。項(xiàng)目共包含18種基本電影類型，如表1所示，共組成301種組合類型，組合類別中最多包含6個(gè)基本類型。實(shí)驗(yàn)過程中，隨機(jī)抽取80%的數(shù)據(jù)作為訓(xùn)練集，余下的20%作為測(cè)試集，采用5折交叉驗(yàn)證。

對(duì)結(jié)果的評(píng)估，用平均絕對(duì)誤差（Mean Absolute Error， MAE）和均方根誤差（Root Mean Squared Error， RMSE）作為評(píng)分預(yù)測(cè)的評(píng)價(jià)標(biāo)準(zhǔn)，采用準(zhǔn)確率、召回率和F1-score以及AUC（Area Under Curve）曲線來評(píng)估Top-N推薦結(jié)果。

5.2?對(duì)比方法

為了評(píng)估本文提出的基于類別組合空間的隨機(jī)游走推薦算法（CCSRank）的有效性，將其與以下相關(guān)算法進(jìn)行了對(duì)比：1）基于用戶的協(xié)同過濾（User-based Collarative Filtering， UCF）[16]：采用余弦相似性計(jì)算用戶間相似性。

2）基于用戶在類別中關(guān)聯(lián)的協(xié)同過濾（User-Based collarative filtering by Genre Correlations， UBGC）[11]：計(jì)算電影類型的關(guān)聯(lián)度，根據(jù)電影的類型及類型間的關(guān)聯(lián)對(duì)電影分類，最后根據(jù)用戶偏好類型及電影分類完成推薦。

3）類別層次潛在因子模型（Category Hierarchy Latent Factor model， CHLF）[15]： 建立項(xiàng)目的類別層次并建立用戶和項(xiàng)目隱語義模型進(jìn)行推薦。

4）使用類別的分類模型（using genre to classification model， GENC）[10]：計(jì)算項(xiàng)目類別間的關(guān)聯(lián)度，完成項(xiàng)目分類與推薦任務(wù)。

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

近鄰選取是UCF提高推薦性能的關(guān)鍵。圖2給出了MAE和RMSE隨近鄰數(shù)的變化情況。從圖2可知，隨著近鄰數(shù)增加MAE和RMSE迅速下降后緩慢增加，近鄰數(shù)為40和60時(shí)MAE和RMSE達(dá)到最小，在后續(xù)實(shí)驗(yàn)中近鄰選取最佳值。

實(shí)驗(yàn)中首先計(jì)算了各方法的指標(biāo)如表2所示。從表2可知，CCSRank和CHLF的全部四項(xiàng)性能都好于UCF、UBGC和GENC，特別是F1-score提高了6～9個(gè)百分點(diǎn);而且CCSRank的性能要好于CHLF，F(xiàn)1-score提高了10%，CCSRank模型更加穩(wěn)定。

這主要是因?yàn)镃CSRank和CHLF都很好地利用和組織了項(xiàng)目類別信息，而組合類別空間比層次類別結(jié)構(gòu)的信息更為豐富。UBGC和GENC的效果相當(dāng)，且好于UCF是由于UBGC和GENC都利用了項(xiàng)目類型間的關(guān)聯(lián)，因此效果好于UCF，但項(xiàng)目類型關(guān)聯(lián)所包含信息不如層次類別和組合類別空間豐富，因此效果差于CHLF和CCSRank。

圖3對(duì)比了各種方法的MAE和RMSE。從圖3可知，CCSRank效果優(yōu)于UCF、UBGC和GENC，其中MAE減小了20%～30%，但卻不如CHLF。這主要是因?yàn)镃CSRank雖利用了信息更為豐富的組合類別空間，但在推薦過程中簡(jiǎn)單地利用個(gè)性化類別編號(hào)進(jìn)行了相似性計(jì)算，而CHLF則采用層次類別結(jié)構(gòu)建立了用戶和項(xiàng)目的隱語義模型。CCSRank雖在評(píng)分預(yù)測(cè)的效果上差于CHLF，但CCSRank提出的組合類別空間結(jié)構(gòu)，實(shí)現(xiàn)項(xiàng)目和類別一對(duì)一的映射關(guān)系，且比CHLF的層次結(jié)構(gòu)更方便地描述用戶瀏覽行為地跳轉(zhuǎn)過程，對(duì)于用戶喜歡項(xiàng)目的排序比CHLF更準(zhǔn)確，因此CCSRank更適合于排序推薦。

6?結(jié)語

本文提出基于組合類別空間的隨機(jī)游走推薦算法可緩解數(shù)據(jù)稀疏、解決冷啟動(dòng)問題，提高推薦系統(tǒng)性能。該方法在組合類別空間中記錄用戶瀏覽行為，學(xué)習(xí)用戶類別偏好特征，最終完成推薦。 首先定義了組合類別空間，它是一種高效哈斯圖結(jié)構(gòu);其次定義了五種語義關(guān)系和兩種偏好距離，在組合類別空間上定性和定量度量用戶行為序列和動(dòng)態(tài)偏好;接著提出基于隨機(jī)游走的個(gè)性化類別偏好模型，充分利用了語義關(guān)系、語義距離、用戶行為跳轉(zhuǎn)、跳轉(zhuǎn)次數(shù)、時(shí)序、評(píng)分等各種信息，學(xué)習(xí)得到一種低維的個(gè)性化用戶類別偏好表示，且每個(gè)維度的含義清楚;最后以此對(duì)用戶進(jìn)行個(gè)性化推薦。實(shí)驗(yàn)結(jié)果說明該方法能提高推薦性能，特別是項(xiàng)目排序推薦。

參考文獻(xiàn)（References）

[1] ZHANG Z， ZENG D D， ABBASI A， et al. A random walk model for item recommendation in social tagging systems[J]. ACM Transactions on Management Information Systems， 2013， 4（2）： 8.

[2] FENG S， CAO J. Improving group recommendations via detecting comprehensive correlative information[J]. Multimedia Tools and Applications， 2017， 76（1）： 1355-1377.

[3] XU G， FU B， GU Y. Point-of-interest recommendations via a supervised random walk algorithm[J]. IEEE Intelligent Systems， 2016， 31（1）： 15-23.

[4] 劉夢(mèng)娟， 王巍， 李楊曦， 等. AttentionRank+： 一種基于關(guān)注關(guān)系與多用戶行為的圖推薦算法 [J]. 計(jì)算機(jī)學(xué)報(bào)， 2017， 40（3）： 634-648. （LIU M J， WANG W， LI Y X， et al. AttentionRank+： a graph-based recommendation combining attention relationship and multi-behaviors [J]. Chinese Journal of Computers， 2017， 40（3）： 634-648.）

[5] XIA F， CHEN Z， WANG W， et al. MVCWalker： random walk-based most valuable collaborators recommendation exploiting academic factors[J]. IEEE Transactions on Emerging Topics in Computing， 2014， 2（3）： 364-375.

[6] YAO W， HE J， HUANG G， et al. A graph-based model for context-aware recommendation using implicit feedback data[J]. World Wide Web， 2015， 18（5）： 1351-1371.

[7] WENG L T， XU Y， LI Y， et al. Exploiting item taxonomy for solving cold-start problem in recommendation making[C]// ICTAI 2008： Proceedings of the 20th IEEE International Conference on Tools with Artificial Intelligence. Piscataway， NJ： IEEE， 2008： 113-120.

[8] REN Y， LI G， ZHOU W. Modelling personal preferences for Top-N movie recommendations[J]. Web Intelligence and Agent Systems： an International Journal， 2014， 12（3）： 289-307.

[9] MANZATO M G. Discovering latent factors from movies genres for enhanced recommendation[C]// RecSys 2012： Proceedings of the Sixth ACM Conference on Recommender Systems. New York： ACM， 2012： 249-252.

[10] CHOI S M， KO S K， HAN Y S. A movie recommendation algorithm based on genre correlations[J]. Expert Systems with Applications， 2012， 39（9）： 8079-8085.

[11] HWANG T G， PARK C S， HONG J H， et al. An algorithm for movie classification and recommendation using genre correlation[J]. Multimedia Tools and Applications， 2016， 75（20）： 12843-12858.

[12] HU L， SUN A， LIU Y. Your neighbors affect your ratings： on geographical neighborhood influence to rating prediction[C]// SIGIR 2014： Proceedings of the 37th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM， 2014： 345-354.

[13] YANG J， SUN Z， BOZZON A， et al. Learning hierarchical feature influence for recommendation by recursive regularization[C]// RecSys 2016： Proceedings of the 10th ACM Conference on Recommender Systems. New York： ACM， 2016： 51-58.

[14] ZHANG Y， AHMED A， JOSIFOVSKI V， et al. Taxonomy discovery for personalized recommendation[C]// WSDM 2014： Proceedings of the 7th ACM International Conference on Web Search and Data Mining. New York： ACM， 2014： 243-252.

[15] SUN Z， GUO G， ZHANG J. Learning hierarchical category influence on both users and items for effective recommendation[C]// SAC 2017： Proceedings of the 32nd ACM SIGAPP Symposium on Applied Computing. New York： ACM， 2017： 1679-1684.

[16] SARWAR B， KARYPIS G， KONSTAN J， et al. Analysis of recommendation algorithms for e-commerce[C]// EC 2000： Proceedings of the 2nd ACM Conference on Electronic Commerce. New York： ACM， 2000： 158-167.