馮 輝，陳 磊，孫妍姑

（淮南師范學(xué)院 計(jì)算機(jī)學(xué)院，安徽 淮南 232038）

1 引 言

據(jù)權(quán)威部門統(tǒng)計(jì)，截止2018 年7 月底，我國互聯(lián)網(wǎng)用戶規(guī)模已達(dá)8.02 億， 其中視屏用戶規(guī)模達(dá)6.09 億［1］。電影服務(wù)類網(wǎng)站隨著用戶數(shù)量的急劇增加，產(chǎn)生了海量的電影用戶評價(jià)數(shù)據(jù)，這些數(shù)據(jù)為我們分析用戶行為提供了有效支持。然而，一方面，基于海量電影用戶評價(jià)數(shù)據(jù)（以下簡稱海量評價(jià)數(shù)據(jù)）的用戶行為模型（User Behavior model，UBM）構(gòu)建具有挑戰(zhàn)性，另一方面，采用傳統(tǒng)單機(jī)串行數(shù)據(jù)處理系統(tǒng)處理海量用戶評價(jià)數(shù)據(jù)顯得相形見絀，使用戶行為計(jì)算、預(yù)測變得比較困難。

貝葉斯網(wǎng)絡(luò)（Bayesian Network，BN）是有向無環(huán)圖（Directed Acyclic Graph，DAG）的一種，用條件概率表（Conditional Probability Table，CPT）描述網(wǎng)絡(luò)中各節(jié)點(diǎn)依賴關(guān)系值，是一種幫助人們在不同應(yīng)用場景下分析模型各屬性間依賴關(guān)系的有效工具，它將概率統(tǒng)計(jì)引入，能夠進(jìn)行各屬性間不確定性推理［2］（P9-12），在不同領(lǐng)域都有著廣泛應(yīng)用。 如圖1 所示。采用貝葉斯網(wǎng)絡(luò)能夠較好的反映出電影用戶行為的不確定性，為系統(tǒng)實(shí)現(xiàn)提供了技術(shù)支持。

圖1 貝葉斯網(wǎng)絡(luò)

面對海量評價(jià)數(shù)據(jù)，傳統(tǒng)單機(jī)串行數(shù)據(jù)處理系統(tǒng)已經(jīng)不能滿足人們對數(shù)據(jù)處理實(shí)時(shí)性及高效性的要求。Hadoop 是一個分布式海量數(shù)據(jù)處理平臺，以Hadoop 分布式文件系統(tǒng) （Hadoop Distributed File System，HDFS）和離線計(jì)算框架MapReduce 為核心，主要有高可靠性、高拓展性、高效性、高容錯性等優(yōu)點(diǎn)［3］（P48-50）。 用戶可以根據(jù)不同的應(yīng)用場景，編寫符合自身業(yè)務(wù)需求的MapReduce 程序， 實(shí)現(xiàn)海量數(shù)據(jù)實(shí)時(shí)、高效處理的功能。Hadoop 的出現(xiàn)為分析海量評價(jià)數(shù)據(jù)、構(gòu)建UBM 以及對用戶行為預(yù)測提供可能。

目前，以貝葉斯網(wǎng)絡(luò)為基礎(chǔ)，以Hadoop 為平臺構(gòu)建UBM，分析、預(yù)測用戶行為這一課題吸引著眾多學(xué)者進(jìn)行研究。王飛考慮到電影用戶評價(jià)數(shù)據(jù)及其評價(jià)行為隨著時(shí)間的變化而變化這一特性，將用戶評價(jià)行為作為貝葉斯網(wǎng)絡(luò)中用戶屬性的隱變量，構(gòu)建可以描述用戶動態(tài)行為的評價(jià)模型［4］，建立在Hadoop 平臺的實(shí)驗(yàn)驗(yàn)證了此方法實(shí)現(xiàn)用戶行為預(yù)測的高效性。徐雅蕓為了提高用戶行為預(yù)測準(zhǔn)確率，改進(jìn)了BiGRU-ADtt 模型，考慮到用戶評價(jià)數(shù)據(jù)服從冪律分布及對稱特點(diǎn)， 首先采用BiGRU模型分析出不同用戶評價(jià)行為之間的依賴關(guān)系，然后將評價(jià)數(shù)據(jù)的對稱性特點(diǎn)作為衡量評價(jià)行為的依據(jù)， 最后建立在Hadoop 上的真實(shí)數(shù)據(jù)表明該方法能夠充分挖掘用戶行為習(xí)慣，實(shí)現(xiàn)高準(zhǔn)確率的用戶行為預(yù)測［5,6］。

