融合用戶動態(tài)標(biāo)簽和信任關(guān)系的協(xié)同過濾算法

吳鴻玲，程耕國

1.武漢科技大學(xué) 信息科學(xué)與工程學(xué)院，武漢 430081

2.武漢科技大學(xué) 冶金自動化與檢測技術(shù)教育部工程研究中心，武漢 430081

1 引言

隨著電子商務(wù)的快速發(fā)展，可提供的商品信息資源也日漸豐富，傳統(tǒng)的推薦算法[1]通過分析用戶購買和評分的歷史記錄來進(jìn)行預(yù)測和推薦。然而協(xié)同過濾推薦算法面臨著一些挑戰(zhàn)[2]，如數(shù)據(jù)稀疏、評分?jǐn)?shù)據(jù)不均衡、冷啟動等問題，使得系統(tǒng)難以向新用戶準(zhǔn)確地推薦商品。

為了有效地獲取用戶和商品的相關(guān)信息，并快速準(zhǔn)確地為用戶推薦感興趣的商品，近年來，基于社會化屬性的推薦算法得到了廣泛關(guān)注，有研究將信任關(guān)系引入到推薦系統(tǒng)的算法中，提出基于用戶信任關(guān)系的過濾推薦模型。例如，文獻(xiàn)[3]描述了一種基于用戶信任關(guān)系的協(xié)同過濾算法原理，它依據(jù)可靠性測試來建立鄰居用戶，進(jìn)而根據(jù)鄰居用戶進(jìn)行推薦。與“基于相似度評價的協(xié)同過濾算法”模型相比，“信任關(guān)系”模型[4]在參考用戶選取方面有所不同，它主要基于核心信任用戶的信息來向用戶推薦商品。文獻(xiàn)[5]中提出朋友關(guān)系為推薦系統(tǒng)中的重要信息之一，通過計算朋友間相似度，修正張量分解以建立推薦模型。文獻(xiàn)[6]提出一種基于共同用戶和相似標(biāo)簽的協(xié)同過濾算法，它通過把用戶個人標(biāo)簽信息加入到最近鄰協(xié)同過濾方法中以改善熱門用戶對推薦的影響。文獻(xiàn)[7]提出FTCF算法，它通過關(guān)系傳播機制尋找關(guān)系網(wǎng)絡(luò)中與目標(biāo)用戶興趣愛好相似的用戶，并找到符合目標(biāo)用戶需要的商品，利用TF-IDF思想，從用戶歷史標(biāo)簽記錄中挖掘該用戶的興趣愛好，最后將兩者進(jìn)行結(jié)合來解決數(shù)據(jù)稀疏問題。文獻(xiàn)[8]提出一種IBCF算法，它通過在項目間引入信任關(guān)系來計算項目相似度，在一定程度上提高了推薦精準(zhǔn)度和覆蓋率。文獻(xiàn)[9]提出SemPMF算法，它使用非監(jiān)督方式生成語義項特征，并將其與用戶項目偏好矩陣結(jié)合起來進(jìn)行推薦，提高了推薦質(zhì)量。

然而，這些推薦系統(tǒng)存在以下不足：（1）覆蓋率指標(biāo)與推薦精度存在互斥問題，采用的社會網(wǎng)絡(luò)信任取值為二進(jìn)制形式，即0-1表示方式，導(dǎo)致推薦精度下降；（2）二進(jìn)制0-1的表示方式會使用戶間的信息不對稱，因此信任值的合理計算對于提高算法性能至關(guān)重要；（3）以朋友關(guān)系式用戶或共同關(guān)注式用戶來計算信任值，使得信任關(guān)系中的用戶變窄，不具有普適性；（4）雖然在一定程度上提高了推薦的準(zhǔn)確度，然而其推薦歷時較長。

為解決上述問題，提出一種融合用戶動態(tài)標(biāo)簽和用戶信任關(guān)系的矩陣概率分解模型（Probability Matrix Factorization Model based on user dynamic Tags and user Trust relationships，TTPMFM）。

2 用戶與物品間的偏好標(biāo)簽矩陣

