基于特定群體興趣的混合個(gè)性化推薦算法

畢 行, 徐煒民

(上海大學(xué)計(jì)算機(jī)工程與科學(xué)學(xué)院,上海 200072)

基于特定群體興趣的混合個(gè)性化推薦算法

畢 行, 徐煒民

(上海大學(xué)計(jì)算機(jī)工程與科學(xué)學(xué)院,上海 200072)

個(gè)性化推薦服務(wù)能夠?yàn)榫W(wǎng)絡(luò)用戶(hù)提供針對(duì)興趣偏好的推薦項(xiàng)目資源,現(xiàn)已被成熟地運(yùn)用到網(wǎng)站導(dǎo)航、數(shù)字化圖書(shū)館檢索系統(tǒng)、電子商務(wù)以及搜索引擎等領(lǐng)域.在研究有關(guān)推薦技術(shù)以及混合方式后,提出一種基于特定群體的混合推薦算法,其緊密結(jié)合了模糊聚類(lèi)與兩種協(xié)同過(guò)濾技術(shù).實(shí)驗(yàn)結(jié)果表明,該算法不僅有效地解決了數(shù)據(jù)集的稀疏性問(wèn)題,而且在一定程度上改善了推薦結(jié)果的質(zhì)量.

個(gè)性化推薦;特定群體;模糊聚類(lèi);協(xié)同過(guò)濾

Abstract:Personalized recommender services provide users with the preference items based on their interests.It has been applied to various areas such aswebsite navigation,indexing and retrieving system of digital libraries,E-commerce,search engine.Having studied recent developments in the relavent areas,we p ropose a new algorithm based on a designated group that using fuzzy clustering combined w ith two collaborative filtering techniques.The result shows that the proposed algorithm can solve the problem of sparsity and improve quality of preferences.

Key words:personal recommendation;designated group;fuzzy clustering;collaborative filtering

互聯(lián)網(wǎng)所提供的信息資源是海量的,但是由于其高度開(kāi)放、異構(gòu)和分布式等特點(diǎn),在進(jìn)行信息檢索時(shí),這些散亂無(wú)序的網(wǎng)絡(luò)資源會(huì)給使用者帶來(lái)一定程度上的不便.因此,如何能夠快速地對(duì)信息資源進(jìn)行追蹤、分析以及以便捷的方式向網(wǎng)絡(luò)用戶(hù)進(jìn)行推薦已成為一個(gè)亟待解決的問(wèn)題.

個(gè)性化推薦服務(wù)的顯著特點(diǎn)是面向用戶(hù)而非面向檢索.本研究所討論的用戶(hù)為一個(gè)特定群體.在整個(gè)社會(huì)中,可以按照屬性劃分出許多不同的群體,如學(xué)生用戶(hù)群體、在職用戶(hù)群體、老年用戶(hù)群體等.在這些群體內(nèi),各個(gè)成員可能處于不同的年齡段以及不同的環(huán)境、領(lǐng)域,但是總能找出一些他們身上的共同興趣點(diǎn).由于距離或者生活背景等因素,使得群體內(nèi)部的成員僅能在一個(gè)孰知范圍內(nèi)獲取有限的信息.因此,為某個(gè)特定群體建立一個(gè)基于他們共同興趣導(dǎo)向的個(gè)性化推薦方法是具有一定意義與應(yīng)用價(jià)值的.

1 個(gè)性化推薦技術(shù)

1.1 推薦方法

目前,主要的推薦方法劃分為以下幾種.

1.1.1 基于內(nèi)容的推薦[1]

該方法又稱(chēng)為基于信息過(guò)濾的推薦,是最早被應(yīng)用到推薦系統(tǒng)中的技術(shù).它在分類(lèi)學(xué)習(xí)方面具有很多成熟的技術(shù)支持,如決策樹(shù)、神經(jīng)網(wǎng)絡(luò)、向量空間模型等.但其只考慮信息項(xiàng)間的相似關(guān)系而忽略了用戶(hù)層面的因素.

1.1.2 基于協(xié)同過(guò)濾的推薦

