王 政，郜魯濤，齊偉恒，彭 偉，彭 琳

(云南農(nóng)業(yè)大學(xué) 大數(shù)據(jù)學(xué)院(信息工程學(xué)院)，云南 昆明 650000)

0 引 言

隨著電子商務(wù)的高速發(fā)展，大量的圖書通過電商平臺進(jìn)行銷售，造成嚴(yán)重的商品信息過載[1]。推薦系統(tǒng)作為解決信息過載的有效手段，能夠幫助用戶對書籍進(jìn)行個性化選擇，同時滿足企業(yè)對用戶需求的逢迎，更好地實現(xiàn)“長尾效應(yīng)”[2-3]。推薦系統(tǒng)中常用的算法有基于項的協(xié)同過濾、基于用戶的協(xié)同過濾等。

將傳統(tǒng)的協(xié)同過濾算法應(yīng)用到圖書推薦領(lǐng)域存在數(shù)據(jù)稀疏、推薦效果差等問題。在進(jìn)行推薦時，商品系統(tǒng)對用戶只購買而不評分的書籍給予默認(rèn)的0分,0分并不能完全體現(xiàn)用戶對該書籍的興趣，同時大量用戶在購買完書籍后很少再次進(jìn)入網(wǎng)站對其進(jìn)行評分，造成數(shù)據(jù)嚴(yán)重稀疏。傳統(tǒng)協(xié)同過濾算法在進(jìn)行預(yù)測評分時，只考慮該用戶的評分平均值，而忽略了最近鄰用戶對待推薦書籍的評分影響。所以將傳統(tǒng)協(xié)同過濾推薦算法應(yīng)用到圖書推薦領(lǐng)域時存在著諸多問題[4]。

數(shù)據(jù)稀疏對推薦效果的影響很大，對原數(shù)據(jù)集進(jìn)行一定的填充很有必要。熊聰聰?shù)萚5]通過設(shè)定的缺省值對評分矩陣中用戶未評分的項進(jìn)行填補。劉林靜等[6]利用項目間的相似度對未評分的進(jìn)行預(yù)測填充。張玉芳等[7]通過設(shè)定目標(biāo)用戶鄰居，將提出的評分公式用于填充未評分的項目。鄭丹等[8]利用Weighted-slope One算法對原始的數(shù)據(jù)集進(jìn)行填充。雖然在數(shù)據(jù)填充方面進(jìn)行過大量的嘗試，但其對推薦效果的提升都比較有限。

將slope_one算法作為預(yù)測評分策略應(yīng)用到協(xié)同過濾中，學(xué)術(shù)界對其進(jìn)行了一定的探索。李桃迎等[9]通過在slope_one算法中加入用戶的興趣變化和用戶相似度，提出了基于用戶興趣遺忘函數(shù)和用戶最近鄰篩選策略的改進(jìn)算法。張鵬等[10]采用標(biāo)簽相似度和用戶的評分相似度作權(quán)重，對slope_one預(yù)測評分公式進(jìn)行修正，但沒有考慮不同項目之間的區(qū)別。劉林靜等[6]提出了BUS weighted slope one方法，在計算評分時，考慮了用戶間的相似度對推薦的影響，但沒有考慮商品間的相似度。杜茂康等[11]在評分公式中用項目間的相似度替換原先的用戶個數(shù)，并沒有在預(yù)測評分時考慮項目相似度對devj,i的影響。

針對上面提到的問題，文中在傳統(tǒng)協(xié)同過濾的基礎(chǔ)上提出了一種基于FP_Growth和slope_one的協(xié)同過濾算法。在該算法中，對數(shù)據(jù)集中系統(tǒng)默認(rèn)評分為0分的記錄重新進(jìn)行評分，針對數(shù)據(jù)稀疏性提出基于FP_Growth的矩陣填充方法，對slope_one預(yù)測評分策略進(jìn)行改進(jìn)，更好地滿足圖書推薦的要求。

1 相關(guān)工作

1.1 基于用戶的協(xié)同過濾算法

基于用戶的協(xié)同過濾算法主要是通過計算用戶之間的相似度，將最近鄰用戶中的其他商品預(yù)測評分后進(jìn)行推薦[12-14]。相似度作為協(xié)同過濾中選擇最近鄰的標(biāo)準(zhǔn)，對推薦效果的影響非常大，其常用的相似度包括：歐幾里德距離、皮爾遜相關(guān)系數(shù)、余弦相似度等[15]。修正的余弦相似度的計算公式如下：

