基于屬性向量協(xié)同過濾推薦算法并行化

溫占考，易秀雙，劉 勇，李 婕，王興偉

(東北大學(xué) 計算機科學(xué)與工程學(xué)院，遼寧 沈陽 110819)

0 引 言

協(xié)同過濾[1]推薦算法可大致分為基于評分預(yù)測和基于排序預(yù)測兩類?；谠u分預(yù)測的協(xié)同過濾是最為熟知的，原理是根據(jù)相似用戶(物品)評分，預(yù)測目標用戶(物品)評分，將評分排序后得到一個Top-N推薦列表。基于用戶的協(xié)同過濾算法[2]利用用戶對所有物品評分行為相似性來查找相似用戶，而基于物品的協(xié)同過濾算法[3]利用所有用戶對物品評分行為相似性來查找相似物品，但兩者都是利用相似用戶或者物品的歷史評分來進行預(yù)測。

現(xiàn)存算法面臨幾個核心問題。①僅考慮用戶對物品評分而忽略物品屬性信息[2,3]，不能準確表示用戶的興趣，使得準確率受到很大的限制；②物品數(shù)量眾多，用戶-物品評分矩陣稀疏程度太高及維度過高[4]，用戶之間共同評分的物品很少，對物品全排列的時間復(fù)雜度變高，不能準確找到相似用戶，影響推薦準確率；③大數(shù)據(jù)背景下，難以及時響應(yīng)用戶請求。

Yi Cai等從全新的方向出發(fā)，提出基于典型性協(xié)同過濾算法，極大提升了預(yù)測準確率[5]；李改等運用基于K近鄰的屬性—特征映射的算法得到新用戶和新項目的特征向量來解決冷啟動問題[6]；文獻[7]基于排序預(yù)測的推薦算法直接預(yù)測用戶對物品的排序；CLiMF算法對二元相關(guān)數(shù)據(jù)進行建模并且優(yōu)化了二元相關(guān)性的度量[8]； VSRank用向量空間模型來表示兩個用戶間的興趣，且通過考慮每對用戶興趣的相對重要性對預(yù)測做出了進一步提升[9]；ListCF用所有物品全排列概率分布直接預(yù)測，降低了基于排序預(yù)測算法計算復(fù)雜度[10]。

本文提出Hadoop環(huán)境下基于屬性向量典型性的協(xié)同過濾推薦算法，綜合考慮物品屬性信息及用戶對物品歷史評分等多維度信息，計算用戶間的相似度，依據(jù)相似用戶的評分行為預(yù)測目標用戶對物品排列概率，將算法在Hadoop環(huán)境下并行化來及時響應(yīng)用戶請求。

1 算法的數(shù)據(jù)處理

(1)

(2)

從上述典型性計算結(jié)果中，可得到物品j在物品類Sk中的典型性Wj,k。通過式(3)，可得出用戶i對物品類Sk的評分，其中n代表物品類Sk中物品的個數(shù)，由此可得到用戶-物品類的評分矩陣

(3)

將物品屬性信息等進行綜合考慮來對物品進行聚類及評分更能體現(xiàn)用戶興趣，提高相似用戶查找準確率。且將矩陣維度從物品數(shù)目的無限維降低到物品類的常數(shù)級別，極大減少查找相似用戶的計算復(fù)雜度。

2 基于屬性向量典型性推薦算法描述

主要描述算法相似用戶查找和物品排序預(yù)測兩部分。根據(jù)物品類全排列的概率分布查找相似用戶；根據(jù)相似用戶對目標用戶未評分物品全排列概率分布，預(yù)測目標用戶對未評分物品排序[12,13]。

2.1 相似用戶查找

Plackett-Luce是用來描述排列概率分布的模型。對于某種排列，如果評分越高對應(yīng)排序越靠前，相應(yīng)的概率也就應(yīng)該越大。用I來表示物品集合，物品所有全排列集合用ΩI(π1，π2，…，πi，…πn)來表示。對于一個排列πi(i1，i2，…ij…，in)，ij表示排列第j個位置上是物品ij，與排列對應(yīng)物品ij的評分為{ri1，ri2，……，rin}，排列π的概率計算如式(4)所示，其中η(rik)表示物品ik被選擇的概率，為遞增的正函數(shù)，本文選取η(rik)=erik

