融合時間上下文的熵驅(qū)動的協(xié)同過濾算法

夏竹青 王竹婷

(合肥學院計算機科學與技術(shù)系， 合肥 230601)

隨著信息量的膨脹，信息過載問題日趨嚴峻，要從龐大的信息中找到自己需要的信息，變得越來越困難。于是，推薦系統(tǒng)[1]應運而生。目前，個性化推薦系統(tǒng)已經(jīng)廣泛應用于電子商務、電子政務和在線學習等在線服務中。推薦系統(tǒng)使用的推薦算法種類很多，應用比較廣泛的是協(xié)同過濾類推薦算法[2-3]。

實踐中，基于內(nèi)存的協(xié)同過濾算法的推薦系統(tǒng)通常面臨2個問題：一是評分差異問題，即兩個用戶對同一個項目的評分差異，在計算相似度時通常被獨立看待，不會考慮兩者的相關(guān)性；二是用戶興趣隨時間變化問題，沒有考慮用戶的興趣會隨時間上下文發(fā)生變化[4]。針對推薦系統(tǒng)的性能問題，學者們已經(jīng)做了一些研究。陳功平等人改進了皮爾森相關(guān)系數(shù)算法，用評分差異懲罰系數(shù)、流行項目懲罰系數(shù)和共同評分項目懲罰系數(shù)調(diào)整評分項的權(quán)重[5]。Lu Jie等人提出了基于模糊集的相似度計算模型，考慮了相對評分差值的影響[6-7]。Yehuda Koren研究了時間上下文對推薦效果的影響，認為用戶近期行為更能反應用戶當前的興趣[8]。張佳等人采用信息熵描述用戶評分分布和傾向程度，以降低數(shù)據(jù)稀疏性對推薦結(jié)果的影響[9]。

在大多數(shù)基于內(nèi)存的協(xié)同過濾算法中，相似度的計算主要取決于絕對評分差值之和。本次研究的出發(fā)點是考慮評分相對差值，采用信息熵度量用戶的相似程度。鑒于用戶興趣會隨時間的推移而發(fā)生變化，引入時間衰減函數(shù)優(yōu)化相似度計算模型，對兩個評分時間間距較大的降低權(quán)重，對時間間距較小的增加權(quán)重，最終形成融合時間上下文的熵驅(qū)動的混合協(xié)同過濾算法，提高算法的推薦準確率。

1 關(guān)于協(xié)同過濾算法的分類

協(xié)同過濾算法是根據(jù)某個分值而產(chǎn)生推薦結(jié)果的。在大多數(shù)基于協(xié)同過濾算法的推薦系統(tǒng)中，這個分值一般用評分表示。推薦系統(tǒng)首先對用戶的興趣進行建模，然后參考已有評分對未評分項做評分預測，推薦過程中不需要項目和用戶的屬性等信息。相比傳統(tǒng)的基于內(nèi)容或基于知識的推薦算法，協(xié)同過濾推薦系統(tǒng)無需理解特定的項目相關(guān)領(lǐng)域的知識，就可以進行推薦。

根據(jù)處理評分的方式的不同，可以把協(xié)同過濾算法分成兩大類：基于內(nèi)存的算法和基于模型的算法?；谀Ｐ偷乃惴ㄊ遣捎靡延械脑u分作為訓練數(shù)據(jù)，去學習確定模型中的參數(shù)值。一旦模型建立了，就可以通過訓練模型對未評分項目做出評分預測?；趦?nèi)存的算法是通過識別用戶或項目的評分模式的相似度來預測評分。由于要將全部已有評分放在內(nèi)存中進行研究和啟發(fā)式學習，因此該類算法被稱為基于內(nèi)存的協(xié)同過濾算法。

1.1 基于內(nèi)存的協(xié)同過濾算法

為追求簡便和高效性，很多推薦系統(tǒng)都采用基于內(nèi)存的協(xié)同過濾算法。該類算法是用一個評分向量去表示用戶的興趣偏好或項目的評分模式，將有相似評分模式的用戶或項目稱為鄰居；用兩個向量間的距離去度量評分模式的相似度，一旦某個用戶或項目的鄰居確定了，就可以通過鄰居們的已有評分去預測未評分項目的評分。基于內(nèi)存的協(xié)同過濾算法最主要的工作就是計算相似度，找出鄰居集和評分預測。

1.1.1 相似度計算

基于內(nèi)存的協(xié)同過濾算法的核心任務就是確定兩個用戶或兩個項目的相似度。用戶或項目的向量不會影響方程式的形式，兩者不用做特別的區(qū)分。余弦公式和皮爾遜公式是最常用的計算相似度的公式，如式(1)和式(2)。