(1)

其中，sim(u,v)為用戶u與用戶v之間的相似度；I為用戶u與用戶v共有的評分項；ru,i和rv,i分別為用戶u和用戶v對項i的真實評分。

協(xié)同過濾中常用的預(yù)測評分策略為：

(2)

其中，Rv,i為用戶v中的待評分項i的預(yù)測值；U為最近鄰中擁有待評分項i的所有用戶。

1.2 FP_Growth算法

FP_Growth是一種求解頻繁項集的關(guān)聯(lián)規(guī)則挖掘算法[16-17]，核心是通過構(gòu)建FP樹，循環(huán)挖掘頻繁項集。步驟如下：

(1)FP樹的構(gòu)建。

掃描事務(wù)數(shù)據(jù)庫，刪除項目集中小于最小支持度min_sup的項，生成1-項頻繁項集，之后對剩余的項目按支持度降序排列。

構(gòu)建FP的原始根節(jié)點，標(biāo)記為null。依次將事務(wù)數(shù)據(jù)庫中每條事務(wù)中的項按1-項頻繁項集中的順序插入到根節(jié)點中。

(2)頻繁項集挖掘。

從FP樹的表頭項中不斷取出每個項，以該項為后綴在FP樹的基礎(chǔ)上建立新樹，直到新樹中只包含單路徑。將單路徑中的每種組合與所有的后綴組成新的集合，支持度計數(shù)與最后一個后綴的相同，當(dāng)其大于最小支持度計數(shù)時進(jìn)行輸出。

1.3 slope_one算法

slope_one是一種推薦算法常用的預(yù)測評分策略，通過計算待評分項與同一用戶中的其他項之間的評分偏差來進(jìn)行預(yù)測。運用slope_one進(jìn)行評分的原理如下：

(1)計算商品之間的評分偏差。

(3)

其中，Sj,i(x)為最近鄰中與待評分用戶有共同評分項i和j的用戶集合，其中j為用戶v的待評分項；card(Sj,i(x))為集合中用戶的個數(shù)；uj和ui為集合中的用戶u對應(yīng)的j項和i項的真實評分；devj,i為集合中的所有用戶對項j和i的平均評分偏差。

(2)根據(jù)偏差預(yù)測用戶對未評分商品的評分。

(4)

其中，P(v)j為用戶v對待評分項j的預(yù)測值；Rj為用戶v中除j以外與最近鄰中用戶所有的共有項的集合；rv,i為用戶v對項i的真實評分。

2 基于FP_Growth和slope_one的協(xié)同過濾算法

2.1 對評分為0的記錄重新進(jìn)行評分

在電商平臺中用戶會對喜歡的書籍進(jìn)行購買，但是通常并不會再次登錄系統(tǒng)對其進(jìn)行評分。對于這些購買行為，商品系統(tǒng)默認(rèn)給予0分，即用戶對商品的評分為0分。這部分?jǐn)?shù)據(jù)不僅不能反映用戶的興趣，而且當(dāng)其在數(shù)據(jù)集中占有很大比重時會嚴(yán)重影響推薦的準(zhǔn)確度，因此需要對默認(rèn)評分為0分的記錄重新進(jìn)行評分。

用戶購買過該商品，說明用戶對商品有一定的興趣，采用商品的不同屬性乘以權(quán)重系數(shù)進(jìn)行重新評分較為合理。作者為書籍的創(chuàng)作者，同一作者創(chuàng)作的書籍一般處于同一水平，屬于同一類型，也是用戶選擇書籍的最重要的原因，文中將其權(quán)重設(shè)定為50%。同一年代的書籍大都處于同一層次，文中將其權(quán)重設(shè)定為25%。出版社側(cè)重于出版某一類型的書籍,文中將其權(quán)重設(shè)定為25%。具體評分公式如下：

(5)

2.2 基于FP_Growth的矩陣填充方法

2.2.1 填充理由

