融合樸素貝葉斯和協同過濾的外賣推薦并行算法研究

鮑凱麗 劉其成 牟春曉

(煙臺大學計算機與控制工程學院 山東 煙臺 264000)

0 引 言

隨著信息技術的高速發展，電子商務系統中的用戶數量和產品種類越來越多，導致用戶很難從海量的信息中獲取自己感興趣的內容。推薦系統作為一種重要的信息過濾技術和手段，是解決信息過載的有效方式[1]。推薦系統主要包括基于內容的推薦、協同過濾推薦和基于知識的推薦[2]，協同過濾推薦算法是目前應用最廣泛的推薦算法[3]。

隨著信息化的迅速發展，餐飲業也加快了腳步，越來越多的用戶通過網上訂餐的方式進行美食選擇。由于美食的種類和樣式不斷增多，導致了用戶在選擇美食時需要花費更多的時間和精力。在推薦算法領域進行外賣的研究分析，不僅可以幫助商家更好地鎖定用戶群，也可以幫用戶高效地選擇自己喜愛的美食。

本文提出了一種融合樸素貝葉斯和協同過濾的外賣推薦并行算法。該算法基于MapReduce分布式計算框架，通過對外賣評論數據集進行深入挖掘，實現外賣個性化的推薦，推薦的信息對用戶具有很高的參考價值。

1 相關工作

評論挖掘是現有的協同過濾算法中用以緩解數據稀疏問題的重要方法之一，當前，已經有許多專家和學者對融入評論文本的推薦方法進行了大量研究。

文獻[4]圍繞從評論標簽中挖掘用戶對產品特征的觀點展開研究，向用戶推薦在他們感興趣的特征上有較高評價的產品。文獻[5]圍繞從評論信息中提取社交情感展開研究，在推薦系統中推薦。文獻[6]研究將用戶評論集和商品評論集各自潛在的主題向量建立正向映射關系，進一步優化推薦模型。文獻[7]提出網絡評論數據的產品設計綜合評價模型，運用情感傾向分析技術和LDA主題模型算法進行主題發現的研究。文獻[8]提出利用評分數據生成評論態度影響因子，建立用戶偏好與物品特征，進而進行評分預測與物品推薦。文獻[9]提出對評論文本進行情感傾向的分析來產生相應的分值，從而進行推薦。文獻[10]研究基于樸素貝葉斯的協同過濾推薦算法，采用改進的樸素貝葉斯方法對沒有評分的數據進行預測。

隨著餐飲行業的快速發展，如何通過網絡及時準確的為用戶提供合適的美食推薦已經成為目前研究的重點。

文獻[11]研究基于協同過濾算法的美食推薦系統，根據用戶對各種美食的評分，結合其他用戶的興趣相似度，并利用美食屬性特征的相似度作為權重因子進行矩陣補全。文獻[12]研究基于LDA模型的餐廳推薦方法。該算法首先對餐廳評價信息進行情感分類，進而獲取積極評價和好評率，然后計算用戶需求與餐廳標簽的相似度，根據相似度和好評率向用戶推薦餐廳。文獻[13]研究基于協同過濾的美食推薦算法，該文獻在計算相似度時引入了遺忘函數和用戶間的信任度。

可以看出，無論是在融入評論文本的推薦方法方面，還是在美食推薦方面，上述文獻都未對融合評論文本和評分數值的外賣推薦針對性的進行深入研究。本文同以上工作相比，數據對象來源于互聯網的上真實美食評論，具有復雜性高、涉及面廣等特點。在提高推薦系統的準確性方面，一方面設計融合評論文本和評分數值綜合評分模型；另一方面在ALS模型前融合物品的相似性信息，設計一種新的損失函數。通過以上改進，本文算法在一定程度上減小了系統的均方根誤差，提高了推薦準確率，改善了推薦系統性能。

2 相關概念

2.1 樸素貝葉斯分類

樸素貝葉斯分類是利用概率統計進行分類的算法，主要利用貝葉斯定理來預測一個未知類別樣本屬于其他類別的可能性，其基本思想如下：

假設有k個類C1，C2，…，Ck給定一個未知的數據實例X，分類器將預測數據實例X分類為屬于具有最高后驗概率的類，其中最大后驗概率的類用P(Ci|X)最大的類Ci表示。

(1)

2.2 ALS算法

ALS算法的實質是填充用戶—物品評分矩陣中缺失的部分，如果用戶評分矩陣為R，其元素表示的是用戶u對物品v的評價，由奇異值分解原理，矩陣R等于幾個矩陣相乘。公式如下:

