基于用戶模糊聚類的綜合信任推薦算法

賈俊杰，張玉超

（西北師范大學計算機科學與工程學院，蘭州 730070）

0 概述

隨著互聯網技術的快速發展，全球信息數據量呈現爆炸式增長，使得互聯網上的用戶難以在海量信息數據中選擇有用和重要的信息。推薦系統通過收集分析用戶的歷史偏好數據向用戶提供更多的個性化信息，其中協同過濾推薦是一種應用比較廣泛的個性化推薦算法［1］，該算法的目標是尋找與目標用戶具有相似興趣愛好的其他用戶，并通過這些用戶的項目體驗感受來對目標用戶所未體驗過的項目進行預測。針對協同過濾推薦算法存在的數據稀疏［2］和冷啟動問題［3］，研究人員提出了很多解決方案來提高推薦精度［4］。一方面，采用基于信息數據的聚類算法解決評分數據不足的問題，其中基于用戶間信任的推薦系統旨在利用用戶間的信任數據對用戶缺失的評分數據進行補充，提高推薦性能［5-7］。另一方面，通過基于聚類的推薦算法緩解評分數據稀疏問題，其主要思想是將偏好差異較小的用戶分為同一類別，偏好差異較大的用戶分為不同類別，在推薦時選擇與目標用戶同屬一個類別中的其他用戶為推薦用戶，可在不同程度上緩解數據稀疏問題，因此選擇合適的聚類算法對推薦系統的推薦性能非常關鍵。本文主要研究用戶間信任關系對推薦效果的影響，通過對信任數據、評分數據進行建模得到用戶顯式信任、隱式信任和全局信任，并將信任機制融入模糊C 均值（Fuzzy C-Means，FCM）聚類算法中以提升推薦質量。

1 相關工作

由于信任是用戶產生決策的重要影響因素，因此基于用戶信任關系的推薦系統得到廣泛應用，目標用戶將信任用戶所推薦的內容作為決策影響因素之一［8］。融合社交網絡的推薦系統通常將基于用戶的協同過濾算法與信任模型相結合，不僅能夠有效緩解傳統協同過濾推薦算法中的數據稀疏和冷啟動問題，而且能提高推薦結果的準確率和覆蓋率［9］。融合用戶之間的信任關系有利于提升推薦系統的性能，可有效防止惡意影響推薦精度的行為。

在基于社交網絡的推薦算法中主要包括顯式和隱式兩種類型的信任關系，它們分別通過用戶之間建立的社交網站收集得到［10］以及用戶-項目評分數據推斷得到。文獻［11］利用用戶間的信任數據取代傳統協同過濾中的興趣相似度進行推薦，其為典型的顯式信任推薦模型，但由于未設置相應的信任傳播閾值，因此使得大量不可信的信任路徑得到保留。文獻［12］將用戶間的評分興趣相似度作為隱式信任關系代替興趣相似度進行協同過濾推薦，其為典型的隱式信任推薦模型，但忽略了隨著時間的推移用戶間信任關系的變化。近年來，研究人員在推薦系統中提出了一些顯式信任與隱式信任混合模型。文獻［7］提出利用二分圖和隱式信任來預測用戶偏好，通過用戶間的信任關系取代用戶興趣相似度進行協同過濾推薦。文獻［13］提出基于信任的矩陣分解算法TrustSVD，該算法不僅考慮了用戶間信任數據和評分數據的顯性影響，同時考慮了用戶間的隱性影響。文獻［5］提出一種融合Pareto 和置信度的信任推薦系統，當用戶間顯式數據過于稀疏時，利用用戶間的項目評分數據進行補充，從而提高推薦系統的準確性。文獻［14］所提出的算法考慮了信任的動態變化，將融合時間衰減函數的皮爾森評分相似度作為用戶間隱式信任值，主要對信任傳遞進行了研究，但未充分挖掘評分數據中隱含的用戶間信任關系。

