面向用戶偏好發(fā)現(xiàn)的隱變量模型構(gòu)建與推理

高 艷，岳 昆，武 浩，付曉東，劉惟一

(1.云南大學(xué) 信息學(xué)院，昆明 650504； 2.昆明理工大學(xué) 信息工程與自動化學(xué)院，昆明 650500)

(*通信作者電子郵箱kyue@ynu.edu.cn)

面向用戶偏好發(fā)現(xiàn)的隱變量模型構(gòu)建與推理

高 艷1，岳 昆1*，武 浩1，付曉東2，劉惟一1

(1.云南大學(xué) 信息學(xué)院，昆明 650504； 2.昆明理工大學(xué) 信息工程與自動化學(xué)院，昆明 650500)

(*通信作者電子郵箱kyue@ynu.edu.cn)

電子商務(wù)應(yīng)用中產(chǎn)生了大量用戶評分?jǐn)?shù)據(jù)，而這些數(shù)據(jù)中富含了用戶觀點(diǎn)和偏好信息，為了能夠從這些數(shù)據(jù)中準(zhǔn)確地推斷出用戶偏好，提出一種面向評分?jǐn)?shù)據(jù)中用戶偏好發(fā)現(xiàn)的隱變量模型(即含隱變量的貝葉斯網(wǎng))構(gòu)建和推理的方法。首先，針對評分?jǐn)?shù)據(jù)的稀疏性，使用帶偏置的矩陣分解(BMF)模型對其進(jìn)行填補(bǔ)；其次，用隱變量表示用戶偏好，給出了基于互信息(MI)、最大半團(tuán)和期望最大化(EM)算法的隱變量模型構(gòu)建方法；最后，給出了基于Gibbs采樣的隱變量模型概率推理和用戶偏好發(fā)現(xiàn)方法。實(shí)驗(yàn)結(jié)果表明，與協(xié)同過濾的方法相比，該方法能有效地描述評分?jǐn)?shù)據(jù)中相關(guān)屬性之間的依賴關(guān)系及其不確定性，從而能夠更準(zhǔn)確地推斷出用戶偏好。

用戶偏好；評分?jǐn)?shù)據(jù)；貝葉斯網(wǎng)；隱變量模型；概率推理；帶偏置的矩陣分解

0 引言

電子商務(wù)和推薦網(wǎng)站等Web 2.0應(yīng)用產(chǎn)生了大量的用戶對商品的評分?jǐn)?shù)據(jù)，而這些評分?jǐn)?shù)據(jù)中則包含了可直接觀測到的用戶和商品本身的屬性，以及用戶對商品的評分等，蘊(yùn)含了用戶對某種商品類型的偏好。近年來，從評分?jǐn)?shù)據(jù)中提取用戶偏好已經(jīng)成為數(shù)據(jù)挖掘、推薦系統(tǒng)和個性化搜索研究的熱點(diǎn)。相對商品類型和用戶評分等可直接觀測到值的變量而言，用戶偏好是隱變量(Latent Variable)。從實(shí)際應(yīng)用看，商品本身的屬性、評分和用戶偏好之間存在相互依賴關(guān)系，且具有不確定性。如何描述上述具有不確定性的依賴關(guān)系，是解決實(shí)際應(yīng)用中針對觀測屬性來提取用戶偏好的關(guān)鍵，進(jìn)而為商品個性化推薦、用戶劃分和虛假評價(jià)檢測等應(yīng)用提供依據(jù)。對此，研究描述各觀測屬性(也稱顯變量)和用戶偏好之間依賴關(guān)系及其不確定性的知識模型構(gòu)建，以及基于該模型進(jìn)行知識推理來發(fā)現(xiàn)用戶偏好的方法，是本文研究的主要任務(wù)和基本思想。

近年來，用戶偏好發(fā)現(xiàn)已有許多研究成果。例如，文獻(xiàn)[1]提出基于用戶認(rèn)知行為的上下文感知的偏好獲取方法；文獻(xiàn)[2]提出一種偏好-主題模型，引入用戶偏好維度來提取用戶偏好。然而，上述工作并未考慮用戶偏好與用戶行為或相關(guān)屬性間的內(nèi)在聯(lián)系，使得發(fā)現(xiàn)的用戶偏好準(zhǔn)確度不高。

通常情況，用戶評分?jǐn)?shù)據(jù)往往比較稀疏。例如，Amazon網(wǎng)站一般存在95%的數(shù)據(jù)缺失[3]，進(jìn)而無法計(jì)算各商品屬性之間的依賴關(guān)系。Salakhutdinov等[4]提出了概率矩陣分解 (Probabilistic Matrix Factorization, PMF)模型，該模型以概率的形式描述評分矩陣和隱含特征矩陣。隨后Salakhutdinov等[5]將PMF擴(kuò)展為貝葉斯概率矩陣分解(Bayesian PMF, BPMF)模型，并用馬爾可夫鏈蒙特卡羅(Markov Chain Monte Carlo, MCMC)方法進(jìn)行訓(xùn)練，該模型的預(yù)測準(zhǔn)確率較高，但BPMF模型是一種線性模型，并不能表示隱含特征之間的非線性關(guān)系。Koren[6]提出了帶偏置的矩陣分解(Biased Matrix Factorization, BMF)模型，該模型對于稀疏性、數(shù)據(jù)擴(kuò)展等問題都有良好的性能。評價(jià)中有很多因素取決于用戶或商品本身的屬性，本文將獨(dú)立于用戶或商品的因素視為偏置部分，將用戶對商品的喜好視為個性化部分，利用矩陣分解中偏置部分對提高評分預(yù)測的準(zhǔn)確率遠(yuǎn)遠(yuǎn)高于個性化部分這一結(jié)論，基于BMF模型來填補(bǔ)缺失的評分值，對評分?jǐn)?shù)據(jù)進(jìn)行預(yù)處理。

