王 飛 岳 昆 孫正寶 武 浩 馮 輝

1(云南大學(xué)信息學(xué)院 昆明 650504)2 (云南大學(xué)科技處 昆明 650504)

?

基于貝葉斯網(wǎng)的評價(jià)數(shù)據(jù)分析和動(dòng)態(tài)行為建模

王 飛1岳 昆1孫正寶2武 浩1馮 輝1

1(云南大學(xué)信息學(xué)院 昆明 650504)2(云南大學(xué)科技處 昆明 650504)

(wangfei_989@163.com)

隨著Web2.0的不斷普及和電子商務(wù)應(yīng)用的迅速發(fā)展，大規(guī)模的在線評價(jià)數(shù)據(jù)不斷產(chǎn)生，使用戶行為數(shù)據(jù)分析和用戶行為建模成為可能，具有重要意義.考慮到用戶評價(jià)數(shù)據(jù)和評價(jià)行為的動(dòng)態(tài)性，提出以帶有隱變量的貝葉斯網(wǎng)作為各屬性間依賴關(guān)系及其不確定性表示的基本框架,構(gòu)建既能刻畫用戶評價(jià)數(shù)據(jù)中各屬性間相互依賴的不確定性、也能描述用戶行為動(dòng)態(tài)性的評價(jià)行為模型.首先，以貝葉斯信息標(biāo)準(zhǔn)(BIC)分值作為模型與數(shù)據(jù)擬合度的度量標(biāo)準(zhǔn)，提出基于打分搜索方法來構(gòu)建各時(shí)間片的隱變量模型，并給出基于期望最大(EM)算法的隱變量取值填充方法;其次，基于條件互信息和時(shí)序的不可逆性，提出了相鄰時(shí)間片間隱變量模型的構(gòu)建方法.建立在MovieLens數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果驗(yàn)證了提出的動(dòng)態(tài)用戶行為建模方法的高效性及有效性.

用戶評價(jià)數(shù)據(jù)；時(shí)序性；隱變量模型；貝葉斯網(wǎng)；動(dòng)態(tài)行為建模

隨著Web2.0和電子商務(wù)的迅速發(fā)展，人們越來越多地參與到了網(wǎng)上購物和對商品的評價(jià)中，產(chǎn)生了大規(guī)模的用戶評價(jià)數(shù)據(jù)(簡稱評價(jià)數(shù)據(jù)).這些評價(jià)數(shù)據(jù)，一方面，能有效支持電子商務(wù)應(yīng)用領(lǐng)域中的個(gè)性化推薦、行為定向和計(jì)算廣告等問題[1]的解決.例如實(shí)際應(yīng)用中，用戶的評價(jià)行為反映了用戶偏好[2]，即用戶對特定商品類型的喜好或傾向.因此，商家可以在評價(jià)數(shù)據(jù)分析的基礎(chǔ)上建立用戶評價(jià)行為模型，從而預(yù)測用戶的興趣特點(diǎn)和購買行為，并根據(jù)不同的用戶興趣或偏好制定合理的個(gè)性化營銷策略，準(zhǔn)確地給用戶推薦其感興趣的商品[1]；另一方面，評價(jià)數(shù)據(jù)和評價(jià)行為具有動(dòng)態(tài)性[1]，也就是說，新的評價(jià)數(shù)據(jù)不斷追加，且用戶評價(jià)行為也隨時(shí)間推移而逐漸演化，如圖1所示.這使得精準(zhǔn)捕獲用戶偏好方法的研究具有實(shí)際意義，也具有一定的挑戰(zhàn).因此，分析用戶的評價(jià)數(shù)據(jù)、對用戶評價(jià)行為進(jìn)行建模、發(fā)現(xiàn)用戶偏好，成為了近年來數(shù)據(jù)分析和知識發(fā)現(xiàn)領(lǐng)域研究的熱點(diǎn)之一.

Fig. 1 An example of user behaviors evolved over time among variables圖1 用戶行為隨時(shí)間演化例子

基于用戶評價(jià)數(shù)據(jù)分析的時(shí)序評價(jià)行為建模，是用戶行為分析和預(yù)測的核心和關(guān)鍵，也是數(shù)據(jù)密集型計(jì)算在社會(huì)數(shù)據(jù)分析方面亟待解決的問題.近年來，已經(jīng)有許多研究成果.例如文獻(xiàn)[3]從帶有時(shí)序特征的用戶評價(jià)數(shù)據(jù)出發(fā)，提出評價(jià)數(shù)據(jù)較少情形下的商品服務(wù)評估模型；文獻(xiàn)[4]基于概率張量分解技術(shù)提出能有效挖掘用戶偏好的時(shí)序評價(jià)行為預(yù)測及推薦模型;文獻(xiàn)[5]提出采用用戶歷史反饋信息的時(shí)序雙線性概率模型，實(shí)現(xiàn)對用戶偏好的描述和追蹤.這些帶有時(shí)序特征的用戶行為建模方法，能夠較好反映并體現(xiàn)用戶評價(jià)行為的動(dòng)態(tài)性.然而，我們把觀測到的評價(jià)數(shù)據(jù)中的屬性視為顯變量(manifest variable)，把潛在的用戶偏好視為隱變量(latent variable)，顯變量和隱變量之間存在依賴關(guān)系，且這種依賴關(guān)系具有不確定性，如圖2所示，在這樣的情形下，以上建模方法難以描述用戶評價(jià)數(shù)據(jù)中相關(guān)屬性間帶有不確定性的依賴關(guān)系，進(jìn)而也無法細(xì)致地刻畫用戶行為影響因素之間的依賴關(guān)系.因此，探尋適應(yīng)在不確定因素下能夠?qū)τ脩粼u價(jià)行為進(jìn)行有效推理的模型和建模方法，具有重要的意義.

