基于社交關(guān)系拓?fù)浣Y(jié)構(gòu)的冷啟動(dòng)推薦方法

張亞楠, 曲明成 ,劉宇鵬

(1.哈爾濱理工大學(xué) 軟件學(xué)院,黑龍江 哈爾濱 150040；2.哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,黑龍江 哈爾濱 150001)

?

基于社交關(guān)系拓?fù)浣Y(jié)構(gòu)的冷啟動(dòng)推薦方法

張亞楠1, 曲明成2,劉宇鵬1

(1.哈爾濱理工大學(xué) 軟件學(xué)院,黑龍江 哈爾濱 150040；2.哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,黑龍江 哈爾濱 150001)

摘要:針對(duì)冷啟動(dòng)用戶僅有很少行為信息,很難為冷啟動(dòng)用戶給出推薦的問題,提出基于比較社交網(wǎng)絡(luò)中用戶間社交關(guān)系拓?fù)浣Y(jié)構(gòu)的冷啟動(dòng)推薦方法.社交網(wǎng)絡(luò)中包含多種可以反映用戶偏好的社交關(guān)系,然而現(xiàn)有基于社交網(wǎng)絡(luò)的冷啟動(dòng)推薦研究僅利用一種或者很少的社交關(guān)系,沒有充分利用社交網(wǎng)絡(luò)中的多種社交關(guān)系,很少考慮融合相異的社交關(guān)系,限制了在實(shí)際環(huán)境中對(duì)冷啟動(dòng)用戶的推薦效果.由于社交關(guān)系在社交網(wǎng)絡(luò)中的權(quán)重越大在推薦中的影響越大,為了給出準(zhǔn)確的冷啟動(dòng)推薦,提出基于社交關(guān)系拓?fù)涞南嗨朴脩舭l(fā)現(xiàn)方法(STSUM),基于最大熵原理融合社交網(wǎng)絡(luò)中多種相異的社交關(guān)系,基于圖形模式匹配為冷啟動(dòng)用戶發(fā)現(xiàn)相似用戶,給出推薦.在真實(shí)的網(wǎng)站中提取社交關(guān)系和用戶數(shù)據(jù),實(shí)驗(yàn)結(jié)果表明,STSUM可以有效地提高對(duì)冷啟動(dòng)用戶的推薦效果且需要較少的訓(xùn)練集．

關(guān)鍵詞：冷啟動(dòng)推薦；社交網(wǎng)絡(luò)；圖形模式匹配；最大熵

新用戶在登錄電子商務(wù)網(wǎng)站的初期,通常沒有或者僅有很少的購買、評(píng)價(jià)等行為信息,稱這類用戶為冷啟動(dòng)用戶.為冷啟動(dòng)用戶的推薦稱為冷啟動(dòng)推薦.由于冷啟動(dòng)推薦是針對(duì)歷史行為信息稀少的用戶的推薦,很難根據(jù)冷啟動(dòng)用戶的行為信息得到推薦的依據(jù).在社交網(wǎng)絡(luò)中,存在多種類型的社交關(guān)系,如興趣組、評(píng)論轉(zhuǎn)發(fā)關(guān)系、微博關(guān)注關(guān)系等,稱為用戶間多種邏輯的社交關(guān)系,這些社交關(guān)系從多個(gè)維度描述用戶的特征．

由于冷啟動(dòng)推薦的難點(diǎn)是冷啟動(dòng)用戶的歷史行為信息稀少,因此對(duì)冷啟動(dòng)推薦的研究一直圍繞著挖掘、擴(kuò)充冷啟動(dòng)用戶的信息以及為冷啟動(dòng)用戶發(fā)現(xiàn)相似用戶[1-6].國內(nèi)外學(xué)者對(duì)冷啟動(dòng)推薦的研究,主要包括基于協(xié)同過濾的推薦和基于用戶間信任關(guān)系的推薦．

1)基于協(xié)同過濾的推薦.基于協(xié)同過濾的推薦根據(jù)用戶之間的相似程度或者項(xiàng)目之間的相似程度給出推薦[7].基于協(xié)同過濾的推薦效果受用戶數(shù)據(jù)的稀疏程度影響.在描述用戶對(duì)項(xiàng)目評(píng)價(jià)的用戶項(xiàng)目矩陣中,絕大多數(shù)用戶僅有很少的數(shù)據(jù)或者沒有數(shù)據(jù),很難判斷哪些用戶相似.為解決用戶數(shù)據(jù)稀疏的問題,Jamali等[8]提出將原用戶項(xiàng)目矩陣分解為低秩矩陣,用低秩矩陣的乘積估計(jì)用戶項(xiàng)目矩陣中的未知值. Ma等[9]提出基于概率矩陣分解(probabilistic matrix factorization, PMF)的推薦,引入 (nonnegative matrix factorization,NMF)的預(yù)測值與真實(shí)評(píng)價(jià)值的誤差符合正態(tài)分布的限制條件,為冷啟動(dòng)用戶給出推薦.Wu等[10]提出在矩陣分解的過程中引入影響用戶喜好的特征向量可以提高推薦的準(zhǔn)確度.Koren[11]提出時(shí)間敏感的協(xié)同過濾推薦算法,在用戶、項(xiàng)目特征向量中引入時(shí)間特征,較好地解決用戶興趣漂移問題.Ren[12]提出平衡評(píng)分預(yù)測機(jī)制的協(xié)同過濾推薦方法,為個(gè)性化評(píng)分與全局評(píng)分的動(dòng)態(tài)權(quán)重調(diào)整提供了一種新思路.基于協(xié)同過濾的推薦可以避免由于不完全或不精確特征抽取而產(chǎn)生的不準(zhǔn)確推薦,并且可以給出較為新穎的推薦,但是推薦效果受用戶歷史行為信息數(shù)量的影響非常明顯．