作為一種重要的概率圖模型，貝葉斯網(wǎng)(Bayesian Network, BN)[7-8]是不確定性知識表示和推理的有效框架，被廣泛應(yīng)用于數(shù)據(jù)分析和醫(yī)療診斷等領(lǐng)域[9- 10]，它以有向無環(huán)圖(Directed Acyclic Graph, DAG)表示隨機(jī)變量或?qū)傩蚤g的依賴關(guān)系，每個節(jié)點(diǎn)對應(yīng)一個條件概率表(Conditional Probability Table, CPT)，定量地描述變量間的依賴關(guān)系。近年來，基于BN的用戶偏好發(fā)現(xiàn)成為了一類有代表性的方法，例如，文獻(xiàn)[11]提出一種非參數(shù)BN模型和從日志數(shù)據(jù)中提取某個用戶的搜索意圖的方法，文獻(xiàn)[12]提出基于BN從Web服務(wù)的行為來動態(tài)提取用戶偏好的方法。但是，上述方法中，BN的構(gòu)建僅涉及觀測到的數(shù)據(jù)，不能有效發(fā)現(xiàn)隱含關(guān)系，進(jìn)而降低了用戶偏好發(fā)現(xiàn)的準(zhǔn)確性。

隱變量是描述不能直接觀測其取值的變量，含有隱變量的BN簡稱隱變量模型(Latent Variable Model)[7]。Elidan等[13]指出，隱變量模型可以簡化模型結(jié)構(gòu)，使顯變量之間的依賴關(guān)系更清晰，能夠發(fā)現(xiàn)和表示數(shù)據(jù)中的隱含信息。如前所述，評分?jǐn)?shù)據(jù)中蘊(yùn)含的用戶偏好并不能直接觀測得到，自然地，本文用隱變量來表示用戶偏好，以隱變量模型作為研究用戶偏好發(fā)現(xiàn)的基礎(chǔ)。因此，引入隱變量、并用隱變量直接表示用戶偏好，可加強(qiáng)模型對用戶行為模式的表達(dá)能力。文獻(xiàn)[14]提出基于深度學(xué)習(xí)的隱馬爾可夫模型和條件隨機(jī)場來發(fā)現(xiàn)主題偏好的方法，文獻(xiàn)[15]基于隱評論主題模型從評級推薦系統(tǒng)中用戶反饋的短語信息中提取用戶偏好。但以上研究未考慮數(shù)據(jù)中相關(guān)屬性之間任意形式依賴關(guān)系的表示和相應(yīng)的模型構(gòu)建。

根據(jù)構(gòu)建好的隱變量模型，可得到表示用戶偏好的隱變量與其他顯變量之間的依賴關(guān)系，因此考慮利用隱變量模型的概率推理機(jī)制，計(jì)算給定證據(jù)變量情形下隱變量(用戶偏好)取值的概率，作為發(fā)現(xiàn)用戶偏好的依據(jù)。由于BN的精確推理是NP困難的[16]，即使評分?jǐn)?shù)據(jù)中的屬性不多，但其可能取值較多而使其計(jì)算復(fù)雜度仍然較高，不能有效地進(jìn)行概率推理和用戶偏好發(fā)現(xiàn)。Gibbs采樣[17-18]能夠支持高效的條件概率和后驗(yàn)概率的計(jì)算，且只要采樣次數(shù)足夠多，總能快速地收斂到一個穩(wěn)定的正確值，因此本文給出基于Gibbs采樣的隱變量模型近似推理算法和相應(yīng)用戶偏好發(fā)現(xiàn)方法。

具體而言，本文的研究主要包括以下三方面：

1)基于評分?jǐn)?shù)據(jù)中的隱變量模型構(gòu)建。本文首先對缺失評分值進(jìn)行填補(bǔ)，然后基于BN給出商品屬性貝葉斯網(wǎng)(Commodity BN, CBN)，最后將描述用戶偏好的隱變量插入CBN中，得到含隱變量的商品屬性貝葉斯網(wǎng)(CBN with a Latent variable, CBNL)。

2)面向用戶偏好發(fā)現(xiàn)的CBNL概率推理。本文基于Gibbs采樣給出了CBNL模型的近似概率推理算法，該算法通過對給定的證據(jù)值計(jì)算隱變量可能取值的不確定性，來高效地計(jì)算發(fā)現(xiàn)用戶偏好。

3)實(shí)驗(yàn)測試?；贛ovieLens[19]上的數(shù)據(jù)集，實(shí)現(xiàn)并測試了本文提出的方法。實(shí)驗(yàn)結(jié)果表明，本文基于隱變量模型來發(fā)現(xiàn)用戶偏好的方法具有一定的可行性。

1 問題陳述

用隱變量L表示用戶對商品類型的偏好。假設(shè)L的取值為1和0，在每一個評分?jǐn)?shù)據(jù)實(shí)例中，分別表示用戶對相應(yīng)商品類型有無偏好。例如，表1給出了電影評分?jǐn)?shù)據(jù)片段，其中：X1表示電影類型(取值為k1、k2和k3)，X2表示發(fā)行年代(取值為t1、t2和t3)，X3表示評價(jià)(T、M和F分別代表好評、中評和差評)，X4表示評分(取值為1,2,…,5)。假設(shè)對于第一個數(shù)據(jù)實(shí)例，L取值為1，說明用戶1對發(fā)行年代為t1、評價(jià)為好評T、評分較高的電影類型k1有偏好。