Fig. 2 An example of uncertain relationships圖2 變量間不確定性關(guān)系例子

貝葉斯網(wǎng)[6](Bayesian network, BN)是由一組隨機(jī)變量(即節(jié)點(diǎn))及各節(jié)點(diǎn)的條件概率表(conditional probability table, CPT)構(gòu)成的有向無環(huán)圖(directed acyclic graph, DAG).作為不確定性知識發(fā)現(xiàn)和推理的有效工具，它不僅克服了樸素貝葉斯模型為代表的一類方法不能客觀描述用戶評價(jià)數(shù)據(jù)中性間依賴關(guān)系的不足，且為多個(gè)變量之間任意形式的依賴關(guān)系及其不確定性建模提供了參考.同時(shí)，伴隨著評價(jià)數(shù)據(jù)時(shí)序性和評價(jià)行為的動(dòng)態(tài)變化，貝葉斯網(wǎng)能夠?qū)τ脩襞d趣模型進(jìn)行實(shí)時(shí)更新，從而更好地適應(yīng)用戶不斷改變的興趣[5].

含隱變量的BN簡稱為隱變量模型[6]，由于其中的隱變量能匯聚用戶評價(jià)數(shù)據(jù)中相關(guān)變量之間的依賴關(guān)系、簡化模型結(jié)構(gòu)，且可以大幅降低用戶評價(jià)行為模型構(gòu)建和推理的復(fù)雜度，在表達(dá)用戶評價(jià)數(shù)據(jù)中相關(guān)屬性和用戶行為之間的不確定性上具有明顯的優(yōu)勢，因此被廣泛用于用戶偏好發(fā)現(xiàn)和行為建模等應(yīng)用領(lǐng)域.例如文獻(xiàn)[7]用顯變量對應(yīng)各個(gè)評價(jià)指標(biāo)，用一個(gè)影響其他顯變量的隱變量來表示最終的用戶評價(jià)行為；文獻(xiàn)[8]用隱變量刻畫用戶的信任偏好，根據(jù)變量的含義給出模型的DAG結(jié)構(gòu)；文獻(xiàn)[9]提出了基于隱語義概率模型的用戶偏好預(yù)測方法，用于個(gè)性化服務(wù)推薦.這些隱變量模型構(gòu)建方法，為本文中的模型構(gòu)建提供了參考，但針對用戶行為時(shí)序性的模型構(gòu)建仍需要進(jìn)一步的研究.

基于隱變量模型的時(shí)序行為建模，目前，也有許多工作，例如文獻(xiàn)[1]將用戶偏好和時(shí)間情景視為影響用戶評價(jià)行為的隱變量，提出能鑒別用戶評價(jià)行為的動(dòng)態(tài)用戶評價(jià)行為模型；文獻(xiàn)[10]基于時(shí)序用戶數(shù)據(jù)提出能追蹤用戶行為變化的時(shí)序用戶行為模型；文獻(xiàn)[11]提出基于隱式用戶反饋的實(shí)時(shí)個(gè)性化推薦方法.然而，以上根據(jù)變量含義而給定的隱變量模型結(jié)構(gòu)，缺乏對數(shù)據(jù)中相關(guān)屬性間任意形式依賴關(guān)系的客觀描述.且由于無法從用戶評價(jià)數(shù)據(jù)中獲得隱變量自身的取值，使得時(shí)序評價(jià)行為模型的構(gòu)建與傳統(tǒng)BN的構(gòu)建不同，即隱變量與顯變量之間依賴關(guān)系的確定及隱變量值的填補(bǔ)計(jì)算方面，存在著較大差異[12].又因?yàn)樵u價(jià)數(shù)據(jù)具有時(shí)序性，需構(gòu)建時(shí)序隱變量模型來體現(xiàn)用戶行為的動(dòng)態(tài)性，這使得含隱變量的時(shí)序評價(jià)行為模型的構(gòu)建具有挑戰(zhàn)性.

基于上述分析，本文基于含隱變量的概率圖模型研究時(shí)序評價(jià)數(shù)據(jù)中的行為建模方法，即從帶有時(shí)序特征的用戶評價(jià)數(shù)據(jù)出發(fā)，首先，針對每個(gè)時(shí)間片構(gòu)建用于描述用戶評價(jià)數(shù)據(jù)中相關(guān)變量間依賴關(guān)系的DAG結(jié)構(gòu)，稱為評價(jià)行為模型(rating behavior model, RBM)；然后，構(gòu)建相鄰時(shí)間片間描述相關(guān)變量間依賴關(guān)系的DAG，從而得到既能反映屬性間相互依賴的不確定性，也能反映用戶評價(jià)行為動(dòng)態(tài)性的時(shí)序評價(jià)行為模型(time-series rating behavior model, TRBM).

具體而言，本文的主要工作可概括為4個(gè)方面：

