蘇凡軍,唐啟桂

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上?！?00000)

SBHCF:基于奇異值分解的混合協(xié)同過(guò)濾推薦算法

蘇凡軍,唐啟桂

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海200000)

摘要針對(duì)傳統(tǒng)協(xié)同過(guò)濾中的最近鄰查找不夠合理導(dǎo)致推薦的準(zhǔn)確率較低的困境。提出一個(gè)基于矩陣分解的混合相似度算法。該方法融合了基于模型的奇異值矩陣分解算法和基于近鄰的協(xié)同過(guò)濾算法皮爾遜相關(guān)系數(shù),并引入閾值和杰卡德系數(shù)對(duì)相似度進(jìn)行修正。在公共有效數(shù)據(jù)集上的實(shí)驗(yàn)表明,所提出算法的平均絕對(duì)誤差比傳統(tǒng)的推薦算法至少降低了7.7%,有效提高了推薦準(zhǔn)確率。

關(guān)鍵詞協(xié)同過(guò)濾;奇異值矩陣分解;杰卡德系數(shù);皮爾遜系數(shù)

SU Fanjun,TANG Qigui

(School of Optical-Electrical and Computer Engineering,University of Shanghai for

Science and Technology,Shanghai 200000,China)

AbstractThe traditional CF recommendation algorithms are poor in accuracy because of its irrational neighbor-retrieve.In this paper,an SVD-based hybrid collaborative filtering algorithm is proposed to solve the challenge.The method combines SVD model-based CF algorithm and PCC memory-based CF algorithm.Several parameters and JACCARD are introduced to revise the similarity.The experiment in the public data set proves that the SBHCF algorithm effectively improves the recommendation accuracy with a reduced MAE by at least 7.7% than the traditional CF algorithm.

Keywordscollaborative filtering;singular value matrix factorization;Jaccard coefficient;Pearson coefficient

大數(shù)據(jù)時(shí)代的用戶數(shù)目和物品數(shù)目增長(zhǎng)至高維狀態(tài),實(shí)際應(yīng)用過(guò)程中用戶的評(píng)分?jǐn)?shù)據(jù)又相當(dāng)稀疏,這使得單純從數(shù)據(jù)集和中度量用戶相似性的準(zhǔn)確率不高,進(jìn)而導(dǎo)致推薦的準(zhǔn)確率低下和用戶體驗(yàn)性差[1-2]。為應(yīng)對(duì)這個(gè)挑戰(zhàn),研究者進(jìn)行了大量研究[3-6]。盡管這些工作有了較大成果,但依然存在不足,文獻(xiàn)[3]和文獻(xiàn)[4]主要的思想是基于鄰域的協(xié)同過(guò)濾,在數(shù)據(jù)集中直接尋找相似用戶,效率相對(duì)低下;文獻(xiàn)[5]和文獻(xiàn)[6]主要是基于模型的協(xié)同過(guò)濾,性能和擴(kuò)展性好,能有效解決評(píng)分稀疏性問(wèn)題,然而基于模型的協(xié)同過(guò)濾使用低階矩陣近似原矩陣有一定數(shù)據(jù)消耗,準(zhǔn)確率不高;更重要的是,上述方法沒(méi)有考慮到有些目標(biāo)用戶其實(shí)沒(méi)有相似用戶,若一個(gè)用戶并沒(méi)有相似用戶,算法也會(huì)產(chǎn)生這個(gè)目標(biāo)用戶的相似用戶,這實(shí)際是降低了推薦的準(zhǔn)確率。

基于以上分析,提出一個(gè)基于奇異值分解的混合協(xié)同過(guò)濾算法SBHCF(Svd-Based Hybird Collaborative Filiting)。算法主要特點(diǎn)是集成了基于記憶的協(xié)同過(guò)濾算法(Memory-Based CF)和基于模型的協(xié)同過(guò)濾算法(Model-Based CF)的優(yōu)點(diǎn),大幅縮小了相似用戶的查找范圍,并引入一系列參數(shù)修正用戶相似度和物品相似度,考慮了用戶評(píng)分項(xiàng)相對(duì)較少和沒(méi)有相似用戶的情況。當(dāng)某個(gè)缺失值找不到相似用戶或相似物品時(shí),并不努力生成一個(gè)預(yù)測(cè)值而是將其置0。相比給用戶推薦無(wú)需物品而言,這樣的策略使得用戶體驗(yàn)性會(huì)更好。

1SBHCF算法框架和具體實(shí)現(xiàn)

