基于雙因素方差分析的推薦算法

摘要：提出一種新的基于雙因素方差分析的推薦算法DFAR。該方法基于成熟的統(tǒng)計學(xué)模型，簡單易理解，具有很好的魯棒性。實驗結(jié)果證明，該算法相比傳統(tǒng)的項目協(xié)作過濾算法取得了更好的推薦效果，并大大節(jié)省了算法所需要的空間。

關(guān)鍵詞：推薦系統(tǒng)；雙因素方差分析；協(xié)作過濾

中圖分類號：TP391文獻(xiàn)標(biāo)志碼：A

文章編號：1001－3695(2008)03－0698－04

0引言

Internet的高速發(fā)展使之成為一個分布廣泛的全球性信息服務(wù)中心。隨著計算機(jī)網(wǎng)絡(luò)技術(shù)的發(fā)展和成熟，Web已成為人們獲取信息的一個重要途徑。隨著Web信息的快速增長，人們卻常常面臨信息爆炸的尷尬處境，不得不花費大量的時間去搜索、瀏覽自己需要的信息。由于Web數(shù)據(jù)本身具有分布、異質(zhì)、動態(tài)等特點，對在Web上開展有效、快速、準(zhǔn)確的信息檢索也帶來了巨大的挑戰(zhàn)。

Web推薦系統(tǒng)的目的就是根據(jù)Web使用模式所表達(dá)的用戶偏好，將Web中一組潛在的與當(dāng)前用戶興趣匹配的對象推薦給他，包括鏈接、廣告、文本、產(chǎn)品或服務(wù)等。高效的推薦技術(shù)對于提高網(wǎng)絡(luò)服務(wù)的質(zhì)量是十分重要的。如何發(fā)現(xiàn)用戶的興趣和愛好為其度身定制推薦內(nèi)容則是推薦技術(shù)研究的關(guān)鍵內(nèi)容之一。近年來，研究者們提出了各種各樣的模型和方法，以捕捉集成在Web站點中的用戶行為模式與用戶描述信息之間的關(guān)系[1~5]。這些模式通常表達(dá)為一組頁面或者項目的集合，有共同需要或興趣的用戶經(jīng)常同時訪問它們，或是給出相似的評價。這些模式可以用來更好地理解訪問者和用戶組的行為特征，從而改善站點的組織結(jié)構(gòu)以及為訪問者提供更好的推薦服務(wù)。目前存在許多不同解決方案實現(xiàn)的推薦系統(tǒng)。其中最成功、也是在實際中應(yīng)用得最廣泛的是基于協(xié)作過濾的推薦思想[5]。

基于協(xié)作過濾的推薦系統(tǒng)分為兩大類：a）基于用戶的協(xié)作過濾（userbased collaborative filtering）。它主要關(guān)注用戶與用戶興趣之間的關(guān)聯(lián)性[6]，認(rèn)為“如果用戶對某些頁面/項目表現(xiàn)出相似的興趣（如對頁面相似的訪問模式或?qū)椖肯嗨频脑u分），那么他們對其他頁面/項目也具有較為相似的愛好”。通過分析不同用戶在相同項目上的評分或瀏覽網(wǎng)站過程中所體現(xiàn)的偏好，該方法為當(dāng)前在線用戶尋找k個最相似的鄰居。針對某個特定的當(dāng)前用戶尚未評分或瀏覽的項目，根據(jù)鄰居們感興趣程度對其作出預(yù)測，或是直接將鄰居們最感興趣的N個項目推薦給當(dāng)前用戶（top N recommendation）?；谟脩舻膮f(xié)作過濾推薦模型的優(yōu)點在于用戶的相似性矩陣是實時計算，因此它能捕捉用戶興趣、愛好的變化并及時加以反應(yīng)。然而，也正是由于使用了依賴內(nèi)存的最近鄰查找方法，數(shù)據(jù)規(guī)模逐漸增大時推薦算法的速度就有可能急劇下降，無法及時產(chǎn)生推薦（可擴(kuò)展性差）；另一方面，由于系統(tǒng)初期資源不足以及用戶對項目相關(guān)的評分密度減少引起的數(shù)據(jù)稀疏性問題也會導(dǎo)致系統(tǒng)產(chǎn)生不可靠的推薦結(jié)果（穩(wěn)定性差）。b）基于項目的協(xié)作過濾（itembased collaborative filtering）。它針對可擴(kuò)展性問題而提出[7]。它認(rèn)為項目空間相對小于用戶空間且項目與項目之間的相似性不易發(fā)生變化，因此通過計算項目之間的相似性來替代計算用戶相似性。該方法線下完成項目相似性列表的計算并加以保存，推薦系統(tǒng)運行時需在線維護(hù)項目相似性列表，以便在O(n)時間內(nèi)為當(dāng)前用戶正在瀏覽的項目尋找到k個最相似的其他項目并產(chǎn)生推薦。然而，基于項目的協(xié)作過濾算法依然不能解決數(shù)據(jù)稀疏性所帶來的問題，并且由于項目相似性列表是線下完成的，無法增量地體現(xiàn)出關(guān)于用戶興趣的改變。

