改進FP-Growth算法在旅游線路規(guī)劃中的應用研究

字云飛,李業(yè)麗,孫華艷,張莉婧

(北京印刷學院信息工程學院,北京 102600)

0 引 言

在物質生活不斷提高的同時，人們對于精神享受的追求也更迫切了，旅行成為了人們追求高質量生活方式的最直接表達。大數(shù)據(jù)表明2016年國內(nèi)旅游人數(shù)超過40億，這一龐大的數(shù)據(jù)使旅游成為部分地方的支柱產(chǎn)業(yè)。但不管是旅游管理者還是旅行者，在充分利用資源的情況下制定旅游規(guī)劃和選擇旅行線路，并使自身利益最大化成為了當前最大的問題。當前的旅游市場主要是以傳統(tǒng)的主題、超市、運籌學和市場導向為中心的線路規(guī)劃，并沒有利用信息技術革命中大數(shù)據(jù)挖掘和分析帶來的優(yōu)勢，這在旅游線路規(guī)劃中會造成一些不必要的損失。信息革命不斷發(fā)展，人類進入工智能(AI)時代，大數(shù)據(jù)、數(shù)據(jù)挖掘及數(shù)據(jù)分析成為了智能旅游推薦系統(tǒng)的核心技術，同時得到了廣泛應用。因此，通過對關聯(lián)規(guī)則挖掘技術FP-tree算法的改進，應用挖掘的大數(shù)據(jù)進行分析和處理幫助旅游管理者和旅客規(guī)劃出高效、科學及最大效益化的決策，這得到了旅游市場的強烈推薦。

1 FP-Growth算法及其改進

Agrawal等人提出的關聯(lián)規(guī)則[1]挖掘技術Apriori算法[2]的缺點是對原始數(shù)據(jù)庫多次重復遍歷而產(chǎn)生大量候選集。針對Apriori算法的這一缺陷，Han等提出了通過樹形結構來存儲數(shù)據(jù)并進行頻繁模式挖掘的算法—FP-tree算法。FP-tree算法是通過類似于數(shù)據(jù)結構中的樹形結構來存儲原始數(shù)據(jù)庫的核心信息，采用逆尋方式來挖掘頻繁項集，此算法只需對原數(shù)據(jù)庫二次掃描且避免了產(chǎn)生大量候選項集。實驗分析表明Apriori算法的性能比FP-tree算法慢一個數(shù)量級。雖然這2種算法的主要目的都是從數(shù)據(jù)庫中挖掘出頻繁項集，然而兩者算法面對存有海量數(shù)據(jù)的數(shù)據(jù)庫且支持度較小時，使用它們都是不現(xiàn)實的[3-6]。通過FP-Growth算法挖掘頻繁項集時，不僅要多次遞歸條件模式樹，且對樹結構挖掘處理中會生成龐大的子集群，這會開銷掉大量存儲空間，使挖掘效率較低，并且需要占用大量的存儲空間和多次遞歸建立條件模式樹。本文將FP-tree樹形條件模式庫通過數(shù)據(jù)結構中的2個一維數(shù)組來存儲[7-8]，極大減小了樹形結構的存儲開銷，又通過FP-tree算法對節(jié)點進行預剪枝，可以減少對建立條件模式樹和遍歷子集次數(shù)，這對于算法挖掘數(shù)據(jù)的執(zhí)行效率有極大提高[9-10]。

FP-Growth算法[11]的執(zhí)行有2個核心過程：對于FP-tree算法的建樹以及對樹的逆尋遞歸挖掘。算法通過對原數(shù)據(jù)庫的二次遍歷，將這些數(shù)據(jù)存儲在樹結構的節(jié)點上，從而構建FP-tree前綴樹，這也表明通過逆尋過程中前綴路徑名共享實現(xiàn)了對數(shù)據(jù)的壓縮。對已構建好的FP-tree樹逆尋每個項的條件FP-tree、條件模式基以及通過遍歷遞歸挖掘得到支持度-置信度模式的所有頻繁項集。

本文將條件模式庫通過數(shù)據(jù)結構的2個一維數(shù)組存放FP-tree樹的節(jié)點信息，分別為支持度數(shù)組和索引數(shù)組作為改進。如頻繁1項集L={I1,I2,…,In}，則支持度數(shù)組和索引數(shù)組長度等于n，數(shù)組下標從1開始，第0號另用。下面為構建FP-tree的過程：

