基于資源類的時間加權協作過濾算法

摘 要：當前e-Learning作為一種重要的教學方式，對其個性化的要求正在日益提高。針對協作過濾推薦是當今應用最為普遍的個性化推薦算法，而數據的稀疏性和算法的可擴展性一直是協作過濾算法所面臨的兩大問題，提出基于資源類的時間加權協作過濾算法。該算法不僅降低了數據的稀疏性和維度，縮小了目標用戶最近鄰的查找范圍；而且避免了傳統推薦算法中推薦值與用戶相似度不密切相關的弊端，提高了最近鄰的準確度，推薦精度較以往傳統算法有明顯提高。

關鍵詞：個性化推薦；協同過濾；相似度；聚類

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695(2009)06-2107-03

doi:10.3969/j.issn.1001-3695.2009.06.032

Time weighted collaborative filtering algorithms based on resources category

ZHANG Jiong，LI Hua

(School of Computer Science， Chongqing University， Chongqing400044， China)

Abstract:Currently e-Learning as an important teaching methods，its individual requirements are increasing.Collaborative filtering is the most common application of personalized recommendation algorithm now， but the sparsity of data and the scalability of algorithm has been a collaborative filtering algorithms faced by the two main issues.Proposed a time weighted collaborative filtering algorithm based on resources category，which not only reduced the data sparsity and dimensionality， and narrowed the area of the nearest neighbor， but also avoided the defects of the traditional recommended method.Key words:personalized recommendation;collaborative filtering;similarity;clustering

隨著Internet的迅速發展和全球對終身教育的需求，以異步教育方式為主要特征的e-Learning正成為Internet上的一種重要應用，同時e-Learning系統的個性化推薦越來越受到重視引起越來越多研究者的關注。個性化推薦是指根據用戶的興趣特點，向用戶推薦其感興趣的信息。目前常用的個性化推薦技術有：協同過濾推薦、基于內容的推薦、基于關聯規則的推薦、基于Bayesian網絡技術的推薦、基于Horting圖技術的推薦。其中協同過濾推薦是目前應用最廣泛、最成功的推薦技術。但目前傳統協同過濾推薦存在數據高維稀疏和興趣失效性的問題，往往導致不準確的推薦。

本文在傳統協同過濾算法的基礎上，針對當前協同過濾算法所存在的一些問題和不足，同時結合現代e-Learning學習所固有的特征，提出了一種新的基于資源類的時間加權協作過濾算法。通過實驗表明，較傳統協同過濾算法，該算法在一定程度上解決了存在的問題和不足，提高了資源推薦的準確性。

1 協同過濾推薦

協同過濾推薦技術是推薦系統中應用最早和最為成功的技術之一。它一般采用最近鄰技術，利用用戶的歷史喜好信息計算用戶之間的距離；然后利用目標用戶的最近鄰居用戶對商品評價的加權評價值來預測目標用戶對特定商品的喜好程度，系統根據這一喜好程度來對目標用戶進行推薦。

協同過濾推薦技術是知識獲取的一種方式，是從可利用的知識源中抽取形式化知識的過程。協同過濾推薦技術的理論基礎是人們的從眾行為，主要利用群體的觀點為當前活動用戶產生推薦項目，其強調一種人與人之間的合作^[1]。

它是基于這樣的假設：為一用戶找到他真正感興趣的內容的好方法是首先找到與此用戶有相似興趣的其他用戶，然后將他們感興趣的內容推薦給此用戶。其基本思想非常易于理解，在日常生活中，人們往往會利用好朋友的推薦來進行一些選擇。協同過濾正是將這一思想運用到個性化推薦系統中來，基于其他用戶對某一內容的評價來向目標用戶進行推薦。

2 基于資源類的時間加權協作過濾推薦算法

雖然協同過濾作為一種典型的推薦技術有其相當的應用，但協同過濾仍有許多的問題需要解決。數據的稀疏性和算法的可擴展性一直是協作過濾算法所面臨的兩大問題。由此提出基于資源類的時間加權協作過濾算法^[2]，該算法采用了協作式過濾與聚類相結合的推薦技術。與以往的基于資源的協作過濾推薦算法相比，該算法的改進：a）用戶對資源的評價從單個資源喜好變為對一個資源類的喜好，這樣既可以大大降低數據的緯度和稀疏程度，又可以擴大資源推薦的范圍；b）考慮時間對興趣的影響加入了時間加權函數^[3]。

2.1 資源項目分類

資源項目分類的方法有很多，基于傳統技術的分類方法主要包括支持向量機(SVM)、K近鄰(KNN)、決策樹、基于關聯規則的、基于數據庫的和貝葉斯分類等算法，當然也可以利用資源已有的分類體系來完成對資源的分類。按照學科知識樹的結構，用資源的學科類別為基礎，以知識單元為一個基本資源類。知識單元是由知識點組成的，知識點是最小的知識單位，每一個資源至少包含一個知識點。根據學習知識的內容相關性，當一個學生學習某一知識點時，他可能對該知識點的相關知識產生興趣，以一個知識單元作為一個最小閉包符合學習規律。