事實上，對于Web中的用戶和項目而言，通常用戶對某項目的喜好很大程度上決定于該項目的質(zhì)量，而不僅僅是他人的看法；某項目得到的評價高低也與用戶的評分習(xí)慣有很大關(guān)系，而不僅僅由那些與它相似的項目得到的評價來決定。通過以上觀察，本文提出一種新的基于雙因素方差分析的推薦算法DFAR，同時考察用戶評分習(xí)慣和項目所獲評價兩個因素對推薦質(zhì)量的影響，以期真實反映上述情況。該方法基于成熟的統(tǒng)計學(xué)模型，計算簡單易理解，具有很好的魯棒性，無須依賴最近鄰查詢和建立相似性列表，因此能解決可擴(kuò)展性與穩(wěn)定性的問題。多個實驗結(jié)果證明，該算法不僅能比傳統(tǒng)的項目協(xié)作過濾算法取得更好的推薦效果，而且大大節(jié)省了算法所需要的空間。

1問題陳述和基本定義

推薦系統(tǒng)中，用戶的事務(wù)數(shù)據(jù)庫中包含m個用戶的集合U={u1，u2，…，um}和n個項目的集合I={i1，i2，…，in}。用戶事務(wù)集可用一個m×n階矩陣A(m，n)表示，如表1所示。其中：矩陣共有m行代表m個用戶；n列代表n個項目；Wj，k代表用戶uj對項目ik賦予的權(quán)重。這個權(quán)重有多種取值方案，如用1或0代表在用戶會話中該項目出現(xiàn)或不出現(xiàn)，也可以是用戶對項目的評分或用戶停留在該項目上的時間等，這個權(quán)值體現(xiàn)了用戶ua對項目的興趣和偏好。實際應(yīng)用中，由于并非所有的用戶都對所有的項目進(jìn)行了瀏覽和評分，在A(m，n)中不是每個入口都有對應(yīng)的權(quán)值。假設(shè)每一個用戶ua都對應(yīng)一個已評分項目集IuaI；相似地，每一個項目it也對應(yīng)一個已對它評分的用戶集UitU。

由于基于項目的協(xié)作過濾算法是基于用戶的協(xié)作過濾算法的改進(jìn)[7]，并且兩者具有非常相似的計算過程，以下將以基于項目的協(xié)作過濾算法為協(xié)作過濾推薦算法的代表加以敘述。

對于用戶—項目事務(wù)矩陣A(m，n)中的任何兩個項目ip和iq，基于項目的協(xié)作過濾算法首先需要定義度量ip和iq相似性的方法[8]。通常有以下三種：

