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

鮑凱麗 劉其成 牟春曉

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

0 引 言

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

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

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

1 相關(guān)工作

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

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

隨著餐飲行業(yè)的快速發(fā)展，如何通過網(wǎng)絡(luò)及時準確的為用戶提供合適的美食推薦已經(jīng)成為目前研究的重點。

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

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

2 相關(guān)概念

2.1 樸素貝葉斯分類

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

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

(1)

2.2 ALS算法

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

R=UTV

(2)

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

(3)

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

2.3 MapReduce

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

3 外賣推薦并行算法設(shè)計

3.1 綜合評分模型設(shè)計

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

3.1.1評分預測

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

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

輸入: 訓練集

輸出:

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階段每個節(jié)點輸出的內(nèi)容進行匯總，輸出<劃分屬性值，數(shù)量統(tǒng)計>鍵值對和情感傾向的先驗概率prior[c]。Reduce階段中每個節(jié)點執(zhí)行的Reduce任務(wù)描述如下：

輸入:

輸出:

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

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

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

輸入: 測試數(shù)據(jù)集

輸出:

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階段的任務(wù)是把上一步輸出結(jié)果進一步合并處理，若Posterior[積極傾向]大于Posterior[消極傾向]，判斷該評論數(shù)據(jù)為積極傾向，否則為消極傾向。其中， 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綜合評分模型

本文將外賣評分數(shù)值與評論文本情感值模型結(jié)合構(gòu)建外賣綜合評分模型。綜合評分模型如下所示:

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

(4)

w1+w2=1

(5)

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

3.2 構(gòu)建推薦模型

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

3.2.1算法的優(yōu)化

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

(6)

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

3.2.2計算推薦集

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

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

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

輸入: 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階段中每個節(jié)點執(zhí)行的Map任務(wù)描述如下:

輸入: R[m]

輸出:

Begin

(1)whileDi!=nulldo

(2)foreachvifromDido

(3) U=rand()

(4) calculate Vjaccording to formula

(5)endfor

(6) write()

End

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

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

4 實驗結(jié)果與分析

4.1 實驗數(shù)據(jù)

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

4.2 評價指標

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

(7)

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

(8)

4.3 綜合評分模型分析

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

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

表1 評論文本和評分數(shù)值正確率 %

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

(9)

(10)

得到綜合評分模型為：

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

(11)

4.4 推薦結(jié)果分析

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

表2 本文算法均方根誤差

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

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

表3 運行時間 s

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

表4 數(shù)據(jù)運行加速比

圖1 不同規(guī)模數(shù)據(jù)的加速比

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

4.5 實驗對比

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

表5 均方根誤差的值

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

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

表6 ALS算法均方根誤差

圖2 RMSE值對比

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

5 結(jié) 語

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

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