李 莉,唐曉嘉(西南大學(xué)邏輯與智能研究中心,重慶400715)
?
基于判斷聚合模型的推薦系統(tǒng)冷啟動(dòng)問題研究
李莉,唐曉嘉
(西南大學(xué)邏輯與智能研究中心,重慶400715)
[摘要]推薦系統(tǒng)是目前解決用戶信息過載的主要工具,協(xié)同過濾算法是推薦系統(tǒng)中應(yīng)用最為廣泛的技術(shù),它主要依賴用戶已有的歷史數(shù)據(jù)為其尋找有相似的其他用戶,然而,當(dāng)遇到新用戶第一次訪問的情況下,這類技術(shù)一般很難給出恰當(dāng)?shù)耐扑],這就是著名的用戶冷啟動(dòng)問題。運(yùn)用判斷聚合理論的技術(shù)手段把已有用戶的行為數(shù)據(jù)聚合成為集體判斷集,然后將這個(gè)集體判斷集推送給新用戶,新用戶根據(jù)自身的偏好購買感興趣的物品,這一方法既解決了新用戶的冷啟動(dòng)問題,又豐富和拓展了推薦系統(tǒng)的功能。
[關(guān)鍵詞]判斷聚合模型;推薦系統(tǒng);冷啟動(dòng);協(xié)同過濾
隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展和應(yīng)用,人類從信息匱乏時(shí)代步入了信息過載的時(shí)代。為了解決信息過載問題,科學(xué)家們已經(jīng)開發(fā)出了一系列解決方案,例如搜索引擎技術(shù)就是非常成功的案例。然而,當(dāng)用戶無法確切地描述自己的需求時(shí),搜索引擎就無法幫助他們找到適合的信息,此時(shí)需要一項(xiàng)技術(shù)通過分析用戶的歷史偏好,然后據(jù)此推薦適合的信息,這項(xiàng)技術(shù)叫做推薦系統(tǒng)(Recommender Systems,RSs)[1],它可以將用戶和產(chǎn)品很快聯(lián)系起來,讓用戶可以在海量的物品中找到適合的物品,并且使物品找到合適的用戶。
協(xié)同過濾算法是應(yīng)用最為廣泛的推薦系統(tǒng)技術(shù),它是1992年由Goldberg等人提出的?;谟脩舻膮f(xié)同過濾算法以用戶為研究對(duì)象,尋找與目標(biāo)用戶有著相似興趣的用戶集合,然后將集合中用戶喜歡的,但目標(biāo)用戶不曾聽說的物品推薦給他[2]。然而,當(dāng)一個(gè)新用戶第一次使用該網(wǎng)站,由于缺乏可用的歷史數(shù)據(jù),基于用戶的協(xié)同過濾算法無法給新用戶推薦物品,推薦系統(tǒng)對(duì)新用戶失效,這就是用戶的“冷啟動(dòng)”問題。目前,學(xué)者們對(duì)用戶冷啟動(dòng)問題進(jìn)行了大量的研究,例如,Sahebi和Cohen提出運(yùn)用社交網(wǎng)絡(luò)數(shù)據(jù)解決用戶冷啟動(dòng)問題[3];Park和Chu提出了一個(gè)預(yù)測(cè)特征回歸模型來解決冷啟動(dòng)問題等[4]。
判斷聚合模型(judgment aggregation model)[5]將集體決策放入更為一般的邏輯框架之內(nèi)進(jìn)行研究,更加明晰地揭示了邏輯與集體決策之間的密切聯(lián)系。給定議程A={a,b,c…}和個(gè)體集U={u1,…,un},個(gè)體根據(jù)自己的偏好對(duì)議程A中的議題進(jìn)行判斷得到個(gè)體判斷集,模型以個(gè)體判斷集作為輸入,通過判斷聚合機(jī)制得到集體決策,判斷聚合機(jī)制通常表現(xiàn)為特定的判斷聚合規(guī)則。
本文將利用判斷聚合模型刻畫集體決策過程,把已有用戶的行為數(shù)據(jù)進(jìn)行聚合形成一個(gè)集體判斷集,然后將這個(gè)集體判斷集推薦給新用戶,進(jìn)而解決用戶冷啟動(dòng)問題。為此,本文要首先基于命題邏輯建立判斷聚合模型,然后選擇一組有歷史數(shù)據(jù)的用戶,在此基礎(chǔ)上,運(yùn)用判斷聚合模型將已有用戶的歷史數(shù)據(jù)聚合成為集體判斷集,最后將這個(gè)集體決策結(jié)果推送給新用戶。
設(shè)計(jì)基于判斷聚合模型的協(xié)同過濾算法來解決用戶冷啟動(dòng)問題,主要是以網(wǎng)站中已有的其他用戶的行為數(shù)據(jù)為輸入,通過判斷聚合機(jī)制將這些個(gè)體的意見或者評(píng)價(jià)聚合成為集體的意見或者評(píng)價(jià),然后將這個(gè)集體的意見推薦給新用戶,算法如圖1所示:
(圖1) 基于判斷聚合模型的協(xié)同過濾算法
從圖1中我們可以看到,基于判斷聚合模型的協(xié)同過濾算法包括三個(gè)階段:第一階段,尋找一組有歷史數(shù)據(jù)的用戶,將他們的用戶-物品評(píng)分矩陣輸入到計(jì)算模塊;第二階段,建立判斷聚合模型將用戶-物品評(píng)分矩陣轉(zhuǎn)化成為個(gè)體判斷集,然后運(yùn)用判斷聚合規(guī)則將個(gè)體判斷集聚合成為集體判斷集;第三階段,將集體判斷集推薦給新用戶,從而解決用戶的冷啟動(dòng)問題。我們現(xiàn)在分階段說明基于判斷聚合模型的協(xié)同過濾算法。
第一階段:尋找一組有歷史數(shù)據(jù)的用戶
根據(jù)孔多塞陪審團(tuán)定理(Condorcet Jury Theorem)[6],即當(dāng)所有的個(gè)體都是獨(dú)立的且他們有同等做出正確決定的概率,那么個(gè)體越多,集體做出正確決定的概率就越大,并且隨著個(gè)體數(shù)量的增多,集體做出正確決定的概率隨之增加直至趨向1,換句話說,集體通常做出正確決定的概率遠(yuǎn)遠(yuǎn)大于個(gè)體,該條定理說明了集體決策通常比個(gè)體更加明智,我們假設(shè)新用戶總是愿意采納之前用戶提供的建議,因此,首先我們需要找到一組有歷史數(shù)據(jù)的用戶,這是實(shí)現(xiàn)新算法的第一步。
假設(shè)目標(biāo)用戶張三在之前從未訪問過該網(wǎng)站,我們需要圍繞目標(biāo)用戶找到一組有歷史數(shù)據(jù)的用戶,如果張三進(jìn)行了注冊(cè),我們可以獲取少量關(guān)于他的數(shù)據(jù),例如性別、IP地址或者是年齡,通過這些信息,我們可以匹配一些和他年紀(jì)相仿、性別相同并且處于同一個(gè)地區(qū)的一組用戶;如果張三通過Facebook、Twitter、QQ或者微博微信等賬戶進(jìn)行關(guān)聯(lián)登錄,我們可以獲取部分他公開的有共同興趣愛好的好友、他所感興趣的微博或者Twitter話題等信息,通過了解這些信息,我們可以匹配一些與他有相似興趣的一組有歷史數(shù)據(jù)的用戶。然而,很多時(shí)候目標(biāo)用戶既沒有注冊(cè)數(shù)據(jù)又沒有用其他的社交網(wǎng)絡(luò)賬戶關(guān)聯(lián)登錄,此時(shí)我們可以單純憑借IP地址的定位來隨機(jī)選擇一組與目標(biāo)用戶同一地區(qū)的用戶作為參照,但要求這些用戶的數(shù)據(jù)一定是足夠可以做出集體決策的,過于稀疏的數(shù)據(jù)會(huì)導(dǎo)致整個(gè)算法失效。
第一階段主要目標(biāo)是尋找一組有歷史數(shù)據(jù)的用戶作為目標(biāo)用戶的參照,一般來說為了避免平局的情形我們選擇多于三個(gè)有歷史數(shù)據(jù)的用戶并且最好數(shù)目為單數(shù)。
例1:假定目標(biāo)用戶是張三,根據(jù)上述選擇參照用戶的方法,選定五位參照用戶形成一個(gè)臨時(shí)的集體,U={u1,u2,u3,u4,u5},他們均對(duì)五種物品有過購買記錄并且有過評(píng)分,物品集I={I1,I2,I3,I4,I5},用戶-物品評(píng)分矩陣如表1所示,5分表示用戶對(duì)物品的滿意程度最高,1分表示用戶對(duì)物品的滿意程度最低。
第二階段:基于判斷聚合模型得到集體判斷集
(表1) 用戶-物品評(píng)分矩陣
判斷聚合模型用于改造協(xié)同過濾算法,是本文探索的新方法。運(yùn)用基于判斷聚合模型的協(xié)同過濾算法,首先要將用戶-物品評(píng)分矩陣按照判斷聚合模型的定義轉(zhuǎn)變?yōu)榕袛嘟M合,然后利用判斷聚合規(guī)則將個(gè)體判斷集聚合成為集體判斷集,最后將這個(gè)一致的集體判斷集推薦給新用戶,從而解決用戶冷啟動(dòng)問題。
2.1判斷聚合模型
選定有歷史數(shù)據(jù)的用戶集U={u1,…,un}(n≥3),即有歷史數(shù)據(jù)的用戶至少要3人,I={I1,…,Im}(m≥2)為非空的物品集。假設(shè)有歷史數(shù)據(jù)的用戶都對(duì)命題邏輯系統(tǒng)L中的命題進(jìn)行了判斷,L中包含原子命題p,q,r,……,所有復(fù)合命題都由原子命題和命題聯(lián)結(jié)詞┐(否定)、∧(合?。?、∨(析取)、→(實(shí)質(zhì)蘊(yùn)涵)等命題連接詞組成,L中也包含矛盾式⊥(contradiction),以及它的否定重言式(tautology)。
判斷聚合模型一個(gè)基本的假設(shè)是:參與判斷的所有用戶都是完全理性的,即作出的判斷既是一致的又是完全的。所謂一致的是指作出的判斷不能具有矛盾,所謂完全的是指對(duì)于所有待斷定的命題都要作出判斷。相關(guān)概念定義如下:
議題(Issues)指待判斷的命題。顯然,議題可以是L中除了矛盾式外的任一命題。議題既不可以是重言式,也不可以是矛盾式,因?yàn)樗鼈儧]有判斷的必要。
議程(Agenda)由議題以及議題的否定形式構(gòu)成的集合稱作議程,記作A。本文中議程A={SIi,j|Ii∈I,1≤j≤|I|}∪{┐SIi,j|Ii∈I,1≤j≤|I|},議題SIi,j表示用戶給物品集I中的任一物品Ii打j分,如果物品集中一共有5件物品,那么用戶對(duì)物品Ii的評(píng)分最低為1分最高為5分。為了編程的方便,我們?cè)谖闹袦p少了下標(biāo)的數(shù)量,用Si,j取代SIi,j表示用戶給物品集I中的任一物品Ii打j分,即SI i,j簡(jiǎn)記為Si,j。
預(yù)議程(Pre-agenda)由議題本身構(gòu)成的集合稱為預(yù)議程,記作[A]。為了文中論述方便,預(yù)議程中只包含議題本身并不包含它們的否定,即[A]={SIi,j|Ii∈I,1≤j≤|I|}。
限制條件(Constraints)是參與判斷用戶在對(duì)議程中議題判斷時(shí)應(yīng)遵循的條件,用Γ表示。Γ是L中的一個(gè)公式,即?!蔐,本文中Γ=∧{┐(Si,j∧Si,j′)|i∈I,j≠j′,1≤j,j′≤|I|}∪∧{┐(Si,j∧Si′,j)|i,i′∈I,i≠i′,1≤j≤|I|}。為了得到一致且完全的個(gè)體判斷集,限制條件要求用戶給每一種物品打出唯一的一個(gè)分?jǐn)?shù),系統(tǒng)不接受一個(gè)物品有兩個(gè)分?jǐn)?shù)和兩個(gè)物品有相同的分?jǐn)?shù)的情況。
判斷集(Judgment set)是與個(gè)體和集體相關(guān)的概念,用J表示。令U是參加判斷的用戶,U={u1,...,un}(n≥3),則任一用戶uk(1≤k≤n)的判斷集是一個(gè)一致的且完全的集合。判斷集Jk是Γ-一致當(dāng)且僅當(dāng),一致性保證了個(gè)體或集體所作出的判斷都是理性的;同時(shí)Jk是完全的當(dāng)且僅當(dāng)對(duì)于議程[A]中的任一議題φ∈[A],要么φ∈Jk要么┐φ∈Jk,判斷集的完全性保證了個(gè)體對(duì)議程中每一項(xiàng)議題都作出判斷。本文中將所有Γ-一致且完全的判斷集記作D(A,Γ)。
判斷組合(Judgment profile)由所有個(gè)體的判斷集組成的n元組稱作判斷組合,可表示為P=(J1,…,Jn)∈Dn(A)。我們用N(P,Si,j)表示判斷組合P中有多少個(gè)用戶的判斷集中包含有Si,j,也就是N(P,Si,j)=#{k|Jk∈P,Si,j∈Jk}。
定義1判斷聚合規(guī)則(Judgment aggregation rules)令U是參加判斷的用戶集,議程A?L,一個(gè)判斷聚合規(guī)則是以所有個(gè)體的判斷集構(gòu)成的n元判斷組合P=(J1,…,Jn)(Jk∈D(A,Γ))為輸入,輸出一個(gè)在A和Γ上非空的集體判斷集J。
2.2基于判斷聚合模型的集體決策過程
根據(jù)判斷聚合模型的定義,預(yù)議程[A]={S1,1,...,Si,j,....},限制條件Γ=∧{┐(Si,j∧Si,j′)|i∈I,j≠j′,1≤j,j′≤|I|}∪∧{┐(Si,j∧Si′,j)|i,i′∈I,i≠i′,1≤j≤|I|},我們將用戶-物品評(píng)分矩陣變形為|U|×|I|2的判斷組合,縱列為選定的有歷史記錄的用戶集U,橫行為物品Ii的所有可能的得分Si,j,根據(jù)模型中的定義若user1給I1打5分,那么在判斷組合中user1與S1,5交叉的空格里標(biāo)上“1”,其余與S1,1、S1,2、S1,3和S1,4交叉的空格里都為“0”。換而言之,由評(píng)分矩陣轉(zhuǎn)變?yōu)榕袛嘟M合的過程是所有用戶對(duì)議題的判斷過程。每位用戶根據(jù)自己的偏好給出他們對(duì)所有議題的判斷,用“1”表示贊同,“0”表示反對(duì)。
例2:仍用例1中選定的用戶集U和物品集I,根據(jù)判斷聚合模型預(yù)議程為[A]={S1,1,S1,2,...,S5,5},即所有用戶要對(duì)這些議題進(jìn)行判斷,而且限制條件為Γ=∧{┐(Si,j∧Si,j′)|i∈I,j≠j′,1≤j,j′≤|I|}∪∧{┐(Si,j∧Si′,j)|i,i′∈I,i≠i′,1≤j≤|I|}。根據(jù)上述分析,我們將表1的用戶-物品評(píng)分矩陣轉(zhuǎn)變?yōu)楸?的判斷組合P。
從判斷組合P可以看到每一位用戶的個(gè)體判斷集:user1的個(gè)體判斷集為J1={S1,5,S2,3,S3,4,S4,1,S5,2},這個(gè)判斷集中沒有兩個(gè)物品有同樣的分?jǐn)?shù),也沒有一個(gè)物品有兩個(gè)分?jǐn)?shù)的情形,即J1是Γ-一致的,同時(shí)user1對(duì)議程A中的所有議題都進(jìn)行了判斷,因而J1也是完全的,J1既是一致又是完全的,因而,user1是理性的用戶。同理,user2的個(gè)體判斷集J2={S1,5,S2,4,S3,3,S4,2,S5,1},user3的個(gè)體判斷集J3={S1,1,S2,4,S3,3,S4,2,S5,5},user4的個(gè)體判斷集J4={S1,2,S2,4,S3,3,S4,5,S5,1},user5的個(gè)體判斷集J5={S1,5,S2,3,S3,4,S4,2,S5,1},這些判斷集中沒有兩個(gè)物品有同樣的分?jǐn)?shù),也沒有一個(gè)物品有兩個(gè)分?jǐn)?shù)的情形,即它們都是Γ-一致的,且對(duì)議程A中的所有議題都進(jìn)行了判斷,因而這些個(gè)體判斷集都是完全的,這些個(gè)體判斷都是一致又是完全的,故而,這些用戶是理性的用戶,所有用戶的個(gè)體判斷形成判斷組合P=(J1,…,J5),現(xiàn)在選定一種判斷聚合規(guī)則將這些個(gè)體的判斷集聚合成為集體判斷集,為了最大化地保留所有個(gè)體的判斷信息,我們選用最常用的多數(shù)聚合規(guī)則[7]。
(表2) 判斷組合P
定義2多數(shù)聚合規(guī)則(Majoritartian aggregation rule)輸出的判斷集是由多數(shù)人贊成的議題構(gòu)成,即對(duì)任一J∈D(A,Γ),J={Si,j∈A|N(P,φ)>n/2},多數(shù)聚合規(guī)則記作Fmaj,由多數(shù)聚合規(guī)則得到的集體判斷集記作JFmaj。
運(yùn)用多數(shù)聚合規(guī)則求得例2的集體判斷集,判斷組合P如上表2中所示,首先求得所有議題的支持人數(shù),結(jié)果如下:
N(P,S1,1)=1;N(P,S1,2)=1;N(P,S1,3)=0;N(P,S1,4)=0;N(P,S1,5)=3;N(P,S2,1)=0;N(P,S2,2)=0;N(P,S2,3)=2;N(P,S2,4)=3;N(P,S2,5)=0;N(P,S3,1)=0;N(P,S3,2)=0;N(P,S3,3)=3;N(P,S3,4)=2;N(P,S3,5)=0;N(P,S4,1)=1;N(P,S4,2)=3;N(P,S4,3)=0;N(P,S4,4)=0;N(P,S4,5)=1;N(P,S5,1)=3;N(P,S5,2)=1;N(P,S5,3)=0;N(P,S5,4)=0;N(P,S5,5)=1。
根據(jù)上述對(duì)每一項(xiàng)議題的支持人數(shù),可得到過半數(shù)用戶支持的議題組成的集體判斷集為{S1,5,S2,4,S3,3,S4,2,S5,1},即集體判斷集JFmaj={S1,5,S2,4,S3,3,S4,2,S5,1},這個(gè)集合中既不存在兩個(gè)物品有同樣的分?jǐn)?shù),也不存在一個(gè)物品有兩個(gè)分?jǐn)?shù),即JFmaj∪{Γ}是推不出矛盾的,因此,JFmaj是Γ-一致的,同時(shí)集體判斷集JFma j中對(duì)A所有議題都進(jìn)行了判斷,因此是JFmaj完全的,所以JFmaj是一致且完全的集體判斷集,它可以作為集體決策執(zhí)行下去。
2.3程序演示
我們用.NET平臺(tái)開發(fā)的演示程序包含三個(gè)表:第一個(gè)表輸入用戶-物品評(píng)分矩陣,第二個(gè)表是將用戶-物品評(píng)分矩陣轉(zhuǎn)化為包含所有個(gè)體判斷集的判斷組合,第三個(gè)表輸出經(jīng)過聚合機(jī)制之后得到的集體判斷集,輸出的集體判斷集也即是給新用戶的推薦內(nèi)容。
如圖2所示,第一個(gè)表中輸入用戶-物品評(píng)分矩陣,以例1中的用戶-物品評(píng)分矩陣為例,第二個(gè)表中是基于判斷聚合模型將第一個(gè)表中矩陣轉(zhuǎn)化為判斷組合P,并同時(shí)在sum一行中計(jì)算出所有議題的支持人數(shù),在第三個(gè)表中運(yùn)用多數(shù)聚合規(guī)則之后得到的集體判斷集,用黑色方框標(biāo)注集體對(duì)所有的物品的評(píng)分。
第三階段:將集體判斷集推送給新用戶
在第二階段中,運(yùn)用判斷聚合模型將個(gè)體判斷集聚合成為集體判斷集,第三階段的主要任務(wù)是將這個(gè)集體判斷集推送給新用戶。
(圖2) 基于判斷聚合模型運(yùn)用多數(shù)聚合規(guī)則得到集體判斷集的推薦過程
在判斷聚合模型上,運(yùn)用多數(shù)聚合規(guī)則得到的集體判斷集為JFmaj={S1,5,S2,4,S3,3,S4,2,S5,1},這個(gè)集體判斷集提供了兩方面的信息:第一,我們可以得到集體對(duì)物品集中物品的偏好排序,即這組選定的參照用戶集認(rèn)為I1是最好的,其次是I2、I3和I4,最差的是I5,這表明大多數(shù)用戶最喜歡I1,I2、I3和I4次之,最不喜歡I5;第二,判斷聚合模型得出的集體判斷集也同時(shí)給出了集體對(duì)每一類物品的精確評(píng)分,即集體給I1打5分,I2打4分,I3打3分,I4打2分,以及I5打1分。
在推薦階段將這個(gè)集體偏好序推薦給新用戶張三,張三也可以根據(jù)集體判斷集進(jìn)行個(gè)性化的選擇:第一,他會(huì)從集體判斷集中的物品里挑選自己感興趣但從未購買過的物品;第二,集體判斷集表明集體認(rèn)為I1是最好的,其次是I2、I3和I4,最差的是I5,對(duì)于得分最高的I1,如果他感興趣他會(huì)毫不猶豫地購買,而對(duì)于I2、I3和I4他可能需要了解更多信息才決定購買,但對(duì)于大家都不喜歡的I5,他可能感興趣但可能不會(huì)購買。如此一來,我們不僅解決了用戶冷啟動(dòng)問題,而且實(shí)現(xiàn)了新用戶個(gè)性化的推薦。
本文基于判斷聚合理論的技術(shù)手段嘗試解決了推薦系統(tǒng)中用戶冷啟動(dòng)的問題,從文中的探索來看,可以得出以下結(jié)論:第一,基于判斷聚合模型的協(xié)同過濾算法來解決用戶冷啟動(dòng)問題是以系統(tǒng)中已有用戶的歷史數(shù)據(jù)為輸入,通過分析已有用戶的歷史數(shù)據(jù)輸出新用戶個(gè)性化的推薦內(nèi)容;第二,基于判斷聚合模型的協(xié)同過濾算法不僅可以得到集體對(duì)物品的偏好排序,而且可以得到集體對(duì)物品的評(píng)分,這些內(nèi)容可以為新用戶提供更為精確的個(gè)體決策依據(jù)。
[附注]本文受到西南大學(xué)人文社會(huì)科學(xué)重要研究項(xiàng)目(編號(hào):12XDSKZ003)的資助。
[參考文獻(xiàn)]
[1]Kantor P B,Rokach L,Ricci F,et al.Recommender systems handbook[M].Berlin:Springer,2011.
[2]Goldberg D,Nichols D,Oki B M,et al.Using collaborative filtering to weave an information tapestry[J].Communications of the ACM,1992,35(12).
[3]Sahebi S,Cohen W W.Community-based recommendations:a solution to the cold start problem[M]//Proceedings of the 2011 ACM Conference on Recommender Systems.New York:ACM Press,2011.
[4]Park S T,Chu W.Pairwise preference regression for cold-start recommendation[M]//Proceedings of 3rd ACM conference on Recommender systems.New York:ACM Press,2009:21~28.
[5]List C,Pettit P.Aggregating sets of judgments:An impossibility result[J].Economics and Philosophy,2002,18(1).
[6]Wit J.Rational choice and the Condorcet jury theorem[J].Games and Economic Behavior,1998,22(2).
[7]Laang J,Pigozzi G,Slavkovik M,et al.Judgment aggregation rules based on minimization[M]//Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge.New York:ACM Press,2011:238~246.
[責(zé)任編輯:熊顯長]
[收稿日期]2015-10-09
[作者簡(jiǎn)介]李莉(1980-),女,內(nèi)蒙古巴彥淖爾人,西南大學(xué)邏輯與智能研究中心2011級(jí)博士研究生;唐曉嘉(1954-),女,廣西全州人,西南大學(xué)邏輯與智能研究中心教授、博士生導(dǎo)師,主要從事現(xiàn)代邏輯與人工智能研究。
[中圖分類號(hào)]B81
[文獻(xiàn)標(biāo)志碼]A
[文章編號(hào)]1001-4799(2016)02-0040-05