對于某個在線目標(biāo)用戶ua和某個ua還未瀏覽或評分的指定項目itIua，推薦系統(tǒng)通過掃描項目相似性列表，在O(n)時間內(nèi)為it尋找最相似的k個鄰居（k根據(jù)經(jīng)驗事先確定），并根據(jù)式（1）為其預(yù)測權(quán)值：

Wa，t=kj=1[Wa， j×sim(ij，it)]/

kj=1sim(ij，it)（1）

其中：Wa，t是推薦算法為用戶ua在指定項目it上的評分預(yù)測；sim(ij，it)表示項目ij與it之間的相似性，只有k個最相似的鄰居會被用于預(yù)測評分。推薦系統(tǒng)可通過判斷Wa，t是否大于一定閾值可知ua對it的感興趣程度，從而決定是否要將it推薦給ua。

2基于雙因素方差模型的推薦算法DFAR

通過分析傳統(tǒng)的協(xié)作過濾推薦算法不難看出，基于用戶的協(xié)作過濾推薦思想主要考慮從用戶觀點出發(fā)，通過分析用戶與用戶之間的關(guān)聯(lián)性來產(chǎn)生推薦，即當(dāng)前用戶對目標(biāo)項目的預(yù)測完全通過其他用戶（當(dāng)前用戶的最近鄰）對此項目的喜好來決定。事實上，目標(biāo)項目本身的素質(zhì)對用戶的評價也存在影響，如質(zhì)量高（已有評分較高）的項目通常比較容易得到認(rèn)可；相似地，基于項目的協(xié)作過濾推薦算法則主要關(guān)注項目之間的相似性來產(chǎn)生推薦，即當(dāng)前用戶對目標(biāo)項目的預(yù)測完全由其他項目（當(dāng)前項目的最近鄰）的特性來決定，而沒有考慮在目標(biāo)項目上的用戶評分習(xí)慣。例如，一個嚴(yán)格的用戶也許對于他認(rèn)為十分滿意的項目才給滿分；而對于那些相對寬容的用戶而言，他們對于還不錯的項目就會給出滿分。這種由于不同評分習(xí)慣造成的偏差，本文認(rèn)為也應(yīng)該在推薦系統(tǒng)中得到體現(xiàn)。

2．1雙因素方差推薦模型

借鑒統(tǒng)計學(xué)的雙因素方差分析[9]，建立基于項目均值的簡單模型，用于項目推薦系統(tǒng)的用戶評估預(yù)測。首先，給出雙因素方差分析的數(shù)學(xué)模型。

設(shè)有兩個因素A、B影響試驗的指標(biāo)，因素A有a個水平，記做(A1，A2，…，Aa)， 因素B有b個水平，記做(B1，B2，…，Bb)，則A與B的不同水平組合AiBj（i=1，2，…，a；j=1，2，…，b）共有ab個，每個水平組合稱為一個處理，每個處理只做一次試驗，得到ab個觀測值Xij和雙因素?zé)o重復(fù)實驗表（表3）。

其中:(a)是初始化用戶平均評分?jǐn)?shù)組μ[1~m]、項目平均評分?jǐn)?shù)組v[1~n]和o；(b)~(f)為每一個用戶計算他的已評分均值，作為他評分習(xí)慣的參照；(g)~(k)為每一個項目計算它已獲評分的均值，作為項目質(zhì)量特性的體現(xiàn)；(l)計算全體用戶對全體項目評分的均值；(m)將μ[1~m]，v[1~n]，o輸出（或保存）。該步驟在最壞情況下的計算復(fù)雜度為O(max(m，n))，而基于項目的協(xié)作過濾推薦算法要為每兩個項目之間計算相似性，因此時間復(fù)雜度為O(n2)；并且基于項目的協(xié)作過濾推薦算法需要O(nk)的空間來存儲相似性列表（其中k為指定的最近鄰個數(shù)），而μ[1~m]，v[1~n]，o的保存只需O(m)+O(n)+O(1)＜＜O(nK)的空間。

b)推薦的產(chǎn)生