(1)

(2)

當出現(xiàn)極高或極低評分時，余弦相似度沒有考慮用戶的評分習慣；皮爾遜算法則利用與評分均值的偏差來避免這個問題。

1.1.2 評分預測

確定了鄰居集后，就可以根據(jù)鄰居們的已有評分對目標用戶的未評分項進行預測評分。常用的計算公式為：

(3)

預測項的評分接近用戶的評分均值，評分預測結(jié)果就算好。大多數(shù)基于內(nèi)存的協(xié)同過濾算法的相似度的計算都是基于共同評分項目，這點也正約束著它的發(fā)展。當數(shù)據(jù)稀疏或共同評分項目很少時，推進系統(tǒng)的性能就會銳減。為了提高預測性能，克服它的不足，結(jié)合數(shù)據(jù)挖掘、機器學習技術(shù)，研究者提出了基于模型的協(xié)同過濾算法。

1.2 基于模型的協(xié)同過濾算法

基于模型的協(xié)同過濾算法的目標是構(gòu)建一個表示用戶興趣的模型，用模型去預測用戶的未知評分，即通過已有評分去學習和估算參數(shù)值。一旦模型建立，評分數(shù)據(jù)就不再存儲在內(nèi)存中了。大部分模型都和數(shù)據(jù)挖掘、機器學習有關(guān)，常用的有貝葉斯、聚類、圖和隱因子模型等。由于建立和更新模型的計算成本過高，基于模型的協(xié)同過濾算法在實踐中很少被推薦系統(tǒng)所采用。

2 新的協(xié)同過濾推薦算法

我們采用熵驅(qū)動的用戶相似度模型，改進相似度計算的準確度；針對用戶興趣隨時間發(fā)生變化的問題，采用時間衰減函數(shù)對評分差值的權(quán)重進行調(diào)整；然后，用融合時間衰減函數(shù)的熵驅(qū)動的混合相似度模型計算相似度，再進行評分預測。

2.1 熵驅(qū)動的用戶相似度計算

協(xié)同過濾算法中常用Pearson相關(guān)系數(shù)和余弦的相似度計算用戶或項目的相似度，而Pearson相關(guān)系數(shù)比余弦相似度的計算效果要好。要改進推薦系統(tǒng)的效果，關(guān)鍵就在于提高相似度計算的準確率。兩個用戶對同一個項目的評分的差值，代表著某種程度的興趣相似。一般的改進做法是設置各種評分差值的權(quán)重，但往往只是考慮了絕對評分差值。

每個人在表達意見時都有自己的習慣，這意味著他給出的評分通常是在某個特定均值附近。當兩個用戶對同一個項目的評分越接近，可以認為這兩個用戶的相似度越高。我們認為，除了評分間的絕對差值，還需要考慮評分偏離均值的相對差值。如果在極少數(shù)項目上的偏離均值的絕對差值很大，相似度不應該受到較大影響；相反，如果在大部分項目中評分總是不同，即使差距不大，也應該認為兩者的相似度較低。僅根據(jù)極少數(shù)評分的差別，不能判斷兩個用戶是否相似。但如果用戶的評分總是遠離均值，那它就提供了更有區(qū)別力的信息，可以幫助判斷用戶興趣是否相似。用戶如果對一些項目極少評分，我們就沒有足夠的信息去將該用戶的偏好和其他用戶區(qū)分開。相對而言，一個用戶的評分與其他用戶總是會有所不同?；谶@種思想，我們采用項目評分的相對差值的信息熵去度量兩個用戶的相似度，而不是為絕對差值賦予不同權(quán)重。

(4)

(5)

最后，定義基于熵驅(qū)動的用戶相似度計算公式：

(6)

根據(jù)定義和條件，當用戶u和v的評分都相同時，熵相似度為1。因為衡量的是評分的相對偏差，這意味著如果用戶u和v只是各自均值偏差的差值不同，在PCC中的相似度仍可能接近1。

2.2 融合時間衰減函數(shù)的用戶相似度

用戶的興趣隨著時間的推移會發(fā)生變化，兩個用戶對同一個項目產(chǎn)生行為的時間相距越遠，那么這兩個用戶的興趣相似度就可能會越小。例如：某圖書網(wǎng)站用戶A在2015年1月購買了“java入門”，在2016年1月購買了“java設計模式”；用戶B在2017年6月購買了“java入門”，在2018年10月購買了“java設計模式”；用戶C在2015年2月購買了“java入門”，在2015年12月購買了“java設計模式”。不考慮時間的話，推薦系統(tǒng)會認為AB和AC的相似度一樣，而實際上AC的相似度比AB要高。為了解決這個問題，引入時間加權(quán)，對時間間距小的增加權(quán)重，對時間間距大的減少權(quán)重。