首先，對1項集的求解。先將支持度數(shù)組設為0，然后通過逆尋遍歷所尋項路徑分支，分支各節(jié)點對應的位置進行支持度累加，掃描完所有分支后，在支持度數(shù)組中記錄各節(jié)點的支持度，存儲樹節(jié)點的支持度。

其次，對于索引數(shù)組的處理。對每個節(jié)點不小于設置的支持度閾值的值從高到低有序存儲于索引數(shù)組中，第0號標記中記錄滿足最小支持度(Minsup)的數(shù)量。這就使1項集在結構樹中的信息按設定的支持度閾值從高到低有序存儲于索引數(shù)組。

最后，構建FP-tree算法的In條件模式樹，通過遍歷In后綴路徑對數(shù)組a[0]進行判斷，看a[0]是否在樹中存在對應節(jié)點，存在計入數(shù)組中，否則存儲為0。當掃描結束后，項目In的條件模式樹也就建成了。

采用此方法建樹及其查找頻繁項集，極大地節(jié)省了空間開銷，提高了建樹和查找頻繁項集的效率。算法偽代碼如下：

Input: constructed FP-tree of according to A database, and a min-sup ξ

Output: maximal frequent item sets(MFIS)

Method: improved FP- tree (FP-tree, α)

Procedure improved FP- tree (FP- tree, α)

{

1)if FP- tree only contains a path of single prex

2)then{

3)generate candidate of maximal frequent item sets β∪α, adjusted item;

4)If β∪α is not a subset of the maximal frequent item sets in MFIS;

5)Then MFIS=MFIS ∪β ∪α;

6)}

7)else{

8)to find nodes from nodes support≥min-sup ξ longest continuous path, record the corresponding item number in a header table as N0;

9)for(N=index array[0]; N≥N0;N--){

10)generate pattern β=an∪α and support=support(an);

11)use improved method of this paper to construct β’s conditional FP-tree Treeβ;

12)if Treeβ≠?

13)then call FP-tree(Treeβ, β);

14)Else{

15)If β is not a subset of MFIS that already has the largest number of frequent item sets;

16)Then MFIS=MFIS∪β;

例11 標準狀況下,往100 mL0.2mol·L-1的FeBr2溶液中通入一定體積的Cl2,充分反應后,溶液中有50%的Br-被氧化。則通入的氯氣的體積是( )。

17)}

18)}

19)}

2 案例分析

以旅游大省云南省為例，從旅游網(wǎng)站采集數(shù)據(jù)，通過算法來挖掘游客最喜歡的旅游線路，優(yōu)化配置旅游市場資源，同時用于旅游行業(yè)的各項判斷，尋找更好的商業(yè)契機。

2.1 算法比較分析

旅游信息系統(tǒng)中，在數(shù)據(jù)庫D中有海量數(shù)據(jù)信息，本文通過表1和表2的數(shù)據(jù)進行算法分析。

表1 旅游目的地

項目編號項目I1昆明I2大理I3麗江I4香格里拉I5西雙版納

表2 旅游網(wǎng)數(shù)據(jù)庫中用戶興趣地調查

TID用戶希望旅游城市01I1，I2，I302I2，I3，I403I1，I504I1，I2，I3，I405I2，I306I1，I4，I507I1，I2，I3，I508I2I3I509I1I2I5

將表2的信息用鄰接矩陣存儲用戶希望旅游城市之間的關系。如表3所示。

表3 鄰接矩陣存儲頻繁1，2-項集

I1I2I3I4I5I164324I247623I336622I422231I543215

通過表3中的數(shù)據(jù)很容易搜索產(chǎn)生頻繁1-項集和2-項集：

1)產(chǎn)生頻繁1-項集。表3中鄰接矩陣對角線上{Ii，Ii}對應的值就是1-項集的支持度，如表4所示。

表4 1-項集支持度表

項集支持度I16I27I36I43I55

2)頻繁2-項集的挖掘。挖掘頻繁2-項集{Ii,Ij}，只需要掃描鄰接矩陣表中第i行和第j列對應數(shù)值，如表5所示。

