基于FP-tree算法的推薦系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

劉 華，張亞昕

（西安鐵路職業(yè)技術(shù)學(xué)院 陜西 西安 710014）

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

1 關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘技術(shù)

1.1 關(guān)聯(lián)規(guī)則分析

關(guān)聯(lián)規(guī)則[2]是指兩個(gè)或多個(gè)事物之間如果有某種關(guān)聯(lián)，那么通過一個(gè)事物可以預(yù)測(cè)其他的關(guān)聯(lián)事物。在數(shù)據(jù)挖掘的世界中，關(guān)聯(lián)規(guī)則挖掘目的是為了在大量的數(shù)據(jù)中挖掘隱藏的數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系。

1.2 FP-tree頻集算法

如何得到關(guān)聯(lián)規(guī)則呢，選用FP-tree頻集算法實(shí)現(xiàn)。我們首先，掃描一次數(shù)據(jù)庫，導(dǎo)出頻繁項(xiàng)的集合l項(xiàng)集。然后將頻繁項(xiàng)按降序排列。最后再次掃描數(shù)據(jù)庫，構(gòu)建FP-tree。

FP-tree的建構(gòu)過程[3]：1）創(chuàng)建樹的根節(jié)點(diǎn)，用 null標(biāo)記；2）將每個(gè)事務(wù)中的項(xiàng)按遞減支持度計(jì)數(shù)排列，并對(duì)每個(gè)事務(wù)創(chuàng)建一個(gè)分支；3）當(dāng)為一個(gè)事務(wù)增加分支時(shí)，沿共同前綴路徑上的每一個(gè)節(jié)點(diǎn)的計(jì)數(shù)加一，為跟隨前綴后的項(xiàng)創(chuàng)建連接節(jié)點(diǎn)。比如將第二個(gè)事務(wù){(diào)b，d}加到樹上時(shí)，將為b增計(jì)數(shù)1，然后為d創(chuàng)建一個(gè)分支；4）為便于對(duì)樹的遍歷，我們用一個(gè)節(jié)點(diǎn)鏈指向每項(xiàng)在樹中的位置。

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

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

2 基于FP-tree算法的推薦系統(tǒng)組成及結(jié)構(gòu)

在這里，針對(duì)圖書銷售網(wǎng)站進(jìn)行推薦系統(tǒng)設(shè)計(jì)。該系統(tǒng)與電子商務(wù)系統(tǒng)相互獨(dú)立，主要由離線模塊和在線推薦模塊組成。其中離線模塊主要的功能是根據(jù)歷史交易數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘運(yùn)算生成商品關(guān)聯(lián)規(guī)則，它是推薦系統(tǒng)的核心。而在線推薦模塊的主要功能是獲取用戶歷史購買記錄，然后根據(jù)離線關(guān)聯(lián)規(guī)則生成模塊生成的關(guān)聯(lián)規(guī)則為用戶提供推薦服務(wù)。

基于FP-tree算法的推薦系統(tǒng)結(jié)構(gòu)如圖1所示。

圖1 推薦系統(tǒng)結(jié)構(gòu)圖Fig.1 Recommended system structure

3 基于FP-tree算法的推薦系統(tǒng)實(shí)現(xiàn)

離線模塊是整個(gè)推薦系統(tǒng)的核心，而在線模塊主要是通過調(diào)用離線模塊生成的關(guān)聯(lián)規(guī)則表的相關(guān)數(shù)據(jù)以動(dòng)態(tài)網(wǎng)頁的形式為用戶推薦商品的，相對(duì)來說比較容易實(shí)現(xiàn)。因而在這里我們關(guān)注離線模塊的實(shí)現(xiàn)。

3.1 離線模塊的實(shí)現(xiàn)

3.1.1 獲取數(shù)據(jù)源

關(guān)聯(lián)規(guī)則推薦系統(tǒng)的數(shù)據(jù)源一般是一段時(shí)期內(nèi)的歷史交易數(shù)據(jù)。在用戶購買商品的過程中，都要準(zhǔn)確填寫購物單，這些購物單會(huì)保存在電子商務(wù)網(wǎng)站的后臺(tái)數(shù)據(jù)庫中。我們就利用這些數(shù)據(jù)作為挖掘的優(yōu)質(zhì)數(shù)據(jù)。文中研究的圖書銷售網(wǎng)站的歷史交易數(shù)據(jù)主要集中在訂單信息表和訂單細(xì)節(jié)表中。為了得到近來一段時(shí)間范圍內(nèi)的訂單號(hào)和訂購圖書號(hào)的列表內(nèi)容。我們可以采用對(duì)訂單表和訂單細(xì)節(jié)表的聯(lián)合查詢得到相關(guān)數(shù)據(jù)。

3.1.2 數(shù)據(jù)的準(zhǔn)備

雖然我們的數(shù)據(jù)源是以訂單表為主，信息準(zhǔn)確無誤。但是實(shí)際業(yè)務(wù)中的數(shù)據(jù)結(jié)構(gòu)比較分散，無法直接使用。因而必須要將數(shù)據(jù)進(jìn)行預(yù)處理。將數(shù)據(jù)準(zhǔn)備分為兩個(gè)階段：一是去掉無意義和干擾數(shù)據(jù)，二是轉(zhuǎn)換格式。

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