協(xié)同過濾嚴(yán)重依賴用戶的歷史數(shù)據(jù)，數(shù)據(jù)的稀疏性對推薦結(jié)果的影響非常大。在進(jìn)行推薦時，由于獲取的用戶的歷史數(shù)據(jù)存在時間和空間的局限性，因此無法完全體現(xiàn)用戶的興趣。文中采用的Book_cross數(shù)據(jù)集，只是收集了用戶在Book-Crossing社區(qū)4周內(nèi)對注冊書籍的評分，并不能說明用戶以后不會在網(wǎng)站對書籍進(jìn)行評分。同時，有些用戶可能通過其他的網(wǎng)站對書籍進(jìn)行評價。為了使數(shù)據(jù)集能夠更加全面地體現(xiàn)用戶的興趣，對原始數(shù)據(jù)集進(jìn)行填充非常有必要。

2.2.2 填充策略

基于大部分人的興趣類似，文中將采用挖掘頻繁項集的方式獲取待填充用戶的填充項，之后對填充項進(jìn)行評分補充到原數(shù)據(jù)集。組成用戶興趣的商品個數(shù)表示為min_interest_num，當(dāng)該值較大時，表示對用戶興趣的反映更為準(zhǔn)確。由原數(shù)據(jù)集構(gòu)建的FP樹稱為FP_original。每本圖書在數(shù)據(jù)集中出現(xiàn)的次數(shù)表示為支持度min_sup。整體流程為先統(tǒng)計待填充的用戶集合U，之后對U中的每個用戶生成待填充項I，最后進(jìn)行評分R。

(1)構(gòu)建FP_original，生成U。

首先，對原數(shù)據(jù)集按用戶進(jìn)行分類,生成每個用戶對應(yīng)的圖書列表，如表1所示。

表1 圖書數(shù)據(jù)

用戶圖書列表用戶圖書列表U1B1,B3,B4U5B2,B3,B4,B5,B6U2B2,B3,B4,B6U6B1,B2,B3U3B1,B6,B3U7B5,B1U4B2U8B2,B3,B6

其次，將每個用戶對應(yīng)的圖書列表作為事務(wù)組成事務(wù)數(shù)據(jù)庫，接著按照上文中FP_Growth算法中的“FP樹的構(gòu)建”方法生成FP_original，如圖1所示。

最后對事務(wù)中用戶對應(yīng)的圖書個數(shù)小于min_interest_num的用戶進(jìn)行統(tǒng)計。這里將min_interest_num設(shè)定為4，獲得的待填充的用戶集合U為{U1,U3,U4,U6,U7,U8}。

圖1 圖書FP_original

(2)生成U中每個用戶的待填充項I。

通過將用戶事務(wù)中支持度最小的項作為后綴，在FP樹的基礎(chǔ)上循環(huán)挖掘獲取待填充項。

初始條件：

list1為U中單個用戶事務(wù)中的所有項的列表。

list2為生成的該用戶的待填充項。其個數(shù)固定但值都為null，循環(huán)挖掘就是對null進(jìn)行填充，直到填滿。

其中l(wèi)ist1與list2中的元素個數(shù)之和等于min_interest_num。

循環(huán)挖掘：

FP_cycle(Tree,list1，list2) //Tree為待挖掘的頻繁模式樹，list1為事務(wù)中的各項集合,list2為生成的項列表。

if list1為空 then

if list2沒有填滿 then

從Tree中選取支持度最大的n個項，將其填入到list2中，直到填滿

return

else

從list2彈出支持度最小的項，以此項作為后綴從Tree中挖掘條件模式基

通過條件模式基，建立新樹Tree1

FP_cycle(Tree1，list1，list2)

由U中每個用戶及其對應(yīng)的list2組成待填充矩陣R。

圖2是對用戶U1進(jìn)行挖掘后生成的填充項。

圖2 對B1,B3,B4圖書列表的填充示意圖

(3)填充評分。

基于大部分人的興趣類似，選取所有用戶對該項評分的平均值作為參數(shù)。頻繁項集所挖掘出來的項，并不是用戶真實購買的商品，而用戶最有可能購買這些，評分公式中應(yīng)加入該用戶對所有項的評分平均值。綜合考慮以上兩種因素，將數(shù)據(jù)集中項的平均值和用戶對所有項的評分平均值求和后再平均較為合理，填充公式如下：

(6)

2.3 改進(jìn)slope_one的預(yù)測評分策略

