融合隱式信任與層次社區(qū)發(fā)現(xiàn)的協(xié)同過濾推薦算法

郭磊，吳清壽

（1.武夷學(xué)院 數(shù)學(xué)與計算機(jī)學(xué)院 福建 武夷山 354300；2.福建省茶產(chǎn)業(yè)大數(shù)據(jù)應(yīng)用與智能化重點實驗室，福建 武夷山 354300）

在信息爆炸的時代，網(wǎng)絡(luò)上數(shù)據(jù)爆炸式增長，導(dǎo)致用戶難以發(fā)現(xiàn)自己感興趣的內(nèi)容，這就是信息過載問題，推薦系統(tǒng)被認(rèn)為是解決信息過載的一種有效方法[1-2]。推薦算法根據(jù)策略可以分為基于內(nèi)容的推薦算法、基于協(xié)同過濾推薦算法和基于混合式推薦算法。而基于協(xié)同過濾的方法[3]由于其有效性與可擴(kuò)展性得到廣泛應(yīng)用[4]。但隨著數(shù)據(jù)量的增加以及數(shù)據(jù)的多樣性，推薦系統(tǒng)長期面臨數(shù)據(jù)稀疏問題，緩解此類問題通常是采用的方法是在通過使用用戶與物品之間的內(nèi)容信息，如社交網(wǎng)絡(luò)信息、時間信息、位置信息等來構(gòu)建混合式推薦算法，提高推薦精度[5]。同時，傳統(tǒng)推薦算法面對海量數(shù)據(jù)效率較差，于是一些基于聚類的算法被提出，如K 均值聚類、模糊C 均值方法與自組織映射聚類[6-7]，這些方法不但可以緩解數(shù)據(jù)稀疏性，還可以以改善推薦系統(tǒng)的可擴(kuò)展性。

社交網(wǎng)絡(luò)信息比其他輔助信息更能挖掘潛在的用戶價值，因此大量基于社交網(wǎng)絡(luò)的算法被提出[8-11]。常用方法是采用信任評估模型對用戶間的直接信任關(guān)系進(jìn)行計算，用于改善推薦精度，如基于信任總體的RSTE[12]，基于信任傳播的Social MF 等[13]，均取得一定成效。隨后研究人員開始研究間接信任關(guān)系，如Yuan 等用評分興趣相似度作為隱式信任關(guān)系進(jìn)行推薦[14]，Azadjalal 等提出融合帕累托和置信度的信任推薦算法[15]，但以上算法均沒有考慮不對稱信任的問題，且此類算法面向大數(shù)據(jù)集時推薦效果不佳。

為解決大數(shù)據(jù)量下推薦精度和效率提升的問題，基于聚類的推薦算法被提出，如K 均值聚類，模糊C均值方法等[16]。Koohi 等將模糊C-means 聚類方法應(yīng)用到推薦算法中，根據(jù)用戶所屬類別，搜索與用戶隸屬程度高的鄰居用戶，從而形成興趣最為相似的用戶社區(qū)[17]。Ahmadian 等提出一種基于自適應(yīng)鄰居選擇機(jī)制的社會推薦算法ARANS[18]。Li 等將重疊社區(qū)發(fā)現(xiàn)與推薦算法結(jié)合，計算用戶之間的相識度和用戶與社區(qū)的相關(guān)度，使用間接社交關(guān)系提升推薦效果[19]。Jianrui Chen 等提出一種基于用戶相關(guān)性和進(jìn)化聚類的推薦算法UCEC&CF[20]，可以提高算法效率與評分預(yù)測準(zhǔn)確性。但以上算法針對單個用戶進(jìn)行處理，提出的方法雖然能緩解一定的數(shù)據(jù)稀疏性，但對推薦性能提升有限。

提出一種融合社區(qū)結(jié)構(gòu)與用戶隱含信任度的協(xié)同過濾推薦算法(CSIT-CF)。算法首先采用基于信任矩陣挖掘用戶做為信任與被信任的非對稱關(guān)系，計算用戶隱含信任度，并結(jié)合隱含信任度進(jìn)行用戶社區(qū)發(fā)現(xiàn)，最后在社區(qū)內(nèi)計算目標(biāo)用戶對項目的預(yù)測評分并形成推薦。算法在保持一定推薦效率的同時，緩解傳統(tǒng)協(xié)同過濾算法數(shù)據(jù)稀疏性問題，提升推薦精度。