本文以貝葉斯網(wǎng)為基礎(chǔ)， 以Hadoop 平臺為工具，首先將海量評價(jià)數(shù)據(jù)及初始UBM 存入Hadoop分布式數(shù)據(jù)庫（Hadoop Database）HBase 中，然后利用MapReduce 結(jié)合期望優(yōu)化 （Expectation Maximization ，EM） 算法將缺失的描述用戶行為的數(shù)據(jù)補(bǔ)全， 接著并行化爬山算法， 以貝葉斯信息準(zhǔn)則（Bayesian Information Criterion，BIC） 為度量標(biāo)準(zhǔn)，高效構(gòu)建并選擇最優(yōu)UBM， 最后根據(jù)模型預(yù)測用戶行為。

2 系統(tǒng)設(shè)計(jì)

2.1 系統(tǒng)架構(gòu)設(shè)計(jì)

針對上述問題，本系統(tǒng)從可維護(hù)性及可拓展性出發(fā)，采用層次化設(shè)計(jì)結(jié)構(gòu)，主要分為數(shù)據(jù)層、算法層、業(yè)務(wù)層以及用戶接口層，總體設(shè)計(jì)架構(gòu)如圖2所示。

1. 數(shù)據(jù)層： 該層是整體架構(gòu)的最底層， 包含HDFS 分布式文件系統(tǒng)及HBase 分布式數(shù)據(jù)庫，主要是對海量評價(jià)數(shù)據(jù)以及初始UBM 進(jìn)行存儲，并與MapReduce 計(jì)算框架交互， 為后續(xù)計(jì)算用戶行為、構(gòu)建UBM 提供數(shù)據(jù)支持。

2.算法層：主要是對EM 算法、爬山算法并行化， 并結(jié)合BIC 評分尋找描述用戶行為的最優(yōu)模型，根據(jù)模型計(jì)算、預(yù)測用戶行為。

3. 業(yè)務(wù)層： 該層是用戶行為預(yù)測功能實(shí)現(xiàn)層次，主要包含數(shù)據(jù)存儲模塊、數(shù)據(jù)處理模塊、UBM構(gòu)建及預(yù)測模塊。

4.用戶接口層：用戶接口層實(shí)現(xiàn)了用戶與系統(tǒng)進(jìn)行交互的層次，用戶可以通過用戶接口向系統(tǒng)提交請求，并得到相應(yīng)的響應(yīng)。

圖2 系統(tǒng)整體架構(gòu)圖

2.2 系統(tǒng)功能設(shè)計(jì)

通過對系統(tǒng)業(yè)務(wù)層進(jìn)行分析，按照其需求將系統(tǒng)劃分成不同的功能模塊，具體的功能模塊結(jié)構(gòu)如圖3 所示。

圖3 系統(tǒng)功能模塊圖

2.2.1 數(shù)據(jù)存儲模塊

數(shù)據(jù)存儲模塊包含三個功能子模塊，即海量評價(jià)數(shù)據(jù)的存儲、 貝葉斯網(wǎng)DAG 結(jié)構(gòu)以及條件概率表（CPT）的存儲。 在存儲海量評價(jià)數(shù)據(jù)之前，需要對數(shù)據(jù)進(jìn)行預(yù)處理，提取出評分?jǐn)?shù)據(jù)屬性［7］作為評分的特征信息，并存入HBase 中。 貝葉斯網(wǎng)是描述用戶評價(jià)數(shù)據(jù)各屬性之間關(guān)系及構(gòu)建UBM 的工具，對其存儲是一個技術(shù)熱點(diǎn)，主要是對其DAG 結(jié)構(gòu)以及描述有向邊關(guān)系的條件概率表（CPT）的存儲，這里定義二元組［8］R=（Gu，S）來表示一個貝葉斯網(wǎng)， 其中Gu 為貝葉斯網(wǎng)的DAG 結(jié)構(gòu)，S 為條件概率表（CPT）的集合，分別使用Map 函數(shù)并行讀取Gu、S，再使用Reduce 函數(shù)進(jìn)行合并、規(guī)約操作，最終生成包含DAG 結(jié)構(gòu)以及CPT 的鍵值對，最終存入HBase 中。

