畢 行, 徐煒民

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

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

畢 行, 徐煒民

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

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

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

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

1 個性化推薦技術

1.1 推薦方法

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

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

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

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

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

1.1.3 其他推薦方法

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

1.2 混合推薦的形式

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

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

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

2 混合個性化推薦算法

2.1 混合推薦的整體框架

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

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

本研究以用戶-項目打分矩陣來表示數(shù)據(jù)集,即用戶所瀏覽的文檔的集合.首先,應用模糊聚類后得到的簇,把打分矩陣劃分為子矩陣.然后,使用元級別的混合方式將各個子矩陣作為協(xié)同過濾步驟的輸入.在協(xié)同過濾部分中,將采用兩種協(xié)同過濾技術來互補它們各自在推薦過程中的不足,而在二者之間采用特征放大的混合方式進行信息數(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個簇,每個簇包含了與其對應聚類中心相似的 q個項目 (q=1,2,…,n).把對當前 q個項目感興趣的 p個用戶歸為一組 (p=1,2,…,m),進而對初始打分矩陣 Rm×n進行劃分.劃分后的子矩陣記為 Rp×q,它們將作為元級別混合方式中的輸入.

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

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

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

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

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

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

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

2.3 混合推薦的完整過程

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

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

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

(2)對子矩陣作稀疏度預判處理,在此定義子矩陣稀疏度 (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)來界定當前子矩陣是否要進行基于項目的協(xié)同過濾稠密化處理,如圖4所示.

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

若 SM(Sdg)

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

(3)根據(jù)基于項目的協(xié)同過濾階段相關步驟對各個子矩陣進行處理.

求用戶感興趣的目標文檔的最形似文檔集合 S,

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

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

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

更新 k個子矩陣 Rp×q得到相應的

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

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

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

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

2.4 算法的時間復雜度分析

3 實驗結果與比較

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

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

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

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

3.2 實驗結果分析

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

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

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

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

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

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

4 結 束 語

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

[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].杭州:浙江大學,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] 高新波.模糊聚類分析與應用[M].西安:西安電子科技大學出版社,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ā)與共享信息化(一期)工程建設資助項目(07dz23401)

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