融合信任因子的多樣化電影推薦算法①

王雨晨

(北京郵電大學 計算機學院(國家示范性軟件學院), 北京 100876)

大數據時代下, 互聯網為我們提供方便的同時, 也給我們帶來了困擾, 網絡中的信息呈爆炸式增長, 從海量的信息中挖掘出對我們需要的信息非常重要[1]. 隨著網絡上電影數量的增加, 用戶不得不花費大量精力來挑選自己感興趣的電影. 此時, 個性化推薦系統的出現在一定程度上解決了信息過載問題[2], 它可以通過分析用戶的歷史行為特征和有關的數據信息, 為用戶推薦可能感興趣的項目, 起到了信息篩選的作用.

現有的個性化電影推薦算法主要有協同過濾算法、基于內容的推薦算法和混合推薦算法等, 其中, 傳統的協同過濾算法(collaborative filtering)應用最為廣泛[3]. 它具有算法復雜性較低、對原始數據的數據內容要求較低的優勢. 該算法通過分析用戶對于電影的歷史評分, 進而找到相似用戶, 并根據相似用戶的電影評價記錄為目標用戶推薦電影.

但是協同過濾算法在實際應用中也存在很多缺陷,比如冷啟動、數據稀疏性問題. 基于此, 國內外學者做了大量實驗研究. Lokhande等[4]提出了一種融合層次聚類和主成分分析的混合推薦算法模型, 降低了用戶-評分矩陣的稀疏性, 提高了傳統協同過濾算法的推薦精度. 楊秀梅等[5]根據已有用戶對不同新聞的瀏覽歷史記錄提取其上下文信息, 解決了新聞推薦系統中的新用戶冷啟動問題, 提高了用戶滿意度. 但是以上研究基本上是依據用戶的評分數據進行分析的, 并沒有考慮用戶間的信任度關系, 對于電影推薦系統中的用戶來說, 其信任朋友的推薦的影片可能會更值得信賴, 推薦效果更能使用戶感興趣. 基于此, 俞美華[6]提出一種融合用戶興趣度的電影推薦算法, 通過改進用戶相似度的計算方法, 提供個性化推薦. Sasmita等[7]提出了用戶相似性和加權信任傳播相結合的信任矩陣度量方法, 通過使用反向傳播、深度神經網絡來進行電影推薦. 但是上述算法沒有充分挖掘用戶之間的隱式信任關系, 沒有建立相對完整的信任機制, 會出現信任關系不完整的問題.

另一方面, 目前電影推薦算法大多數都是基于用戶之間的相似度或者物品之間的相似度, 主要關注推薦的準確率, 推薦熱門物品給用戶, 而忽略了非熱門物品的推薦機會, 從整體推薦結果上來看, 推薦種類多樣性較低、用戶容易產生審美疲勞. 針對用戶的個性化需求, 為用戶推薦他們感興趣但難以發現的商品, 即將長尾商品準確地推薦給需要它的用戶是個亟待解決的問題[8-10]. Zhou等[11]使用傳導的方法將熱門項目的權重傳遞給長尾項目, 提高長尾項目的推薦度, 提高了系統的推薦多樣性, 但是系統準確率較低. Adamopoulos等[12]針對物品的概率分布計算相似度, 提高了系統的多樣性和準確度, 但是作者只分析了顯性評分. 因此, 在保證準確率的前提下提升推薦算法的多樣性具有一定的研究意義.

綜上所述, 本文對傳統的協同過濾算法進行改進,針對于推薦準確性和多樣性, 提出了一種融合信任因子的多樣化電影推薦算法. 本算法首先挖掘用戶的屬性特征和用戶之間的信任度關系, 將其和傳統的相似度計算方法結合, 保證了每位用戶推薦的可靠度和可信度. 然后使用改進類簇中心確認方法的K-means聚類方法, 將擁有相同興趣愛好的用戶聚集在同一個社群中. 最后在用戶推薦階段使用重排序方法, 通過加入懲罰因子來計算電影推薦度, 提高了電影推薦算法的整體多樣性, 同時能夠在一定程度上解決冷啟動和數據稀疏性問題

1 融合信任因子的相似度算法

信任關系是指用戶對于鄰居用戶的推薦可靠性的認可程度, 認可度越高, 推薦越符合用戶興趣[13]. 而信任關系受到諸多因素的影響, 比如用戶自身屬性、社會信任度關系等, 這些因素通常被統稱為信任因子[14].本文將信任因子與傳統相似度計算方法相融合, 旨在充分挖掘用戶信息特征.

1.1 社會信任度關系

1.1.1 傳統直接信任度模型