協同過濾推薦算法適合運行在小型數據集中，并且運行效果較好，但現實生活中用戶-項目數據量太大，很難利用其對用戶進行準確推薦。為了解決這一問題，可在推薦系統中使用聚類算法將用戶-項目分成若干聚類，從而縮小推薦系統搜索相似用戶的范圍。若用戶被劃分到同一類別，則表示其興趣相似度較大，否則表示興趣相似度較小。在眾多聚類算法中，K-Means 是較為經典的聚類算法，每次對用戶進行聚類時，都只能分配到一個類別中。但實際上，在聚類完成時，每個類別中都有和目標用戶相似的用戶［15］，從而使得推薦結果精度降低。為了解決此類聚類問題，將模糊C-Means 聚類算法應用到推薦系統中［15］，根據用戶所屬類別的隸屬程度來確定用戶屬于一個或多個類別，從而獲得更大的搜索空間尋找興趣最為相似的用戶。文獻［16］為進一步提高文獻［15］所提算法的推薦質量，利用模糊C 均值聚類算法將用戶分成若干類別，采用傳統歐式距離加權化來獲得最佳聚類進行推薦。文獻［17］利用用戶評分過程中的潛在信任關系，提出一種基于信任機制的概率矩陣分解協同過濾推薦算法，通過構建用戶-信任評分矩陣提高推薦準確性。文獻［18］應用粒子群優化算法優化模糊C 均值聚類算法對用戶進行聚類，有效提高了推薦準確率。文獻［19］通過K-Means 聚類算法對用戶進行聚類，然后利用Slope One 算法對評分矩陣進行填充，有效緩解了數據稀疏問題。上述推薦算法都是利用用戶評分數據進行處理，而真實用戶評分數據集通常極度稀疏，導致推薦質量依然較低。

通過以上研究可知，推薦系統中引入信任機制可有效提升推薦效率，但上述推薦算法均未充分挖掘用戶間信任傳遞的關聯性，且未綜合考慮用戶全局信任對每個用戶信任關系的影響。由于用戶的信任關系僅針對一小部分用戶數據，因此無須浪費大量時間掃描全部用戶數據。本文提出基于模糊C 均值聚類的綜合信任推薦算法，旨在緩解數據稀疏與冷啟動問題的前提下縮減搜索目標用戶的最近鄰，并提高推薦質量。首先通過對用戶評分數據進行聚類，根據用戶隸屬情況得到用戶所屬類別，基于信任數據、評分數據計算所屬類別中用戶的顯式信任值、隱式信任值并得到綜合直接信任值；然后通過信任的可傳遞特性，獲取用戶間Jaccard 全局信任值；最后動態結合用戶間綜合直接信任與Jaccard 全局信任得到綜合信任值，將綜合信任值取代傳統推薦算法中的興趣相似度實現協同過濾推薦。

2 相關技術

本文主要通過用戶-評分矩陣獲得用戶的聚類類別，根據聚類類別計算用戶間的全局信任度，以此對用戶進行協同過濾推薦，其中主要包括用戶-項目構建、模糊C 均值聚類、近鄰形成和評分預測4 個部分。

2.1 用戶-項目評分矩陣構建

在推薦系統中，用戶-項目評分數據是由n個用戶和m個項目（音樂、書籍、商品等）所組成的n×m維的矩陣，其中，用戶集合U=(u1,u2,…,un)，項目集合I=(i1,i2,…,im)，un表示用戶集合中第n個用戶，im表示項目集合中第m個項目。用戶對項目的評分為R=(ru1,i1,ru2,i2,…,run,im)，其中rij?[1,5]中的離散值，表示用戶ui對項目Ij的評分。本文中用戶評分缺失采用評分0 來代替。如果用戶對項目的評分為1，則表示用戶對該項目非常不感興趣，如果用戶對項目的評分為5，則表示用戶對該項目非常感興趣。評分項目矩陣如表1 所示。

表1 用戶-項目評分矩陣Table 1 User-project rating matrix

