基于熱門度修正因子和置信度的協(xié)同過濾算法

劉昊東，王 誠

(南京郵電大學 通信與信息工程學院，江蘇 南京 210003)

0 引 言

如今，信息量過載困擾著很多用戶，導致無法精確、有效地找到用戶感興趣的信息，還會使用戶在獲取信息的過程中浪費過多的時間和精力，因此，推薦系統(tǒng)應運而生。目前，推薦系統(tǒng)已經(jīng)在多個領域得到廣泛應用，如教育[1]、電商[2]、醫(yī)療[3]、旅游[4]等都有涉及。一般來說，推薦算法主要分為3類，包括基于用戶的算法[5]、基于項目的算法[6]以及基于模型的算法[7]，其核心思想分別通過近鄰用戶、相似項目以及歷史數(shù)據(jù)去挖掘用戶感興趣的內容。

為了使推薦系統(tǒng)的性能得到進一步的提升，許多應用場景也對推薦算法做了相應的改進，從而更好地彌補該算法的一些不足。眾所周知，協(xié)同過濾算法[8]在推薦領域占據(jù)半壁江山，具有高效的性能和較強的解釋性。而在實際應用過程中，此算法依舊存在著諸多問題，如拓展性差、冷啟動[9]、馬太效應、數(shù)據(jù)稀疏[10]等，影響了推薦系統(tǒng)的性能。為了解決這些問題，許多學者對此做了更近一步的研究。文獻[11]為了得到更精確的推薦，考慮時間因素對用戶評分的影響和用戶之間的非對稱影響度，對相似度計算方法做相應的改進。文獻[12]提出基于信任的矩陣分解技術，此技術通過建模用戶作為受托人和信托人的角色,進而生成信任網(wǎng)絡的結構信息，最終將信息源集成到推薦模型中,此方法雖然降低了數(shù)據(jù)的稀疏性，但是沒有考慮熱門項目對推薦效果的影響。文獻[13]使用標準差反映用戶評分值的差異度，將離散系數(shù)作為用戶評分傾向相似性的判斷依據(jù)，從而避免項目自身屬性對計算相似度的影響。文獻[14]主要從完全和非完全冷啟動問題進行探討，首先根據(jù)用戶與項目之間的聯(lián)系去構建關系網(wǎng)絡，然后通過關系網(wǎng)絡去挖掘近鄰用戶的選取方法，最終融入到協(xié)同過濾算法。文獻[15]考慮兩個用戶共同評分的平均差異，以及對項目的偏愛程度，設計了一個可以充分利用用戶有限的評分信息的相似度計算模型，從而提高推薦性能。

該文綜合考慮了項目熱門度和評分矩陣稀疏性兩方面因素，提出一種結合熱門度修正因子與置信度的協(xié)同過濾推薦算法(Popularity Correction Factor and Confidence Collaborative Filtering，PCFCCF)，該算法的優(yōu)勢在于:

(1)通過將熱門度修正因子引入到協(xié)同過濾算法，可以很有效地削弱熱門項目對推薦結果造成的影響，一個項目的熱門程度可以通過用戶對此項目所發(fā)出正向反饋的次數(shù)來表示；

(2)通過融入置信度度量函數(shù)可以很好地克服用戶間共同評分的項目比較稀少的情況；

(3)最終相似度計算公式通過將上述改進的相似度計算公式按照權重進行融合，使得在為用戶生成推薦時，既考慮了熱門項目對預測評分的影響，又考慮了稀疏度對推薦效果的影響。

1 傳統(tǒng)的協(xié)同過濾算法

1992年，隨著協(xié)同過濾算法的提出，它所應用的領域也越來越廣泛，此算法的核心思想是通過建立用戶行為數(shù)據(jù)模型進而推薦給用戶所感興趣的項目。推薦算法可以解決如領域、圖、關聯(lián)規(guī)則和知識等相關方面的問題，其中在領域這個層次更具有拓展性。推薦算法主要包括三個步驟，首先是用戶評分數(shù)據(jù)模型的建立，其次是尋找與目標用戶相似的用戶集合，最后根據(jù)評分產(chǎn)生相關推薦。

1.1 用戶模型的建立