R=UTV

(2)

通過用戶-物品的評分矩陣分解原理可知，預測用戶對物品的喜好只需求取UT和V，一般通過最小化損失函數求取。為了防止損失函數過擬合，采用正則化方法添加正則化項，最后損失函數如下：

(3)

對于求解上述損失函數的最優化，可以使用梯度下降也可以使用最小二乘法，其中二乘法求取的是全局的最小值，固定一個向量，求取另一個向量，然后交替迭代執行，最終訓練出一個最好的預測模型。

2.3 MapReduce

MapReduce是處理大數據的一種并行編程框架，將數據表達成鍵值對的形式。MapReduce包含任務分解(Map)和結果匯總(Reduce)兩個步驟處理數據，Map任務和Reduce任務可以被分配到不同的資源節點并行執行。

3 外賣推薦并行算法設計

3.1 綜合評分模型設計

目前，越來越多的外賣網站都支持用戶對購買的外賣進行打分和發表評論，用戶在挑選外賣時越來越注重商品的評論。評論文本內容是用戶對外賣美食特征、質量、商家服務等的描述，評分并不能全面衡量用戶對外賣的情感，所以結合評論文本這一指標來修正原來評分。

3.1.1評分預測

對外賣評論文本進行關鍵詞提取，進而構建出針對外賣評論的情感詞典，然后設計并行化的樸素貝葉斯文本情感分類器，量化評論文本情感值。經過數據預處理輸出外賣訓練評論數據形為D={C1,C2,…,Ck,A1,A2,…,An}, 其中A是屬性變量，C為情感傾向。這部分算法主要分為兩個步驟：

第一步訓練階段的主要目標就是生成外賣評論數據情感傾向的分類器，在算法訓練階段的Map階段中，每一個節點隨機抽取本臺機器中存儲的訓練集Di中的外賣評論數據，Map階段中每個節點執行的Map任務描述如下：

輸入: 訓練集

輸出:

Begin

(1) While Di!=null do

(2) for each value do

(3) vals=str.split(″″)

(4) ClassID.set(vals[0])

(5) write(ClassID, one)

(6) end for

(7) for each value do

(8) GetCateInClass()

(9) cws.set(temp)

(10) write(cws, one)

(11) end for

End

Reduce階段主要負責將Map階段每個節點輸出的內容進行匯總，輸出<劃分屬性值，數量統計>鍵值對和情感傾向的先驗概率prior[c]。Reduce階段中每個節點執行的Reduce任務描述如下：

輸入:

輸出:

Begin

(1) int Num=0

(2) int Count=0

(3) for each vido

(4) Num+=val.get()

(5) write(ClassID, Num)

(6) end for

(7) for each vido

(8) Count+=val.get()

(9) write(cws, Count)

(10) end for

(11) for each calss do

(12) prior[c]=Num/sum

(13) end for

(14) write(ClassID, prior[c])

End

第二步分類階段目標是使用第一步的分類器對未知情感傾向的評論文本預測分類，對每一條測試數據，根據式(1)計算測試樣本的后驗概率，然后將最大的后驗概率的情感傾向判定為測試樣本的類。

算法分類階段的Map階段的目標是計算每條外賣測試數據的條件概率，根據先驗概率和條件概率通過計算測試樣本的后驗概率。Map階段中每個節點執行的Map任務描述如下:

輸入: 測試數據集

輸出:

Begin

(1) While Bi!=null do

(2) for each value do

(3) Record=Data.freq.get(date)

(4) Tct=Record/Num

(5) P=P*Tct

(6) end for

(7) for each Class do

(8) Posterior[c]=prior[c]*P

(9) end for

(10) write(id, Posterior[c])

End

算法分類階段的Reduce階段的任務是把上一步輸出結果進一步合并處理，若Posterior[積極傾向]大于Posterior[消極傾向]，判斷該評論數據為積極傾向，否則為消極傾向。其中， Score即該外賣評論文本情感值。

輸入:

輸出:

Begin

(1) for each calss do

(2) if(P>maxf)

(3) maxf=p

(4) end for

(5) id=new Text(val[ ])

(6) Score=new Text(ClassNames.get(maxf))；

(7) write(id, Score)

End

由于外賣評分值是五分制，需要對上述量化的情感值Score進行處理使其取值范圍在[0, 5]之間。

3.1.2綜合評分模型

本文將外賣評分數值與評論文本情感值模型結合構建外賣綜合評分模型。綜合評分模型如下所示:

Score(i)new=w1×Score(i)1+w2×Score(i)2

