高 艷,岳 昆,武 浩,付曉東,劉惟一
(1.云南大學(xué) 信息學(xué)院,昆明 650504; 2.昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院,昆明 650500)
(*通信作者電子郵箱kyue@ynu.edu.cn)
面向用戶偏好發(fā)現(xiàn)的隱變量模型構(gòu)建與推理
高 艷1,岳 昆1*,武 浩1,付曉東2,劉惟一1
(1.云南大學(xué) 信息學(xué)院,昆明 650504; 2.昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院,昆明 650500)
(*通信作者電子郵箱kyue@ynu.edu.cn)
電子商務(wù)應(yīng)用中產(chǎn)生了大量用戶評(píng)分?jǐn)?shù)據(jù),而這些數(shù)據(jù)中富含了用戶觀點(diǎn)和偏好信息,為了能夠從這些數(shù)據(jù)中準(zhǔn)確地推斷出用戶偏好,提出一種面向評(píng)分?jǐn)?shù)據(jù)中用戶偏好發(fā)現(xiàn)的隱變量模型(即含隱變量的貝葉斯網(wǎng))構(gòu)建和推理的方法。首先,針對(duì)評(píng)分?jǐn)?shù)據(jù)的稀疏性,使用帶偏置的矩陣分解(BMF)模型對(duì)其進(jìn)行填補(bǔ);其次,用隱變量表示用戶偏好,給出了基于互信息(MI)、最大半團(tuán)和期望最大化(EM)算法的隱變量模型構(gòu)建方法;最后,給出了基于Gibbs采樣的隱變量模型概率推理和用戶偏好發(fā)現(xiàn)方法。實(shí)驗(yàn)結(jié)果表明,與協(xié)同過(guò)濾的方法相比,該方法能有效地描述評(píng)分?jǐn)?shù)據(jù)中相關(guān)屬性之間的依賴關(guān)系及其不確定性,從而能夠更準(zhǔn)確地推斷出用戶偏好。
用戶偏好;評(píng)分?jǐn)?shù)據(jù);貝葉斯網(wǎng);隱變量模型;概率推理;帶偏置的矩陣分解
電子商務(wù)和推薦網(wǎng)站等Web 2.0應(yīng)用產(chǎn)生了大量的用戶對(duì)商品的評(píng)分?jǐn)?shù)據(jù),而這些評(píng)分?jǐn)?shù)據(jù)中則包含了可直接觀測(cè)到的用戶和商品本身的屬性,以及用戶對(duì)商品的評(píng)分等,蘊(yùn)含了用戶對(duì)某種商品類型的偏好。近年來(lái),從評(píng)分?jǐn)?shù)據(jù)中提取用戶偏好已經(jīng)成為數(shù)據(jù)挖掘、推薦系統(tǒng)和個(gè)性化搜索研究的熱點(diǎn)。相對(duì)商品類型和用戶評(píng)分等可直接觀測(cè)到值的變量而言,用戶偏好是隱變量(Latent Variable)。從實(shí)際應(yīng)用看,商品本身的屬性、評(píng)分和用戶偏好之間存在相互依賴關(guān)系,且具有不確定性。如何描述上述具有不確定性的依賴關(guān)系,是解決實(shí)際應(yīng)用中針對(duì)觀測(cè)屬性來(lái)提取用戶偏好的關(guān)鍵,進(jìn)而為商品個(gè)性化推薦、用戶劃分和虛假評(píng)價(jià)檢測(cè)等應(yīng)用提供依據(jù)。對(duì)此,研究描述各觀測(cè)屬性(也稱顯變量)和用戶偏好之間依賴關(guān)系及其不確定性的知識(shí)模型構(gòu)建,以及基于該模型進(jìn)行知識(shí)推理來(lái)發(fā)現(xiàn)用戶偏好的方法,是本文研究的主要任務(wù)和基本思想。
近年來(lái),用戶偏好發(fā)現(xiàn)已有許多研究成果。例如,文獻(xiàn)[1]提出基于用戶認(rèn)知行為的上下文感知的偏好獲取方法;文獻(xiàn)[2]提出一種偏好-主題模型,引入用戶偏好維度來(lái)提取用戶偏好。然而,上述工作并未考慮用戶偏好與用戶行為或相關(guān)屬性間的內(nèi)在聯(lián)系,使得發(fā)現(xiàn)的用戶偏好準(zhǔn)確度不高。
通常情況,用戶評(píng)分?jǐn)?shù)據(jù)往往比較稀疏。例如,Amazon網(wǎng)站一般存在95%的數(shù)據(jù)缺失[3],進(jìn)而無(wú)法計(jì)算各商品屬性之間的依賴關(guān)系。Salakhutdinov等[4]提出了概率矩陣分解 (Probabilistic Matrix Factorization, PMF)模型,該模型以概率的形式描述評(píng)分矩陣和隱含特征矩陣。隨后Salakhutdinov等[5]將PMF擴(kuò)展為貝葉斯概率矩陣分解(Bayesian PMF, BPMF)模型,并用馬爾可夫鏈蒙特卡羅(Markov Chain Monte Carlo, MCMC)方法進(jìn)行訓(xùn)練,該模型的預(yù)測(cè)準(zhǔn)確率較高,但BPMF模型是一種線性模型,并不能表示隱含特征之間的非線性關(guān)系。Koren[6]提出了帶偏置的矩陣分解(Biased Matrix Factorization, BMF)模型,該模型對(duì)于稀疏性、數(shù)據(jù)擴(kuò)展等問(wèn)題都有良好的性能。評(píng)價(jià)中有很多因素取決于用戶或商品本身的屬性,本文將獨(dú)立于用戶或商品的因素視為偏置部分,將用戶對(duì)商品的喜好視為個(gè)性化部分,利用矩陣分解中偏置部分對(duì)提高評(píng)分預(yù)測(cè)的準(zhǔn)確率遠(yuǎn)遠(yuǎn)高于個(gè)性化部分這一結(jié)論,基于BMF模型來(lái)填補(bǔ)缺失的評(píng)分值,對(duì)評(píng)分?jǐn)?shù)據(jù)進(jìn)行預(yù)處理。
作為一種重要的概率圖模型,貝葉斯網(wǎng)(Bayesian Network, BN)[7-8]是不確定性知識(shí)表示和推理的有效框架,被廣泛應(yīng)用于數(shù)據(jù)分析和醫(yī)療診斷等領(lǐng)域[9- 10],它以有向無(wú)環(huán)圖(Directed Acyclic Graph, DAG)表示隨機(jī)變量或?qū)傩蚤g的依賴關(guān)系,每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)條件概率表(Conditional Probability Table, CPT),定量地描述變量間的依賴關(guān)系。近年來(lái),基于BN的用戶偏好發(fā)現(xiàn)成為了一類有代表性的方法,例如,文獻(xiàn)[11]提出一種非參數(shù)BN模型和從日志數(shù)據(jù)中提取某個(gè)用戶的搜索意圖的方法,文獻(xiàn)[12]提出基于BN從Web服務(wù)的行為來(lái)動(dòng)態(tài)提取用戶偏好的方法。但是,上述方法中,BN的構(gòu)建僅涉及觀測(cè)到的數(shù)據(jù),不能有效發(fā)現(xiàn)隱含關(guān)系,進(jìn)而降低了用戶偏好發(fā)現(xiàn)的準(zhǔn)確性。
隱變量是描述不能直接觀測(cè)其取值的變量,含有隱變量的BN簡(jiǎn)稱隱變量模型(Latent Variable Model)[7]。Elidan等[13]指出,隱變量模型可以簡(jiǎn)化模型結(jié)構(gòu),使顯變量之間的依賴關(guān)系更清晰,能夠發(fā)現(xiàn)和表示數(shù)據(jù)中的隱含信息。如前所述,評(píng)分?jǐn)?shù)據(jù)中蘊(yùn)含的用戶偏好并不能直接觀測(cè)得到,自然地,本文用隱變量來(lái)表示用戶偏好,以隱變量模型作為研究用戶偏好發(fā)現(xiàn)的基礎(chǔ)。因此,引入隱變量、并用隱變量直接表示用戶偏好,可加強(qiáng)模型對(duì)用戶行為模式的表達(dá)能力。文獻(xiàn)[14]提出基于深度學(xué)習(xí)的隱馬爾可夫模型和條件隨機(jī)場(chǎng)來(lái)發(fā)現(xiàn)主題偏好的方法,文獻(xiàn)[15]基于隱評(píng)論主題模型從評(píng)級(jí)推薦系統(tǒng)中用戶反饋的短語(yǔ)信息中提取用戶偏好。但以上研究未考慮數(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],即使評(píng)分?jǐn)?shù)據(jù)中的屬性不多,但其可能取值較多而使其計(jì)算復(fù)雜度仍然較高,不能有效地進(jìn)行概率推理和用戶偏好發(fā)現(xiàn)。Gibbs采樣[17-18]能夠支持高效的條件概率和后驗(yàn)概率的計(jì)算,且只要采樣次數(shù)足夠多,總能快速地收斂到一個(gè)穩(wěn)定的正確值,因此本文給出基于Gibbs采樣的隱變量模型近似推理算法和相應(yīng)用戶偏好發(fā)現(xiàn)方法。
具體而言,本文的研究主要包括以下三方面:
1)基于評(píng)分?jǐn)?shù)據(jù)中的隱變量模型構(gòu)建。本文首先對(duì)缺失評(píng)分值進(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模型的近似概率推理算法,該算法通過(guò)對(duì)給定的證據(jù)值計(jì)算隱變量可能取值的不確定性,來(lái)高效地計(jì)算發(fā)現(xiàn)用戶偏好。
3)實(shí)驗(yàn)測(cè)試?;贛ovieLens[19]上的數(shù)據(jù)集,實(shí)現(xiàn)并測(cè)試了本文提出的方法。實(shí)驗(yàn)結(jié)果表明,本文基于隱變量模型來(lái)發(fā)現(xiàn)用戶偏好的方法具有一定的可行性。
用隱變量L表示用戶對(duì)商品類型的偏好。假設(shè)L的取值為1和0,在每一個(gè)評(píng)分?jǐn)?shù)據(jù)實(shí)例中,分別表示用戶對(duì)相應(yīng)商品類型有無(wú)偏好。例如,表1給出了電影評(píng)分?jǐn)?shù)據(jù)片段,其中:X1表示電影類型(取值為k1、k2和k3),X2表示發(fā)行年代(取值為t1、t2和t3),X3表示評(píng)價(jià)(T、M和F分別代表好評(píng)、中評(píng)和差評(píng)),X4表示評(píng)分(取值為1,2,…,5)。假設(shè)對(duì)于第一個(gè)數(shù)據(jù)實(shí)例,L取值為1,說(shuō)明用戶1對(duì)發(fā)行年代為t1、評(píng)價(jià)為好評(píng)T、評(píng)分較高的電影類型k1有偏好。
表1 電影評(píng)分?jǐn)?shù)據(jù)片段
下面首先給出一些相關(guān)定義和概念。
BN是一個(gè)DAGG=(V,E),隨機(jī)變量集V構(gòu)成G中的節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)隨機(jī)變量,節(jié)點(diǎn)狀態(tài)對(duì)應(yīng)隨機(jī)變量取值,E中的有向邊表示節(jié)點(diǎn)之間的依賴關(guān)系。如果存在從節(jié)點(diǎn)X指向節(jié)點(diǎn)Y(即X→Y)的有向邊,稱X是Y的一個(gè)父節(jié)點(diǎn),變量X在G中的父節(jié)點(diǎn)集用Pa(X)表示。每個(gè)節(jié)點(diǎn)都有一個(gè)CPT,用以量化父節(jié)點(diǎn)集對(duì)該節(jié)點(diǎn)的影響。
基于BN的基本概念,下面給出商品屬性貝葉斯網(wǎng)(CBN)的定義。
定義1CBN模型為一個(gè)DAGG=(V,E,θ),其中:V={X1,X2,…,Xn}為G中的節(jié)點(diǎn)集合,每個(gè)節(jié)點(diǎn)對(duì)應(yīng)評(píng)分?jǐn)?shù)據(jù)中的一個(gè)屬性;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為一個(gè)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.1 缺失評(píng)分值填補(bǔ)
BMF模型以概率的形式描述評(píng)分矩陣和隱含特征矩陣,并考慮用戶和商品的偏置部分。例如,不同用戶對(duì)商品的評(píng)分都有自己的標(biāo)準(zhǔn),有的用戶對(duì)商品的整體評(píng)分偏高,有的用戶對(duì)商品的整體評(píng)分偏低。評(píng)分?jǐn)?shù)據(jù)集D中的評(píng)分值往往非常稀疏,因此在D中抽取出“用戶-商品”評(píng)分矩陣M,基于BMF模型來(lái)填補(bǔ)矩陣M中的缺失值,通過(guò)降維的思想來(lái)抽象出商品的T個(gè)隱含特征。
利用BMF模型填補(bǔ)矩陣M中的缺失值時(shí),將矩陣M分解為用戶隱含特征矩陣U和商品隱含特征矩陣V,則用戶ui對(duì)商品vj的缺失評(píng)分可由式(1)表示:
(1)
其中:μ為M中所有評(píng)分記錄的全局評(píng)分平均值,用戶偏置bi是獨(dú)立于商品特征的因素,商品偏置bj是獨(dú)立于用戶興趣的因素。
采用平方誤差作為損失函數(shù),利用式(2)使已知評(píng)分與填補(bǔ)評(píng)分之間的誤差最小,即計(jì)算出的評(píng)分盡可能與實(shí)際評(píng)分相吻合。
(2)
表2為基于BMF模型進(jìn)行評(píng)分值填補(bǔ)前、后的用戶-商品評(píng)分矩陣。特別強(qiáng)調(diào),即使用戶u4沒(méi)有對(duì)任何商品給出評(píng)分,通過(guò)BMF仍能得到比較合理的評(píng)分。
表2 基于BMF模型得到的填補(bǔ)評(píng)分矩陣
基于上述方法,可以填補(bǔ)矩陣M中的所有缺失評(píng)分值,得到完整的評(píng)分矩陣M,根據(jù)統(tǒng)計(jì)算出每個(gè)用戶對(duì)某種商品類型的平均評(píng)分,從而得到完整的商品評(píng)分?jǐn)?shù)據(jù)集,為CBN構(gòu)建進(jìn)行數(shù)據(jù)預(yù)處理。
2.2 CBNL模型結(jié)構(gòu)構(gòu)建
本文提出的CBN構(gòu)建方法,通過(guò)計(jì)算兩個(gè)商品屬性之間的互信息[20](式(3))和條件互信息,來(lái)判斷兩個(gè)屬性之間的依賴關(guān)系。
(3)
根據(jù)式(4)所示的條件互信息計(jì)算公式[20]可以判斷兩個(gè)商品屬性之間的條件獨(dú)立性。
I(Xi,Xj|C)=
(4)
其中:C表示節(jié)點(diǎn)Xi和Xj的最小割集,最小割集指Xi和Xj的所有鄰接路徑上的鄰居節(jié)點(diǎn),鄰接路徑是兩個(gè)節(jié)點(diǎn)間所有邊構(gòu)成的路徑。與Xi相鄰的節(jié)點(diǎn)存入集合N1中,與Xj相鄰的節(jié)點(diǎn)存入N2中,若|N1|<|N2|,則N1中元素為最小割集,否則N2中元素為最小割集。
基于上述方法來(lái)判斷兩個(gè)屬性之間是否有邊,見(jiàn)算法1。
算法1CBN結(jié)構(gòu)構(gòu)建。
輸入 商品評(píng)分?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組成的無(wú)邊圖,H←?,E←?
/*H為節(jié)點(diǎn)對(duì)列表,E為有向邊集合*/Forρ中任意兩個(gè)不同變量DoIfI(Xi,Xj)>ωThenH←H∪(Xi,Xj)
EndFor
按I(Xi,Xj)由大到小的順序重排H中的節(jié)點(diǎn)對(duì)
ForH中不存在開(kāi)放路徑的節(jié)點(diǎn)對(duì)(Xi,Xj)Do
/*開(kāi)放路徑是不存在碰撞節(jié)點(diǎn)的路徑,
碰撞節(jié)點(diǎn)指大于1條邊指向它的節(jié)點(diǎn)*/ 根據(jù)ρ連接X(jué)i和Xj,將(Xi,Xj)添加到E中H←H{Xi,Xj}
EndFor
H1←H
2)
缺邊檢測(cè)。
IfH1=?Thengoto3)
ElseFor對(duì)每個(gè)節(jié)點(diǎn)對(duì)(Xi,Xj)∈H1DoZ←min{cut(Xi, Xj)}IfI(Xi,Xj|Z)>ωThen根據(jù)ρ連接X(jué)i與Xj,將(Xi,Xj)添加到E中
EndFor
EndIf
3)
冗余邊檢測(cè)。
For對(duì)每條有向邊(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對(duì)于包含m個(gè)數(shù)據(jù)實(shí)例、n個(gè)節(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)對(duì)才計(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)集合,若對(duì)于任一節(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是一個(gè)半團(tuán)。
定義4 若在半團(tuán)T中引入與T相鄰的所有節(jié)點(diǎn)都不滿足半團(tuán)定義,那么T是一個(gè)最大半團(tuán)。
為了構(gòu)建CBNL結(jié)構(gòu),首先搜索G中所有包含3個(gè)屬性的子團(tuán)(即3-clique);然后對(duì)每個(gè)子團(tuán)進(jìn)行擴(kuò)展,找到G中所有的最大半團(tuán)C={C1,C2,…,Cm};其次向每個(gè)最大半團(tuán)中插入表示用戶偏好的隱變量,得到m個(gè)候選模型結(jié)構(gòu);最后對(duì)每一個(gè)模型結(jié)構(gòu)分析與隱變量相關(guān)的依賴關(guān)系,據(jù)此判斷該隱變量是否能夠表示用戶偏好。任選一個(gè)模型結(jié)構(gòu)作為最終的CBNL結(jié)構(gòu)GL,見(jiàn)算法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對(duì)任意與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(zhǎng)的父節(jié)點(diǎn)
EndFor
在m個(gè)候選結(jié)構(gòu)δ1,δ2,…,δm中選擇一個(gè)作為GL
ReturnGL
例如,對(duì)于表1中的評(píng)分?jǐn)?shù)據(jù)集D及相關(guān)屬性,由算法1可得到如圖1(a)所示的CBN結(jié)構(gòu);再由算法2可以找到2個(gè)3-clique,C1={X1,X3,X4},C2={X2,X3,X4},分別對(duì)其擴(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算法來(lái)估算該結(jié)構(gòu)中各節(jié)點(diǎn)的CPT。EM算法從隨機(jī)產(chǎn)生的初始值θ0開(kāi)始迭代,假設(shè)已迭代了t-1次,那么第t次迭代由如下步驟完成。
E步:基于θt-1對(duì)隱變量取值進(jìn)行修補(bǔ),利用式(5)計(jì)算期望對(duì)數(shù)似然函數(shù)。
(5)
其中:m是評(píng)分?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)定值。
例如,針對(duì)圖1(b)所示的CBNL結(jié)構(gòu),鑒于描述的方便,假定商品評(píng)分?jǐn)?shù)據(jù)中的每個(gè)屬性可能取值數(shù)為2,基于EM算法得到各節(jié)點(diǎn)的CPT,最終的CBNL如圖2所示。
圖2 最終的CBNL
為了進(jìn)行基于CBNL的用戶偏好發(fā)現(xiàn),對(duì)CBNL進(jìn)行概率推理時(shí),把隱變量作為目標(biāo)變量,把CBNL中與隱變量有直接依賴關(guān)系的屬性作為證據(jù)變量(即已知變量)。經(jīng)過(guò)Gibbs采樣算法多次迭代計(jì)算得到隱變量的最大后驗(yàn)概率值,將計(jì)算出的概率值與給定的偏好閾值進(jìn)行比較,從而發(fā)現(xiàn)用戶對(duì)商品類型是否有偏好。
Gibbs采樣算法從滿足條件分布中迭代地進(jìn)行抽樣,當(dāng)?shù)螖?shù)足夠大時(shí),就可以得到來(lái)自聯(lián)合后驗(yàn)分布的樣本。為了簡(jiǎn)化計(jì)算而又不失一般性,對(duì)于隱變量的計(jì)算僅考慮其馬爾可夫覆蓋(X的馬爾可夫覆蓋包括X的直接孩子節(jié)點(diǎn)、X的直接父節(jié)點(diǎn)、以及X的直接孩子的其他父節(jié)點(diǎn)的集合,記為MB(X))中的節(jié)點(diǎn)對(duì)它的影響。見(jiàn)算法3。
算法3 基于Gibbs采樣的CBNL概率推理。
輸入GL=(V,L,E,θ),證據(jù)變量集合Φ,Φ的取值e,非證據(jù)變量L,L的取值l,遍歷次數(shù)s;
輸出P(L=1|e)。
1)
初始化。 隨機(jī)地為L(zhǎng)賦值,v0←e∪l,N[l]←0
/*N[l]為L(zhǎng)取1的個(gè)數(shù)*/
2)
產(chǎn)生樣本序列。Fork←1tosDoFor每一個(gè)樣本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)個(gè)樣本中去除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)為用戶對(duì)這樣的商品類型有偏好。文獻(xiàn)[16, 22]指出,只要采樣次數(shù)足夠多,Gibbs采樣算法總能收斂到一個(gè)穩(wěn)定的正確值,后面將通過(guò)實(shí)驗(yàn)進(jìn)一步測(cè)試算法3的收斂性和正確性。
針對(duì)圖2中的CBNL,計(jì)算P(L=1|X1=k1,X2=t1,X3=T,X4=1)。隨機(jī)地為L(zhǎng)賦值得到D0=[X1=k1,X2=t1,L=0,X3=T,X4=1]。第一次對(duì)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,表明用戶對(duì)發(fā)行年代為t1、好評(píng)、高分的電影類型t1有偏好。
本文使用MovieLens[19]上用戶評(píng)分?jǐn)?shù)據(jù)作為測(cè)試數(shù)據(jù)集,包含6 040個(gè)用戶對(duì)3 900部電影的1 000 209條評(píng)分?jǐn)?shù)據(jù),將電影類型、發(fā)行年代、評(píng)價(jià)(從標(biāo)簽中抽取出來(lái))和評(píng)分4個(gè)屬性作為CBNL的節(jié)點(diǎn)。實(shí)驗(yàn)環(huán)境:IntelPentiumDual-Core2.0GHz處理器,2GB內(nèi)存,Windows7(32位)操作系統(tǒng),使用MatlabR2012b作為開(kāi)發(fā)平臺(tái)。
首先,測(cè)試基于BMF模型進(jìn)行評(píng)分值填補(bǔ)結(jié)果的準(zhǔn)確性,并在不同的數(shù)據(jù)量情形下與PMF[4]、BPMF[5]模型進(jìn)行比較。用平均絕對(duì)誤差(MeanAbsoluteError,MAE)和均方根誤差(RootMeanSquaredError,RMSE)作為衡量填補(bǔ)結(jié)果準(zhǔn)確性的依據(jù),MAE和RMSE值越小,說(shuō)明填補(bǔ)的數(shù)據(jù)與真實(shí)數(shù)據(jù)之間的誤差越小。如圖3、圖4所示,在不同數(shù)據(jù)量情形下,BMF模型填補(bǔ)數(shù)據(jù)時(shí)的MAE和RMSE值均最小,這說(shuō)明BMF模型在數(shù)據(jù)填補(bǔ)時(shí)更為準(zhǔn)確。
圖3 MAE值
圖4 RMSE值
然后,測(cè)試CBNL構(gòu)建算法的執(zhí)行效率。在數(shù)據(jù)實(shí)例為2×104情形下,測(cè)試節(jié)點(diǎn)數(shù)分別為5、7、9、11、13時(shí)構(gòu)建CBNL的時(shí)間開(kāi)銷,結(jié)果如圖5所示,表明構(gòu)建CBNL的時(shí)間開(kāi)銷主要取決于參數(shù)計(jì)算;還測(cè)試了數(shù)據(jù)實(shí)例數(shù)分別為1×104、10×104、20×104,…,60×104時(shí)構(gòu)建CBNL的時(shí)間開(kāi)銷,結(jié)果如圖6所示,也表明CBNL構(gòu)建的時(shí)間主要取決于參數(shù)計(jì)算,且隨著數(shù)據(jù)實(shí)例數(shù)的增加基本呈線性趨勢(shì)增加。
圖5 不同節(jié)點(diǎn)數(shù)的CBNL構(gòu)建效率
進(jìn)一步,測(cè)試了參數(shù)計(jì)算的準(zhǔn)確性。從測(cè)試數(shù)據(jù)集中選取包括5×104、10×104、15×104個(gè)數(shù)據(jù)實(shí)例的片段,把其中一個(gè)已知屬性值當(dāng)作未知的,用EM算法迭代計(jì)算MLE值,然后用得到的MLE值與原MLE值進(jìn)行對(duì)比,將其比值作為誤差來(lái)衡量參數(shù)計(jì)算的準(zhǔn)確性,結(jié)果如圖7所示??梢钥闯?,隨著迭代次數(shù)的增加,EM算法收斂到一個(gè)穩(wěn)定的值,且數(shù)據(jù)量越大,計(jì)算出的MLE值與真實(shí)值越接近。
其次,測(cè)試了基于CBNL推理發(fā)現(xiàn)用戶偏好的效率,圖8和圖9分別給出了在不同數(shù)據(jù)量的情形下,隨著采樣次數(shù)增加,算法3返回結(jié)果的收斂性和執(zhí)行的時(shí)間開(kāi)銷。從圖8可以看出,隨著采樣次數(shù)的增加,不同數(shù)據(jù)量情形下的推理結(jié)果均能快速地收斂到一個(gè)穩(wěn)定的值;從圖9可以看出,在不同數(shù)據(jù)量的情形下,算法3的執(zhí)行時(shí)間均能隨著采樣次數(shù)呈線性增長(zhǎng)。
圖6 不同實(shí)例數(shù)的CBNL構(gòu)建效率
圖7 CBNL參數(shù)計(jì)算的準(zhǔn)確性
圖8 CBNL近似推理結(jié)果收斂性
圖9 CBNL推理算法效率
最后,測(cè)試了基于CBNL推理發(fā)現(xiàn)用戶偏好的準(zhǔn)確性。假設(shè)評(píng)分?jǐn)?shù)據(jù)中的評(píng)分反映了真實(shí)的用戶偏好,針對(duì)4或5分的評(píng)價(jià),通過(guò)多次實(shí)驗(yàn)確定偏好閾值為0.67。隨機(jī)選取3名用戶(記為u1、u2和u3),同時(shí)選取20部他們都評(píng)價(jià)過(guò)的電影作為測(cè)試數(shù)據(jù),其中10部電影的評(píng)價(jià)作為訓(xùn)練數(shù)據(jù),剩下10部電影的評(píng)價(jià)作為對(duì)比數(shù)據(jù)。表3給出了3名用戶對(duì)10部電影的評(píng)分。
表3 用戶對(duì)電影的評(píng)分信息
將基于協(xié)同過(guò)濾(CollaborativeFiltering,CF)的方法[23]和本文方法進(jìn)行對(duì)比,該CF方法預(yù)測(cè)評(píng)分時(shí)定義了一個(gè)推薦值來(lái)適當(dāng)?shù)靥岣呶粗唐返脑u(píng)分。本文方法選定u1為目標(biāo)用戶,基于余弦相似度得到u1和u3最相似,將后10部電影按u1的喜好推薦給u3。其中表4給出他們對(duì)后10部電影的評(píng)分信息,u1的評(píng)分是真實(shí)的用戶評(píng)分,通過(guò)CF預(yù)測(cè)得到u3的評(píng)分與u3真實(shí)的評(píng)分相比,正確率為60%,通過(guò)本文方法發(fā)現(xiàn)用戶偏好的正確率為70%。可以看出,基于本文方法發(fā)現(xiàn)用戶偏好的結(jié)果比CF預(yù)測(cè)得到的評(píng)分正確率高,這從一定程度上說(shuō)明了本文方法的正確性和有效性。
表4 用戶對(duì)電影的預(yù)測(cè)評(píng)分信息
本文基于隱變量模型和概率推理,提出了從商品評(píng)分?jǐn)?shù)據(jù)中發(fā)現(xiàn)用戶偏好的方法,解決了現(xiàn)有方法不能描述評(píng)分?jǐn)?shù)據(jù)中相關(guān)屬性間任意形式的依賴關(guān)系問(wèn)題,可支持實(shí)際中商品推薦和用戶定向等應(yīng)用。
作為基于概率圖模型進(jìn)行偏好發(fā)現(xiàn)的初步試探性研究,本文構(gòu)建隱變量模型時(shí)只引入一個(gè)二值隱變量,且未考慮評(píng)分?jǐn)?shù)據(jù)大規(guī)模和動(dòng)態(tài)性。引入多個(gè)隱變量、考慮與實(shí)際更吻和的情形,從海量用戶評(píng)分?jǐn)?shù)據(jù)中來(lái)發(fā)現(xiàn)用戶偏好,滿足海量數(shù)據(jù)處理需求和針對(duì)實(shí)際情形下用戶偏好發(fā)現(xiàn)的可行性,是將來(lái)要開(kāi)展的工作。
)
[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)目:國(guó)家自然科學(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會(huì)員,主要研究方向:知識(shí)發(fā)現(xiàn)、社會(huì)媒體數(shù)據(jù)分析; 岳昆(1979—),男,云南曲靖人,教授,博士生導(dǎo)師,博士,CCF會(huì)員,主要研究方向:海量數(shù)據(jù)分析與服務(wù); 武浩(1979—),男,河南平頂山人,副教授,博士,主要研究方向:信息檢索、推薦系統(tǒng)、服務(wù)計(jì)算; 付曉東(1975—),男,云南鎮(zhèn)雄人,教授,博士,CCF會(huì)員,主要研究方向:服務(wù)計(jì)算、智能決策;劉惟一(1950—),男,云南昆明人,教授,博士生導(dǎo)師,CCF會(huì)員,主要研究方向:人工智能、數(shù)據(jù)與知識(shí)工程。
1001- 9081(2017)02- 0360- 07
10.11772/j.issn.1001- 9081.2017.02.0360
TP311.13; TP181
A