羅云芳 李 力

1(廣西職業(yè)技術(shù)學(xué)院機電與信息工程學(xué)院 廣西 南寧 530226)2(電子科技大學(xué)計算機科學(xué)與工程學(xué)院 四川 成都 610054)

0 引 言

近年來，大數(shù)據(jù)已發(fā)展成為許多工業(yè)和科學(xué)領(lǐng)域、電子商務(wù)和電子政務(wù)的數(shù)據(jù)分析和服務(wù)新技術(shù)。大數(shù)據(jù)這個術(shù)語通常指的是數(shù)據(jù)集，其容量超出了傳統(tǒng)工具在可接受的計算時間內(nèi)捕獲、管理和處理數(shù)據(jù)的能力。由于網(wǎng)絡(luò)上可用信息的爆炸性增長，用戶面臨著壓倒性選擇的關(guān)鍵挑戰(zhàn)，出現(xiàn)信息過載現(xiàn)象。因此，大數(shù)據(jù)技術(shù)的挑戰(zhàn)在于探索和分析海量數(shù)據(jù)，以提取特定目標所需的相關(guān)信息[1-2]，為搜索服務(wù)和推薦系統(tǒng)提供更廣泛、實時和精準的信息，尤其是面向用戶和組織的個性化服務(wù)。

推薦系統(tǒng)已經(jīng)成為解決上述問題的強大工具，該技術(shù)的目標是根據(jù)用戶過去的喜好和興趣為用戶提供個性化建議[3-4]。目前，隨著用戶、項目和生成的其他信息數(shù)量的快速增長，海量的數(shù)據(jù)給推薦系統(tǒng)帶來了諸多挑戰(zhàn)[5]。這些挑戰(zhàn)啟發(fā)了許多研究者提出了幾種方法來提高大數(shù)據(jù)背景下推薦系統(tǒng)的性能。Hsieh等[6]提出了一個基于關(guān)鍵詞的推薦系統(tǒng)，利用從用戶和項目文本數(shù)據(jù)中提取的關(guān)鍵詞提高該系統(tǒng)使用Apache Hadoop處理大規(guī)模數(shù)據(jù)集的性能，緩解冷啟動問題。Papadakis等[7]設(shè)計了一個基于綜合坐標的推薦系統(tǒng)SCOR，通過使用vivaldi綜合坐標算法將用戶和項目放置在多維歐氏空間中，利用項目和用戶之間的歐氏距離來預(yù)測未知偏好，從而提高預(yù)測精度。Hammou等[8]提出了一種大數(shù)據(jù)量的近似并行推薦算法，該算法是基于Apache Spark開發(fā)的，有效地提升處理大規(guī)模數(shù)據(jù)的效率。Tran等[9]提出了一種規(guī)則化的多嵌入推薦模型RME，該模型采用加權(quán)矩陣分解，結(jié)合用戶嵌入、共同不喜好項嵌入和共同喜歡項嵌入，用以獲得較高的預(yù)測精度。Costa等[10]提出了一種基于集成的協(xié)同訓(xùn)練方法ECoRec，它采用兩種或兩種以上的推薦方法來提高系統(tǒng)的性能，提高預(yù)測精度。

盡管當(dāng)前一些推薦技術(shù)可以很好地應(yīng)對大數(shù)據(jù)和推薦系統(tǒng)所面臨的各種挑戰(zhàn)，但是，執(zhí)行訓(xùn)練任務(wù)的計算成本可能會對大規(guī)模數(shù)據(jù)造成計算上的限制，對于海量數(shù)據(jù)需要考慮計算效率。除此之外，數(shù)據(jù)稀疏性是面臨的另一個關(guān)鍵問題，它對預(yù)測質(zhì)量有負面影響。針對上述問題，本文提出一種基于數(shù)據(jù)分割策略和新的學(xué)習(xí)過程的分布式推薦模型，然后提出基于矩陣分解和隨機森林的混合推薦算法，通過加速訓(xùn)練任務(wù)縮短計算時間，解決數(shù)據(jù)稀疏性問題，提高預(yù)測質(zhì)量，有效地處理大規(guī)模數(shù)據(jù)。

1 相關(guān)知識

1.1 隨機森林