2)基于信任的推薦.信任關(guān)系是一種穩(wěn)定的社交關(guān)系,由信任用戶給出的推薦更可靠.準(zhǔn)確地發(fā)現(xiàn)用戶間信任關(guān)系是基于信任推薦的關(guān)鍵.對(duì)信任關(guān)系的研究主要包括信任關(guān)系的傳遞策略[13-14]、驗(yàn)證信任網(wǎng)絡(luò)具有小世界特征[15],基于社交網(wǎng)絡(luò)的小世界特性和用戶間弱關(guān)系構(gòu)建信任網(wǎng)絡(luò)[16].如Liu等[17]提出傳播過程中擴(kuò)散的相對(duì)量與絕對(duì)量的權(quán)重博弈.Guha等[18]提出用戶間的信任關(guān)系可通過由用戶給出少量不信任或信任實(shí)例預(yù)測.印桂生等[19]提出將長尾分布與受限信任關(guān)系融合的推薦方法,為很少被關(guān)注的冷門商品給出一種推薦的途徑,以及基于受限信任關(guān)系和概率分解矩陣的推薦[20],孫光福等[21]提出基于時(shí)序行為的協(xié)同過濾推薦算法,將時(shí)序因素融入推薦中,較好的解決了推薦結(jié)果偏移的問題。然而基于信任的推薦對(duì)用戶歷史行為信息不敏感,并且信任關(guān)系僅僅是單一維度的社交關(guān)系,不能全面描述用戶的特征.本文研究如何基于社交網(wǎng)絡(luò)的拓?fù)?融合社交網(wǎng)絡(luò)中多種社交關(guān)系為冷啟動(dòng)用戶發(fā)現(xiàn)相似用戶,進(jìn)而根據(jù)相似用戶的行為記錄為冷啟動(dòng)用戶給出推薦．

1冷啟動(dòng)推薦問題的定義

隨著社交網(wǎng)絡(luò)的發(fā)展,越來越多的用戶加入到社交網(wǎng)絡(luò)中,社交網(wǎng)絡(luò)中豐富的用戶社交信息可以用來反映用戶在現(xiàn)實(shí)社會(huì)中的偏好,社交網(wǎng)絡(luò)中存在部分用戶有大量的購物記錄和評(píng)價(jià)信息,也存在相當(dāng)數(shù)量的冷啟動(dòng)用戶,由于社交網(wǎng)絡(luò)中用戶間的社交關(guān)系反映了用戶的行為及交友偏好,因此可以通過挖掘冷啟動(dòng)用戶的社交關(guān)系,進(jìn)而發(fā)現(xiàn)與其具有相似社交關(guān)系且歷史評(píng)價(jià)信息充足的用戶,根據(jù)這些用戶的偏好給冷啟動(dòng)用戶推薦.用戶商品矩陣描述用戶對(duì)商品的評(píng)價(jià)值.用戶商品矩陣是以用戶ID號(hào)為行,商品ID為列組成的二維矩陣.矩陣中的元素表示用戶對(duì)商品的評(píng)價(jià)值,評(píng)價(jià)值越高,表示用戶對(duì)商品越滿意,用戶選擇該商品的概率要高于評(píng)價(jià)值低的商品.推薦算法的實(shí)質(zhì)是預(yù)測用戶項(xiàng)目矩陣R=[ru,i]m×s中的未知元素,即用戶對(duì)未知商品的評(píng)價(jià)值,依據(jù)評(píng)價(jià)值的排序,將Top-N評(píng)價(jià)值對(duì)應(yīng)的商品推薦給用戶.在用戶項(xiàng)目矩陣中ru,i為用戶u對(duì)商品i的評(píng)價(jià)值,m為用戶個(gè)數(shù),s為商品個(gè)數(shù)．

本文提出的相似用戶發(fā)現(xiàn)方法( (socialtopologybasedsimilarusermatchingmethod,STSUM)方法可以分為2步,第1步發(fā)現(xiàn)與目標(biāo)用戶存在相似社交關(guān)系的用戶.第2步根據(jù)社交關(guān)系的相似程度預(yù)測用戶項(xiàng)目矩陣中的未知項(xiàng)．

2冷啟動(dòng)用戶的社交關(guān)系拓?fù)?/p>

社交關(guān)系拓?fù)涫巧缃痪W(wǎng)絡(luò)中用戶間社交關(guān)系的抽象.社交網(wǎng)絡(luò)是用戶在現(xiàn)實(shí)社會(huì)中交往關(guān)系在網(wǎng)絡(luò)中的真實(shí)映射,在社交網(wǎng)絡(luò)中用戶間的社交關(guān)系體現(xiàn)了用戶的偏好和特征.例如,用戶加入探險(xiǎn)俱樂部說明他很可能非常喜歡探險(xiǎn),加入車友會(huì)則預(yù)示他很喜歡駕車出游,因此通過用戶在社交網(wǎng)絡(luò)中的社交關(guān)系可以預(yù)測出用戶的偏好.雖然冷啟動(dòng)用戶的購買、評(píng)價(jià)等信息少,但是在社交網(wǎng)絡(luò)中的部分冷啟動(dòng)用戶具有多種類型的社交關(guān)系,可以通過社交關(guān)系推測冷啟動(dòng)用戶的偏好特征.冷啟動(dòng)用戶的社交關(guān)系種類越多,反映其偏好特征的信息越多,充分挖掘冷啟動(dòng)用戶的社交關(guān)系,并為其發(fā)現(xiàn)具有相似社交關(guān)系的用戶,根據(jù)與冷啟動(dòng)用戶相似用戶的評(píng)價(jià)或購買信息為冷啟動(dòng)用戶給出推薦．