預(yù)測的評分項與相似項本身存在一定的差異，這種差異會對評分預(yù)測產(chǎn)生影響。而在slope_one預(yù)測評分策略中并沒有考慮這種差異,導(dǎo)致評分不準(zhǔn)確。在實際中，項目之間的相似度對預(yù)測評分的影響更大。為此，文中在預(yù)測公式的評分偏差上乘以不同項目之間的相似度，具體如下：

(7)

(8)

其中，P(v)j為用戶v對待評分項j等的預(yù)測值；Rj為用戶v中除j以外與最近鄰中用戶所有的共有項的集合；rv,i和ru,j分別為用戶v和用戶u對項i的真實評分；sim(j,i)為項j和i之間的余弦相似度；U為數(shù)據(jù)集中同時擁有項j和i的用戶集合。

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

通過Book-Crossing Dataset來驗證文中方法對推薦結(jié)果的影響。進(jìn)行以下實驗：在基于FP_Growth的矩陣填充中通過設(shè)定不同min_sup和組成用戶興趣的商品數(shù)來測試推薦的效果；通過將改進(jìn)的slope_one預(yù)測評分策略、傳統(tǒng)slope_one預(yù)測評分策略、傳統(tǒng)協(xié)同過濾算法應(yīng)用到相同的數(shù)據(jù)集，測試不同的評分策略對推薦結(jié)果的影響。

3.1 數(shù) 據(jù)

實驗采用的Book-Crossing Dataset來自于informatik網(wǎng)站。該數(shù)據(jù)集由Cai-Nicolas Ziegler在Book-Crossing社區(qū)收集，包含從2004年8月到9月共四個星期的數(shù)據(jù)。其中包括248 858個用戶對271 349本圖書的1 149 780個評分，采用從0到10的不同評分，0表示用戶對其的評價最低，10表示用戶對其的評價最高。用戶通過不同的評分來表示對不同的書籍的興趣。

由于0到10的評分范圍過于寬泛，文中將其壓縮到0到5，即0分為原來的0分，0到2分為1分，依次類推，最后10分為5分。在數(shù)據(jù)集中，評分過多的項不予考慮，過少的項由于非常冷門，同樣予以刪除。

通過以上方法對數(shù)據(jù)集進(jìn)行預(yù)處理后，運用基于FP_Growth的矩陣填充算法對數(shù)據(jù)集進(jìn)行填充，之后按照80%和20%的比例隨機分成訓(xùn)練集和測試集。

3.2 評價標(biāo)準(zhǔn)

采用MAE(平均絕對誤差)對不同算法的推薦效果進(jìn)行評估。MAE是通過測試集中用戶的預(yù)測評分和真實評分之間的偏差程度來評估推薦算法的準(zhǔn)確程度。當(dāng)MAE值越小時，預(yù)測的準(zhǔn)確率越高。MAE的計算公式為：

(9)

3.3 實驗結(jié)果

3.3.1 基于FP_Growth矩陣填充時采用不同的min_sup對協(xié)同過濾推薦效果的影響

由于不同的min_sup對FP_Tree_original的生成產(chǎn)生影響，進(jìn)而影響填充數(shù)據(jù)集的生成。因此，有必要測試不同的min_sup對推薦效果的影響程度,以便采取合適參數(shù)進(jìn)行后面的實驗。填充前對數(shù)據(jù)集進(jìn)行了一定程度的預(yù)處理，將min_sup設(shè)定為5,10,15三種不同的值，組成用戶興趣的商品數(shù)設(shè)定為5，進(jìn)行協(xié)同過濾的推薦實驗。其中k表示最近鄰中的用戶個數(shù)，從10開始，依次增加到15,20,25,30,35,40,45,50，結(jié)果如圖3所示。

圖3 不同min_sup值對推薦效果的影響

從圖3可以看出，最近鄰數(shù)目和min_sup值的變化都會對推薦結(jié)果產(chǎn)生影響。隨著最近鄰數(shù)目的增加，三條線的MAE值都呈下降趨勢，主要原因是最近鄰數(shù)目越大，獲取到的用戶興趣越準(zhǔn)確，推薦效果越好。

