溫占考，易秀雙，田申申，李 婕，王興偉

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

基于邊界矩陣低階近似和近鄰模型的協(xié)同過濾算法

溫占考，易秀雙*，田申申，李 婕，王興偉

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

為解決矩陣分解應(yīng)用到協(xié)同過濾算法的局限性和準(zhǔn)確率等問題，提出基于邊界矩陣低階近似(BMA)和近鄰模型的協(xié)同過濾算法(BMAN-CF)來提高物品評(píng)分預(yù)測的準(zhǔn)確率。首先，引入BMA的矩陣分解算法，挖掘子矩陣的隱含特征信息，提高近鄰集合查找的準(zhǔn)確率；然后，根據(jù)傳統(tǒng)基于用戶和基于物品的協(xié)同過濾算法分別預(yù)測出目標(biāo)用戶對(duì)目標(biāo)物品的評(píng)分，利用平衡因子和控制因子動(dòng)態(tài)平衡兩個(gè)預(yù)測結(jié)果，得到目標(biāo)用戶對(duì)物品的評(píng)分；最后，利用MapReduce計(jì)算框架的特點(diǎn)，對(duì)數(shù)據(jù)進(jìn)行分塊，將該算法在Hadoop環(huán)境下并行化。實(shí)驗(yàn)結(jié)果表明，BMAN-CF比其他矩陣分解算法有更高的評(píng)分預(yù)測準(zhǔn)確率，且加速比實(shí)驗(yàn)驗(yàn)證了該算法具有較好的可擴(kuò)展性。

協(xié)同過濾；矩陣分解；邊界矩陣；近鄰模型；Hadoop

0 引言

推薦系統(tǒng)是根據(jù)用戶現(xiàn)在的興趣，預(yù)測用戶將來可能感興趣的物品，并推薦給用戶[1]。根據(jù)推薦算法不同，可以分為：基于內(nèi)容的推薦(Content-based Recommendation)算法、協(xié)同過濾和混合推薦[2]。協(xié)同過濾算法主要是利用用戶-物品評(píng)分矩陣分析用戶興趣，在用戶群中找到與目標(biāo)用戶興趣相似的用戶，綜合這些用戶對(duì)某一物品的評(píng)分，形成目標(biāo)用戶對(duì)該物品喜好程度的預(yù)測。協(xié)同過濾推薦算法主要的階段是近鄰集合的查找，其準(zhǔn)確率直接影響到推薦的準(zhǔn)確率。在實(shí)際的電子商務(wù)系統(tǒng)和視頻網(wǎng)站系統(tǒng)中(比如Amazon、NetFlix等)，用戶和物品種類的數(shù)量都非常巨大，這對(duì)于協(xié)同過濾算法準(zhǔn)確率和效率都是非常大的挑戰(zhàn)。

目前協(xié)同過濾算法主要面臨以下幾點(diǎn)問題：1)數(shù)據(jù)稀疏性是制約協(xié)同過濾推薦算法準(zhǔn)確率的最主要問題。用戶對(duì)物品評(píng)分的數(shù)量較少，造成用戶-物品評(píng)分矩陣非常稀疏。在這種情況下，用戶之間共同評(píng)分的物品數(shù)量少，計(jì)算出的最近鄰居用戶集合質(zhì)量不高，會(huì)造成推薦的準(zhǔn)確率低。2)算法的可擴(kuò)展性是制約推薦系統(tǒng)實(shí)施的重要因素。協(xié)同過濾算法面對(duì)日益增加的用戶維度和物品維度時(shí)，用戶間相似性計(jì)算的耗費(fèi)也很大，這樣會(huì)導(dǎo)致算法遇到嚴(yán)重的擴(kuò)展性問題。3)大數(shù)據(jù)背景下，系統(tǒng)難以及時(shí)響應(yīng)用戶的請(qǐng)求，影響用戶的實(shí)時(shí)性體驗(yàn)。

為了解決上述問題，提出基于邊界矩陣低階近似(Bounded Matrix low rank Approximation, BMA) 和近鄰模型的協(xié)同過濾并行化算法(Collaborative Filtering algorithm based on BMA and Nearest neighbor model, BMAN-CF)。BMAN-CF是根據(jù)實(shí)際推薦系統(tǒng)的評(píng)分范圍，將評(píng)分矩陣R分解為子矩陣P和Q，降低矩陣維度和稀疏性；挖掘子矩陣中P、Q中的隱含特征，提高近鄰集合查找準(zhǔn)確率；綜合考慮用戶和物品對(duì)預(yù)測結(jié)果的影響，利用平衡因子動(dòng)態(tài)平衡兩種協(xié)同過濾算法的預(yù)測結(jié)果，得到最終的預(yù)測結(jié)果。