傳統的信任關系模型大多數是通過簡單計算用戶間的交互次數來建立的[15,16]. 文獻[17]提出了一種計算用戶直接信任度的方法, 通過最初信任度與用戶間成功交互次數的乘積計算得到用戶直接信任度, 如式(1)所示. 其中Init(u, v)為初始信任度, 計算方法如式(2)所示,Iu∩Iv為用戶u和用戶v交互的次數,d為設置的閾值, 表示兩個用戶成功建立信任關系最少的交互次數, 文獻實驗證明,d取值為80效果最佳.countt表示兩用戶交互的總次數,counts表示用戶交互成功的次數, 此處交互成功的標準為兩用戶對于同一項目的評分小于2分.

1.1.2 改進的直接信任度模型

傳統的信任關系模型能夠有效地表示用戶的信任關系, 但是式(1)中成功交互的計算方法忽略了用戶之間對于非感興趣電影的信任度. 如果兩個用戶對于某部電影的評分都為1.5分, 根據傳統信任度計算方法,由于兩個用戶都看過同一電影并且對于電影的評分相同, 系統會認定兩用戶間有較高的相似度. 但是這個分數只能夠說明兩個用戶對于這部電影不喜愛, 并不能代表用戶間喜愛的項目相似. 因此, 針對此問題, 本文在傳統信任度模型中引入感興趣因子, 定義如下:

其中, |Iuv＞D|表示用戶u和用戶v共同評分的電影分數大于D的數量,countt表示兩個用戶交互的總次數.如果用戶u和用戶v對于同一部電影的評分都大于閾值D, 則說明兩用戶的興趣比較相似. 基于電影的評分分值區間為1-5, 因此設定閾值D為3.5.

綜合得到用戶直接信任度模型, 定義如下:

1.1.3 間接信任度模型

由于用戶-評分矩陣本身比較稀疏, 可能會出現用戶u和用戶v沒有直接信任關系, 但是他們有共同朋友k, 根據信任關系的傳遞性特征, 用戶能夠信任自己的直接朋友, 也會在一定程度上信任朋友的朋友. 故本文引入間接信任度, 用ITrust(u, v)表示. 但是隨著信任鏈的長度增加, 信任度會逐漸減弱. 在保證時間復雜度和保留有效用戶的前提下, 根據文獻[18]對于間接信任的關系研究, 本文只考慮目標用戶的兩級信任關系.

假設用戶v是用戶u的二級信任用戶, 兩用戶之間至少存在一條路徑, 每條路徑表示為Path(ui,vi)=(ui,k,vi), 每條路徑的信任度計算方法如下:

用戶的間接信任模型通過計算路徑信任度的均值得到, 如式(6), 其中n表示從用戶u到用戶v的路徑數目之和.

得到用戶間接信任度矩陣后, 將其填充到直接信任度矩陣Trust1中, 構建社會信任度關系矩陣Trust(u,v).

1.2 用戶屬性信息

充分挖掘用戶的屬性信息是獲得用戶特征的重要方法, 通過數據挖掘, 我們可以對用戶進行更全面而深入的了解, 從而能夠更加準確地預測、并推薦適合的電影給用戶. 較早嘗試將屬性信息與推薦算法融合的典型代表有Kazienko等[19]開發的電商推薦系統, 他通過挖掘用戶注冊的信息進行推薦, 對于新用戶來說, 利用屬性特征的推薦算法的點擊率達到了89%, 相比于隨機推薦提高了62%. 屬性信息從某種程度上反映了用戶的喜好度, 因此本文對用戶的年齡、性別、職業信息進行挖掘.

本文參考文獻[20]中的計算方法, 對于用戶年齡,將其劃分為7個年齡段, 分別用數值1-7表示(年齡段為: 小于18、18～24、25～34、35～44、45～49、50～55、大于56). 對于用戶性別, 用1表示男(M), 0表示女(F). 對于用戶職業, 將其分為七大類, 分別用數值1-7表示(包含企事業負責人、專業技術人員、服務業人員、文娛從事人員、教育行業、家政以及其他7類).組合的屬性信息相似度如式(7), 其中S(u,v)代表性別相似度,A(u,v)代表年齡相似度,O(u,v)代表職業相似度.

1.3 融合信任因子模型

融合信任因子模型綜合考慮了信任關系的潛在因素和用戶個體差異, 主要包含社會信任度關系和屬性特征相似度. 用戶u和用戶v的信任因子模型如式(8),其中, α為權重因子, α ∈0,1.

1.4 改進的相似度計算

用戶之間的相似度可以使用余弦相似度來計算,但是不同用戶評分可能會有不同的評分標準, 有的用戶習慣性打高分, 而有的用戶習慣性打低分, 考慮到不同用戶的評分偏好問題, 本文使用修正的余弦相似度作為傳統相似度計算方法. 其中表示用戶u,v對于所有評分電影的均值,ruv表示兩個用戶共同的評分集合,ru,i,rv,i分別表示用戶u,v對于電影i的評分, 修正的余弦相似度計算如下:

結合本節所述, 將信任因子和修正的余弦相似度融合得到用戶綜合相似度sim(u,v), β為調整綜合相似度的系數, β∈(0,1), 用戶相似度計算如下:

2 重排序多樣化推薦

2.1 聚類

K-means算法是基于劃分的無監督聚類算法[21,22],用途廣泛且收斂速度快. 通過K-means聚類算法對用戶進行劃分, 能夠將用戶分為k個用戶社群, 社群內用戶的相似度較高, 社群間用戶的相似度較低. 但是Kmeans算法容易受到初始聚類中心的影響[23], 對初始聚類中心具有較高的敏感性, 而且合適的初始聚類中心的選擇能夠減少聚類迭代的次數, 加快收斂速度, 因此, 選擇合適的初始聚類中心至關重要. 本文對K-means進行一些改進, 在選取初始類簇中心時保證其各中心之間的距離盡可能大, 然后進行聚類并不斷更新類簇中心, 用戶-評分矩陣聚類的步驟如算法1.

算法1. 用戶-評分矩陣聚類算法Rm×n 輸入: 用戶-評分矩陣 , 聚類的類簇個數k C={C1,C2,···,Ck}輸出: k個用戶社群C1 1) 隨意選取一個用戶作為初始聚類的中心 .D(x)2/∑D(x)2 2) 首先計算每個用戶與當前存在的類簇中心之間最小相似度, 用D(x)表示, 則每個用戶被選為下一個聚類中心的概率為 ,按照輪盤概率法選擇下一個聚類中心.C′={C1′,C2′,···,Ck′}3) 重復2), 直到選出k個聚類中心 .4) 對于矩陣中每個用戶u, 計算它到k個聚類中心的相似度并將其劃分到最近的聚類中心所對應的簇中.Ci 5) 針對每個類簇, 重新計算它的聚類中心 .6) 重復步驟4)和步驟5), 直到聚類中心的位置不再變化.

2.2 多樣化推薦

用戶的推薦列表是根據相似用戶的電影評分和相似度計算得到的預測評分來推薦的. 以得到用戶u的推薦列表為例, 首先需要計算目標用戶u與所有聚類中心的距離, 找到距離最近的類簇. 然后計算用戶u與該類簇中所有用戶的相似度, 選取最近的k個鄰居, 記作Uu, 則用戶u對于電影m的預測評分計算如下:

但是在計算預測評分時, 推薦算法的多樣性容易受到用戶活躍度的影響[24], 如果用戶比較活躍, 那么他的感興趣范圍更廣, 更容易和其他用戶有共同的評價電影, 但是這不能表示活躍用戶的興趣特征, 推薦的電影參考價值不大, 因此本文使用重排序技術, 通過引入懲罰因子, 使非活躍用戶的推薦權重增大, 活躍用戶的推薦權重減小. 重排序技術不會改變電影推薦的候選集, 只是在排序過程中改變電影的推薦概率, 把一些新物品移到推薦列表前面. 本文引入懲罰因子修正電影的推薦度, 改進后的電影預測評分計算如下:

其中, |N(v)|表示鄰居v的評分電影數. 用戶越活躍, 其評價的電影數量就越多, 那么懲罰因子就越大, 該用戶的推薦度參考性就相對更低一些.

2.3 推薦算法模型

結合上文所述, 融合信任因子的多樣化電影推薦算法整體的流程如圖1所示.

圖1 推薦算法模型

3 實驗結果與分析

3.1 實驗數據集及評價指標

本實驗使用美國明尼蘇達大學GroupLens實驗組創建的開源電影數據集Movielens-100K. 此數據集包含了943名用戶對1682部電影的100 000條評分記錄, 每位用戶至少評分20部電影, 評分值區間為1～5,評分越高表明用戶對于電影的喜愛度越高. 同時數據集中還包含用戶信息表、職業列表等, 能夠對用戶數據進行挖掘. 為避免偶然性, 實驗采用五折交叉驗證法,將數據均分為5份, 其中1份作為測試數據集, 另外4份作為訓練數據集. 重復進行實驗5次, 5次實驗結果的平均值為實驗最終結果.

實驗軟件環境為Windows10 x64、PyCharm x64,硬件環境為Intel(R) Core(TM) I5-10210U CPU ＠1.60 GHz 8核.

本文采用平均絕對誤差MAE(Mean Absolute Error)[25],整體多樣性[26]作為算法度量標準.MAE能夠衡量預測評分和真實評分的差距, 其值越小, 誤差越小, 推薦準確度就越高. 其定義為:

其中,pi表 示目標用戶u對于電影i的預測評分,qi表 示目標用戶u對電影i的真實評分.n表示推薦的電影數量.

