張新猛，李 松

（1.天津市體育彩票管理中心，天津 300074；2.河北工業(yè)大學 計算機科學與軟件學院，天津 300401）

協(xié)同過濾算法[2]是時至今日非常成功的一種個性化推薦技術(shù)，在很多領(lǐng)域中得到了應(yīng)用。協(xié)同過濾算法中最重要的一步是相似度的計算方法。傳統(tǒng)的協(xié)同過濾算法在計算相似度時多采用余弦相似性、相關(guān)相似性、修正的余弦相似性等度量方法。以上方法基本都是依據(jù)項目評分進行相似性計算的。但是在現(xiàn)實的評分矩陣中，評分在大多情況下是比較稀疏的，導致單純地依據(jù)評分向量度量相似度效果不佳，導致推薦精度降低。這是傳統(tǒng)的協(xié)同過濾推薦模型存在的一大弊端[3]，評分矩陣的稀疏性問題隨著信息量的急速增加將愈加突出。借鑒基于內(nèi)容的推薦系統(tǒng)[4]，將項目屬性引入到相似性的度量方法中。同時傳統(tǒng)的基于項目協(xié)同過濾算法不能體現(xiàn)用戶意向隨時間的變化，而這一點在個性化推薦中又是極度重要的。本文首先運用考慮項目屬性的相似度計算方法來衡量項目相似度，其次通過反映項目與用戶意向相關(guān)程度的數(shù)據(jù)權(quán)重來調(diào)整評分預(yù)測公式，基于以上兩點得出一種新的協(xié)同過濾算法；新的算法既能解決評分矩陣稀疏時相似性計算不準確的問題，又能表示用戶意向的轉(zhuǎn)移。

1 基本算法描述

基于項目的協(xié)同過濾推薦算法[1]的核心就是通過用戶對目標項最近鄰項的評分產(chǎn)生最后的推薦結(jié)果，用戶對目標項的評分通過用戶對目標項最近鄰項評分的加權(quán)平均值逼近來預(yù)測。推薦過程主要有兩部分：

1）最近鄰查詢：首先計算項目之間的相似度，然后依據(jù)項之間的相似度搜索出目標項的最近鄰集合。

目前計算相似性的方法種類繁多，但使用最多的是下面3種方法：

余弦相似性

項目評分看作為m維用戶空間上的向量，如果用戶對項目沒有進行評分，則將用戶對該項目的評分設(shè)為0，項目間的相似性通過向量間的余弦夾角度量。設(shè)項目i和項目j在m維用戶空間上的評分分別表示為向量i→，j→，則項目i和項目j之間的相似性sim（i，j）為

分子為2個項目評分向量的內(nèi)積，分母為2個項目評分向量模的乘積。

相關(guān)相似性

設(shè)對項目i和項目j共同評分過的用戶集合用Uij表示，則項目i和項目j之間的相似性sim（i，j）通過Pearson相關(guān)系數(shù)度量：

式中：Ru，i為用戶u對項目i的評分；分別表示對項目i和項目j的平均評分。

修正的余弦相似性

在余弦相似性度量方法中沒有考慮不同用戶的評分尺度問題，修正的余弦相似性度量方法通過減去用戶對項目的平均評分改善上述缺陷，設(shè)對項目i和項目j共同評分過的用戶集合用Uij表示，Ui和Uj分別表示對項目i和項目j評分過的用戶集合，則項目i和項目j之間的相似性sim（i，j）為

式中：Ru，i為用戶u對項目i的評分分別表示對項目i和項目j的平均評分。

2）推薦產(chǎn)生：根據(jù)目標User對目標Item的最近鄰居項評分與相似度，得出用戶對目標項的評價的預(yù)測值；取其中排在前面的而且目標用戶中未出現(xiàn)過的前N個項目作為Top-N推薦集。預(yù)測結(jié)果可以按式（4）計算：

2 改進算法描述

2.1 考慮屬性相似性的項目相似度計算方法

本文采用了對項目的評分相似性和類別相似性組合的方法來計算項目的相似性，則：

式中：simrating（i，j）為項目的評分相似性；simattribute（i，j）為項目的類別相似性；λ為用戶對項目的評分在項目相似性計算中的貢獻系數(shù)；1-λ為類別屬性在項目相似性計算中的貢獻系數(shù)。由于項目相似性總是小于等于1，所以作了歸一化處理。

