基于社交關系拓撲結構的冷啟動推薦方法

張亞楠, 曲明成 ,劉宇鵬

(1.哈爾濱理工大學 軟件學院,黑龍江 哈爾濱 150040；2.哈爾濱工業大學 計算機科學與技術學院,黑龍江 哈爾濱 150001)

?

基于社交關系拓撲結構的冷啟動推薦方法

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

(1.哈爾濱理工大學 軟件學院,黑龍江 哈爾濱 150040；2.哈爾濱工業大學 計算機科學與技術學院,黑龍江 哈爾濱 150001)

摘要:針對冷啟動用戶僅有很少行為信息,很難為冷啟動用戶給出推薦的問題,提出基于比較社交網絡中用戶間社交關系拓撲結構的冷啟動推薦方法.社交網絡中包含多種可以反映用戶偏好的社交關系,然而現有基于社交網絡的冷啟動推薦研究僅利用一種或者很少的社交關系,沒有充分利用社交網絡中的多種社交關系,很少考慮融合相異的社交關系,限制了在實際環境中對冷啟動用戶的推薦效果.由于社交關系在社交網絡中的權重越大在推薦中的影響越大,為了給出準確的冷啟動推薦,提出基于社交關系拓撲的相似用戶發現方法(STSUM),基于最大熵原理融合社交網絡中多種相異的社交關系,基于圖形模式匹配為冷啟動用戶發現相似用戶,給出推薦.在真實的網站中提取社交關系和用戶數據,實驗結果表明,STSUM可以有效地提高對冷啟動用戶的推薦效果且需要較少的訓練集．

關鍵詞：冷啟動推薦；社交網絡；圖形模式匹配；最大熵

新用戶在登錄電子商務網站的初期,通常沒有或者僅有很少的購買、評價等行為信息,稱這類用戶為冷啟動用戶.為冷啟動用戶的推薦稱為冷啟動推薦.由于冷啟動推薦是針對歷史行為信息稀少的用戶的推薦,很難根據冷啟動用戶的行為信息得到推薦的依據.在社交網絡中,存在多種類型的社交關系,如興趣組、評論轉發關系、微博關注關系等,稱為用戶間多種邏輯的社交關系,這些社交關系從多個維度描述用戶的特征．

由于冷啟動推薦的難點是冷啟動用戶的歷史行為信息稀少,因此對冷啟動推薦的研究一直圍繞著挖掘、擴充冷啟動用戶的信息以及為冷啟動用戶發現相似用戶[1-6].國內外學者對冷啟動推薦的研究,主要包括基于協同過濾的推薦和基于用戶間信任關系的推薦．

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

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

1冷啟動推薦問題的定義

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

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

2冷啟動用戶的社交關系拓撲

社交關系拓撲是社交網絡中用戶間社交關系的抽象.社交網絡是用戶在現實社會中交往關系在網絡中的真實映射,在社交網絡中用戶間的社交關系體現了用戶的偏好和特征.例如,用戶加入探險俱樂部說明他很可能非常喜歡探險,加入車友會則預示他很喜歡駕車出游,因此通過用戶在社交網絡中的社交關系可以預測出用戶的偏好.雖然冷啟動用戶的購買、評價等信息少,但是在社交網絡中的部分冷啟動用戶具有多種類型的社交關系,可以通過社交關系推測冷啟動用戶的偏好特征.冷啟動用戶的社交關系種類越多,反映其偏好特征的信息越多,充分挖掘冷啟動用戶的社交關系,并為其發現具有相似社交關系的用戶,根據與冷啟動用戶相似用戶的評價或購買信息為冷啟動用戶給出推薦．

為發現冷啟動用戶的相似用戶,需要從社交網絡的拓撲結構中尋找與冷啟動用戶的社交關系的拓撲相似的用戶.社交網絡中用戶間的社交關系可以抽象為以用戶為節點,用戶間的社交關系為有向邊的拓撲.社交網絡是由表示用戶的節點以及表示用戶間社交關系的邊組成的有向圖.其中邊的權重值可以表示社交關系的緊密程度,對邊標記類型可以區分不同種類的社交關系.以代表冷啟動用戶的節點和其連接的節點共同構成冷啟動用戶社交關系的拓撲．

社交關系的拓撲：令u表示冷啟動用戶,u′表示與冷啟動用戶存在某種社交關系的用戶,用戶u和u′之間邊的權重值(即社交關系緊密程度),用u和u′之間路徑長度fe(u, u′)表示,路徑長度越短則對應的社交關系越緊密,路徑長度越長則對應的社交關系越疏遠.fe(u, u′)=∞表示用戶u和u′之間不存在社交關系.在社交網絡中,對邊標記類型可以區分不同種類的社交關系,任意用戶u和u′間的社交關系類型用fL(u, u′)表示,其中fL為社交關系類型的謂詞.通過社交關系類型和社交關系的路徑長度可以描述用戶在社交網絡中的社交關系拓撲.用戶u的社交關系拓撲中包括與u直接存在社交關系的用戶u′,以及通過u′間接與u存在社交關系的用戶u”.令Topo(u)表示用戶u的拓撲,則Topo (u)=∑u′?ufe(u,u′)?fL(u,u′),其中u′為在社交網絡中與u存在直接或者間接社交關系的用戶．

3基于社交關系拓撲結構發現冷啟動用戶的相似用戶

