基于FP-tree算法的推薦系統設計與實現

劉 華，張亞昕

（西安鐵路職業技術學院 陜西 西安 710014）

互聯網技術的迅速發展給我們普通人生活帶來了翻天覆地的變化，它為我們提供了海量的信息。但信息量大而導致其利用率降低卻是個不爭的事實。在這種情況下，推薦系統脫穎而出，成為當前解決該問題的有效工具，受到廣大學者的關注和研究。20世紀90年代中后期，大量的電子商務興起。為了提高自身競爭力，幾乎所有大型電子商務網站利用推薦系統來營銷。更有文獻表明，早期Amazon的35%銷售增長值都來自它的推薦系統。推薦系統[1]就是在用戶和商品信息之間建立二元關系，挖掘出用戶存在的消費傾向，為更多用戶提供推薦服務。

1 關聯規則數據挖掘技術

1.1 關聯規則分析

關聯規則[2]是指兩個或多個事物之間如果有某種關聯，那么通過一個事物可以預測其他的關聯事物。在數據挖掘的世界中，關聯規則挖掘目的是為了在大量的數據中挖掘隱藏的數據之間的關聯關系。

1.2 FP-tree頻集算法

如何得到關聯規則呢，選用FP-tree頻集算法實現。我們首先，掃描一次數據庫，導出頻繁項的集合l項集。然后將頻繁項按降序排列。最后再次掃描數據庫，構建FP-tree。

FP-tree的建構過程[3]：1）創建樹的根節點，用 null標記；2）將每個事務中的項按遞減支持度計數排列，并對每個事務創建一個分支；3）當為一個事務增加分支時，沿共同前綴路徑上的每一個節點的計數加一，為跟隨前綴后的項創建連接節點。比如將第二個事務{b，d}加到樹上時，將為b增計數1，然后為d創建一個分支；4）為便于對樹的遍歷，我們用一個節點鏈指向每項在樹中的位置。

FP-tree的挖掘簡述如下[4]，由長度為l的頻繁模式開始，構造它的子數據庫 （由FP-tree中與后綴模式一起出現的前綴路徑集組成）構造該初始后綴模式的條件FP-tree，并遞歸的對該樹實現挖掘。模式增長通過后綴模式與條件FP-tree產生的頻繁模式連接實現。

FP-tree算法只掃描數據庫兩次，它有效的減少挖掘所需的I/O“成本”，而且它不會產生龐大的候選集，從而減少了內存臨時空間的占用[5]。

2 基于FP-tree算法的推薦系統組成及結構

在這里，針對圖書銷售網站進行推薦系統設計。該系統與電子商務系統相互獨立，主要由離線模塊和在線推薦模塊組成。其中離線模塊主要的功能是根據歷史交易數據進行數據挖掘運算生成商品關聯規則，它是推薦系統的核心。而在線推薦模塊的主要功能是獲取用戶歷史購買記錄，然后根據離線關聯規則生成模塊生成的關聯規則為用戶提供推薦服務。

基于FP-tree算法的推薦系統結構如圖1所示。

圖1 推薦系統結構圖Fig.1 Recommended system structure

3 基于FP-tree算法的推薦系統實現

離線模塊是整個推薦系統的核心，而在線模塊主要是通過調用離線模塊生成的關聯規則表的相關數據以動態網頁的形式為用戶推薦商品的，相對來說比較容易實現。因而在這里我們關注離線模塊的實現。

3.1 離線模塊的實現

3.1.1 獲取數據源

關聯規則推薦系統的數據源一般是一段時期內的歷史交易數據。在用戶購買商品的過程中，都要準確填寫購物單，這些購物單會保存在電子商務網站的后臺數據庫中。我們就利用這些數據作為挖掘的優質數據。文中研究的圖書銷售網站的歷史交易數據主要集中在訂單信息表和訂單細節表中。為了得到近來一段時間范圍內的訂單號和訂購圖書號的列表內容。我們可以采用對訂單表和訂單細節表的聯合查詢得到相關數據。

3.1.2 數據的準備

雖然我們的數據源是以訂單表為主，信息準確無誤。但是實際業務中的數據結構比較分散，無法直接使用。因而必須要將數據進行預處理。將數據準備分為兩個階段：一是去掉無意義和干擾數據，二是轉換格式。

關聯規則的目的就在于能夠找到人們在購買商品A就很可能買商品B這樣的規律。因而我們所關注的交易長度肯定大于1的數據信息，那么訂單中在只包含一件商品的數據沒有任何意義應該刪除掉。還有，訂單中若有太多商品，那么也是值得考慮它的合理性。例如有的圖書館或學校等機構通過網購的形式采購圖書，那么一次性購買的圖書的量會很大，甚至有上千本的情況。這種訂單信息若也參與運算中，不僅影響挖掘的準確性，而且會大大增加挖掘計算的難度。根據實際網上調查，我們發現個人購買圖書數量范圍基本上是1至4本。那么我們的將超過5本的訂單信息做為干擾數據，此類數據也應該清除掉。接下來，我們就要考慮挖掘的數據格式了。在實際數據挖掘時，一般要將數據信息轉換為文本型。并且將訂單號的位數后面加空格字符補齊為10位。

數據準備的實現方法：可以先將訂單細節表進行排序，然后只保留訂單號和已訂購圖書編號兩個關注的目標屬性。從后臺數據庫中取出自2013年1月至2013年4月這一時期的部分用戶的購買記錄，共20000條，采用了SQLSERVER2000數據庫基于SQL查詢的數據轉換工具DTS來整理出所需的數據表。

所用SQL如下：