2.2 模糊C 均值聚類

基于用戶屬性向量對用戶進行聚類，即用戶-項目評分數據映射到n維向量上u=(r1,r2,…,rn)，對用戶屬性向量進行模糊C 均值聚類。模糊C 均值聚類算法［20］原理為根據隸屬度來表示樣本點屬于某個聚類的隸屬程度。將樣本集X={x1,x2,…,xn}中的每一個樣本點模糊劃分到K個聚類中，更新每個聚類中心ci(i=1,2,…,k)，并使得劃分代價損失函數達到最小值。劃分代價損失函數的計算公式為：

為使式（1）取得最小值，對聚類中心ci與隸屬度ui(xj)求偏導，得到損失函數取得最小值的必要條件如式（3）、式（4）所示。將必要條件通過迭代求解，得到聚類中心與樣本點的隸屬度矩陣。

算法1模糊C 均值聚類推薦算法

輸入 用戶-項目評分矩陣，聚類個數K，最近鄰個數N，目標用戶u

輸出 缺失項目預測評分

步驟1輸入用戶評分矩陣，根據用戶評分數據對用戶進行模糊C 均值聚類。

步驟2計算每個用戶對每個類別的隸屬度，根據用戶隸屬度對用戶進行聚類。

步驟3找到目標用戶所在聚類，同一類中用戶偏好相似度較高，不同類別中用戶相似度較低，計算目標用戶與類別中其他用戶的偏好相似度。找到與目標用戶相似度最高的K個用戶為目標用戶的最近鄰。

步驟4對所得目標用戶與最近鄰進行缺失項目的評分預測或top-N 推薦。

2.3 近鄰形成

協同過濾推薦算法的基本原理是通過分析挖掘目標的歷史評分數據，找到與其興趣偏好相似的用戶，并為目標用戶推薦未體驗過的商品和項目。換言之，通過目標用戶的歷史評分數據找到相似用戶，利用相似用戶為目標用戶進行推薦。度量用戶間相似性是推薦過程中的重要流程，與推薦精確度密切相關，其主要度量指標為皮爾森相關系數、余弦相似度和Jaccard 相似度等，其中皮爾森相關系數是一種較常用的相似性度量系數［21］，計算公式為：

其中，Iu,v表示用戶u和用戶v共同評分的項目，ru,i和rv,i分別表示用戶u和用戶v對項目i的評分。

2.4 評分預測

通過度量用戶間的興趣相似度可得到K個與用戶興趣最為相似的近鄰進行評分預測，評分預測公式為：

其中，ru,i表示目標用戶對缺失項目i的預測評分，表示目標用戶對所有評分項目的平均評分值，NNK(u,i)表示具有預測項目i的目標用戶的最近鄰集合，sim(u,v)表示用戶間的皮爾森相似度。

3 改進的模糊C 均值聚類推薦算法

模糊C 均值聚類推薦算法［15］運用聚類方法將興趣相似用戶劃分到相同類別中，并選擇與目標用戶同屬一個類別的其他用戶作為推薦用戶，以此來解決推薦系統中的數據稀疏與冷啟動問題，但在推薦系統中遇到絕對數據稀疏與冷啟動用戶時推薦效率依舊較低。因此，本文將用戶間信任機制融入該算法，進一步提高推薦效率。將協同過濾推薦算法中用戶之間的聯系拓展為用戶間綜合信任，其中：綜合信任關系包含用戶間顯式信任、隱式信任、綜合直接信任與Jaccard 全局信任，顯式信任關系由用戶間信任數據計算所得，隱式信任關系由用戶間評分數據所得，綜合信任關系是由顯式信任關系與隱式信任關系融合計算所得；Jaccard 全局信任是指用戶在整個推薦系統中的活躍強度，若用戶在推薦系統中越活躍，則獲得的Jaccard 全局信任度就越高。本文算法主要包含3 個階段：1）通過模糊C 均值聚類算法對用戶進行聚類；2）利用用戶信任數據和項目評分數據得到用戶間顯式信任值、隱式信任值及綜合直接信任值；3）由用戶間綜合直接信任值得到Jaccard 全局信任值，并加權結合Jaccard 全局信任關系組成綜合信任值進行協同過濾推薦。本文算法流程如圖1所示。