為發(fā)現(xiàn)冷啟動(dòng)用戶的相似用戶,需要從社交網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)中尋找與冷啟動(dòng)用戶的社交關(guān)系的拓?fù)湎嗨频挠脩?社交網(wǎng)絡(luò)中用戶間的社交關(guān)系可以抽象為以用戶為節(jié)點(diǎn),用戶間的社交關(guān)系為有向邊的拓?fù)?社交網(wǎng)絡(luò)是由表示用戶的節(jié)點(diǎn)以及表示用戶間社交關(guān)系的邊組成的有向圖.其中邊的權(quán)重值可以表示社交關(guān)系的緊密程度,對(duì)邊標(biāo)記類型可以區(qū)分不同種類的社交關(guān)系.以代表冷啟動(dòng)用戶的節(jié)點(diǎn)和其連接的節(jié)點(diǎn)共同構(gòu)成冷啟動(dòng)用戶社交關(guān)系的拓?fù)洌?/p>

社交關(guān)系的拓?fù)洌毫顄表示冷啟動(dòng)用戶,u′表示與冷啟動(dòng)用戶存在某種社交關(guān)系的用戶,用戶u和u′之間邊的權(quán)重值(即社交關(guān)系緊密程度),用u和u′之間路徑長度fe(u, u′)表示,路徑長度越短則對(duì)應(yīng)的社交關(guān)系越緊密,路徑長度越長則對(duì)應(yīng)的社交關(guān)系越疏遠(yuǎn).fe(u, u′)=∞表示用戶u和u′之間不存在社交關(guān)系.在社交網(wǎng)絡(luò)中,對(duì)邊標(biāo)記類型可以區(qū)分不同種類的社交關(guān)系,任意用戶u和u′間的社交關(guān)系類型用fL(u, u′)表示,其中fL為社交關(guān)系類型的謂詞.通過社交關(guān)系類型和社交關(guān)系的路徑長度可以描述用戶在社交網(wǎng)絡(luò)中的社交關(guān)系拓?fù)?用戶u的社交關(guān)系拓?fù)渲邪ㄅcu直接存在社交關(guān)系的用戶u′,以及通過u′間接與u存在社交關(guān)系的用戶u”.令Topo(u)表示用戶u的拓?fù)?則Topo (u)=∑u′?ufe(u,u′)?fL(u,u′),其中u′為在社交網(wǎng)絡(luò)中與u存在直接或者間接社交關(guān)系的用戶．

3基于社交關(guān)系拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)冷啟動(dòng)用戶的相似用戶

基于社交網(wǎng)絡(luò)中用戶間的社交關(guān)系為冷啟動(dòng)用戶發(fā)現(xiàn)相似用戶,進(jìn)而根據(jù)相似用戶的購買或者評(píng)價(jià)等行為信息為冷啟動(dòng)用戶給出推薦.首先用戶間的社交關(guān)系表示為以用戶為節(jié)點(diǎn),和帶有權(quán)重的邊組成的拓?fù)?通過比較用戶社交關(guān)系的拓?fù)?為冷啟動(dòng)用戶發(fā)現(xiàn)相似用戶.相似的社交關(guān)系拓?fù)渲赣脩糸g的社交關(guān)系類型一致或者相似,并且用戶間該社交關(guān)系的緊密程度相似.其中,用戶間某種社交關(guān)系的緊密程度指在社交網(wǎng)絡(luò)中通過該社交關(guān)系連接的用戶節(jié)點(diǎn)間的距離.例如,社交網(wǎng)絡(luò)中的用戶a參加攝影團(tuán)隊(duì),且就職于醫(yī)療機(jī)構(gòu),與用戶a具有相似的社交關(guān)系的用戶,需要同時(shí)具備相似的社交關(guān)系類型以及相近的社交關(guān)系緊密程度.如果存在用戶b參加過攝影比賽,并且就職于醫(yī)院,則可得出用戶a與用戶b比較相似.如果存在用戶c參加過攝影比賽,并且就讀于醫(yī)科院校,則可得出用戶a與用戶c具有一定的相似性．

表示冷啟動(dòng)用戶的節(jié)點(diǎn)和與其連接的節(jié)點(diǎn)共同構(gòu)成冷啟動(dòng)用戶的社交關(guān)系拓?fù)?為冷啟動(dòng)用戶發(fā)現(xiàn)相似用戶的步驟可以分為：1)標(biāo)記出冷啟動(dòng)用戶的社交關(guān)系拓?fù)浣Y(jié)構(gòu),即找到與冷啟動(dòng)用戶存在某種社交關(guān)系的節(jié)點(diǎn),標(biāo)記節(jié)點(diǎn)間的社交關(guān)系類型fL和緊密程度fe.2)在社交網(wǎng)絡(luò)中發(fā)現(xiàn)與冷啟動(dòng)用戶拓?fù)浣Y(jié)構(gòu)相似的用戶.3)基于相似用戶的歷史購物記錄或評(píng)價(jià)記錄作為冷啟動(dòng)用戶的推薦依據(jù).將表示冷啟動(dòng)用戶社交關(guān)系的拓?fù)浣Y(jié)構(gòu)作為匹配模式.為冷啟動(dòng)用戶發(fā)現(xiàn)相似用戶的過程,可等價(jià)于在社交網(wǎng)絡(luò)中發(fā)現(xiàn)與匹配模式相匹配的拓?fù)涞倪^程.為冷啟動(dòng)用戶u發(fā)現(xiàn)相似用戶的示意圖如圖1所示,圖1中左側(cè)虛線內(nèi)為冷啟動(dòng)用戶的社交關(guān)系拓?fù)?中間虛線內(nèi)為整個(gè)社交網(wǎng)絡(luò)拓?fù)涞氖疽鈭D.實(shí)線和虛線分別表示2種不同類型的社交關(guān)系.在表示社交網(wǎng)絡(luò)的有向圖中比較社交關(guān)系的類型和社交關(guān)系的緊密程度,發(fā)現(xiàn)與冷啟動(dòng)用戶的社交關(guān)系相匹配的用戶為圖1中右側(cè)虛線中的d1和f2．