表1 電影評分?jǐn)?shù)據(jù)片段

下面首先給出一些相關(guān)定義和概念。

BN是一個DAGG=(V,E)，隨機(jī)變量集V構(gòu)成G中的節(jié)點(diǎn)，每個節(jié)點(diǎn)對應(yīng)一個隨機(jī)變量，節(jié)點(diǎn)狀態(tài)對應(yīng)隨機(jī)變量取值，E中的有向邊表示節(jié)點(diǎn)之間的依賴關(guān)系。如果存在從節(jié)點(diǎn)X指向節(jié)點(diǎn)Y(即X→Y)的有向邊，稱X是Y的一個父節(jié)點(diǎn)，變量X在G中的父節(jié)點(diǎn)集用Pa(X)表示。每個節(jié)點(diǎn)都有一個CPT，用以量化父節(jié)點(diǎn)集對該節(jié)點(diǎn)的影響。

基于BN的基本概念，下面給出商品屬性貝葉斯網(wǎng)(CBN)的定義。

定義1CBN模型為一個DAGG=(V,E,θ)，其中：V={X1,X2,…,Xn}為G中的節(jié)點(diǎn)集合，每個節(jié)點(diǎn)對應(yīng)評分?jǐn)?shù)據(jù)中的一個屬性；E為G中節(jié)點(diǎn)間有向邊的集合；θ為G中節(jié)點(diǎn)CPT的集合。有向邊Xi→Xj(1≤i,j≤n,i≠j)表示Xj依賴于Xi。若Xi的父節(jié)點(diǎn)集合為Pa(Xi)，則節(jié)點(diǎn)Xi的CPT為P(Xi|Pa(Xi))。給定Xi的父節(jié)點(diǎn)集Pa(Xi)，Xi與其所有非后代節(jié)點(diǎn)條件獨(dú)立。

將描述用戶偏好的隱變量加入CBN中，可得到用戶偏好與商品屬性間依賴關(guān)系的隱變量模型，下面給出含隱變量的商品屬性貝葉斯網(wǎng)(CBNL)的定義。

定義2CBNL為一個DAGGL=(V,L,E,θ)。其中：V∪L為GL中的節(jié)點(diǎn)集合，L為GL中表示用戶偏好的隱變量，E為GL中節(jié)點(diǎn)間有向邊的集合，θ為GL中CPT的集合。

CBNL的構(gòu)建包括DAG構(gòu)建和各節(jié)點(diǎn)CPT計(jì)算，下面分別介紹這兩方面的工作。

2 評分?jǐn)?shù)據(jù)中的隱變量模型構(gòu)建

2.1 缺失評分值填補(bǔ)

BMF模型以概率的形式描述評分矩陣和隱含特征矩陣，并考慮用戶和商品的偏置部分。例如，不同用戶對商品的評分都有自己的標(biāo)準(zhǔn)，有的用戶對商品的整體評分偏高，有的用戶對商品的整體評分偏低。評分?jǐn)?shù)據(jù)集D中的評分值往往非常稀疏，因此在D中抽取出“用戶-商品”評分矩陣M，基于BMF模型來填補(bǔ)矩陣M中的缺失值，通過降維的思想來抽象出商品的T個隱含特征。

利用BMF模型填補(bǔ)矩陣M中的缺失值時(shí)，將矩陣M分解為用戶隱含特征矩陣U和商品隱含特征矩陣V，則用戶ui對商品vj的缺失評分可由式(1)表示：

(1)

其中：μ為M中所有評分記錄的全局評分平均值，用戶偏置bi是獨(dú)立于商品特征的因素，商品偏置bj是獨(dú)立于用戶興趣的因素。

采用平方誤差作為損失函數(shù)，利用式(2)使已知評分與填補(bǔ)評分之間的誤差最小，即計(jì)算出的評分盡可能與實(shí)際評分相吻合。

(2)

表2為基于BMF模型進(jìn)行評分值填補(bǔ)前、后的用戶-商品評分矩陣。特別強(qiáng)調(diào)，即使用戶u4沒有對任何商品給出評分，通過BMF仍能得到比較合理的評分。

表2 基于BMF模型得到的填補(bǔ)評分矩陣

基于上述方法，可以填補(bǔ)矩陣M中的所有缺失評分值，得到完整的評分矩陣M，根據(jù)統(tǒng)計(jì)算出每個用戶對某種商品類型的平均評分，從而得到完整的商品評分?jǐn)?shù)據(jù)集，為CBN構(gòu)建進(jìn)行數(shù)據(jù)預(yù)處理。

2.2 CBNL模型結(jié)構(gòu)構(gòu)建

本文提出的CBN構(gòu)建方法，通過計(jì)算兩個商品屬性之間的互信息[20](式(3))和條件互信息，來判斷兩個屬性之間的依賴關(guān)系。

(3)

根據(jù)式(4)所示的條件互信息計(jì)算公式[20]可以判斷兩個商品屬性之間的條件獨(dú)立性。

I(Xi,Xj|C)=

(4)

其中：C表示節(jié)點(diǎn)Xi和Xj的最小割集，最小割集指Xi和Xj的所有鄰接路徑上的鄰居節(jié)點(diǎn)，鄰接路徑是兩個節(jié)點(diǎn)間所有邊構(gòu)成的路徑。與Xi相鄰的節(jié)點(diǎn)存入集合N1中，與Xj相鄰的節(jié)點(diǎn)存入N2中，若|N1|<|N2|，則N1中元素為最小割集，否則N2中元素為最小割集。