隨機森林算法是在2001年由Breiman提出的一種新的機器學(xué)習(xí)模型[11]，該模型將隨機子空間方法與引導(dǎo)聚集算法結(jié)合在一起，通過反復(fù)二分數(shù)據(jù)進行分類或回歸，從而降低計算量。其原理是采用隨機的方式建立一個森林，在森林里存在很多決策樹，然后利用多棵決策樹對樣本數(shù)據(jù)進行訓(xùn)練、分類和預(yù)測。RF算法對大部分數(shù)據(jù)具有很好的分類效果，模型訓(xùn)練速度快，不易出現(xiàn)過擬合現(xiàn)象，具有一定抗噪聲能力，同時預(yù)測準確率高。

隨機森林的構(gòu)建過程如下：

(1) 原始訓(xùn)練集有N個樣本數(shù)，使用Bootstraping方法從中隨機有放回地采樣n(n≤N)個樣本，共進行K次采樣，生成K個訓(xùn)練集。

(2) 對K個訓(xùn)練集，分別訓(xùn)練K個決策樹模型。

(3) 對于單個決策樹模型，假設(shè)訓(xùn)練樣本具有m個特征數(shù)，那么每次分裂時根據(jù)信息增益、信息增益比或者基尼指數(shù)，選擇最好的特征進行分裂。

(4) 每棵樹都采用這種形式分裂，直到該節(jié)點的所有訓(xùn)練樣例都屬于同一類。

(5) 每棵決策樹的分裂過程中不需要剪枝，以最大限度生長。

(6) 將生成的多棵決策樹組成隨機森林，用隨機森林分類器對新的數(shù)據(jù)進行分類與回歸。對于分類問題，按照多棵樹分類器投票決定最終分類結(jié)果；對于回歸問題，由多棵樹預(yù)測值的均值決定最終預(yù)測結(jié)果。

1.2 矩陣分解

矩陣分解[12]是一種將矩陣簡化為其組成部分的方法，這種方法可以簡化更復(fù)雜的矩陣運算。矩陣分解是降維技術(shù)，屬于潛在因子模型。由于在可伸縮性和推薦系統(tǒng)方面的卓越性能，它受了極大的歡迎。

矩陣因式分解的主要思想是，項目和用戶可以通過從評分矩陣中推斷出的少量潛在因素來表示。具體來說，給定用戶項評級矩陣R和潛在因子的數(shù)量C

R≈EW

(1)

(2)

式中：Eu和Wi是用戶u和項目i的潛在向量。

對于訓(xùn)練任務(wù)，常用方法是最小化目標函數(shù)：

(3)

式中：ru,i是用戶項目評分矩陣R中的已知偏好；λm是正則化參數(shù)。

2 基于MF和RF的推薦方法

大數(shù)據(jù)已經(jīng)引起了學(xué)術(shù)界和行業(yè)的廣泛關(guān)注，研究學(xué)者開發(fā)了一些分布式計算框架。由于MapReduce對于跨多個步驟共享數(shù)據(jù)的應(yīng)用程序效率低下，最近出現(xiàn)了Apache Spark[13]，克服了Hadoop的弱點。Spark中的關(guān)鍵部分被稱為彈性分布式數(shù)據(jù)集(RDD)，這是元素的不可變和分區(qū)集合，可以通過分布式方式進行處理。RDD設(shè)計為容錯的，即在節(jié)點發(fā)生故障的情況下，Spark能夠通過沿襲信息重建丟失的RDD分區(qū)。它運行速度比Hadoop MapReduce快100倍，而磁盤上的速度快10倍。

推薦系統(tǒng)是一種主動給用戶推送信息的推薦技術(shù)，通過分析用戶過往的行為信息與興趣特點，向用戶推薦其感興趣的個性化決策支持和信息服務(wù)。大數(shù)據(jù)環(huán)境下的個性化推薦問題可以定義為：假定U={u1,u2,…,uM}和I={i1,i2,…,iN}是用戶和項目的集合，其中M和N為系統(tǒng)中用戶和項目的數(shù)量。每個用戶u提供的偏好可以表示為評級向量Ru=(ru,i1,ru,i2,…,ru,iN)，ru,i表示用戶u對項目i的評級。使用用戶項目評分矩陣R表示所有用戶對項目的偏好。由于每個用戶u∈U僅對非常少的項目進行評分，因此ru,i對評分矩陣R中的大多數(shù)對(u,i)是未知的，這是數(shù)據(jù)稀疏的主要原因。

