基于重要性的信任感知推薦方法

譚晏松，宋鐵成

(1.重慶電子工程職業學院 人工智能與大數據學院，重慶 401331； 2.重慶郵電大學 通信與信息工程學院，重慶 400065)

0 引 言

由于近幾十年來互聯網上的信息爆炸，推薦系統(recomme-ndation systems，RS)已經成為大多數電子商務和社交網絡系統中的重要模塊[1,2]，成為解決日益增長的信息過載問題的有效方法。在各種推薦方法中，協同過濾(collaborative filtering，CF)是一種最成功的方法，它利用許多用戶的反饋來尋找相似的用戶和項目，作為推薦的基礎。但該技術也存在一些固有缺陷，如數據稀疏、冷啟動和推薦結果失真[3]。推薦系統的關鍵作用導致了該領域的大量研究，而如何克服傳統推薦系統的不足也成為研究的關鍵。

為了解決傳統推薦系統存在的冷啟動和準確率低等問題，基于機器學習的推薦模型得到了廣泛關注[4]。Zou等[5]提出一種社會推薦方法，使用自適應鄰居選擇來提高預測的準確性。Wu等[6]提出了一種融合潛在社交信任模型的協同過濾推薦算法，以提高推薦質量。Hai等[7]提出了一種基于時空感知的推薦方法。考慮到用戶的社會關系，通過構建用戶、地點、時間、活動和朋友的信息網絡，獲得推薦活動。Wei等[8]提出了一種將離散內容與興趣貼近度相結合的算法，用以提高推薦質量與性能。Li等[9]提出了一種結合社會標簽和信任關系的社會網絡推薦方法。Wu等[10]提出一種將社會網絡結構與用戶項目交互行為的內在聯系有機結合起來的社會推薦神經網絡結構。

已有的信任感知推薦系統大多認為不同項目對用戶具有相同的重要性，但是現實生活中并非如此。本文基于不同人口統計學背景下項目重要性不一致的概念，提出了一種基于重要性的信任感知推薦方法，該方法通過用戶的人口統計上下文來衡量項目對用戶的重要性，然后以項目重要性來評估委托人和受托人之間的信任級別，從而有效地適應用戶偏好的動態變化。

1 混合蛙跳算法

混合蛙跳算法[11](shuffled frog leaping algorithm，SFLA)在2003年由Eusuff等提出，是一種新型仿生學的群體進化算法，屬于啟發式智能優化算法。在這種算法中，一組青蛙(或初始解決方案)協同感知最大的食物來源。通過同時使用局部和全局搜索，SFLA對各種優化問題都是有效的[12]。

混合蛙跳算法描述如下：首先隨機初始化P只青蛙的種群，在D維搜索空間中，Xi=(Xi1,Xi2,…,XiD)表示第i個青蛙的位置。適應度函數用于評估每個個體的適應度。然后，按照青蛙的健康程度降序排列。種群中最好青蛙的位置用Xg表示。然后，將整個種群劃分為m個模因叢，每個模因叢包含n只青蛙(即P=m×n)。為此，第((i-1)×m+j)個青蛙被分配給第j個模因叢(i,j=1,2,…,m)。然后，對于每一個模因，最差青蛙的位置通過進化過程得到改善。讓Xw,j和Xb,j分別列出第j個模因叢中最差和最好青蛙的位置。在第j個模因進化過程中，最差的青蛙跳向位置Xb,j。第j個模因進化中最差的青蛙的跳躍步長計算如下

ΔXw,j=rand×(Xb,j-Xw,j)- ΔXmax≤ΔXw,j≤ΔXmax

(1)

式中：rand是(0.1)中的隨機數，而ΔXmax是最大允許步長。因此，SFLA確定最差青蛙的新位置如下

Xw,j(new)=Xw,j+ΔXw,j

(2)

如果Xw,j(new)比Xw,j具有更好的適應值，那么當前位置將被新位置替換。另外，Xw,j是根據全局最佳青蛙的位置進行了改進。為此，用Xg代替Xb,j來重復式(1)和式(2)。如果仍然沒有改進，SFLA用一個新的隨機生成的解決方案替換最差的青蛙。進化過程在預定的迭代次數內繼續。然后，執行洗牌過程以形成下一代的新種群。重復這些過程，直到滿足終止條件。

2 基于重要性的信任感知推薦方法

