朱彥松,竇桂琴

(中原工學院計算機學院,河南 鄭州 450007)

綜合項目權(quán)值分配與時間相關(guān)的協(xié)同過濾模型*

朱彥松,竇桂琴

(中原工學院計算機學院,河南 鄭州 450007)

根據(jù)長尾理論,被反饋次數(shù)少的項目所包含的反饋信息并不少于被反饋次數(shù)較高的,傳統(tǒng)的協(xié)同過濾算法中缺乏考慮冷門項目在最終的項目推薦過程中的影響力,對此,提出了一種改進的協(xié)同過濾推薦模型。通過對冷門項目的分析篩選,在用戶相似性計算時提高冷門項目所占的比重，以體現(xiàn)用戶的個性和興趣。此外,考慮到時間效應的影響,在興趣預測過程中引入時間因子。實驗結(jié)果表明,提出的算法能提高尋找最近鄰居的準確性,從而改善協(xié)同過濾的推薦質(zhì)量。

反饋次數(shù)；協(xié)同過濾；個性化推薦；時間因子

1 引言

根據(jù)用戶對信息的不同需求,個性化推薦系統(tǒng)可通過數(shù)據(jù)篩選和分析得到用戶感興趣的信息內(nèi)容,它往往能從海量信息中提取出用戶最感興趣、最有用的結(jié)果,因此,個性化推薦系統(tǒng)被認為能解決信息超載問題。目前所公認的推薦算法主要包括：協(xié)同過濾推薦算法、基于內(nèi)容的推薦算法、譜分析方法、主元素分析方法以及組合推薦算法等[1]。

協(xié)同過濾(Collaborative Filtering)是一種在推薦系統(tǒng)中廣泛采用的推薦方法,通過計算用戶之間的相似度尋求目標用戶的最鄰近鄰居集合,綜合這些用戶對某一信息的評價后形成目標用戶的推薦集。針對不同的應用需求,專家學者對基本的協(xié)同過濾算法從不同的側(cè)重方面進行了改進。

文獻[2]考慮到由于對未知目標相關(guān)聯(lián)的近鄰對象的分析不夠全面可能影響推薦質(zhì)量,基于動態(tài)規(guī)劃思想提出了一種對推薦子群進行概率分析的方法。文獻[3]在綜合顯性興趣度、隱性興趣度和預測興趣度的基礎(chǔ)上提出了一種基于綜合興趣的協(xié)同過濾方法。文獻[4]設(shè)計了一個基于樸素貝葉斯方法的協(xié)同過濾推薦算法,能根據(jù)應用需求的不同自適應動態(tài)調(diào)整,而無需像其他算法(例如k-NN)那樣需要事先手動設(shè)置參數(shù)。文獻[5]提出一種有效的針對稀疏評分的最近鄰選擇方法,先通過計算用戶間的近鄰傾向性后得到初始近鄰集合,再在該集合的基礎(chǔ)上進行目標用戶與其他用戶相似性比較,然后不斷進行修正后得到最近鄰集合。文獻[6]引入二分網(wǎng)絡來描述個性化推薦系統(tǒng),使用灰色關(guān)聯(lián)度來度量用戶相似性和項目相似性,再通過加權(quán)求和對項目進行預測打分,排序后得到推薦項目列表。

但是，現(xiàn)有的算法在計算用戶的相似性時往往基于用戶共同評價過的項目來計算,而對于項目之間的關(guān)系分析得不夠,對于評分項目的流行度以及在求解相似度時所占的權(quán)重考慮得不夠細致。另外,在推薦過程中往往忽視了用戶評價的時效性特征。這些因素都可能對推薦質(zhì)量造成影響。

2 基于用戶的協(xié)同過濾推薦算法

對于協(xié)同過濾推薦模型來說,應用比較多的方法是基于用戶的算法,通過計算活躍用戶與其他用戶的相似度,選出近鄰子集；再使用鄰居評分進行活躍用戶評分預測；最后對預測結(jié)果進行排序形成Top-N推薦。具體步驟如下：

(1)首先定義一個用戶評分矩陣Rm×n,其中m表示用戶數(shù),n表示評測項目個數(shù),Rij為第i個用戶對第j個項目的評分。

(2)根據(jù)評分矩陣計算用戶之間的相似性。求解用戶相似性的主要方法有余弦相似性、修正的余弦相似性和Pearson相關(guān)系數(shù)等。

①余弦相似性。相似性度量采用向量間的余弦夾角來計算求得。

其中的項目i、j為兩個m維的用戶向量。

②修正的余弦相似性。通過減去用戶評分平均值修正了不同用戶的評分尺度之間的差異性。

