融合標簽傳播和信任擴散的個性化推薦方法

陳博文,劉功申,張浩霖,郭弘毅

(上海交通大學信息安全工程學院,上海 200240)

1 概述

近年來,互聯網與信息技術高速發展,人們逐漸地從曾經信息匱乏的時代步入到了信息過載的時代[1]。在這個時代,對于信息消費者而言,從無數信息中尋找自己感興趣的內容并非易事；同時對于信息生產者,讓自己生產的信息從無數信息中脫穎而出被人注意同樣是件困難的事情。而推薦系統則是實現信息消費者和信息生產者雙贏的重要工具。目前,推薦系統已滲透到互聯網的各種領域,電子商務網站(如卓越網的圖書銷售)、音樂網站(如豆瓣電臺的歌曲推薦)、社區平臺(如新浪微博的熱門微博推薦)等都不同程度上使用了推薦系統。

基于內容的推薦和協同過濾推薦是如今使用最為廣泛的推薦算法[2]之一。與基于內容的推薦不同,協同過濾無需計算物品特征描述或者用戶記錄的相似度,取而代之的是尋找與用戶相似的用戶群[3],然后經由這些用戶預測此用戶可能喜歡的物品。傳統的協同過濾算法面臨著用戶-項目評分數據稀疏的問題,如果用戶之間共同評分的項目很少,那么往往無法得到令人滿意的推薦。

目前人們使用網絡的方式已然發生了顯著變化,互聯網用戶扮演起越發活躍的角色,不僅會向其他人展示自己的偏好,而且還會和志同道合且值得信任的用戶建立信任聯系。在龐大而復雜的網絡中,一群個體相互之間類似,而與網絡中其他個體不相似,則這些個體能構成一個社區[4]。美國著名的尼爾森調查機構調查了影響用戶相信某個推薦的因素,結果顯示,90% 的用戶相信朋友對他們的推薦[5]。而由信任網絡得到的推薦可以很好地模擬現實社會,因此,信任網絡也可以在推薦算法中扮演重要角色,傳統協同過濾算法中的用戶間的相似度可以被信任網絡中用戶間的信任度替代。然而,由于用戶數目的龐大,用戶間的信任數據也不可避免地面臨著數據稀疏的問題。

針對上述問題,本文提出一種融合標簽傳播和信任擴散的信任網絡個性化推薦方法。由于每個用戶都有屬于自己的大社區,包括現實的和潛在的信任關系,因此利用標簽傳播算法得到每個用戶獨屬的大社區。而在每個用戶各自的大社區中,由于與其他用戶的信任關系數據存在類似的情況,因此提出信任預處理算法,擴展用戶的信任網絡。此外,考慮到各個用戶對其他用戶的信任程度存在差異,提出信任擴散算法,對預處理算法得到的信任度做進一步區分,使得用戶之間的信任程度更趨向差異化。

2 相關研究

近年來,已有不少研究將信任網絡引入到推薦系統中。文獻[6]提出一般信任傳遞算法,定義(d-n+1)/d為源節點與目標節點的預測信任度,其中,d是信任傳遞的最大距離；n代表源節點和目標節點間的最短距離。文獻[7]在預測間接信任度時考慮源節點與目標節點間傳遞路徑的總數。文獻[8]除考慮社交網絡關系中的friendship 外,還考慮了membership,即社群關系。文獻[9]使用隱性信任網絡,由用戶-項目評分數據導出信任網絡,從用戶和用戶對于特定項目兩層次進行分析。文獻[10]提出了標簽傳播算法(Label Propagation Algorithm,LPA),用已標記節點標簽信息去預測未標記節點標簽信息。文獻[11]提出的算法使用標簽傳播在大范圍網絡中探測區域結構,該算法是近線性時間的。文獻[12]提出了用戶-商品二部圖推薦算法,也稱作物質擴散算法,這個算法的過程就是模擬了物質在空間中擴散即能量發生變化的過程。文獻[13]提出了用戶-商品-標簽三部圖推薦算法,使用了之前的物質擴散算法并利用標簽信息進行推薦,大幅提高了算法的推薦性能。