針對大數(shù)據(jù)提出一種分布式推薦方法，由于稀疏性、預(yù)測質(zhì)量和計算時間幾個因素可能會影響推薦系統(tǒng)的性能，因此，本文解決方案的目標是解決數(shù)據(jù)稀疏性問題，提高預(yù)測質(zhì)量，減少計算時間并有效處理大規(guī)模數(shù)據(jù)。提出的分布式推薦方法是基于Apache Spark設(shè)計的，它基于三個步驟：(1) 數(shù)據(jù)分區(qū)，目標是將數(shù)據(jù)劃分為最佳數(shù)量的分區(qū)；(2) 通過使用一種新的學(xué)習(xí)過程來訓(xùn)練模型，以提高推薦質(zhì)量，同時減少計算時間；(3) 預(yù)測偏好。圖1給出分布式推薦方法的流程。

圖1 分布式推薦方法的流程

2.1 數(shù)據(jù)分區(qū)

數(shù)據(jù)在節(jié)點間的分布對于并行和分布式計算的效率至關(guān)重要。該步驟的主要目標是將訓(xùn)練數(shù)據(jù)RDDtrain劃分為一個最優(yōu)的分區(qū)數(shù)目，從而使所提出的模型能夠加速并行和分布式訓(xùn)練任務(wù)的執(zhí)行。

設(shè)Np為可能分區(qū)數(shù)的集合，Time(RDDtrain，np)為根據(jù)參數(shù)np執(zhí)行訓(xùn)練任務(wù)所需的計算時間的函數(shù)。問題可以定義如下：

(4)

2.2 模型訓(xùn)練

該模型可以表示為有向無環(huán)圖。每個節(jié)點代表一個接收輸入數(shù)據(jù)并產(chǎn)生輸出的函數(shù)。每個節(jié)點的輸出用作下一個節(jié)點的輸入，依此類推。為了說明步驟的順序，圖2給出了本文模型的總體結(jié)構(gòu)。

圖2 本文模型的總體結(jié)構(gòu)

設(shè)pr為用戶表示評分r∈[rmin,rmax]的概率，相關(guān)概率集的定義如下：

P=(pr(1),pr(2),…,pr(k))

P∩(pr(k+1),pr(k),…,pr(0))=?

(5)

式中：k表示用于反映用戶意見的概率數(shù)；將等級r(1)表示為偏好的概率高于r(2)的概率，依此類推；符號O表示系統(tǒng)中可能的額定值數(shù)目。

如圖2所示，該模型將每個輸入實例X∈R|X|映射到相關(guān)表示A∈R|A|，表示為：

Au=T(X=Ru)=(ru,i1,ru,i2,…,ru,i|l|)

Ai=T(X=Ri)=(ru1,i,ru2,i,…,ru|U|,i)

(6)

式中：X表示用戶u的等級Ru的集合，或為項目i提供的等級Ri的集合。函數(shù)T(·)在pru,i∈P為真時，僅選擇每個等級ru,i∈X。產(chǎn)生的Au和Ai根據(jù)每個用戶u和項目i聚合如下：

(7)

式中：Vu∈R概括了用戶u的評級行為；Vi∈R近似于用戶對一個項目i的偏好。式(7)的主要目標是反映用戶對項目的樂觀、中立或悲觀偏好。

由于大數(shù)據(jù)的不同挑戰(zhàn)以及評級矩陣的稀疏性，必須采用更復(fù)雜的機制來有效地處理大量數(shù)據(jù)，解決稀疏性問題。因此，對于每個Ru，模型僅啟用來自用戶u的單位Vu和由u評定的每個項目的單位Vi的連接，其中ru,i∈Ru且ru,i≠0。然后，將問題分解為一組子問題，每個子問題基于一組連續(xù)的目標函數(shù)進行優(yōu)化。因為系統(tǒng)中的用戶是獨立的，該模型將問題分解為|U|優(yōu)化子問題，表示為：

(8)

(9)

根據(jù)z的偏導(dǎo)數(shù)?z/?γu=0，每個用戶u的啟用單元之間的交互定義如下：

(10)

式中：參數(shù)γu∈R表示最優(yōu)值，它控制相對于用戶u的單元之間的交互。

為了考慮每個用戶u的個性化行為受到的影響。通過最小化損失函數(shù)直接估計參數(shù)βu：

(11)