表5 2-項集支持度表

根據(jù)產(chǎn)生FP-tree樹[12-13]的2個步驟來建立本文案例樹：

根據(jù)支持度數(shù)據(jù)表(表6)，構建FP-tree樹(圖1)，尋路共用相同前綴路徑。

表6 支持度有序表

TID項集(有序的)頻繁項集01I1，I2，I3I2，I3，I102I2，I3，I4I2，I3，I403I1，I5I1，I504I1，I2，I3，I4I2，I1，I3，I405I2，I3I2，I306I1，I4，I5I1，I5，I407I1，I2，I3，I5I2，I1，I3，I508I2，I3，I5I2，I3，I509I1，I2，I5I2，I1，I5

圖1 構建FP-tree樹

通過逆序HT(Header Table)表中的項，產(chǎn)生每個項的條件模式基(表7)，應用HT表中的項，逆尋遍歷結構樹找出對應項的全部前綴路徑，該項(item)的條件模式基(CPB)就是這些前綴路徑，該前綴路徑上項(item)的頻繁度為這些條件模式基(CPB)的頻繁度構成。如圖1構建的FP-tree樹中，包含I4的其中一條路徑是I2I1I3，該路徑中I4的頻繁度為1，則該CPB I2I1I3的頻繁度為1。

表7 條件模式基

項集條件模式基I4I2I1I3：1， I2I3：1I5I2I1：1， I2I1I3I5：1， I2I3：1， I1：2I3I2I1：3， I2：3I1I2：4I2NULL

構造條件FP-tree(conditional FP-tree)。通過累加每個條件模式基(CPB)上的項(item)的頻繁度，去除低于閾值的項(item)，從而構建FP-tree樹。從而很容易在FP-tree樹中得到頻繁3-項集{Ii,Ij,Ik}或者更高頻繁項集。通過設置的最小支持度在已構建的FP-tree中尋路獲取頻繁項集(圖2)。

圖2 挖掘頻繁3-項集

假設設置最小支持度為3，則3-項集{I1，I2，I3}為最終頻繁項集，對于N-項集不再為所需項集。改進后的算法，不但極大減少了頻繁項集量，且對存儲空間也是一個極大的釋放，在計算支持度時，只需要掃描部分鄰接矩陣和所構建FP-tree樹。

然而，當挖掘對象為旅游網(wǎng)站的海量數(shù)據(jù)且支持度較小時，會產(chǎn)生大量頻繁項集，內(nèi)存開銷很大。這時，可以通過索引改進方法彌補這一缺陷。

下面是挖掘項目I3為后綴的最大頻繁集實驗算法步驟。設置最小支持度為3。對2個數(shù)據(jù)結構數(shù)組初始值設為0，對I3為后綴的分支進行逆尋遍歷并對數(shù)組做對應的更新，更新后支持度數(shù)組如圖3所示。

063

圖3 I3條件模式基中的支持度

滿足最小支持度為3的支持度數(shù)組為[1]=6，[2]=3，這樣讓數(shù)組下標1，2存入索引數(shù)組中，如圖4所示。

212

圖4 索引數(shù)組

再對I3為后綴的路徑進行逆尋遍歷，抽取首次遍歷的路徑，把結構樹中的節(jié)點信息存儲于支持度數(shù)組中，如圖5所示。

012

圖5 取出路徑(I2,I1)后的支持度數(shù)組

因此，以I3為后綴的最大頻繁集為{I2,I1,I3}:3。以同樣的方法挖掘以I5為后綴的最大頻繁集所得{I1,I5}:4，以I1為后綴的最大頻繁項目集{I2,I1}:4為已存在最大頻繁項集的子集，故拋棄，其他為不滿足最小支持度。至此本算法的挖掘過程結束，挖掘結果和FP-Growth算法挖掘結果相同。這一改進可以大大減小數(shù)據(jù)存儲的內(nèi)存開銷以及提高執(zhí)行效率。

優(yōu)化算法的同時也需要得到精準的關聯(lián)規(guī)則，當可信度和支持度挖掘出的關聯(lián)規(guī)則完全無法滿足游客對于旅行線路規(guī)劃的判斷時，引入了一個新的標準：通過興趣度來更精準判定強關聯(lián)規(guī)則。