用戶可以通過不同的形式向后臺反饋相關的數(shù)據(jù)，因此，第一步需要將用戶所反饋的數(shù)據(jù)進行預處理。建立一個m×n的矩陣S(m,n)來表示用戶對項目的行為信息，其中m表示用戶的數(shù)量，n表示項目的數(shù)量，sij表示用戶i對項目j的評分值。sij評分值越高，說明用戶對此項目的喜愛度越高，用戶評分矩陣如式(1)所示：

(1)

1.2 尋找近鄰集合

用戶間的相似性可以運用如下幾個相似度計算公式所求值去度量，從而篩選出相似性較高的用戶集合。

1.2.1 余弦相似度

a、b分別代表兩個用戶的評分向量，計算出來的余弦值與用戶之間的相似度成正比，如式(2)所示：

(2)

1.2.2 皮爾遜相似度

(3)

式中，rai、rbi分別為用戶a、b對項目i的各自評分，此式取值范圍為[-1,1]。

1.2.3 修正余弦相似度

通過對皮爾遜相似度進行改進得到修正余弦相似度，二者的區(qū)別是分母中心化的方式不同，如式(4)所示。

(4)

式中，rai、rbi分別為用戶a、b對項目i的各自打分，Ia、Ib分別為兩位用戶各自評分項目的集合；

1.3 產(chǎn)生推薦

通過相似度計算公式獲取近鄰集合，然后利用式(5)對未評分的項目預測其評分值，最終將預測分數(shù)按照從大到小進行排序，取評分較高的前N個項目推薦給用戶。

(5)

2 算法改進

隨著用戶評分的項目越來越多，使得所建立的用戶-項目數(shù)學模型的評分矩陣的稀疏性也可能會越來越大。雖然一些傳統(tǒng)的協(xié)同過濾算法已在很多應用場景得到廣泛應用，但是通過傳統(tǒng)算法去尋找精確度相對較高的近鄰集合還是存在著一些壁壘。接下來介紹了傳統(tǒng)協(xié)同過濾算法存在的一些問題以及對其改進之處。

2.1 評分數(shù)據(jù)稀疏性的問題

評分數(shù)據(jù)稀疏性是影響推薦系統(tǒng)性能的問題之一。由于每位用戶的喜好不同，他會對不同的項目進行評分，從而得到一個稀疏性較大的評分矩陣，就好比用戶A只對一個感興趣的項目評分，用戶B評分項目比較多，而且用戶B所評分的項目恰好包括了用戶A所評分的項目。通過傳統(tǒng)的相似性計算公式計算出二者的相似性會很高，得到的推薦項目也不能很好地反映用戶的真實喜好，相應的推薦質量也會很差。考慮到Jaccard函數(shù)[17]可以描述集合間相似性這一特性，選取其作為置信度的度量函數(shù)，如式(6)所示。

(6)

式中，I(a)、I(b)代表用戶a、b各自所評分項目的集合；用戶共同評分的項目和評分項目的總和通過兩個集合的交集和并集來表示。

將式(6)引入到修正余弦相似度計算公式中，得到改進后的相似度計算公式，如式(7)所示：

(7)

simi1(a,b)在一定程度上緩解了用戶間評分矩陣稀疏性較大的問題，使得推薦的項目更滿足用戶的需求。

2.2 項目熱門度差異

隨著課外補習班的蓬勃發(fā)展，家長們需要在形形色色的課程中做出選擇，大多數(shù)家長可能為了提升孩子學習成績選擇語數(shù)英這類主課，還有一部分家長想為孩子選擇一些課外興趣課程，如美術、音樂等，然而推薦的課程表會出現(xiàn)選擇次數(shù)較多的語數(shù)英這類主課，而這些課程并不能代表家長的意愿。因此，如果運用傳統(tǒng)的協(xié)同過濾算法會很難探索到目標用戶真實的需求。此類問題就是某項目被很多用戶評價次數(shù)過多而算法未做相應的處理導致的。為了更好地規(guī)避這種情況帶來的問題，該文通過在皮爾遜相似度計算公式中引入熱門度修正因子來抑制熱門項目對推薦效果產(chǎn)生的影響，如式(8)所示。

(8)

