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

樊瑋 謝聰 肖春景 曹淑燕

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

關鍵詞：偏好相似度;梯度下降;隨機游走;協同過濾;推薦算法

中圖分類號：TP301.6

文獻標志碼：A

文章編號：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?引言

協同過濾是目前推薦系統中最成功的推薦算法，它認為具有相似偏好的用戶應該喜歡相似的項目，因此它的核心是為用戶尋找最相似近鄰。它利用用戶與項目的交互信息，將用戶項目評分看成向量，利用余弦、皮爾遜相關系數等相似性度量來發現近鄰，通過近鄰對項目評分預測目標用戶的喜好。但是一方面計算相似性時的評分向量維度和系統中的項目數一致，向量維度較高;另一方面由于用戶自身特點，將產生很多相同評分，由此得到的評分向量信息冗余且不全面，它的性能在數據稀疏或冷啟動的情況下受到嚴重制約。

當游走步數趨于無窮大時，基于圖的隨機游走算法能夠返回圖中節點重要性的排序。它能從全局挖掘用戶/項目關系，已被廣泛應用到推薦過程中緩解數據稀疏問題[1-6]。由于項目類別（類型）作為附加信息時，屬性值相對穩定、與項目內容相關性強，同時一個項目往往與多個類別相關等特性，項目類別作為重要附加信息引入推薦系統能夠有效緩解數據稀疏、解決冷啟動問題。

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

二是挖掘用戶偏好和項目類別間的關聯，如：Ren等[8]利用項目類別信息，建立用戶動態偏好模型，但是計算量較大;Manzato等[9]分解用戶類型矩陣得到類別的隱向量解決冷啟動問題。

三是計算項目類別間的關聯，根據用戶偏好類別完成項目推薦[10-11]，但此類方法要求系統必須輸入用戶喜好類別。

最后一類是利用矩陣分解等潛語義模型根據項目類別的扁平或層次結構，建立用戶和項目k維向量表示的潛語義模型，來完成項目推薦的過程[12-14]。Sun等[15]根據類別層次建立用戶和項目隱語義模型并以線性復雜度自動學習不同類別的權值。但它們僅用到項目類別的扁平結構或上下層次關系，并不能應用同層次類別間的關系;而且用戶和項目的k維向量的維度往往是隨機設定的，并沒有明確的語義含義。

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

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

1?組合類別空間

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

2?組合類別空間上的五種語義關系及距離

每個用戶的消費行為表示成在組合類別空間的節點上的跳轉序列，它暗含著用戶的動態偏好，為了挖掘用戶的偏好變化，從跳轉節點間的語義關系及語義距離兩個角度描述用戶的偏好變化劇烈程度。

2.1?五種語義關系

定義2?瀏覽行為語義關系。

2.2?語義距離

五種關系定性描述了用戶行為在CCS上的跳轉，及它表示的興趣偏好變化。要利用這種跳轉行為建模用戶的動態偏好，還必須能定量衡量它。

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

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

定義3?鏈接距離。

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

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

每個類型組包含類別數少，相同類別數越多，則鏈接距離越小，表明類型組合自身簡單且差異小;

如果兩個組合類別完全一致時，鏈接距離為0。

按照偏好距離的定義可知，當用戶跳轉的組合類別沒有變化時，也即興趣穩定時，偏好距離最小為0。其次為興趣縮小的情況，接著是興趣擴張的情況，而興趣不可比較時，用戶偏好變化最為劇烈，偏好距離最大。

3?基于隨機游走的個性化類別偏好建模

為了更好地對用戶組合類別偏好進行建模，首先定義了用戶瀏覽圖，融合了語義關系、鏈接與偏好距離、跳轉次數、評分、時序等信息;利用PageRank對用戶組合類別的偏好進行建模，并優化求解得到用戶對組合類別的個性化偏好。

3.1?用戶瀏覽圖

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

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

4?項目推薦

得到用戶對組合類別的個性化偏好矢量，利用余弦相似性度量用戶間相似性（式（9）），并選擇與用戶ui最相似的k個用戶來預測評分，如式（10）所示。

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

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

5?實驗結果及分析

5.1?實驗數據及評估標準

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

對結果的評估，用平均絕對誤差（Mean Absolute Error， MAE）和均方根誤差（Root Mean Squared Error， RMSE）作為評分預測的評價標準，采用準確率、召回率和F1-score以及AUC（Area Under Curve）曲線來評估Top-N推薦結果。

5.2?對比方法

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

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

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

4）使用類別的分類模型（using genre to classification model， GENC）[10]：計算項目類別間的關聯度，完成項目分類與推薦任務。

5.3?實驗結果及分析

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

實驗中首先計算了各方法的指標如表2所示。從表2可知，CCSRank和CHLF的全部四項性能都好于UCF、UBGC和GENC，特別是F1-score提高了6～9個百分點;而且CCSRank的性能要好于CHLF，F1-score提高了10%，CCSRank模型更加穩定。

這主要是因為CCSRank和CHLF都很好地利用和組織了項目類別信息，而組合類別空間比層次類別結構的信息更為豐富。UBGC和GENC的效果相當，且好于UCF是由于UBGC和GENC都利用了項目類型間的關聯，因此效果好于UCF，但項目類型關聯所包含信息不如層次類別和組合類別空間豐富，因此效果差于CHLF和CCSRank。

圖3對比了各種方法的MAE和RMSE。從圖3可知，CCSRank效果優于UCF、UBGC和GENC，其中MAE減小了20%～30%，但卻不如CHLF。這主要是因為CCSRank雖利用了信息更為豐富的組合類別空間，但在推薦過程中簡單地利用個性化類別編號進行了相似性計算，而CHLF則采用層次類別結構建立了用戶和項目的隱語義模型。CCSRank雖在評分預測的效果上差于CHLF，但CCSRank提出的組合類別空間結構，實現項目和類別一對一的映射關系，且比CHLF的層次結構更方便地描述用戶瀏覽行為地跳轉過程，對于用戶喜歡項目的排序比CHLF更準確，因此CCSRank更適合于排序推薦。

6?結語

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

參考文獻（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] 劉夢娟， 王巍， 李楊曦， 等. AttentionRank+： 一種基于關注關系與多用戶行為的圖推薦算法 [J]. 計算機學報， 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.