SBHCF算法具體可分為3個(gè)步驟:第一步是聚類(lèi),通過(guò)矩陣分解將相關(guān)用戶聚為同類(lèi);第二步通過(guò)引入閾值在相關(guān)用戶子群中度量用戶相似度;第三步是聚合相似用戶評(píng)分,為更好地提高準(zhǔn)確率,引入?yún)?shù)混合了相似用戶評(píng)分和相似物品的評(píng)分來(lái)預(yù)測(cè)目標(biāo)用戶缺失值。算法架構(gòu)如圖1所示。

圖1　SBHCF算法框架圖

1.1　SVD聚類(lèi)

一個(gè)具有m個(gè)用戶和n個(gè)項(xiàng)目的推薦系統(tǒng)可看做一個(gè)m×n的矩陣,SVD算法的目的是根據(jù)用戶的評(píng)分?jǐn)?shù)據(jù)將高維數(shù)據(jù)投射從而將興趣相關(guān)的用戶聚合在一起[7]。分解的思想為:對(duì)于任意矩陣A∈Fm×n,rank(A)=r,可進(jìn)行如下的矩陣分解,模型如下

(1)

1.2　改進(jìn)杰卡德的基于用戶的協(xié)同過(guò)濾

通過(guò)SVD矩陣分解,文中可將相同興趣的相關(guān)用戶置于一個(gè)子用戶群中,在此群中找相似用戶?；谟脩?User-based)的協(xié)同過(guò)濾是當(dāng)前流行的用戶相似度計(jì)算方法,公式如下

(2)

(3)

(4)

(5)

1.3　混合協(xié)同過(guò)濾求缺失值

在以上的兩個(gè)步驟的基礎(chǔ)上引入?yún)?shù)來(lái)提高平滑預(yù)測(cè)缺失值的準(zhǔn)確率。引入?yún)?shù)η來(lái)判斷這一相似用戶的相似度是否滿足要求,若不滿足,就認(rèn)為這一用戶不是目標(biāo)用戶的相似用戶。引入?yún)?shù)θ來(lái)判斷是此物品和目標(biāo)物品是否有足夠的相似度,當(dāng)計(jì)算出的相似度低于閾值,則認(rèn)為此物品和目標(biāo)物品不相似。

對(duì)于缺失評(píng)分ru,i,用戶u的相似用戶應(yīng)滿足

(6)

式中,sim′(ua,u)可通過(guò)式(4)計(jì)算得出。同樣,物品i的相似物品也應(yīng)滿足式(7)才被認(rèn)為是相似物品

(7)

從實(shí)際角度出發(fā),基于用戶的協(xié)同過(guò)濾通過(guò)用戶的主觀打分來(lái)預(yù)測(cè)相似,用戶評(píng)分的隨意性有時(shí)會(huì)導(dǎo)致出不一致結(jié)果,基于物品的協(xié)同過(guò)濾通過(guò)物品的評(píng)分來(lái)預(yù)測(cè)相似度,若item是熱門(mén)物品,其評(píng)分基本較高,這些評(píng)分較高的物品卻不能表達(dá)出用戶對(duì)其的喜愛(ài)。因此,預(yù)測(cè)評(píng)分值僅用基于物品的協(xié)同過(guò)濾或只用基于用戶的協(xié)同過(guò)濾都會(huì)忽略一些信息從而導(dǎo)致預(yù)測(cè)不夠準(zhǔn)確,綜合以上情況合并基于用戶的協(xié)同過(guò)濾和的基于物品的混合協(xié)同過(guò)濾能有效提高推薦效果。

(8)

α和β是兩個(gè)引入的參數(shù),α+β=1,參數(shù)取值范圍為[0 1],這兩個(gè)參數(shù)決定了混合算法對(duì)基于主觀的User-basedCF和基于客觀的Item-basedCF有多大程度的依賴。α取值為1時(shí),混合協(xié)同過(guò)濾算法蛻化為User-basedCF算法;β取1時(shí),混合協(xié)同過(guò)濾蛻化為Item-basedCF算法。這是因?yàn)樵趯?shí)際中,一些用戶沒(méi)有相似用戶,即相似度低于規(guī)定的閾值,以往算法忽視了這一問(wèn)題,還是選擇了Topn個(gè)相似用戶,再根據(jù)這些相似用戶去預(yù)測(cè)缺失的值,這將大幅削弱預(yù)測(cè)的精確度。為能更加準(zhǔn)確地預(yù)測(cè)缺失數(shù)據(jù),當(dāng)用戶沒(méi)有相似用戶時(shí),文中采用Item-basedCF算法來(lái)計(jì)算缺失評(píng)分值。

(9)

若item找不到與其相似的物品,文中用User-basedCF的算法來(lái)計(jì)算缺失評(píng)分值。

(10)

