胡必云 李舟軍
(北京航空航天大學 軟件開發(fā)環(huán)境國家重點實驗室,北京 100191)
王 君
(北京航空航天大學 計算機學院,北京 100191)
巢文涵
(北京航空航天大學 北京市網(wǎng)絡技術(shù)重點實驗室,北京 100191)
評分偏差對于推薦質(zhì)量的影響
胡必云 李舟軍
(北京航空航天大學 軟件開發(fā)環(huán)境國家重點實驗室,北京 100191)
王 君
(北京航空航天大學 計算機學院,北京 100191)
巢文涵
(北京航空航天大學 北京市網(wǎng)絡技術(shù)重點實驗室,北京 100191)
從理論上分析了評分偏差對于推薦質(zhì)量的影響;基于潛在偏好及已知評分對評分偏差進行度量,其中潛在偏好通過心理測量學模型計算得出;通過設定不同的評分偏差水平,對評分偏差的影響進行了實驗驗證.理論分析及實驗驗證表明:評分偏差可導致推薦準確度及覆蓋度下降;基于高質(zhì)量的評分數(shù)據(jù),協(xié)同過濾算法可為用戶作出好的推薦.
人工智能;信號過濾與預測;信息檢索;評分偏差;數(shù)據(jù)質(zhì)量;協(xié)同過濾;推薦準確度;覆蓋度
個性化推薦是解決信息過載問題的行之有效的方法之一,并已廣泛應用于大型的信息服務提供商,它旨在根據(jù)用戶的歷史偏好信息,向用戶主動推薦他/她可能感興趣的項目,如新聞、書籍等.為了提高推薦質(zhì)量,研究者提出了許多推薦算法,這些算法可分為3類[1]:基于內(nèi)容的推薦、協(xié)同過濾(CF,Collaborative Filtering)及混合的推薦算法.在這些算法中,CF算法得到了廣泛的研究與應用.CF算法可進一步分為基于用戶、基于項目及基于模型的算法,它們通?;谟脩粼u分為用戶進行推薦,其中廣泛使用的數(shù)據(jù)集包括MovieLens,EachMovie,Netflix,Jester等.一般認為,評分數(shù)據(jù)稀疏會導致CF算法的推薦質(zhì)量下降[2],因此,研究者提出了很多方法以解決該問題.然而,對于評分數(shù)據(jù)的另一重要特征——數(shù)據(jù)質(zhì)量問題的研究卻較少,這可能是由于數(shù)據(jù)質(zhì)量相對于數(shù)據(jù)稀疏更加難以衡量造成的.
在少數(shù)涉及到數(shù)據(jù)質(zhì)量問題的研究中,文獻[3]將推薦算法不能準確預測的評分看成是噪聲數(shù)據(jù)并將它們刪除,這使得推薦準確度有了一定的提高,但卻造成了推薦覆蓋度(coverage)下降(推薦覆蓋度指算法可給出的評分預測數(shù)占待預測評分總數(shù)的比率),后者是容易理解的,因為數(shù)據(jù)刪除加劇了數(shù)據(jù)稀疏問題;文獻[4]將符合隨機噪聲模式(CNP,Causal Noise Pattern)的用戶評分系列刪除,使得推薦準確度有所提高,文中未報道評分刪除對推薦覆蓋度的影響;文獻[5]嘗試了使用專家評分對普通用戶進行推薦,因為專家的評分質(zhì)量更高.以上文獻雖然對數(shù)據(jù)質(zhì)量問題進行了一定研究,并取得了一些初步的研究成果,但存在以下問題:①對數(shù)據(jù)質(zhì)量問題的定義過于模糊,即將某些評分[3]或用戶評分系列[4]整體地看作是噪聲.然而,用戶的評分可能只是在某種程度上偏離了其真實偏好,即一個評分數(shù)據(jù)可能含有噪聲而不全部是噪聲;②對數(shù)據(jù)質(zhì)量對于CF算法推薦質(zhì)量的影響機制,特別是對于推薦覆蓋度的影響,沒有做明確的分析與驗證;③對于噪聲數(shù)據(jù)的處理方式太極端,即將噪聲數(shù)據(jù)整體刪除,這雖然可使推薦準確度有一定的提高,但卻導致推薦覆蓋度下降[3].
針對上述問題,本文首先從心理學角度對用戶評分過程進行分析,并提出評分偏差的概念,以對數(shù)據(jù)質(zhì)量問題進行明確的定義.同時,分析評分偏差對于CF算法每一步驟的影響,以初步研究數(shù)據(jù)質(zhì)量問題對于推薦質(zhì)量的影響.其次,基于心理測量學模型對評分偏差加以度量.再次,通過設定不同的評分偏差水平,進一步在現(xiàn)實世界數(shù)據(jù)集上驗證評分偏差對于CF算法推薦質(zhì)量的影響.本文最后對實驗結(jié)果進行了詳細分析并對未來工作進行了說明.
CF算法常依據(jù)用戶評分為用戶作出推薦,而從心理學角度分析,用戶根據(jù)不同項目滿足他/她的潛在興趣的程度對不同項目進行評分,因此觀測到的評分只是用戶潛在興趣的一種外在表現(xiàn).在評分過程中,用戶可能會受到各種因素的干擾,導致用戶的評分偏離于他/她的真實偏好,即產(chǎn)生了評分偏差.造成評分偏差的因素可以是錯誤地使用了評分標準,如對于一個5級評分量表來說,一個用戶偏向于使用1~3的評分(可稱該用戶為一個較嚴的評分人),那么該用戶的評分2代表其真實偏好為3(2和3分別為錯誤的評分量表1~3和正確的評分量表1~5的中間值),即產(chǎn)生了評分偏差-1(觀測值2-真實值3).其它可以造成評分偏差的因素包括:對某些項目不在意而給出的隨意評分、輸入錯誤等.更為具體的例子如Jester數(shù)據(jù)集,它使用了[-10,10]的連續(xù)評分,用戶通過在評分條上點擊以給出評分,這種評分方式則更傾向于產(chǎn)生評分偏差[6].
下文所提及的CF算法主要指基于用戶的CF算法(user-based CF)[7].CF 算法主要包含 3 個步驟:相似度計算、鄰居選取及預測.CF算法將用戶對于項目的評分看成用戶評分向量,然后基于兩個用戶共同評分的項目(co-rated items)計算用戶之間的相似度.常用的相似度計算方法有皮爾森(Pearson)相關系數(shù)、余弦相似度等[2].在鄰居選取階段,CF算法通常選擇和當前用戶(需要為其作出推薦的用戶)最相似的若干個用戶作為他/她的鄰居;然后根據(jù)鄰居對于目標項目(需要為其作出評分預測的項目)的評分情況預測當前用戶對于目標項目的評分;常用的預測公式如式(1)所示:
其中,pa,i是算法給出的當前用戶a對于目標項目i的評分預測值;為a的平均評分;k為鄰居個數(shù);s(a,un)為 a和其鄰居 un之間的相似度;run,i為un對于i的評分.值得注意的是,在鄰居選取階段選出的鄰居并非全部是有效的.
定義1 有效鄰居.在預測階段實際使用到的鄰居.即對于CF算法,有效用戶鄰居對于目標項目的評分run,i(見式(1))是存在的.
1.3.1 評分偏差對于用戶相似度計算的影響
直觀地,評分偏差可導致兩個具有低相似度值的用戶變得更為相似,兩個具有高相似度值的用戶變得較不相似,即評分偏差可導致兩個用戶ui和uj之間的相似度值s(ui,uj)升高或降低.
例1 如表1所示,對于1~5的5級評分,其中用戶u1是一個理想的評分人,她的評分ru1代表了她的真實偏好tu1,而用戶u2是一個較嚴的評分人,他的觀測評分ru2集中于評分等級1~3.如果u2正確地使用了評分等級1~5,則他的真實偏好很可能為表中第4列所列的評分tu2.根據(jù)真實偏好計算得到的u1和u2之間的Pearson相關系數(shù)是0.4,而根據(jù)觀測評分計算得到的u1和u2之間的相關系數(shù)為0.2,即因為評分偏差的影響,u1和u2之間的相似程度s(u1,u2)降低;同樣地,用戶u3的真實偏好tu3列于表1中最后一列,但u3在評分過程中,總有值為1或-1的評分偏差,即觀測到的u3的評分為表中第5列數(shù)據(jù)ru3.當使用真實偏好時,u1和u3之間的Pearson相關系數(shù)為-0.1,但是當使用觀測評分時,兩者的相關系數(shù)為0.1,即因為評分偏差的影響,用戶u1和u3之間的相似程度s(u1,u3)升高.
表1 用戶u對于項目i的評分r及真實偏好t
1.3.2 評分偏差對于鄰居選取的影響
為了便于分析,首先給出關于相似用戶的假設及其推論.
假設1 兩個用戶共同評分的項目越多,則這兩個用戶傾向于越相似.
假設1是符合直覺的,即兩個用戶之間的共同點越多,則傾向于越相似;同時,本文依據(jù)用戶評分計算得出的用戶平均相似度隨共評項目數(shù)變化的實驗結(jié)果也反應了該假設.
基于假設1,可以得出以下推論:
推論1 兩個用戶之間的相似性越小,則這兩個用戶共同評分的項目傾向于越少.
在鄰居選取階段,評分偏差對于用戶相似度計算的影響會導致具有低相似度值的用戶被選擇為鄰居,而根據(jù)推論1,這些具有低相似度的鄰居是無效鄰居的可能性增大.
例2 如表2所示,由于評分偏差的影響,具有低相似度值的用戶u2被選擇為用戶u1的鄰居,CF算法目前需要為u1對于項目i4的評分進行預測(以?表示).因為u1和u2相似程度低,根據(jù)推論1,u2對于i4沒有進行評分,即u2是無效鄰居的可能性增大.
表2 被用戶u1和u2共同評分的項目
1.3.3 評分偏差對于推薦質(zhì)量的影響
具有低相似度值的鄰居被使用會導致推薦準確度下降,更進一步地,由于低相似性鄰居是有效鄰居的可能性小,導致推薦覆蓋度下降.評分偏差對于推薦質(zhì)量的影響分析可總結(jié)為圖1.
圖1 評分偏差對于推薦質(zhì)量的影響分析
在心理測量學研究領域,潛在特質(zhì)模型(latent traitmodels)或稱項目反應理論模型(item response theorymodels),是一系列旨在通過人對項目如試題、調(diào)查問卷等的反應數(shù)據(jù),測量人的潛在特質(zhì)如能力、興趣、滿意度等的模型[8].典型的項目反應理論模型有Rasch模型,如式(2)所示.Rasch模型最初用于教育測量學領域,隨著模型及其參數(shù)估計技術(shù)的發(fā)展,Rasch模型被用于越來越多的心理測量領域[9].
在不同的應用領域中,Rasch模型的參數(shù)意義是不同的.在傳統(tǒng)的教育測量領域,式(2)建模了學生u答對題目i的概率p(ru,i=1)與學生能力θu及題目難度bi之間的關系[8];因為本文主要考慮通過用戶對于項目的評分數(shù)據(jù)測量用戶潛在興趣,所以將p(ru,i=1)解釋為用戶u對于項目i的反應為積極(如表示感興趣或評分為1)的概率;將θu解釋為用戶的潛在興趣(latent interest);將bi解釋為項目的可接受程度(agreeability).因此,式(2)直觀上表示了用戶的潛在興趣越強,則越可能表現(xiàn)出積極的反應.
文獻[11]將心理測量學模型引入個性化推薦算法的研究中,并提出了基于潛在興趣的CF算法,實驗結(jié)果表明基于潛在興趣的CF算法相比于傳統(tǒng)CF算法可提高推薦準確度.
上述研究結(jié)果表明,將心理測量學引入個性化推薦算法研究中是有益的.提出具有更高推薦準確度的算法雖然重要,但對于評分數(shù)據(jù)質(zhì)量問題的研究同樣重要,因為低質(zhì)量的數(shù)據(jù)可能會造成研究結(jié)果產(chǎn)生偏差甚至誤導.因此,鑒于用戶在評分過程中傾向于產(chǎn)生評分偏差,前期工作[12]提出了使用潛在偏好(latent preference)表示用戶偏好,其中潛在偏好通過心理測量學模型計算得出,并實驗驗證了潛在偏好相比于觀測評分可更準確地表示用戶偏好.然而,文中并沒有對評分偏差對于推薦質(zhì)量的影響進行實驗分析.本文在前期研究的基礎上,提出評分偏差的度量方法,并分析評分偏差對于推薦質(zhì)量的影響,從而對推薦算法作出更為客觀的評價.
具體地,評分偏差的度量分為3個步驟:
1)依據(jù)用戶評分及心理測量學模型估計用戶潛在興趣θu.本文用Rasch模型參數(shù)估計軟件Winsteps[13].Winsteps 首先將 θu,bi及 τx初始化為0,然后遍歷用戶評分數(shù)據(jù)集,通過正態(tài)逼近算法(PROX,Normal Approximation Estimation Algorithm)迭代更新θu及bi,直至θu及bi的變化程度小于某一閾值(詳細的推導過程可參見文獻[14]).Winsteps然后通過 JML進行第2階段的參數(shù)估計.首先依據(jù)當前 θu,bi,τx值及 Rasch 模型計算用戶評分期望值,然后依據(jù)評分期望值與評分的差別程度,通過 Newton-Raphson算法對θu,bi及τx進行迭代更新.例如,如果依據(jù)目前參數(shù)計算得到的用戶期望評分總分小于實際總分,則提高用戶的潛在興趣值θu.具體的參數(shù)迭代更新公式可參見W right等的推導[15].
2)對于每一用戶評分,依據(jù)用戶潛在興趣,計算相應的潛在偏好,如式(5),其中 lu,i為計算得到的用戶u對于項目i的潛在偏好:
3)依據(jù)潛在偏好,計算用戶的評分偏差R.計算公式見式(6),其中ru,i為用戶u對于項目i的評分.前期工作表明,潛在偏好lu,i相比于觀測評分 ru,i可更準確地表示用戶偏好[12],因此,由式(6)度量用戶評分偏差是可行的.
實驗采用了廣泛使用的數(shù)據(jù)集之一MovieLens[2].該數(shù)據(jù)集含有943個用戶對于1 682個電影項目的100000個評分.評分可取值為1~5.實驗隨機選取了80%的用戶評分作為訓練集,其余的評分作為測試集.
實驗采用廣泛使用的平均絕對誤差(MAE,Mean Absolute Error)[2]作為推薦準確度的度量標準,用E表示:
其中,pu,i為算法給出的用戶u對于項目i的評分預測值;ru,i為測試集中的對應評分.MAE值越小,則推薦準確度越高;推薦覆蓋度(coverage)定義為算法可給出的預測值數(shù)目占測試評分總數(shù)N的比例[5].
實驗首先通過訓練集數(shù)據(jù)使用Rasch模型參數(shù)估計軟件Winsteps[13]估計用戶潛在興趣;然后針對訓練集中的每一用戶評分ru,i,計算其對應的潛在偏好 lu,i及評分偏差 Ru,i=ru,i- lu,i,接著,通過設定不同的評分偏差水平a(a分別取值0,0.2,0.4,…,1.0)形成不同的訓練數(shù)據(jù)集 tu,i=aRu,i+lu,i.通過由不同評分偏差水平形成的訓練集,分別分析評分偏差對于用戶相似度計算、鄰居選取及推薦質(zhì)量的影響.
實驗采用Pearson相關系數(shù)[2]計算用戶相似度,鄰居數(shù) k分別設置為 5,10,…,60,評分預測公式為式(1).
3.3.1 評分偏差對于相似度計算的影響實驗分析
實驗計算了在不同評分偏差水平a下,含有不同共評項目數(shù)c>x(x分別取值為2,4,…,10,15,25,…,105)的用戶之間的平均相似度,結(jié)果如圖2所示(為了清楚的呈現(xiàn)實驗結(jié)果,本文省略了某些參數(shù)取值下的結(jié)果,或?qū)⒉煌瑓?shù)下的結(jié)果分別呈現(xiàn)).
圖2 平均用戶相似度隨共評項目數(shù)c的變化情況
圖2的結(jié)果顯示,隨著偏差水平的增大,具有低相似度的用戶之間的相似水平相對提高;具有高相似度的用戶之間的相似水平相對降低.例如,對于a=0.2,c<10的這些低相似性用戶(圖2b),隨著偏差水平的升高,這些用戶之間的相似度值逐漸相對提高(相對于同一偏差水平下,c>10的那些用戶);而對于a=0.2,c>10的這些高相似性用戶,隨著偏差水平的升高,這些用戶之間的相似度值逐漸相對下降.這些相似度變化與本文第1.3.1節(jié)的分析結(jié)果一致(圖1中A→B).
3.3.2 評分偏差對于鄰居選取的影響實驗分析
圖2的結(jié)果顯示,隨著偏差水平的升高,具有低相似度值的用戶在鄰居中占的比率增大(圖1中 B→C).例如,對于 a=0.2,c<10 的這些低相似性用戶(圖2b),當偏差水平升至0.8及1.0時,CF算法完全優(yōu)先選擇這些用戶作為鄰居,而這些用戶之間的共評項目數(shù)相對較少,即是有效鄰居的可能性小.
為了進一步分析鄰居的有效性,定義平均有效鄰居比(average effective neighbor ratio),用e表示,如式(8),其中N為測試集中的評分個數(shù),ni1為預測任一測試集中的評分時,有效鄰居的個數(shù),ni2為可選鄰居的個數(shù).
當鄰居數(shù)k設為不同值時,平均有效鄰居比的實驗結(jié)果報告于圖3.圖3顯示,隨著偏差水平的升高,鄰居的有效性降低;而前述分析表明:偏差水平增大,鄰居中低相似度值的用戶比率增大;據(jù)此兩點可得出結(jié)論:具有低相似度值的用戶鄰居的有效性低(圖1:C→E).
圖3 不同評分偏差水平a下的平均鄰居有效比
3.3.3 評分偏差對于推薦質(zhì)量影響實驗分析
圖4顯示了不同偏差水平下的推薦準確度結(jié)果,可見,平均絕對誤差隨偏差水平a的增加而增加,即隨著偏差水平的提高,推薦準確度下降.最大降幅達20%(當鄰居數(shù)k為5時,將偏差水平平均絕對誤差從0.2提高至0.8,a值從 0.785 增至0.945).
不同偏差水平下的推薦覆蓋度結(jié)果見圖5,可見,推薦覆蓋度隨偏差水平a的增加而下降,即隨著偏差水平的提高,推薦覆蓋度下降.最大降幅達12%(當鄰居數(shù)k=60時,將偏差水平a從0.2提高至0.8,推薦覆蓋度從 0.648 降至 0.572).
圖4 不同評分偏差水平a下的推薦準確度
圖5 不同評分偏差水平a下的推薦覆蓋度
推薦準確度主要與用戶相似度值有關,即所選鄰居是否具有真實可靠的高相似性;推薦覆蓋度主要與鄰居有效性有關,即針對每一測試評分,是否可找到有效的用戶鄰居.因此,在實驗分析了評分偏差對于用戶相似度計算及鄰居選取的影響后,不難得出評分偏差對于推薦準確度及覆蓋度的影響,即評分偏差使得相似度值低的用戶被選擇為鄰居,導致推薦準確度下降(圖1中A→B→C→D);同時,相似度值低的鄰居的有效性低,導致推薦覆蓋度下降(圖1中A→B→C→E→F).
本文的主要貢獻在于:①給出了評分數(shù)據(jù)質(zhì)量問題的明確定義,即評分偏差;②對評分偏差對于推薦質(zhì)量(包括推薦準確度及覆蓋度)的影響機制進行了分析,并基于心理測量學模型對用戶評分偏差進行了度量,通過實驗驗證了評分偏差的影響:評分偏差導致具有低相似度值的用戶被選擇為鄰居,從而導致推薦準確度下降;同時,由于具有低相似度值的鄰居的有效性低,導致推薦覆蓋度下降;③結(jié)果表明,基于高質(zhì)量的數(shù)據(jù),CF算法可獲得好的推薦準確度及覆蓋度.
References)
[1] Gediminas A,Alexander T.Toward the next generation of recommender systems:a survey of the state-of-the-art and possible extensions[J].IEEE Trans on Knowledge and Data Engineering(TKDE),2005,17(6):734 -749
[2] Badrul S,George K,Joseph K,et al.Item-based collaborative filtering recommendation algorithms[C]//Proc of10th International World Wide Web Conference(WWW'01).New York:ACM Press,2001:285 -295
[3] O'Mahony M P,Hurley N J,Silvestre G CM.Detecting noise in recommender system databases[C]//Proc of the 10th International Conference on Intelligent User Interfaces(IUI'06).New York:ACM Press,2006:109 -115
[4] Cao Huanhuan,Chen Enhong,Yang Jie,et al.Enhancing recommender systems under volatile user interest drifts[C]//Proc of the 18th ACM Conference on Information and Knowledge Management(CIKM'09).New York:ACM Press,2009:1257 -1266
[5] Xavier A,Neal L,Pujol JM,et al.The wisdom of the few:a collaborative filtering approach based on expert opinions from the web[C]//Proc of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval(SIGIR'09).New York:ACM Press,2009:532 -539
[6] Herlocker JL,Konstan JA,Terveen L G,et al.Evaluating collaborative filtering recommender systems[J].Transactions on Information Systems(TOIS),2004,22(1):5 -53
[7] Wang Jun,de Vries A P,Reinders M J T.Unifying user-based and item-based collaborative filtering approaches by similarity fusion[C]//Proc of the29th International ACM SIGIRConference on Research and Development in Information Retrieval(SIGIR'06).New York:ACM Press,2006:501 -508
[8]杜文久.高等項目反應理論[M].重慶:西南師范大學出版社,2007:71-88 Du Wenjiu.Advanced item response theory[M].Chongqing:Southwest Normal University Press,2007:71 -88(in Chinese)
[9] Cheng Yunghsiang.Exploring passenger anxiety associated with train travel[J].Transportation,2010,37(6):875 -896
[10] David Andrich.A rating formulation for ordered response categories[J].Psychometrikia,1978,43(4):561 - 573
[11] HuBiyun,Li Zhoujun,Wang Jun.User's latent interest-based collaborative filtering[C]//Proc 32nd European Conference on Information Retrieval(ECIR'10).Berlin:Springer-Verlag,2010:619-622
[12] HuBiyun,Li Zhoujun,Chao Wenhan,et al.User preference representation based on psychometric models[C]//Proc 22nd Australia Database Conference(ADC'11).Sydney:ACS,2011:57-64
[13] LinacreMike.WINSTEPS Rasch measurement computer program[EB/OL].Chicago:Winsteps.com,2007[2011-05-15].http://www.winsteps.com
[14] Linacre Mike.PROX for polytomous data[J].Rasch Measurement Transactions,1995,8(4):400
[15] Wright B D,Masters G N.Rating scale analysis[M].Chicago:MESA Press,1982:100
(編 輯:文麗芳)
Effect of rating residual on recommendation quality
Hu Biyun Li Zhoujun
(State Key Laboratory of Software Development Environment,Beijing University of Aeronautics and Astronautics,Beijing 100191,China)
Wang Jun
(School of Computer Science and Technology,Beijing University of Aeronautics and Astronautics,Beijing 100191,China)
Chao Wenhan
(Key Laboratory of Network Technology of Beijing,Beijing University of Aeronautics and Astronautics,Beijing 100191,China)
The effect of the rating residual on recommendation quality was analyzed.The rating residual was measured through user ratings and latent preferences.Latent preferences were computed with psychometric models.With different levels of rating residual,the effect of the rating residual was experimentally evaluated on real world datasets.Theoretical analysis and experimental results show that rating residual has negative effects on recommendation accuracy and coverage.Based on high quality of data,collaborative filtering algorithms can make precise recommendations for users.
artificial intelligence;signal filtering and prediction;information retrieval;rating residual;data quality;collaborative filtering;recommendation accuracy;coverage
TP 182
A
1001-5965(2012)06-0823-06
2011-03-18;網(wǎng)絡出版時間:2012-06-15 15:43
www.cnki.net/kcms/detail/11.2625.V.20120615.1543.024.htm l
國家自然科學基金資助項目(61170189,60973105);軟件開發(fā)環(huán)境國家重點實驗室自主研究課題資助項目(SKLSDE-2011ZX-03)
胡必云(1982 -),女,安徽六安人,博士生,hubiyun@cse.buaa.edu.cn.