輸入：目標(biāo)用戶ua，待評分項目it，μ[1~m]，v[1~n]，o

輸出：ua在項目it上的預(yù)測評分Pa，t

scan μ[1~m]，find μ[a] for ua

scan v[1~n]，find v[t] for it

Pa，t=μ[a]+v[t]-o

3實驗結(jié)果及分析

本文的數(shù)值實驗平臺是PC（Pentium 4，CPU 2.4 GHz，內(nèi)存512 MB），操作系統(tǒng)是Windows XP，使用的數(shù)據(jù)類型是雙精度浮點型。算法使用Java語言編寫。

3．1數(shù)據(jù)集

本實驗采用的數(shù)據(jù)集是目前在衡量推薦算法質(zhì)量中比較常用的MovieLens數(shù)據(jù)集。這個數(shù)據(jù)集由美國Minnesota大學(xué)的GroupLens研究小組創(chuàng)建并維護(hù)。目前，該Web站點的用戶已經(jīng)超過43 000人，用戶評分的電影超過3 500部。選取公開的一部分?jǐn)?shù)據(jù)，包括943個用戶在1 682部電影上的100 000條評分記錄，其中每個用戶至少對20部電影進(jìn)行了評分。評分值是1~5，其中5表示“perfect”，而1表示“bad”。用戶通過對不同電影上的不同評分表達(dá)了自己的興趣。MovieLens 100K提供了能進(jìn)行五折交叉驗證（5fold cross validation）的數(shù)據(jù)劃分，數(shù)據(jù)集被隨機(jī)不相交地劃分為5份(U1~U5)，每一份根據(jù)80/20規(guī)則進(jìn)一步劃分為訓(xùn)練集(.base文件)和測試集(.test文件)。以下實驗將采用此劃分好的數(shù)據(jù)集。

另一方面，為了度量整個數(shù)據(jù)集的稀疏性，引入稀疏等級的概念。稀疏等級Ψ的含義是用戶評分矩陣中未評分項目在整體數(shù)據(jù)集中所占的比例。那么，選擇的電影數(shù)據(jù)集的稀疏等級為

ψ=1-10 000/(943×1 682)=0.936 95

由此可見所選數(shù)據(jù)集的評分矩陣是相當(dāng)稀疏的。

3．2推薦質(zhì)量的評估標(biāo)準(zhǔn)

本文實驗中采用平均絕對偏差(mean absolute error，MAE)作為度量算法優(yōu)劣的標(biāo)準(zhǔn)。MAE通過計算預(yù)測的用戶評分與實際用戶評分之間的偏差來度量預(yù)測的準(zhǔn)確性。MAE為推薦質(zhì)量提供了直觀的度量方法，是最常用的一種推薦質(zhì)量度量方法[8]。推薦算法整體的MAE越小，意味著推薦的質(zhì)量越高。假設(shè)算法對N個項目預(yù)測的評分向量表示為{p1，p2，…，pN}，對應(yīng)的實際用戶評分集合為{r1，r2，…，rN}，則算法的MAE表示為

MAE=Ni=1|pi-ri|/N

3．3與基于項目的協(xié)作過濾算法的推薦質(zhì)量的比較

本實驗的目的是比較基于雙因素方差的推薦算法DFAR與基于k最近鄰的項目協(xié)作過濾推薦算法的推薦質(zhì)量。在傳統(tǒng)的基于項目的協(xié)作過濾算法中，本實驗將采用標(biāo)準(zhǔn)余弦相似性并采用式(1)來產(chǎn)生推薦，k分別取1、25、50、75和100。在DFAR中，本實驗將采用式(2)來產(chǎn)生推薦，實驗結(jié)果如表4所示。

表4中的黑體部分標(biāo)志當(dāng)前數(shù)據(jù)子集中最低MAE的值，最后一行是五折交叉驗證后的平均值。從實驗結(jié)果中可以看出，DFAR幾乎在每個數(shù)據(jù)子集上都取得或接近MAE最低值，并且在五折交叉驗證后獲得了最低的MAE。從2.2節(jié)的描述中可以看到，DFAR無論在時間效率上還是空間占有上均優(yōu)于傳統(tǒng)的基于項目的協(xié)作過濾推薦算法。