1) 各時(shí)間片中RBM構(gòu)建的關(guān)鍵在于其DAG的構(gòu)建，需要確定變量間的相互依賴關(guān)系，進(jìn)而確定有向邊的方向.期望最大(expectation maximization, EM)算法是尋找參數(shù)最大似然或者最大后驗(yàn)估計(jì)的有效算法[13]，我們首先采用EM算法對隱變量的值進(jìn)行填充.經(jīng)典的用于BN結(jié)構(gòu)學(xué)習(xí)的打分搜索和爬山算法[7]簡單規(guī)范、易于確定邊的方向.因此，本文以貝葉斯信息標(biāo)準(zhǔn)(Bayesian information criterion, BIC)評分函數(shù)為尺度，選擇BIC評分值最高的候選模型作為各時(shí)間片的RBM，給出了用于構(gòu)建各時(shí)間片內(nèi)RBM的打分搜索算法.

2) 為了構(gòu)建相鄰時(shí)間片間的DAG，我們考慮時(shí)序的不可逆性(即有向邊的方向只能從前一個(gè)時(shí)間片中的變量指向后一個(gè)時(shí)間片中的變量)，因此，只需確定變量間的相關(guān)性，無需確定有向邊的方向.條件互信息為描述隨機(jī)變量間的相關(guān)性提供了良好的基礎(chǔ)，本文使用條件互信息來測試相鄰時(shí)間片間用戶評價(jià)數(shù)據(jù)中變量間的條件獨(dú)立性[14-15]，進(jìn)而確定它們之間存在的相關(guān)性、判斷節(jié)點(diǎn)間是否存在相連的邊，給出了構(gòu)建相鄰時(shí)間片中變量間DAG的算法.

3) 在構(gòu)建的DAG基礎(chǔ)上，本文給出基于最大似然(maximum likelihood, ML)估計(jì)的TRBM中各節(jié)點(diǎn)CPT計(jì)算方法，從而得到完整的TRBM.

4) 建立在MovieLens數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，驗(yàn)證了本文所提出方法的高效性和有效性.

1 問題描述及模型定義

例1. 用戶對電影的評價(jià)數(shù)據(jù)包含屬性userID，type，rating.其中userID為用戶標(biāo)識，type為電影類型，rating為用戶對電影的評分.鑒于討論的方便，我們將rating的取值簡化為low或high.表1展示了相鄰時(shí)間片中用戶對電影的評價(jià)數(shù)據(jù)片段.

Table 1 User Rating Data in Adjacent Time Slices表1 相鄰時(shí)間片中的用戶評價(jià)數(shù)據(jù)

P(X(t0),X(t1),…,X(tm))=P(X(t0))P(X(t1)|

X(t0))…P(X(tm)|X(t0),X(t1),…,X(tm-1))，

(1)

式(1)可解釋為ti時(shí)間片中的用戶評價(jià)行為會(huì)對其后所有時(shí)間片中的評價(jià)行為產(chǎn)生影響，而這樣的模型復(fù)雜度太高、實(shí)現(xiàn)代價(jià)太大.因此，假設(shè)當(dāng)前用戶評價(jià)行為只與前一個(gè)時(shí)間片有關(guān)，即X(ti+1)條件獨(dú)立于X(tj)，其中j

P(X(t0),X(t1),…,X(tm))=P(X(t0))P(X(t1)|

X(t0))…P(X(tm)|X(tm-1)).

(2)

可見，用戶評價(jià)數(shù)據(jù)中變量的相互依賴關(guān)系，同時(shí)存在于同一個(gè)時(shí)間片中，以及相鄰時(shí)間片之間.其中,X(ti)描述了時(shí)間片ti中用戶評價(jià)數(shù)據(jù)相關(guān)屬性間的任意依賴關(guān)系(即RBM)；P(X(ti+1)|X(ti))描述了相鄰時(shí)間片間用戶評價(jià)數(shù)據(jù)相關(guān)變量間的依賴關(guān)系，體現(xiàn)了用戶評價(jià)行為的動(dòng)態(tài)性；直觀地，P(X(ti))，P(X(ti+1))，P(X(ti+1)|X(ti))由TRBM表達(dá).

例如，電影評分?jǐn)?shù)據(jù)實(shí)例“userID=1，type=2，rating=high，H=1”，表示userID=1的用戶喜好type=2的電影，對應(yīng)的評分較高(即rating=high).

2 時(shí)序評價(jià)行為模型構(gòu)建

本節(jié)首先給出用于隱變量取值填充的EM算法；然后給出各時(shí)間片中RBM模型的構(gòu)建算法；接著給出相鄰時(shí)間片中DAG的構(gòu)建算法,得到TRBM模型；最后，給出TRBML模型中參數(shù)的計(jì)算方法.

2.1 各時(shí)間片中的RBM構(gòu)建

在機(jī)器學(xué)習(xí)領(lǐng)域，BN結(jié)構(gòu)構(gòu)建的經(jīng)典算法思想為[6]：從任意的初始模型開始，對其采用爬山算法進(jìn)行加邊、減邊和反向邊搜索，得到若干候選模型后，計(jì)算和比較這些候選模型與數(shù)據(jù)的吻合程度(稱為打分值)，從而選擇分值最高的模型為候選模型.本文借鑒該思路，同時(shí)考慮到評價(jià)數(shù)據(jù)中不包含隱變量的值這一特點(diǎn)，首先，采用EM算法對隱變量進(jìn)行取值填充；然后，計(jì)算各候選模型的BIC分值，選擇BIC分值最高的候選模型作為各時(shí)間片中的RBM.

2.1.1 基于EM算法的隱變量取值填充