1 相關(guān)工作

協(xié)同過濾推薦算法主要分為基于內(nèi)存的協(xié)同過濾算法和基于模型的協(xié)同過濾算法兩類。

基于內(nèi)存的協(xié)同過濾算法分為4個(gè)過程：1)構(gòu)建用戶-物品評(píng)分矩陣；2)計(jì)算用戶(物品)間相似度；3)查找近鄰集合；4)預(yù)測用戶對(duì)物品的評(píng)分。文獻(xiàn)[3]利用典型性相關(guān)概念對(duì)物品和用戶進(jìn)行聚類降低數(shù)據(jù)稀疏性，提高了預(yù)測準(zhǔn)確率；文獻(xiàn)[4]將隱式數(shù)據(jù)作為用戶積極或者消極偏好的指示，與置信度聯(lián)系起來，訓(xùn)練出針對(duì)隱式反饋推薦的因子模型降低數(shù)據(jù)稀疏性；文獻(xiàn)[5]使用關(guān)聯(lián)檢索框架和相關(guān)的實(shí)際算法，根據(jù)用戶歷史反饋來探索用戶間的傳遞性關(guān)聯(lián)，用這種傳遞性關(guān)聯(lián)來描述用戶的興趣，從而解決數(shù)據(jù)稀疏性的問題。

基于模型的協(xié)同過濾算法利用用戶歷史行為，依托機(jī)器學(xué)習(xí)或數(shù)據(jù)挖掘算法來構(gòu)建用戶興趣模型，利用該模型為用戶推薦物品。此類算法構(gòu)建用戶興趣模型需要耗費(fèi)大量時(shí)間，但在建立用戶興趣模型后，數(shù)據(jù)規(guī)模明顯降低，所以可以離線訓(xùn)練模型，在線推薦及時(shí)響應(yīng)用戶請(qǐng)求?；谀Ｐ蛥f(xié)同過濾算法主要有隱語義模型、貝葉斯分類、神經(jīng)網(wǎng)絡(luò)等，隱語義模型由于高預(yù)測精度成為目前使用較為廣泛的技術(shù)。文獻(xiàn)[6]提出基于轉(zhuǎn)移學(xué)習(xí)的方法，利用變分期望最大化(Variational Expectation-Maximization, VEM)來學(xué)習(xí)出概率矩陣分解模型，利用多方面具有密集數(shù)據(jù)的輔助信息來解決數(shù)據(jù)稀疏問題，實(shí)驗(yàn)結(jié)果證明該算法在每個(gè)用戶只對(duì)一個(gè)物品評(píng)分時(shí)能得到最好的效果；文獻(xiàn)[7]提出用概率矩陣分解來填充用戶-物品評(píng)分矩陣，然后融合基于用戶的協(xié)同過濾和基于物品的協(xié)同過濾，但該算法以固定的權(quán)重融合基于用戶和基于項(xiàng)目預(yù)測的評(píng)分值，忽略了用戶和物品間的關(guān)系，并且不同的數(shù)據(jù)集權(quán)值分配差別很大；文獻(xiàn)[8]將流形正則化與矩陣分解結(jié)合構(gòu)成新模型，此模型有全局最優(yōu)和封閉形式的解決方法，使用交替迭代和不精確的內(nèi)部迭代來求解新模型，對(duì)矩陣分解算法效率和準(zhǔn)確率都有很大的提升。

2 BMAN-CF設(shè)計(jì)

非負(fù)矩陣分解(Nonnegative Matrix Factorization, NMF)是針對(duì)實(shí)際應(yīng)用中矩陣元素為負(fù)數(shù)沒有意義而提出的，但在推薦系統(tǒng)中用戶-物品評(píng)分矩陣元素不僅非負(fù)，還有固定的評(píng)分區(qū)間。矩陣分解算法在應(yīng)用到推薦系統(tǒng)時(shí)，將超過評(píng)分區(qū)間的預(yù)測評(píng)分設(shè)為區(qū)間的最大值，這會(huì)限制預(yù)測準(zhǔn)確率。而邊界矩陣低階近似根據(jù)實(shí)際推薦系統(tǒng)的評(píng)分區(qū)間確定近似矩陣PQ元素的一個(gè)上界和一個(gè)下界，而不僅僅在子矩陣P、Q的元素上保證非負(fù)[9]。