圖1 本文算法流程Fig.1 Procedure of the proposed algorithm

3.1 用戶間顯式信任

信任在宏觀上是指相信對方是誠實可信賴的，在推薦系統上的信任是指用戶對對方所體驗過的項目感興趣。若用戶之間存在顯式直接信任關系，則T(ui,uj)=1，表示用戶ui信任用戶uj，否則T(ui,uj)=0，表示用戶i沒有直接信任關系。用戶-用戶信任矩陣如表2 所示。

表2 用戶-用戶信任矩陣Table 2 User-user trust matrix

用戶間信任數據矩陣可使用有向圖G=(V,E)來表示，其中，V為信任網絡中的每個用戶節點，E為信任網絡中用戶節點之間的有向邊，表示用戶之間存在信任關系。

用戶信任網絡如圖2 所示，用戶u1與用戶u3之間有兩條有向邊，表示用戶之間相互信任。用戶u1與用戶u4之間有一條有向邊，表示用戶u1信任用戶u4，但用戶u4不信任u1。用戶信任網絡上的邊［22］可形象表示為。利用MASSA 等人［11］提出的信任計算方法計算用戶間的顯式信任值：

圖2 用戶信任網絡Fig.2 User trust network

其中，dui,uj表示用戶ui與用戶uj的最短信任傳播距離。例如，用戶u1與用戶u5沒有直接信任關系，但他們可以通過信任傳遞的方式獲取對彼此的信任，此時u1與u5的信任傳播距離為dmin(u1u2u6u5,u1u2u3u6u5,u1u2u3u5,u1u3u6u5,u1u3u5,u1u4u5)=3，dmax表示用戶間最大傳播距離［23］，計算公式為：

其中，n表示用戶信任網絡中用戶節點的總數，k表示用戶節點出入度的平均值。

3.2 用戶間隱式信任

本文算法利用用戶-項目評分數據、時間衰減函數綜合推斷出用戶間的隱式信任關系。本文采用LATHIA 等人［24］提出的信任計算模型來計算用戶間的隱式信任值，若用戶間有相同評分項目，則表示用戶互動一次，評分差異越小，用戶間越信任，而互動次數越多表示用戶信任程度越高，計算公式為：

其中，ru,i和rv,i表示用戶u與用戶v對項目i的評分，表示用戶間的可信度，|Iu|和|Iv|表示用戶u和用戶v對項目評分不為0 的數量，分子部分表示用戶間共同擁有評分不為0 的項目。用戶可信度越大，用戶的隱式信任程度越高。如圖3、圖4 所示，用戶u與用戶v共同擁有評分不為0 的項目5 項，但用戶u與用戶v之間的隱式信任程度不同，且隨著時間的推移，用戶間的隱式信任的衰減速度會由快到慢，最后無限趨于0。時間衰減函數［14，25］H的計算公式為：

圖3 互動程度相同的示例Fig.3 Example with the same degrees of interaction

圖4 互動程度不同的示例Fig.4 Example with the different degrees of interaction

其中，k為影響時間的衰減因子，T為當前時刻，t為用戶間的最后交互時刻，即用戶最后一次共同擁有不為0 評分項目的時刻。

3.3 用戶間綜合直接信任值計算

將用戶間顯式信任與隱式信任進行結合，得到用戶間綜合直接信任值，計算公式［26］為：

1.3.2 B組31例患兒給予多次胰島素皮下注射,患兒三餐前皮下注射短效胰島素,根據患兒血糖檢測情況適當調整胰島素注射用量,患兒睡前給予中效諾和靈注射。