若相似用戶和相似物品均未找到,則對(duì)于這樣的缺失評(píng)分將不予評(píng)測(cè),將其置0。

(11)

2閾值和參數(shù)討論

在文中共引入了4個(gè)閾值和2個(gè)參數(shù),γ和δ是引入的閾值,防止用戶和物品在樣本較少時(shí)出現(xiàn)過(guò)擬合,但閾值設(shè)置過(guò)低,過(guò)擬合無(wú)法消除,引入過(guò)高會(huì)導(dǎo)致所有的相似用戶或相似物品都要乘以權(quán)重系數(shù),所以在不同的數(shù)據(jù)集里參數(shù)的設(shè)定要參考實(shí)際情況。

η和θ也是重要的閾值,設(shè)定過(guò)高會(huì)導(dǎo)致眾多缺失數(shù)據(jù)不用去預(yù)測(cè),設(shè)定的太低會(huì)造成幾乎缺失數(shù)據(jù)均需要預(yù)測(cè),當(dāng)η為1和θ為1的情況下,這一算法就不用去預(yù)測(cè)缺失數(shù)據(jù),直接是最基本的協(xié)同過(guò)濾。當(dāng)η為0和θ為0的情況下,算法預(yù)測(cè)所有數(shù)據(jù),算法收斂為T(mén)opN鄰域選擇算法。在文中,為了不讓實(shí)驗(yàn)復(fù)雜化,將η和θ取相同值。

最終的參數(shù)為α和β,其決定算法依靠用戶信息或是物品信息的程度。

3實(shí)驗(yàn)

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

實(shí)驗(yàn)的數(shù)據(jù)集選用MovieLens,這是推薦系統(tǒng)中著名的數(shù)據(jù)集,數(shù)據(jù)集合包含了943個(gè)用戶對(duì)1 682部電影評(píng)分(分?jǐn)?shù)為1～5級(jí))的情況,評(píng)分記錄約有100 000,可得出數(shù)據(jù)集的密度為

(12)

從數(shù)據(jù)集中抽取500用戶來(lái)進(jìn)行實(shí)驗(yàn),300用戶用來(lái)訓(xùn)練,200用戶來(lái)做預(yù)測(cè)。

3.2　評(píng)定準(zhǔn)則

文章使用平均絕對(duì)差(MeanAbsoluteError,MAE)去度量算法的預(yù)測(cè)質(zhì)量。MAE的計(jì)算公式如下

(13)

3.3　實(shí)驗(yàn)設(shè)置

使用五折交叉驗(yàn)證來(lái)對(duì)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),在每一折實(shí)驗(yàn)中,針對(duì)訓(xùn)練集中的評(píng)分?jǐn)?shù)據(jù),對(duì)測(cè)試集中的評(píng)分?jǐn)?shù)據(jù)進(jìn)行預(yù)測(cè)。通過(guò)比值,得出每一折的預(yù)測(cè)精度,而最終的MAE預(yù)測(cè)精度是五折的平均值。

3.4　參數(shù)影響

因?yàn)棣梁挺率蔷€性關(guān)系,文中只討論α的情況,將α以步長(zhǎng)0.2從0遞增到1來(lái)計(jì)算α對(duì)算法預(yù)測(cè)的影響。在實(shí)驗(yàn)中,將閾值取值分別為γ=30,δ=30,η=0.5,θ=0.5,選擇相似用戶為5、10和15來(lái)計(jì)算SBHCF的MAE值。

表1　隨α取值變化的MAE值

從圖2中可看到,隨著參數(shù)α的逐漸增大,MAE值隨之減小,算法的性能類(lèi)似于線性遞增,當(dāng)大約α=0.6時(shí),算法的性能最佳,此時(shí)當(dāng)參數(shù)α再增大時(shí),性能遞減。

圖2　參數(shù)α取值對(duì)MAE的影響

3.5　閾值設(shè)置和性能對(duì)比

為驗(yàn)證算法的有效性,將其與傳統(tǒng)的協(xié)同過(guò)濾算法SVD和混合協(xié)同過(guò)濾HCF以及基于用戶的協(xié)同過(guò)濾UCF進(jìn)行了對(duì)比。在實(shí)驗(yàn)中,將閾值設(shè)置為γ=30,δ=30,η=0.5,θ=0.5,α=0.6,并分別選擇相似用戶數(shù)分別為5、10、15、20和30來(lái)比較這些算法的性能。

圖3　在不同相似用戶下算法的MAE值