2.2.2 數(shù)據(jù)處理模塊

在實(shí)際的用戶評價(jià)數(shù)據(jù)集中，并不包含用戶行為這一屬性，而本文研究的重點(diǎn)就是從海量評價(jià)數(shù)據(jù)出推演用戶行為，因此挖掘用戶行為是一項(xiàng)重要工作。數(shù)據(jù)處理模塊主要功能就是以海量評價(jià)數(shù)據(jù)為基礎(chǔ)，將EM 算法與MapReduce 相結(jié)合，實(shí)現(xiàn)并行化挖掘用戶行為功能，具體過程我們將在第3 章進(jìn)一步闡述。

2.2.3 UBM 構(gòu)建及預(yù)測模塊

UBM 構(gòu)建及預(yù)測是本文的核心模塊， 通過構(gòu)建好的UBM 實(shí)現(xiàn)行為預(yù)測功能，其中主要使用了爬山算法及貝葉斯信息準(zhǔn)則。

爬山算法是經(jīng)典的貝葉斯網(wǎng)結(jié)構(gòu)學(xué)習(xí)算法，目標(biāo)是從眾多候選模型中找出評分最高的模型。 首先，從初始模型開始搜索，一般把初始模型定義為無邊模型，在進(jìn)行搜索時(shí)，利用三個搜索算子（即加邊、減邊、轉(zhuǎn)邊）對選定模型進(jìn)行局部修改，然后對每一個經(jīng)過局部修改后的模型進(jìn)行BIC 度量，選擇評分最高的模型與選定模型進(jìn)行比較，若選定模型的BIC 評分值比評分最高模型的分值小，則將后者作為下一個選定模型，繼續(xù)搜索，具體過程我們將在第3 章進(jìn)一步闡述。

貝葉斯信息準(zhǔn)則（Bayesian Information Criterion，BIC）是一種可以度量UBM 與用戶評價(jià)數(shù)據(jù)之間關(guān)系的方法，并用擬合程度表達(dá)，擬合程度越高，則表示當(dāng)前UBM 的BIC 分值就越高。

由數(shù)據(jù)存儲模塊、數(shù)據(jù)處理模塊分別得到初始描述用戶行為的貝葉斯網(wǎng)絡(luò)以及帶有用戶行為的完整評價(jià)數(shù)據(jù)集， 然后利用MapReduce 與爬山法及BIC 評分相結(jié)合，并行化構(gòu)建用戶行為構(gòu)建，最后根據(jù)用戶模型，計(jì)算用戶行為。

3 算法層詳細(xì)設(shè)計(jì)

3.1 EM 算法設(shè)計(jì)

如2.2.2 節(jié)所述， 在實(shí)際的用戶評價(jià)數(shù)據(jù)集中并沒有用戶行為這一屬性，這里把用戶行為稱為缺失值。

期望優(yōu)化（Expectation Maximization，EM）算法是經(jīng)典的參數(shù)學(xué)習(xí)算法， 通過E、M 步驟的反復(fù)迭代，達(dá)到對缺失值進(jìn)行補(bǔ)全的目的。