在函數(shù)g相對于參數(shù)βu的偏導(dǎo)數(shù)?g/?βu=0時，βu∈R最優(yōu)值表示為：

(12)

式中：參數(shù)βu的主要思想是根據(jù)用戶的行為來調(diào)整預(yù)期的偏好。為了提供更適當(dāng)?shù)念A(yù)測，必須根據(jù)最佳參數(shù)γu、βu和過去的偏好來更新每個用戶u(Vu)的估計個性化行為。因此新目標函數(shù)可以表示為：

(13)

同理，由?f/?ωu=0計算每個參數(shù)ωu：

(14)

(15)

(16)

因此，通過考慮目標之間的權(quán)衡來執(zhí)行估計過程。在數(shù)學(xué)上，此任務(wù)的公式如下：

(17)

式中：O表示可能值的集合來估計B(x)；min(Y(1))和max(Y(1))表示Y(1)的最小值和最大值。

(18)

(19)

(20)

用于改善用戶意見的估計值D(x)可以表示為：

(21)

式中：q(1)(x)、q(2)(x)是兩個目標函數(shù)。q(1)(x)、q(2)(x)可以表示為：

q(x)=[q(1)(x),q(2)(x)]

(22)

基于式(4)-式(22)，模型訓(xùn)練步驟如算法1所示。

算法1分布式推薦模型的訓(xùn)練步驟

輸出：估計參數(shù)的RDD*。

2.利用式(5)確定相關(guān)概率集P={pr(1),pr(2),…,pr(k)}；

3.為每個用戶u和項目i提供偏好設(shè)置Ru和用戶意見Ri；

4.for ?u和?ido

利用式(6)將Ru、Ri表示為Au和Ai的形式；

利用式(7)近似用戶u的評級行為Vu以及項目i的用戶意見Vi；

end for

5.for?subproblemu和?subproblemido

end for

6.返回RDD*：

2.3 預(yù)測步驟

用戶u對項目i的預(yù)測評分的計算方式如下：

(23)

2.4 矩陣分解和隨機森林

利用矩陣分解和隨機森林模型來提高推薦質(zhì)量，基本思想是將訓(xùn)練集中的每個已知評級ru,i表示為特征和標簽。然后，將評級預(yù)測任務(wù)作為回歸問題解決。

設(shè)C={(xj,yj),j=1,2,…,|C|}是訓(xùn)練數(shù)據(jù)集，|C|是非零等級的用戶項目等級R的數(shù)量，xj∈Rβ+1和yj∈R分別表示實體j的特征和標簽。

令β為矩陣分解模型的數(shù)量，主要目標是訓(xùn)練β矩陣分解模型，然后利用學(xué)習(xí)到的模型為訓(xùn)練集中的每個偏好ru,i生成一個表示：

L(ru,i)=(xj,yj)

(24)

yj=ru,i

評級預(yù)測任務(wù)被視為回歸問題，通過使用帶有預(yù)定義標簽的生成表示來訓(xùn)練機器學(xué)習(xí)模型來解決此問題。隨機森林是一種有監(jiān)督的學(xué)習(xí)方法，廣泛用于回歸和分類問題。因此采用隨機森林來執(zhí)行評級預(yù)測任務(wù)，在訓(xùn)練了隨機森林之后，采用學(xué)習(xí)模型來預(yù)測未知的偏好。

3 實 驗

所有的實驗運行在16 Intel Xeon CPU和64 GB RAM平臺。實驗是在由兩個節(jié)點組成的群集上進行的：一個主節(jié)點和一個從節(jié)點。每個節(jié)點都運行Ubuntu 16.04。同時，在相同條件下將本文方法與APRA[8]、FRAIPA[13]和CMII[14]幾種推薦方法在Yelp、Movielens 10和Movielens 20M三個真實數(shù)據(jù)集[8]上的測試結(jié)果進行對比。這些方法是使用Apache Spark 2.1.0框架實現(xiàn)的。APRA是一種并行的近似推薦方法，采用隨機抽樣技術(shù)和特殊的學(xué)習(xí)過程來加速訓(xùn)練任務(wù)，用于處理大規(guī)模數(shù)據(jù)；FRAIPA將每個用戶的評分行為和用戶對每個項目的意見視為一組概率，然后利用估計的概率來預(yù)測偏好；CMII是一種基于混淆矩陣的推薦方法，將基于內(nèi)容的聚類與協(xié)同過濾相結(jié)合，使用加權(quán)策略來預(yù)測偏好。

