基于判斷聚合模型的推薦系統(tǒng)冷啟動問題研究

李　莉，唐曉嘉（西南大學(xué)邏輯與智能研究中心，重慶400715）

?

基于判斷聚合模型的推薦系統(tǒng)冷啟動問題研究

李莉，唐曉嘉
（西南大學(xué)邏輯與智能研究中心，重慶400715）

［摘要］推薦系統(tǒng)是目前解決用戶信息過載的主要工具，協(xié)同過濾算法是推薦系統(tǒng)中應(yīng)用最為廣泛的技術(shù)，它主要依賴用戶已有的歷史數(shù)據(jù)為其尋找有相似的其他用戶，然而，當(dāng)遇到新用戶第一次訪問的情況下，這類技術(shù)一般很難給出恰當(dāng)?shù)耐扑]，這就是著名的用戶冷啟動問題。運用判斷聚合理論的技術(shù)手段把已有用戶的行為數(shù)據(jù)聚合成為集體判斷集，然后將這個集體判斷集推送給新用戶，新用戶根據(jù)自身的偏好購買感興趣的物品，這一方法既解決了新用戶的冷啟動問題，又豐富和拓展了推薦系統(tǒng)的功能。

［關(guān)鍵詞］判斷聚合模型；推薦系統(tǒng)；冷啟動；協(xié)同過濾

1　問題的提出

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展和應(yīng)用，人類從信息匱乏時代步入了信息過載的時代。為了解決信息過載問題，科學(xué)家們已經(jīng)開發(fā)出了一系列解決方案，例如搜索引擎技術(shù)就是非常成功的案例。然而，當(dāng)用戶無法確切地描述自己的需求時，搜索引擎就無法幫助他們找到適合的信息，此時需要一項技術(shù)通過分析用戶的歷史偏好，然后據(jù)此推薦適合的信息，這項技術(shù)叫做推薦系統(tǒng)（Recommender Systems，RSs）[1]，它可以將用戶和產(chǎn)品很快聯(lián)系起來，讓用戶可以在海量的物品中找到適合的物品，并且使物品找到合適的用戶。

協(xié)同過濾算法是應(yīng)用最為廣泛的推薦系統(tǒng)技術(shù)，它是1992年由Goldberg等人提出的?；谟脩舻膮f(xié)同過濾算法以用戶為研究對象，尋找與目標(biāo)用戶有著相似興趣的用戶集合，然后將集合中用戶喜歡的，但目標(biāo)用戶不曾聽說的物品推薦給他[2]。然而，當(dāng)一個新用戶第一次使用該網(wǎng)站，由于缺乏可用的歷史數(shù)據(jù)，基于用戶的協(xié)同過濾算法無法給新用戶推薦物品，推薦系統(tǒng)對新用戶失效，這就是用戶的“冷啟動”問題。目前，學(xué)者們對用戶冷啟動問題進(jìn)行了大量的研究，例如，Sahebi和Cohen提出運用社交網(wǎng)絡(luò)數(shù)據(jù)解決用戶冷啟動問題[3]；Park和Chu提出了一個預(yù)測特征回歸模型來解決冷啟動問題等[4]。

判斷聚合模型（judgment aggregation model）[5]將集體決策放入更為一般的邏輯框架之內(nèi)進(jìn)行研究，更加明晰地揭示了邏輯與集體決策之間的密切聯(lián)系。給定議程A=｛a，b，c…｝和個體集U=｛u1，…，un｝，個體根據(jù)自己的偏好對議程A中的議題進(jìn)行判斷得到個體判斷集，模型以個體判斷集作為輸入，通過判斷聚合機(jī)制得到集體決策，判斷聚合機(jī)制通常表現(xiàn)為特定的判斷聚合規(guī)則。