本文用ti表示用戶評價(jià)某個時(shí)間片，L 表示用戶行為（L∈{0，1}），θ 為結(jié)點(diǎn)CPT 集合，對給定的DAG 結(jié)構(gòu)， 采用EM 算法對含有N 個評價(jià)實(shí)例的評價(jià)數(shù)據(jù)集［4］的用戶行為進(jìn)行填充時(shí)，從隨機(jī)產(chǎn)生的初始值θ0開始迭代， 設(shè)已經(jīng)進(jìn)行了l 次迭代，得到參數(shù)估計(jì)為θl，第l+1 次迭代過程可由算法1 表示。 為了提高計(jì)算效率，將MapReduce 計(jì)算框架引入，實(shí)現(xiàn)EM 算法的并行化，并生成相應(yīng)的key/value鍵值對，算法流程圖如4 所示。

圖4 并行化EM 算法流程圖

算法1：并行化EM 算法

輸入： δ—收斂閾值；

Dti—ti缺失用戶行為的評價(jià)數(shù)據(jù)集；

G—ti爬山算法得到的UBM；

輸出：Dti—ti中帶有用戶行為的評價(jià)數(shù)據(jù)集。

步驟：

l←0；θ0←隨機(jī)參數(shù)值；

/*計(jì)算θl基于Dti的對數(shù)似然值*/

oldValue←L（θl|Dti）；

while(true)

E-步驟:

Mapper 函數(shù)

key ←計(jì)算L 取值概率；

value ←計(jì)算L 取值概率和；

M-步驟:

Reducer 函數(shù)

計(jì)算參數(shù)θl+1；

計(jì)算θl+1基于Dti的對數(shù)似然值；

newValue←L（θl+1|Dti）；

if (newValue－oldValue＞δ)

oldValue←newValue；

l←l+1；

else

選擇概率最高的填充值填充Dti；

return Dti．

end if

end while

3.2 爬山算法設(shè)計(jì)

由2.2.3 節(jié)所述， 通過爬山算法可以對基于貝葉斯網(wǎng)絡(luò)的UBM 進(jìn)行搜索操作，由三個搜索算子（加邊、減邊、轉(zhuǎn)邊）可產(chǎn)生多個候選UBM，再通過BIC 評分度量， 選擇評分最高的UBM 與當(dāng)前選定的UBM 進(jìn)行比較， 若選定UBM 的BIC 分值比評分最高的UBM 分值小，則將后者作為下一個選定UBM，繼續(xù)搜索。 為了提高模型搜索、打分效率，這里將爬山算法與MapReduce 相結(jié)合，實(shí)現(xiàn)模型搜索、評分地并行化，主要過程見算法2，流程圖見圖5。

算法2：并行化爬山算法

輸入：δ—收斂閾值；

f=ValueBIC（g|Dti）—模型選擇BIC 打分函數(shù)；

Dti—ti中評價(jià)數(shù)據(jù)集；

g0—初始DAG 結(jié)構(gòu)；

輸出：時(shí)間片ti中UBM 結(jié)構(gòu)g．

步驟：

Mapper 函數(shù)

/*初始化g 結(jié)構(gòu)最大似然估計(jì)g0*/

g ←g0；

/*調(diào)用算法1 填充用戶行為值*/

θ←FillValue（g，Dti）

key←g；

value←θ；

oldValue←ValueBIC（g|Dti）

Reducer 函數(shù)

while (true)

g*←null；θ*←null；

newValue←-∞

for(爬山算法對g 搜索而得到的候選結(jié)構(gòu)g′)

θ′←FillValueBIC（g′，Dti）；

tempValue←ValueBIC（g′|Dti）；

if (tempValue＞newValue)

g*←g′；θ*←θ′；

newValue←tempValue；

end if

end for

if(newValue＞oldValue)

g ←g*；θ←θ*；

oldValue←newValue；

else return g．

end if

end while

圖5 并行化爬山算法流程圖

4 系統(tǒng)實(shí)現(xiàn)

4.1 數(shù)據(jù)存儲模塊實(shí)現(xiàn)

1.測試數(shù)據(jù)來源。

表1 用戶評價(jià)數(shù)據(jù)