3 融合標簽傳播和信任擴散的個性化推薦

一般情況下,可以用有向圖來表示信任網絡,用戶由節點來表示,而邊就可以表示為用戶間的信任關系。在本文所使用的Epinions.com 數據集中,用戶關系數據“22605 42915 1”表示為用戶節點“22605”信任用戶節點“42915”(數據集中信任關系全是用“1”表示,無差異)。本文的個性化推薦旨在有效處理信任關系數據稀疏的問題,在對用戶之間的信任關系數據進行擴展的同時,將信任進一步差異化,舉例來說,A同時信任B和C,但A對B的信任度可能與A對C的信任度不同。本文個性化推薦方法的架構如圖1 所示。將用戶項目評分數據與用戶之間信任數據作為整個架構的輸入,并且用字典來表示數據,分別為用戶信任關系字典和用戶項目評分字典；個性化推薦架構核心為經由基于標簽傳播的大社區發現模塊得到每個用戶獨屬的大社區,在大社區內通過信任預處理模塊和信任擴散模塊得到新的用戶信任關系字典,接著使用用戶項目評分字典進行協同過濾,得到預測評分值。該架構的輸出為用戶的推薦列表。

圖1 個性化推薦方法架構

3.1 基于標簽傳遞的大社區發現算法

在龐大的信任網絡中,總是存在著由興趣愛好或行業領域或內容主題等組成的大社區。但是每個用戶信任或者被信任的用戶是有限的,因此,有必要為用戶發掘獨屬于自己的大社區。大社區的鄰居們總能或多或少地對用戶提供一些幫助,推薦用戶可能喜愛或者感興趣的東西。本文擴展標簽傳遞算法去發現用戶各自的大社區。

用戶的標簽可以代表用戶所屬的興趣愛好、行業領域或者是關注的內容主題。如果一個用戶關注了其他用戶,也就代表著此用戶可能與其關注的人有共同愛好或者屬于同一領域。標簽傳遞的意義在于,在一個用戶關注的所有用戶中,標簽出現次數最多的用戶代表該用戶也可能有此愛好或是屬于此領域；具有相同標簽的用戶則能構成一個大社區,這個大社區能夠表達用戶最顯著的特征。

基于標簽傳遞的大社區發現算法步驟如下：

(1) 使用用戶信任關系字典進行迭代,得到用戶A的信任列表以及被信任列表,然后獲得信任用戶的信任列表以及被信任用戶的被信任列表,可以設定迭代層數來控制用戶的關系網大小,得到關系網用戶集合U。

(2) 發現用戶A的1-派系,此派系中所有用戶相互關注：遍歷用戶A所信任的用戶,得到同時也關注用戶A的用戶列表,在這個列表中尋找相互關注的用戶列表U′,并且將此列表的所有用戶賦予標簽L0。使用1-派系的目的是為了減小標簽傳遞算法得到社區的隨機性。

(3) 圖分割

1) 在用戶集合U中,除了U′中賦予L0,其余用戶x都賦予標簽x,Lx(0)=x,這些用戶的標簽都是唯一的。

2) 設置t=1。

3) 以隨機模式訪問U中所有用戶。

4) 對于任意x∈U：

其中,k為用戶A關注的用戶數；函數f返回用戶x所關注的人標簽出現頻次最高的標簽(為了避免標簽來回震蕩,m代表在一輪計算中,計算用戶x的標簽時,有m個用戶x關注的用戶標簽已更新)。

5) 如果每個用戶的標簽都是他關注的所有人的標簽出現頻次最高的標簽,那么停止迭代,否則t=t+1,回到步驟3)。