由于在實驗環(huán)節(jié)中許多參數(shù)需要調(diào)整才能獲得最佳的預(yù)測結(jié)果，對本文推薦算法做如下參數(shù)設(shè)置：分區(qū)數(shù)設(shè)置為Np=[8,16,24,32]，相關(guān)概率的數(shù)量k=6，O=[-0.3,0.3]，間隔為0.1。矩陣分解模型的數(shù)量參數(shù)β=3，每個分解模型的等級設(shè)置為10，學(xué)習(xí)率為0.05，執(zhí)行訓(xùn)練任務(wù)的迭代次數(shù)為15。隨機森林決策樹數(shù)目設(shè)置為5。

3.1 實驗數(shù)據(jù)集和評價標準

MovieLens 10M和MovieLens 20M是一個真實世界的數(shù)據(jù)集，由明尼蘇達大學(xué)的GroupLens研究小組收集，包含多個用戶對多部電影的評級數(shù)據(jù)，及電影元數(shù)據(jù)信息和用戶屬性信息。MovieLens 10M由71 567個用戶對10 000部電影，進行的1 000萬個評級和100 000個電影標簽。MovieLens 20M電影推薦數(shù)據(jù)集包含138 493位用戶對27 278部電影的20 000 000項電影的評分和465 564個電影標簽。Yelp數(shù)據(jù)集由6 685 900個交互組成，由1 637 138個用戶表示，用于10個大都市地區(qū)的192 609個企業(yè)。由于原始數(shù)據(jù)是高度稀疏的，需要進一步處理數(shù)據(jù)集，保留至少30個偏好的項目和用戶。最終數(shù)據(jù)集包含大約15 139個用戶、27 307個項目和1 210 783個偏好。在測試過程中，根據(jù)現(xiàn)有研究工作中采用的方法對每個數(shù)據(jù)集進行拆分。將數(shù)據(jù)集隨機分為兩部分，其中80%的數(shù)據(jù)用作訓(xùn)練集，其余20%用作測試集。

為了評估推薦算法的性能，采用了均方根誤差(RMSE)和均值絕對誤差(MAE)兩個指標用于測量預(yù)測精度：

(25)

(26)

3.2 結(jié)果分析

對于本文方法，數(shù)據(jù)分區(qū)是一個重要步驟，通過確定分區(qū)數(shù)量來加速訓(xùn)練步驟。選擇最佳的分區(qū)數(shù)量對于改善模型的性能至關(guān)重要。圖3顯示了MovieLens 10M和MovieLens 20M數(shù)據(jù)集上不同np值的計算時間變化。可以看出，計算時間對組數(shù)np的選擇很敏感。對于MovieLens 10M，當(dāng)np=16時，模型獲得最佳性能；對于MovieLens 20M，當(dāng)np=24時，模型可以大大減少計算時間。

圖3 分區(qū)數(shù)量np對運行時間的影響

為了有效地評估本文模型的性能，將在三個數(shù)據(jù)集上的測試結(jié)果與其他方法進行對比。表1給出了在MovieLens 10M、MovieLens 20M和Yelp數(shù)據(jù)集上的實驗結(jié)果，可以清楚地看到，本文模型在預(yù)測質(zhì)量方面優(yōu)于其他方法。

表1 不同推薦算法在三個數(shù)據(jù)集上的測試結(jié)果

4 結(jié) 語

本文針對大數(shù)據(jù)環(huán)境下的個性化推薦，提出一種分布式預(yù)測模型。它是基于Apache Spark設(shè)計的，可解決傳統(tǒng)環(huán)境下的推薦算法效率低、計算成本高的問題。該模型采用數(shù)據(jù)分區(qū)策略用于加速大數(shù)據(jù)處理；基于較復(fù)雜的過程來表征用戶的評分行為和項目的用戶意見；將優(yōu)化問題劃分為一組獨立子問題，每個子問題可以基于一系列連續(xù)的目標函數(shù)進行求解，并且對這些目標函數(shù)采用矩陣分解和隨機森林技術(shù)，以并行和分布式的方式有效學(xué)習(xí)參數(shù)，克服了數(shù)據(jù)稀疏性問題。實驗結(jié)果表明，本文算法在預(yù)測誤差指標上明顯優(yōu)于其他推薦方法。