2.1 邊界矩陣分解

邊界矩陣分解主要是將原始用戶-物品評(píng)分矩陣Rn*m分解為兩個(gè)低階矩陣Pn*k和Qk*m，P和Q分別由列向量px和行向量qxT組成，接下來詳細(xì)介紹近似矩陣元素在評(píng)分區(qū)間的界定下，如何通過最小化目標(biāo)函數(shù)來求解列向量px和行向量qxT，即式(1):

(1)

s.t.T+pxqxT≤rmax,T+pxqxT≥rmin

假設(shè)px，已知根據(jù)px求解qxT。為了不失一般性，固定px求解qxT的情景同樣適用于固定qxT求解px,這樣就會(huì)產(chǎn)生兩種不同的更新策略：p1→q1T→…→pk→qkT和p1→…→pk→q1T→…→qkT。

根據(jù)文獻(xiàn)[10]對(duì)不同損失函數(shù)如何選擇相應(yīng)更新策略作出的說明，本文算法選擇交替更新px和qxT策略。本文算法利用塊坐標(biāo)下降算法來迭代求解問題，從塊坐標(biāo)下降算法性質(zhì)中可以發(fā)現(xiàn)，qxi、qxj∈qxT是相互獨(dú)立的，計(jì)算qxi并不影響元素qxi求解過程，qxT中其他元素的求解方法相同。qxi的計(jì)算過程如圖1所示。

圖1 矩陣元素qxi計(jì)算過程Fig. 1 Calculation process of qxi in matrix

?i=[1,m],?x=[1,k]

(2)

s.t.T(:,i)+pxqxi≤rmax，T(:,i)+pxqxi≥rmin

2[M(:,i)·*(R-T)(:,i)]Tpx

(3)

(4)

(5)

(6)

(7)

交替求解矩陣P和矩陣Q的各個(gè)向量，從而完成算法的一次迭代，當(dāng)?shù)Y(jié)果符合結(jié)束條件時(shí)停止迭代，最終得到分解后的矩陣P和矩陣Q，滿足R≈P×Q。

這里面的結(jié)束迭代條件有必要說明一下。由文獻(xiàn)[12]可知，迭代停止標(biāo)準(zhǔn)應(yīng)該是對(duì)于給定低階階數(shù)k，低階子矩陣P與Q的乘積應(yīng)該接近原有矩陣R的階數(shù)。所以可以定義停止迭代標(biāo)準(zhǔn)ε如式(8):

(8)

當(dāng)取浮點(diǎn)數(shù)精度為1E-5時(shí)，在精度范圍內(nèi)，迭代標(biāo)準(zhǔn)ε在成功迭代之后不再發(fā)生變化，此時(shí)迭代結(jié)束。

2.2 推薦列表計(jì)算

2.2.1 相似用戶查找

接下來充分挖掘子矩陣P、Q的隱含特征，矩陣P和Q的潛在特征可以描述為，矩陣Pn*k每行可以看成用戶對(duì)k個(gè)特征的喜愛程度，矩陣Qk*m每列可以看成物品對(duì)k個(gè)屬性的擁有程度。這樣通過對(duì)k個(gè)特征喜愛程度和k個(gè)屬性擁有程度的差異來計(jì)算用戶間和物品間的相似度。在矩陣P上利用挖掘出的隱語義特征來查找目標(biāo)用戶u的近鄰集合Nu，在矩陣Q上利用挖掘出的隱含義屬性查找目標(biāo)物品i的近鄰集合Ni。

2.2.2 物品評(píng)分預(yù)測

根據(jù)用戶u的近鄰集合Nu，利用傳統(tǒng)基于用戶的協(xié)同過濾算法和式(9)可以計(jì)算出目標(biāo)用戶u對(duì)物品i的評(píng)分Pu:

(9)

然后根據(jù)物品i的近鄰集合Ni，利用基于物品的協(xié)同過濾算法與式(10)可以計(jì)算出目標(biāo)用戶對(duì)物品i評(píng)分Pi:

(10)

如果只使用基于用戶的協(xié)同過濾或者只使用基于物品的協(xié)同過濾，容易忽略一些有用信息，所以本算法利用基于近鄰的協(xié)同過濾算法，即同時(shí)從用戶和物品兩個(gè)角度考慮，分別預(yù)測用戶u對(duì)物品i的評(píng)分，然后利用平衡因子來動(dòng)態(tài)平衡兩個(gè)預(yù)測評(píng)分。文獻(xiàn)[11]提出使用系數(shù)λ將兩個(gè)算法進(jìn)行整合如式(11):

