基于FP_Growth和Slope_one的圖書推薦

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

(云南農業大學 大數據學院(信息工程學院)，云南 昆明 650000)

0 引 言

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

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

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

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

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

1 相關工作

1.1 基于用戶的協同過濾算法

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

(1)

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

協同過濾中常用的預測評分策略為：

(2)

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

1.2 FP_Growth算法

FP_Growth是一種求解頻繁項集的關聯規則挖掘算法[16-17]，核心是通過構建FP樹，循環挖掘頻繁項集。步驟如下：

(1)FP樹的構建。

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

構建FP的原始根節點，標記為null。依次將事務數據庫中每條事務中的項按1-項頻繁項集中的順序插入到根節點中。

(2)頻繁項集挖掘。

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

1.3 slope_one算法

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

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

(3)

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

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

(4)

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

2 基于FP_Growth和slope_one的協同過濾算法

2.1 對評分為0的記錄重新進行評分

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

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

(5)

2.2 基于FP_Growth的矩陣填充方法

2.2.1 填充理由

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

2.2.2 填充策略

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

(1)構建FP_original，生成U。

首先，對原數據集按用戶進行分類,生成每個用戶對應的圖書列表，如表1所示。

表1 圖書數據

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

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

最后對事務中用戶對應的圖書個數小于min_interest_num的用戶進行統計。這里將min_interest_num設定為4，獲得的待填充的用戶集合U為{U1,U3,U4,U6,U7,U8}。

圖1 圖書FP_original

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

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

初始條件：

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

list2為生成的該用戶的待填充項。其個數固定但值都為null，循環挖掘就是對null進行填充，直到填滿。

其中list1與list2中的元素個數之和等于min_interest_num。

循環挖掘：

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

if list1為空 then

if list2沒有填滿 then

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

return

else

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

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

FP_cycle(Tree1，list1，list2)

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

圖2是對用戶U1進行挖掘后生成的填充項。

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

(3)填充評分。

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

(6)

2.3 改進slope_one的預測評分策略

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

(7)

(8)

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

3 實驗結果及分析

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

3.1 數 據

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

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

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

3.2 評價標準

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

(9)

3.3 實驗結果

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

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

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

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

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

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

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

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

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

3.3.3 在傳統的協同過濾中采用不同預測評分策略對推薦效果的影響

為了驗證提出的slope_one加權評分的推薦效果，將sup5_tian5與原數據集合并作為測試數據集，采用傳統的協同過濾作為推薦方法，對原始評分、slope_one評分和slope_one加權評分三種不同的預測評分策略進行對比，結果如圖5所示。

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

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

4 結束語

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