基于社交網絡中用戶間的社交關系為冷啟動用戶發現相似用戶,進而根據相似用戶的購買或者評價等行為信息為冷啟動用戶給出推薦.首先用戶間的社交關系表示為以用戶為節點,和帶有權重的邊組成的拓撲.通過比較用戶社交關系的拓撲,為冷啟動用戶發現相似用戶.相似的社交關系拓撲指用戶間的社交關系類型一致或者相似,并且用戶間該社交關系的緊密程度相似.其中,用戶間某種社交關系的緊密程度指在社交網絡中通過該社交關系連接的用戶節點間的距離.例如,社交網絡中的用戶a參加攝影團隊,且就職于醫療機構,與用戶a具有相似的社交關系的用戶,需要同時具備相似的社交關系類型以及相近的社交關系緊密程度.如果存在用戶b參加過攝影比賽,并且就職于醫院,則可得出用戶a與用戶b比較相似.如果存在用戶c參加過攝影比賽,并且就讀于醫科院校,則可得出用戶a與用戶c具有一定的相似性．

表示冷啟動用戶的節點和與其連接的節點共同構成冷啟動用戶的社交關系拓撲.為冷啟動用戶發現相似用戶的步驟可以分為：1)標記出冷啟動用戶的社交關系拓撲結構,即找到與冷啟動用戶存在某種社交關系的節點,標記節點間的社交關系類型fL和緊密程度fe.2)在社交網絡中發現與冷啟動用戶拓撲結構相似的用戶.3)基于相似用戶的歷史購物記錄或評價記錄作為冷啟動用戶的推薦依據.將表示冷啟動用戶社交關系的拓撲結構作為匹配模式.為冷啟動用戶發現相似用戶的過程,可等價于在社交網絡中發現與匹配模式相匹配的拓撲的過程.為冷啟動用戶u發現相似用戶的示意圖如圖1所示,圖1中左側虛線內為冷啟動用戶的社交關系拓撲,中間虛線內為整個社交網絡拓撲的示意圖.實線和虛線分別表示2種不同類型的社交關系.在表示社交網絡的有向圖中比較社交關系的類型和社交關系的緊密程度,發現與冷啟動用戶的社交關系相匹配的用戶為圖1中右側虛線中的d1和f2．

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

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

3.1基于有界圖形模式匹配的相似用戶發現方法

冷啟動用戶的社交關系拓撲作為匹配模式,用有向圖表示整個社交網絡中用戶間的社交關系,在有向圖中發現所有與匹配模式相匹配的節點集合,即與冷啟動用戶具有相似社交關系的用戶.令u表示冷啟動用戶,u′表示與冷啟動用戶存在社交關系的用戶,fe(u,u′)表示u和u′之間的路徑長度,fL(u,u′)表示u和u′間的社交關系類型,v和v′表示社交網絡中任意用戶,fC(v,v′)表示社交網絡中(v,v′)的社交關系類型,VQ表示匹配模式中的節點集合,V表示有向圖中所有節點集合,令S?VQ×V,基于有界圖形模式匹配的相似用戶條件：a)用戶v的屬性與用戶u的屬性相似.b)對于(u,u′),有向圖中存在一個非空且長度不超過fe(u,u′)的路徑v/…/v′,且存在(u,v)∈S.c)對于(u,u′),G中存在路徑v/…/v′,使fC(v,v1)…fC(vn,v′)滿足(u,u′) 上的關系fL(u,u′),其中路徑v/…/v′中節點的順序為(v,v1,…,vn,v′). 設匹配模式P= (VQ,EQ,fc,fe),用戶數據圖G=(V,E,fA).基于有界圖形模式匹配的相似用戶發現算法如算法1所示.在模式P和用戶數據圖G的匹配過程中,將匹配結果按照匹配程度的降序排列．

算法1基于有界圖形模式匹配的相似用戶發現

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

輸出: 當P

1. 計算G的距離矩陣M;

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

3. 計算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

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

3.2相異邏輯的社交關系賦權重值

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

(1)

3.3基于相似用戶的冷啟動推薦

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

(2)

(3)

4實驗結果與分析

4.1實驗數據及測評方法

實驗數據集來自Epinions網站，實驗數據集包括trust和rating表，trust表記錄每個用戶信任的用戶ID， rating表記錄用戶對商品的評價值,其中1表示不推薦,5表示非常推薦.有49 289個用戶對139 544個不同商品的評價,評價總數達到586 361條. 在Epinions網站中的社區功能中提取用戶的社交關系,將用戶社交關系按照社交關系類型和緊密程度標注為社交關系拓撲結構圖.為了驗證STSUM方法的效果,選取具有冷啟動用戶特征的數據.數據集中有73.8%的用戶至多評價過3個商品,17.93%的用戶至多評價過1個商品.測試集中的大多數用戶的評價個數在3以下,冷啟動用戶數量占91.73%．

驗證實驗結果的方法：均方根誤差 (root mean square error, RMSE)是評估算法計算的預測值與真實值之間差距的指標,可用于衡量推薦效果[17],RMSE的定義如式(4)所示,用戶均方根誤差 (user root mean square error, URMSE)的定義如式(5)所示：

(4)

(5)

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

4.2實驗結果

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

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

圖2　STSUM的參數k與RMSE值關系Fig.2　Experimental results for different k of STSUM against RMSE

圖3　STSUM的參數k與URMSE值關系Fig.3　Experimental results for different k of STSUM against URMSE

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

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

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

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

圖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結語

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

參考文獻(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]. 計算機研究與發展,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] 印桂生, 張亞楠, 董宇欣, 等.基于受限信任關系和概率分解矩陣的推薦[J]. 電子學報, 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] 孫光福, 吳樂, 劉淇, 等. 基于時序行為的協同過濾推薦算法[J].軟件學報, 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.浙江大學學報(工學版)網址： www.journals.zju.edu.cn/eng

基金項目：國家自然科學基金青年基金資助項目(61300115).

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

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

中圖分類號：TP 391

文獻標志碼：A

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