對于給定的DAG結(jié)構(gòu)，采用EM算法對含有N個(gè)實(shí)例的評價(jià)數(shù)據(jù)集Dti的隱變量值進(jìn)行填充時(shí)，從隨機(jī)產(chǎn)生的初始值θ0開始迭代，設(shè)已經(jīng)進(jìn)行了l次迭代，參數(shù)估計(jì)結(jié)果為θl.第l+1次迭代過程：

1) E步驟

首先，根據(jù)Dti中顯變量的值和參數(shù)θl，如式(3)所示，計(jì)算每一個(gè)評價(jià)實(shí)例中H的每一個(gè)可能取值的概率:

(3)

(4)

其中，X1,X2,…,Xn為給定DAG結(jié)構(gòu)中的n個(gè)節(jié)點(diǎn)，Xi有ri個(gè)取值，Xi的父節(jié)點(diǎn)π(Xi)有qi種組合，若Xi無父節(jié)點(diǎn)，則qi=1.

2) M步驟

基于填充后的完整數(shù)據(jù)計(jì)算θ的最大似然估計(jì)，得到θl+1ijk:

(5)

迭代執(zhí)行上述E步驟和M步驟，直到按式(6)計(jì)算得到的θl和θl+1的對數(shù)似然值不再變化，選擇概率最高的取值作為最終填充值.上述思想見算法1.

(6)

算法1. 隱變量取值填充：FillValue(G,Dti,δ).

輸入：δ—收斂閾值、Dti—ti中無隱變量值的評價(jià)數(shù)據(jù)集、G—ti中爬山算法得到的候選DAG；

輸出:Dti—ti中完整的用戶評價(jià)數(shù)據(jù)集.

步驟：

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

oldScore←L(θl|Dti)；

while(true)

E-步驟：

按式(3)計(jì)算H取值概率；

按式(4)計(jì)算H取值概率和；

M-步驟：

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

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

newScore←L(θl+1|Dti)；

if (newScore-oldScore>δ)

oldScore←newScore；

l←l+1；

else

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

returnDti;

end if

end while

例2. 給定DAG結(jié)構(gòu)及初始參數(shù)θ0，分別如圖3(a)和圖3(b)所示，采用算法1進(jìn)行隱變量值填充，首先，按式(3)分別計(jì)算每個(gè)評價(jià)實(shí)例中隱變量每一種可能取值的概率，如針對(1,2,high,0)和(1,2,high,1)分別計(jì)算出概率為0.2和0.8.然后，分別按式(4)和式(5)計(jì)算得到新參數(shù)θ1，如圖3(c)所示.接著，按式(6)計(jì)算并比較參數(shù)θ0和θ1的對數(shù)似然值，L(θ1|Dti)-L(θ0|Dti)=-2 771.293 5-(-6 211.653 2)=3 440.359 8，直到該值小于所設(shè)定的收斂閾值δ，即對數(shù)似然值基本不再變化時(shí)，選擇概率最大的取值作為該評價(jià)實(shí)例的填充值.

Fig. 3 Latent variable filling based on Algorithm 1圖3 基于算法1的隱變量值填充

2.1.2 基于BIC評分標(biāo)準(zhǔn)的RBM構(gòu)建

對于時(shí)間片ti，采用爬山算法進(jìn)行搜索后得到的若干個(gè)候選模型結(jié)構(gòu)，首先，2.1.1節(jié)給出隱變量值填充算法；然后，通過式(7)分別計(jì)算出每一個(gè)候選模型的BIC分值.最后，比較并選擇BIC分值最高的模型作為當(dāng)前模型.重復(fù)搜索迭代，直至BIC分值不再變化后，選擇分值最高的候選模型作為ti時(shí)間片中的RBM.

(7)

其中，X1,X2,…,Xn為候選結(jié)構(gòu)S包含的n個(gè)節(jié)點(diǎn)，Xi有ri個(gè)取值，Xi的父節(jié)點(diǎn)π(Xi)有qi種組合，若Xi無父節(jié)點(diǎn)，則qi=1；mijk為Dti中Xi=k(1≤k≤ri)且π(Xi)=j(1≤j≤qi)的實(shí)例數(shù)，mij為Dti中π(Xi)=j的數(shù)據(jù)實(shí)例數(shù)；N為Dti中數(shù)據(jù)實(shí)例數(shù).

上述模型構(gòu)建思想見算法2.

Fig. 4 Candidate RBM model by algorithm 2圖4 基于算法2得到的候選RBM

算法2. RBM構(gòu)建：LearnBN-HC(X,Dti,f,?0,δ).

輸入：X—用戶評價(jià)屬性集Uti、δ—收斂閾值、f=ScoreBIC(?|Dti)—模型選擇BIC打分函數(shù)、Dti—ti中評價(jià)數(shù)據(jù)集、?0—初始DAG結(jié)構(gòu)；

步驟：

?←?0；

θ←FillValue(?,Dti,σ)；

oldScore←ScoreBIC(?|Dti)；

while (true)

?*←null；

θ*←null；

newScore←-∞；

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

θ′←FillValue(?′,Dti,σ)；

tempScore←ScoreBIC(?′|Dti)；

if (tempScore>newScore)

?*←?′；

θ*←θ′；

newScore←tempScore；

end if

end for

if (newScore>oldScore)

?←?*；

θ←θ*；

oldScore←newScore；

else return ?；

end if

end while