針對(duì)基于內(nèi)容的推薦方面的不足,該方法采用用戶(hù)-項(xiàng)目打分矩陣來(lái)對(duì)數(shù)據(jù)項(xiàng)進(jìn)行處理,它又可細(xì)分為基于用戶(hù)的協(xié)同過(guò)濾[2]和基于項(xiàng)目的協(xié)同過(guò)濾[3]兩種方式.前者能夠充分挖掘用戶(hù)的潛在興趣,但打分矩陣稀疏問(wèn)題[4-6]難以解決;后者雖然解決了矩陣稀疏的問(wèn)題,但總是推薦相似類(lèi)型的項(xiàng)目,不能洞察到用戶(hù)的潛在興趣.

1.1.3 其他推薦方法

除了基于內(nèi)容和基于協(xié)同過(guò)濾的推薦方法外,還有許多其他推薦方式,如基于關(guān)聯(lián)規(guī)則的推薦、基于效用的推薦以及基于知識(shí)的推薦等.這些方法在不同程度上有著各自的優(yōu)點(diǎn)與缺陷.

1.2 混合推薦的形式

雖然推薦技術(shù)已發(fā)展很多年,但迄今為止尚未有一種推薦技術(shù)是全面和完善的.因此,研究者們開(kāi)始對(duì)推薦技術(shù)進(jìn)行混合使用以達(dá)到取長(zhǎng)補(bǔ)短的效果[7].Burke在文獻(xiàn)[4]中提到以下 7種混合推薦的方式:加權(quán)、切換、混用、特征組合、層疊、特征放大以及元級(jí)別.本研究將根據(jù)需求分別采用其中兩種混合方式構(gòu)建下文中提到的混合個(gè)性化算法,概括描述如下:

(1)特征放大.應(yīng)用前一種推薦技術(shù)所得到的推薦結(jié)果作為后一種推薦技術(shù)的特征輸入.

(2)元級(jí)別.和特征放大方法混合方式較類(lèi)似,其僅把信息數(shù)據(jù)進(jìn)行元級(jí)別處理 (如聚類(lèi)等方式),并未修改數(shù)據(jù)的元 (Meta)特性,并把經(jīng)過(guò)前一級(jí)的處理結(jié)果交由后一級(jí)推薦技術(shù)作為輸入.

2 混合個(gè)性化推薦算法

2.1 混合推薦的整體框架

根據(jù)上一節(jié)所描述的兩種混合推薦方法,算法將通過(guò)模糊聚類(lèi)、基于項(xiàng)目的協(xié)同過(guò)濾和基于用戶(hù)的協(xié)同過(guò)濾三種推薦方式先后進(jìn)行兩次混合,如圖1所示.

圖1 混合過(guò)程示意圖Fig.1 Hybr id process of recomm endation s

本研究以用戶(hù)-項(xiàng)目打分矩陣來(lái)表示數(shù)據(jù)集,即用戶(hù)所瀏覽的文檔的集合.首先,應(yīng)用模糊聚類(lèi)后得到的簇,把打分矩陣劃分為子矩陣.然后,使用元級(jí)別的混合方式將各個(gè)子矩陣作為協(xié)同過(guò)濾步驟的輸入.在協(xié)同過(guò)濾部分中,將采用兩種協(xié)同過(guò)濾技術(shù)來(lái)互補(bǔ)它們各自在推薦過(guò)程中的不足,而在二者之間采用特征放大的混合方式進(jìn)行信息數(shù)據(jù)的傳遞.

2.2 算法的各階段描述

2.2.1 模糊聚類(lèi)階段

對(duì)初始打分矩陣 Rm×n中的所有項(xiàng)目文檔進(jìn)行模糊 C均值 (fuzzy C-means,FCM)聚類(lèi)[8-9].經(jīng)過(guò)多次迭代,使得簇內(nèi)緊湊性最大,簇間耦合性最小,最終確定出聚類(lèi)中心,劃分出 k個(gè)簇 C1,C2,…,Ck,如圖2所示.

圖2 模糊聚類(lèi)后的矩陣劃分Fig.2 M atr ix par tition after cluster ing

聚類(lèi)后形成 k個(gè)簇,每個(gè)簇包含了與其對(duì)應(yīng)聚類(lèi)中心相似的 q個(gè)項(xiàng)目 (q=1,2,…,n).把對(duì)當(dāng)前 q個(gè)項(xiàng)目感興趣的 p個(gè)用戶(hù)歸為一組 (p=1,2,…,m),進(jìn)而對(duì)初始打分矩陣 Rm×n進(jìn)行劃分.劃分后的子矩陣記為 Rp×q,它們將作為元級(jí)別混合方式中的輸入.

