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

畢 行, 徐煒民

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

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

畢 行, 徐煒民

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

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

個性化推薦;特定群體;模糊聚類;協(xié)同過濾

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)所提供的信息資源是海量的,但是由于其高度開放、異構(gòu)和分布式等特點,在進行信息檢索時,這些散亂無序的網(wǎng)絡(luò)資源會給使用者帶來一定程度上的不便.因此,如何能夠快速地對信息資源進行追蹤、分析以及以便捷的方式向網(wǎng)絡(luò)用戶進行推薦已成為一個亟待解決的問題.

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

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

1.1 推薦方法

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

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

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

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

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

1.1.3 其他推薦方法

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

1.2 混合推薦的形式

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

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

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

2 混合個性化推薦算法

2.1 混合推薦的整體框架

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

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

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

2.2 算法的各階段描述

2.2.1 模糊聚類階段

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

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

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

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

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

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

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

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

圖3 最終的推薦過程Fig.3 Final process of recommendation

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

2.3 混合推薦的完整過程

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

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

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

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

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

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

用子矩陣閾值 (matrix sparsity threshold,MST)來界定當(dāng)前子矩陣是否要進行基于項目的協(xié)同過濾稠密化處理,如圖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é)同過濾階段相關(guān)步驟對各個子矩陣進行處理.

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

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

計算 S中每個項目 Sj和 I間的相似性,這里用余弦相似度來進行相似性計算.在每個子矩陣中獲取前N個文檔的推薦集,

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

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

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

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

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

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

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

3 實驗結(jié)果與比較

3.1 數(shù)據(jù)源和評價標(biāo)準

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

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

式中,絕對誤差 ei=fi-yi,fi為預(yù)測推薦值,yi為實際評價值.

3.2 實驗結(jié)果分析

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

分別采用基于項目與基于用戶的協(xié)同過濾算法,分別用 I-CFRA與 U-CEFA表示,實驗結(jié)果如圖5所示.

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

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

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

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

4 結(jié) 束 語

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

[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é)同過濾系統(tǒng)的稀疏性與冷啟動問題研究[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] 高新波.模糊聚類分析與應(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.

(編輯:劉志強)

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

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

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