MovieLens 是一個關(guān)于電影評分的數(shù)據(jù)集，源于美國Minnesota 大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院創(chuàng)建的一個非商業(yè)性質(zhì)的、 以研究為目的的實(shí)驗(yàn)性站點(diǎn)，主要是對不同種類的電影進(jìn)行描述，包含用戶名稱、電影類型、評分值、時(shí)間戳等基本信息［9］。 我們從中選取7 條評分?jǐn)?shù)據(jù)作為測試，如表1 所示，其中UID 表示用戶ID，style 表示影片類型，score表示用戶對該電影的評分值，time 表示用戶評價(jià)時(shí)間。

2. 評價(jià)數(shù)據(jù)存儲。 分別啟動HDFS、Yarn、HBase，調(diào)用MapReduce 計(jì)算框架，將最終的計(jì)算結(jié)果存儲到HBase 中，命為UserData 表，如圖6 所示。 對于給定的用戶評價(jià)數(shù)據(jù)，逐行進(jìn)行讀取，并以時(shí)間time 為標(biāo)識進(jìn)行存儲。

圖6 UserData 表中的數(shù)據(jù)

3.貝葉斯網(wǎng)DAG 及CPT 存儲。 針對表1 的用戶評價(jià)數(shù)據(jù)，初始化一個UBM，如圖6 所示，其中L 表 示 用 戶 行 為，UID、style、score 為 評 價(jià) 數(shù) 據(jù) 屬性， 屬性之間的不確定性關(guān)系用條件概率表CPT表示。

圖7 初始的UBM

針對L 節(jié)點(diǎn)，在Map 階段，Mapper 函數(shù)會讀取該節(jié)點(diǎn)對應(yīng)的CPT，即P（L=0|UID=1）=0.33、P（L=1|UID=1）=0.67、P（L=0|UID=2）=0.5、P（L=1|UID=2）=0.5， 然后根據(jù)以上讀取的數(shù)值， 設(shè)置key=（L=0|UID=1），value=0.33、key=（L=1|UID=1），value=0.67、key=（L=0|UID=2），value=0.5、key=（L=1|UID=2），value=0.5，最后生成相應(yīng)的key/value 鍵值對，即、< L=1|UID=1，0.67>、< L=0|UID=2，0.5>、< L=1|UID=2，0.5>，對其他節(jié)點(diǎn)進(jìn)行類似操作， 最終會得到關(guān)于圖7 的DAG 表及CPT 表，分別如圖8，圖9 所示。

圖8 DAG 表

圖9 CPT 表

4.2 數(shù)據(jù)處理模塊實(shí)現(xiàn)

根據(jù)4.1 節(jié)存入的用戶評價(jià)數(shù)據(jù)及初始UBM，調(diào)用算法1 對其進(jìn)行用戶行為補(bǔ)全，并最終將補(bǔ)全的完整用戶評價(jià)數(shù)據(jù)寫入HBase，如圖10 所示。

圖10 完整用戶評價(jià)數(shù)據(jù)

如1997.01.01 用戶2 對于1 類型的電影評分為1，那么經(jīng)過計(jì)算，將用戶行為的值補(bǔ)全為1。

4.3 UBM 構(gòu)建及預(yù)測模塊實(shí)現(xiàn)

1.模型構(gòu)建實(shí)現(xiàn)。調(diào)用算法1、2，基于完整評價(jià)數(shù)據(jù)集，對初始用戶模型迭代搜索，并用BIC 評分對每個模型的搜索結(jié)果進(jìn)行擬合程度評估，選取擬合度最高的模型作為最終的UBM， 并將最終結(jié)果寫入HBase，如圖11、12 分別表示描述最終構(gòu)建完成的用戶模型DAG 表及CPT 表。

圖11 用戶模型的DAG 表

圖12 用戶模型的CPT 表

根據(jù)上述的DAG 表與CPT 表，可以刻畫出最終的UBM，如圖13 所示。

圖13 最終的UBM

2. 用戶行為預(yù)測。 從HBase 中讀取構(gòu)建好的UBM，采用貝葉斯網(wǎng)推理方法，預(yù)測用戶行為。

圖14 用戶行為預(yù)測

