基于隱含信任關(guān)系的概率張量分解推薦算法

趙超， 韓立新， 楊憶,2， 何戀

(1.河海大學(xué),計(jì)算機(jī)與信息學(xué)院，南京 211100;2.淮北師范大學(xué),計(jì)算機(jī)學(xué)院，安慶 235000)

0 引言

隨著互聯(lián)網(wǎng)的不斷發(fā)展，網(wǎng)絡(luò)中產(chǎn)生的信息呈爆炸性增長(zhǎng)，出現(xiàn)了信息過(guò)載的現(xiàn)象，在此背景下，基于信息過(guò)濾技術(shù)的推薦系統(tǒng)應(yīng)運(yùn)而生。推薦系統(tǒng)試圖給用戶推送用戶可能感興趣的物品(包括音樂(lè)、電影、圖書等)。盡管傳統(tǒng)的基于協(xié)同過(guò)濾的推薦方法[1]已經(jīng)被廣泛運(yùn)用到像亞馬遜這種大型著名公司的商業(yè)系統(tǒng)中，但是仍存在數(shù)據(jù)稀疏性以及預(yù)測(cè)準(zhǔn)確性的問(wèn)題。

為了緩解上述兩個(gè)問(wèn)題，很多學(xué)者對(duì)其進(jìn)行了研究，并提出了很多有效的算法。Ma等人[2-3]通過(guò)在矩陣分解中加入社會(huì)正則化項(xiàng)、考慮利用用戶之間的直接信任關(guān)系進(jìn)行推薦，這種方法忽視了用戶之間的隱含信任關(guān)系。Liu等人[4]基于上下文利用決策樹對(duì)數(shù)據(jù)進(jìn)行分組，并融入社會(huì)關(guān)系進(jìn)行推薦；Chen等人[5]考慮到存在離散的和連續(xù)的上下文，利用譜聚類對(duì)數(shù)據(jù)進(jìn)行分組，并融入信任關(guān)系來(lái)提升推薦效果。這些方法只是利用上下文對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，并沒(méi)有將上下文融入到模型中。為了進(jìn)一步提高推薦系統(tǒng)性能，本文通過(guò)鏈路預(yù)測(cè)的方法找出用戶之間的隱含信任關(guān)系并對(duì)利用上下文構(gòu)建的張量進(jìn)行分解[7-11]，提出基于隱含信任關(guān)系的概率張量分解推薦算法。

1 相關(guān)工作

1.1 用戶信任關(guān)系

1.2 概率矩陣分解

概率矩陣分解[6](PMF)是在基本的矩陣分解基礎(chǔ)上引入概率模型來(lái)進(jìn)一步優(yōu)化。PMF基于以下假設(shè)：觀測(cè)評(píng)分矩陣R以及近似矩陣R′服從高斯分布；用戶特征矩陣U以及物品特征矩陣V服從高斯分布。通過(guò)觀測(cè)評(píng)分矩陣已知值得到用戶特征矩陣U以及物品特征矩陣V，然后利用特征矩陣去預(yù)測(cè)觀測(cè)評(píng)分矩陣中的未知值。

假設(shè)有m個(gè)用戶對(duì)n個(gè)物品的評(píng)分矩陣，Rij表示用戶i對(duì)物品j的評(píng)分，根據(jù)貝葉斯推理，通過(guò)最小化如下目標(biāo)函數(shù)來(lái)求解用戶特征矩陣U以及物品特征矩陣V：

1.3 網(wǎng)絡(luò)鏈路預(yù)測(cè)

網(wǎng)絡(luò)中的鏈路預(yù)測(cè)[13]是指如何通過(guò)已知的網(wǎng)絡(luò)節(jié)點(diǎn)以及網(wǎng)絡(luò)結(jié)構(gòu)等信息預(yù)測(cè)網(wǎng)絡(luò)中尚未產(chǎn)生連邊的兩個(gè)節(jié)點(diǎn)之間產(chǎn)生連接的可能性，預(yù)測(cè)過(guò)程實(shí)際上是一種數(shù)據(jù)挖掘的過(guò)程?？紤]到計(jì)算復(fù)雜度以及預(yù)測(cè)效果等因素，基于網(wǎng)絡(luò)結(jié)構(gòu)相似性的方法被廣泛運(yùn)用到鏈路預(yù)測(cè)中，因此本文采用基于局部信息的相似性指標(biāo)進(jìn)行預(yù)測(cè)(包括共同鄰居指數(shù)，Jaccard指數(shù)，Salton指數(shù))，文獻(xiàn)[13]給出了多種相似性指標(biāo)?？紤]到社會(huì)信任關(guān)系網(wǎng)絡(luò)是有向圖，節(jié)點(diǎn)相似度計(jì)算公式如下:

共同鄰居指數(shù)：

Jaccard指數(shù)：

Salton指數(shù)：

其中，x和y表示社會(huì)信任網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)，Γout(x)和Γin(x)分別表示從節(jié)點(diǎn)x指向鄰居節(jié)點(diǎn)和從鄰居節(jié)點(diǎn)指向節(jié)點(diǎn)x的節(jié)點(diǎn)集合，kout(x)和kin(x)分別表示節(jié)點(diǎn)x的出度和入度，k為歸一化因子。

1.4 張量CP分解

(1)

1.5 協(xié)同主題回歸模型

協(xié)同主題回歸(CTR)模型是由Wang等人[14]提出的一種基于概率主題模型的協(xié)同過(guò)濾方法。Purushotham等人[15]將CTR模型與社會(huì)關(guān)系相結(jié)合來(lái)提升推薦效果。CTR模型將傳統(tǒng)的協(xié)同過(guò)濾方法與主題模型相結(jié)合，假設(shè)LDA模型生成K個(gè)主題，CTR的生成過(guò)程如下所示：

(1)對(duì)于每個(gè)用戶i，其潛在特征向量

(2)對(duì)于每個(gè)物品j：

a.主題后驗(yàn)參數(shù)θj～Dirichlet(α)；

c.對(duì)于每個(gè)單詞，生成的主題zjn～Mult(θ)，單詞wjn～Mult(βzjn)；

2 基于隱含信任關(guān)系的概率張量分解推薦算法

2.1 概率張量分解

概率張量分解(PTF)可以看作是對(duì)PMF的一個(gè)推廣。由1.4節(jié)可知，一個(gè)N階張量χ可以通過(guò)CP分解得到N個(gè)因子矩陣U(1),…,U(N)。類似PMF，假設(shè)N個(gè)因子矩陣服從高斯分布，張量χ和近似張量χ′服從高斯分布。根據(jù)貝葉斯推理，通過(guò)最小化如下目標(biāo)函數(shù)來(lái)求解因子矩陣U(i),如式(2)。

(2)

2.2 用戶隱含信任關(guān)系

現(xiàn)有的推薦算法只考慮了用戶之間的直接信任關(guān)系對(duì)推薦性能的影響，而忽視了用戶之間的隱含信任關(guān)系，本節(jié)給出尋找用戶隱含信任關(guān)系算法的偽代碼：

算法1:用戶隱含信任關(guān)系預(yù)測(cè)輸入:有向社會(huì)信任網(wǎng)絡(luò)圖對(duì)應(yīng)的信任矩陣M,用戶數(shù)量U,選擇概率P輸出:用戶隱含信任關(guān)系矩陣N對(duì)于每個(gè)用戶u: 找出用戶的間接朋友節(jié)點(diǎn)(即用戶沒(méi)有直接指向的節(jié)點(diǎn)) 對(duì)于每個(gè)用戶u: 對(duì)于用戶u的每個(gè)間接朋友v: 利用1.3節(jié)中的相似度公式計(jì)算用戶u與其間接朋友的相似度S 如果S>P,則將Nuv置為S;否則將Nuv置為0 返回N

得到用戶隱含信任關(guān)系后，用戶潛在特征矩陣U(i)包含3個(gè)部分：用戶正則化項(xiàng)、用戶直接信任關(guān)系、用戶隱含信任關(guān)系。

2.3 提出的算法模型

由于考慮了用戶之間的隱含信任關(guān)系，CTR中的用戶潛在特征向量Ui～p(U)，如式(3)。

(3)

根據(jù)1.5節(jié)描述的CTR模型可知，物品潛在特征向量Vj是由物品內(nèi)容和物品偏置共同構(gòu)成的，可表示為式(4)。

(4)

根據(jù)2.1節(jié)可知通過(guò)概率張量分解得到的因子矩陣服從高斯分布且該張量也服從高斯分布，因此上下文特征向量可表示為式(5)。

(5)

如圖1所示。

圖1 融入隱含信任關(guān)系的PTF推薦算法模型

根據(jù)貝葉斯推理，我們提出的算法模型的后驗(yàn)分布為式(6)。

(6)

2.4 參數(shù)學(xué)習(xí)

為了求上式的后驗(yàn)概率最大值，通過(guò)對(duì)式(6)求對(duì)數(shù)，可以得到式(7)。

(7)

λf*∑f∈Ni*Tif*(Ui-Uf*)