③皮爾森相關(guān)系數(shù)(Pearson Correlation Coefficient)。在求解相似性之前先篩選出共同評分的用戶,以提高相似性度量的精確性。

(4)得到最近鄰集合之后,通過以下公式來預測評估用戶對商品i的評分:

3 綜合項目權(quán)值分配與時間相關(guān)的協(xié)同過濾模型

在個性化推薦系統(tǒng)中,如果兩個用戶對某一項目的評分相近,且從項目分類的角度來說,此項目上參與評分的用戶數(shù)量占總體評分人數(shù)比例較大,那么我們可認定該評分項為熱門項目；與之相反則為冷門項目。從現(xiàn)實生活中來看,多數(shù)人對某一問題持相同觀點,說明該評價對象就很難反饋用戶間的理解差異；反之,如果兩個用戶評分相近,而其參與評分用戶數(shù)量相比總參與評分人數(shù)較少,則更能從中找到代表兩用戶獨特的偏好信息,更能真正體現(xiàn)兩用戶間的相似性。顯然,在計算相似性時,將所有項目的被反饋信息不加區(qū)分地設(shè)置為相同的權(quán)重并不合理,易導致馬太效應。即,在推薦系統(tǒng)中,大部分無特定興趣的用戶會對熱門或流行度高的項目評價并反饋,這些項目在推薦系統(tǒng)中會更加熱門；而冷門或流行度低的項目因不易被用戶發(fā)掘,反饋程度差而變得愈加不受關(guān)注。

大多數(shù)算法選擇兩用戶共同評分的所有項目進行用戶之間的相似度的計算,且在用戶共同評分的項目中被反饋程度高的項目和被反饋程度低的項目在相似度計算時所占的比重一樣。而實際上,冷門項目相比熱門項目,其反饋信息更能凸顯用戶的真實興趣度。本文對傳統(tǒng)的協(xié)同過濾算法進行如下改進：首先,通過對冷門項目的分析篩選,在用戶相似性計算時提高冷門項目所占的比重以體現(xiàn)用戶的個性和興趣；其次,考慮到時間效應的影響,在興趣預測過程中引入時間因子。

3.1 改進的算法

(1)根據(jù)m個用戶對n個項目的評價,構(gòu)造用戶評價矩陣R：

(1)

進而,根據(jù)對項目是否進行評價,可以得到反饋信息矩陣,表示為：

(2)

矩陣Q為0-1矩陣,矩陣中qij取值為0或者為1,當用戶ui對項目pj做出反饋,則qij=1；反之,qij=0。

(2)D=QTQ,D為一個n×n的對稱矩陣,對角線上元素djj的值即為第j個評價項目被評價的次數(shù),記為d[j]。

(3)對所有項目的評價次數(shù)進行規(guī)范化,有：norm(d[j])=(d[j]-dmin)/(dmax-dmin), 其中dmax、dmin分別為評價次數(shù)的最大值、最小值。進一步,從評價項目被評價次數(shù)角度得到該評價項目的權(quán)值,有：

(3)

(4)

(5)在計算用戶相似性過程中，本文根據(jù)對項目流行度的分析,引入項目相關(guān)性的權(quán)重。推薦系統(tǒng)中項目相關(guān)性的計算不采用Pearson相關(guān)系數(shù)法,而是采用更客觀的基于項目特征屬性的方法。改進后的用戶相似性計算公式如下：

(5)

得到計算給果后,按照相似性值從大到小排序,前N個用戶構(gòu)成鄰居用戶集合。

(6)時間因子。用戶的評價具有時效性特征,早期評價對于預測值的影響相對要小。目前,多數(shù)推薦系統(tǒng)主要依據(jù)用戶的興趣進行推薦,但系統(tǒng)中早期的評價信息可能會過期失效,導致推薦成功率的下降。為此,我們充分考慮到時效帶來的影響,引入時間加權(quán)函數(shù)C(t)=e-a(t-t0)(t為時間變量)到興趣預測過程中,網(wǎng)絡信息老化繼承了信息老化的經(jīng)典負指數(shù)模型[7]:

(6)

其中,t0表示評價發(fā)布的時間,t表示當前的時間,a代表的是信息老化率系數(shù),C(t)表示信息在t時刻的影響力因子。

(7)最后,在預測評分中加入時間因子,目標用戶uT對未評分項目iT的加權(quán)預測評分TP(uT,pT)進行改進,如公式(7)所示：

(7)

3.2 改進算法的實現(xiàn)

輸入：包括目標用戶uT,最近鄰用戶數(shù)T,評分矩陣R以及待預測項目集IT。

