朱彥松,竇桂琴

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

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

朱彥松,竇桂琴

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

其中的項(xiàng)目i、j為兩個m維的用戶向量。

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

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

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

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

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

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

3.1 改進(jìn)的算法

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

(1)

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

(2)

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

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

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

(3)

(4)

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

(5)

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

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

(6)

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

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

(7)

3.2 改進(jìn)算法的實(shí)現(xiàn)

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

輸出：產(chǎn)生目標(biāo)用戶uT的M個推薦項(xiàng)目。

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

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

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

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

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

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

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

3.3 算法分析

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

5 結(jié)束語

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

附中文參考文獻(xiàn)：

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

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

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

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

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

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

竇桂琴(1979),女,山西洪洞人，碩士，講師，研究方向?yàn)檐浖こ毯陀嬎銠C(jī)仿真。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

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

TP311.13

：A

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

朱彥松(1979),男,河南漯河人，碩士，講師，研究方向?yàn)檐浖こ毯陀嬎銠C(jī)仿真。E-mail:33725032@qq.com

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

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