本文將利用判斷聚合模型刻畫集體決策過程，把已有用戶的行為數(shù)據(jù)進(jìn)行聚合形成一個集體判斷集，然后將這個集體判斷集推薦給新用戶，進(jìn)而解決用戶冷啟動問題。為此，本文要首先基于命題邏輯建立判斷聚合模型，然后選擇一組有歷史數(shù)據(jù)的用戶，在此基礎(chǔ)上，運用判斷聚合模型將已有用戶的歷史數(shù)據(jù)聚合成為集體判斷集，最后將這個集體決策結(jié)果推送給新用戶。

2　基于判斷聚合模型的協(xié)同過濾算法

設(shè)計基于判斷聚合模型的協(xié)同過濾算法來解決用戶冷啟動問題，主要是以網(wǎng)站中已有的其他用戶的行為數(shù)據(jù)為輸入，通過判斷聚合機(jī)制將這些個體的意見或者評價聚合成為集體的意見或者評價，然后將這個集體的意見推薦給新用戶，算法如圖1所示：

（圖1）　基于判斷聚合模型的協(xié)同過濾算法

從圖1中我們可以看到，基于判斷聚合模型的協(xié)同過濾算法包括三個階段：第一階段，尋找一組有歷史數(shù)據(jù)的用戶，將他們的用戶-物品評分矩陣輸入到計算模塊；第二階段，建立判斷聚合模型將用戶-物品評分矩陣轉(zhuǎn)化成為個體判斷集，然后運用判斷聚合規(guī)則將個體判斷集聚合成為集體判斷集；第三階段，將集體判斷集推薦給新用戶，從而解決用戶的冷啟動問題。我們現(xiàn)在分階段說明基于判斷聚合模型的協(xié)同過濾算法。

第一階段：尋找一組有歷史數(shù)據(jù)的用戶

根據(jù)孔多塞陪審團(tuán)定理（Condorcet Jury Theorem）[6]，即當(dāng)所有的個體都是獨立的且他們有同等做出正確決定的概率，那么個體越多，集體做出正確決定的概率就越大，并且隨著個體數(shù)量的增多，集體做出正確決定的概率隨之增加直至趨向1，換句話說，集體通常做出正確決定的概率遠(yuǎn)遠(yuǎn)大于個體，該條定理說明了集體決策通常比個體更加明智，我們假設(shè)新用戶總是愿意采納之前用戶提供的建議，因此，首先我們需要找到一組有歷史數(shù)據(jù)的用戶，這是實現(xiàn)新算法的第一步。

假設(shè)目標(biāo)用戶張三在之前從未訪問過該網(wǎng)站，我們需要圍繞目標(biāo)用戶找到一組有歷史數(shù)據(jù)的用戶，如果張三進(jìn)行了注冊，我們可以獲取少量關(guān)于他的數(shù)據(jù)，例如性別、IP地址或者是年齡，通過這些信息，我們可以匹配一些和他年紀(jì)相仿、性別相同并且處于同一個地區(qū)的一組用戶；如果張三通過Facebook、Twitter、QQ或者微博微信等賬戶進(jìn)行關(guān)聯(lián)登錄，我們可以獲取部分他公開的有共同興趣愛好的好友、他所感興趣的微博或者Twitter話題等信息，通過了解這些信息，我們可以匹配一些與他有相似興趣的一組有歷史數(shù)據(jù)的用戶。然而，很多時候目標(biāo)用戶既沒有注冊數(shù)據(jù)又沒有用其他的社交網(wǎng)絡(luò)賬戶關(guān)聯(lián)登錄，此時我們可以單純憑借IP地址的定位來隨機(jī)選擇一組與目標(biāo)用戶同一地區(qū)的用戶作為參照，但要求這些用戶的數(shù)據(jù)一定是足夠可以做出集體決策的，過于稀疏的數(shù)據(jù)會導(dǎo)致整個算法失效。

第一階段主要目標(biāo)是尋找一組有歷史數(shù)據(jù)的用戶作為目標(biāo)用戶的參照，一般來說為了避免平局的情形我們選擇多于三個有歷史數(shù)據(jù)的用戶并且最好數(shù)目為單數(shù)。

