郭磊，吳清壽

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

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

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

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

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

1 用戶隱含信任度計算

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

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

后驗概率分布為:

損失函數如下:

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

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

2 社區(qū)發(fā)現

用戶的偏好受到其好友的直接或者間接影響，采用社區(qū)發(fā)現算法將用戶根據其社交網絡結構進行劃分，即能更準確反應用戶間的影響力關系，又能提升在大數據量背景上的推薦效率。

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

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

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

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

其中:V 是網絡G 中節(jié)點集合。

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

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

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

定義5 朋友圈由core 與N(core)構成。對于ν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)。

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

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

2.2 層次社區(qū)構建

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

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

定義8 朋友圈連接強度。朋友圈連接強度定義為:

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

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

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

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

一棵HCT 對應一個社區(qū)，逐個加入HCT 中的朋友圈將構成社區(qū)的層次結構。

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

3 預測評分與推薦

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

4 結果與實驗分析

4.1 數據集

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

4.2 評價指標

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

4.3 實驗分析

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

4.3.1 參數對算法影響

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

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

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

4.3.2 算法與相關方法對比

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

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

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

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

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

圖2 各算法MAE 指標比較Fig.2 Comparison of Mae indices for each algorithm

圖3 各算法RMSE 指標比較Fig.3 Comparison of RMSE indices of each algorithm

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

5 結語

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