對于含有n個(gè)變量的RBM構(gòu)建，算法2中，爬山法搜索執(zhí)行一次時(shí)共需要產(chǎn)生O(n2)個(gè)獲選模型且每一個(gè)候選結(jié)構(gòu)需要調(diào)用一次算法1進(jìn)行隱變量值的填充，因此需要調(diào)用O(n2)次算法1.對算法2的效率我們將通過實(shí)驗(yàn)進(jìn)行進(jìn)一步測試.

例3. 若圖4(a)為當(dāng)前模型?1，圖4(b)是執(zhí)行算法2時(shí)刪去邊(H→rating)后得到的候選模型?2.首先，采用算法1對?2中隱變量的值進(jìn)行填充.然后，計(jì)算得到?1和?2對于Dti的ScoreBIC分值分別為：ScoreBIC(?1|Dti)=-4 190.4，ScoreBIC(?2|Dti)=-4 272.7，由于，ScoreBIC(?1|Dti)=max{ScoreBIC(?1|Dti)，ScoreBIC(?2|Dti)}，因此，選擇?1為當(dāng)前RBM.繼續(xù)重復(fù)搜索過程，直至ScoreBIC分值不再變化為止，從而可得到時(shí)間片ti中的RBM.

2.2 基于條件互信息的相鄰時(shí)間片間DAG結(jié)構(gòu)構(gòu)建

為了構(gòu)建相鄰時(shí)間片的DAG結(jié)構(gòu)，我們基于互信息測試變量間的條件獨(dú)立性，進(jìn)而確定它們之間是否存在相關(guān)性，定義4首先給出互信息的概念.

定義4. 設(shè)U=Uti∪Uti+1，X，Y和Z為U的3個(gè)互不相交子集，給定條件Z的情況下，X和Y的條件互信息定義為

I(X|Z|Y)=

(8)

其中，X ?Uti,Y ?Uti+1，Z ?Uti∪Uti+1-X-Y，x,y和z分別為X,Y和Z的取值，

P(x,y,z)=

若I(X|Z|Y)≤ε成立，則給定Z條件下X和Y條件獨(dú)立,即P(X,Y|Z)=P(X|Z)P(Y|Z).否則不獨(dú)立，即P(X,Y|Z)≠P(X|Z)P(Y|Z).其中ε為給定的閾值.

基于上述思想給出相鄰時(shí)間片間DAG構(gòu)建算法，如算法3所示.

步驟：

forl=1 tondo

forj=1 tondo

I←CItests(P,Q,R,ε,Dti,Dti)；

ifI≤εthen

S←R；

end if

end for

end for

算法3中，CItests()操作共執(zhí)行O(n2)次，其中n為Uti中屬性的個(gè)數(shù).由于有向邊的方向只能從ti中的變量指向ti+1中的變量，因此，CItests()很大程度上避免了不必要的測試.算法3的性能將通過實(shí)驗(yàn)進(jìn)行進(jìn)一步測試.

例4. 如表1所示，時(shí)間片ti和ti+1中用戶評價(jià)數(shù)據(jù)集為Dti和Dti+1，屬性集Uti=Uti+1={userID,type,rating}.對于userIDti和typeti+1，令X={userIDti}，Y={typeti+1}，Z?Uti-X∪Uti+1-Y={typeti,ratingti,userIDti+1,ratingti+1}，按照式(8)計(jì)算得到userIDti和typeti+1的條件互信息為

.

同理，我們計(jì)算相鄰時(shí)間片中其他所有變量間的條件互信息，基于算法3得到圖5中的TRBM結(jié)構(gòu).

Fig. 5 Time-series rating behavior model圖5 時(shí)序評價(jià)行為模型

2.3 時(shí)序評價(jià)行為模型的參數(shù)計(jì)算

構(gòu)建時(shí)間片ti(0≤i≤m)中的RBM時(shí)，已經(jīng)通過EM算法對隱變量的值進(jìn)行了填充.因此，可以通過計(jì)算最大似然估計(jì)的方法來得到TRBM的參數(shù)：

(9)

其中，D是用戶評價(jià)數(shù)據(jù)集，計(jì)算ti時(shí)間片中的最大似然估計(jì)時(shí)，D=Dti；計(jì)算相鄰時(shí)間片間的最大似然估計(jì)時(shí)，D=Dti∪Dti+1.

基于最大似然估計(jì)算法思想，下面我們給出TRBM參數(shù)計(jì)算方法如算法4所示.

算法4. 參數(shù)計(jì)算LearnPRM-ML(Dti,Dti).

輸入：Dti—ti中用戶評價(jià)數(shù)據(jù)集、Dti—ti+1中用戶評價(jià)數(shù)據(jù)集；

輸出：θ—TRBM的參數(shù)估計(jì).

步驟：

if (計(jì)算時(shí)間片ti中DAG參數(shù)) then

D←Dti；

else

D←Dti∪Dti+1；

end if

returnθ.

例5. 對于圖5中的TRBM，相鄰時(shí)間片間的參數(shù)：P(Hti+1=0|typeti=1,ratingti=high)=Num(Hti+1=0|typeti=1,ratingti=high)(Num(Hti+1=0|typeti=1,ratingti=high)+Num(Hti+1=1|typeti=1,ratingti=high)) =0.25，Num()表示滿足條件的實(shí)例數(shù).同理，我們可以計(jì)算得到如圖5所示的TRBM中所有節(jié)點(diǎn)的參數(shù).

3 實(shí)驗(yàn)結(jié)果