例1：假定目標(biāo)用戶是張三，根據(jù)上述選擇參照用戶的方法，選定五位參照用戶形成一個臨時的集體，U=｛u1，u2，u3，u4，u5｝，他們均對五種物品有過購買記錄并且有過評分，物品集I=｛I1，I2，I3，I4，I5｝，用戶-物品評分矩陣如表1所示，5分表示用戶對物品的滿意程度最高，1分表示用戶對物品的滿意程度最低。

第二階段：基于判斷聚合模型得到集體判斷集

（表1）　　用戶-物品評分矩陣

判斷聚合模型用于改造協(xié)同過濾算法，是本文探索的新方法。運用基于判斷聚合模型的協(xié)同過濾算法，首先要將用戶-物品評分矩陣按照判斷聚合模型的定義轉(zhuǎn)變?yōu)榕袛嘟M合，然后利用判斷聚合規(guī)則將個體判斷集聚合成為集體判斷集，最后將這個一致的集體判斷集推薦給新用戶，從而解決用戶冷啟動問題。

2.1判斷聚合模型

選定有歷史數(shù)據(jù)的用戶集U=｛u1，…，un｝（n≥3），即有歷史數(shù)據(jù)的用戶至少要3人，I=｛I1，…，Im｝（m≥2）為非空的物品集。假設(shè)有歷史數(shù)據(jù)的用戶都對命題邏輯系統(tǒng)L中的命題進(jìn)行了判斷，L中包含原子命題p，q，r，……，所有復(fù)合命題都由原子命題和命題聯(lián)結(jié)詞┐（否定）、∧（合?。?、∨（析取）、→（實質(zhì)蘊涵）等命題連接詞組成，L中也包含矛盾式⊥（contradiction），以及它的否定重言式（tautology）。

判斷聚合模型一個基本的假設(shè)是：參與判斷的所有用戶都是完全理性的，即作出的判斷既是一致的又是完全的。所謂一致的是指作出的判斷不能具有矛盾，所謂完全的是指對于所有待斷定的命題都要作出判斷。相關(guān)概念定義如下：

議題（Issues）指待判斷的命題。顯然，議題可以是L中除了矛盾式外的任一命題。議題既不可以是重言式，也不可以是矛盾式，因為它們沒有判斷的必要。

議程（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件物品，那么用戶對物品Ii的評分最低為1分最高為5分。為了編程的方便，我們在文中減少了下標(biāo)的數(shù)量，用Si，j取代SIi，j表示用戶給物品集I中的任一物品Ii打j分，即SI i，j簡記為Si，j。

預(yù)議程（Pre-agenda）由議題本身構(gòu)成的集合稱為預(yù)議程，記作［A］。為了文中論述方便，預(yù)議程中只包含議題本身并不包含它們的否定，即［A］=｛SIi，j|Ii∈I，1≤j≤|I|｝。

限制條件（Constraints）是參與判斷用戶在對議程中議題判斷時應(yīng)遵循的條件，用Γ表示。Γ是L中的一個公式，即?！蔐，本文中Γ=∧｛┐（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ǐn)?shù)，系統(tǒng)不接受一個物品有兩個分?jǐn)?shù)和兩個物品有相同的分?jǐn)?shù)的情況。

判斷集（Judgment set）是與個體和集體相關(guān)的概念，用J表示。令U是參加判斷的用戶，U=｛u1，...，un｝（n≥3），則任一用戶uk（1≤k≤n）的判斷集是一個一致的且完全的集合。判斷集Jk是Γ-一致當(dāng)且僅當(dāng)，一致性保證了個體或集體所作出的判斷都是理性的；同時Jk是完全的當(dāng)且僅當(dāng)對于議程［A］中的任一議題φ∈［A］，要么φ∈Jk要么┐φ∈Jk，判斷集的完全性保證了個體對議程中每一項議題都作出判斷。本文中將所有Γ-一致且完全的判斷集記作D（A，Γ）。