綜合信任值由用戶間綜合直接信任值與Jaccard全局信任值組成，計算公式［27］為：

其中，α+β=1。

在聚類完成后，相同聚類中用戶間最為信任。通過結合用戶間綜合直接信任關系、全局信任關系得到用戶綜合信任值，并找到目標用戶所屬聚類中最為信任的K個用戶進行下一步處理。用戶間Jaccard 全局信任值計算如式（13）所示：

式（13）表示用戶u與用戶v所擁有的共同信任用戶越多（綜合直接信任值大于0.5），則用戶u和v間的全局信任值越高。

3.4 用戶-項目評分預測

通過在用戶所屬類別中找到與目標用戶綜合信任值最高的K個推薦用戶，利用用戶間綜合信任值取代傳統用戶間評分興趣相似度進行推薦。應用式（14）對目標用戶缺失項目評分進行預測［28］：

算法2基于模糊C 均值聚類的綜合信任推薦算法

輸入用戶-用戶信任矩陣，用戶-項目評分矩陣，目標用戶

步驟1根據用戶屬性向量，計算每個用戶對每個類別的隸屬度，根據用戶隸屬度進行聚類。

步驟2計算用戶間顯式信任值：

步驟3找到目標用戶所在聚類，計算目標用戶與類中其他用戶的隱式信任值。利用用戶間顯式信任值、隱式信任值得到綜合直接信任值，并采用綜合直接信值計算出用戶間Jaccard 全局信任值：

根據式（11）、式（13）計算用戶間綜合直接信任與全局信任值

步驟4將用戶間綜合直接信任值與Jaccard 全局信任值加權結合得到綜合信任。利用式（12）計算用戶間的綜合信任值Wu,v

步驟5將目標用戶與其他用戶的綜合信任值降序排序，選取前K個用戶為目標用戶的最近鄰集合Un，利用用戶間綜合信任值取代傳統協同過濾中的相似度進行缺失項目的評分預測及top-N 推薦。

利用式（14）對目標用戶未評分項目進行預測評分及top-N 推薦

4 實驗結果與分析

本節使用真實數據集并利用Python 語言實現本文算法，并在配置為Windows 7、2.50 GHz CPU 和8 GB 內存的計算機上進行實驗。

4.1 數據集

實驗使用FilmTrust 數據集（http：//www.trust.mindswap.org/FilmTrust/），該數據集抓取自FilmTrust網站，包括1 508 名用戶為2 071 部電影項目的評分情況，由評分數據ratings.txt和用戶信任數據trust.txt兩部分組成，其中：ratings.txt包含35 497條數據，評分范圍為0.5～4.0，步長為0.5，密集度為1.044%；trust.txt 包含1 853 條數據，密集度為0.069%。

4.2 評價指標

為檢驗本文算法的有效性，采用平均絕對誤差（MAE）、覆蓋率（COV）和綜合評價指標（F1）來評價推薦系統性能。平均絕對誤差是指推薦系統為用戶所推薦的商品評分與測試集中真實用戶商品評分之差的平均值，其值越小表示預測評分越準確，計算公式如式（15）所示。覆蓋率是指推薦系統能為用戶預測評分商品數量占測試集總商品數量的比值，其值越高，表示算法挖掘長尾商品的能力越強，計算公式如式（16）所示。F1值是指推薦系統綜合評價指標［28］，其值越高表示性能越好，計算公式如式（17）所示。

其中，ri為測試集中項目i的真實評分，rp為推薦系統為目標用戶的商品預測評分，|Lu|表示推薦系統為目標用戶預測評分商品的數量，n表示測試集中的總商品數量，rmax和rmin分別表示推薦系統中的最高評分與最低評分。

4.3 結果分析

實驗選取FilmTrust數據集的80%作為訓練集，20%作為測試集，使用推薦系統為用戶所推薦的商品評分與已知的測試集中的商品評分做對比，利用所給出的評價指標來度量推薦算法性能。將本文算法與傳統基于用戶的推薦算法BUCF、基于模糊C 均值聚類的協同過濾算法FCMCF和基于隱式信任的推薦算法BTCF進行對比，在設置相同參數的情況下，通過評分和top?N預測來評估推薦算法的性能。