2.2.2 基于項(xiàng)目的協(xié)同過(guò)濾階段

一般情況下,對(duì)每個(gè)子矩陣 Rp×q來(lái)說(shuō),用戶(hù)對(duì)文檔的打分仍然有些稀疏,這時(shí)求解出每一項(xiàng)目標(biāo)文檔的最近鄰居項(xiàng)集合,得到前N個(gè)文檔作為推薦集.合并當(dāng)前子矩陣中 q個(gè)目標(biāo)文檔的前 N項(xiàng)推薦集作為總推薦集,再次取前 N項(xiàng)作為最終用來(lái)更新每一個(gè)子矩陣的結(jié)果,更新后的子矩陣命名為 R＊p×q,它們將作為元級(jí)別混合推薦后的輸出.對(duì)于經(jīng)過(guò)基于項(xiàng)目的協(xié)同過(guò)濾處理后的 k個(gè) R＊p×q來(lái)說(shuō) ,其稀疏性大大降低,并為下一步基于用戶(hù)的協(xié)同過(guò)濾提供了良好的輸入.由此,元級(jí)別混合推薦過(guò)程結(jié)束,并把輸出結(jié)果傳遞給后續(xù)的特征放大混合推薦作為其輸入源.

2.2.3 基于用戶(hù)的協(xié)同過(guò)濾階段

由于每個(gè)用戶(hù)不會(huì)對(duì)所有的 k個(gè)簇劃分出來(lái)的內(nèi)容均感興趣,因此,篩選出 f個(gè)稠密子矩陣 R＊p×q作為本階段的輸入,也是在特征放大混合推薦過(guò)程中的實(shí)際輸入.

對(duì)于每個(gè) R＊p×q中的用戶(hù) ,求出其最近鄰居集 ,并根據(jù)自己對(duì) R＊p×q中所有文檔的平均打分以及其最近鄰居對(duì)這些文檔的平均打分,推導(dǎo)出推薦預(yù)測(cè)值;然后取預(yù)測(cè)值最高的前 N項(xiàng)文檔作為推薦集;最后合并 f個(gè) R＊p×q的推薦集作為總的推薦結(jié)果,再次選其前N項(xiàng)作為最后對(duì)目標(biāo)用戶(hù)的推薦結(jié)果.推薦過(guò)程如圖3所示.

圖3 最終的推薦過(guò)程Fig.3 Final process of recommendation

經(jīng)過(guò)特征放大,有效結(jié)合了基于項(xiàng)目的協(xié)同過(guò)濾以及基于用戶(hù)的協(xié)同過(guò)濾,得到了最終的推薦結(jié)果.

2.3 混合推薦的完整過(guò)程

每個(gè)階段都有相應(yīng)的輸入與輸出,完整混合推薦算法過(guò)程如下:

(1)對(duì)打分矩陣 Rm×n進(jìn)行模糊聚類(lèi),把相似的文檔集合 Sdg聚為一簇 (g=1,2,…,k),再根據(jù)每個(gè)簇產(chǎn)生子矩陣 Rp×q.

根據(jù)模糊聚類(lèi)后得到的 k個(gè)簇 Ci,把初始矩陣劃分為 k個(gè)子矩陣 Rp×q.

(2)對(duì)子矩陣作稀疏度預(yù)判處理,在此定義子矩陣稀疏度 (sparse measurement,SM).在定義 SM之前,把相似的項(xiàng)目文檔集合 Sdg中的文檔分為無(wú)效打分文檔和有效打分文檔兩類(lèi).

把無(wú)效打分文檔集合 Dlow定義為打分值低于文檔興趣度閾值 (document interest threshold,D IT)的文檔集合.反之,定義為有效打分文檔 Dhigh,即為 Dlow對(duì) Sdg集合的補(bǔ)集.由此可得子矩陣稀疏度定義

式中,N(Dlow)為無(wú)效打分文檔的數(shù)目,N(Dtotal)為Sdg中文檔的數(shù)目.SM(Sdg)取值在 [0,1]閉區(qū)間內(nèi),取值越小,表明稀疏度越大.

用子矩陣閾值 (matrix sparsity threshold,MST)來(lái)界定當(dāng)前子矩陣是否要進(jìn)行基于項(xiàng)目的協(xié)同過(guò)濾稠密化處理,如圖4所示.

圖4 混合推薦算法流程圖Fig.4 W ork ing flow of hybr id recomm endation