2.1.1 項目的類別相似性

在各種不同的系統(tǒng)中，所提供的項目一般都是以類別進行劃分。如電影網(wǎng)站將所有的電影按照動作片、愛情片等流派進行平行劃分，把由于項目分類的不同而引起的相似性稱為項目的類別相似性。只要獲得項目的類別信息，就可以計算它們的類別相似性。對于項目i與j，其所屬的類別分別表示為集合Ai和Aj。當項目i與j同屬的相同類別越多，則它們的相似性越強。所以，項目i與j的類別相似性可以通過它們的類別集合來計算，表示如下：

式中：Ai∩Aj為項目i與j所屬相同類別的交集的元素個數(shù)；Ai∪Aj為項目i與j所屬類別的并集的元素個數(shù)，二者的比值體現(xiàn)了項目i與j的類別相似程度。

2.1.2 項目的評分相似性

用Ui和Uj的交集表示對項目i與j共同評分的用戶集合，則項目i與j的評分相似性simrating（i，j）可以通過修正的余弦相似性計算[5]：

2.2 數(shù)據(jù)權(quán)重的調(diào)整策略WS

不同時間段的用戶數(shù)據(jù)對預(yù)測目標行為的參考價值顯然是不同的，傳統(tǒng)的協(xié)同過濾算法大多使用某種基于時間的數(shù)據(jù)權(quán)重方法[6]，來反映這種數(shù)據(jù)間的不同；這類方法的核心思想是數(shù)據(jù)權(quán)重隨著用戶訪問時間呈線性或非線性變化，越是近期被用戶訪問數(shù)據(jù)，其權(quán)重越高；即越是近期的訪問數(shù)據(jù)其重要性與參考價值越大。但是這種方法只是片面強調(diào)時間，使得長時間訪問的歷史數(shù)據(jù)權(quán)重較低，從而忽略了歷史數(shù)據(jù)中具有很高參考價值部分的作用，這是一個很大的弊端；而本文引入的基于項目相似度權(quán)重調(diào)整策略WS，這一策略能夠更加全面有效地反映衡量用戶數(shù)據(jù)的參考價值[7]。

WS代表基于項目相似度權(quán)重調(diào)整策略，WS可以用函數(shù)WS（u，i），用WS（u，i）來計算項目i對用戶u評分預(yù)測的權(quán)重。設(shè)Iu為用戶u訪問過的項目集合，定義一個可調(diào)控的時間窗T在時間窗內(nèi)用戶u訪問過的資源集合定義為Iut。對于在時間窗內(nèi)的項目i∈Iu；無論u何時訪問i，如果Iut中有很多項目和i很相似，說明項目i與用戶u近期行為相一致，在對用戶u進行評分預(yù)測時項目i可能會起到比較重要的作用。通過計算i和Iut的總體相似度sim（i，IuT）得到WS（u，i），而WS（u，i）可以用i和IuT中每個資源j的平均相似度來表示：

其中，size（IuT）表示IuT的資源個數(shù)。

2.3 改進后的協(xié)同過濾推薦算法

運用的數(shù)據(jù)權(quán)重WS對傳統(tǒng)評分預(yù)測公式進行調(diào)整得：

其中：C為目標項目的最近鄰集合；cj為集合C中的第j個元素；式（9）的相似度計算方法sim（i，j）采用上文的考慮屬性相似性的項目相似度計算方法，這樣就將項目屬性引入到數(shù)據(jù)調(diào)整策略WS當中，從而使得評分計算方法反映用戶對不同類型信息的興趣度，從而使得算法能夠反映用戶興趣隨時間的變化，同時又能解決傳統(tǒng)算法的冷啟動問題。

引入數(shù)據(jù)權(quán)重WS改進評分預(yù)測公式之后的推薦預(yù)測流程大致如下。首先遍歷目標用戶評分過的項目集合Iu，讀入Iu中每個元素的K最近鄰集以及相應(yīng)的相似度，生成候選推薦集。第二步遍歷Iu中所有資源根據(jù)式（8）計算目標用戶對Iu中第i個項目的數(shù)據(jù)權(quán)重WS（u，i）。最后按照式（9）預(yù)測目標用戶對候選集項目的評分，尋找N個預(yù)測評分最高的項目作為推薦項。推薦集算法的具體描述如下：