2.2 算法步驟

協同過濾作為一種經典的推薦技術，基于協同過濾技術的個性化學習資源推薦流程如圖1所示。

算法步驟描述如下：

輸入：數據集；

a)對資源項目依所屬知識單元進行分類；

b)將用戶—資源項目評分矩陣轉換為用戶—資源類別評分矩陣；

c)對用戶—資源類別評分矩陣進行加權數據預處理；

d)用戶聚類；

e)計算目標用戶與其他用戶的相似性；

f)選取目標用戶的若干最相似用戶(最近鄰居)，建立最近鄰居集；

g)通過鄰居集計算各資源的推薦度；

輸出：目標用戶的推薦集。

2.3 建立用戶—資源類評分矩陣

隨著資源項目的日益增多，用戶的評分數據卻一般只集中在自己感興趣的領域，前者的增長速度遠遠高于后者，這樣數據的稀疏性就日益突現。雖然資源項目越來越多，但其可以根據自身的內容，劃分為不同的類別，且類別總數還相對比較固定。故而可將用戶—資源項目評分矩陣轉換為用戶—資源類別評分矩陣，這樣就可以大大降低數據的維度和稀疏程度^[4]。由于每項資源依據其內容劃分可能屬于多個不同的類別，在進行矩陣轉換時，可將用戶對每項資源的評分轉換為用戶對其所屬類別的平均評分。假設資源項目被分成X個類別，則可以將用戶—資源項目評分矩陣R(M×N)轉換為用戶—資源類別評分矩陣C(M×X)。矩陣C(M×X)如下所示：

Ci， j=(Ri，1W1+…+Ri，nWn)/n

其中：每項Ci， j表示用戶i對資源項目類別j的評分^[5]；Ri， j表示用戶i對資源項目j的評分；Wj表示資源j的權重；n是用戶i給出同一資源類中評分的資源數。

用戶—資源類評分矩陣C(M×X)為

usercategory

category1…categoryjcategoryx

user1C1，1…C1，j…C1，x

useriC1，1…C1，j…Ci，x

userMCM，1…CM，j…CM，x

考慮到每個用戶評分數據的多少以及頻率等方面的影響，不同用戶對單一資源進行相同操作但是其準確性卻不盡相同，所以對數據進行相應加權處理，具體步驟如下^[6]： signalj=log2(TIFj)-ni=1（ifi， j/TIFj）log2(TIFj/ifi， j)（1）

wi， j=ifi， j*signalj（2）

CW[M×X]=C[M×X]+W[M×X]（3）

式（1）TIFj表示用戶對所有資源的使用次數（包括瀏覽、收藏、下載等行為），ifi， j表示用戶j對資源類i的使用次數；式（2）wi， j是加權矩陣W中用戶j對資源類i權值。

2.4 用戶聚類

由于系統的用戶數目可能會很多，在所有用戶中通過逐個計算相似度來找近鄰是不現實的。為了縮小找近鄰的范圍，降低時間復雜性，系統在找近鄰之前先對所有用戶聚類。常用的聚類算法有很多，各有優缺點。本文結合e-Learning系統的特點，選擇了基于k-中心點的最大距離聚類算法，該算法的最大優點是簡單靈活，能夠動態計算出各個聚類中心^[7]。

2.5 找近鄰

用戶聚類后，根據聚類結果，在一個聚類中心內為用戶找近鄰，從中選取若干最相似的用戶作為最近鄰，這樣減小了計算量，提高了效率^[8]。

為了獲取最鄰近用戶需要計算活動用戶與其他用戶之間的相似度。用戶之間的相似度度量方法有很多種，主要有以下三種方法，即余弦相似性、相關相似性和修正的余弦相似性。

1）余弦相似性

sim(i， j)=cos(i，j)=

i#8226;j/‖i‖2*‖j‖2)=kRi，k/l∈IiR2i，lRj，k/l∈IiR2j，l

2)相關相似性

sim(i， j)=k∈K(Ri，k-i)(Rj，k-j)/k∈K(Ri，k-i)2k∈K(Rj，k-j)2

其中:Ri，k與Rj，k分別表示用戶i和j對項目k的評分；i與j分別表示用戶i和j在各自所有已打分項目上的評分的平均值；K是用戶i與j重合的評分項目。

3)修正的余弦相似性

sim(i， j)=k∈Iij(Ri，k-i)(Rj，k-j)/k∈Iij(Ri，k-i)2k∈Iij(Rj，k-j)2

其中：Iij表示用戶i和j共同評分過的項目集合；Ii和Ij分別表示用戶i和j評分過的項目集合。