通過對比三個不同的min_sup值在相同最近鄰數(shù)目下的效果，得出min_sup越大推薦效果越差。當(dāng)min_sup越大時，數(shù)據(jù)集的頻度較小的數(shù)據(jù)項在生成FP_Tree_original時就不會被考慮到。然而，原數(shù)據(jù)集中頻度較小的書籍占據(jù)較大的比重，被評價的大部分圖書頻度都比較低，造成生成FP_Tree_original的事務(wù)中的圖書個數(shù)減少，最終生成的填充數(shù)據(jù)集隨min_sup的增大而減小，用于訓(xùn)練模型的數(shù)據(jù)集更加稀疏，影響推薦效果。從圖3中得出，當(dāng)min_sup為5時效果最好，將其設(shè)定為5進(jìn)行后面的實驗，能更好地體現(xiàn)不同參數(shù)對推薦結(jié)果的影響。

3.3.2 基于FP_Growth的矩陣填充時采用組成用戶興趣的不同商品數(shù)對協(xié)同過濾推薦效果影響

組成用戶興趣的商品數(shù)會影響待填充的用戶個數(shù)(對用戶列表中少于組成用戶興趣的商品數(shù)的用戶進(jìn)行填充)，進(jìn)而影響到填充數(shù)據(jù)集的規(guī)模，可能會對推薦結(jié)果產(chǎn)生一定的影響。為此，在min_sup為5時，采用組成用戶興趣的商品數(shù)為0,5,10,15四種不同的參數(shù)進(jìn)行測試，如圖4所示。

圖4 不同組成用戶興趣的商品數(shù)對推薦效果的影響

從圖4可以得出，在min_sup=5時，組成用戶興趣的商品數(shù)越大，獲得的推薦效果越好，相對于組成用戶興趣的商品數(shù)而言最近鄰數(shù)目的大小對推薦的影響較小。組成用戶興趣的商品數(shù)越大時，獲取的待填充的用戶越多，生成的填充數(shù)據(jù)集越大，與原始數(shù)據(jù)集合并后數(shù)據(jù)的稀疏度得到很大程度的提高，改善了推薦的效果。同時也證明，數(shù)據(jù)稀疏度相對于最近鄰數(shù)目，對推薦效果的影響更大。

3.3.3 在傳統(tǒng)的協(xié)同過濾中采用不同預(yù)測評分策略對推薦效果的影響

為了驗證提出的slope_one加權(quán)評分的推薦效果，將sup5_tian5與原數(shù)據(jù)集合并作為測試數(shù)據(jù)集，采用傳統(tǒng)的協(xié)同過濾作為推薦方法，對原始評分、slope_one評分和slope_one加權(quán)評分三種不同的預(yù)測評分策略進(jìn)行對比，結(jié)果如圖5所示。

圖5 不同預(yù)測評分策略對推薦效果的影響

從圖5可以得出，隨著最近鄰居數(shù)目的增加，slope_one加權(quán)評分策略的MAE值隨著最近數(shù)目的增加逐漸減小，說明推薦的效果逐漸變好。slope_one加權(quán)評分策略的MAE值在整體上低于其他兩種評分策略。原始預(yù)測評分策略只考慮待評分的項在最近鄰中與用戶評分的平均值之間的差異，slope_one預(yù)測評分策略考慮到了待評分項與所有共有項的評分值之間的差異，而slope_one加權(quán)評分策略在原slope_one預(yù)測評分策略的基礎(chǔ)上考慮到了共有項之間的不同項與待評分項的相似度差異，因此推薦更加準(zhǔn)確。

4 結(jié)束語

人們通過電商平臺在大量圖書中進(jìn)行選擇時困難重重，圖書推薦系統(tǒng)能夠有效地解決這個問題。文中對商品系統(tǒng)默認(rèn)給予的0分重新進(jìn)行評分，有效地解決0分不能體現(xiàn)用戶興趣的問題。針對用戶的歷史數(shù)據(jù)過于稀疏，提出了基于FP_Growth的填充方法；針對傳統(tǒng)協(xié)同過濾推薦效果不佳的問題，提出了改進(jìn)的slope_one評分策略。實驗結(jié)果表明，改進(jìn)后的算法推薦效果提升明顯。未來希望在數(shù)據(jù)集填充方面進(jìn)行更多的探索，同時對基于FP_Gowth和slope_one的協(xié)同過濾算法進(jìn)行進(jìn)一步改進(jìn)，以使其推薦效果更好。