本文算法涉及參數α與β，其中，α為用戶間綜合信任值在綜合直接信任值中所占比重，β為用戶間全局信任值在綜合信任值中所占比重。如圖5 所示，不同α值對預測評分的平均絕對誤差的影響較大，在α=0.1 和β=0.9 時，平均絕對誤差值最小，覆蓋率與F1 值最大，分別為0.45、0.593 和0.715，說明當數據稀疏和冷啟動用戶較多時，本文算法更依賴于通過用戶之間的信任傳遞來獲得最佳信任近鄰以實現評分預測。

圖5 α 值對推薦質量的影響Fig.5 The effect of α values on recommendation quality

圖6 給出了本文算法在不同近鄰個數時的推薦質量比較結果。可以看出，隨著近鄰個數的增加，推薦質量不斷降低，最終趨于平緩，其中MAE 隨著近鄰個數的增加而增加，原因是隨著近鄰個數的增加用戶間綜合信任值不斷減小，導致推薦質量不斷降低，最終趨于平緩，而COV 和F1 值隨著近鄰個數的增加而降低，從而證明本文算法在近鄰個數為5 時推薦質量較優。

圖6 近鄰個數對推薦質量的影響Fig.6 Influence of the number of neighbors on recommendation quality

圖7 給出了本文算法與對比算法在不同近鄰個數下的MAE 變化情況。可以看出，在不同近鄰個數時，FCMCF 和BUCF 算法的MAE 均是先下降后上升，最終趨于平穩，且MAE 值都在1.0 以上，而本文算法與BTCF算法均是隨著近鄰個數的增加MAE值不斷增加，最終趨于穩定，且MAE 明顯要比FCMCF 和BUCF 算法小很多。

圖7 4 種推薦算法的MAE 比較Fig.7 MAE comparison of four recommendation algorithms

圖8、圖9 給出了本文算法與對比算法在不同近鄰個數時的COV 和F1 值變化情況。可以看出，4 種推薦算法隨著近鄰個數的增加，為目標用戶推薦的長尾商品和個性化商品減少導致COV 不斷減少。當近鄰個數為35～40 時，本文算法與對比算法在COV 上沒有很大差別，但當近鄰個數為5～20 時，本文算法相比對比算法對于長尾商品的挖掘效果更好，并且具有更優的推薦效果。

圖8 4 種推薦算法的COV 比較Fig.8 COV comparison of four recommendation algorithms

圖9 4 種推薦算法的F1 值比較Fig.9 F1 values comparison of four recommendation algorithms

綜合以上實驗結果表明，本文算法相比傳統基于用戶的推薦算法、基于模糊C 均值聚類的協同過濾算法和基于隱式信任的推薦算法在平均絕對誤差、對長尾商品的挖掘能力以及綜合評價指標上具有更好的性能表現，特別是在近鄰個數較少的情況下，本文算法在數據稀疏、冷啟動問題下仍能為目標用戶進行精準推薦。

5 結束語

本文提出一種基于用戶模糊聚類的綜合信任推薦算法，使用用戶信任數據構建信任網絡計算用戶間顯式信任值，利用評分數據計算用戶間動態隱式信任值，并將用戶間顯式信任與隱式信任相融合得到綜合直接信任值，通過動態結合用戶綜合直接信任值與Jaccard 全局信任值得到用戶綜合信任值，同時利用綜合信任值取代傳統基于用戶的協同過濾中的相似度對目標用戶實現精準推薦。實驗結果表明，本文算法相比傳統推薦算法在平均絕對誤差、覆蓋率以及F1 值指標上具有更好的性能表現。后續將研究用戶間的信任傳播對推薦系統的性能影響，進一步提升推薦質量與用戶體驗。