CREATE TABLE [transcactionnew].[dbo].[order_book]（[orderid]char（10） NOTNULL， [bookid]char（13） NOTNULL）

采集出的初始數據表如表1所示。

表1 采集好的數據表Tab.1 Collecting good data sheet

接著再次利用DTS數據轉換工具清除無意義的數據和干擾數據。

所用SQL如下：

Select a.orderid a.bookid from order_detail where a.orderid not in （select distinct orderid，count （*）from order_detail group by orderid having count（*）=1 or count（*）>5）order by orderid，bookid；

其中條件過濾掉只有一種商品或超過5種商品的訂單排序主要為以后處理格式文件的方便。

數據預處理后的得到的結果如表2所示。

表2 預處理后的數據表Tab.2 Data Sheet preprocessed

3.1.3 基于FP-tree關聯挖掘運算

要將預處理后的數據表中涉及的每個訂單中購買的圖書信息組合在一起。數據表中的數據已經做了排序處理，訂單號已經集中在一起，所以用程序實現生成事務數據庫也很方便。生成的事務數據庫數據示意如表3所示。

表3中的數據主要是對數據組合情況予以說明。真正的事務數據我們是采取文本方式處理的。我們先將預處理數據后得到的數據表轉換輸出為文本形式。我們注意在轉換過程中將orderid字段的數據類型轉換為char，寬度改為11位。數據轉換過程仍然用DTS來實現。

表3 數據庫Tab.3 Database

所用SQL如下：

CREATE TABLE C: ransaction.txt （orderid varchar （11）NOT NULL， bookid varchar（13） NOT NULL）

有了事務數據集“transaction.txt”文件。接下來統計單個圖書商品在全部侯選集中出現的次數與相同事務在文件中出現的次數，即事務的支持度計數。最后在挖掘出頻繁項的同時，可以計算可信度，從而實現輸出關聯規則。

FP-tree具體算法流程[6]如圖2所示。

圖2 實現FP-tree算法的具體流程Fig.2 Achieve specific processes FP-tree algorithm

程序執行后，生成的挖掘結果保存在“association_rule.txt”文本文件中，接下來將文本文件導入數據庫。如表3所示。

表3 關聯規則數據表Tab.3 Association rules data sheet

這樣，通過FP-tree的挖掘計算，將得到一個商品對商品的關聯規則文件，表3中第一列代表圖書編號，第二列代表關聯的圖書編號，第三列代表可信度。其中可信度就是判斷關聯規則優劣的指標。在同樣滿足支持度的情況下，認為可信度高的規則更精確。

接著，將關聯規則結果association_rule表采用SQLSERVER DTS的方式進行導入到個性化推薦的數據庫中。關聯規則的數據表配合復制的電子商務系統中圖書信息表的數據就可以為用戶進行個性化推薦了。

3.2 在線模塊的實現

我們將離線模塊得到的關聯規則數據表導入到后臺數據庫，并以動態網頁來實現推薦。

4 結束語

文中在對FP-tree關聯規則算法及其在推薦系統中的應用進行深入的研究后，發現這種推薦方式很有優勢。但是，它仍然存在耗時和復雜兩大缺陷[7]。因而，在實際的挖掘運算處理過程中，一定要在充分的理解數據的基礎上，做好數據的準備工作，同時還要注意選擇合適的最小支持度閾值和最小置信度閾值，這樣才能極大的發揮FP-tree關聯規則推薦算法的優勢。

[1]趙曉嵐，張招杰.數字化圖書館個性化推薦研究與實例[J].科技情報開發與經濟，2011（23）:6-8.ZHAO Xiao-lan，Zhang-zhao Jie.Personalized recommendations digital library research and examples[J].Sci-Tech Information Development&Economy，2011（23）:6-8.

[2]侯雪波，田斌，葛少云，等.關聯規則技術在電力市場營銷分析中的應用[J].電力系統及其自動化學報，2005（2）:67-71.HOU Xue-bo，TIAN Bin，GE Shao-yun，et al.Application association rules technology in electric power marketing analysis[J].Systems EPSA，2005（2）:67-71.

[3]趙麟.基于最大頻繁模式挖掘算法進行書目推薦系統的設計與實現[J].現代圖書情報技術，2010（5）:23-24，28.ZHAO Lin.Frequent pattern mining algorithm based on maximum design and implementation of bibliographic recommendation system[J].conducted Modern Library and Information Technology，2010（5）:23-24，28.

[4]趙群禮.基于FP-Tree的最大頻繁項目集綜合更新算法[J].安徽教育學院學報，2006（3）:42-43.ZHAO Qun-li.ceremony.Based on FP-Tree maximum frequent integrated updating algorithm[J].Anhui Institute of Education，2006（3）:42-43.

[5]顏躍進，李舟軍，陳火旺.基于FP-Tree有效挖掘最大頻繁項集[J].軟件學報，2005（2）:88-89.YAN Yue-jin， LIZhou-jun，CHEN Huo-wang.FP-Tree valid mining maximal frequent itemsets[J].Journal of Software，2005（2）:88-89.

[6]劉川，方思行.基于FP-增長算法的復合項關聯規則挖掘[J].計算機工程與應用，2005（2）:182-183.LIU Chuan，FANG Si-xing of thinking based on a composite term association rules mining algorithm FP-growth Computer Engineering and Applications，2005（2）:182-183.

[7]鄭泉，王建東.基于FP-樹挖掘大數據庫的方法及算法PCM.計算機工程與應用，2004（3）:182-184.ZHENG Quan，WANG Jian-dong.FP-tree method of mining large databases and algorithms PCM.based[J].Computer Engineering and Applications，2004（3）:182-184.