式中，N(i)表示項目i出現(xiàn)的次數(shù)。通過此式可以分析出當N(i)值越大時，相應的p(i)會越小，從而對熱門度相對較高的項目起了抑制效果。因此，引入該因子到皮爾遜相似度計算公式中，如式(9)所示：

(9)

式中，p(i)是衡量項目i的熱門度修正因子，公式加入該因子后的算法可以弱化此類問題，使推薦的結果更為精確。

2.3 改進相似度計算模型

綜合考慮2.1、2.2小節(jié)所述，為了更好地減少此類問題對推薦效果的影響，最終將式(7)和式(9)所得到的相似度計算公式按照w，(1-w)的權重進行融合，得到如式(10)所示的最終的相似度計算公式。

Tsim(a,b)=wsimi1(a,b)+(1-w)simi2(a,b)

(10)

其中，w∈[0,1]代表融合兩種相似度計算的權重， Tsim(a,b)代表最終用戶相似度計算公式，通過該式求出的值越大，說明兩位用戶之間的相似性也越高，喜好也越接近，使得最終的推薦結果也符合用戶的興趣。

2.4 改進后算法的流程

該文在原有的推薦流程中引入熱門度修正因子和置信度系數(shù)，不但可以削弱熱門產(chǎn)品造成的影響，還可以降低用戶評分矩陣的稀疏性對推薦性能的影響。改進后算法的流程如圖1所示。

圖1 改進后的算法流程

改進后的算法主要包括如下幾個步驟：(1)從訓練集中提取用戶對項目的評分數(shù)據(jù)進行預處理；(2)構建用戶評分矩陣數(shù)學模型；(3)按照一定的權重引入熱門度修正因子和置信度度量函數(shù)去計算用戶最終相似度，進而產(chǎn)生近鄰集合；(4)將式(10)帶入到式(5)預測目標用戶對測試集項目的評分prea,i；(5)將評分數(shù)值從高到低進行排序，選擇前N個項目推薦給目標用戶。

上述的步驟3是整個推薦算法的核心部分，與傳統(tǒng)協(xié)同過濾算法選擇鄰居用戶不同，該算法是融合了熱門度修正因子和置信度函數(shù)兩個參數(shù)去研究近鄰集合。

2.5 算法分析

文中在計算基于熱門度修正因子相似度以及基于置信度相似度時，只是在傳統(tǒng)的相似度計算公式乘以相應的因子，并沒有做一些復雜的運算，因此，文中的相似度計算方法與傳統(tǒng)的相似度計算方法的復雜度都為O(n2)。在沒有提升算法復雜度的同時，很好地提高了推薦的性能。

3 實驗及結果分析

3.1 實驗數(shù)據(jù)集

該文主要使用MovieLens數(shù)據(jù)集對改進的算法進行實驗研究，其中該數(shù)據(jù)集主要包括用戶信息表、電影名稱表以及評分記錄表，共包含了1 682部電影，有943個用戶對電影做出的100 000條評分記錄，本次實驗訓練集與測試集的配比為7∶3。

3.2 評價標準

該文使用平均絕對誤差[18](Mean Absolute Error，MAE)作為評估推薦性能指標之一，其原理是將實驗的理論值與實際結果之間的絕對誤差的平均值作為度量結果，推薦性能的優(yōu)劣與MAE值成反比，計算方法如式(11)所示：

(11)

對于測試集T中的用戶a和項目i，用戶對項目的真實打分用ra,i表示，qa,i為計算所得的預測分數(shù)，n表示用戶所評分項目的數(shù)量。

準確率[19](precision)作為衡量推薦系統(tǒng)性能的重要指標之一，其計算公式如式(12)所示，其精度越高，推薦性能就越好。

(12)

式中，R(u)表示對用戶u推薦項目的個數(shù)；T(u)表示測試集中用戶u喜歡項目的集合。

3.3 實驗結果

3.3.1 改進相似度有效性的驗證