Pu,i=λ×Pu+(1-λ)×Pi

(11)

但是系數(shù)λ沒有考慮用戶間和物品間的內(nèi)在相關(guān)性，為了進(jìn)一步提升預(yù)測準(zhǔn)確率，本算法采用平衡因子mu、mi和系數(shù)θ相結(jié)合的方法來動(dòng)態(tài)平衡兩種算法預(yù)測的評(píng)分[13]。mu、mi的計(jì)算方法為式(12):

(12)

由于多個(gè)近鄰用戶與目標(biāo)用戶之間的相似度不同，平衡因子mu的作用就是得到一個(gè)能夠用來代表用戶間的相似度權(quán)值，同理mi是代表物品間相似度權(quán)值。根據(jù)平衡因子mu、mi和系數(shù)λ組合出新的系數(shù)tu和ti，計(jì)算方法如式(13):

(13)

目標(biāo)用戶u對(duì)物品i的評(píng)分就可以轉(zhuǎn)換為式(14)，最終可以計(jì)算出用戶u對(duì)未評(píng)分物品集合Iu中所有物品的評(píng)分，評(píng)分排序后將評(píng)分最高的Top-N個(gè)物品推薦給目標(biāo)用戶u，這樣就完成了對(duì)用戶u推薦列表的計(jì)算。

Pu,i=tu×Pu+ti×Pi

(14)

3 BMAN-CF并行化

3.1 邊界矩陣分解并行化

BMA矩陣分解是利用塊坐標(biāo)下降迭代求解子矩陣，塊坐標(biāo)下降并行化思想應(yīng)用到邊界矩陣分解并行化就是，將初始化后的矩陣P和矩陣Q按照集群節(jié)點(diǎn)數(shù)分別進(jìn)行列分塊和行分塊，得到P={P1,P2,…,Ps}，Q={Q1,Q2,…,Qs}(s為集群節(jié)點(diǎn)個(gè)數(shù))；根據(jù)矩陣P和Q分塊結(jié)果，將R分解為這樣的形式：R=R1+R2+…+Rs，其中矩陣Ri依然是n行m列，這樣就完成了參數(shù)集合和相應(yīng)數(shù)據(jù)集的劃分；并行化執(zhí)行階段每個(gè)Map任務(wù)都讀入矩陣P和Q的一個(gè)分塊Pi、Qi以及相應(yīng)的數(shù)據(jù)集Ri，在Map函數(shù)中就可以利用2.1節(jié)的方法對(duì)Pi和Qi中的各個(gè)行列向量進(jìn)行迭代更新，直到收斂為止，Reduce階段的Reduce函數(shù)就是將各個(gè)Map的結(jié)果進(jìn)行整合輸出兩個(gè)更新后的矩陣P和Q。邊界矩陣分解MapReduce并行化流程如圖2所示。

圖2 邊界矩陣分解并行化數(shù)據(jù)流Fig. 2 Data flow of boundary matrix decomposition parallelization

3.2 推薦列表計(jì)算并行化

推薦列表并行化是在獲取到分解后的矩陣P和Q后，預(yù)測出用戶對(duì)未評(píng)分物品的評(píng)分，然后將評(píng)分最高Top-N個(gè)物品推薦給用戶。本并行化算法假設(shè)查找近鄰集合時(shí)用戶和物品都是獨(dú)立的，基于這個(gè)假設(shè)可以直接利用MapReduce的特性對(duì)算法進(jìn)行并行化。推薦列表計(jì)算MapReduce并行化的流程如圖3所示。進(jìn)行評(píng)分預(yù)測之前需要找到目標(biāo)用戶未評(píng)分的物品集合，結(jié)果保存以〈TargetUserID,list〈TargetItemID〉〉形式保存在Hadoop分布式文件系統(tǒng)(Hadoop Distributed File System, HDFS)文件中。下面介紹利用矩陣P和矩陣Q進(jìn)行評(píng)分預(yù)測得到Pu、Pi的數(shù)據(jù)流。

圖3 推薦列表計(jì)算并行化流程Fig. 3 Flow chart of recommended list calculation parallelization

3.2.1 利用矩陣P預(yù)測評(píng)分