判斷組合（Judgment profile）由所有個體的判斷集組成的n元組稱作判斷組合，可表示為P=（J1，…，Jn）∈Dn（A）。我們用N（P，Si，j）表示判斷組合P中有多少個用戶的判斷集中包含有Si，j，也就是N（P，Si，j）=#｛k|Jk∈P，Si，j∈Jk｝。

定義1判斷聚合規(guī)則（Judgment aggregation rules）令U是參加判斷的用戶集，議程A?L，一個判斷聚合規(guī)則是以所有個體的判斷集構(gòu)成的n元判斷組合P=（J1，…，Jn）（Jk∈D（A，Γ））為輸入，輸出一個在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|｝，我們將用戶-物品評分矩陣變形為|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”。換而言之，由評分矩陣轉(zhuǎn)變?yōu)榕袛嘟M合的過程是所有用戶對議題的判斷過程。每位用戶根據(jù)自己的偏好給出他們對所有議題的判斷，用“1”表示贊同，“0”表示反對。

例2：仍用例1中選定的用戶集U和物品集I，根據(jù)判斷聚合模型預(yù)議程為［A］=｛S1，1，S1，2，...，S5，5｝，即所有用戶要對這些議題進(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的用戶-物品評分矩陣轉(zhuǎn)變?yōu)楸?的判斷組合P。

從判斷組合P可以看到每一位用戶的個體判斷集：user1的個體判斷集為J1=｛S1，5，S2，3，S3，4，S4，1，S5，2｝，這個判斷集中沒有兩個物品有同樣的分?jǐn)?shù)，也沒有一個物品有兩個分?jǐn)?shù)的情形，即J1是Γ-一致的，同時user1對議程A中的所有議題都進(jìn)行了判斷，因而J1也是完全的，J1既是一致又是完全的，因而，user1是理性的用戶。同理，user2的個體判斷集J2=｛S1，5，S2，4，S3，3，S4，2，S5，1｝，user3的個體判斷集J3=｛S1，1，S2，4，S3，3，S4，2，S5，5｝，user4的個體判斷集J4=｛S1，2，S2，4，S3，3，S4，5，S5，1｝，user5的個體判斷集J5=｛S1，5，S2，3，S3，4，S4，2，S5，1｝，這些判斷集中沒有兩個物品有同樣的分?jǐn)?shù)，也沒有一個物品有兩個分?jǐn)?shù)的情形，即它們都是Γ-一致的，且對議程A中的所有議題都進(jìn)行了判斷，因而這些個體判斷集都是完全的，這些個體判斷都是一致又是完全的，故而，這些用戶是理性的用戶，所有用戶的個體判斷形成判斷組合P=（J1，…，J5），現(xiàn)在選定一種判斷聚合規(guī)則將這些個體的判斷集聚合成為集體判斷集，為了最大化地保留所有個體的判斷信息，我們選用最常用的多數(shù)聚合規(guī)則[7]。

（表2）　判斷組合P

定義2多數(shù)聚合規(guī)則（Majoritartian aggregation rule）輸出的判斷集是由多數(shù)人贊成的議題構(gòu)成，即對任一J∈D（A，Γ），J=｛Si，j∈A|N（P，φ）>n/2｝，多數(shù)聚合規(guī)則記作Fmaj，由多數(shù)聚合規(guī)則得到的集體判斷集記作JFmaj。

運用多數(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ù)上述對每一項議題的支持人數(shù)，可得到過半數(shù)用戶支持的議題組成的集體判斷集為｛S1，5，S2，4，S3，3，S4，2，S5，1｝，即集體判斷集JFmaj=｛S1，5，S2，4，S3，3，S4，2，S5，1｝，這個集合中既不存在兩個物品有同樣的分?jǐn)?shù)，也不存在一個物品有兩個分?jǐn)?shù)，即JFmaj∪｛Γ｝是推不出矛盾的，因此，JFmaj是Γ-一致的，同時集體判斷集JFma j中對A所有議題都進(jìn)行了判斷，因此是JFmaj完全的，所以JFmaj是一致且完全的集體判斷集，它可以作為集體決策執(zhí)行下去。