修正的余弦相似性度量方法通過減去用戶對項目的平均分來改善余弦相似性方法存在的某些數據孤立點的問題，其次修正的余弦相似性選擇用戶i和j共同評過分的項目作為參與評分的對象，保證了參加計算的數據都是真實的數據。鑒于上述原因本文選擇修正余弦作為用戶相似度計算方法。

2.6 個性化推薦形成

在計算用戶對資源興趣度時，充分考慮到時間效應的影響，即用戶對某一事物的興趣會隨著時間產生變化，一般興趣度和時間成反比，興趣會隨時間慢慢減弱。所以引入時間加權函數f(t)(t為時間變量)到興趣預測中：

Ra， j=i+ni=1sim(a， j)(Ri， j-j)f(t)/ni=1sim(a， j)f(t)（4）

f(t)=e-t(5)

其中：Ra， j為用戶a對資源j的推薦度；n為用戶的近鄰數；sim(a， j)為用戶a與j的相關度；Ri， j為用戶i對資源j感興趣的程度，即用戶i對資源j的權值。時間函數f(t)是單調遞減函數，它隨時間t一直在降低，且時間權值保持在(0，1)內。

3 實驗分析

在本文的研究中，筆者希望最后的算法能夠準確地預測未評價的資源的評價分，從而為用戶作出比較準確的推薦，算法的精確度是評價推薦算法的一個主要指標^[9，10]。平均絕對偏差MAE(mean absolute error)是最常用的一種推薦質量度量方法，通過計算預測用戶評分與實際用戶評分之間的偏差來度量預測的準確性，MAE越小，推薦質量就越高。MAE定義為

MAE=Ni=1|pi-qi|/N

其中：N為測試集大小；pi為預測評分；qi為實際評分。

實驗采用MovieLens(http://movielens.umn.edu)提供的數據集^[5]，包括943位用戶對1 682部電影的100 000條評分數據，每位用戶至少對20部電影進行了評分，所有電影分屬于19種電影類別?；谫Y源類的時間加權推薦算法與一般的協作推薦算法進行比較和分析，取最近鄰居數分別為5、10、15、20、25，對上述兩種算法分別進行實驗測試。實驗結果如圖2所示。

由圖2可知，基于資源類的時間加權推薦算法具有更小的MAE。根據學生學習知識興趣規律的分析，以類別為單位進行資源推薦內容的延展性更好，更符合學生學習需求；另外通過增加時間權值，能隨用戶興趣的轉移發現最近的興趣所在進行推薦，與傳統協同過濾算法相比推薦更具準確性。

4 結束語

本文提出了一種基于資源類的時間加權推薦算法，在對資源項目依內容劃分的基礎上，將用戶—項目評分數據轉換為用戶—資源類別評分數據，對用戶資源興趣度預測中引入時間加權函數。實驗結果顯示，該算法較傳統的協作過濾推薦算法，不僅大大降低了數據的稀疏程度，而且在用戶興趣預測中考慮用戶興趣的變化，把時間加權函數引入到興趣計算公式中，使推薦更加準確。從實驗中發現在對用戶進行不同的聚類時，也影響著算法推薦質量的好壞，所以研究并選取一種更加有效的聚類算法，可以提高推薦算法的信息推薦質量。其次，本文在用戶的個性化方面的支持程度還不夠，對e-Learning用戶的個性特征還需要進一步研究。

參考文獻：

［1］王霞，劉琴.協同過濾在推薦系統中的應用研究[J].計算機系統應用，2005，14(4):24-27.

[2]許建潮，王紅梅.改進的協同過濾算法[J].吉林大學學報，2008，26(1):99-100.

[3]張鋒，常會友.使用BP神經網絡緩解協同過濾推薦算法的稀疏性問題[J].計算機研究與發展，2006，43(4):667-672.

[4]鄧愛林，朱楊勇，施伯樂.基于項目評分預測的協同過濾算法[J].軟件學報，2003，14(9):1621-1628.

[5]潘紅艷，林鴻飛，趙屏.基于矩陣劃分和興趣力差的協同過濾算法[J].情報學報，2006，25(1):49- 54.

[6]SUMIYA T，CHUN J H，LEE S G，et al.A weighted sifting method to improve the effectiveness of collaborative filtering[C]//Proc of IEEE Region 10 Conference on TENCON’04.2004:266-269.

[7]KUO R J，LIAO J L，TU C.Integration of ART2 neural network and genetic K-means algorithm for analyzing Web browsing paths in electronic commerce[J].Decision Support Systems，2005，40(2):355-374.

[8]ZHOU Jun-feng，TANG Xian，GUO Jing-feng.An optimized collaborative filtering recommendation algorithm[J].Journal of Computer Research and Development，2004，14(10):1842-1847.

[9]黃光球，靳峰，彭緒友.基于興趣度的協同過濾商品推薦系統模型[J].微電子學與計算機，2005，22(3):5-8.

[10]郭艷紅，鄧貴仕.協同過濾的一種個性化推薦算法研究[J].計算機應用研究，2008，25(1):39-42.