MapReduce(MR1)中Setup函數(shù)是用來讀取第一步保存的文件，數(shù)據(jù)緩存格式為〈TargetUserID,list〈TargetItemID〉〉；Map階段輸入為矩陣P的一行，數(shù)據(jù)格式為〈UserID,list〈Feature,rate〉〉,通過map函數(shù)計(jì)算用戶間的相似度輸出為〈TargetUserID,〈UserID,Similarity〉〉；經(jīng)過Shuffle后相同的TargetUserID會(huì)被送到同一個(gè)Reduce中，Reduce階段reduce函數(shù)先將相似度排序，選取相似度最高的Top-k個(gè)相似用戶作為近鄰集合，根據(jù)式(4)預(yù)測目標(biāo)用戶對(duì)這些物品的評(píng)分，輸出為〈TargetUserID,list〈TargetItemID,Rate〉〉。

3.2.2 利用矩陣Q預(yù)測評(píng)分

MapReduce(MR2)與MR1Map和Shuffle操作類似，只是MR2中Map階段輸入的是矩陣Q的轉(zhuǎn)置的一行。Reduce階段reduce函數(shù)先將TargetItemID相同的數(shù)據(jù)聚集在一起，然后根據(jù)相似度大小為每個(gè)TargetItem選擇Top-k個(gè)物品作為近鄰集合，依次計(jì)算出目標(biāo)用戶對(duì)各個(gè)TargetItem的評(píng)分，輸出為〈TargetUserID,list〈TargetItemID,Rate〉〉。

3.2.3 最終評(píng)分預(yù)測

MapReduce(MR3)Map階段輸入為MR1和MR2的輸出〈TargetUserID,list〈TargetItemID,Rate〉〉，經(jīng)過Shuffle后TargetUserID相同的數(shù)據(jù)會(huì)被送到同一reduce函數(shù)中；在reduce函數(shù)中對(duì)每個(gè)TargetItemID都有兩個(gè)評(píng)分，利用式(14)來平衡兩個(gè)評(píng)分，得到對(duì)TargetItemID的最終評(píng)分，然后將評(píng)分最高的N個(gè)物品輸出〈TargetUserID,list〈TargetItemID,Rate〉〉。

4 實(shí)驗(yàn)結(jié)果與分析

串行實(shí)驗(yàn)是在單機(jī)上對(duì)BMAN-CF進(jìn)行實(shí)驗(yàn)，主要是在算法準(zhǔn)確率上基于近鄰模型的協(xié)同過濾(Nearest-based Model Collaborative Filtering, NMCF)算法、概率矩陣分解與近鄰模型相結(jié)合的協(xié)同過濾(Probabilistic Matrix Factorization and Nearest-based Model Collaborative Filtering, PNCF)算法、邊界矩陣低階近似(BMA)算法進(jìn)行比較分析。

并行實(shí)驗(yàn)是在Hadoop分布式集群上對(duì)并行化算法進(jìn)行實(shí)驗(yàn)，通過與串行實(shí)驗(yàn)運(yùn)行時(shí)間的比較，得到算法加速比，分析算法的可擴(kuò)展性。

4.1 算法串行實(shí)驗(yàn)與分析

4.1.1 MAE指標(biāo)下算法準(zhǔn)確率比較分析

由于矩陣分解的階數(shù)k可能會(huì)影響平均絕對(duì)誤差(Mean Absolute Error, MAE)指標(biāo)下的算法準(zhǔn)確率，所以首先測試k值對(duì)準(zhǔn)確率影響，選取合適的k值，實(shí)驗(yàn)時(shí)選取k值依次是10、20、30、40、50，實(shí)驗(yàn)數(shù)據(jù)集選取MovieLens-100k，圖4為不同k值下算法的準(zhǔn)確率。

圖4 不同k值下BMAN-CF的MAEFig. 4 MAE under BMAN-CF of different k values

從圖4縱坐標(biāo)軸的間隔來看，不同k值下算法MAE差異很小，但是在k為20時(shí)達(dá)到最小，所以接下來實(shí)驗(yàn)選取k=20。

本文算法在選取近鄰集合使用Top-k選擇策略，近鄰的個(gè)數(shù)對(duì)算法準(zhǔn)確率有很大影響，所以接下來是比較各算法在不同近鄰個(gè)數(shù)時(shí)MAE的大小，實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 不同近鄰個(gè)數(shù)下的MAEFig. 5 MAE under different number of neighbors