從圖3中可看到,SBHCF算法比傳統(tǒng)的相似度算法SVD、HCF和UCF的平均絕對(duì)誤差低,在相似用戶為20時(shí),SBHF和最強(qiáng)競(jìng)爭(zhēng)力的SVD相比,MAE值比SVD降低了7.7%;同UCF相比,MAE值降低了10.7%。當(dāng)相似用戶遞增時(shí),MAE的值是遞減的,代表隨著相似用戶越多預(yù)測(cè)的數(shù)據(jù)越和真實(shí)數(shù)據(jù)相符。但不是相似用戶越多越好,當(dāng)相似用戶到25以上時(shí),可看到MAE不減反增,證明有不太相似的用戶加入了相似用戶隊(duì)列造成預(yù)測(cè)率降低。

4結(jié)束語(yǔ)

文章提出了一個(gè)有效的預(yù)測(cè)缺失數(shù)據(jù)的推薦算法,使用矩陣分解模型將用戶分為不同子群,引入?yún)?shù)找到相似用戶集合和相似物品集合,線性加權(quán)了基于主觀的User-basedCF算法和基于客觀的Item-basedCF算法,并將其合并。這樣傳統(tǒng)的協(xié)同過(guò)濾算法實(shí)際是文中算法的特例,算法根據(jù)設(shè)定的閾值決定了是否去預(yù)測(cè)一個(gè)缺失記錄增強(qiáng)了預(yù)測(cè)的準(zhǔn)確率,通過(guò)實(shí)驗(yàn)證明,SBHCF算法優(yōu)于傳統(tǒng)的協(xié)同過(guò)濾算法。

參考文獻(xiàn)

[1]劉建國(guó),周濤,汪秉宏.個(gè)性化推薦系統(tǒng)的研究進(jìn)展[J].自然科學(xué)進(jìn)展,2009,19(1):1-15.

[2]AdomaviciusG,TuzhilinA.Towardthenextgenerationofrecommendersystems:Asurveyofthestate-of-the-artandpossibleextensions[J].IEEETransactionsonKnowledgeandDataEngineering,2005,17(6):734-749.

[3]張光衛(wèi),李德毅,李鵬,等.基于云模型的協(xié)同過(guò)濾推薦算法[J].軟件學(xué)報(bào),2007,18(10):2403-2411.

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

[5]ChoiK,SuhY.Anewsimilarityfunctionforselectingneighborsforeachtargetitemincollaborativefiltering[J].Knowledge-BasedSystems,2013,37(2):146-153.

[6]XueGR,LinC,YangQ,etal.Scalablecollaborativefilteringusingcluster-basedsmoothing[C].Lanzhou:Proceedingsofthe28thAnnualInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval,2005.

[7]方耀寧,郭云飛,丁雪濤,等.一種基于局部結(jié)構(gòu)的改進(jìn)奇異值分解推薦算法[J].電子與信息學(xué)報(bào),2013(6):1284-1289.

[8]HerlockerJL,KonstanJA,TerveenLG,etal.Evaluatingcollaborativefilteringrecommendersystems[J].ACMTransactionsonInformationSystems,2004,22(1):5-53.

[9]LiuQ,ChenE,XiongH,etal.Acocktailapproachfortravelpackagerecommendation[J].IEEETransactionsonKnowledgeandDataEngineering,2014,26(2):278-293.

[10]GeY,XiongH,TuzhilinA,etal.Cost-awarecollaborativefilteringfortraveltourrecommendations[J].ACMTransactionsonInformationSystems,2014,32(1):4-10.

[11]HuangZ,ChenH,ZengD.Applyingassociativeretrievaltechniquestoalleviatethesparsityproblemincollaborativefiltering[J].ACMTransactionsonInformationSystems,2004,22(1):116-142.

通信作者:唐啟桂(1977—),女,碩士研究生。研究方向:推薦系統(tǒng)和服務(wù)計(jì)算。

作者簡(jiǎn)介:蘇凡軍(1976—),男,博士,講師。研究方向:網(wǎng)絡(luò)智能與服務(wù)質(zhì)量。

基金項(xiàng)目:上海智能家居大規(guī)模物聯(lián)共性技術(shù)工程中心基金資助項(xiàng)目(GCZX14014);滬江基金研究基地專(zhuān)項(xiàng)基金資助項(xiàng)目(C14001);廣西可信軟件重點(diǎn)實(shí)驗(yàn)室開(kāi)放課題基金資助項(xiàng)目(KX201415)

收稿日期:2015- 06- 05

中圖分類(lèi)號(hào)TP306.1

文獻(xiàn)標(biāo)識(shí)碼A

文章編號(hào)1007-7820(2016)01-044-04

doi:10.16180/j.cnki.issn1007-7820.2016.01.012

SBHCF:An SVD-based Hybrid Collaborative Filtering Recommendation Algorithm