劉 華，張亞昕

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

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

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

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

關(guān)聯(lián)規(guī)則[2]是指兩個或多個事物之間如果有某種關(guān)聯(lián)，那么通過一個事物可以預(yù)測其他的關(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頻集算法實現(xiàn)。我們首先，掃描一次數(shù)據(jù)庫，導出頻繁項的集合l項集。然后將頻繁項按降序排列。最后再次掃描數(shù)據(jù)庫，構(gòu)建FP-tree。

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

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

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

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

在這里，針對圖書銷售網(wǎng)站進行推薦系統(tǒng)設(shè)計。該系統(tǒng)與電子商務(wù)系統(tǒng)相互獨立，主要由離線模塊和在線推薦模塊組成。其中離線模塊主要的功能是根據(jù)歷史交易數(shù)據(jù)進行數(shù)據(jù)挖掘運算生成商品關(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)實現(xiàn)

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

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

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

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

3.1.2 數(shù)據(jù)的準備

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

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

數(shù)據(jù)準備的實現(xiàn)方法：可以先將訂單細節(jié)表進行排序，然后只保留訂單號和已訂購圖書編號兩個關(guān)注的目標屬性。從后臺數(shù)據(jù)庫中取出自2013年1月至2013年4月這一時期的部分用戶的購買記錄，共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ù)處理后的數(shù)據(jù)表中涉及的每個訂單中購買的圖書信息組合在一起。數(shù)據(jù)表中的數(shù)據(jù)已經(jīng)做了排序處理，訂單號已經(jīng)集中在一起，所以用程序?qū)崿F(xiàn)生成事務(wù)數(shù)據(jù)庫也很方便。生成的事務(wù)數(shù)據(jù)庫數(shù)據(jù)示意如表3所示。

表3中的數(shù)據(jù)主要是對數(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來實現(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)計單個圖書商品在全部侯選集中出現(xiàn)的次數(shù)與相同事務(wù)在文件中出現(xiàn)的次數(shù)，即事務(wù)的支持度計數(shù)。最后在挖掘出頻繁項的同時，可以計算可信度，從而實現(xiàn)輸出關(guān)聯(lián)規(guī)則。

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

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

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

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

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

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

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

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

4 結(jié)束語

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

[1]趙曉嵐，張招杰.數(shù)字化圖書館個性化推薦研究與實例[J].科技情報開發(fā)與經(jīng)濟，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ù)在電力市場營銷分析中的應(yīng)用[J].電力系統(tǒng)及其自動化學報，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]趙麟.基于最大頻繁模式挖掘算法進行書目推薦系統(tǒng)的設(shè)計與實現(xiàn)[J].現(xiàn)代圖書情報技術(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的最大頻繁項目集綜合更新算法[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-增長算法的復(fù)合項關(guān)聯(lián)規(guī)則挖掘[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.計算機工程與應(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.