興趣度[14]的主要思想就是：通過支持度-置信度模式，若P(B|A)與P(B)的概率比較后相差較大，可以表明A的存在對B的存在影響很大，規(guī)則A=>B興趣度很高，這也將給用戶的各種選擇及決策過程提供有意義的指導信息。以下為基于概率差值的興趣度定義:

Interest(A->B)=P(B|A)-P(B)

Interest(A->B)的度量有2種可能的情況：

1)如果Interest>0，那么A和B正相關；

2)如果Interest<0，那么A和B負相關。

以表1中的數(shù)據(jù)作一個分析“去昆明(I1)-去大理、麗江(I2，I3)”其興趣度為：

Interest(I1->I2，I3)=P(I2，I3|I1)-P(I2，I3)=1/3

由此得出，該規(guī)則體和結論是正相關的，反映正相關的規(guī)則體“去昆明(I1)-去大理、麗江(I2，I3)”應該加大投入。

2.2 實驗結果與分析

對改進算法性能的分析評估是以Windows 7操作系統(tǒng)作為實驗支撐，相關配置為Inter(R) Pentium CPU G2303主頻3.00 GHz，4 GB內(nèi)存，通過C++語言來實現(xiàn)。樣本數(shù)據(jù)來源于UCI旅游數(shù)據(jù)集，抽取數(shù)據(jù)集中5672條記錄。將改進算法與經(jīng)典FP-Growth算法及Apriori算法進行比較，實驗結果分析表明，改進算法數(shù)據(jù)挖掘效率明顯優(yōu)于FP-Growth算法及Apriori算法，算法比較分析如圖6所示。

圖6 算法執(zhí)行效率比較

根據(jù)實驗結果分析得到，面對海量數(shù)據(jù)，當最小支持度為1.0%時，改進算法的執(zhí)行時間要比FP-Growth算法減少約38%，比Apriori算法減少約67%，表明當挖掘對象為海量數(shù)據(jù)且支持度越小時改進算法的高效性。然而當設定最小支持度≥4.5%時，遍歷迭代次數(shù)急劇減少，所以這幾種算法的執(zhí)行效率相差從0.01%趨于0。

2.3 旅游線路規(guī)劃中數(shù)據(jù)挖掘的結構性系統(tǒng)設計

基于數(shù)據(jù)挖掘技術在旅游市場及線路規(guī)劃系統(tǒng)的在線模塊[15]，能夠為用戶提供在線瀏覽最受歡迎的旅游線路，同時為商家提供游客最喜歡的線路，以便做好更好的服務和獲得最大的收益。在線模塊的具體結構如圖7所示。

圖7 系統(tǒng)體系結構

數(shù)據(jù)挖掘技術中的關聯(lián)規(guī)則模塊是通過對數(shù)據(jù)的清理、轉換以及應用加載工具對初始數(shù)據(jù)庫D的數(shù)據(jù)抽取，同時獲得標準數(shù)據(jù)，對深入挖掘海量數(shù)據(jù)有極大的幫助。對于數(shù)據(jù)挖掘中的關聯(lián)規(guī)則挖掘實施，可以通過對Apriori算法與FP-tree算法進行疊加，然后通過對已挖掘關聯(lián)規(guī)則分析后寫入規(guī)則庫中。

旅游線路規(guī)劃推薦模塊讓消費者通過Web或者APP來訪問，后臺數(shù)據(jù)庫會通過大數(shù)據(jù)平臺記錄用戶的訪問信息，這樣數(shù)據(jù)庫記錄生成相關聯(lián)的數(shù)據(jù)，當網(wǎng)站瀏覽者不知如何規(guī)劃旅游熱線的時候，不需要用戶更多的信息，即可為用戶提出多條相關的旅游熱線和游客最熱衷的旅游熱線，用戶也不用擔心個人信息的泄漏。這些體現(xiàn)了關聯(lián)規(guī)則在旅游線路推薦系統(tǒng)中的智能[16]化特點。應用這一智能模塊，系統(tǒng)可以存儲消費者訪問過程中搜索旅游線路的頻繁數(shù)據(jù)，然后反饋到推薦模塊，最后系統(tǒng)通過分析和預處理將以一定形式把處理好的數(shù)據(jù)推薦給用戶，反饋數(shù)據(jù)以一定的形式返回給系統(tǒng)，從而實現(xiàn)旅游線路推薦的目的。

