改進型動態度量推薦算法

張洪軍 楊霞

（1、南京國電南自電網自動化有限公司，江蘇南京 210000 2、易思奇汽車電子（上海）有限公司，江蘇南京 210000）

1 概述

電子商務、搜索引擎中應用范圍最廣的推薦算法是由Goldberg 等人提出的協同過濾推薦算法(collaborative filtering recommendation algorithm)。傳統的協同過濾算法基于兩種假設：（1）用戶的喜好是固定不變的；（2）對商品評分相同的用戶之間具有相同的喜好。

協同過濾算法基于這兩個假設來構建用戶的可信網絡并使用該可信網絡來計算推薦條目。隨著社會的發展、新事物的出現、用戶習慣的變化、歷史數據時間跨度的變大，用戶的興趣愛好發生了很大的變化。這就導致協同過濾算法中的兩種假設誤差變大，相同用戶集誤差的變大會導致可信網絡的準確度變低。為了解決協同過濾算法中存在的這些問題，本文在協同過濾算法的基礎上引入了動態度量的概念，提出了一種動態度量可信度的推薦算法（dynamic reliability measure recommendation algorithms, DRMRA）。DRMAR 算法通過相似度與信任的耦合值來替代相似度值，通過耦合的相似度值來構建可信網絡并計算初始評分值，然后利用DRMAR 算法來重構所有低于預定值的可信網絡。DRMAR 算法在Epinions、Flixster 數據集上進行了對比測試，測試結果顯示與主流的推薦算法比較DRMAR 算法在用戶覆蓋率、推薦條目準確率上面有所提高。

2 推薦系統常用算法介紹

協同過濾算法：

Goldberg 等人提出的協同過濾算法是推薦系統中使用率最高的算法，協同過濾算法兩種假設：（1）用戶的喜好（轉下頁）是固定不變的；（2）對商品評分相同的用戶之間具有相同的喜好。協同過濾算法計算方法如下：（1）預定義相似值，并使用該值來計算用戶之間的距離權值；（2）利用距離權值來生成可信網絡；（3）根據可信網絡來生成推薦推薦條目。協同過濾算法檢索歷史數據中用戶對不同條目的評分并根據歷史評分來查找鄰居，通過檢索鄰居的購買條目來生成當前用戶的推薦條目。協同過濾算法可以分為兩類：基于項目的方法（Project-Base）、基于模型的方法（Mode-base）。Project-Base 算法會首先遍歷該用戶的歷史評分，通過歷史評分記錄來計算用戶、條目之間的相似值，并根據該相似度值來直接訪問包含所有用戶評分、建議的用戶- 商品評分矩陣并為當前活躍用戶生成預測評分。Mode-Base 算法使用AI 算法來生成統計模型，并使用生成的統計模型來為不可見商品進行評分。

3 改進型可信度動態度量推薦算法

為了解決傳統的協同算法中由于用戶矩陣準確率低、依賴于用戶歷史評分造成的推薦結果準確率低及惡意評分導致的一系列安全風險。本文引入了可靠性動態度量的概念提出了一種新的算法：可信度動態度量的推薦算法（dynamic reliability measure recommendation algorithms, DRMRA）。DRMRA 算法將可靠性度量值、信任聲明進行耦合成新的動態度量值來跟提高推薦系統準確性。算法的改進主要體現在以下方面：（1）將相似性矩陣與用戶信任聲明矩陣耦合來生成全新的動態可信網絡；（2）提出積極/消積因子動態度量可信值；（3）使用基于信任的動態可靠性度量值來重建用戶的信任網絡。DRMRA 工作流程由六部組成：（1）耦合信任網絡構造；（2）初始評分預測；（3）基于信任的動態可信度計算；（4）耦合可信網絡重構；（5）用戶最終評分預測；（6）Top-N 商品選擇。

3.1 耦合信任網絡構建

DRMRA 算法在傳統的協同過濾算法信任網絡構建的基礎上進行了改進，改進如下：

（1）將用戶信任值、皮爾遜系數測量值合并生成耦合相似度值；（2）使用耦合相似度值來計算用戶鄰居的加權有向圖。每個用戶是加權有向圖的一個節點，用戶之間的相似度值是用戶節點之間的權重值。用戶對之間的信任聲明Ta，u、信任傳播距離dmax計算如下：

用戶之間的權重調整方法如下：

3.2 初始評分預測

用戶未選購商品的默認評分是通過初始可信網絡來計算的，用戶u 對于商品i 的預測評分計算方法如下：

其中ra表示用戶a 的平均評分，Ka，i表示商品i 跟用戶a 具有相同評分的用戶集，wa，u表示用戶a 跟用戶u 之間的相似度權重即可信網絡中兩個節點之間的邊長。

3.3 基于信任的動態可信度計算

傳統的協同過濾算法中是在用戶評分矩陣中使用一個正因子一個負因子來計算可信度，因此這種方法不適用于基于信任的協同過濾算法。本文在傳統的協同過濾算法的基礎上做了如下改進：（1）在傳統協同過濾算法基礎上引入了信任聲明；（2）將信任值引入正負因子中，提出了一種全新的基于信任的動態可信度計算方法，將基于信任的動態可信度度量值做為可信網絡重構的反饋依據，基于信任的動態可信度度量值計算方法如下：

其中fs（Sa，i）表示正因子fv（Sa，i）表示負因子，正負因子計算方法如下：

3.4 耦合可信網絡重構

可信度計算完成后利用可信度度量值來評估預測評分的質量，當前用戶a 對于商品i 的可信值Ra，i小于預定義的閥值θ 那么就需要重構可信網絡。我們在可信網絡重構過程中引入正因子wa，u和負因子V（u）來重構可信網絡，將可信網絡中的無用用戶刪除來提高可信網絡的質量。負因子V（u）計算方法如下：

3.5 Top-N 商品選擇

當可信網絡重構完成后，我們用可信網絡來預測Top-N 條商品推薦給用戶。

4 實驗結果與分析

4.1 實驗環境設定

為了評估DRMRA 算法的效果我們選取了Epinions、Flixster兩個數據集進行驗證，初始用戶-商品評分矩陣、用戶信任矩陣初始值如表1 所示，商評分值的范圍為[1,10]步進值1。

我們將數據集中的用戶分為三類：新注冊用戶、活躍用戶、惡意用戶。我們將商品分為如下兩類：冷門商品、有爭議商品。為了比對DRMRA 算法在推薦準確率、用戶覆蓋率方面的改進，我們選擇了CF、TARS、TCF、RTW、BIBR 五種算法來做對比測試，使用留一法（LOO）在平均絕對值誤差（MAE）、平均用戶誤差（MAUE）、評分覆蓋率（RC）、用戶覆蓋率（UC）四個方面進行對比。實驗過程中試驗參數設定如下，可信網絡重建閥值θ=0.7，可信網絡重建過程中閥值α=0.6，β=0.7，用戶鄰居選在范圍K=500。

表1 用戶信任、用戶商品評分矩陣

圖1 數據集Epinions、Flixster 測試結果

4.2 實驗結果及分析

Epinions、Flixster 數據集所有數據測試結果（圖1）所示，DRMRA 算法具有最低的MAE 僅次于RTW 算法的用戶覆蓋率。DRMRA 算法在RC、UC 指標跟TCF 算法很接近但是準確率最高。