(4)

w1+w2=1

(5)

式中：i表示第i條外賣評論；Score(i)1表示外賣評分數值；Score(i)2表示外賣評論文本的情感值；w1和w2分別表示外賣評分數值和外賣評論文本情感值的權重；Score(i)new表示結合外賣評分數值和外賣評論文本情感值的綜合評分。

3.2 構建推薦模型

在得到外賣綜合評分數據集后將其整合到并行文件系統HDFS中。在后續的并行推薦過程中，算法將從HDFS直接獲取數據。

3.2.1算法的優化

依據ALS算法的原理可以發現，損失函數忽略了物品之間有價值的數據信息。因此，針對這個問題本文設計了一種新的損失函數，引入物品相似度。本文選擇修正的余弦相似度，則此時損失函數為:

(6)

式中:nui表示用戶Ui評價過的外賣的數量；nvj表示為外賣Vj評過分的用戶數量；rui表示用戶u對物品i的評分；ruj表示用戶u對物品j的評分。

3.2.2計算推薦集

該部分主要通過3個步驟實現： ① 針對用戶評分數據集求出外賣項目向量矩陣和用戶向量矩陣。 ② 求用戶特征矩陣U和外賣特征矩陣V。 ③ 利用上述步驟產生的U和V，求出推薦矩陣。

第①步的實現需要兩個MapReduce過程，分別求出用戶u評價過的外賣的集合和評價過外賣v的用戶的集合。第一個Map階段接受初始輸入的數據集合， 統計不同用戶對同一外賣的評分，Reduce階段將其合并輸出記為R[n]。第二個Map階段統計同一用戶對不同外賣的評分，Reduce階段將其合并輸出記為R[m]。

第②步計算用戶特征矩陣U和外賣特征矩陣V， 每次求用戶特征矩陣U和外賣特征矩陣V都需要一次MapReduce過程。由于用戶ID和外賣ID的唯一性，在迭代計算過程不需要Reduce階段。當求解U矩陣時，輸入用戶評分過的外賣的集合R[n]及外賣特征矩陣V，利用式(6)計算用戶的特征向量Ui，Map階段中每個節點執行的Map任務描述如下：

輸入: R[n]

輸出:

Begin

(1)whileDi!=nulldo

(2)foreachvifromDido

(3) V=rand()

(4) calculate Uiaccording to formula

(5)endfor

(6) write()

End

同理，當求解V矩陣時，輸入評價過的外賣的用戶的集合R[m]及用戶特征矩陣U，利用式(6)計算外賣的特征向量Vj，Map階段中每個節點執行的Map任務描述如下:

輸入: R[m]

輸出:

Begin

(1)whileDi!=nulldo

(2)foreachvifromDido

(3) U=rand()

(4) calculate Vjaccording to formula

(5)endfor

(6) write()

End

這樣反復迭代計算U和V， 最后通過一個迭代次數計數器的任務來結束整個算法流程。

第③步利用上述步驟產生U和V，根據X=UVT求出預測評分矩陣X，得到的結果即為用戶對每個項目的預測評分。最后對這些評分從高到低進行排序， 同時除去用戶已經評價過的外賣，即可得到最終的用戶推薦外賣項目集。

4 實驗結果與分析

4.1 實驗數據

從某外賣網站抓取了外賣的評論數據記為Date，采集的評論數據包括評論用戶編號、外賣編號、評論時間、評分數值、評論文本。其中，評分值都是整數值(1～5之間)，分數越高代表用戶相應的外賣評分就越高。本實驗數據集包括三組：第一組從Date中隨機抽取5 000條評論數據記為Date1；第二組從Date中隨機抽樣500 000條數據記為Date2；第三組從Date中分別采集3種不同規模的數據集，得到數據規模分別為三組測試數據的大小分別是：589 MB、1 432 MB和2 471 MB。

4.2 評價指標

(1) 準確度。衡量一個推薦系統的優劣，有很多種評價指標[14]。本文將通過均方根誤差(RMSE)來評價評分預測的準確度。均方根誤差值越小，意味著準確度越高。公式表示為:

(7)

(2) 加速比。加速比用來衡量并行算法并行化的性能和效果。指同一個串行算法的運行時間(Ts)和并行處理器算法中運行消耗的時間(Tp)的比率，公式表示為：

(8)

4.3 綜合評分模型分析

權重的確定方法主要分為主觀賦權法[15]和客觀賦權法[16]兩大類。本文使用主觀賦權法，通過人工標注對Date1數據集中評論文本和評分數值進行綜合打分(5分制)，然后比較評分數值的正確率(A1)和評論文本情感值正確率(A2)。