輸出：產(chǎn)生目標用戶uT的M個推薦項目。

步驟1構(gòu)造用戶評價矩陣R得到反饋信息矩陣Q;

步驟2求解D=QTQ,定義一個一維數(shù)組d[j],存放對稱矩陣D對角線元素djj的值；

步驟3根據(jù)公式(3)求得各評價項目的權(quán)值wj；

步驟4對用戶評價矩陣進行歸一化后的矩陣P,計算各用戶評價向量之間的差異系數(shù)φij；

步驟5求解代入差異系數(shù)后的改進的用戶相似性;

步驟6按照相似性值從大到小排序,選取前N個用戶構(gòu)成鄰居用戶集合；

步驟7根據(jù)加入了時間因子的加權(quán)預測評分函數(shù),對目標用戶uT的未評分項目iT進行評分預測。

3.3 算法分析

本文提出的改進算法通過在計算用戶相似性時考慮了流行度不同項目權(quán)重的區(qū)別,盡可能將用戶對冷門項目評價的個性化特質(zhì)凸顯出來,以求推導出的鄰居用戶集更準確。此外,在預測評分過程中,引入時間因子函數(shù),對項目評價從時效上進行了區(qū)分,這對于最終推薦精度的提高起到很重要的作用。

此外,從時間復雜度上來看,算法執(zhí)行的時間開銷主要在于公式(4)、公式(5)和公式(7)中對于用戶相似度的計算,若用戶屬性中有m個數(shù)值型屬性和評價項目n個名稱型屬性,本文中算法時間復雜度保持在O(n2)內(nèi),與文獻[2，3]提出的推薦算法的時間復雜度相同，不會帶來太大的開銷。

4 實驗結(jié)果與分析

為了對改進算法的性能進行驗證,本文以MovieLens網(wǎng)站提供的數(shù)據(jù)樣本進行實驗,根據(jù)評價推薦質(zhì)量的平均絕對誤差標準,從準確率和覆蓋率等方面，與傳統(tǒng)Top-N推薦算法(tradition-CF)[8]和適應用戶興趣變化的協(xié)同過濾算法(interest-CF)[9]進行了對比。實驗中選取的樣本集包含了943名用戶、1 682部電影以及100 000 個評分數(shù)據(jù)。用戶對評價指標分為五個等級，評分取值為從1到5的整數(shù)，評價喜好程度與取值大小成正比。在所有實驗中,推薦數(shù)目N的取值為20,鄰居數(shù)目則在5～80變動。

此外，本文提出的算法與tradition-CF在推薦準確率方面進行了比較,結(jié)果如圖1所示?？梢钥闯?，當最近鄰居節(jié)點數(shù)為30時,本文算法的準確率達到最高,為17.76%,另外兩個算法的準確率分別為17.58%和17.67%。此后,隨著鄰居節(jié)點數(shù)量的增加,準確率呈逐步下降趨勢,本文的算法與其他兩種算法相比較下降得更為平穩(wěn)。

圖2為本文提出的算法與tradition-CF算法以及interest-CF在推薦覆蓋率上的比較。對比隨著最近鄰節(jié)點數(shù)取值的變化，本文算法的覆蓋率稍高,且隨著最近鄰居節(jié)點數(shù)的增加呈線性下降的趨勢,當鄰居節(jié)點數(shù)量為50～80時,覆蓋率基本保持在一個比較窄的區(qū)間內(nèi)變化。

Figure 1 Comparison of the precision rate with different numbers of neighbour nodes圖1 最近鄰居節(jié)點數(shù)不同時的準確率比較

Figure 2 Comparison of the coverage rate with different numbers of neighbour nodes圖2 最近鄰居節(jié)點數(shù)不同時的覆蓋率比較

5 結(jié)束語

在傳統(tǒng)的協(xié)同過濾算法中,冷門項目在項目推薦過程中的影響不易引起重視,但實際上冷門項目上的評分更能突出用戶真正興趣。本文提出了一種綜合項目權(quán)值分配與時間相關(guān)的協(xié)同過濾推薦模型,在用戶相似性計算時提高冷門項目所占的比重以體現(xiàn)用戶的個性化選擇；另外，在興趣預測過程中引入時間因子，以反映項目評分隨時間變化而衰減,以提高尋找最近鄰居時的準確性，并改善協(xié)同過濾的推薦質(zhì)量。

[1] Wang Guo-xia, Liu He-ping. Survey of personalized recommendation system[J]. Computer Engineering and Applications,2012,48(7):66-76. (in Chinese)