2.3程序演示

我們用.NET平臺開發(fā)的演示程序包含三個表：第一個表輸入用戶-物品評分矩陣，第二個表是將用戶-物品評分矩陣轉(zhuǎn)化為包含所有個體判斷集的判斷組合，第三個表輸出經(jīng)過聚合機(jī)制之后得到的集體判斷集，輸出的集體判斷集也即是給新用戶的推薦內(nèi)容。

如圖2所示，第一個表中輸入用戶-物品評分矩陣，以例1中的用戶-物品評分矩陣為例，第二個表中是基于判斷聚合模型將第一個表中矩陣轉(zhuǎn)化為判斷組合P，并同時在sum一行中計算出所有議題的支持人數(shù)，在第三個表中運用多數(shù)聚合規(guī)則之后得到的集體判斷集，用黑色方框標(biāo)注集體對所有的物品的評分。

第三階段：將集體判斷集推送給新用戶

在第二階段中，運用判斷聚合模型將個體判斷集聚合成為集體判斷集，第三階段的主要任務(wù)是將這個集體判斷集推送給新用戶。

（圖2）　基于判斷聚合模型運用多數(shù)聚合規(guī)則得到集體判斷集的推薦過程

在判斷聚合模型上，運用多數(shù)聚合規(guī)則得到的集體判斷集為JFmaj=｛S1，5，S2，4，S3，3，S4，2，S5，1｝，這個集體判斷集提供了兩方面的信息：第一，我們可以得到集體對物品集中物品的偏好排序，即這組選定的參照用戶集認(rèn)為I1是最好的，其次是I2、I3和I4，最差的是I5，這表明大多數(shù)用戶最喜歡I1，I2、I3和I4次之，最不喜歡I5；第二，判斷聚合模型得出的集體判斷集也同時給出了集體對每一類物品的精確評分，即集體給I1打5分，I2打4分，I3打3分，I4打2分，以及I5打1分。

在推薦階段將這個集體偏好序推薦給新用戶張三，張三也可以根據(jù)集體判斷集進(jìn)行個性化的選擇：第一，他會從集體判斷集中的物品里挑選自己感興趣但從未購買過的物品；第二，集體判斷集表明集體認(rèn)為I1是最好的，其次是I2、I3和I4，最差的是I5，對于得分最高的I1，如果他感興趣他會毫不猶豫地購買，而對于I2、I3和I4他可能需要了解更多信息才決定購買，但對于大家都不喜歡的I5，他可能感興趣但可能不會購買。如此一來，我們不僅解決了用戶冷啟動問題，而且實現(xiàn)了新用戶個性化的推薦。

3　結(jié)論

本文基于判斷聚合理論的技術(shù)手段嘗試解決了推薦系統(tǒng)中用戶冷啟動的問題，從文中的探索來看，可以得出以下結(jié)論：第一，基于判斷聚合模型的協(xié)同過濾算法來解決用戶冷啟動問題是以系統(tǒng)中已有用戶的歷史數(shù)據(jù)為輸入，通過分析已有用戶的歷史數(shù)據(jù)輸出新用戶個性化的推薦內(nèi)容；第二，基于判斷聚合模型的協(xié)同過濾算法不僅可以得到集體對物品的偏好排序，而且可以得到集體對物品的評分，這些內(nèi)容可以為新用戶提供更為精確的個體決策依據(jù)。

［附注］本文受到西南大學(xué)人文社會科學(xué)重要研究項目（編號：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

［作者簡介］李莉（1980-），女，內(nèi)蒙古巴彥淖爾人，西南大學(xué)邏輯與智能研究中心2011級博士研究生；唐曉嘉（1954-），女，廣西全州人，西南大學(xué)邏輯與智能研究中心教授、博士生導(dǎo)師，主要從事現(xiàn)代邏輯與人工智能研究。

［中圖分類號］B81

［文獻(xiàn)標(biāo)志碼］A

［文章編號］1001－4799（2016）02－0040－05