正確率=判斷評分和人工標注評分相同的個數/總個數，結果如表1所示。

表1 評論文本和評分數值正確率 %

從表1可以看出，評論文本情感值的正確率比評分數值的正確率高，所以評論文本情感值更能反映外賣的真實評分，因此在構建綜合評分模型時通過正確率的大小來確定評論文本和評分數值這兩個變量的權重。

(9)

(10)

得到綜合評分模型為：

Score(i)new=0.46×Score(i)1+0.54×Score(i)2

(11)

4.4 推薦結果分析

(1) 準確率分析。本文算法中最重要的參數是正則化參數λ和迭代次數。其中，迭代次數越大越精確，但是設置的越大也就意味著越耗時，算法在每次迭代時都會優化矩陣，因此經少數迭代就能收斂到一個較合理的模型，所以本文選取迭代次數為20、30、40。正則化參數越高正則化越嚴厲，但并非越高越好，在本文中選取正則化參數的值為0.1、1、10。因此共產生9個模型，該部分實驗使用數據集Date2，分別計算9個模型的均方根誤差如表2所示。

表2 本文算法均方根誤差

從表2中可以發現，在正則化參數固定的條件下，隨著迭代次數值增大，均方根誤差的值越來越小。而在迭代次數值不變的情況下，隨著正則化參數值增大，均方根誤差值越來越大。其中當迭代次數為40，正則化參數為0.1時，算法的均方根誤差最優，得到最優模型后，可以通過最優模型來進行推薦。

(2) 加速比分析。實驗采用第三組數據集，分別測試三種規模數據在1個、2個和3個節點上的運行時間，實驗結果如表3所示。

表3 運行時間 s

根據表3中的數據，可以計算出算法在三組數據集的加速比如表4所示，算法加速比的曲線如圖1所示。

表4 數據運行加速比

圖1 不同規模數據的加速比

分析表4和圖1可以發現，在數據量不變的情況下，加速比隨著節點數目的增加而增加。當節點數目不變時，隨著數據規模的增大，加速比也會隨之增高。實驗結果表明，本文算法在處理比較大規模的數據時展現出了良好的性能，可以有效提高算法的執行效率，具有比較好的加速比。

4.5 實驗對比

(1) 綜合評分模型有效性實驗對比。為驗證融合評論文本和評分數值綜合評分模型有效性，對數據集Date2進行處理，將僅有評論數值的外賣評論數據記為訓練數據集D21，融合評論文本和評分數值的外賣評分數據記為訓練數據集D22。使用兩個數據集分別進行實驗，推薦結果準確率對比如表5所示。

表5 均方根誤差的值

由表5可知，采用訓練數據集D22比訓練數據集D21進行實驗得到的均方根誤差略小。實驗結果表明，使用融合評論文本和評分數值綜合評分模型會降低RMSE值，使推薦結果更加準確。

(2) 算法準確性實驗對比。為驗證本文算法是否提高了推薦結果的準確性，采用ALS算法在相同的數據集、正則化參數和迭代次數情況下，用均方根誤差指標對以上兩種算法的推薦效果進行對比。得到ALS算法的均方根誤差值如表6所示，在正則化參數不變的情況下，隨著迭代次數的變化兩種算法的均方根誤差值對比如圖2所示。

表6 ALS算法均方根誤差

圖2 RMSE值對比

結合表2、表6和圖2可以發現，無論在迭代次數固定正則化參數增加，還是在正則化參數固定迭代次數增加的情況下，本文算法的RMSE值比ALS算法的值都有所減小。實驗結果表明，本文算法與傳統ALS算法相比降低了預測評分的均方根誤差，提高了推薦系統的準確率，該算法用于個性化外賣推薦是可行和有效的。

5 結 語

本文提出了一種融合樸素貝葉斯和協同過濾的外賣推薦并行算法，該算法具有較高的準確性，能夠較準確地對用戶進行外賣推薦。同時，算法可以處理大規模的數據并且具有良好的加速比，有效地提升了協同過濾算法對于海量數據的處理能力。本文實現了對外賣信息的深度挖掘，推薦的信息對用戶具有很高的參考價值。

推薦系統的一個目標是向用戶推薦滿足個性化要求的物品，而如果只以推薦準確度為目標進行推薦，將影響推薦系統的長期性能，導致長尾效應。所以下一步的研究重點是如何將本算法與其他推薦方法結合使用，提升推薦結果的多樣性，從而構建以本文算法為核心的高效推薦算法。