(4) 通過圖分割,得到與用戶A標簽相同的用戶群,從而獲得獨屬于用戶A的大社區用戶列表CA。

3.2 信任預處理算法

在獨屬于每個用戶的大社區中,都是些志同道合或是值得信任的用戶,但由于大社區中的用戶真實的信任關系有限,因此大社區的信任網絡也不可避免地面臨著信任關系數據稀疏的問題,所以,對大社區的信任網絡進行新的信任關系的預測是很有必要的。在用戶信任關系字典中,如果用戶A信任用戶B,則表示為D[A][B]=1,反之,則為D[A][B]=0,無值則表示信任不明確[14]。假如用戶A信任的用戶相當一部分信任用戶B,從一定程度上表明A和B存在一定相似性[5],未來B信任的人A也有可能信任,所以,可以將協同過濾思想應用于用戶信任關系字典。對于用戶Ui,在其獨屬的大社區CUi中,同時包含與有Ui有信任關系的成員集合CUi1和沒有信任關系的成員集合CUi2,對于?B∈CUi2,可以計算用戶A和成員集合CUi1的相似度,得到相應的鄰居集合,接著可以依據鄰居集合中的用戶對B的評價來預測A對B的評價。

(1) 用戶相似度計算

用戶Ui對用戶Uj相似度可以定義為：用戶Ui信任的用戶集合與信任用戶Uj的用戶集合的用戶交集數和用戶Ui信任的用戶的總數之比。此處相似度的含義是用戶Ui關注的用戶中,有多大比例也關注了用戶Uj。其中,用戶Ui信任的用戶集合由TUi表示,而信任用戶Uj的集合由TRUj表示。但是,如果用戶Ui關注的用戶中極少數關注了用戶Uj,則不足以表明他們存在相似性,因此應當設定閾值x,只有用戶Ui關注的用戶中同時關注用戶Uj的數量大于等于x,才可計算兩者之間的相似度。

S(Ui,Uj)≠S(Uj,Ui),Ui和Uj之間的相似度不可逆。

(2) 用戶信任度預測

獲取用戶Ui大社區內有信任關系的、并且能夠計算得到相似度的用戶作為鄰居用戶集合,CUi1′為鄰居用戶中信任Uj的用戶子集,CUi2為Ui大社區CUi內無信任關系的用戶集合。則Ui與Uj之間信任度表達式W(Ui,Uj) 如下：

其中,Uj∈CUi2。

3.3 信任擴散算法

傳統的擴散算法是應用在用戶-商品二部圖或者用戶-商品-標簽三部圖上；本文則是對擴散算法進行改進,應用于用戶-用戶二部圖上,稱之為信任擴散算法。

信任網絡中有信任關系和被信任關系,有些信任關系式對稱的,是雙向信任關系；也有許多信任關系是非對稱的,僅是單向信任關系。Epinions.com網站上用戶可以對某物品寫評論(review),而其他用戶可以對評論進行反饋評分(review rating)。有調查顯示,大多數人認為對于一件商品最為可靠的信息來源是和他們相似的一群人[15]。在Epinions.com 網站中,評論者(reviewer)如果撰寫了一篇評論(review),又或者是向別人進行推薦,那么和這個評論者志趣相投的用戶通常會覺得這篇評論很有價值,并且有極大可能相信該評論者未來撰寫的評論或者去購買該評論者所推薦的物品,即信任該評論者[16]。每一個人都會對某些事物產生興趣,只是各人表現方式不同,有些人會寫關于自己感興趣事物的評論,有些人會閱讀別人的評論并且進行反饋,展現出自己感興趣的方面。寫下評論的評論者大多希望得到其他用戶的反饋,他們希望能夠從反饋的那些用戶中尋找與自己愛好類似領域的用戶,并閱讀這些用戶的評論或者進一步關注他們推薦的事物,即對評論反饋者產生信任[17]。所以,如果當用戶A對用戶B的評論贊同或是對他買的物品感興趣時,那么A信任B,而且這個信任關系可以在給A做推薦的時候做出貢獻；同樣B被A信任,從一定程度上來說,A與B也存在一定相似性,對于被信任者B來講,A對其信任,也能使得A 的某些決策給B做推薦的時候做出貢獻[18]。