1 用戶隱含信任度計算

將信任關(guān)系引入推薦系統(tǒng)，能夠顯著提高推薦效果。在信任網(wǎng)絡(luò)中，每個用戶均有信任與被信任兩種角色，擔(dān)任不同角色的評分不盡相同，因此在進(jìn)行信任計算時，同時考慮兩種角色的情況更加合理。為更好的挖掘信任矩陣中的隱含的信任關(guān)系，提出一種融合信任與被信任的非對稱隱含信任度計算方法。

首先對信任矩陣T 采用概率矩陣分解的方法進(jìn)行分解，假設(shè)T 由信任矩陣Rzk×n與被信任矩陣Rpk×n正態(tài)分布生成，則其條件概率分布表示為:

后驗概率分布為:

損失函數(shù)如下:

對損失函數(shù)使用梯度下降法可求得Rz 和Rp。根據(jù)所得的兩個向量，可計算兩用戶之間的信任相似度與被信任相似度，采用皮爾遜相關(guān)系數(shù)來計算其相似度。兩用戶的信任相似度計算公式為:

將以上兩種相似度按照一定比例加和可得用戶隱含信任度。使用權(quán)值α∈（0,1）來調(diào)整二者比例，具體計算如公式（8）所示:

2 社區(qū)發(fā)現(xiàn)

用戶的偏好受到其好友的直接或者間接影響，采用社區(qū)發(fā)現(xiàn)算法將用戶根據(jù)其社交網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行劃分，即能更準(zhǔn)確反應(yīng)用戶間的影響力關(guān)系，又能提升在大數(shù)據(jù)量背景上的推薦效率。

采用的社區(qū)發(fā)現(xiàn)算法的主要思想:根據(jù)節(jié)點的重要性選擇核心節(jié)點，將核心節(jié)點與其鄰居節(jié)點組織為朋友圈。判斷朋友圈的獨立性，若存在不滿足獨立性的朋友圈，根據(jù)朋友圈相似度將其合并到最相似的相鄰朋友圈，下面對相關(guān)定義及算法進(jìn)行描述。

2.1 核心節(jié)點發(fā)現(xiàn)與朋友圈識別

定義1 節(jié)點影響力。用LeaderRank 算法[21-23]計算節(jié)點的lr 值，節(jié)點νi對應(yīng)的lr 值表示節(jié)點在網(wǎng)絡(luò)中的影響力，記為lri.

將節(jié)點按照lr 值非升序排列，用VLR 表示已排序節(jié)點結(jié)合:

其中:V 是網(wǎng)絡(luò)G 中節(jié)點集合。

定義2 νi的鄰居節(jié)點記為N（i）={νj│i?j}，νi鄰域記為Nh（i）=N（i）∪νi。

定義3 朋友圈核心節(jié)點選擇規(guī)則。初始時，從VLR 中選擇第一個節(jié)點為核心節(jié)點，記為core。用core 構(gòu)建朋友圈，并將該朋友圈所有節(jié)點從VLR 中刪除；從剩余節(jié)點中選擇第一個節(jié)點為下一個core，繼續(xù)構(gòu)建朋友圈。重復(fù)以上過程，直到VLR 為空。以上每次選擇的節(jié)點core 稱為朋友圈核心節(jié)點。

定義4 核心節(jié)點與鄰居節(jié)點的相似度記為Seccore，x，定義為:

定義5 朋友圈由core 與N(core)構(gòu)成。對于νx∈N(core)，若Seccore，x≥α，將νx加入core 所在的朋友圈，朋友圈定義為:

Fr(core)={x | x∈N(core) ∧Seccore，x≥α }∪core (11)

定義6 相鄰朋友圈。對于?νy∈N(core)，若νy?Fr(core)，則νy所屬的朋友圈稱為Fr(core)的相鄰朋友圈，記為NFk。NFk集合記為NFr(core)。

根據(jù)上述思路，得到朋友圈識別算法如下:

ConsFr 算法中，第3 行將VLR 中的第一個節(jié)點設(shè)置為核心節(jié)點，第7～10 行對core 的鄰居節(jié)點進(jìn)行判斷，將滿足的節(jié)點加入core 所在的朋友圈，并將其從VLR 中刪除。重復(fù)上述過程，最終得到朋友圈核心節(jié)點集合Lcore 和對應(yīng)的朋友圈Fr。