基于上述方法來判斷兩個屬性之間是否有邊，見算法1。

算法1CBN結(jié)構(gòu)構(gòu)建。

輸入 商品評分?jǐn)?shù)據(jù)集D，商品相關(guān)屬性X={X1,X2,…,Xn}，節(jié)點(diǎn)順序ρ和閾值ω；

輸出CBN的DAG結(jié)構(gòu)：G=(X,E)。

1)

確定網(wǎng)絡(luò)初始結(jié)構(gòu)。G←由節(jié)點(diǎn)X1,X2,…,Xn組成的無邊圖，H←?,E←?

/*H為節(jié)點(diǎn)對列表,E為有向邊集合*/Forρ中任意兩個不同變量DoIfI(Xi,Xj)>ωThenH←H∪(Xi,Xj)

EndFor

按I(Xi,Xj)由大到小的順序重排H中的節(jié)點(diǎn)對

ForH中不存在開放路徑的節(jié)點(diǎn)對(Xi,Xj)Do

/*開放路徑是不存在碰撞節(jié)點(diǎn)的路徑，

碰撞節(jié)點(diǎn)指大于1條邊指向它的節(jié)點(diǎn)*/ 根據(jù)ρ連接Xi和Xj，將(Xi,Xj)添加到E中H←H{Xi,Xj}

EndFor

H1←H

2)

缺邊檢測。

IfH1=?Thengoto3)

ElseFor對每個節(jié)點(diǎn)對(Xi,Xj)∈H1DoZ←min{cut(Xi, Xj)}IfI(Xi,Xj|Z)>ωThen根據(jù)ρ連接Xi與Xj，將(Xi,Xj)添加到E中

EndFor

EndIf

3)

冗余邊檢測。

For對每條有向邊(Xi,Xj)∈EDoIfXi與Xj間還有其他路徑Then暫時(shí)刪除(Xi,Xj)，Z←min{cut(Xi,Xj)}IfI(Xi,Xj|Z)>ωThen將(Xi,Xj)添加到E中

Else永久刪除(Xi,Xj)

EndIf

EndIf

EndFor

ReturnG

算法1對于包含m個數(shù)據(jù)實(shí)例、n個節(jié)點(diǎn)的DAG，式(3)執(zhí)行O(n2)次，每次計(jì)算時(shí)間為O(m)；而互信息大于ω(ω為給定的互信息閾值，為了盡可能多地表達(dá)節(jié)點(diǎn)之間的依賴關(guān)系，ω一般取值為[0.01，0.05])的節(jié)點(diǎn)對才計(jì)算條件互信息，式(4)的執(zhí)行次數(shù)遠(yuǎn)小于O(n2)。因此，算法1可在O(mn2)時(shí)間內(nèi)構(gòu)建CBN。

在構(gòu)建好的CBN結(jié)構(gòu)G中，基于最大半團(tuán)插入表示用戶偏好的隱變量，得到CBNL結(jié)構(gòu)。下面首先給出判斷半團(tuán)和最大半團(tuán)的定義。

定義3[12]假設(shè)Q是BN中的節(jié)點(diǎn)集合，若對于任一節(jié)點(diǎn)Y∈Q，有|Δ(Y;Q)|>2-1|Q|，其中Δ(Y;Q)表示Y在Q中的鄰居節(jié)點(diǎn)(Y的父節(jié)點(diǎn)或孩子節(jié)點(diǎn))組成的集合，|Q|為Q中節(jié)點(diǎn)數(shù)，則Q是一個半團(tuán)。

定義4 若在半團(tuán)T中引入與T相鄰的所有節(jié)點(diǎn)都不滿足半團(tuán)定義，那么T是一個最大半團(tuán)。

為了構(gòu)建CBNL結(jié)構(gòu)，首先搜索G中所有包含3個屬性的子團(tuán)(即3-clique)；然后對每個子團(tuán)進(jìn)行擴(kuò)展，找到G中所有的最大半團(tuán)C={C1,C2,…,Cm}；其次向每個最大半團(tuán)中插入表示用戶偏好的隱變量，得到m個候選模型結(jié)構(gòu)；最后對每一個模型結(jié)構(gòu)分析與隱變量相關(guān)的依賴關(guān)系，據(jù)此判斷該隱變量是否能夠表示用戶偏好。任選一個模型結(jié)構(gòu)作為最終的CBNL結(jié)構(gòu)GL，見算法2。

算法2CBNL結(jié)構(gòu)構(gòu)建。

輸入CBN模型結(jié)構(gòu)G；

輸出CBNL模型結(jié)構(gòu)GL。

從G中找出所有的3-clique結(jié)構(gòu){C1,C2,…,Cn}Fori←1tonDoFor對任意與Ci直接相連的節(jié)點(diǎn)XjDoIf{Ci∪Xj}滿足半團(tuán)定義ThenCi←Ci∪Xj

EndIf

EndFor

EndFor

去除重復(fù)的最大半團(tuán)，得到{C1,C2,…,Cm}

Fori=1tomDo刪除Ci中的所有邊，若|Pa(Xj)|≥1，則將L作為Xj的父節(jié)點(diǎn)，否則Xj作為L的父節(jié)點(diǎn)

EndFor

在m個候選結(jié)構(gòu)δ1,δ2,…,δm中選擇一個作為GL

ReturnGL

例如，對于表1中的評分?jǐn)?shù)據(jù)集D及相關(guān)屬性，由算法1可得到如圖1(a)所示的CBN結(jié)構(gòu)；再由算法2可以找到2個3-clique，C1={X1,X3,X4}，C2={X2,X3,X4}，分別對其擴(kuò)展得到相同的最大半團(tuán)結(jié)構(gòu)C={X1,X2,X3,X4}，在C中插入表示用戶偏好的隱變量L，可得到如圖1(b)所示的CBNL結(jié)構(gòu)。