(8)

(9)

(10)

給定U，V和C(1)…C(m)，采用EM算法來(lái)估計(jì)參數(shù)θj。設(shè)q(zjn=k)=Φjnk，將上述目標(biāo)函數(shù)中包含θj的項(xiàng)分離出來(lái)，利用Jensen不等式得到式(11)。

(11)

L(θj,Φj)是L(θj)的下界，將L(θj,Φj)不斷逼近L(θj)從而得到最優(yōu)解，可以采用梯度投影法來(lái)優(yōu)化θj。

得到U，V，C，θ，Φ后，可以通過(guò)下式來(lái)優(yōu)化β為式(12)。

βkw∝∑j∑nΦjnk1[wjn=w]

(12)

2.5 相關(guān)工作比較

矩陣分解技術(shù)已經(jīng)成功運(yùn)用于各類推薦算法中。通過(guò)對(duì)用戶的評(píng)分矩陣進(jìn)行分解來(lái)預(yù)測(cè)未評(píng)分物品的分?jǐn)?shù)，根據(jù)分?jǐn)?shù)的高低生成最終的推薦結(jié)果。文獻(xiàn)[6]從概率的角度對(duì)用戶的評(píng)分矩陣進(jìn)行分解，提出PMF模型，該方法對(duì)于稀疏數(shù)據(jù)集有很好的性能，但是PMF方法沒(méi)有充分利用用戶之間的信任關(guān)系，因此文獻(xiàn)[3]給出一種基于用戶信任關(guān)系的推薦算法，在矩陣分解過(guò)程中加入用戶信任關(guān)系進(jìn)行推薦。雖然該方法在一定程度上可以提高推薦效率，但是并沒(méi)有考慮上下文對(duì)用戶評(píng)分的影響；文獻(xiàn)[4-5]提出一種上下文感知的推薦算法，首先利用上下文運(yùn)用分類或聚類算法對(duì)數(shù)據(jù)進(jìn)行分塊，再對(duì)每個(gè)分塊的數(shù)據(jù)進(jìn)行矩陣分解，這種方法雖然加入了上下文對(duì)評(píng)分的影響，但是并沒(méi)有讓上下文參與分解過(guò)程，并不能體現(xiàn)上下文在推薦上的優(yōu)勢(shì)。因此本文在矩陣分解的基礎(chǔ)上進(jìn)行推廣，結(jié)合上下文將用戶評(píng)分?jǐn)?shù)據(jù)用張量表示，并在張量分解的過(guò)程中利用用戶之間的直接信任關(guān)系以及隱含信任關(guān)系來(lái)提升推薦效果。

3 實(shí)驗(yàn)結(jié)果及分析

3.1 數(shù)據(jù)集

本文實(shí)驗(yàn)使用的數(shù)據(jù)集為Epinions數(shù)據(jù)集，我們從Epinions數(shù)據(jù)集中挑選2 784名用戶對(duì)25 626個(gè)商品的評(píng)分?jǐn)?shù)據(jù)，其中包括47 434條評(píng)分記錄以及33 282條直接信任關(guān)系，利用2.2節(jié)中的算法1預(yù)測(cè)出346 567條隱含信任關(guān)系，并選取物品評(píng)分的平均值作為上下文構(gòu)建張量參與計(jì)算。通過(guò)隨機(jī)采樣的方法進(jìn)行實(shí)驗(yàn)。

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

采用文獻(xiàn)[4]提出的SoCo算法和文獻(xiàn)[5]提出的C-CTR-SMF2算法與本文提出的基于隱含信任關(guān)系的概率張量分解推薦算法(ITR-PTF)進(jìn)行比較,采用MAE、RMSE來(lái)衡量預(yù)測(cè)誤差，采用F1值來(lái)衡量推薦質(zhì)量。

實(shí)驗(yàn)中，選取主題數(shù)量K=100，潛在特征矩陣維度D=30。SoCo算法中設(shè)置參數(shù)λ=0.1，α=0.01時(shí)能夠達(dá)到最好性能；C-CTR-SMF2算法設(shè)置參數(shù)D=30，λU=0.01,λf=0.01，λV=1時(shí)能達(dá)到最好性能；本文提出的ITR-TF算法設(shè)置參數(shù)D=30，λU=λf=λf*=0.01，λC=λV=1。不同算法的MAE和RMSE對(duì)比結(jié)果，如表1所示。

表1 不同算法性能對(duì)比

不同算法進(jìn)行topN推薦時(shí)F1值變化,如圖2所示。

圖2 不同算法F1值對(duì)比