從圖5中可以看出，本文算法受近鄰個(gè)數(shù)影響較小，并且跟其他算法相比，本文算法MAE值始終最小，也就是本文算法準(zhǔn)確率最高。BMAN-CF的MAE相比NMCF至少提升了1.87個(gè)百分點(diǎn)，說明近鄰模型不能更好地為用戶興趣建模，導(dǎo)致近鄰集合查找不準(zhǔn)確，從而影響算法準(zhǔn)確率；相比PNCF，BMAN-CF的MAE至少提升了1.86個(gè)百分點(diǎn)，PNCF也是在概率矩陣分解后結(jié)合近鄰模型產(chǎn)生推薦，但本文算法在矩陣分解時(shí)限制了近似矩陣元素上、下界，因此比概率矩陣分解更適合推薦系統(tǒng)；BMAN-CF的MAE相比BMA至少提升了4.2個(gè)百分點(diǎn)，本文算法通過挖掘子矩陣的隱含信息，提高了算法預(yù)測精度。

4.1.2 RMSE指標(biāo)下算法準(zhǔn)確率比較分析

首先對(duì)比本文算法與改進(jìn)的奇異值分解(Singular Value Decomposition, SVD++)算法、帶偏置的奇異值分解(Biased Singular Value Decomposition, Bias-SVD)算法、隨機(jī)梯度下降(Stochastic Gradient Descent, SGD)算法、正則化交替最小二(Alternating Least Squares with Regularization, ALSWR)乘法在不同階數(shù)k下的均方根誤差(Root Mean Square Error, RMSE)結(jié)果，如表1所示。

從表1中可以看出，k值不同時(shí)，本文算法的RMSE比其他算法都要高一些。隨著k值增加雖然各個(gè)算法精度都有稍許的增加，但k值增大會(huì)增加矩陣分解階段計(jì)算時(shí)間復(fù)雜度，所以要選取適合的k值；本文算法的RMSE相比其他算法有一定程度的提升，是因?yàn)槠渌惴ǘ紝Ｗ⒂谧泳仃嘝和Q乘積與原始矩陣的近似程度，將更多的精力放在了如何優(yōu)化矩陣分解上，而沒有利用子矩陣隱含信息來進(jìn)行評(píng)分預(yù)測。

表1 不同階數(shù)k下不同算法的RMSETab. 1 RMSE of different algorithms under different k values

比較本文算法與其他算法在不同近鄰個(gè)數(shù)下的RMSE結(jié)果，進(jìn)行比較的算法有基于非負(fù)矩陣分解和近鄰模型結(jié)合的協(xié)同過濾(Nonnegative Matrix Factorization and Nearest neighbor model CF, NMFN-CF)算法、邊界矩陣分解BMA，實(shí)驗(yàn)結(jié)果如圖6所示。從圖6中可以看出，隨著近鄰個(gè)數(shù)的增加，各個(gè)算法的RMSE都有一定程度的下降，本文算法與BMA相比RMSE至少提升了2.5個(gè)百分點(diǎn)，與NMFN-CF相比RMSE至少提升了1.6個(gè)百分點(diǎn)。

圖6 不同算法在不同近鄰個(gè)數(shù)下的RMSEFig. 6 RMSE of different algorithms under different number of neighbors

本文算法結(jié)合邊界矩陣分解和基于近鄰模型的協(xié)同過濾算法，在矩陣分解階段利用實(shí)際推薦系統(tǒng)中的評(píng)分區(qū)間來限制子矩陣P和Q的元素取值范圍，從而使近似矩陣PQ更加接近于原始評(píng)分矩陣R，由于得到的子矩陣P和Q是低階子矩陣，且它們并不是稀疏矩陣，所以這樣可以很好地解決推薦系統(tǒng)數(shù)據(jù)稀疏所帶來的一系列問題。在查找近鄰集合時(shí)利用子矩陣P和Q中的隱含語義，提高了近鄰集合查找的準(zhǔn)確率，并且查找近鄰集合時(shí)，兩個(gè)子矩陣可以看作原始矩陣降維而來，所以可以降低計(jì)算復(fù)雜度，算法有較好的可擴(kuò)展性；預(yù)測用戶對(duì)物品的評(píng)分時(shí)，先利用基于用戶和基于物品兩種協(xié)同過濾算法分別預(yù)測用戶對(duì)物品的評(píng)分，再利用平衡因子和控制因子來動(dòng)態(tài)平衡兩種算法的預(yù)測評(píng)分，使最終預(yù)測評(píng)分更加準(zhǔn)確。

4.2 算法并行實(shí)驗(yàn)與分析

算法并行化實(shí)驗(yàn)環(huán)境是有7個(gè)節(jié)點(diǎn)的集群環(huán)境，數(shù)據(jù)集是MovieLens-latest，評(píng)價(jià)指標(biāo)是加速比。通過實(shí)驗(yàn)得到本文算法與理想情況下的加速比，實(shí)驗(yàn)結(jié)果如圖7所示。

