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

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

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

0 引 言

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

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

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

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

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

(1)

(2)

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

(3)

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

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

主要描述算法相似用戶查找和物品排序預(yù)測兩部分。根據(jù)物品類全排列的概率分布查找相似用戶；根據(jù)相似用戶對目標(biāo)用戶未評分物品全排列概率分布，預(yù)測目標(biāo)用戶對未評分物品排序[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ù)測

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

如果將s個物品進(jìn)行全排列，計算復(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)

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

(8)

(9)

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

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

隨著數(shù)據(jù)量的爆炸式增長，為及時響應(yīng)用戶請求，本文將算法在Hadoop環(huán)境下進(jì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ù)用于找出每個用戶與目標(biāo)用戶共同評分過得物品類，Reduce()函數(shù)計算每個用戶對物品類概率分布。②Map()函數(shù)利用任務(wù)①在HDFS中保存的中間結(jié)果計算目標(biāo)用戶與每個用戶之間的相似性，Reduce()函數(shù)將相似度排序后，輸出Top-K個相似用戶到本地。數(shù)據(jù)流如圖2所示。

推薦并行化設(shè)計兩個MapReduce任務(wù)：①計算未評分物品概率分布，與相似用戶查找中第一個MapReduce相似；②根據(jù)目標(biāo)函數(shù)迭代求取目標(biāo)用戶對未評分物品的概率分布，Map()函數(shù)是進(jìn)行一次迭代，Reduce()函數(shù)則用于判斷是否達(dá)到迭代結(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算法準(zhǔn)確率，并進(jìn)行相應(yīng)的分析。

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

4.2 算法效率評價

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

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

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

(10)

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

圖4 各個算法準(zhǔn)確率

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

4.4 并行化加速比分析

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

圖5 算法加速比

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

5 結(jié)束語

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