輸入用戶u、與之對應(yīng)的己訪問資源集Iu、資源近鄰模型M。

輸出用戶u的top-N推薦集。

過程：

Step1對每個資源i∈Iu，讀取M得到它的k最近鄰居集，合并所有Ni得到集合C；

Step2從C中刪除Iu中己經(jīng)存在的資源，得到候選推薦項集Candidate；

Step3對每個資源i∈Iu，根據(jù)式（8）計算WS（u，i）；

Step4對資源j∈Candidate，運用式（9）預(yù)測用戶u對項目i的加權(quán)評分Pui；

Step5將Candidate中的資源按最終評分Iu大小排列，其中最前的N個資源作為用戶u的推薦集。

3 試驗結(jié)果及分析

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

本文采用MovieLens站點提供的數(shù)據(jù)集（http：// movielens.umn.edu），MovieLens是一個基于Web的研究型推薦系統(tǒng)，用于接收用戶對電影的評分并提供相應(yīng)的電影推薦列表。目前該Web站點的用戶已經(jīng)超過43000人，用戶評分的電影超過3500部。隨機抽取其中100000個評價數(shù)據(jù)，包含了943名用戶對1682部電影的評價，并要求每一用戶至少對20部電影進行了評價，評價值為1～5的整數(shù)，數(shù)值越高，表明用戶對該電影的偏愛程度高。還整理出這1682部電影的19個屬性的描述矩陣A（數(shù)據(jù)由0和1表示，0表示不具有該屬性，1則表示具有該屬性）。屬性項如下IMDb URL|Action|Adventure |Animation|Children’s|Comedy|Crime| Documentary|Drama|Fantasy|Film-Noir|Horror| Musical|Mystery|Romance|Sci-Fi|Thriller|War| Western。

3.2 試驗的度量指標

推薦質(zhì)量常用來衡量一個推薦算法優(yōu)秀與否，在推薦系統(tǒng)中通常認為，如果通過推薦算法得到的結(jié)果能夠和用戶的興趣愛好相符合，能夠達到用戶滿意的程度，那么此推薦系統(tǒng)就會被用戶認可，進而用戶對此推薦系統(tǒng)的信賴度會增加，最終網(wǎng)站的銷售量會大大增加，會形成客戶滿意和網(wǎng)上商家獲益的一種雙贏局面。因此推薦算法的優(yōu)劣直接關(guān)系到整個電子商務(wù)系統(tǒng)的好壞。目前學術(shù)界在評定推薦算法優(yōu)劣時，通常把平均絕對偏差MAE（mean absolute error）作為指標[8]。平均絕對偏差是計算實際評分值與系統(tǒng)中使用的推薦算法得到的預(yù)測評分值之間的差值來反映算法的準確性，方法為

3.3 試驗結(jié)果

本文設(shè)置2組對比試驗，分別驗證本文算法在解決用戶評分矩陣稀疏性和用戶興趣轉(zhuǎn)移上的先進性。

試驗1由于λ為設(shè)定的可調(diào)節(jié)的基于2種來源的項目相似度平衡因子，所以λ取值可能會對推薦精度有影響。所以在該實驗中λ取值從0～1.0，每次增加0.1，觀察MAE的變化。數(shù)據(jù)集分為訓練集（占80%）和測試集（占20%）。此組試驗在該數(shù)據(jù)集中提取記錄包括450個用戶和2954部電影、共69988條記錄、本試驗中數(shù)據(jù)集的稀疏度為94.734%。

從表1和圖1可以看出當取值接近0.6時推薦效果較好。

表1 平衡因子λ與對相應(yīng)MAE表Tab.1 Balance factor λ and corresponding MAE value

圖1 平衡因子λ變化對推薦因子的影響Fig.1 Influence of the change of balance factor λ on the recommendation factor

試驗2將其中80%的數(shù)據(jù)作為訓練集，剩下的20%為測試集。此數(shù)據(jù)集記為數(shù)據(jù)集A，試驗2需要驗證本文算法在解決稀疏性問題上的改進。算法2代表基于考慮項目屬性與評分相似度計算的改進算法，算法1代表傳統(tǒng)基于項目的協(xié)同過濾算法。此組試驗在該數(shù)據(jù)集中提取記錄包括450個用戶和2954部電影、共69988條記錄、本試驗中數(shù)據(jù)集的稀疏度為94.734%。