用戶-用戶二部圖如圖2 所示,從中可知,A,B,C,D信任用戶總數為2,1,2,3。

圖2 用戶-用戶二部圖

將二部圖轉為信任推薦貢獻字典,如表1 所示。其中,行和列表示為不同的用戶,而值則表示用戶間的推薦貢獻。

表1 信任推薦貢獻字典

如表1 中的第2 行所示,由二部圖可知A信任C,D,則A,B,C、D在給A做推薦時貢獻為0.00,0.00,0.50,0.50。同樣的,如表1 第5 行所示,二部圖可知D信任A,B,C,則A,B,C,D在給D做推薦的時候貢獻為0.33,0.33,0.33,0.00。上文提到,Epinions.com 數據集中信任關系全是用“1”表示,表1 只是在假設所有信任值均1 的前提下進行的推薦貢獻字典輸出,因此,3.2 節信任預處理算法擴展得到的某些預測信任值雖不等于1,并不會影響信任推薦貢獻字典的生成。

本文考慮一般的用戶信任關系二部網絡G(X,X′,E),X和X′代表用戶節點,由x1,x2,…,xn和x1′,x2′,…,xn′各自表示,X′是X的拷貝,均是用戶節點集合[12]；而E則為表示信任關系的邊。每個用戶節點xi(二部圖左側)對于他信任的用戶節點xj′(二部圖右側),在xj′處標注xi對xj′的信任值(這里的信任值由3.2 節信任預處理算法得到)。接著將xi信任的所有用戶節點的信任值進行累加,并且得到xj′處標注的值和信任累加值之比,即經由信任擴散過程后,xj′給xi做推薦時的貢獻值。

進一步推廣,假設Ui信任m個用戶,信任集合為M,對于用戶Uj,其給Ui做推薦的貢獻值為：

同時,由用戶-用戶二部圖可知,A,B,C,D被信任用戶總數為2,1,3,2。將二部圖轉為被信任推薦貢獻字典,如表2 所示。行列均表示用戶,值代表了用戶間的推薦貢獻。如表2 中的第4 行所示,由二部圖可知,C被A,B,D信任,則A,B,C,D在給C做推薦時貢獻為0.33,0.33,0.00,0.33。

表2 被信任推薦貢獻字典

與之前類似,考慮一般的用戶信任關系二部網絡G(X,X′,E),X,X′和E代表意義不加贅述。每個用戶節點xi′(二部圖右側),對于信任他的用戶節點xj(二部圖左側),即xj信任xi′,在xj處標注xj對xi′的信任值(這里的信任值由3.2 節信任預處理算法得到)。接著將所有信任xi′的用戶節點對xi′的信任值進行累加,并且得到xj處標注的值和信任累加值之比,即經由信任擴散過程后,xj給xi′做推薦時的貢獻值。

進一步推廣,假設Ui被n個用戶信任,被信任集合為N,對于用戶Uj,其給Ui做推薦的貢獻值為：

本文3.2 節信任預處理算法預測了用戶之間的信任值,擴展了信任網絡。對于用戶Ui來說,在其獨屬的大社區CUi1中,原來有信任關系的成員集合CUi1將擴展為CUiNew,并且將之前的2 種推薦貢獻情況混合考慮,引入調節因子λ,則擴散后的用戶信任度為：

其中,Uj∈CUiNew；λ為引入的調節因子,其取值范圍為[0,1]。

3.4 用戶項目預測評分