多樣性指標[25]顯示了推薦列表中電影的多種類、非相似性, 能夠覆蓋到用戶不同的興趣和愛好, 推薦系統中用戶u的推薦列表的多樣性定義如下:

其中, |R(u)|表示用戶u的推薦列表數目,sim(i,j)表示推薦列表中的電影i和j之間的相似度.

用戶的個體推薦結果多樣性越高, 系統整體的多樣性越高, |U|表示用戶個數, 系統整體多樣性定義如下:

3.2 實驗結果分析與對比

實驗1. 聚類個數k, 相似度計算方法的選擇.為了達到更好的推薦效果, 使用聚類算法時要確定一個合適的類簇數目k. 此處先采用傳統的協同過濾方法進行實驗, 相似度計算方法使用余弦相似度和修正的余弦相似度方法進行對比實驗, 設置類簇的取值范圍為[5, 50], 增量為5, 然后計算MAE值, 實驗結果如圖2.

圖2 聚類個數對應的MAE值

根據實驗可得出結論, 修正后的余弦相似度計算方法比余弦相似度方法得到的結果整體誤差要小一些,隨著類簇數量的增多, 兩種方法的MAE值減小的速度逐漸變慢趨于收斂, 故本文采用修正的余弦相似度方法作為相似度的計算方法.

在基于修正的余弦相似度方法中, 當類簇數目達到35之后,MAE值趨于平穩, 考慮到算法的計算效率,因此選取類簇數目k為35進行實驗.

實驗2. 信任因子模型權重.

將用戶的社會信任度和屬性特征相似度相融合得到信任因子模型simt(u,v) , 設置權重系數α ∈0,1, 增量為0.1, 計算不同權重下的MAE值, 結果如圖3.

圖3 權重系數對應的MAE值

根據實驗可知, 當 α 為0.4時,MAE值較小, 因此取0.4為權重系數.

實驗3. 用戶相似度參數選擇.

將用戶的信任因子模型和修正的余弦相似度相融合得到用戶相似度sim(u,v), 設置參數 β∈(0,1), 增量為0.1, 計算不同參數下的MAE值, 結果如圖4.

圖4 相似度參數對應的MAE值

根據實驗可知, 當 β為0.7時,MAE值較小, 因此取0.7為權重系數.

實驗4. 本文算法與其他算法性能對比.

本實驗選取基于皮爾遜相似性的協同過濾算法(PB-UCF), 文獻[17]提出的融入用戶喜好度到信任關系中的協同過濾算法(WTUBCF), 文獻[27]提出的topN推薦算法Expectation approach, 文獻[28]提出的DNMF算法和本文提出的算法做對比, 5種算法的最近鄰居用戶區間取值為[5, 50], 增量為5, 比較MAE和多樣性指標.

從圖5中可以看出, 本文提出的算法在最近鄰居數達到35能夠取得較好的推薦效果. 4種算法隨著最近鄰居數目的增多MAE值逐漸下降, 本文算法的MAE值明顯低于其他4種算法, 說明本文提出的算法能夠提高算法推薦的準確度.

圖5 不同算法的MAE值對比

從圖6中可以看出, 隨著推薦物品的數量增多, 系統的多樣性逐步增加. PB-UCF和WTUBCF兩種算法由于沒有對多樣性問題進行改進, 所以算法多樣性相對較低. 和Expectation approach相比, 隨著最近鄰居數的增加, 本文提出的算法在多樣性指標中相對較高些.在最近鄰居數小于40時, DNMF算法的多樣性較其他算法高一些, 在鄰居數大于40后, 本文提出的算法的多樣性相對較高, 可見隨著推薦電影的數目的增多, 本文提出的算法能夠更好地分析用戶屬性特征并為其提供個性化的推薦. 因此本文提出的算法在保證準確度的情況下, 能夠在一定程度上提升電影推薦系統的多樣性.

圖6 不同算法的多樣性對比

4 結論與展望

本文提出的融合信任因子的多樣化電影推薦算法,通過分析社會性信任度關系和用戶特征信息, 充分挖掘了用戶的特征信息. 另外通過引入懲罰因子, 結合用戶活躍度實現了電影多樣化推薦. 通過實驗分析, 證明了本文提出的算法有效, 相對于之前的電影推薦算法來說, 算法平均絕對誤差更小, 同時推薦算法的多樣性有了相對地提升. 另外, 本文提出的算法具有一定的通用性, 除了可以用于電影推薦系統之外, 還能應用于電商推薦系統、新聞推薦系統等.

但是對于實際推薦系統, 隱式反饋對于推薦算法也起著至關重要的作用. 在接下來的工作中將會對隱式反饋進行研究, 使推薦算法更迎合用戶的偏好.