圖1　基于有界圖形模式匹配的相似用戶發(fā)現(xiàn)示意圖Fig.1　Schematic diagram of finding similar users for cold-start users by Bounded graphic pattern matching

用戶間社交關(guān)系的拓?fù)浣Y(jié)構(gòu)匹配可以借鑒圖形模式匹配的思想,現(xiàn)有的圖形模式匹配主要包括子圖同形和圖形模擬.子圖同形匹配條件是有向圖與匹配模式中的節(jié)點(diǎn)存在雙射關(guān)系,在社交網(wǎng)絡(luò)中雙射關(guān)系意味著用戶間的社交關(guān)系是完全對(duì)稱的,以微博關(guān)注關(guān)系為例,雙射關(guān)系要求2個(gè)用戶彼此關(guān)注,這種限制非常嚴(yán)格,在微博關(guān)注這種社交關(guān)系中更多的情況是眾多的用戶關(guān)注少數(shù)微博博主.圖形模擬是一種邊到邊映射,邊到邊的映射可以比較2條邊的類型、權(quán)重信息,可以在社交網(wǎng)絡(luò)中比較存在直接社交關(guān)系的用戶節(jié)點(diǎn),卻不能比較存在間接社交關(guān)系的用戶是否相似,因此不能為冷啟動(dòng)用戶匹配社交網(wǎng)絡(luò)中間接的社交關(guān)系,在社交網(wǎng)絡(luò)中,直接的社交關(guān)系數(shù)量有限,不能充分為冷啟動(dòng)用戶發(fā)現(xiàn)相似用戶,間接的社交關(guān)系中蘊(yùn)含著范圍更廣闊的潛在相似用戶.因此充分挖掘間接社交關(guān)系并比較用戶間的間接社交關(guān)系的相似程度,可以為冷啟動(dòng)用戶發(fā)現(xiàn)大量的相似用戶.本文提出一種在社交網(wǎng)絡(luò)中匹配間接社交關(guān)系的方法,為冷啟動(dòng)用戶發(fā)現(xiàn)相似用戶,進(jìn)而為冷啟動(dòng)用戶給出推薦．

3.1基于有界圖形模式匹配的相似用戶發(fā)現(xiàn)方法

冷啟動(dòng)用戶的社交關(guān)系拓?fù)渥鳛槠ヅ淠Ｊ?用有向圖表示整個(gè)社交網(wǎng)絡(luò)中用戶間的社交關(guān)系,在有向圖中發(fā)現(xiàn)所有與匹配模式相匹配的節(jié)點(diǎn)集合,即與冷啟動(dòng)用戶具有相似社交關(guān)系的用戶.令u表示冷啟動(dòng)用戶,u′表示與冷啟動(dòng)用戶存在社交關(guān)系的用戶,fe(u,u′)表示u和u′之間的路徑長度,fL(u,u′)表示u和u′間的社交關(guān)系類型,v和v′表示社交網(wǎng)絡(luò)中任意用戶,fC(v,v′)表示社交網(wǎng)絡(luò)中(v,v′)的社交關(guān)系類型,VQ表示匹配模式中的節(jié)點(diǎn)集合,V表示有向圖中所有節(jié)點(diǎn)集合,令S?VQ×V,基于有界圖形模式匹配的相似用戶條件：a)用戶v的屬性與用戶u的屬性相似.b)對(duì)于(u,u′),有向圖中存在一個(gè)非空且長度不超過fe(u,u′)的路徑v/…/v′,且存在(u,v)∈S.c)對(duì)于(u,u′),G中存在路徑v/…/v′,使fC(v,v1)…fC(vn,v′)滿足(u,u′) 上的關(guān)系fL(u,u′),其中路徑v/…/v′中節(jié)點(diǎn)的順序?yàn)?v,v1,…,vn,v′). 設(shè)匹配模式P= (VQ,EQ,fc,fe),用戶數(shù)據(jù)圖G=(V,E,fA).基于有界圖形模式匹配的相似用戶發(fā)現(xiàn)算法如算法1所示.在模式P和用戶數(shù)據(jù)圖G的匹配過程中,將匹配結(jié)果按照匹配程度的降序排列．

算法1基于有界圖形模式匹配的相似用戶發(fā)現(xiàn)

輸入:模式P= (Vp,Ep,fc,fe),用戶數(shù)據(jù)圖G= (V,E,fA)．

輸出: 當(dāng)P

1. 計(jì)算G的距離矩陣M;

2. for each (u′,u) ∈Ep,x∈Vdo

3. 計(jì)算anc(fe(u′,u),fv(u′),x), desc (fe(u′,u),fv(u′),x);

4. for eachu∈Vpdo

5. mat (u) := {x|x∈V,fA(x)符合fv(u),且out-degree(a)≠0,out-degree (x) ≠ 0 };

6. premv (u) := {x|x∈V, out-degree (x) if out-degree (a)≠0, 并且?(u′,u) ∈Ep(x′ ∈mat (u),fA(x)滿足fv(u′),并且len (x/.../x′) ≤fe(u′,u))};

7. while (u∈Vpwith premv (u) ≠ ?) do

8. for (each (u′,u) ∈Ep,z∈premv (u) ∩ mat (u′)) do