從圖14 可以發(fā)現(xiàn)，用戶2 對于2 類型的電影，喜歡的概率為0.75，我們就認(rèn)為用戶2 對2 類型的電影存在偏好，并在以后的時(shí)間片內(nèi)對2 類型電影有著較高概率的需求， 那么就可以根據(jù)這個結(jié)果，在近期為用戶2 做2 類型的電影推薦。

5 系統(tǒng)測試

5.1 系統(tǒng)有效性測試

為了測試本系統(tǒng)預(yù)測用戶行為的有效性和高效性， 本文截取了MovieLens 從1993-2013 年13 255個用戶對18 種電影類型共12 435 232 行評價(jià)數(shù)據(jù)作為測試［10］。 實(shí)驗(yàn)環(huán)境設(shè)置主要包含一個Master 節(jié)點(diǎn)和三個Slave 節(jié)點(diǎn)，具體設(shè)置如表2 所示。

BPTF (Bayesian probabilistic tensor factorization)貝葉斯概率張量分解技術(shù)，在用戶行為建模及預(yù)測領(lǐng)域有著廣泛應(yīng)用［11］（P211-222）。

TCAM (temporal context-aware mixture model)也是一種受歡迎的用戶行為預(yù)測模型，考慮到用戶行為受時(shí)間變化的影響， 該模型融合了時(shí)間序列，使用戶行為的預(yù)測更加精準(zhǔn)［12］。

我們將采集到的1 243 522 行評價(jià)數(shù)據(jù)中前70%作為建模數(shù)據(jù)，后30%作為測試數(shù)據(jù)。 測試了BPTF、TCAM、UBM 用戶行為預(yù)測的準(zhǔn)確率（Precision）和覆蓋率（Coverage）。 用precision@k 表示各模型返回k 個用戶行為的準(zhǔn)確率［13］；用coverage@k表示各模型返回k 個用戶行為的覆蓋率［14］，分別如表3、4 所示， 從表可知UBM 在預(yù)測用戶行為的準(zhǔn)確率、覆蓋率均高于其他模型，這驗(yàn)證了本文提出的基于UBM 的系統(tǒng)在預(yù)測用戶行為的有效性。

表2 節(jié)點(diǎn)軟硬件配置表

表3 準(zhǔn)確率

表4 覆蓋率

5.2 系統(tǒng)運(yùn)行效率測試

基于表2 的Hadoop 分布式計(jì)算集群的配置，我們將測試數(shù)據(jù)分為100KB、1MB 及10MB 三個級別，測試了算法在并行、串行環(huán)境下的執(zhí)行效率，測試結(jié)果見表5。

表5 并行計(jì)算與串行計(jì)算運(yùn)行時(shí)間對比

從表5 的實(shí)驗(yàn)結(jié)果我們可以看出，隨著測試數(shù)據(jù)量的增加，傳統(tǒng)單機(jī)串行系統(tǒng)的算法執(zhí)行效率明顯低于Hadoop 分布式集群［15］。

6 總結(jié)與展望

本文從海量電影用戶評分?jǐn)?shù)據(jù)出發(fā)，以Hadoop 平臺中的MapReduce 計(jì)算框架為依托，以貝葉斯網(wǎng)絡(luò)為不確定性推理工具，并結(jié)合期望優(yōu)化（EM）算法、爬山算法、貝葉斯信息準(zhǔn)則（BIC），設(shè)計(jì)了一種能夠從海量電影用戶評價(jià)數(shù)據(jù)中構(gòu)建用戶行為模型（UBM），并進(jìn)行用戶行為預(yù)測的系統(tǒng)，實(shí)驗(yàn)驗(yàn)證了本系統(tǒng)的有效性及高效性。

本文為在海量用戶評價(jià)數(shù)據(jù)情況下，用戶行為建模、計(jì)算及預(yù)測提供了思路。 但這只是用戶行為預(yù)測初步探索，隨著新的評價(jià)數(shù)據(jù)不斷追加［13］，用戶行為不斷演變， 如何在數(shù)據(jù)發(fā)生變化的時(shí)候，模型的訓(xùn)練依舊取得較好的效果，這是今后要開展的工作。