傳統的CF方法面臨兩個主要問題：稀疏性和冷啟動。信任感知的RS通過使用用戶之間信任網絡中的其它信息來克服這些問題。基于信任的方法可以分為顯式和隱式方法。在顯式方法中，用戶顯式表達對其他用戶的信任。顯式方法的主要缺點是用戶可能對提供顯式信任語句不感興趣，從而導致稀疏的信任網絡。與顯式方法相反，隱式方法從用戶評級行為推斷信任關系。因此，隱式方法比顯式方法更實用。但是，已有的信任感知推薦方法均假定不同項目對用戶具有相同的重要性，但是在現實生活中，項目的重要性對于個人用戶來說并不盡然相同且是動態變化的，取決于性別、年齡、受教育程度等很多人口統計特征因素。例如，越流行的產品對年輕人群的重要性要大于年老人群。在本文中，提出了一種基于重要性的信任感知推薦方法，該方法在計算用戶之間的信任時考慮了項目的重要性。針對用戶的人口統計上下文定義了此方法中使用的重要性度量。因此，所提出的方法可以適應用戶興趣的動態變化。

圖1給出了提出的基于重要性的信任感知推薦方法的框架。從圖中可以看出，提出的方法包含在線和離線兩個階段，離線階段主要用于用戶的集群，在線主要用于推薦列表的生產。在離線階段，混合蛙跳算法用于根據用戶的人口統計特征對用戶進行聚類。在線階段包括5個步驟：首先識別與活動用戶最相似的群集，以獲得候選鄰域集，即鄰居預選步驟；其次，計算活動用戶與每個候選鄰居之間的基于重要性的信任值，即基于重要性的信任計算步驟；再次，選擇最合適的候選者作為最終鄰居，即鄰居選擇步驟；然后，根據所選鄰居的偏好來預測活動用戶的未知評分，即評分預測步驟；最后，將前n個項目推薦給活動用戶，即推薦列表生成步驟。下面給出每個階段的詳細描述。

圖1 提出方法的框架

2.1 離線階段

圖2 青蛙的結構

對于每個解決方案，計算用戶和每個集群中心之間的人口統計相似性，以將用戶分配到最近的集群。用戶u與質心Zk之間的相似度計算為其對應特征向量的余弦相似度

(3)

式中：DSimi(u,Zk)∈[0,1]是解Xi中u與第k個集群中心的人口統計學相似性。

下一步的目標是使用適應度函數評估每個解決方案，利用SFLA算法從中選擇適應度最高的值作為最優解。集群解的適應度基于集群內距離之和確定，如式(4)所示

(4)

式中：Fitness(Xi)是青蛙Xi的適應度。顯然，當集群內距離之和較小時，解的質量較高。

在模因進化過程中，每個模因叢中最壞的青蛙的位置是基于局部最優或全局最優青蛙的位置或基于隨機位置進行改進的。Xw,j是第j個模因叢中最差青蛙的位置。根據跳躍的步長(i.e.,ΔXw,j)，確定最差青蛙(i.e.,ΔXw,j(new))的新位置。由于位置向量的二元表示，將Xw,j(new)離散為二元向量，為此，使用改進的離散SFLA。在這個改進的算法中，用下列公式代替式(2)計算Xw,j(new)的第dbit

t=1/(1+exp(-ΔXwd,j))

(5)

式中：下標d∈{1,2,…,K×L}表示對應向量的第d位，δ稱為靜態概率。當達到預定義的迭代次數時，滿足停止條件。

2.2 在線階段

提出算法的在線階段主要目標是生成推薦意見，此階段可以分為鄰居預選、信任計算、鄰居選擇、評級預測和推薦列表生成5步。

2.2.1 鄰居預選

在第一步中，識別與活動用戶最相似的集群。這些集群的所有成員都被選為活動用戶的候選鄰居。設CNau為活動用戶au的候選鄰居。對CNau的定義如下

CNau={u∈ck|ck∈C∧DSim(au,Zk)≥α}

(6)

式中：α是相似度閾值。如果α小，則人口統計學相似性相對較低的那些用戶也被視為候選鄰居；當α大時，候選鄰居的數量不足以識別可信賴的鄰居。

2.2.2 基于重要性的信任計算

根據活動用戶對候選鄰居的共同評價項以及這些項對活動用戶的重要性來計算活動用戶對候選鄰居的隱式信任。為了實現這一目標，定義了一個新的顯著性度量，它基于人口統計學背景下的項目評級。然后，提出了一種新的信任度量方法，該方法考慮了項目的重要性。

首先是顯著性計算，通過計算項目i的平均評級和評級的用戶的百分比兩個測量指標來計算項目i的重要性。假定si表示項目i的顯著性，其最小值為0(非顯著)和最大值為1(非常顯著)。為了確保si介于0和1之間，額定值標準化為[0,>1]。使用最小-最大標準化方法，將原始評級r轉換為標準化評級r′∈[0,1]，如下所示

(7)

式中：最小值是最小額定值，最大值是系統中的最大額定值。

設ru,i為從用戶u到項目i的標準化評級，設Ui={u∈U|ru,i≠·}為項目i評級的用戶集，符號ru,i=·表示u沒有對項目i進行評級，項目的重要性評價計算如下