為了測試本文提出方法的有效性和高效性，本文使用GroupLens的電影評分?jǐn)?shù)據(jù)集MovieLens[16]，其中包括1996—2016年11 327個(gè)用戶對20種電影類型的共1 048 576行評價(jià)數(shù)據(jù)，包括：userID，type，rating，timestamp四個(gè)變量.我們用timestamp將數(shù)據(jù)集按照年份劃分成20個(gè)時(shí)間片數(shù)據(jù)片，userID，type，rating作為TRBM每個(gè)時(shí)間片的DAG中的節(jié)點(diǎn).

實(shí)驗(yàn)環(huán)境如下：Intel?CoreTMi3-3240 CPU 3.40 GHz處理器；4.00 GB內(nèi)存；Windows7 64 b操作系統(tǒng)；MATLAB R2014b開發(fā)平臺.

3.1 基準(zhǔn)描述

μ-rating[17]也稱mean-r[17]，是一種傳統(tǒng)、簡單的評分預(yù)測方法，它的基本思想是采用所有用戶評價(jià)的平均值，對缺失的數(shù)據(jù)進(jìn)行填充.

SVD[17-18](singular value decomposition)是協(xié)同過濾[19]中常見的評分預(yù)測算法.其基本思想是先采用梯度下降算法計(jì)算得到2個(gè)完整的矩陣;然后，用2個(gè)矩陣運(yùn)算得到的值，對缺失的數(shù)據(jù)進(jìn)行填充.

TT[20](time-topic model)是一種主題模型.該模型假設(shè)主題是由時(shí)間背景產(chǎn)生的，即用戶的行為受時(shí)間背景的影響；不考慮用戶興趣對主題或行為的影響.其概率為

P(v|t;ψ)=λBP(v|θB)+

BPTF[4](Bayesian probabilistic tensor factoriza-tion)是概率張量分解技術(shù)針對時(shí)序特征的拓展，是一種目前主流的評價(jià)行為預(yù)測模型.

TCAM[1](temporal context-aware mixture model)是一種用戶行為預(yù)測模型，同時(shí)考慮了用戶興趣和時(shí)間背景對用戶評價(jià)行為的影響.概率為

3.2 TRBM構(gòu)建效率

Fig. 6 Execution time with the increase of nodes圖6 增加節(jié)點(diǎn)數(shù)測試運(yùn)行時(shí)間

我們首先測試了相同用戶評價(jià)數(shù)據(jù)量情形下，隨著節(jié)點(diǎn)數(shù)的增加使用本文方法和傳統(tǒng)的BN學(xué)習(xí)方法來構(gòu)建TRBM的運(yùn)行時(shí)間，如圖6所示；同時(shí)，測試了相同節(jié)點(diǎn)數(shù)的情形下，隨著用戶評價(jià)數(shù)據(jù)量增加使用2種方法構(gòu)建TRBM的運(yùn)行時(shí)間，如圖7所示.可以看出，使用本文方法構(gòu)建TRBM的執(zhí)行時(shí)間比基于BN學(xué)習(xí)方法構(gòu)建TRBM的執(zhí)行時(shí)間少，這從一定程度上說明了本文構(gòu)建TRBM的方法具有高效性.其次，我們針對上述2種情形，分別測試了TRBM構(gòu)建過程中算法1、算法2和算法3的執(zhí)行時(shí)間，如圖8和圖9所示.可以看出，構(gòu)建TRBM時(shí)算法1計(jì)算隱變量填充值的耗時(shí)最多.因?yàn)?，算?每執(zhí)行1次爬山搜索需要調(diào)用O(n2)次算法1來填充數(shù)據(jù)，因此，這成為了影響TRBM構(gòu)建效率的瓶頸.

Fig. 7 Execution time with the increase of user rating data圖7 增加用戶評價(jià)數(shù)據(jù)量測試運(yùn)行時(shí)間

Fig. 8 Execution time of algorithm 1-3 with the increase of nodes圖8 隨著節(jié)點(diǎn)數(shù)增加各算法的執(zhí)行時(shí)間

Fig. 9 Execution time of algorithm 1-3 with the increase of user rating data圖9 增加用戶評價(jià)數(shù)據(jù)量各算法執(zhí)行時(shí)間

3.3 填充數(shù)據(jù)準(zhǔn)確性

我們將MovieLens數(shù)據(jù)集中能夠觀測到值的顯變量rating值視為空值，采用本文算法1、μ-rating方法及SVD方法對其值進(jìn)行填充.鑒于均方根能夠反映填補(bǔ)數(shù)據(jù)與真實(shí)數(shù)據(jù)的接近程度，即均方根值越小，填補(bǔ)的值與真實(shí)值越接近.我們計(jì)算填補(bǔ)數(shù)據(jù)與真實(shí)用戶評價(jià)數(shù)據(jù)間的均方根值:

(10)

如圖10所示，算法1對隱變量值填補(bǔ)的均方根值最小，表明相比于μ-rating方法和SVD方法，算法1能夠更為準(zhǔn)確地填充隱變量的值，且隨著評價(jià)數(shù)量的增加，算法1填充數(shù)據(jù)的準(zhǔn)確性增加.

Fig. 10 Accuracy of filled data圖10 填充數(shù)據(jù)的準(zhǔn)確性

3.4 TRBM有效性

我們將20個(gè)時(shí)間片數(shù)據(jù)中的前80%作為建模數(shù)據(jù)，后20%作為測試數(shù)據(jù)，并將測試數(shù)據(jù)中，所有用戶評價(jià)為”high”的電影類型視為用戶偏好的類型.測試了TRBM，TT，BPTF，TCAM用戶行為預(yù)測的準(zhǔn)確率(precision)和覆蓋率(coverage).其中，用precision@k表示TRBM返回k個(gè)用戶偏好的準(zhǔn)確率，用coverage@k表示TRBM返回k個(gè)用戶偏好的覆蓋率:

(11)

(12)

其中，Num(preference)是TRBM模型計(jì)算出的k個(gè)電影類型中實(shí)際為用戶偏好的電影類型數(shù),Num(Allpreference)是實(shí)際用戶偏好的電影類型數(shù).

進(jìn)一步，我們測試了反映準(zhǔn)確率和覆蓋率綜合性能的F1值:

(13)

Fig. 11 Precision圖11 準(zhǔn)確率

Fig. 12 Coverage圖12 覆蓋率

Fig. 13 F1 score圖13 F1值

準(zhǔn)確率、覆蓋率和F1值分別如圖11、圖12和圖13所示，不難看出TRBM對用戶行為預(yù)測的準(zhǔn)確率、覆蓋率、F1值均高于其他動(dòng)態(tài)行為模型，這從一定程度上驗(yàn)證了本文所提出方法的有效性.

4 總結(jié)與展望

本文針對用戶評價(jià)數(shù)據(jù)具有時(shí)序性和評價(jià)行為具有動(dòng)態(tài)性的特點(diǎn)，提出了一種既可以描述用戶評價(jià)數(shù)據(jù)相關(guān)屬性間任意依賴關(guān)系、又可以反映用戶評價(jià)行為動(dòng)態(tài)性的時(shí)序評價(jià)行為模型,實(shí)驗(yàn)驗(yàn)證了本文所提出方法的高效性和有效性.

本文的研究為針對一段時(shí)間內(nèi)多個(gè)時(shí)間片的動(dòng)態(tài)行為模型構(gòu)建、用戶不同偏好之間的聯(lián)系提供了一種思路.但是，作為這一問題的初步探索，在針對新追加的評分?jǐn)?shù)據(jù)來定量地確定模型中需要修改的部分，從而對當(dāng)前模型進(jìn)行增量修改，而不需要重新學(xué)習(xí)，以保證模型構(gòu)建的高效性和實(shí)時(shí)性，仍然需要進(jìn)一步研究，也是我們將要開展的工作.

[1]Yin Hongzhi, Cui Bin, Chen Ling, et al. Dynamic user modeling in social media systems[J]. ACM Trans on Information Systems, 2015, 33(3): Article No.10

[2]McAuley J, Leskovec J. Hidden factors and hidden topics: Understanding rating dimensions with review text[C]Proc of the 7th ACM Conf on Recommender Systems. New York: ACM, 2013: 165-172

[3]Zhao Guoshuai, Qian Xueming, Xie Xing. User service rating prediction by exploring social users’ rating behaviors[J]. IEEE Trans on Multimedia, 2016, 18(3): 496-506

[4]Xiong Liang, Chen Xi, Huang Tzu-Kuo, et al. Temporal collaborative filtering with Bayesian probabilistic tensor factorization[C]Proc of the 2010 SIAM Int Conf on Data Mining. Philadelphia, PA: SIAM, 2010: 211-222

[5]Luo Cheng, Cai Xiongcai, Chowdhury N. Probabilistic temporal bilinear model for temporal dynamic recommender systems[C]Proc of 2015 Int Joint Conf on Neural Networks. Piscataway, NJ: IEEE, 2015: 1-8

[6]Zhang Lianwen, Guo Haipeng. Introduction to Bayesian Networks[M]. Beijing: Science Press, 2006 (in Chinese)(張連文, 郭海鵬. 貝葉斯網(wǎng)引論[M]. 北京: 科學(xué)出版社, 2006)

[7]Kim J S, Jun C H. Ranking evaluation of institutions based on a Bayesian network having a latent variable[J]. Knowledge-Based Systems, 2013, 50(3): 87-99

[8]Fang Hui, Bao Yang, Zhang Jie. Misleading opinions provided by advisors: Dishonesty or subjectivity[C]Proc of the 23rd Int Joint Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 2013: 1983-1989

[9]Hu Yan, Peng Qimin, Hu Xiaohui. A personalized Web service recommendation method based on latent semantic probabilistic model[J]. Journal Computer Research and Development, 2014, 51(8): 1781-1793 (in Chinese)(胡堰, 彭啟民, 胡曉惠. 一種基于隱語義概率模型的個(gè)性化Web服務(wù)推薦方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(8): 1781-1793)

[10]Kapoor K, Subbian K, Srivastava J, et al. Just in time recommendations: Modeling the dynamics of boredom in activity streams[C]Proc of the 8th ACM Int Conf on Web Search and Data Mining. New York: ACM, 2015: 233-242

[10]Kapoor K, Subbian K, Srivastava J, et al. Just in time recommendations: Modeling the dynamics of boredom in activity streams[C]Proc of the 8th ACM Int Conf on Web Search and Data Mining. New York: ACM, 2015: 233-242

[11]Wang Zhisheng, Li Qi, Wang Jing, et al. Real time personalized recommendation based on implicit user feedback data stream[J]. Chinese Journal of Computers, 2016, 39(1): 52-64 (in Chinese)(王智圣, 李琪, 汪靜, 等. 基于隱式用戶反饋數(shù)據(jù)流的實(shí)時(shí)個(gè)性化推薦[J]. 計(jì)算機(jī)學(xué)報(bào), 2016, 39(1): 52-64)