9. mat (u′) := mat (u′) {z};

10. if (mat (u′) = ?) then return ?;

11. for eachu″ with (u″,u′) ∈Epdo

12. for (z′ ∈anc(fe(u″,u′),fv(u″),z) ∧z′ ∈premv(u′)) do

13. if (desc (fe(u″,u′),fv(u′),z′) ∩ mat (u′) = ?)

14. then premv (u′) := premv (u′) ∪ {z′};

15. premv (u) := ?;

16.S:= ?;

17. for (u∈Vpandx∈mat (u)) doS:=S∪ {(u,x)};

18. returnS

對(duì)任意模式P= (Vp,Ep,fc,fe),待匹配用戶數(shù)據(jù)圖G= (V,E,fA), 基于有界圖形模式匹配的相似用戶發(fā)現(xiàn)算法的時(shí)間復(fù)雜度與模式P和用戶數(shù)據(jù)圖G中的節(jié)點(diǎn)個(gè)數(shù)以及邊的個(gè)數(shù)的乘積正相關(guān),基于有界圖形模式匹配的相似用戶發(fā)現(xiàn)的時(shí)間復(fù)雜度O((|V| + |Vp|)(|E| + |Ep|)),將(|V| + |Vp|)(|E| + |Ep|))展開得(|V||E| +|V||Ep|+|E||Vp|+ |Vp||Ep|),通常模式P的節(jié)點(diǎn)和有向邊規(guī)模要遠(yuǎn)小于用戶數(shù)據(jù)圖G,且在用戶數(shù)據(jù)圖中|E|與|V|2是近似相等的,因此可化簡為O(|V||E|+|Ep||V|+|Vp||V|2)．

3.2相異邏輯的社交關(guān)系賦權(quán)重值

在社交網(wǎng)絡(luò)中,用戶間具有多種邏輯的社交關(guān)系,如興趣組、評(píng)論轉(zhuǎn)發(fā)關(guān)系、微博關(guān)注關(guān)系等,這些社交關(guān)系從多個(gè)維度描述用戶的特征,相似的特征映射著用戶間的購買或評(píng)價(jià)行為也相似.利用多種邏輯的社交關(guān)系發(fā)現(xiàn)相似用戶,需要為社交網(wǎng)絡(luò)中相異邏輯的社交關(guān)系給出合理的權(quán)重值,即融合多種相異邏輯的社交關(guān)系,以得到最準(zhǔn)確的推薦.社交網(wǎng)絡(luò)中不同社交關(guān)系的權(quán)重是很難直接設(shè)定的,對(duì)某種社交關(guān)系給予不同的權(quán)重值,得到的冷啟動(dòng)用戶的相似用戶也不相同.各種社交關(guān)系的權(quán)重分配可以有多種組合分布,其中有一種社交關(guān)系權(quán)重的分布可以得到最大的熵.選用這種具有最大熵的分布作為社交關(guān)系組合的權(quán)重分布,是在未完整掌握社交關(guān)系權(quán)重分布時(shí),選取符合已知條件且熵值最大的概率分布策略.這種推斷就是符合已知條件最不確定或最隨機(jī)的推斷,任何其他的社交關(guān)系權(quán)重都意味著增加了有偏向性且多余的約束.基于最大熵準(zhǔn)則為相異邏輯的社交關(guān)系賦權(quán)值,使得社交關(guān)系的權(quán)重值的熵最大,并且使相似用戶預(yù)測的評(píng)價(jià)值與真實(shí)評(píng)價(jià)值的差值與社交關(guān)系權(quán)重的乘積之和最小,其數(shù)學(xué)模型如下：

(1)

3.3基于相似用戶的冷啟動(dòng)推薦

STSUM方法基于有界圖形模式匹配和相異邏輯的社交關(guān)系賦權(quán)重值可以為冷啟動(dòng)用戶發(fā)現(xiàn)相似用戶,基于這些相似用戶的已有評(píng)價(jià)或者購買記錄為冷啟動(dòng)用戶給出推薦.在基于有界圖形模式匹配的過程中,將模式P和用戶數(shù)據(jù)圖G匹配,將匹配結(jié)果按照匹配程度的降序排列,根據(jù)社交關(guān)系的相似程度預(yù)測用戶項(xiàng)目矩陣中的未知項(xiàng),其中未知項(xiàng)的值可由式(2)求得,為冷啟動(dòng)用戶a給出推薦的形式化描述如式(3)所示:

(2)

(3)

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

4.1實(shí)驗(yàn)數(shù)據(jù)及測評(píng)方法

實(shí)驗(yàn)數(shù)據(jù)集來自Epinions網(wǎng)站，實(shí)驗(yàn)數(shù)據(jù)集包括trust和rating表，trust表記錄每個(gè)用戶信任的用戶ID， rating表記錄用戶對(duì)商品的評(píng)價(jià)值,其中1表示不推薦,5表示非常推薦.有49 289個(gè)用戶對(duì)139 544個(gè)不同商品的評(píng)價(jià),評(píng)價(jià)總數(shù)達(dá)到586 361條. 在Epinions網(wǎng)站中的社區(qū)功能中提取用戶的社交關(guān)系,將用戶社交關(guān)系按照社交關(guān)系類型和緊密程度標(biāo)注為社交關(guān)系拓?fù)浣Y(jié)構(gòu)圖.為了驗(yàn)證STSUM方法的效果,選取具有冷啟動(dòng)用戶特征的數(shù)據(jù).數(shù)據(jù)集中有73.8%的用戶至多評(píng)價(jià)過3個(gè)商品,17.93%的用戶至多評(píng)價(jià)過1個(gè)商品.測試集中的大多數(shù)用戶的評(píng)價(jià)個(gè)數(shù)在3以下,冷啟動(dòng)用戶數(shù)量占91.73%．

