王雨晨

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

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

現(xiàn)有的個性化電影推薦算法主要有協(xié)同過濾算法、基于內(nèi)容的推薦算法和混合推薦算法等, 其中, 傳統(tǒng)的協(xié)同過濾算法(collaborative filtering)應(yīng)用最為廣泛[3]. 它具有算法復(fù)雜性較低、對原始數(shù)據(jù)的數(shù)據(jù)內(nèi)容要求較低的優(yōu)勢. 該算法通過分析用戶對于電影的歷史評分, 進(jìn)而找到相似用戶, 并根據(jù)相似用戶的電影評價記錄為目標(biāo)用戶推薦電影.

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

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

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

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

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

1.1 社會信任度關(guān)系

1.1.1 傳統(tǒng)直接信任度模型

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

1.1.2 改進(jìn)的直接信任度模型

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

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

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

1.1.3 間接信任度模型

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

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

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

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

1.2 用戶屬性信息

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

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

1.3 融合信任因子模型

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

1.4 改進(jìn)的相似度計(jì)算

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

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

2 重排序多樣化推薦

2.1 聚類

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

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

2.2 多樣化推薦

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

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

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

2.3 推薦算法模型

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

圖1 推薦算法模型

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集及評價指標(biāo)

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

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

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

其中,pi表 示目標(biāo)用戶u對于電影i的預(yù)測評分,qi表 示目標(biāo)用戶u對電影i的真實(shí)評分.n表示推薦的電影數(shù)量.

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

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

用戶的個體推薦結(jié)果多樣性越高, 系統(tǒng)整體的多樣性越高, |U|表示用戶個數(shù), 系統(tǒng)整體多樣性定義如下:

3.2 實(shí)驗(yàn)結(jié)果分析與對比

實(shí)驗(yàn)1. 聚類個數(shù)k, 相似度計(jì)算方法的選擇.為了達(dá)到更好的推薦效果, 使用聚類算法時要確定一個合適的類簇?cái)?shù)目k. 此處先采用傳統(tǒng)的協(xié)同過濾方法進(jìn)行實(shí)驗(yàn), 相似度計(jì)算方法使用余弦相似度和修正的余弦相似度方法進(jìn)行對比實(shí)驗(yàn), 設(shè)置類簇的取值范圍為[5, 50], 增量為5, 然后計(jì)算MAE值, 實(shí)驗(yàn)結(jié)果如圖2.

圖2 聚類個數(shù)對應(yīng)的MAE值

根據(jù)實(shí)驗(yàn)可得出結(jié)論, 修正后的余弦相似度計(jì)算方法比余弦相似度方法得到的結(jié)果整體誤差要小一些,隨著類簇?cái)?shù)量的增多, 兩種方法的MAE值減小的速度逐漸變慢趨于收斂, 故本文采用修正的余弦相似度方法作為相似度的計(jì)算方法.

在基于修正的余弦相似度方法中, 當(dāng)類簇?cái)?shù)目達(dá)到35之后,MAE值趨于平穩(wěn), 考慮到算法的計(jì)算效率,因此選取類簇?cái)?shù)目k為35進(jìn)行實(shí)驗(yàn).

實(shí)驗(yàn)2. 信任因子模型權(quán)重.

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

圖3 權(quán)重系數(shù)對應(yīng)的MAE值

根據(jù)實(shí)驗(yàn)可知, 當(dāng) α 為0.4時,MAE值較小, 因此取0.4為權(quán)重系數(shù).

實(shí)驗(yàn)3. 用戶相似度參數(shù)選擇.

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

圖4 相似度參數(shù)對應(yīng)的MAE值

根據(jù)實(shí)驗(yàn)可知, 當(dāng) β為0.7時,MAE值較小, 因此取0.7為權(quán)重系數(shù).

實(shí)驗(yàn)4. 本文算法與其他算法性能對比.

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

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

圖5 不同算法的MAE值對比

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

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

4 結(jié)論與展望

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

但是對于實(shí)際推薦系統(tǒng), 隱式反饋對于推薦算法也起著至關(guān)重要的作用. 在接下來的工作中將會對隱式反饋進(jìn)行研究, 使推薦算法更迎合用戶的偏好.