圖1 CBNL結(jié)構(gòu)構(gòu)建

2.3 條件概率參數(shù)計(jì)算

期望最大化(ExpectationMaximization,EM)算法[21]主要用于在含有隱變量的概率模型中計(jì)算參數(shù)的最大似然估計(jì)(MaximumLikelihoodEstimation)或極大后驗(yàn)概率估計(jì)。因此，基于2.2節(jié)中得到的CBNL結(jié)構(gòu)，使用EM算法來估算該結(jié)構(gòu)中各節(jié)點(diǎn)的CPT。EM算法從隨機(jī)產(chǎn)生的初始值θ0開始迭代，假設(shè)已迭代了t-1次，那么第t次迭代由如下步驟完成。

E步：基于θt-1對隱變量取值進(jìn)行修補(bǔ)，利用式(5)計(jì)算期望對數(shù)似然函數(shù)。

(5)

其中:m是評分?jǐn)?shù)據(jù)集D中的實(shí)例數(shù)，l是隱變量L的取值。

M步：利用式(6)計(jì)算使Q(θ|θt)達(dá)到最大時(shí)θ的取值。

(6)

E步和M步不斷交替進(jìn)行，直到各節(jié)點(diǎn)的CPT收斂到穩(wěn)定值。

例如，針對圖1(b)所示的CBNL結(jié)構(gòu)，鑒于描述的方便，假定商品評分?jǐn)?shù)據(jù)中的每個屬性可能取值數(shù)為2，基于EM算法得到各節(jié)點(diǎn)的CPT，最終的CBNL如圖2所示。

圖2 最終的CBNL

3 面向偏好發(fā)現(xiàn)的CBNL概率推理

為了進(jìn)行基于CBNL的用戶偏好發(fā)現(xiàn)，對CBNL進(jìn)行概率推理時(shí)，把隱變量作為目標(biāo)變量，把CBNL中與隱變量有直接依賴關(guān)系的屬性作為證據(jù)變量(即已知變量)。經(jīng)過Gibbs采樣算法多次迭代計(jì)算得到隱變量的最大后驗(yàn)概率值，將計(jì)算出的概率值與給定的偏好閾值進(jìn)行比較，從而發(fā)現(xiàn)用戶對商品類型是否有偏好。

Gibbs采樣算法從滿足條件分布中迭代地進(jìn)行抽樣，當(dāng)?shù)螖?shù)足夠大時(shí)，就可以得到來自聯(lián)合后驗(yàn)分布的樣本。為了簡化計(jì)算而又不失一般性，對于隱變量的計(jì)算僅考慮其馬爾可夫覆蓋(X的馬爾可夫覆蓋包括X的直接孩子節(jié)點(diǎn)、X的直接父節(jié)點(diǎn)、以及X的直接孩子的其他父節(jié)點(diǎn)的集合，記為MB(X))中的節(jié)點(diǎn)對它的影響。見算法3。

算法3 基于Gibbs采樣的CBNL概率推理。

輸入GL=(V,L,E,θ)，證據(jù)變量集合Φ，Φ的取值e，非證據(jù)變量L，L的取值l，遍歷次數(shù)s；

輸出P(L=1|e)。

1)

初始化。 隨機(jī)地為L賦值，v0←e∪l，N[l]←0

/*N[l]為L取1的個數(shù)*/

2)

產(chǎn)生樣本序列。Fork←1tosDoFor每一個樣本v(k)中的LDoB←P(L=0|vMB(L))+P(L=1|vMB(L))

v(k)←(v(k-1)(-l),l)

/*v(k-1)(-l)表示在第(k-1)個樣本中去除L值后的樣本*/

EndFor

EndFor

3)

計(jì)算P(L=1|e)。

/*l(k)1為第k次采樣中L=1*/N[l]←N[l]+1

EndIf

EndFor

P(L=1|e)←N[l]/s

利用算法3，基于給定的閾值λ，若P(L=1|e)≥λ，則認(rèn)為用戶對這樣的商品類型有偏好。文獻(xiàn)[16, 22]指出，只要采樣次數(shù)足夠多，Gibbs采樣算法總能收斂到一個穩(wěn)定的正確值，后面將通過實(shí)驗(yàn)進(jìn)一步測試算法3的收斂性和正確性。

針對圖2中的CBNL，計(jì)算P(L=1|X1=k1,X2=t1,X3=T,X4=1)。隨機(jī)地為L賦值得到D0=[X1=k1,X2=t1,L=0,X3=T,X4=1]。第一次對L采樣，有P(L=1|X1,X2,X3,X4)=0.25，則P(L=0|X1,X2,X3,X4)=0.75，若r1=0.4，得到D1=[X1=k1,X2=t1,L=0,X3=T,X4=1]。若采樣300次，其中L=1有250次，則P(L=1|X1=k1,X2=t1,X3=T,X4=1)=0.833，表明用戶對發(fā)行年代為t1、好評、高分的電影類型t1有偏好。

4 實(shí)驗(yàn)結(jié)果與分析

本文使用MovieLens[19]上用戶評分?jǐn)?shù)據(jù)作為測試數(shù)據(jù)集，包含6 040個用戶對3 900部電影的1 000 209條評分?jǐn)?shù)據(jù)，將電影類型、發(fā)行年代、評價(jià)(從標(biāo)簽中抽取出來)和評分4個屬性作為CBNL的節(jié)點(diǎn)。實(shí)驗(yàn)環(huán)境：IntelPentiumDual-Core2.0GHz處理器，2GB內(nèi)存，Windows7(32位)操作系統(tǒng)，使用MatlabR2012b作為開發(fā)平臺。