2.2 層次社區(qū)構(gòu)建

朋友圈是用于構(gòu)建層次聚類樹(hierarchical clustering tree，HCT)的基礎(chǔ)單元[25-26]。構(gòu)建HCT 需要判斷朋友圈的獨立性，若一個朋友圈滿足獨立性條件，則該朋友圈將作為HCT 的根節(jié)點，否則，將該朋友圈鏈接到相似度最大的HCT 中。因為候選核心節(jié)點按照lr值非升序排列，一般情況下，其對應(yīng)的朋友圈包含的節(jié)點數(shù)量總體上也呈現(xiàn)出按大到小排列的趨勢，且排名靠前的朋友圈滿足獨立性的概率更大。按照朋友圈形成的順序構(gòu)建HCT，能更快的找到具備獨立性的根節(jié)點，有利于后續(xù)HCT 的構(gòu)建。

若Idpcore＞β，表示該朋友圈滿足獨立性要求，可作為HCT 的根節(jié)點，否則將其鏈接到最相似的HCT 或者其他朋友圈。因為朋友圈之間不存在共同節(jié)點，需要通過朋友圈之間邊的相關(guān)性判斷朋友圈的相似度。對于滿足i?j 的節(jié)點，若νj∈Fr(core)并且νi?Fr(core)，將νi稱為朋友圈鄰居節(jié)點。

定義8 朋友圈連接強(qiáng)度。朋友圈連接強(qiáng)度定義為:

朋友圈連接強(qiáng)度統(tǒng)計Fr(core)鄰居節(jié)點歸屬于相鄰朋友圈的情況。

定義9 朋友圈相似度用于衡量NFr (core) 中與Fr(core)最相似的朋友圈，定義如式(14):

Thrcore是與Fr(core)最相似朋友圈的索引，用Fr(Thr)表示Thrcore對應(yīng)的朋友圈。

定義10 HCT 構(gòu)建規(guī)則。若Idpcore＞β，其對應(yīng)的Fr (core) 作為一棵新的HCT 的根節(jié)點，且其對應(yīng)的core 是當(dāng)前社區(qū)的核心節(jié)點;否則，計算第三階結(jié)構(gòu)，得到Fr(Thr)，若Fr(Thr)已加入某HCT，將Fr(core)加入該HCT，否則，將Fr(core)與Fr(Thr)合并。

一棵HCT 對應(yīng)一個社區(qū)，逐個加入HCT 中的朋友圈將構(gòu)成社區(qū)的層次結(jié)構(gòu)。

算法2 中，find()函數(shù)用于查找當(dāng)前朋友圈要加入的目標(biāo)HCT，update () 方法將HCT 的變動更新到HCTs 中。

3 預(yù)測評分與推薦

通過用戶社區(qū)劃分，可以得到目標(biāo)用戶ui的鄰居用戶集合，取用戶隱含信任度最高的前K 個做為用戶近鄰集合s(i)參與運算。通過對用戶ui的鄰居用戶對物品z 的評分進(jìn)行加權(quán)求和，得到最終的預(yù)測得分。

4 結(jié)果與實驗分析

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

為驗證算法效果，使用公開的電影評分?jǐn)?shù)據(jù)集FilmTrust 進(jìn)行驗證。該數(shù)據(jù)集包含1 508 名用戶對2 071 個電影項目的評分，共計35 497 條評分?jǐn)?shù)據(jù)，評分范圍為0.5～4.5，評分?jǐn)?shù)據(jù)密度為1.044%，以及1 853 條信任數(shù)據(jù)，信任值為二值信任，數(shù)據(jù)密度為0.069%。

4.2 評價指標(biāo)

為衡量方法的性能，采用平均絕對誤差(MAE)，均方根誤差（RMSE）作為評估指標(biāo)。假設(shè)推薦算法預(yù)測用戶評分集為PS，用戶真實評分集為TS，Nrs為測試集中推薦列表長度，N 為訓(xùn)練集得到推薦列表長度，則3 項評價指標(biāo)的定義表達(dá)式為:

4.3 實驗分析

實驗選取數(shù)據(jù)集中的80%作為訓(xùn)練集，20%作為測試集，采用不同的劃分進(jìn)行10 重交叉驗證，結(jié)果取平均值，對模型有效性進(jìn)行驗證，在后文圖中用CSTCF 表示本文算法。