(8)

式中：#表示集合的基數。

對于具有不同人口學特征的不同用戶，項目的重要性是不同的。此外，用戶的個人偏好可能在整個生命周期(從童年到老年)中發生變化。因此，當前對用戶重要的項在將來可能變得不那么重要。為了處理這一事實，在測量項目對u的重要性時考慮了用戶u的人口統計學背景。為此，將式(8)修改如下

(9)

式中：si,k∈[0,1]是集群ck用戶i項的重要性，Uk是集群ck用戶的集合，Ui,k={u∈ck|ru,i≠·}是集群ck用戶中對i項評級的集合。

其次是對信任進行計算。本文采用的信任度量包含了項目的重要性。從用戶u到用戶v，STrustu→v∈[0,1]的基于顯著性的信任定義如下

(10)

(11)

(12)

根據式(12)，直接信任值由相應用戶之間的共同評級項目數加權。這種傳播方法的基本原理是，直接信任關系的可靠性隨著共同評級項目的數量而增加。因此，如果兩個用戶有更多的共同評價項，那么在傳播過程中，他們之間的關系權重會更大。信任網絡中任意兩個用戶之間的間接信任可以通過等式(12)的重復應用來計算。如果網絡中兩個用戶之間存在多個路徑，則計算從可選路徑推斷的所有信任值的算術平均值。

2.2.3 鄰居選擇

從候選集中選擇活動用戶最可信的鄰居。為此，選擇信任值大于或等于指定閾值的候選對象作為鄰居。讓FNau表示活動用戶au的最后鄰居集。FNau定義如下

FNau={u∈CNau|STrustau→u≥θ}

(13)

式中：θ是信任閾值。

2.2.4 評分預測

選擇的鄰居用于預測活動用戶的偏好。目標項的活動用戶的未知分級估計如下

(14)

式中：pau,i是活動用戶au對目標項目i∈I1Iu的預測評級。

2.2.5 生成推薦列表

最后，使用預測的評級為活動用戶生成top-n推薦列表。目標項目根據其預測評級進行排名。然后，系統會推薦級別最高的項目。

3 實驗結果與分析

3.1 數據集

實驗數據集采用MovieLens 1M1(ML)和Book-Crossing(BX2)兩個不同領域的公開來源真實數據集，ML和BX均包含用戶的人口統計信息。

ML數據集由6040個用戶為3952部電影提供的1 000 209個評級組成。評級從1分(差)到5分(優)。其稀疏度為95.809%。除了評級數據外，ML還提供了一些用戶的人口統計信息，包括年齡、性別和職業。性別是“M”(男性)或“F”(女性)。在這個數據集中，有21種不同的職業，如工程師、藝術家、醫生等。

BX數據集包含1 149 780個評級，來自271 379本書的278 858個用戶。有433 681個明確的評級，等級為1到10，716 109個隱含評級(值為0)。在這個數據集中，人口信息包括年齡和地點(國家)。刪除沒有評級的用戶和項目，數據集包含407 332個明確的評級，來自178 647本書的74 085個用戶(99.996%稀疏度)。

對于這兩個數據集，將用戶的人口統計特征表示為二進制特征向量，其中1和0分別表示特征的存在和不存在。用戶人口統計學向量的結構見表1。

表1 數據集基本參數

根據表1，年齡、性別、職業和地點被定義為分類屬性。有4個年齡類別，2個性別類別，21個職業類別和30個地點類別。如果用戶屬于某個類別，則相應的比特設置為1；否則為0。因此，對于每個分類屬性，只有一個位是1，其余的是0。對于ML數據集，人口統計學向量的長度為27，而對于另一個數據集，長度為34。在這兩種情況下，向量的前四位表示年齡類別。對于ML，第5和第6位表示用戶的性別，其余的位對應于職業類別。對于BX，用戶的位置由位5-34指定(表1)。

3.2 實驗設置

在這項研究中，所有的實驗都使用5倍交叉驗證。評級數據被隨機分成5個大小相等的子集。在每次評估運行中，一個子集用作測試數據，而另一個子集用作訓練數據。以5次平均成績作為總成績。從兩個不同的角度進行實驗：①所有用戶，其中對所有用戶及其評級進行評估;以及②冷用戶，主要關注評級低于10的用戶。

選用配置為Intel Corei5 @2.53 GHz和4 GB RAM的機器測試，調整每種方法的參數以獲得盡可能好的結果。對于所提出的方法，對SFLA進行微調以獲得最佳結果。SFLA的參數值見表2。

表2 SFLA參數設置

3.3 評價指標

為了評估推薦算法的性能，在實驗中預測精度是由均值絕對誤差(mean absolute error，MAE)來評估的，均值絕對誤差衡量的是預測值和實際值之間的誤差，其值越小說明算法性能越好。讓T表示要估計的額定值集(即測試集)。MAE定義如下