數(shù)據(jù)準(zhǔn)備的實(shí)現(xiàn)方法：可以先將訂單細(xì)節(jié)表進(jìn)行排序，然后只保留訂單號(hào)和已訂購圖書編號(hào)兩個(gè)關(guān)注的目標(biāo)屬性。從后臺(tái)數(shù)據(jù)庫中取出自2013年1月至2013年4月這一時(shí)期的部分用戶的購買記錄，共20000條，采用了SQLSERVER2000數(shù)據(jù)庫基于SQL查詢的數(shù)據(jù)轉(zhuǎn)換工具DTS來整理出所需的數(shù)據(jù)表。

所用SQL如下：

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

采集出的初始數(shù)據(jù)表如表1所示。

表1 采集好的數(shù)據(jù)表Tab.1 Collecting good data sheet

接著再次利用DTS數(shù)據(jù)轉(zhuǎn)換工具清除無意義的數(shù)據(jù)和干擾數(shù)據(jù)。

所用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種商品的訂單排序主要為以后處理格式文件的方便。

數(shù)據(jù)預(yù)處理后的得到的結(jié)果如表2所示。

表2 預(yù)處理后的數(shù)據(jù)表Tab.2 Data Sheet preprocessed

3.1.3 基于FP-tree關(guān)聯(lián)挖掘運(yùn)算

要將預(yù)處理后的數(shù)據(jù)表中涉及的每個(gè)訂單中購買的圖書信息組合在一起。數(shù)據(jù)表中的數(shù)據(jù)已經(jīng)做了排序處理，訂單號(hào)已經(jīng)集中在一起，所以用程序?qū)崿F(xiàn)生成事務(wù)數(shù)據(jù)庫也很方便。生成的事務(wù)數(shù)據(jù)庫數(shù)據(jù)示意如表3所示。

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

表3 數(shù)據(jù)庫Tab.3 Database

所用SQL如下：

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

有了事務(wù)數(shù)據(jù)集“transaction.txt”文件。接下來統(tǒng)計(jì)單個(gè)圖書商品在全部侯選集中出現(xiàn)的次數(shù)與相同事務(wù)在文件中出現(xiàn)的次數(shù)，即事務(wù)的支持度計(jì)數(shù)。最后在挖掘出頻繁項(xiàng)的同時(shí)，可以計(jì)算可信度，從而實(shí)現(xiàn)輸出關(guān)聯(lián)規(guī)則。

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

圖2 實(shí)現(xiàn)FP-tree算法的具體流程Fig.2 Achieve specific processes FP-tree algorithm

程序執(zhí)行后，生成的挖掘結(jié)果保存在“association_rule.txt”文本文件中，接下來將文本文件導(dǎo)入數(shù)據(jù)庫。如表3所示。

表3 關(guān)聯(lián)規(guī)則數(shù)據(jù)表Tab.3 Association rules data sheet

這樣，通過FP-tree的挖掘計(jì)算，將得到一個(gè)商品對(duì)商品的關(guān)聯(lián)規(guī)則文件，表3中第一列代表圖書編號(hào)，第二列代表關(guān)聯(lián)的圖書編號(hào)，第三列代表可信度。其中可信度就是判斷關(guān)聯(lián)規(guī)則優(yōu)劣的指標(biāo)。在同樣滿足支持度的情況下，認(rèn)為可信度高的規(guī)則更精確。

接著，將關(guān)聯(lián)規(guī)則結(jié)果association_rule表采用SQLSERVER DTS的方式進(jìn)行導(dǎo)入到個(gè)性化推薦的數(shù)據(jù)庫中。關(guān)聯(lián)規(guī)則的數(shù)據(jù)表配合復(fù)制的電子商務(wù)系統(tǒng)中圖書信息表的數(shù)據(jù)就可以為用戶進(jìn)行個(gè)性化推薦了。

3.2 在線模塊的實(shí)現(xiàn)

我們將離線模塊得到的關(guān)聯(lián)規(guī)則數(shù)據(jù)表導(dǎo)入到后臺(tái)數(shù)據(jù)庫，并以動(dòng)態(tài)網(wǎng)頁來實(shí)現(xiàn)推薦。

4 結(jié)束語

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

[1]趙曉嵐，張招杰.數(shù)字化圖書館個(gè)性化推薦研究與實(shí)例[J].科技情報(bào)開發(fā)與經(jīng)濟(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]侯雪波，田斌，葛少云，等.關(guān)聯(lián)規(guī)則技術(shù)在電力市場(chǎng)營銷分析中的應(yīng)用[J].電力系統(tǒng)及其自動(dòng)化學(xué)報(bào)，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ìn)行書目推薦系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].現(xiàn)代圖書情報(bào)技術(shù)，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的最大頻繁項(xiàng)目集綜合更新算法[J].安徽教育學(xué)院學(xué)報(bào)，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]顏躍進(jìn)，李舟軍，陳火旺.基于FP-Tree有效挖掘最大頻繁項(xiàng)集[J].軟件學(xué)報(bào)，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-增長算法的復(fù)合項(xiàng)關(guān)聯(lián)規(guī)則挖掘[J].計(jì)算機(jī)工程與應(yīng)用，2005（2）:182-183.LIU Chuan，F(xiàn)ANG 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-樹挖掘大數(shù)據(jù)庫的方法及算法PCM.計(jì)算機(jī)工程與應(yīng)用，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.