2.1 用戶與物品間的動態(tài)標(biāo)簽關(guān)系

用戶通過對項目添加注解來設(shè)置標(biāo)簽，且所設(shè)置的標(biāo)簽具有一定的社會屬性[10]，能引導(dǎo)和幫助用戶瀏覽和組織資源。本文采用三元組的形式在標(biāo)簽集、用戶集和項目集之間建立動態(tài)聯(lián)系，具體如圖1所示。

其中，用戶集涵蓋了系統(tǒng)中的所有用戶。標(biāo)簽集包括了系統(tǒng)使用的所有標(biāo)簽，每個標(biāo)簽可用詞語來表示，如“數(shù)據(jù)挖掘”。項目集囊括了模型中的所有項目資源，并且每個項目資源有唯一編號。

2.2 用戶動態(tài)標(biāo)簽偏好評分矩陣

圖1 用戶標(biāo)簽動態(tài)關(guān)系圖

用戶在訪問項目資源時，通常表現(xiàn)出兩類行為：（1）對標(biāo)簽進(jìn)行查找、新增和關(guān)注；（2）與資源進(jìn)行交互，例如瀏覽、點擊和收藏等。這兩類行為可以充分表現(xiàn)出用戶實時的偏好行為。通過計算這兩類行為的相關(guān)特征，并將其作為算法預(yù)測的權(quán)重，可以更好地向用戶推薦資源。

標(biāo)簽的質(zhì)量可用Sigmoid函數(shù)[11]進(jìn)行計算，從而獲得相關(guān)特征的權(quán)重。假定項目i與對應(yīng)標(biāo)簽t之間的權(quán)重值為w(i,t)，則可通過式（1）來計算w(i,t)。

其中，m是推薦標(biāo)簽的質(zhì)量，且滿足關(guān)系m=TF×IDF，其中TF為詞頻參數(shù)，指的是文檔d中詞條t的出現(xiàn)次數(shù)，IDF為文檔的逆頻文件頻率，指的是文檔頻率與詞條t頻率之間存在的反比關(guān)系。

為了對系統(tǒng)用戶與資源的交互過程進(jìn)行用戶偏好標(biāo)簽的預(yù)測推導(dǎo)，將用戶的偏好用評分來表達(dá)。這種方法也稱項目資源評級（Item-Rating，IR）。該方法充分考慮了相關(guān)特征權(quán)重對標(biāo)簽偏好預(yù)測推導(dǎo)過程的影響。

式中，變量ru,i表示用戶u對項目資源i的評價分?jǐn)?shù)，變量ω(i ,t)是項目資源i與標(biāo)簽t之間的權(quán)重，變量Mt是包含顯式標(biāo)簽t的所有項目資源集。

然而式（2）未考慮用戶未評價過的項目資源，例如，當(dāng)用戶對某個項目資源執(zhí)行收藏、關(guān)注等操作時，表明此類項目資源是用戶偏好的。為了展示隱式標(biāo)簽對項目資源預(yù)測推導(dǎo)的作用，采用公式（3）對用戶偏好進(jìn)一步預(yù)測：

綜合考慮顯隱式標(biāo)簽，即將式（2）和式（3）結(jié)合，則用戶與物品間的偏好標(biāo)簽矩陣為：

式中，TGut為融合顯式標(biāo)簽與隱式標(biāo)簽后的用戶偏好標(biāo)簽矩陣，且使用α（0≤α≤1）調(diào)節(jié)因子來為物品顯式標(biāo)簽與物品隱式標(biāo)簽設(shè)置權(quán)重。

3 用戶信任關(guān)系矩陣

基于圖的概念引出用戶信任關(guān)系圖，并分析用戶信任關(guān)系的建立過程。同時，在用戶信任關(guān)系的基礎(chǔ)上，建立基于用戶信任關(guān)系圖的反饋機制。

3.1 用戶信任關(guān)系分析

