一種基于矩陣分解和隨機森林算法的推薦模型

羅云芳 李 力

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

0 引 言

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

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

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

1 相關知識

1.1 隨機森林

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

隨機森林的構建過程如下：

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

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

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

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

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

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

1.2 矩陣分解

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

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

R≈EW

(1)

(2)

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

對于訓練任務，常用方法是最小化目標函數：

(3)

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

2 基于MF和RF的推薦方法

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

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

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

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

2.1 數據分區

數據在節點間的分布對于并行和分布式計算的效率至關重要。該步驟的主要目標是將訓練數據RDDtrain劃分為一個最優的分區數目，從而使所提出的模型能夠加速并行和分布式訓練任務的執行。

設Np為可能分區數的集合，Time(RDDtrain，np)為根據參數np執行訓練任務所需的計算時間的函數。問題可以定義如下：

(4)

2.2 模型訓練

該模型可以表示為有向無環圖。每個節點代表一個接收輸入數據并產生輸出的函數。每個節點的輸出用作下一個節點的輸入，依此類推。為了說明步驟的順序，圖2給出了本文模型的總體結構。

圖2 本文模型的總體結構

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

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

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

(5)

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

如圖2所示，該模型將每個輸入實例X∈R|X|映射到相關表示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的集合。函數T(·)在pru,i∈P為真時，僅選擇每個等級ru,i∈X。產生的Au和Ai根據每個用戶u和項目i聚合如下：

(7)

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

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

(8)

(9)

根據z的偏導數?z/?γu=0，每個用戶u的啟用單元之間的交互定義如下：

(10)

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

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

(11)

在函數g相對于參數βu的偏導數?g/?βu=0時，βu∈R最優值表示為：

(12)

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

(13)

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

(14)

(15)

(16)

因此，通過考慮目標之間的權衡來執行估計過程。在數學上，此任務的公式如下：

(17)

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

(18)

(19)

(20)

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

(21)

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

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

(22)

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

算法1分布式推薦模型的訓練步驟

輸出：估計參數的RDD*。

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

3.為每個用戶u和項目i提供偏好設置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 預測步驟

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

(23)

2.4 矩陣分解和隨機森林

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

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

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

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

(24)

yj=ru,i

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

3 實 驗

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

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

3.1 實驗數據集和評價標準

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

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

(25)

(26)

3.2 結果分析

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

圖3 分區數量np對運行時間的影響

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

表1 不同推薦算法在三個數據集上的測試結果

4 結 語

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