若 SM(Sdg)

若 SM(Sdg)>MST,跳轉(zhuǎn)到 (4)執(zhí)行后續(xù)步驟.

(3)根據(jù)基于項(xiàng)目的協(xié)同過(guò)濾階段相關(guān)步驟對(duì)各個(gè)子矩陣進(jìn)行處理.

求用戶(hù)感興趣的目標(biāo)文檔的最形似文檔集合 S,

式中,I={D1,D2,…,Dk}代表用戶(hù)所喜好的文檔集合,Nd為最近鄰居項(xiàng)目數(shù).

計(jì)算 S中每個(gè)項(xiàng)目 Sj和 I間的相似性,這里用余弦相似度來(lái)進(jìn)行相似性計(jì)算.在每個(gè)子矩陣中獲取前N個(gè)文檔的推薦集,

合并子矩陣中 q個(gè)目標(biāo)文檔獲取的前 N項(xiàng)推薦,并從總集合中再次選取前 N項(xiàng)作為最終推薦結(jié)果.

更新 k個(gè)子矩陣 Rp×q得到相應(yīng)的

(4)根據(jù)算法基于用戶(hù)的協(xié)同過(guò)濾階段的相關(guān)步驟篩選出 f個(gè)稠密子矩陣.這些子矩陣有兩種來(lái)源,一種是直接得到的大于MST閾值的 Rp×q矩陣集合,另一種是經(jīng)過(guò) (3)處理后的子矩陣

求出目標(biāo)用戶(hù) Ui最近的鄰居集合 UNN,利用推薦預(yù)測(cè)公式 (4)獲取目標(biāo)用戶(hù) Ui對(duì)任意項(xiàng)目文檔Dx的推薦預(yù)測(cè)值,

式中,Uk為最近鄰居集合 UNN中的用戶(hù),RUk為用戶(hù)Uk對(duì)項(xiàng)目Dx的打分,R′Ui和R′Uk分別為目標(biāo)用戶(hù)Ui和 Uk對(duì)子矩陣 Rp×q或 R＊p×q所有項(xiàng)目文檔的平均打分,sim(Ui,Uk)為用戶(hù) Ui和 Uk間的余弦相似度.

根據(jù)每個(gè)子矩陣中 prediction(Ui,Uk)結(jié)果,分別取排在前 N個(gè)的文檔作推薦,然后合并目標(biāo)用戶(hù)Ui所對(duì)應(yīng)的 f個(gè)子矩陣的所有前 N個(gè)推薦文檔集合,并從總集合中選取前N項(xiàng)作為最終的推薦結(jié)果.

2.4 算法的時(shí)間復(fù)雜度分析

3 實(shí)驗(yàn)結(jié)果與比較

3.1 數(shù)據(jù)源和評(píng)價(jià)標(biāo)準(zhǔn)

本研究數(shù)據(jù)來(lái)自于上海科普網(wǎng)搜索引擎——搜索雷達(dá)所檢索的出站文檔集合.把使用科普雷達(dá)的用戶(hù)預(yù)定義為特定用戶(hù)群體,共收集 35位用戶(hù)的瀏覽文檔 930篇.

關(guān)于推薦質(zhì)量的評(píng)價(jià)標(biāo)準(zhǔn)文獻(xiàn)[3]提出了三種方式:覆蓋范圍評(píng)價(jià)標(biāo)準(zhǔn)、統(tǒng)計(jì)準(zhǔn)確性標(biāo)準(zhǔn)[10]和決策支持標(biāo)準(zhǔn).本研究采用統(tǒng)計(jì)準(zhǔn)確性標(biāo)準(zhǔn)中的平均絕對(duì)誤差 (mean absolute error,MAE)方法來(lái)對(duì)本算法進(jìn)行評(píng)價(jià).MAE定義如下:

式中,絕對(duì)誤差 ei=fi-yi,fi為預(yù)測(cè)推薦值,yi為實(shí)際評(píng)價(jià)值.

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

先使用未經(jīng)過(guò)模糊聚類(lèi)處理的原始數(shù)據(jù)源,取鄰居個(gè)數(shù)采樣間隔為 5.

分別采用基于項(xiàng)目與基于用戶(hù)的協(xié)同過(guò)濾算法,分別用 I-CFRA與 U-CEFA表示,實(shí)驗(yàn)結(jié)果如圖5所示.