驗(yàn)證實(shí)驗(yàn)結(jié)果的方法：均方根誤差 (root mean square error, RMSE)是評(píng)估算法計(jì)算的預(yù)測值與真實(shí)值之間差距的指標(biāo),可用于衡量推薦效果[17],RMSE的定義如式(4)所示,用戶均方根誤差 (user root mean square error, URMSE)的定義如式(5)所示：

(4)

(5)

分別采用RMSE和URMSE評(píng)價(jià)STSUM的推薦效果.RMSE和URMSE值越小,則算法的推薦效果越好.選擇近期在冷啟動(dòng)推薦取得較好效果的方法做對(duì)比實(shí)驗(yàn),Bobadilla等[1]基于神經(jīng)學(xué)習(xí)提出一種優(yōu)化的相似度量方法,進(jìn)而為冷啟動(dòng)用戶給出推薦.Lika等[2]提出基于分類算法的協(xié)同過濾方法發(fā)現(xiàn)相似用戶,進(jìn)而為冷啟動(dòng)用戶給出推薦.Ling等[4]提出通過矢量余弦法獲取用戶相似矩陣,并將用戶分組,使用top-N方法為各組推薦.冷啟動(dòng)推薦的初始參數(shù)需要一定量的數(shù)據(jù)訓(xùn)練,將整個(gè)數(shù)據(jù)集分成訓(xùn)練集和測試集,取訓(xùn)練集依次占整個(gè)數(shù)據(jù)集的5%、10%、20%、50%,80%．

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

4.2.1STSUM參數(shù)選擇在確定STSUM中的社交關(guān)系的個(gè)數(shù)k時(shí),首先,將不同類型的社交關(guān)系按照其所覆蓋的用戶數(shù)量降序排列,覆蓋用戶數(shù)量多的社交關(guān)系排在前列.其次確定STSUM中社交關(guān)系的最優(yōu)個(gè)數(shù)k.由于不同個(gè)數(shù)的社交關(guān)系所包含的用戶信息數(shù)量不同,通常包含的社交關(guān)系個(gè)數(shù)越多,能夠表征的用戶信息越多.通過實(shí)驗(yàn)給出推薦效果和社交關(guān)系個(gè)數(shù)k的對(duì)應(yīng)關(guān)系.實(shí)驗(yàn)中,分別取不同個(gè)數(shù)的社交關(guān)系,通過基于最大熵原理的數(shù)學(xué)模型給出每個(gè)社交關(guān)系的權(quán)重,然后得到社交關(guān)系k的個(gè)數(shù)對(duì)STSUM推薦效果的影響．

不同k取值對(duì)STSUM推薦效果如圖2所示.其中RMSE值越小表明預(yù)測值與真實(shí)值的差距越小,說明算法的推薦結(jié)果越準(zhǔn)確.實(shí)驗(yàn)中當(dāng)社交關(guān)系個(gè)數(shù)k取1時(shí),STSUM的RMSE值最大,表明此時(shí)給出的推薦結(jié)果與真實(shí)情況偏離最大,這是因?yàn)檫^少的社交關(guān)系不能完整地描述用戶特征.逐漸增加k值,RMSE值降低,當(dāng)k值取3時(shí),STSUM的RMSE值最小,繼續(xù)增加k值,STSUM的RMSE值不斷緩慢增加,沒有下降的趨勢(shì),說明繼續(xù)增加社交關(guān)系的個(gè)數(shù)不能提高推薦的準(zhǔn)確度.由于RMSE是對(duì)整個(gè)測試集中用戶的推薦誤差求平方加和,可以衡量測試集中用戶整體的推薦效果.為了能夠有效地反映k值對(duì)每個(gè)用戶的推薦效果的影響,通過URMSE比較不同k值下對(duì)用戶的推薦效果,實(shí)驗(yàn)結(jié)果如圖3所示.其中URMSE值越小表明預(yù)測值與真實(shí)值的差距越小.當(dāng)k取1時(shí),STSUM的URMSE值最大,表明此時(shí)給出的推薦結(jié)果與真實(shí)情況偏離最大,URMSE實(shí)驗(yàn)結(jié)果與RMSE實(shí)驗(yàn)結(jié)果一致.逐漸增加k,其URMSE值降低,當(dāng)k取3時(shí),STSUM的URMSE值最小,繼續(xù)增加k值,其URMSE值不斷增加,說明繼續(xù)增加社交關(guān)系的個(gè)數(shù)不能提高推薦的準(zhǔn)確度.當(dāng)k取3時(shí),STSUM的RMSE和URMSE都取得最小,并且當(dāng)k取值繼續(xù)增大的情況下,RMSE和URMSE的值都緩慢上升,可知最優(yōu)社交關(guān)系數(shù)量為3．

圖2　STSUM的參數(shù)k與RMSE值關(guān)系Fig.2　Experimental results for different k of STSUM against RMSE

圖3　STSUM的參數(shù)k與URMSE值關(guān)系Fig.3　Experimental results for different k of STSUM against URMSE

4.2.2對(duì)比試驗(yàn)結(jié)果為了驗(yàn)證基于最大熵原理給出的相異邏輯的社交關(guān)系權(quán)重值是合理的,采用對(duì)比實(shí)驗(yàn)驗(yàn)證效果.在k取3的情況下,分別由式(1)～(3)計(jì)算社交關(guān)系權(quán)重,與各種社交關(guān)系賦予相同權(quán)重的情況做對(duì)比.實(shí)驗(yàn)結(jié)果如圖4所示,其中t為訓(xùn)練集占的百分比,采用STSUM得出的推薦結(jié)果在不同測試集的情況下都優(yōu)于采用相同權(quán)重社交關(guān)系的推薦,為了能夠有效地比較對(duì)每個(gè)用戶STSUM和采用相同權(quán)重社交關(guān)系推薦的效果,通過URMSE比較推薦效果,實(shí)驗(yàn)結(jié)果如圖5所示,比較圖4與圖5所示的結(jié)果得出STSUM的推薦結(jié)果在不同測試集的情況下都優(yōu)于采用相同權(quán)重社交關(guān)系的推薦．