3 結束語

本文描述了數(shù)據(jù)挖掘FP-Growth算法及其相關改進，并且把基于關聯(lián)規(guī)則挖掘技術應用到旅游線路挖掘中，挖掘最受游客喜愛的旅游線路。對旅游信息系統(tǒng)中的數(shù)據(jù)通過使用FP-tree算法及改進后的算法結果進行比較分析，表明改進后的建樹方法提高了建樹的效率、減少了內(nèi)存開銷同時也提高了查找效率，結果分析驗證了改進后的FP-Growth算法的有效性。改進后的算法有著比較明顯的優(yōu)勢，對于海量的用戶數(shù)據(jù)存儲和細化旅游線路執(zhí)行效率有了更好的提高，這也可以更好地挖掘出消費者喜愛的旅游線路、目的地等重要信息，挖掘結果對旅游線路的設計及規(guī)劃有重要的指導意義。但由于數(shù)據(jù)挖掘技術很多算法都是基于“支持度(support)-置信度(confidence)”這一框架，這樣的模式結構同時也容易挖掘出精確度低或錯誤的數(shù)據(jù)規(guī)則，所以怎樣使用戶的極大需求和系統(tǒng)的高效性相結合，后續(xù)需要做更多的研究應用。

[1] Agrawal R, Imielinski T, Sami A． Mining association rules between sets of items in large database[C]// Proceedings of 1993 ACM SIGMOD International Conference on Management of Data. 1993:207-216．

[2] 馬盈倉． 挖掘關聯(lián)規(guī)則中Apriori算法的改進[J]． 計算機應用與軟件， 2004,21(11):82-84．

[3] 劉娟,宋安軍. 改進FP-Growth算法在氣象預報中的應用[J]. 計算機系統(tǒng)應用, 2016,25(10):199-204.

[4] 廖友金. 基于有向圖的關聯(lián)規(guī)則挖掘研究與改進[D]. 南京:東南大學, 2015.

[5] 晏杰,亓文娟. 基于Aprior & FP-Growth算法的研究[J]. 計算機系統(tǒng)應用, 2013,22(5):122-125.

[6] 周茂恩,柳虹. Apriori和FP-Growth算法在軟考數(shù)據(jù)分析中的應用[C]// 2010 International Conference on Management Science and Engineering. 2010:225-228.

[7] 紀懷猛. 基于改進FP-Tree的最大頻繁項集高效挖掘算法[J]. 計算機與數(shù)字工程， 2014,42(6):959-963.

[8] 楊云,羅艷霞. FP-Growth算法的改進[J]. 計算機工程與設計, 2010,31(7):1506-1509.

[9] 黃劍,李明奇,郭文強. 并行FP-Growth算法在搜索引擎中的應用[J]. 計算機科學, 2015,42(S1):459-461.

[10] 侯長滿,余彪. 關聯(lián)規(guī)則算法FP-Growth的研究與分析[J]. 計算機與網(wǎng)絡， 2016,42(24):58-61.

[11] 遲麗寧. 基于FP-Growth的分類規(guī)則挖掘算法及其應用[D]. 青島:青島大學, 2012.

[12] 劉喜蘋. 基于FP-Growth算法的關聯(lián)規(guī)則挖掘算法研究和應用[D]. 長沙:湖南大學, 2006.

[13] 李志云,周國祥. 基于FP-Growth的關聯(lián)規(guī)則挖掘算法研究[C]// 全國第18屆計算機技術與應用(CACIS)學術會議. 2007:204-206.

[14] 李偉東,倪志偉,劉曉． 基于興趣度的關聯(lián)規(guī)則挖掘[J]． 計算機技術與發(fā)展, 2007,17(6):80-82.

[15] 吳春陽,何友全. 數(shù)據(jù)挖掘技術及其在旅游線路規(guī)劃系統(tǒng)的應用[J]. 計算機技術與發(fā)展, 2008，18(9):235-238.

[16] 朱全,廖光忠. 基于加權關聯(lián)規(guī)則的智慧旅游推薦系統(tǒng)[J]． 工業(yè)控制計算機， 2014(9):116-118．