[12]Yue Kun, Fang Qiyu, Wang Xiaoling, et al. A parallel and incremental approach for data intensive learning of Bayesian networks[J]. IEEE Trans on Cybernetics, 2015, 45(12): 2890-2267

[13]Dempster A P. Maximum likelihood from incomplete data via the EM algorithm[J]. Journal of the Royal Statistical Society, 1977, 39(1): 1-38

[14]Wang Shuangcheng, Yuan Senmiao. Research on learning Bayesian networks structure with missing data[J]. Journal of Software, 2004, 15(7): 1042-1048 (in Chinese)(王雙成, 苑森淼. 具有丟失數(shù)據(jù)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)研究[J]. 軟件學(xué)報(bào), 2004, 15(7): 1042-1048)

[15]Liu Weiyi, Yue Kun, Liu Shuangxian, et al. Qualitative probabilistic network based modeling of temporal causalities and its application to feedback loop identification[J]. Information Sciences, 2008, 178(7): 1803-1824

[16]GroupLens. MovieLens data sets[EBOL]. [2016-02-28]. http:grouplens.orgdatasetsmovielenslatest

[17]Harvey M, Carman M J, Ruthven I, et al. Bayesian latent variable models for collaborative item rating prediction[C]Proc of the 20th ACM Conf on Information and Knowledge Management. New York: ACM, 2011: 699-708

[18]Zhao Guoshuai, Qian Xueming. Service objective evaluation via exploring social users’ rating behaviors[C]Proc of 2015 IEEE Int Conf on Multimedia Big Data. Piscataway, NJ: IEEE, 2015: 228-235

[19]Sun Guangfu, Wu Le, Liu Qi, et al. Recommendations based on collaborative filtering by exploiting sequential behaviors[J]. Journal of Software, 2013, 24(11): 2721-2733 (in Chinese)(孫光福, 吳樂, 劉淇, 等. 基于時(shí)序行為的協(xié)同過濾推薦算法[J]. 軟件學(xué)報(bào), 2013, 24(11): 2721-2733)

[20]Wang Xuanhui, Zhai Chengxiang, Hu Xiao, et al. Mining correlated bursty topic patterns from coordinated text streams[C]Proc of the 13th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2007: 784-793

Wang Fei, born in 1989. Master candidate at Yunnan University, and student member of CCF. His main research interests include uncertain data knowledge discovery and social media data analysis.

Sun Zhengbao, born in 1985. Received his MS degree in 2012. Experimentalist at Department of Science and Technology， Yunnan University. His main research interests include massive spatial data analysis.

Wu Hao, born in 1979. Received his PhD degree in computer science from Huazhong University of Science and Technology in 2007. Associate professor at Yunnan University. His main research interests include information retrieval, recommendation system and service computing.

Feng Hui, born in 1993. Master candidate at Yunnan University. His main research interests include uncertain data knowledge discovery and social media data analysis.

Analyzing Rating Data and Modeling Dynamic Behaviors of Users Based on the Bayesian Network

Wang Fei1, Yue Kun1, Sun Zhengbao2, Wu Hao1, and Feng Hui1

1(SchoolofInformationScienceandEngineering,YunnanUniversity,Kunming650504)2(DepartmentofScienceandTechnology,YunnanUniversity,Kunming650504)

With the rapid development of Web2.0 and the e-commerce applications, large-scale online rating data are generated, which makes it possible to analyze users behavior data and model user behaviors. Considering the dynamic property of rating data and user behaviors, in this paper we adopt the Bayesian network with a latent variable (abbreviated as latent variable model) as the framework for describing mutual dependencies and corresponding uncertainties, and then construct the model that can reflect not only the uncertainty of dependence relationships among attributes in rating data but also the dynamic property of user behaviors. We first adopt the Bayesian information criterion (BIC) as the coincidence measure between candidate model and rating data, and then propose the scoring-and-search based method to construct the latent variable model. Then, we give the method for filling latent variable values based on the expectation maximization (EM) algorithm. Further, we propose the method for constructing the latent variable model between adjacent time slices based on conditional mutual information and irreversibility of time series. Finally, experimental results established on the MovieLens data set verify the efficiency and effectiveness of the method proposed in this paper.

user rating data; time-series; latent variable model; Bayesian network; dynamic behavior model

?born in 1979.

his MS degree in computer science from Fudan University in 2004, and received his PhD degree in computer science from Yunnan University in 2009. Professor and PhD supervisor at Yunnan University. His main research interests include massive data analysis and services.

2016-08-02；

2016-10-10

國家自然科學(xué)基金項(xiàng)目(61472345，61562090)；云南省應(yīng)用基礎(chǔ)研究計(jì)劃重點(diǎn)項(xiàng)目(2014FA023)；云南大學(xué)青年英才培育計(jì)劃項(xiàng)目(WX173602)；云南大學(xué)創(chuàng)新團(tuán)隊(duì)培育計(jì)劃項(xiàng)目(XT412011)；云南省教育廳科研基金項(xiàng)目(2016ZZX006) This work was supported by the National Natural Science Foundation of China (61472345,61562090), the Key Program of Applied Basic Research Foundation of Yunnan Province (2014FA023), the Program for Excellent Young Talents of Yunnan University (WX173602), the Program for Innovative Research Team in Yunnan University (XT412011), and the Science Research Foundation of Yunnan Provincial Education Department (2016ZZX006).

岳昆(kyue@ynu.edu.cn)

TP18