從人類社會關(guān)系的推薦角度來看，人們通常傾向于信任來自其熟人所推薦的信息。在電子商務(wù)推薦系統(tǒng)中，所有用戶都可以通過圖來建立用戶間的信任關(guān)系，如圖2的A所示，實線代表用戶間的直接信任關(guān)系（N1信任N2，N2信任N3）。通過N2與N3之間的信任關(guān)系，用戶N1間接地信任N3。如果N2與N3之間沒有信任關(guān)系，那么不可能在N1和N3之間建立信任關(guān)系，如圖2的B所示。下面給出與信任相關(guān)的一些定義。

定義1（直接信任）通過定義一個三元組＜i,j,DTi,j＞來表示直接信任，其中三元組代表從節(jié)點i指向節(jié)點 j的有向邊，DTi,j代表節(jié)點i到節(jié)點 j的直接信任值。

定義2（間接信任）通過定義一個三元組＜i,j,IDTi,j＞來表示間接信任，其中節(jié)點i通過有限跳H(H＞1,H∈N)到達(dá)節(jié)點 j，IDTi,j代表節(jié)點i到節(jié)點 j的間接信任值。

定義3（直接信任偏好準(zhǔn)則）對于信任圖中的任何一個節(jié)點i，它的直接信任節(jié)點比間接信任節(jié)點更加可信。例如圖2的A中DTN1N2比IDTN1N3可信度更高，即DTN1N2＞IDTN1N3。

圖2 人類社會中的信任過程

3.2 用戶信任關(guān)系的建立過程

用戶信任關(guān)系的主要因素是用戶偏好相似性和用戶的影響力。為了在用戶間建立信任值，需設(shè)置閾值θ來獲取用戶之間的相似度，如式（5）：

用戶間的信任關(guān)系具有轉(zhuǎn)移性和方向性等非對稱特性，通過使用這些非對稱的信任關(guān)系信息，可以有效緩解用戶評分矩陣的數(shù)據(jù)稀疏問題。為了測量用戶間的影響力，使用Jaccard距離[12]來衡量用戶的非對稱關(guān)系。的計算公式如式（6）：

用戶間的信任值TRu,v主要由用戶間相似度和用戶間影響力組成，通過分配不同的權(quán)值計算TRu,v，如式（7）：

3.3 基于用戶關(guān)系圖的信任反饋機制

定義4（信任查詢機制）根據(jù)輸入的查詢深度Level，查詢與活躍用戶節(jié)點Ni有關(guān)聯(lián)的直接信任值和間接信任值，直到查詢深度大于Level為止。將所有查詢到的直接信任用戶與間接信任用戶存放到信任用戶TNLl列表中。

定義5（反饋機制）基于信任值TRu,v（包括直接信任值和間接信任值）和項目評分值Rvi，根據(jù)公式（8）計算項目i的預(yù)測評分PRV(i)。如果PRV(i)與用戶的實際評分Rui相差不大，即滿足式（9），則將信任用戶列表TNLl中的top-N反饋給用戶u；如果相差太大，則更改閾值θ，直到項目i的預(yù)測評分PRV(i)與用戶的實際評分Rui相差不大為止。其中，Rvi為信任用戶對項目的評分值，Rui為活躍用戶對項目i的評分值。

式中，Level代表距離節(jié)點Ni的距離；W(l,α)代表信任值的加權(quán)因子函數(shù)，如式（10）所示；TNLl代表活躍用戶U直接信任和間接信任的用戶列表。

式中，α代表信任值初始衰減因子。

基于前文所述的用戶信任關(guān)系，提出一種基于用戶信任關(guān)系圖的反饋機制，如圖3所示。

圖3 基于信任的用戶反饋模型

圖3 中，邊緣代表不同節(jié)點之間的信任關(guān)系。當(dāng)請求用戶U0的推薦信息時，首先，該節(jié)點根據(jù)信任查詢機制向其直接信任節(jié)點（U1和U4）發(fā)送信任查詢信息，這些節(jié)點也同樣向其受信任的節(jié)點發(fā)送信任查詢信息，直到信任查詢過程結(jié)束；然后，基于反饋機制選擇信任值高的前N個用戶，并反饋其所有產(chǎn)品的信任值。通過此信任反饋模型，可以得到用戶U0的受信任節(jié)點（包括直接信任節(jié)點和間接信任節(jié)點）所推薦項目的綜合評分。