(7)

式(7)中，α是時間衰減參數(shù)。數(shù)據(jù)集不同，其取值也不同。如果用戶的興趣變化很快，α的取值應該較大。

融合時間衰減函數(shù)的熵驅(qū)動的用戶相似度，用式(8)計算。

(8)

其中，

融合時間衰減函數(shù)的Pearson相關(guān)系數(shù)，用式(9)計算。

(9)

2.3 混合相似度的計算

綜合考慮Pearson相關(guān)系數(shù)和熵驅(qū)動的相似度，用加權(quán)平均法混合計算用戶之間的最終相似度。

(10)

式(10)中，參數(shù)β是計算用戶u和v的相似度時融合時間衰減函數(shù)的Pearson相關(guān)系數(shù)所占的權(quán)重，它決定了用戶相似度對Pearson相關(guān)系數(shù)和熵驅(qū)動相似度的依賴程度。當β=0時，預測完全取決于Pearson相關(guān)系數(shù)；當β=1時，鄰居集的選擇完全由熵驅(qū)動的相似度算法決定。可以通過實驗來確定β的取值。

到這一步，要去選取跟當前用戶相似度最高的鄰居集。然后，通過這些鄰居集進行評分預測。top-N方法和閾值法是推薦系統(tǒng)中常用的兩種選取鄰居的方法，我們選用top-N方法[8]。

3 算法實驗

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

實驗采用GroupLens小組的Movielens數(shù)據(jù)集ml-100k，對算法的性能進行驗證評估。該數(shù)據(jù)集共有943名用戶對1 682部電影的10萬條評分記錄，分成7組。每條評分記錄包含用戶ID、電影ID、評分值和評分時間。評分值的取值范圍是1～5。在ml-100k的7組數(shù)據(jù)集上做驗證實驗。將每組數(shù)據(jù)集的現(xiàn)有訓練集與測試集合并，然后對合并后數(shù)據(jù)集中的每個用戶的評分記錄按照時間先后排序，選取每個用戶有序評分記錄的前80%的數(shù)據(jù)放入訓練集，剩下的20%作為測試集。

3.2 實驗設計

采用基于用戶的協(xié)同過濾算法，運用余弦相似性(COS)和Pearson相關(guān)系數(shù)(PCC)，基于熵驅(qū)動的混合相似度算法(EP)，融合了時間衰減函數(shù)的熵驅(qū)動的混合相似度算法(TEP)，計算用戶之間的相似度，進行評分預測，比較算法的性能。

為了評估算法的性能，采用平均絕對誤差(MAE)去評估算法的推薦效果。

(11)

3.3 實驗結(jié)果

實驗得到的MAE如圖1所示。圖中，橫坐標對應7個數(shù)據(jù)集的名稱，縱坐標對應的為MAE值。通過EP算法得到的MAE，比其他算法得到的MAE都要小一些，這表明EP算法優(yōu)于其他算法，同時也說明相對差值有時能更準確地描述項目之間的關(guān)聯(lián)程度。

圖1 三種算法的實驗結(jié)果

圖2 EP和TEP算法的實驗結(jié)果

為了說明時間上下文對推薦性能的影響，將融合時間衰減函數(shù)的TEP算法和沒有考慮時間影響的EP算法在7個數(shù)據(jù)集上進行了實驗對比。從圖2可以看出，TEP算法的效果要優(yōu)于EP算法。前面說過，參數(shù)β是調(diào)節(jié)PCC和熵的相似度比例的，參數(shù)α是用來調(diào)節(jié)時間對用戶興趣改變的影響的，時間距離越遠權(quán)重越小。通過實驗測試得出，在此數(shù)據(jù)集上，β=0.7、α=0.4時，效果最優(yōu)。

4 結(jié) 語

在個性化推薦技術(shù)中，協(xié)同過濾算法具有一定優(yōu)勢，同時也存在一定不足。為了改進算法的性能，提出了一種融合時間衰減函數(shù)和信息熵的相似度計算方法，用以分析評分的相對差值。當共同評分項目的數(shù)量較多時，在計算相似度時就對這部分評分賦予更高的權(quán)重。這種算法對少數(shù)的評分差距很大的情形不敏感，但對有持續(xù)差距的情形則很敏感。實驗結(jié)果表明，運用改進算法可以有效提高預測準確率。