(4)

用Kullback-Leibler(KL)散度實現(xiàn)用戶之間的相似性度量，可描述兩個概率分布差異。兩個用戶u和v之間的KL散度可由式(5)得到

(5)

(6)

2.2 物品排序預(yù)測

接下來是對目標用戶u未評分的物品R(r1,r2,……,rs)進行預(yù)測排序，將排序靠前的k個物品推薦給用戶u。

如果將s個物品進行全排列，計算復(fù)雜度是s!。Top-K概率模型只關(guān)注排列的前K個位置物品，可以將計算復(fù)雜度降到s!/(s-k)![12]。Top-K物品排列集合表示為G(g1，g2，……，gn)，其中g(shù)j(i1，i2，……，ik)代表前K個位置是(i1，i2，…,ik)這些物品所有排列，Top-K排列概率用式(7)計算

(7)

相對熵損失函數(shù)可以調(diào)優(yōu)概率分布間的距離[13]，使u對R全排列的概率分布PRu與Nu對R的全排列概率分布PRNu盡可能接近，用式(8)構(gòu)造出相應(yīng)的優(yōu)化函數(shù)，其中R’代表目標用戶u未評分，但相似用戶v評分的物品集合，PR’v代表是物品集合的概率分布，G’代表對R’的Top-K全排列

(8)

(9)

對每個相似用戶v∈Nu，都可對物品集合R’中物品Top-K全排列G’的概率分布進行求解，可得到PRu。根據(jù)概率的大小對物品進行排序后進行推薦。

3 在Hadoop環(huán)境下并行化算法

隨著數(shù)據(jù)量的爆炸式增長，為及時響應(yīng)用戶請求，本文將算法在Hadoop環(huán)境下進行并行化。算法并行化包含數(shù)據(jù)處理并行化、相似用戶查找并行化、推薦并行化3部分。

數(shù)據(jù)處理并行化設(shè)計兩個MapReduce任務(wù)：①物品屬性向量典型性計算任務(wù)，Map()函數(shù)將物品歸入到所屬類中，Reduce()函數(shù)根據(jù)物品屬性向量和類原型向量計算典型性，將結(jié)果保存在HDFS中；②矩陣計算任務(wù)，Map()函數(shù)讀取用戶對每個物品的評分，Reduce()函數(shù)根據(jù)Map()函數(shù)中間結(jié)果以及任務(wù)①中輸出在HDFS中的數(shù)據(jù)，計算每個用戶每個物品類的評分。數(shù)據(jù)流為圖1。

圖1 數(shù)據(jù)處理并行化數(shù)據(jù)流

相似用戶查找并行化設(shè)計兩個MapReduce任務(wù)：①計算物品類的概率分布，Map()函數(shù)用于找出每個用戶與目標用戶共同評分過得物品類，Reduce()函數(shù)計算每個用戶對物品類概率分布。②Map()函數(shù)利用任務(wù)①在HDFS中保存的中間結(jié)果計算目標用戶與每個用戶之間的相似性，Reduce()函數(shù)將相似度排序后，輸出Top-K個相似用戶到本地。數(shù)據(jù)流如圖2所示。

推薦并行化設(shè)計兩個MapReduce任務(wù)：①計算未評分物品概率分布，與相似用戶查找中第一個MapReduce相似；②根據(jù)目標函數(shù)迭代求取目標用戶對未評分物品的概率分布，Map()函數(shù)是進行一次迭代，Reduce()函數(shù)則用于判斷是否達到迭代結(jié)束條件。這部分任務(wù)間邏輯關(guān)系與相似用戶查找并行化的數(shù)據(jù)流圖基本相同就不再重復(fù)。

4 仿真實驗與性能分析

4.1 實驗步驟