圖4　相同權(quán)重與最大熵社交關(guān)系STSUM的RMSE值比較Fig.4　Comparison of different social relationship weight assignment against RMSE

圖5　相同權(quán)重與最大熵社交關(guān)系STSUM的URMSE值比較Fig.5　Comparison of different social relationship weight assignment against URMSE

為了驗(yàn)證STSUM對(duì)冷啟動(dòng)用戶的推薦效果,通過和Bobadilla,Lika,Ling的方法比較,以RMSE衡量推薦的效果,對(duì)比試驗(yàn)的結(jié)果如圖6所示,按照RMSE值從大到小的排列上述算法,依次為Bobadilla,Lika,Ling,STSUM.當(dāng)訓(xùn)練集少于20%時(shí),STSUM的RMSE值遠(yuǎn)小于其他方法,當(dāng)訓(xùn)練集超過20%時(shí),繼續(xù)增加訓(xùn)練集百分比,STSUM的RMSE值變化很小,說明STSUM在訓(xùn)練集占20%時(shí)就可以得到很好的推薦效果.如圖7所示,將上述算法按照URMSE值從大到小排列,依次為Bobadilla,Lika,Ling,STSUM,與圖6的結(jié)果一致.當(dāng)訓(xùn)練集小于20%時(shí),STSUM的URMSE值小于其他算法,當(dāng)訓(xùn)練集超過20%時(shí),繼續(xù)增加訓(xùn)練集的百分比,STSUM的URMSE值變化很小,說明STSUM在訓(xùn)練集占20%時(shí)就可以得到很好的推薦效果.在包含大量冷門商品的數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明STSUM的推薦效果優(yōu)于Bobadilla,Lika,Ling的方法,并且需要較少的訓(xùn)練集．

圖6　STSUM算法與其他推薦算法的RMSE值比較Fig.6　Comparison with state-of-art methods against RMSE

圖7　STSUM算法與其他推薦算法的URMSE值比較Fig.7　Comparison with state-of -art methods against URMSE

5結(jié)語

在世界上電子商務(wù)系統(tǒng)中,存在部分僅有很少購買、評(píng)價(jià)等行為信息的冷啟動(dòng)用戶.由于缺乏冷啟動(dòng)用戶購買、評(píng)價(jià)等信息,為冷啟動(dòng)用戶推薦一直是推薦領(lǐng)域的難點(diǎn)之一.為冷啟動(dòng)用戶推薦喜歡的商品,則可以吸引更多的用戶,提高用戶對(duì)系統(tǒng)的黏滯度,因此冷啟動(dòng)推薦是眾多網(wǎng)絡(luò)應(yīng)用的核心支撐技術(shù)之一.社交網(wǎng)絡(luò)是用戶現(xiàn)實(shí)社交關(guān)系的映射,充分利用社交網(wǎng)絡(luò)中多種邏輯的社交關(guān)系,融合相異邏輯的社交關(guān)系,可以在更廣闊的范圍內(nèi)為冷啟動(dòng)用戶發(fā)現(xiàn)相似用戶,進(jìn)而為冷啟動(dòng)用戶給出推薦.本文基于圖形模式匹配、最大熵準(zhǔn)則,充分利用用戶間多種邏輯的社交關(guān)系,提出基于最大熵原理融合社交網(wǎng)絡(luò)中多種相異邏輯的社交關(guān)系,最大限度的為冷啟動(dòng)用戶發(fā)現(xiàn)相似用戶,進(jìn)而為冷啟動(dòng)用戶給出合理的推薦結(jié)果.在包含大量冷啟動(dòng)用戶的實(shí)驗(yàn)結(jié)果表明,STSUM在訓(xùn)練集較小的情況下,有效地提高了對(duì)冷啟動(dòng)用戶的推薦效果．

參考文獻(xiàn)(Reference):

[1] BOBADILLA J S, ORTEGA F, HERNANDO A, et al. A collaborative filtering approach to mitigate the new user cold start problem [J]. Knowledge-Based Systems, 2012, 26(1): 225-238．

[2] LIKA B, KOLOMVATSOS K, HADJIEFTHYMIADES S. Facing the cold start problem in recommender systems [J]. Expert Systems with Applications, 2014, 41(4): 2065-2073．

[3] REN Y L, LI G, ZHOU W L. PRICAI 2012: Trends in Artificial Intelligence[M]. Berlin Heidelberg: Springer, 2012: 887-890．

[4] LING Y X, GUO D K, CAI F, et al. User-based Clustering with Top-N Recommendation on Cold-Start Problem[C]∥Proceedings of the 2013 3rd international conference on intelligent system design and engineering applications. Hong Kong:IEEE Computer Society, 2013: 1585-1589．

[5] LOPS P, DE GEMMIS M, SEMERARO G. Recommender systems handbook [M]. Berlin Heidelberg: Springer, 2011: 73-105．

[6] YIN H, CUI B, CHEN L, et al. A temporal context-aware model for user behavior modeling in social media systems[C]∥Proceedings of the 2014 ACM SIGMOD international conference on Management of data. Snowbird, USA: ACM, 2014: 1543-1554．