圖2表明推薦3-5個(gè)物品時(shí)推薦性能較好。從表1中可以看出C-CTR-SMF2算法的MAE、RMSE值小于SoCo算法，F(xiàn)1@5值大于SoCo算法，表明C-CTR-SMF2算法推薦效果優(yōu)于SoCo算法，這是因?yàn)镃-CTR-SMF2算法不僅結(jié)合了上下文信息以及信任關(guān)系，還利用CTR模型對(duì)物品內(nèi)容進(jìn)行建模。本文提出的ITR-PTF算法推薦效果優(yōu)于C-CTR-SMF2算法，因?yàn)橄啾菴-CTR-SMF2算法，ITR-PTF算法將上下文信息融入到構(gòu)建的模型中，利用上下文構(gòu)建張量并將用戶的隱含信任關(guān)系加入到張量分解過(guò)程中，充分利用上下文以及用戶信任關(guān)系來(lái)提高推薦的性能。

4 總結(jié)

本文提出了一種基于隱含信任關(guān)系的概率張量分解推薦算法，首先利用上下文構(gòu)建用戶在上下文中的評(píng)分張量，同時(shí)根據(jù)LDA模型結(jié)合物品內(nèi)容對(duì)物品進(jìn)行解釋，其次考慮了用戶直接信任關(guān)系的同時(shí)還考慮了用戶的隱含信任關(guān)系對(duì)推薦性能的影響，最終在傳統(tǒng)的推薦方法中加入上下文、用戶信任關(guān)系、物品內(nèi)容構(gòu)建推薦模型。實(shí)驗(yàn)結(jié)果表明，本文所提出的算法可以從一定程度上緩解數(shù)據(jù)的稀疏性問(wèn)題，并且具有更高的準(zhǔn)確率。

[1] Adomavicius G, and Tuzhilin A. Toward the next Generation of Recommender Systems: A Survey of the State-of-the-Art and Possible Extensions[J]. IEEE Transactions on Knowledge & Data Engineering, 2005, 17(6): 734-749.

[2] Ma H, Zhou D Y, et al. Recommender Systems with Social Regularization[C]//Forth International Conference on Web Search & Web Data Mining. Hong Kong, 2011: 287-296.

[3] Ma H, King I, Lyu M R. Learning to recommend with social trust ensemble[C]//International ACM SIGIR Conference on Research and Development in Information Retrieval. Boston, 2009: 2003-210.

[4] Liu X, Aberer K. SoCo: A Social Network Aided Context-Aware Recommender System[C]//International Conference on World Wide Web. Rio de Janeiro, 2013: 781-802.

[5] Chen C, Zheng X, Wang Y, et al. Context-Aware Collaborative Topic Regression with Social Ma- trix Factorization for Recommender Systems[J]. Palo Alto California Aaai Press, 2014, 3(3): 239-242.

[6] Salakhutdinov R, Mnih A. Probabilistic matrix factorization[C]//International Conference on Machine Learning, Edinburgh, 2012: 880-887.

[7] Matrix and Tensor Factorization Techniques for Recommender System[M]. Springer Internatio- nal Publishing,2016.

[8] Luan W J, and Jiang C J.Collaborative Tensor Factorizaiton and its Application in POI recommendation[C]//IEEE 13th International Conference on Network, Sensing, and Control, Mexico City, 2016.

[9] Tan H C, Feng G D, et al. A tensor-based method for missing traffic data completion[J]. Transp- ortation Research (Part C), 2013, 28: 15-27.

[10] Zhao S, Lyu M R, King I. Aggregated Temporal Tens-or Factorization Model for Point-of-intrest Recommendation [M]. Neural Information processing. America: Springer International Publishing, 2016.

[11] Frolov E, Oseledets I. Tensor Methods and Recommender Systems[J]. Computer Science, Cornell University Library, arXiv: 1603.06038, 19 Mar 2016.

[12] Kolda T G, Bader B W. Tensor Decompositions and Applications[J]. Siam Review, 2009, 51(3): 455-500.

[13] Martinez V, Berzal F, et al. A Survey of Link Prediction in Complex Networks[J]. ACM Computing Surveys, University of Granada, 2016, 49(4):1-33.

[14] Wang C, Blei D M. Collaborative topic modeling for recommending scientific articles[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Diego, 2011: 448-456.

[15] Purushotham S, Liu Y, Kuo C C J. Collaborative Topic Regression with Social Matrix Factorization for Recommendation Systems[C]//Proceedings of the 29th International Conference on Machine Learning. Edinburgh, UK, 2012.