圖5 模糊聚類(lèi)前協(xié)同過(guò)濾的推薦質(zhì)量Fig.5 Quality of collaboration f ilter ing before fuzzy cluster ing

在同樣的數(shù)據(jù)源上進(jìn)行模糊聚類(lèi)后,分別獨(dú)立采用兩種協(xié)同過(guò)濾方式進(jìn)行 MAE計(jì)算,記為I-CFRA＊與 U-CEFA＊.采用本研究混合推薦算法產(chǎn)生的推薦預(yù)測(cè)值進(jìn)行MAE計(jì)算,記為 H-RA.實(shí)驗(yàn)結(jié)果如圖6所示.

圖6 H-RA與 I-CFRA＊,U-CEFA＊測(cè)試結(jié)果對(duì)比Fig.6 Compar ison of I-CFRA＊,U-CEFA＊and H-RA

對(duì)比圖5和圖6可觀(guān)察到,經(jīng)過(guò)模糊聚類(lèi)后,協(xié)同過(guò)濾質(zhì)量有一定幅度的提高,并且在用戶(hù)數(shù)達(dá)到25后,推薦質(zhì)量比較平穩(wěn).

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

經(jīng)對(duì)比實(shí)驗(yàn),本研究提出的針對(duì)特定群體的混合個(gè)性化算法,在所采用的數(shù)據(jù)源下一定程度上改善了推薦的預(yù)測(cè)結(jié)果.同時(shí),也證明了在協(xié)同過(guò)濾前進(jìn)行模糊聚類(lèi)的必要性,以及在算法后半部分中,兩種協(xié)同過(guò)濾技術(shù)的互補(bǔ)可以有效提高推薦質(zhì)量,與理論分析結(jié)果達(dá)成了一致.

[1] DEGEMM IS M,LOPS P,SEMERARO G.A contentcollaborative recommender that exploits wordnet-based user p rofiles for neighborhood formation [J]. User Modeling and User-Adapted Interaction,2007,17(3):217-255.

[2] GOLDBERG D,N ICHOLS D,OKI B M,et al.Using collaborative filtering to weave[J].Communication of ACM,1992,35(12):61-70.

[3] SARWAR B M,KARYPIS G,KONSTAN J A,et al.App lication of dimensionality reduction in recommender system—a case study[C]∥ Web M ining for ECommerce Workshop,ACM WebKDD2000.2000:82-90.

[4] BURKE R.Hybrid recommender systems:survey and experiments[J]. User Modeling and User-Adap ted Interaction,2002,12(4):331-370.

[5] GORDEA S,ZANKER M. Time filtering for better recommendationswith small and sparsity rating matrices[J].Web Information Systems Engineering,2007,4831:171-183.

[6] 孫小華.協(xié)同過(guò)濾系統(tǒng)的稀疏性與冷啟動(dòng)問(wèn)題研究[D].杭州:浙江大學(xué),2005:63-79.

[7] KIEWRA M,NGUYEN N T.AdaptRank:a hybrid method for imp roving recommendation recall[J].New Trends in Applied Artificial Intelligence,2007,4570:1061-1071.

[8] YU J,YANGM S.A study on a generalized FCM[C]∥RSFDGrC’2003,Lecture Notes in Artificial Intelligence.Berlin:Springer-Verlag,2003:390-393.

[9] 高新波.模糊聚類(lèi)分析與應(yīng)用[M].西安:西安電子科技大學(xué)出版社,2004:49-60.

[10] HERLOCKER JL,KONSTAN JA,TERVEEN L G,et al.Evaluating collaborative filtering recommender systems[J].ACM Transaction on Information Systems,2004,22(1):19-49.

(編輯:劉志強(qiáng))

A Hybr id Per sonal Recommendation Algor ithm Based on Designated Group Interest

B IHang, XU Wei-min
(School of Computer Engineering and Science,ShanghaiUniversity,Shanghai200072,China)

TP 391;TP 393

A

1007-2861(2010)03-0318-05

10.3969/j.issn.1007-2861.2010.03.020

2009-01-05

上海市科普資源開(kāi)發(fā)與共享信息化(一期)工程建設(shè)資助項(xiàng)目(07dz23401)

徐煒民 (1949～),男,教授,博士生導(dǎo)師,研究方向?yàn)橄到y(tǒng)結(jié)構(gòu)、并行處理.E-mail:wmxu@staff.shu.edu.cn