首先，測試基于BMF模型進(jìn)行評分值填補(bǔ)結(jié)果的準(zhǔn)確性，并在不同的數(shù)據(jù)量情形下與PMF[4]、BPMF[5]模型進(jìn)行比較。用平均絕對誤差(MeanAbsoluteError，MAE)和均方根誤差(RootMeanSquaredError,RMSE)作為衡量填補(bǔ)結(jié)果準(zhǔn)確性的依據(jù)，MAE和RMSE值越小，說明填補(bǔ)的數(shù)據(jù)與真實(shí)數(shù)據(jù)之間的誤差越小。如圖3、圖4所示，在不同數(shù)據(jù)量情形下，BMF模型填補(bǔ)數(shù)據(jù)時(shí)的MAE和RMSE值均最小，這說明BMF模型在數(shù)據(jù)填補(bǔ)時(shí)更為準(zhǔn)確。

圖3 MAE值

圖4 RMSE值

然后，測試CBNL構(gòu)建算法的執(zhí)行效率。在數(shù)據(jù)實(shí)例為2×104情形下，測試節(jié)點(diǎn)數(shù)分別為5、7、9、11、13時(shí)構(gòu)建CBNL的時(shí)間開銷，結(jié)果如圖5所示，表明構(gòu)建CBNL的時(shí)間開銷主要取決于參數(shù)計(jì)算；還測試了數(shù)據(jù)實(shí)例數(shù)分別為1×104、10×104、20×104,…,60×104時(shí)構(gòu)建CBNL的時(shí)間開銷，結(jié)果如圖6所示，也表明CBNL構(gòu)建的時(shí)間主要取決于參數(shù)計(jì)算，且隨著數(shù)據(jù)實(shí)例數(shù)的增加基本呈線性趨勢增加。

圖5 不同節(jié)點(diǎn)數(shù)的CBNL構(gòu)建效率

進(jìn)一步，測試了參數(shù)計(jì)算的準(zhǔn)確性。從測試數(shù)據(jù)集中選取包括5×104、10×104、15×104個數(shù)據(jù)實(shí)例的片段，把其中一個已知屬性值當(dāng)作未知的，用EM算法迭代計(jì)算MLE值，然后用得到的MLE值與原MLE值進(jìn)行對比，將其比值作為誤差來衡量參數(shù)計(jì)算的準(zhǔn)確性，結(jié)果如圖7所示?？梢钥闯觯S著迭代次數(shù)的增加，EM算法收斂到一個穩(wěn)定的值，且數(shù)據(jù)量越大，計(jì)算出的MLE值與真實(shí)值越接近。

其次，測試了基于CBNL推理發(fā)現(xiàn)用戶偏好的效率，圖8和圖9分別給出了在不同數(shù)據(jù)量的情形下，隨著采樣次數(shù)增加，算法3返回結(jié)果的收斂性和執(zhí)行的時(shí)間開銷。從圖8可以看出，隨著采樣次數(shù)的增加，不同數(shù)據(jù)量情形下的推理結(jié)果均能快速地收斂到一個穩(wěn)定的值；從圖9可以看出，在不同數(shù)據(jù)量的情形下，算法3的執(zhí)行時(shí)間均能隨著采樣次數(shù)呈線性增長。

圖6 不同實(shí)例數(shù)的CBNL構(gòu)建效率

圖7 CBNL參數(shù)計(jì)算的準(zhǔn)確性

圖8 CBNL近似推理結(jié)果收斂性

圖9 CBNL推理算法效率

最后，測試了基于CBNL推理發(fā)現(xiàn)用戶偏好的準(zhǔn)確性。假設(shè)評分?jǐn)?shù)據(jù)中的評分反映了真實(shí)的用戶偏好，針對4或5分的評價(jià)，通過多次實(shí)驗(yàn)確定偏好閾值為0.67。隨機(jī)選取3名用戶(記為u1、u2和u3)，同時(shí)選取20部他們都評價(jià)過的電影作為測試數(shù)據(jù)，其中10部電影的評價(jià)作為訓(xùn)練數(shù)據(jù)，剩下10部電影的評價(jià)作為對比數(shù)據(jù)。表3給出了3名用戶對10部電影的評分。

表3 用戶對電影的評分信息

將基于協(xié)同過濾(CollaborativeFiltering,CF)的方法[23]和本文方法進(jìn)行對比，該CF方法預(yù)測評分時(shí)定義了一個推薦值來適當(dāng)?shù)靥岣呶粗唐返脑u分。本文方法選定u1為目標(biāo)用戶，基于余弦相似度得到u1和u3最相似，將后10部電影按u1的喜好推薦給u3。其中表4給出他們對后10部電影的評分信息，u1的評分是真實(shí)的用戶評分，通過CF預(yù)測得到u3的評分與u3真實(shí)的評分相比，正確率為60%，通過本文方法發(fā)現(xiàn)用戶偏好的正確率為70%。可以看出，基于本文方法發(fā)現(xiàn)用戶偏好的結(jié)果比CF預(yù)測得到的評分正確率高，這從一定程度上說明了本文方法的正確性和有效性。

表4 用戶對電影的預(yù)測評分信息

5 結(jié)語