從表2和圖2可以看出綜合考慮項目屬性與評分的相似度計算方法能夠有效緩解數(shù)據(jù)稀疏性并改善推薦性能。

試驗2驗證了本文算法在解決稀疏性問題上的改進。試驗3需要驗證本文算法在解決用戶興趣轉(zhuǎn)移上的改進。本組試驗將其中80%的數(shù)據(jù)作為訓練集，剩下的20%為測試集。此數(shù)據(jù)集記為數(shù)據(jù)集B。為了避免數(shù)據(jù)稀疏性問題的發(fā)生，B組試驗在數(shù)據(jù)集中提取記錄時，要求每個用戶最少為60部電影評過分并且每部電影最少被60個用戶評過分，最終提取的數(shù)據(jù)集包括45個用戶，275部電影，其中時間跨度為30天，共4666條記錄。算法2為只改進相似度計算算法，算法3為在算法2上引入數(shù)據(jù)權(quán)重WS的改進算法。

表2 算法1與算法2MAE值隨最近鄰變化表Tab.2 Algorithm 1 and algorithm 2MAE value changes with the nearest neighbor

圖2 算法1與算法2性能比較Fig.2 Performance comparison of algorithm 1 and algorithm 2

表3 算法2與算法3MAE值隨最近鄰變化表Tab.3 Algorithm 2 and algorithm 3MAE value changes with the nearest neighbor

圖3 算法2與算法3的推薦性能比較Fig.3 Comparison of the recommended performance of algorithm 2 and algorithm 3

可見改進算法不但在數(shù)據(jù)較稀疏的情況下效果比傳統(tǒng)算法效果明顯改善，而且隨著訓練集數(shù)據(jù)的增多，本文算法能夠有效體現(xiàn)用戶的興趣變化。所以本文所提出的協(xié)同過濾算法在解決數(shù)據(jù)稀疏性問題，同時反映用戶興趣變化。

4 結(jié)語

本文針對協(xié)同過濾算法中存在的稀疏性以及不能及時反映用戶意向變化的問題，提出了結(jié)合考慮屬性相似性的項目相似度計算方法與數(shù)據(jù)權(quán)重WS相結(jié)合的一種相似性計算方法。對比實驗表明，改進的算法可以更好地解決評分矩陣的稀疏性并且同時能夠更有效地捕捉用戶意向，因此推薦精度更高。未來的工作方向是如何更充分的利用項目屬性信息，以及動態(tài)調(diào)整反映用戶意向的時間窗口來更好反映用戶意向變化，提高推薦質(zhì)量。

[1]Starwar B，Karypis G，Konstan J，et al.Item-based collaborative filtering recommendation algorithms[C]//Proc of the 10th Int’l World Wide Web Conf.New York：ACM Press，2001：285-295.

[2]Goldberg D，Nichols D，Oki B M，et al.Using collaborative filtering to weave an information tapestry[J].Communications of the ACM，1992，35（12）：61-70.

[3]許海玲，吳瀟，李曉東，等.互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J].軟件學報，2009（2）：350-362.

[4]王繼成，潘金貴，張福炎.Web文本挖掘技術(shù)研究[J].計算機研究與發(fā)展，2000（5）：513-520.

[5]Robin Burke.Hybrid recommender systems：survey and experiments[J].User Modeling and User-Adapted Interaction，2002：124.

[6]Gediminas Adomavicius，Alexander Tuzhilin，et al.Toward the next generation of recommender systems：a survey of the stateof-the-art and possible extensions[J].IEEE Transactions on Knowledge and Data Engineering，2012，17（6）：375-386.

[7]刑春曉，高風榮，戰(zhàn)思南，等.適應(yīng)用于興趣變化的協(xié)同過濾推薦[J].計算機研究與發(fā)展，2007，44（2）：296-391.

[8]Herloker J I，Konstan J A，Terveen L G.Evaluating calla6arative filtering recommender systems[J].ACM Transactions on Information System，2004，22（1）：5-53.