[2] Huang Chuang-guang,Yin Jian,Wang Jing.Uncertain neighbors’ collaborative filtering recommendation algorithm[J]. Chinese Journal of Computers, 2010, 33(8):1369-1373.(in Chinese)

[3] Inoue T,Abe S. Fuzzy support vector machines for pattern classification[C]∥Proc of International Joint Conference on Neural Networks(IJCNN’01), 2001:1449-1454.

[4] Wang Ke-bin, Tan Ying. A new collaborative filtering recommendation approach based on naive Bayesian method[C]∥Proc of the 2nd International Conference on Swarm Intelligence(ICSI’2011), 2011:218-227.

[5] Leng Ya-Jun, Liang Chang-yong, Ding Yong, et al. Method of neighborhood formation in collaborative filtering[J]. Pattern Recognition and Artificial Intelligence, 2013,26(10):968-974.(in Chinese)

[6] Li Xia, Li Shou-wei. Research on collaborative filtering algorithm of bipartite network oriented to personal recommendation system[J]. Application Research of Computers, 2013,30(7):1946-1949.(in Chinese)

[7] Blanco-Fernandez Y, Lopez-Nores M, Pazos-Arias J J, et al. An improvement for semantics-based recommender systems grounded on attaching temporal information to ontologies and user profiles[J]. Engineering Applications of Artificial Intelligence, 2011, 24(8):1385-1397.

[8] Hyung Jun Ahn.Utilizing popularity characteristics for product recommendation[J]. International Journal of Electronic Commerce,2006,11(2):59-80.

[9] Xing Chun-xiao,Gao Feng-rong,Zhan Si-nan. A collaborative filtering recommendation algorithm incorporated with user interest change[J]. Journal of Computer Research and Development, 2007, 44(2):296-301.(in Chinese)

附中文參考文獻：

[1] 王國霞,劉賀平. 個性化推薦系統(tǒng)綜述[J]. 計算機工程與應用,2012,48(7):66-76.

[2] 黃創(chuàng)光,印鑒,汪靜. 不確定近鄰的協(xié)同過濾推薦算法[J]. 計算機學報, 2010, 33(8):1369-1373.

[5] 冷亞軍,梁昌勇,丁勇, 等. 協(xié)同過濾中一種有效的最近鄰選擇方法[J]. 模式識別與人工智能,2013,26(10):968-974.

[6] 李霞,李守偉. 面向個性化推薦系統(tǒng)的二分網(wǎng)絡協(xié)同過濾算法研究[J].計算機應用研究, 2013, 30(7):1946-1949.

[9] 刑春曉, 高風榮, 戰(zhàn)思南. 適應用戶興趣變化的協(xié)同過濾推薦算法[J]. 計算機研究與發(fā)展, 2007, 44(2):296-301.

ZHUYan-song,born in 1979,MS,lecturer,his research interests include software engineering, and computer simulation.

竇桂琴(1979),女,山西洪洞人，碩士，講師，研究方向為軟件工程和計算機仿真。E-mail:dou_guiqin@163.com

DOUGui-qin,born in 1979,MS,lecturer,her research interests include software engineering, and computer simulation.

Acollaborativefilteringrecommendationalgorithmcombiningitemsweightallocationandtimedependence

ZHU Yan-song,DOU Gui-qin

(College of Computer,Zhongyuan University of Technology,Zhengzhou 450007,China)

According to the long tail theory,the items with fewer feedbacks do not necessarily contain less information than those with more feedbacks.In the traditional collaborative filtering algorithms,the influences from unpopular items are usually ignored in the process of the eventual recommendation.To address this problem,an improved collaborative filtering recommendation model is proposed.By evaluating the unpopular items analytically,the weight of these items should be improved in calculating users’ similarities,so as to reflect users’ personalities and interests. Moreover,taking into account the impact of the time dependence,the time factor is introduced during the prediction of interests.Experimental results show that the algorithm can raise the accuracy of searching the nearest neighbors,and improve the recommendation quality of the collaborative filtering.

feedback frequency;collaborative filtering;personalized recommendation;time factor

1007-130X(2014)11-2234-05

2014-06-21;

：2014-08-28

河南省教育廳項目(13A520125)

TP311.13

：A

10.3969/j.issn.1007-130X.2014.11.030

朱彥松(1979),男,河南漯河人，碩士，講師，研究方向為軟件工程和計算機仿真。E-mail:33725032@qq.com

通信地址：450007 河南省鄭州市中原西路146號中原工學院西區(qū)計算機學院

Address:College of Computer,Zhongyuan University of Technology,146 Zhongyuan Rd West,Zhengzhou 450007,Henan,P.R.China