[7] WANG J, DE VRIES A P, REINDERS M J T. Unifying user-based and item-based collaborative filtering approaches by similarity fusion[C]∥Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval. Washington, USA: ACM, 2006: 501-508．

[8] JAMALI M, ESTER M. A matrix factorization technique with trust propagation for recommendation in social networks[C]∥Proceedings of the 4th ACM conference on Recommender systems. Barcelona, Spain: ACM, 2010: 135-142．

[9] MA H, YANG H, LYU M R, et al. Sorec: social recommendation using probabilistic matrix factorization[C]∥Proceedings of the 17th ACM conference on Information and knowledge management. Napa Valley, USA: ACM, 2008: 931-940．

[10] WU L, CHEN E H, LIU Q, et al. Leveraging tagging for neighborhood-aware probabilistic matrix factorization[C]∥Proceedings of the 21st ACM international conference on Information and knowledge management. Maui Hawaii, USA: ACM, 2012: 1854-1858．

[11] KOREN Y. Collaborative filtering with temporal dynamics[J]. Communications of the ACM, 2010, 53(4): 89-97．

[12] REN L, GU J Z, XIA W W. An item-based collaborative filtering approach based on balanced rating prediction[C]∥Proceedings of 2011 International Conference on Multimedia Technology. Hangzhou, China: IEEE, 2011: 3405-3408．

[13] MA H, KING I, LYU M R. Learning to recommend with social trust ensemble[C]∥Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval. Gold Coast, Australia: ACM, 2009: 203-210．

[14] KIM Y A, SONG H S. Strategies for predicting local trust based on trust propagation in social networks[J]. Knowledge-Based Systems, 2011, 24(8): 1360-1371．

[15] YUAN W W, GUAN D H, LEE Y K, et al. Improved trust-aware recommender system using small-worldness of trust networks[J]. Knowledge-Based Systems, 2010, 23(3): 232-238．

[16] JIANG W J, WANG G J, WU J. Generating trusted graphs for trust evaluation in online social networks[J]. Future Generation Computer Systems, 2014, 31(1): 48-58．

[17] LIU R R, LIU J G, JIA C X, et al. Personal recommendation via unequal resource allocation on bipartite networks[J]. Physica A: Statistical Mechanics and its Applications, 2010, 389(16): 3282-3289．

[18] GUHA R, KUMAR R, RAGHAVAN P, et al. Propagation of trust and distrust[C]∥Proceedings Of The 13th International Conference On World Wide Web. New York, USA: ACM, 2004: 403-412．

[19] 印桂生, 張亞楠, 董紅斌, 等.一種由長尾分布約束的推薦方法[J]. 計(jì)算機(jī)研究與發(fā)展,2013,50(9):1814-1824．

YIN Gui-sheng, ZHANG Ya-nan, DONG Hong-bin,et al. A long tail distribution constrained recommendation method [J].Journal of computer research and development， 2013,50(9):1814-1824．

[20] 印桂生, 張亞楠, 董宇欣, 等.基于受限信任關(guān)系和概率分解矩陣的推薦[J]. 電子學(xué)報(bào), 2013, 42(5): 904-911．

YIN Gui-sheng, ZHANG Ya-nan, DONG Yu-xin, et al. A Constrained trust recommendation using probabilistic matrix factorization [J]. Acta Electronica Sinica, 2013, 42(5): 904-911．

[21] 孫光福, 吳樂, 劉淇, 等. 基于時(shí)序行為的協(xié)同過濾推薦算法[J].軟件學(xué)報(bào), 2013, 24(11):2721-2733．

SUN Guang-fu, WU Le, LIU Qi, et al. Recommendations based on collaborative filtering by exploiting sequential behaviors [J]. Journal Of Software, 2013, 24(11):2721-2733．

Recommendation method based on social topology for cold-start users

ZHANG Ya-nan1,QU Ming-cheng2,LIU Yu-peng1

(1.Softwareschool,HarbinUniversityofScienceandTechnology,Harbin150040,China；2.SchoolofcomputerscienceandTechnology,HarbinInstituteofTechnology,Harbin150001,China)

Abstract:It is very difficult to give recommendations for cold-start user who usually has very sparse historical behavior records. A cold-start recommendation method was proposed based on comparison of topology of social relationships in social networks to improve recommendation effectiveness for cold-start user. Social network contains many social relationships which could reflect user’s preference. However, most of existing social network based recommendation methods use only one or a few social relationships of social network, which do not make full use of multiple social relationships; rarely consider how to merge dissimilar social relationships, and could not give satisfactory recommendation in actual environment. In social network the higher weight a kind of social relationship takes, the greater right of recommendations it will have. In order to give accurate recommendations for cold-start user, a social topology based similar user matching method (STSUM) was proposed, Maximum entropy principle was introduced to merge multiple social relationships, and graph pattern matching was used to find similar users for cold-start user. Then recommendations were given according to similar users’ records. Social relationship and user data from a real website to show the recommendation effectiveness of STSUM. The experimental results show that STSUM con give accurate recommendations for cold-start user and needs a few training set．

Key words:cold-start recommendation; social network; graph pattern matching; maximum entropy

收稿日期：2015-12-04.浙江大學(xué)學(xué)報(bào)(工學(xué)版)網(wǎng)址： www.journals.zju.edu.cn/eng

基金項(xiàng)目：國家自然科學(xué)基金青年基金資助項(xiàng)目(61300115).

作者簡介：張亞楠(1981-), 男, 講師,從事社交網(wǎng)絡(luò)推薦等研究.ORCID: 0000-0002-0633-826X E-mail: ynzhang_1981@163.com

DOI:10.3785/j.issn.1008-973X.2016.05.026

中圖分類號(hào)：TP 391

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

文章編號(hào)：1008-973X(2016)05-01001-08