經過基于標簽傳遞的社區發現、信任預處理和信任擴散算法,得到了新的用戶信任關系字典,接著將用戶信任度取代傳統協同過濾的用戶相似度,并且以用戶信任度為權重。然后,依據用戶的信任用戶集合對項目的評分來預測目標用戶對目標項目的評分。這里使用最常用的評分預測公式[19]：

4 實驗結果及分析

4.1 數據集

本文使用的是來源于Epinions.com 的數據集[6],在Epinions.com 的用戶評論平臺上,用戶不但可以表達他們喜歡某個物品,而且還能聲明一般情況下會信任某些用戶及其觀點。整個數據集由49 290 個用戶、139 738 個項目、487 181 條用戶信任數據以及664 824 條用戶-項目評分數據組成。隨機選取整個數據集的80% 作為訓練集,20% 作為測試集。經實驗,設定信任預處理算法中的閾值x設為3。

4.2 度量標準

平均絕對誤差(Mean Absolute Error,MAE)是常用的推薦質量評價標準之一,MAE 通過衡量預測評分值與實際評分值之間的差距來計算準確率,MAE 值越小則準確率越高。MAE 的計算公式如式(7)所示,其中,是所有預測評分個數；dp是預測評分值；dt是實際評分值。

4.3 實驗結果

4.3.1 調節因子實驗

在3.3 節的信任擴散算法中,λ的取值為[0,1]。本文將λ的值從0 到1 以步長0.05 增加。隨機選取得到1 份訓練集和測試集,應用本文的個性化推薦算法共做21 次實驗,結果如圖3 所示。

圖3 不同λ 值的準確率比較

可見,在進行信任擴散時,λ在0.95 和0.05 時準確率最差。而當各占50% 左右時準確率最好。若信任用戶(被信任用戶)被賦予較大權重,被信任用戶(信任用戶)權重很小時,相對于只考慮信任用戶(被信任用戶)時來說,準確率要下降很多,原因可能是：新添加的權重很小的被信任用戶(信任用戶),導致相當多的新用戶信任度數值很小,引入了噪聲,影響了準確率。在λ為0.5 左右時準確率最好,原因可能是同時考慮信任用戶和被信任用戶,是將所有和目標用戶有直接關聯的全盤考慮進去,可能在類似Epinions.com 的交流平臺上,信任者可以給被信任者做決策時提供相當可觀的貢獻。

4.3.2 準確率實驗

基于初始信任網絡的算法是指直接使用默認的用戶之間的信任數據,不進行擴展和差異化,以用戶信任度替代用戶相似度進行協同過濾,本文以only_trust 表示該方法。基礎信任擴散算法是指直接使用默認用戶之間的信任數據,并且使用本文3.3 節算法,進行協同過濾,本文以only_diff 表示該方法。文獻[6]使用簡單信任傳遞模型,得到的預測信任度(d-n+1)/d,d為最大信任傳遞距離,n為源節點和目標節點的最短距離,本文以prop_trust 表示該方法,且d設置為2,將得到的用戶信任度進行協同過濾。將本文提出的推薦方法以lp_pre_diff 表示且λ取0.5,與prop_trust,only_trust 以及only_diff 方法進行比較。隨機選取得到5 份訓練集以及測試集用來實驗,實驗結果如圖4 所示。每次實驗使用一份訓練集和測試集,并且對4 種推薦方法的準確率進行比較。

圖4 不同推薦方法的準確率比較

從實驗結果可知,本文方法和prop_trust 方法[6]準確率明顯高于only_trust 和only_diff 方法,原因可能是only_trust 和only_diff 方法所使用的用戶信任關系數據都是原始的,較為稀疏,無法得到可靠的推薦。除去實驗2,本文算法均好于prop_trust 方法。原因可能是本文算法通過大社區提取、預處理和信任擴散等一系列方法擴展信任網絡并且將信任差異化,在預測目標用戶對某用戶信任度時,考慮到了目標用戶所在大社區內的大多數和某用戶有關聯的用戶群的意見,因此相對合理；不過,用戶所屬的大社區中提供建議的用戶較多,因此預測處的信任關系仍然可能沒有那么可靠,在最后預測項目評分的時候使最后得到的準確率降低。