本文基于隱變量模型和概率推理，提出了從商品評分?jǐn)?shù)據(jù)中發(fā)現(xiàn)用戶偏好的方法,解決了現(xiàn)有方法不能描述評分?jǐn)?shù)據(jù)中相關(guān)屬性間任意形式的依賴關(guān)系問題，可支持實(shí)際中商品推薦和用戶定向等應(yīng)用。

作為基于概率圖模型進(jìn)行偏好發(fā)現(xiàn)的初步試探性研究，本文構(gòu)建隱變量模型時(shí)只引入一個二值隱變量，且未考慮評分?jǐn)?shù)據(jù)大規(guī)模和動態(tài)性。引入多個隱變量、考慮與實(shí)際更吻和的情形，從海量用戶評分?jǐn)?shù)據(jù)中來發(fā)現(xiàn)用戶偏好，滿足海量數(shù)據(jù)處理需求和針對實(shí)際情形下用戶偏好發(fā)現(xiàn)的可行性，是將來要開展的工作。

)

[1] 高全力,高嶺,楊建峰，等.上下文感知推薦系統(tǒng)中基于用戶認(rèn)知行為的偏好獲取方法[J].計(jì)算機(jī)學(xué)報(bào), 2015,38(9):1767-1776.(GAOQL,GAOL,YANGJF,etal.Apreferenceelicitationmethodbasedonuser’scognitivebehaviorforcontext-awarerecommendersystem[J].ChineseJournalofComputers, 2015, 38(9): 1767-1776.)

[2]LIUL,ZHUF,ZHANGL,etal.Aprobabilisticgraphicalmodelfortopicandpreferencediscoveryonsocialmedia[J].Neurocomputing, 2012, 95: 78-88.

[3] 項(xiàng)亮.推薦系統(tǒng)實(shí)踐[M].北京:人民郵電出版社,2012:196-212.(XIANGL.PracticeofRecommendationSystem[M].Beijing:Posts&TelecomPress, 2012: 196-212.)

[4]SALAKHUTDINOVR,MNIHA.Probabilisticmatrixfactorization[C]//NIPS2008:Proceedingsofthe2008ConferenceonNeuralInformationProcessingSystems,Cambridge,MA:MITPress, 2008: 1257-1264.

[5]SALAKHUTDINOVR,MNIHA.BayesianprobabilisticmatrixfactorizationusingMarkovchainMonteCarlo[C]//ICML’08:Proceedingsofthe25thInternationalConferenceonMachineLearning.NewYork:ACM, 2008: 880-887.

[6]KORENY.Factorizationmeetstheneighborhood:amultifacetedcollaborativefilteringmodel[C]//KDD’08:Proceedingsofthe14thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork:ACM, 2008: 426-434.

[7] 張連文，郭海鵬.貝葉斯網(wǎng)引論[M].北京:科學(xué)出版社,2006:31-36，194.(ZHANGLW,GUOHP.IntroductiontoBayesianNetworks[M].Beijing:SciencePress, 2006: 31-36， 194.)

[8]HECKERMAND.AtutorialonlearningwithBayesiannetworks[M]//InnovationsinBayesianNetworks:TheoryandApplications,Volume156oftheSeriesStudiesinComputationalIntelligence.Berlin:Springer-Verlag, 2008: 33-82.

[9]DAYEJ,YEUYK,AHNJ,etal.Inferenceofdisease-specificgeneinteractionnetworkusingaBayesiannetworklearnedbygeneticalgorithm[C]//SAC’15:Proceedingsofthe30thAnnualACMSymposiumonAppliedComputing.NewYork:ACM, 2015: 47-53.

[10]ZHANGJ,CORMODEG,CECILIAM,etal.PrivBayes:privatedatareleaseviaBayesiannetworks[C]//SIGMOD’14：Proceedingsofthe2014ACMSIGMODInternationalConferenceonManagementofData.NewYork:ACM, 2014: 1423-1434.

[11]WANGH,ZHAICX,LIANGF,etal.UsermodelinginsearchlogsviaanonparametricBayesianapproach[C]//WSDM’14：Proceedingsofthe7thACMInternationalConferenceonWebSearchandDataMining.NewYork:ACM, 2014: 203-212.

[12]BIANJ,LONGB,LIL,etal.ExploitinguserpreferenceforonlinelearninginWebcontentoptimizationsystems[J].ACMTransactionsonIntelligentSystemsandTechnology—SpecialIssueonLinkingSocialGranularityandFunctions, 2014, 5(2):ArticleNo.33.

[13]ELIDANG,LOTNERN,FRIEDMANN,etal.Discoveringhiddenvariables:astructure-basedapproach[C]//NIPS2000:Proceedingsofthe2000ConferenceonNeuralInformationProcessingSystems.Cambridge,MA:MITPress, 2000: 479-485.

[14] 吳蕾,張文生,王玨.基于深度學(xué)習(xí)框架的隱藏主題變量圖模型[J].計(jì)算機(jī)研究與發(fā)展,2015,52(1):191-199.(WUL,ZHANGWH,WANGJ.Hiddentopicvariablegraphicalmodelbasedonlearningframework[J].JournalofComputerResearchandDevelopment, 2015, 52(1): 191-199.)

[15]GUANL,ALAMMH,RYUW-J,etal.Aphrase-basedmodeltodiscoverhiddenfactorsandhiddentopicsinrecommendersystems[C]//BigComp2016:ProceedingsoftheInternationalConferenceonBigDataandSmartComputing.Washington,DC:IEEEComputerSociety, 2016: 337-340.

[16] 張宏毅，王立威，陳瑜希.概率圖模型研究進(jìn)展綜述 [J].軟件學(xué)報(bào),2013,24(11):2476-2497.(ZHANGHY,WANGLW,CHENYX.Researchprogressofprobabilisticgraphicalmodels:asurvey[J].JournalofSoftware, 2013, 24(11): 2476-2497.)