從圖7中可以看出，隨著集群中節(jié)點(diǎn)數(shù)量的增加，并行化的優(yōu)勢(shì)漸漸體現(xiàn)出來，MapReduce任務(wù)由多個(gè)節(jié)點(diǎn)來執(zhí)行，所以加速比增速較大；但最后加速比增速緩慢，這是因?yàn)樽泳仃囯A數(shù)k沒發(fā)生變化，矩陣分解階段對(duì)參數(shù)劃分不能太小，否則文件讀取時(shí)間耗費(fèi)太多，所以只使用部分節(jié)點(diǎn)執(zhí)行MapReduce任務(wù)來迭代分解矩陣，造成加速比增速緩慢，從加速比實(shí)驗(yàn)結(jié)果可以看出，本文算法有較好的可擴(kuò)展性。

圖7 并行化算法加速比Fig. 7 Speedup of parallelized algorithm

5 結(jié)語

針對(duì)矩陣分解應(yīng)用到協(xié)同過濾算法中的局限性和準(zhǔn)確率等問題，本文提出基于邊界矩陣低階近似和近鄰模型的協(xié)同過濾算法(BMAN-CF)來提高物品評(píng)分預(yù)測的準(zhǔn)確率。該算法根據(jù)實(shí)際推薦系統(tǒng)的評(píng)分范圍界定近似矩陣及目標(biāo)函數(shù)，找出目標(biāo)用戶和目標(biāo)物品近鄰集合，并利用平衡因子和控制因子動(dòng)態(tài)平衡兩個(gè)預(yù)測結(jié)果，得到目標(biāo)用戶對(duì)物品的評(píng)分。在Hadoop環(huán)境下并行化實(shí)現(xiàn)了該算法。實(shí)驗(yàn)結(jié)果表明，所提算法能夠提高算法的預(yù)測準(zhǔn)確率，且并行環(huán)境下的加速比實(shí)驗(yàn)表明，所提算法具有較好的可擴(kuò)展性。由于并行化后的加速比受矩陣分解的階數(shù)k和并行化節(jié)點(diǎn)數(shù)量兩個(gè)參數(shù)的影響，接下來將進(jìn)一步研究如何選擇及優(yōu)化矩陣分解的階數(shù)k和并行化節(jié)點(diǎn)數(shù)量。

References)

[1] BARJASTEH I, FORSATI R, ROSS D, et al. Cold-start recommendation with provable guarantees: a decoupled approach [J]. IEEE Transactions on Knowledge & Data Engineering, 2016, 28(6):1462-1474.

[2] ADOMAVICIUS G, SANKARANARAYANAN R, SEN S, et al. Incorporating contextual information in recommender systems using a multidimensional approach [J]. ACM Transactions on Information Systems, 2005, 23(1): 103-145.

[3] CAI Y, LEUNG H F, LI Q, et al. TyCo: towards typicality-based collaborative filtering recommendation [J]. IEEE Transactions on Knowledge & Data Engineering, 2014, 2(3): 97-104.

[4] HU Y, KOREN Y, VOLINSKY C. Collaborative filtering for implicit feedback datasets [C]// Proceedings of the 8th IEEE International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2008: 263-272.

[5] HUANG Z, CHEN H, ZENG D. Applying associative retrieval techniques to alleviate the sparsity problem in collaborative filtering [J]. ACM Transactions on Information Systems, 2004, 22(1): 116-142.

[6] JING H, LIANG A C, LIN S D, et al. A transfer probabilistic collective factorization model to handle sparse data in collaborative filtering [C]// Proceedings of the 2014 IEEE International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2014: 250-259.

[7] WANG J, DE VRIES A P, REINDERS M J T. Unifying user-based and item-based collaborative filtering approaches by similarity fusion [C]// Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development In Information Retrieval. New York: ACM, 2006: 501-508.