5 結束語

基于信任網絡的推薦方法面臨信任數據過于稀疏的問題,導致推薦效果不理想。本文提出改進方法,得到屬于各個用戶的大社區、擴展用戶信任網絡并且使信任度差異化,一定程度上解決了數據稀疏的問題。實驗結果表明,改進后的算法具有較高的準確率。下一步工作是將隱性信任引入到推薦系統中,從而更好地解決數據稀疏問題,提高準確率。

[1]項 亮.推薦系統實踐[M].北京：人民郵電出版社,2012.

[2]Lü L,Medo M,Yeung C H.Recommender Systems[J].Physics Reports,2012,519(1)：1-49.

[3]Segaran T.集體智慧編程[M].王開福,譯.北京：電子工業出版社,2009.

[4]Rajaraman A,Ullman J D.大數據：互聯網大規模數據挖掘與分布式處理[M].王 斌,譯.北京：人民郵電出版社,2012.

[5]Jannach D,Zanker M,Felfernig A.推薦系統[M].蔣 凡,譯.北京：人民郵電出版社,2013.

[6]Massa P,Avesani P.Trust-aware Collaborative Filtering for Recommender Systems[C]//Proceedings of CoopIS,DOA,and ODBASE Book Subtitle OTM Confederated International Conferences.Agia Napa,Cyprus,[s.n.],2004：492-508.

[7]陳曉誠.基于信任傳播模型的協同過濾算法研究[D].廣州：中山大學,2010.

[8]Yuan Quan,Chen Li,Zhao Siwan.Factorization vs.Regularization：Fusing Heterogeneous Social Relationships in Top-N Recommendation[C]//Proceedings of the 5th ACM Conference on Recommender Systems.New York,USA：ACM Press,2011：245-252.

[9]O’Donavan J,Smyth B.Trust in Recommender Systems[C]// Proceedings of the 10th International Conference on Intelligent User Interfaces.New York,USA：[s.n.],2005：167-174.

[10]Zhu Xiaojin,Ghahramani Z.Learning from Labeled and Unlabeled Data with Label Propagation[R].Pittsburgh,USA：Carnegie Mellon University,Technical Report：CMU-CALD-02-107,2002.

[11]Raghavan U N,Albert R,Kumara S.Near Linear Time Algorithm to Detect Community Structures in Largescale Networks[J].Physical Review E,2007,76(3).

[12]Zhou Tao,Ren Jie,Medo M.Bipartite Network Projection and Personal Recommendation [J].Physical Review E,2007,76(4).

[13]Zhang Zike,Zhou Tao,Zhang Yicheng.Personalized Recommendation via Integrated Diffusion on User-itemtag Tripartite Graphs[J].Physica A：Statistical Mechanics and Its Applications,2010,389(1)：179-186.

[14]Kantor P B,Ricci F,Rokach L.Recommender Systems Handbook[M].Berlin,Germany：Springer,2010.

[15]Edelman R,Williams E.Edelman Trust Barometer[EB/OL].[2014-01-15].http：//www.edelman.co.uk/trustbarometer/2007.

[16]Hill S,Provost F,Volinsky C.Network-based Marketing：Identifying Likely Adopters via Consumer Networks[J].Statistical Science,2006,21(2)：256-276.

[17]張 宇.在線社會網絡信任計算與挖掘分析中若干模型與算法研究[D].杭州：浙江大學,2009.

[18]定明靜.基于信任網絡的推薦技術研究與應用[D].成都：電子科技大學,2013.

[19]Resnick P,Lacovou N,Suchak M.GroupLens：An Open Architecture for Collaborative Filtering of Netnews[C]//Proceedings of ACM Conference on Computer Supported Cooperative Work.New York,USA：ACM Press,1994：175-186.