4 融合用戶動態(tài)標(biāo)簽與信任關(guān)系的概率矩陣分解模型

在矩陣概率分解過程中，主要基于潛在用戶特征與信任間存在的內(nèi)部關(guān)聯(lián)來實現(xiàn)信任矩陣的預(yù)測和計算。

文獻(xiàn)[13]中所使用的矩陣概率分解模型（Probability Matrix Factorization Model，PMFM）如圖4所示，該矩陣分解模型具有線性概率特征，它將用戶對項目的評價問題轉(zhuǎn)換為概率問題，其中σν和σμ為用戶和物品的隱式特征向量，σR為用戶評分?jǐn)?shù)據(jù)。然而，該模型未考慮到參與評分用戶的信任級別以及用戶與物品標(biāo)簽間的動態(tài)聯(lián)系。實際評分過程中不同用戶具有不同的定位和角色，過于均值化的評分概率預(yù)測不利于體現(xiàn)重點用戶的評分意見，不能獲得較為合理的決策結(jié)果。同時，用戶對物品標(biāo)簽的偏好是動態(tài)的，在實際推薦系統(tǒng)中，需要獲取用戶與物品標(biāo)簽的偏好交互行為，這樣才能更好地向用戶推薦商品。

圖4 PMFM模型

為解決上述問題，融合信任關(guān)系和動態(tài)標(biāo)簽，設(shè)計如圖5所示TTPMFM模型。在TTPMFM模型中，評分矩陣為n行m列，其中，第 j行對應(yīng)的潛在特征為uj，第i列對應(yīng)的潛在特征為vi。，Nui為具有相似偏好標(biāo)簽的用戶集合，Nvi為用戶u所信任的用戶集合，tg(u1,t)為用戶u1與物品標(biāo)簽t之間的關(guān)聯(lián)程度，tr(v1,u)為用戶v1與用戶u之間的信任程度，且tg(u1,t)與tr(v1,u)分別來源于用戶偏好標(biāo)簽矩陣和用戶信任關(guān)系矩陣。

圖5 TTPMFM模型

在進(jìn)行模型求解過程中，uj和vi兩個潛在特征均服從高斯特征分布，以來表示，融合用戶動態(tài)偏好標(biāo)簽矩陣和用戶信任關(guān)系矩陣后，用戶動態(tài)偏好矩陣與物品潛在特征的聯(lián)合概率分布為：

同理，用戶信任關(guān)系矩陣與用戶潛在特征的聯(lián)合概率分布為：

并且在TTPMFM模型中，U和V相互獨立，評分矩陣R的條件概率為：

結(jié)合公式（11）、（12）和（13），通過貝葉斯推理可以得到用戶和物品潛在特征的后驗概率分布為：

利用梯度下降法來對目標(biāo)函數(shù)進(jìn)行求解，對每個用戶Uj和每件物品Vi分別求偏導(dǎo)，如式（16）和式（17）：

綜上所述，TTPMFM模型的求解過程描述如下。

輸入：用戶與物品之間的動態(tài)偏好標(biāo)簽矩陣TGut，用戶信任關(guān)系矩陣TRu,v，用戶項目的評分矩陣R，近鄰參數(shù)k。

輸出：預(yù)測目標(biāo)用戶對未評分項目的評分值。

求解步驟：

（1）根據(jù)數(shù)據(jù)集計算用戶-項目評分矩陣。

（2）根據(jù)公式（4）計算用戶-項目的動態(tài)偏好標(biāo)簽矩陣。

（3）根據(jù)公式（5）計算目標(biāo)用戶與其他用戶之間的信任關(guān)系。

（4）根據(jù)步驟（2）和（3）得到的矩陣，利用K-NN算法[14]獲得目標(biāo)用戶u的K個用戶-項目偏好標(biāo)簽集合，以及K個與目標(biāo)用戶信任值極高的近鄰用戶集合。