首先給出算法實現(xiàn)流程圖3所示。

具體實驗過程分為以下3個部分：

(1)根據(jù)算法實現(xiàn)流程圖將算法在串行環(huán)境和并行環(huán)境下分別實現(xiàn)。

(2)對于串行環(huán)境，用MovieLens-1M數(shù)據(jù)集，測試本算法和其它算法在不同K值的時耗；然后測試本算法和基于評分預(yù)測算法，CoFiRank算法，Listwise算法準確率，并進行相應(yīng)的分析。

(3)在并行環(huán)境下，用MovieLens-lastest數(shù)據(jù)集，對目標用戶隨機選取不為0的評分數(shù)據(jù)的10%作為測試集，其它部分作為訓(xùn)練集，進行加速比實驗分析。

4.2 算法效率評價

由于數(shù)據(jù)預(yù)處理矩陣轉(zhuǎn)換可以離線進行，且在線進行部分查找相似用戶所占時間比重遠高于推薦所占用時間，而Top-K中K的選擇影響推薦準確率。因此在不考慮矩陣轉(zhuǎn)換耗時情況下，分析本文算法和Listwise算法各種Top-K排列時，查找相似用戶效率，得到結(jié)果見表1。

從表1可看出，算法在相同k值情況下，由于物品類數(shù)量m遠小于物品數(shù)量n，計算耗時遠低于Listwise算法，說明本文算法在查找相似用戶時效率更高。

4.3 預(yù)測準確率評價

(10)

與本文算法進行比較的是基于評分預(yù)測算法，CoFiRank算法和Listwise算法。由于求所有物品全排列概率分布計算復(fù)雜度過高，用Top-K概率模型只考慮排列的前K個位置來降低計算復(fù)雜度。選擇k=3，因為當k>3時，算法準確率提升有限，計算復(fù)雜度卻指數(shù)增長。通過仿真實現(xiàn)，得到實驗結(jié)果如圖4所示。

圖4 各個算法準確率

通過以上實驗可以發(fā)現(xiàn)，將NDCG作為評價指標，面向排序預(yù)測的算法準確率明顯優(yōu)于面向評分預(yù)測的算法準確率。本文算法相對最先進的面向評分預(yù)測的算法相比，準確率提升了11.9%，比CoFiRank算法提升了6.1%，比面向排序預(yù)測Listwise算法提升了3.6%。在用戶-物品評分矩陣非常稀疏時，相似用戶查找的準確率受到限制，從而使得預(yù)測準確率也遇到瓶頸，本文通過矩陣轉(zhuǎn)換較好解決了這個問題，因此本算法有更高的預(yù)測準確率。

4.4 并行化加速比分析

本文對所實現(xiàn)的算法進行了并行化設(shè)計，評價算法并行化優(yōu)劣可通過算法加速比進行。通過實驗，得到本文算法加速比與理想情況下的算法加速比，實驗結(jié)果如圖5所示。

圖5 算法加速比

從圖3中可以看出，在只有兩臺計算機的集群中由于其中一臺是進行任務(wù)調(diào)度，且每個任務(wù)的中間結(jié)果都輸出到本地，再交給下一個任務(wù)，此時加速比是小于1；后續(xù)加速比的增長越來越慢，是由于在最后預(yù)測排序階段，通過梯度下降算法迭代進行，每次迭代結(jié)果都輸出到本地，再從本地讀取進行下一次迭代，這樣隨著集群規(guī)模擴大，需將中間結(jié)果合并耗費時間也就越來越長，使得加速比增長受到限制。

5 結(jié)束語

本文利用物品屬性向量典型性將用戶-物品評分矩陣轉(zhuǎn)換為用戶-物品類矩陣，更能體現(xiàn)用戶的興趣，然后用物品類全排列的概率分布代替物品全排列概率分布，解決了數(shù)據(jù)稀疏性對相似用戶準確查找及物品維度過高造成的計算復(fù)雜度過高問題。通過仿真實驗說明本文算法在時間效率和推薦排序準確率均有明顯提升，同時在Hadoop環(huán)境下對算法進行并行化，根據(jù)加速比實驗結(jié)果，可以表明本算法有較好的可擴展性及應(yīng)用價值。