(15)

預測的質量根據覆蓋率進行評估。評級覆蓋率(rating coverage，RC)是指系統可以預測的測試評級百分比，其值越大說明算法預測質量越好

(16)

式中：pu,i≠·表示用戶u對項目i的評級是可預測的。

3.4 實驗結果與分析

在第一個實驗中，驗證算法在離線、在線階段對參數的敏感性。圖3給出了離線階段集群K數量對算法的影響。從圖中可以看出，隨著K的增加，所提算法的MAE先下降后上升，ML和BX數據集分別在K=14和17時取得最優。

圖3 集群K對算法的影響

圖4給出了在線階段相似度閾值α對算法的影響。從圖中可以看出，RC隨著α的增大而減小，并且較低的α值會導致較高覆蓋率和較低的準確性。對于兩個數據集，α分別取0.6和0.5時，可以獲得最佳的MAE。

圖4 相似度閾值α對算法的影響

在第二個實驗中，將提出的方法的整體性能與SRANS[5]、

DTTN[13]、TCFACO[14]這3種流行算法進行了比較。所有用戶(包括冷啟動和非冷啟動用戶)都參與了這個實驗。兩個數據集的MAE和RC結果見表3。

表3 ML和BX數據集的所有用戶視圖的MAE和RC結果

如表3所示，提出的方法在兩個數據集中的MAE最低。這驗證了基于重要性的信任度量在提高信任感知推薦系統性能方面的能力。此外，基于重要性的信任感知推薦方法具有比其它方法更高的RC。由于人口統計信息的利用，即使沒有評級數據，它也能為用戶找到足夠的鄰居。

第三個實驗，評估了提出的方法在緩解冷啟動問題方面的有效性。評級低于10項的用戶被視為冷啟動用戶，設N為測試用戶觀察到的評級數。通過改變評級的數量來評估預測和建議的質量。對于每個測試用戶，保留N個培訓等級，其余的則丟棄。實驗進行了N等于2，4，6和8的實驗。結果如圖5-圖10所示。

圖5 不同算法在ML數據集冷用戶視圖的MAE結果

圖5-圖6分別給出了4種不同方法在ML數據集的預測精度和質量結果，從圖5中可以看出，所提出的方法比其它3種方法的MAE值要低，當評級數N越高時MAE值越低；圖6展示了它們在ML數據集冷用戶視圖的RC結果對比，同樣從圖中可以看出，所提出的方法的RC值均高于其它3種方法，當評級數N越高時RC值也越高。圖7-圖8則給出了4種方法在BX數據集的表現，結果與在ML數據集的表現相似。基于重要性的信任感知推薦方法，在預測精度和預測質量上均優于對比的方法。結果表明，將人口統計信息納入基于重要性的信任感知推薦方法有助于解決冷啟動問題。

圖6 不同算法在ML數據集冷用戶視圖的RC結果比較

圖7 不同算法在BX數據集冷用戶視圖的MAE結果

圖8 不同算法在BX數據集冷用戶視圖的RC結果比較

圖9給出了不同推薦方法在ML和BX數據集上的執行時間對比結果。從圖中可以看出，在所有方法中，提出方法的執行時間最短。由于采用了兩層鄰居選擇策略，DTTN的執行時間較長。SRANS比DTTN慢是因為SRANS需要復雜的過程來識別初始鄰居集合并以自適應方式對其進行優化。TCFACO具有最長的執行時間，因為它同時使用信任和相似性信息來構造用戶映射，然后在該映射上應用ACO搜索策略來查找用戶的最佳鄰居。

圖9 不同算法的執行時間對比結果

圖10 不同傳播距離下的執行時間

為了更好地理解所提推薦方法的效率，圖10比較了不同方法對MPD的不同值的執行時間。MPD是決定信任者與被信任者之間最大距離的參數。基于該參數，重復使用信任傳播式(12)來計算用戶u與其他用戶之間的信任。從圖中可以看出，隨著傳播距離的增加，其它方法的效率急劇下降，所提方法的在不同傳播距離下執行時間最短，該方法優勢隨著距離的增加而變得更加明顯。

4 結束語

本文針對傳統推薦系統存在的局限，提出了一種基于重要性的信任感知推薦方法，該方法的研究重點是一種基于項目重要性的信任度量。本文方法分為兩個關鍵階段，在離線階段，項目采用混合蛙跳算法(SFLA)，對用戶的重要性是根據用戶的人口統計特征來衡量的，以此可以實現用戶偏好的動態變化。在線階段根據活動用戶的信任鄰居的偏好為其生成top-n推薦列表。實驗結果表明，通過與幾種最新推薦方法的比較，在預測精度和預測質量上，提出的方法優于其它方法。