4結(jié)束語

推薦系統(tǒng)是Web使用挖掘中的一個熱點課題。傳統(tǒng)的協(xié)作過濾推薦算法面臨可擴(kuò)展性差、當(dāng)缺乏足夠的評價信息而導(dǎo)致產(chǎn)生的預(yù)測不準(zhǔn)確甚至不能產(chǎn)生預(yù)測的情況。本文借鑒統(tǒng)計學(xué)的雙因素方差分析模型，從用戶評分習(xí)慣和項目特性兩方面加以考慮，在深入分析了基于項目的協(xié)作過濾算法之后提出了一個基于雙因素方差分析模型的推薦算法，同時結(jié)合用戶的評分習(xí)慣和項目本身的質(zhì)量因素來為當(dāng)前的用戶提供目標(biāo)項目的預(yù)測評價。這種方法可以有效地解決現(xiàn)有的基于CF推薦算法的不足，使得系統(tǒng)對目標(biāo)對象的預(yù)測較為準(zhǔn)確。實驗結(jié)果證明，基于雙因素方差分析模型的推薦算法能在數(shù)據(jù)集稀疏的情況下，對系統(tǒng)仍然產(chǎn)生準(zhǔn)確的推薦。另外，DFAR模型的優(yōu)勢還包括計算簡便；每個推薦值的產(chǎn)生只需做一次加法計算和一次減法計算；計算的空間和時間復(fù)雜度極低。

未來工作是改進(jìn)目前的基于雙因素方差分析模型。因為推薦系統(tǒng)是一個涉及用戶興趣以及項目質(zhì)量、含義等多因素的復(fù)雜變化系統(tǒng)，這些因素在推薦產(chǎn)生過程中所起的作用是不等同的。另一方面，如何改進(jìn)目前模型使其具有增量計算的能力，能應(yīng)付日益更新的信息資源和隨時變化的用戶愛好也是本文下一步工作的主要內(nèi)容。

參考文獻(xiàn)：

［1］ Broadvision[EB/OL].http://www.broadvision.com.

[2]NANOPOULOS A，KATSAROS D，MANOLOPOULOS Y.A data mining algorithm for generalized Web prefetching [J].IEEE Trans on Knowledge and Data Engineering，2003，15(5):11551169.

[3]WANG Shi， GAO Wen， LI Jintao. Realtime personalization based on classification[J].Journal of Computers，2002，25(8):845－852.

[4]JIN Xin，ZHOU Yanzan，MOBASHER B.A unified approach to personalization based on probabilistic latent semantic models of Web usage and content [C]//Proc of AAAI Workshop on Semantic Web Personalization.San Jose: AAAI， 2004:26－34.

[5]HERLOCKER J，KONSTAN J，RIEDLJ.Explaining collaborative filtering recommendations[C]//Proc of ACM Conference on Computer Supported Cooperative Work.New York:ACM Press， 2000:241－250.

[6]BREESE J，HECHERMAN D，KADIE C.Empirical analysis of predictive algorithms for collaborative filtering[C]//Proc of the 14th Conference on Uncertainty in Artificial Intelligence.1998:43－52.

[7]SARWAR B，KARYPIS G，KONSWTAN J，et al. Itembased collaborative filtering recommendation algorithms[C]//Proc of the 10th International World Wide Web Conference. Hong Kong:[s.n.]，2001:285－295.

[8]HERLOCKER J，KONSTAN J，TERVEEN L，et al.Evaluating collaborative filtering recommender systems[J].ACM Trans on Information Systems，2004，22(1):5－53.

[9]LARSEN R T，MARZ M L.An introduction to mathematical statistics[M].2nd.ed.[S.l.]:PrenticeHall，1986.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”