（5）設(shè)置迭代初始步數(shù)i=1，將步驟（4）得到的集合帶入公式（15）。

（6）根據(jù)梯度下降法原理，計算目標(biāo)函數(shù)的下降可行方向d(i)，并依據(jù)公式（15）中的約束條件來計算下降方向的步長[0，λmax]。

（7）根據(jù)步驟（6）所獲得的下降方向以及步長范圍，利用0.618法[15]計算最優(yōu)步長λi。

（8）遍歷步驟（4）所得到集合的每個數(shù)據(jù)。

（9）獲得公式（16）、（17）的最優(yōu)解，最終得到目標(biāo)用戶u所有參數(shù)。

（10）對步驟（9）得到的目標(biāo)用戶參數(shù)進(jìn)行矢量相乘，即獲得目標(biāo)用戶對待評物品的預(yù)測值。

5 實驗結(jié)果及分析

為了進(jìn)一步提高計算速度，實驗平臺使用VMware Workstation9.0虛擬軟件將1臺TS250聯(lián)想塔式服務(wù)器（Intel至強E3-1200 v6處理器，8 GB內(nèi)存）虛擬成8臺虛擬主機，1臺惠普PAVILION 14-AL125TX作為Master，在Ubuntu 12.0.4系統(tǒng)上部署計算機集群，集群中包括8個DataNode和1個TaskTracker。

5.1 實驗數(shù)據(jù)

在MovieLens數(shù)據(jù)集以及Jester-Data數(shù)據(jù)集上對所提模型進(jìn)行驗證。在基于包含用戶對電影的評分信息、用戶間的評價信息、用戶的人口特征統(tǒng)計等類型信息的數(shù)據(jù)集上預(yù)測模型做出的用戶評分。使用Python爬蟲技術(shù)隨機從淘票票站點抓取了943個用戶對1 682部電影的評分?jǐn)?shù)據(jù)，共計100 000條評分信息，其中每組用戶至少對10組標(biāo)簽進(jìn)行了評分，原評分區(qū)間為1～10之間的整數(shù)，為了便于計算，將其歸一化為0～1之間的區(qū)間。評分值越高，則表明用戶對電影的喜好程度越高。即在MovieLens測試集中，共有943組用戶，1 682組電影，100 000條標(biāo)簽評分信息，其中每組用戶至少對10組標(biāo)簽進(jìn)行了評分。考慮到Jester-Data數(shù)據(jù)集過于稠密，因此該數(shù)據(jù)集（用Python技術(shù)隨機在百度新聞?wù)军c上抓取數(shù)據(jù)）選取1 743組用戶，這些用戶對121組新聞進(jìn)行了評價，包含18 924組用戶標(biāo)簽評分信息，且每組用戶至少包含一組用戶標(biāo)簽評分信息。這兩個數(shù)據(jù)集的相關(guān)屬性如表1所示。

為了使實驗結(jié)果不失一般性，采用5-fold交叉驗證方法，將數(shù)據(jù)集分為測試集和訓(xùn)練集，比例為1∶4，且這兩個集合互補，能涵蓋整個數(shù)據(jù)集。

表1 數(shù)據(jù)集相關(guān)屬性

5.2 評價指標(biāo)

（1）平均絕對誤差指標(biāo)MAE：

其中，pi表示用戶的預(yù)測評分，ri表示用戶的實際評分，N表示評分條數(shù)。平均絕對誤差值越小，推薦系統(tǒng)的推薦精度越高。

（2）平均準(zhǔn)確率指標(biāo)Precision和平均召回率指標(biāo)Recall：

其中，Ru為模型根據(jù)訓(xùn)練集用戶的行為給用戶做出的Top-N推薦集，Tu為用戶對測試集所做出的正面評分集，N為測試用戶的數(shù)目。平均準(zhǔn)確率和平均召回率的值越大，所預(yù)測出的項目越接近目標(biāo)用戶，表現(xiàn)出的推薦效果越好。

5.3 實驗結(jié)果分析

（1）閾值對數(shù)據(jù)集的影響