4.3.1 參數(shù)對算法影響

由于在信任相似度計算采用的是加權(quán)的方法，不同權(quán)值對推薦準(zhǔn)確度可能會產(chǎn)生較大影響，故通過實驗來探索不同α 對實驗結(jié)果的影響。實驗對α 值在[0，1]區(qū)間，以0.1 為步長進(jìn)行實驗。

分析圖1 可知，首先，當(dāng)α 值向中心部分靠近，即兩種相似度進(jìn)行結(jié)合時，MAE 值獲得顯著下降，說明兩種相識度的混合能夠有效提升推薦效率，其次，當(dāng)α=0.4 時，MAE 取得算法最優(yōu)值，故本實驗將0.4 作為α 的默認(rèn)值。

圖1 不同α 值得實驗效果Fig.1 Different α are worthy of experimental effect

4.3.2 算法與相關(guān)方法對比

為驗證本算法性能，在相同條件下，將本文算法與以下3 種算法進(jìn)行對比:

1）Social MF[13]。該算法利用直接社交關(guān)系，使用好友信息與信任傳播機(jī)制來對用戶特征矩陣進(jìn)行優(yōu)化。

2）Trust MF[27]。該算法對評分矩陣和社交矩陣進(jìn)行同步分解，同時將用戶信任關(guān)系映射為信任者和被信任者兩個特征向量來增強(qiáng)推薦效果。

3）UCEC&CF[24]。該算法對分?jǐn)?shù)矩陣進(jìn)行修正與動態(tài)進(jìn)化聚類，同時參考用戶興趣度量用戶相關(guān)性，最后在用戶組內(nèi)進(jìn)行推薦。

本文算法與Social MF、Trust MF、UCEC&CF 三種算法在數(shù)據(jù)集、實驗環(huán)境相同的條件下的推薦效果對比如圖2、圖3 所示。

圖2 各算法MAE 指標(biāo)比較Fig.2 Comparison of Mae indices for each algorithm

圖3 各算法RMSE 指標(biāo)比較Fig.3 Comparison of RMSE indices of each algorithm

通過對圖2、圖3 的分析可以發(fā)現(xiàn)，與其他算法相比較，本文算法在MAE 和RMSE 均有明顯下降，推薦效果更加，分析原因，Social MF 只考慮直接社交網(wǎng)絡(luò)信息，后面三種算法同時使用評分信息和社交網(wǎng)絡(luò)信息對用戶間的影響力進(jìn)行混合計算，因此推薦準(zhǔn)確度明顯提高，說明評分信息和社交網(wǎng)絡(luò)信息綜合能夠更準(zhǔn)確刻畫用戶間的影響；Trust MF 結(jié)合個人影響力計算用戶間非對稱影響力，相比于沒有考慮非對稱影響力的Social MF 算法，推薦效果更好，說明綜合非對稱影響力因素能夠取得更好的推薦效果；UCEC&CF 使用動態(tài)聚類，推薦效果優(yōu)于不考慮聚類的Social MF、TrustMF，表明聚類能夠更加有效的利用用戶的社交關(guān)系；本文算法計算用戶間非對稱社交關(guān)系，利用信任信息進(jìn)行社區(qū)劃分，更加準(zhǔn)確刻畫用戶間影響力的同時，一定程度緩解用戶間社交稀疏的問題，因此整體上獲得更好的推薦效果。

5 結(jié)語

在傳統(tǒng)協(xié)同過濾推薦算法的基礎(chǔ)上，提出一種融合用戶的社區(qū)結(jié)構(gòu)與隱含信任度的協(xié)同過濾推薦算法。該算法將信任關(guān)系分解為信任和被信任兩種非對稱關(guān)系，計算用戶隱含信任度，并依此進(jìn)行用戶社區(qū)發(fā)現(xiàn)，更準(zhǔn)確的發(fā)現(xiàn)用戶間的影響力關(guān)系，最后結(jié)合用戶評分計算目標(biāo)用戶的預(yù)測評分并形成推薦。在當(dāng)前研究中，主要考慮用戶的靜態(tài)社交關(guān)系，但隨著時間的推移，用戶社交關(guān)系會不斷變化，導(dǎo)致推薦結(jié)果準(zhǔn)確度下降，未來將考慮在動態(tài)場景下的協(xié)同過濾推薦算法。