[8] ZHANG Z, ZHAO K. Low-rank matrix approximation with manifold regularization [J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2013, 35(7): 1717-1729.

[9] KANNAN R, ISHTEVA M, PARK H. Bounded matrix low rank approximation [C]// Proceedings of the 2013 IEEE 13th International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2012: 319-328.

[10] KIM J, HE Y, PARK H. Algorithms for non-negative matrix and tensor factorization: a unified view based on block coordinate descent framework [J]. Journal of Global Optimization, 2014, 58(2): 285-319.

[11] MA H, KING I, LYU M R. Effective missing data prediction for collaborative filtering [C]// Proceedings of the 2007 International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM, 2007: 39-46.

[12] KANNAN R, ISHTEVA M, DRAKE B, et al. Bounded matrix low rank approximation [C]// Proceedings of the 8th IEEE International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2012: 319-328.

[13] 陳彥萍,王賽.基于用戶-項(xiàng)目的混合協(xié)同過濾算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2014,24(12):88-91.(CHEN Y P, WANG S. A hybrid collaborative filtering algorithm based on user-item [J]. Computer Technology and Development, 2014, 24(12): 88-91.)

This work is partially supported by the National Natural Science Foundation of China (61572123), the National Science Foundation for Distinguished Young Scholars in China (61225012, 71325002), the Liaoning Bai Qian Wan Talents Program (2013921068), the CERNET Innovation Project (NGII20160616).

WENZhankao, born in 1980, M. S., engineer. His research interests include next generation Internet, network security, big data analysis.

YIXiushuang, born in 1969, Ph. D., professor. His research interests include next generation Internet, network security, big data analysis.

TIANShenshen, born in 1992, M. S. candidate. His research interests include next generation Internet, big data analysis.

LIJie, born in 1981, Ph. D., associate professor. His research interests include next generation Internet, smart routing.

WANGXingwei, born in 1968, Ph. D., professor. His research interests include next generation Internet, smart routing, software defined network, cyberspace security, big data analysis.

Collaborativefilteringalgorithmbasedonboundedmatrixlowrankapproximationandnearestneighbormodel

WEN Zhankao, YI Xiushuang*, TIAN Shenshen, LI Jie, WANG Xingwei

(SchoolofComputerScienceandEngineering,NortheasternUniversity,ShenyangLiaoning110819,China)

To solve the limitation and accuracy of matrix decomposition in Collaborative Filtering (CF) algorithm, a Collaborative Filtering algorithm based on Bounded Matrix low rank Approximation (BMA) and Nearest neighbor model (BMAN-CF) was proposed to improve the accuracy of item scoring prediction. Firstly, the matrix factorization algorithm of BMA was introduced to extract the implicit feature information of sub-matrix and improve the accuracy of neighborhood set search. Then, the target users’ scores on target items were respectively predicted according to the traditional user-based and item-based collaborative filtering algorithms. And the equilibrium factor and control factor were used to dynamically balance the two prediction results, the target users’ scores of items were obtained. Finally, the data was partitioned, and the proposed algorithm was parallelized in Hadoop environment by using the characteristics of MapReduce computing framework. The experimental results show that, the BMAN-CF has higher rating prediction accuracy than other matrix factorization algorithms, and the speedup experiment shows that the proposed parallelized algorithm has better scalability.

collaborative filtering; matrix factorization; bounded matrix; nearest neighbor model; Hadoop

2017- 05- 04;

2017- 07- 10。

國家自然科學(xué)基金資助項(xiàng)目(61572123);國家杰出青年科學(xué)基金資助項(xiàng)目(61225012,71325002);遼寧省百千萬人才工程項(xiàng)目(2013921068);賽爾網(wǎng)絡(luò)下一代互聯(lián)網(wǎng)技術(shù)創(chuàng)新項(xiàng)目(NGII20160616)。

溫占考(1980—)，男，江西贛州人，工程師，碩士，主要研究方向:下一代互聯(lián)網(wǎng)、網(wǎng)絡(luò)安全、大數(shù)據(jù)分析； 易秀雙(1969—)，男，內(nèi)蒙古赤峰人，教授，博士，主要研究方向:下一代互聯(lián)網(wǎng)、網(wǎng)絡(luò)安全、大數(shù)據(jù)分析； 田申申(1992—)，男，遼寧沈陽人，碩士研究生，主要研究方向:下一代互聯(lián)網(wǎng)、大數(shù)據(jù)分析； 李婕(1981—)，女，遼寧沈陽人，副教授，博士，主要研究方向:下一代互聯(lián)網(wǎng)、智能路由； 王興偉(1968—)，男，內(nèi)蒙古包頭人，教授，博士，主要研究方向:下一代互聯(lián)網(wǎng)、智能路由、軟件定義網(wǎng)絡(luò)、網(wǎng)絡(luò)空間安全、大數(shù)據(jù)分析。

1001- 9081(2017)12- 3472- 05

10.11772/j.issn.1001- 9081.2017.12.3472

(*通信作者電子郵箱xsyi@mail.neu.edu.cn)

TP181；TP312

A