在Jester-Data測試集和MovieLens測試集上設(shè)置不同的閾值，并設(shè)定用戶近鄰參數(shù)值為8，測試這兩個數(shù)據(jù)集的平均絕對誤差。實驗結(jié)果如圖6所示。

圖6 不同閾值下的平均絕對誤差

從圖6可以看出，隨著閾值θ不斷增大，MovieLens測試集的平均絕對誤差呈下降趨勢（先迅速下降，后趨于平穩(wěn)）。而對于Jester-data測試集，其平均絕對誤差先緩慢下降，再逐漸增加，最后趨于平穩(wěn)。這是由于Jesterdata測試集的規(guī)模要小于MovieLens測試集的規(guī)模。當(dāng)閾值θ較小時，由于MovieLens測試集的規(guī)模大，當(dāng)前用戶的信任關(guān)系用戶較多，計算用戶相似性的時間復(fù)雜度和空間復(fù)雜度較大，因此無法快速準(zhǔn)確地為當(dāng)前用戶生成推薦；而Jester-data測試集的規(guī)模小，通過公式（5）、（6）、（7）可以計算出較高信任值的用戶，因此可以為當(dāng)前用戶準(zhǔn)確地生成推薦信息。當(dāng)閾值θ較大時，由于Jester-data測試集的規(guī)模小，當(dāng)前用戶的信任關(guān)系用戶較少，導(dǎo)致相似性用戶較少，無法計算出較高信任值的用戶，因此缺少足夠的評分?jǐn)?shù)據(jù)來進(jìn)行預(yù)測推薦；而MovieLens測試集的規(guī)模大，可以計算出較高信任值用戶，因此可以得到足夠的評分?jǐn)?shù)據(jù)來進(jìn)行預(yù)測推薦。

由圖6可知，對于Jester-data數(shù)據(jù)集，閾值θ設(shè)定為0.1時，推薦性能最佳；對于MovieLens數(shù)據(jù)集，閾值θ設(shè)定為1時，推薦性能最佳。因此，針對不同的數(shù)據(jù)集，需要選取合適的閾值θ才能獲取準(zhǔn)確的推薦信息。

（2）與其他算法性能的比較

為了驗證所提算法的性能，以MAE、Precision以及Recall為評估指標(biāo)，選取FTCF[16]、IBCF[17]以及SemPMF[18]3種經(jīng)典的協(xié)同過濾算法，在不同近鄰參數(shù)K下進(jìn)行訓(xùn)練和測試。如圖7為4種算法在不同近鄰參數(shù)K下的平均絕對誤差、準(zhǔn)確率及召回率的對比。

圖7 不同近鄰參數(shù)K的實驗結(jié)果

從圖7的實驗結(jié)果可以看出，與FTCF、IBCF以及SemPMF算法相比，本文算法在不同近鄰參數(shù)K的環(huán)境下，均可獲得良好的性能。這是由于本算法在推薦過程中融合了用戶的動態(tài)偏好標(biāo)簽和信任關(guān)系，使得推薦模型能迅速感知用戶的喜好并基于用戶的社會化屬性選擇近鄰用戶，從而向當(dāng)前用戶準(zhǔn)確地推薦商品。

6 結(jié)束語

針對社交網(wǎng)絡(luò)的推薦因信任值存在互斥導(dǎo)致的推薦精度下降的問題，提出了一種融合用戶動態(tài)標(biāo)簽和用戶信任關(guān)系的矩陣概率分解模型。它在一定程度上緩解了傳統(tǒng)的協(xié)同過濾算法存在的數(shù)據(jù)稀疏、用戶評分不均等問題，提高了協(xié)同過濾推薦算法的性能。實驗結(jié)果表明，該算法模型在絕對誤差均值、準(zhǔn)確率與召回率方面獲得了不錯的效果。目前，有關(guān)推薦系統(tǒng)中信任關(guān)系的研究主要體現(xiàn)在強關(guān)系和弱關(guān)系上，而關(guān)于非信任關(guān)系的研究很少，本文接下來可以針對非信任關(guān)系做進(jìn)一步的研究。