[1]Meng-Hui Chen,Chin-Hung Teng,Pei-Chann Chang.Appl-ying artificial immune systems to collaborative filtering for movie recommendation[J].Advanced Engineering Informatics,2015,29(4):830-839.

[2]RONG Huigui,HUO Shengxu,HU Chunhua,et al.User similarity-based collaborative filtering recommendation algorithm[J].Journal on Communications,2014,35(2):16-24(in Chinese).[榮輝桂,火生旭,胡春華,等.基于用戶相似度的協(xié)同過濾推薦算法[J].通信學(xué)報,2014,35(2):16-24.]

[3]Baltrunas L,Ricci F.Experimental evaluation of context-dependent collaborative filtering using item splitting[J].User Modeling and User-Adapted Interaction,2014,24(1):7-34.

[4]YANG Yang,XIANG Yang,XIONG Lei.Collaborative filtering and recommendation algorithm based on matrix factorization and user nearest neighbor model[J].Journal of Computer Applications,2012,32(2):395-398(in Chinese).[楊陽,向陽,熊磊.基于矩陣分解與用戶近鄰模型的協(xié)同過濾推薦算法[J].計算機應(yīng)用,2012,32(2):395-398.]

[5]Yi Cai,Ho-fung Leung,Qing Li.Typicality-based collaborative filtering recommendation[J].IEEE Transactions on Knowledge and Data Engineering,2014,26(3):766-779.

[6]LI Gai,LI Lei.A new algorithm of cold-start in a collaborative filtering system[J].Journal of Shandong University(Engineering Science),2012,42(2):11-17(in Chinese).[李改,李磊.一種解決協(xié)同過濾系統(tǒng)冷啟動問題的新算法[J].山東大學(xué)學(xué)報(工學(xué)版),2012,42(2):11-17.]

[7]ZHU Yuxiao,LYU Linyuan.Evaluation metrics for recommender systems[J].Journal of University of Electronic Scie-nce and Technology of China,2012,41(2):163-175(in Chinese).[朱郁筱,呂琳媛.推薦系統(tǒng)評價指標綜述[J].電子科技大學(xué)學(xué)報,2012,41(2):163-175.]

[8]Shi Y,Karatzoglou A,Baltrunas L,et al.Climf:Learning to maximize reciprocal rank with collaborative less-is-more filtering[C]//The 6th ACM Conference on Recommender Systems.New York:ACM,2012:139-146.

[9]Wang S,Sun J,Gao BJ,et al.VSRank:A novel framework for ranking-based collaborative filtering[J].ACM Trans Intelligent Systems Technolgy,2014,5(3):51.

[10]Shanshan Huang,Shuaiqiang Wang,Tie-Yan Liu.Listwise collaborative filtering[C]//International ACM SIGIR Conference on Research & Development in Information Retrieval.New York:ACM,2015:343-352.

[11]CHEN Kehan,HAN Panpan,WU Jian.User clustering based social network recommendation[J].Chinese Journal of Computers,2013,36(2):349-359(in Chinese).[陳克寒,韓盼盼,吳健.基于用戶聚類的異構(gòu)社交網(wǎng)絡(luò)推薦算法[J].計算機學(xué)報,2013,36(2):349-359.]

[12]HUANG Zhenhua,ZHANG Jiawen,TIAN Chunqi,et al.Survey on learning-to-rank based recommendation algorithms[J].Journal of Software,2016,27(3):691-713(in Chinese).[黃震華,張佳雯,田春岐,等.基于排序?qū)W習(xí)的推薦算法研究綜述[J].軟件學(xué)報,2016,27(3):691-713.]

[13]Mohammad Abbassia,Maryam Ashrafib,Ebrahim Sharifi Tashnizic.Selecting balanced portfolios of R&D projects with interdependencies:A cross-entropy based methodology[J].Technovation,2014,34(1):54-63.