文中算法在修正余弦相似度計算公式中引入置信度度量函數(shù)，以及將熱門度修正因子引入到皮爾遜相似度中，因此需要驗證這一步驟的有效性。文獻[20]將Jaccard函數(shù)引入到皮爾遜相似度計算中，將此改進公式用J-PCOS表示其運算的結果，其中PES、ACOS、J-ACOS、P-PES分別表示相似度計算公式(3)、(4)、(7)、(9)的運算結果。選取近鄰集合k在[5,50]取值，步長為5，評價指標參考MAE值。對比結果如表1所示，繪制如圖2所示。

表1 引入變量后不同相似度計算公式的MAE

圖2 引入變量后不同相似度計算公式MAE對比

從圖中可以看出，改進的相似度計算公式的MAE都有所降低，因此說明了相似度計算公式中引入這兩個因子是有效的。當k<15時，改進公式的MAE下降幅度較大，當k>30時，兩個改進公式的效果相差不大，其MAE趨于平穩(wěn)。并且由圖2可知，當k=25時，改進的相似度計算公式在此數(shù)據(jù)集中計算的MAE取得最小值。

3.3.2 確定權重因子w

由圖2可知，在k=25情況下，改變公式(10)中的w的值，在(0,1)區(qū)間內選擇步長為0.1進行取值，對比不同的w計算出來MAE值，如表2所示，繪制如圖3。

表2 不同權重因子(w)對應的MAE

如圖3所示，在w取[0.1,0.2]時，最終改進的相似度計算方法的MAE隨著w值的增大而減小，之后隨著w值的增大，其值也不斷增大，因此當w為0.2時，MAE取最小，算法效果最好。

圖3 不同權重因子(w)對應的MAE

3.3.3 不同相似度計算方法之間的對比

為了更好地檢驗改進算法的效果，將改進的算法與文獻[11-13]提出的算法以及傳統(tǒng)的協(xié)同過濾算法(余弦相似度)進行對比實驗。結果如圖3所示，將w=0.2代入最終的相似度計算公式中，近鄰數(shù)從5開始，間隔為5直到50為止，分析比較不同的近鄰人數(shù)與MAE值以及算法準確率之間的關系。如表3所示。

表3 五種算法在MovieLens數(shù)據(jù)集上的對比

結果如圖4所示，此圖表示不同近鄰個數(shù)五種算法MAE值的對比，當鄰居數(shù)目在不斷增加時，改進算法的MAE值先呈現(xiàn)下降趨勢，然后逐漸趨于平穩(wěn)。出現(xiàn)這種情況的原因是隨著近鄰集合的增加，推薦過程中所參考的用戶數(shù)目也在增多，因此推薦的精確性也會上升。當鄰居數(shù)目k為25時，改進算法的MAE取最小值，并且后半段在鄰居數(shù)目為40、50處與文獻[13]算法的MAE值比較接近，雖然其他四種算法的MAE值在隨著近鄰個數(shù)增加時，整體趨勢在減小，但是改進算法整體上的MAE值都小于其他四種相似度計算方法。

圖4 不同算法之間MAE的比較

圖5也證明了該算法顯著的改進效果。從圖中可以清晰地看出，隨著鄰居數(shù)目的增加，改進算法的準確率也逐漸上升，當鄰居數(shù)目大于20時其準確率趨于平穩(wěn)，盡管當近鄰數(shù)目為30時準確率有所下降，但是改進算法的準確率都高于其他四種算法。

圖5 不同算法準確率的對比

4 結束語

主要從兩個方面分析傳統(tǒng)協(xié)同過濾算法在推薦過程中出現(xiàn)的問題，并對用戶相似度計算公式進行相應的改進，考慮到由于用戶喜好不同，打分項目也不盡相同，評分矩陣稀疏性會偏大，因此引入置信度函數(shù)，由于熱門項目也會對推薦性能有影響，又引入熱門度修正因子。提出了一種融合熱門度修正因子和置信度的協(xié)同過濾算法，通過控制兩種相似度計算公式的權重，得到最終的相似度計算公式。據(jù)實驗對比分析，改進算法的平均絕對誤差(MAE)相應減小，推薦性能有了明顯的改善，并且融合權重后的算法的準確率也有所提升，因此該算法的改進效果是顯而易見的。但是在對該算法改進的同時，并沒有充分考慮到用戶的興趣會伴隨著時間的變化而變化這一問題，也就是時間因子對相似度的影響，接下來需要在此方面做進一步研究。