基于項(xiàng)目屬性與數(shù)據(jù)權(quán)重的協(xié)同過濾推薦算法

張新猛，李 松

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

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

1 基本算法描述

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

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

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

余弦相似性

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

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

相關(guān)相似性

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

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

修正的余弦相似性

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

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

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

2 改進(jìn)算法描述

2.1 考慮屬性相似性的項(xiàng)目相似度計(jì)算方法

本文采用了對項(xiàng)目的評分相似性和類別相似性組合的方法來計(jì)算項(xiàng)目的相似性，則：

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

2.1.1 項(xiàng)目的類別相似性

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

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

2.1.2 項(xiàng)目的評分相似性

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

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

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

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

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

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

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

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

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

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

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

過程：

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

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

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

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

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

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

3.1 試驗(yàn)數(shù)據(jù)集

本文采用MovieLens站點(diǎn)提供的數(shù)據(jù)集（http：// movielens.umn.edu），MovieLens是一個基于Web的研究型推薦系統(tǒng)，用于接收用戶對電影的評分并提供相應(yīng)的電影推薦列表。目前該Web站點(diǎn)的用戶已經(jīng)超過43000人，用戶評分的電影超過3500部。隨機(jī)抽取其中100000個評價(jià)數(shù)據(jù)，包含了943名用戶對1682部電影的評價(jià)，并要求每一用戶至少對20部電影進(jìn)行了評價(jià)，評價(jià)值為1～5的整數(shù)，數(shù)值越高，表明用戶對該電影的偏愛程度高。還整理出這1682部電影的19個屬性的描述矩陣A（數(shù)據(jù)由0和1表示，0表示不具有該屬性，1則表示具有該屬性）。屬性項(xiàng)如下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 試驗(yàn)的度量指標(biāo)

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

3.3 試驗(yàn)結(jié)果

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

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

從表1和圖1可以看出當(dāng)取值接近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

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

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

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

表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

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

4 結(jié)語

本文針對協(xié)同過濾算法中存在的稀疏性以及不能及時反映用戶意向變化的問題，提出了結(jié)合考慮屬性相似性的項(xiàng)目相似度計(jì)算方法與數(shù)據(jù)權(quán)重WS相結(jié)合的一種相似性計(jì)算方法。對比實(shí)驗(yàn)表明，改進(jìn)的算法可以更好地解決評分矩陣的稀疏性并且同時能夠更有效地捕捉用戶意向，因此推薦精度更高。未來的工作方向是如何更充分的利用項(xiàng)目屬性信息，以及動態(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].軟件學(xué)報(bào)，2009（2）：350-362.

[4]王繼成，潘金貴，張福炎.Web文本挖掘技術(shù)研究[J].計(jì)算機(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]刑春曉，高風(fēng)榮，戰(zhàn)思南，等.適應(yīng)用于興趣變化的協(xié)同過濾推薦[J].計(jì)算機(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.