[17]HRYCEJT.GibbssamplinginBayesiannetworks[J].ArtificialIntelligence, 1990, 46(3): 351-363.

[18] 岳昆,王朝祿,朱運(yùn)磊,等.基于概率圖模型的互聯(lián)網(wǎng)廣告點(diǎn)擊率發(fā)現(xiàn)[J].華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2013(3):15-25.(YUEK,WANGCL,ZHUYL,etal.Click-throughratepredictionofonlineadvertisementsbasedonprobabilisticgraphicalmodel[J].JournalofEastChinaNormalUniversity(NaturalScience), 2013(3): 15-25.)

[19]MovieLens[EB/OL].[2016- 03- 18].http://grouplens.org/datasets/movielens/latest/.

[20]CHENGJ,BELLDA,LIUW.LearningBayesiannetworksfromdata:anefficientapproachbasedoninformationtheory[J].ArtificialIntelligence, 2002, 137(1/2): 43-90

[21]DEMPSTERAP,LAIRDNM,RUBINDB.MaximumlikelihoodfromincompletedataviatheEMalgorithm[J].JournaloftheRoyalStatisticalSociety,SeriesB(Methodological), 2007, 39(1): 1-38.

[22]PEARLJ.Evidentialreasoningusingstochasticsimulationofcausalmodels[J].ArtificialIntelligence, 1987, 32(2): 245-257.

[23]SHIHT-Y,HOUT-C,JIANGJ-D,etal.Dynamicallyintegratingitemexposurewithratingpredictionincollaborativefiltering[C]//SIGIR’16:Proceedingsofthe39thInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval.NewYork:ACM, 2016: 813-816.

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(61472345, 61562090, 61462056),theAppliedBasicResearchProjectofYunnanProvince(2014FA023, 2014FA028),theProgramofYunnanProvincialFoundationforLeadersofDisciplinesinScienceandTechnology(2012HB004)，theProgramforExcellentYoungTalentsinYunnanUniversity(XT412003),theProgramforInnovativeResearchTeaminYunnanUniversity(XT412011).

GAO Yan, born in 1991, M.S.candidate.Her research interests include knowledge discovery, social media data analysis.

YUE Kun, born in 1979, Ph.D., professor.His research interests include massive data analysis and services.

WU Hao, born in 1979, Ph.D., associate professor.His research interests include information retrieval, recommendation system, service computing.

FU Xiaodong, born in 1975, Ph.D., professor.His research interests include service computing, intelligent decision.

LIU Weiyi, born in 1950, professor.His research interests include artificial intelligence, data and knowledge engineering.

Construction and inference of latent variable model oriented to user preference discovery

GAO Yan1, YUE Kun1*, WU Hao1, FU Xiaodong2, LIU Weiyi1

(1.SchoolofInformationScienceandEngineering,YunnanUniversity,KunmingYunnan650504,China;2.FacultyofInformationEngineeringandAutomation,KunmingUniversityofScienceandTechnology,KunmingYunnan650500,China)

Large amount of user rating data, involving plentiful users’ opinion and preference, is produced in e-commerce applications.An construction and inference method for latent variable model (i.e., Bayesian Network with a latent variable) oriented to user preference discovery from rating data was proposed to accurately infer user preference.First, the unobserved values in the rating data were filled by Biased Matrix Factorization (BMF) model to address the sparseness problem of rating data.Second, latent variable was used to represent user preference, and the construction of latent variable model based on Mutual Information (MI), maximal semi-clique and Expectation Maximization (EM) was given.Finally, an Gibbs sampling based algorithm for probabilistic inference of the latent variable model and the user preference discovery was given.The experimental results demonstrate that, compared with collaborative filtering, the latent variable model is more efficient for describing the dependence relationships and the corresponding uncertainties of related attributes among rating data, which can more accurately infer the user preference.

user preference; rating data; Bayesian network; latent variable model; probabilistic inference; biased matrix factorization

2016- 08- 12;

2016- 09- 06。 基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(61472345, 61562090, 61462056)；云南省應(yīng)用基礎(chǔ)研究計(jì)劃項(xiàng)目(2014FA023, 2014FA028)；云南省中青年學(xué)術(shù)和技術(shù)帶頭人才后備人才培育計(jì)劃項(xiàng)目(2012HB004)；云南大學(xué)青年英才培育計(jì)劃項(xiàng)目(XT412003)；云南大學(xué)創(chuàng)新團(tuán)隊(duì)培育計(jì)劃項(xiàng)目(XT412011)。

高艷(1991—),女,云南曲靖人,碩士研究生,CCF會員,主要研究方向:知識發(fā)現(xiàn)、社會媒體數(shù)據(jù)分析; 岳昆(1979—),男,云南曲靖人,教授,博士生導(dǎo)師,博士,CCF會員,主要研究方向:海量數(shù)據(jù)分析與服務(wù); 武浩(1979—),男,河南平頂山人,副教授,博士,主要研究方向:信息檢索、推薦系統(tǒng)、服務(wù)計(jì)算; 付曉東(1975—),男,云南鎮(zhèn)雄人,教授,博士,CCF會員,主要研究方向:服務(wù)計(jì)算、智能決策;劉惟一(1950—),男,云南昆明人,教授,博士生導(dǎo)師,CCF會員,主要研究方向:人工智能、數(shù)據(jù)與知識工程。

1001- 9081(2017)02- 0360- 07

10.11772/j.issn.1001- 9081.2017.02.0360

TP311.13; TP181

A