船舶管理中基于負(fù)載平衡的并行 FP-growth算法研究

尚 弘，徐平平，姚 湘

(1.無錫太湖學(xué)院 江蘇省物聯(lián)網(wǎng)應(yīng)用技術(shù)重點建設(shè)實驗室，江蘇 無錫 214064；2.東南大學(xué) 信息科學(xué)與工程學(xué)院，江蘇 南京 210096)

0 引 言

近年來，物聯(lián)網(wǎng)技術(shù)發(fā)展迅猛，各行業(yè)的數(shù)據(jù)都呈現(xiàn)井噴趨勢，大數(shù)據(jù)已經(jīng)成為規(guī)模龐大的船舶運(yùn)營管理中不可或缺的一部分。將數(shù)據(jù)技術(shù)應(yīng)用到船舶管理領(lǐng)域，不僅限于將采集的數(shù)據(jù)信息化、可視化，更重要的是通過深度挖掘技術(shù)，將數(shù)據(jù)中所蘊(yùn)含的信息應(yīng)用于智能化船舶安全管理、船舶資源管理、物流貿(mào)易等領(lǐng)域，發(fā)揮大數(shù)據(jù)和人工智能技術(shù)在促進(jìn)經(jīng)濟(jì)發(fā)展、提高航運(yùn)貿(mào)易量及船舶運(yùn)能中的積極作用，從而推動整個行業(yè)快速前行。

1993年，R.Agrawal等提出了關(guān)聯(lián)規(guī)則的概念及其模型，目前最經(jīng)典的是1994年R.Agrawal等提出的Apriori算法和2000年Han等提出的FP-growth算法[1]。胡曉軒將改進(jìn)型Apriori算法應(yīng)用于船舶安全管理中，通過對生產(chǎn)中的考核指標(biāo)進(jìn)行挖掘分析，發(fā)現(xiàn)指標(biāo)間的高度關(guān)聯(lián)關(guān)系，分析和事故的相關(guān)性，并將其作為預(yù)警因子，提前預(yù)防安全事故的發(fā)生[2]。孫斌采用改進(jìn)的多維Apriori算法，挖掘人為失誤導(dǎo)致船舶碰撞事故的頻繁因素組合，并對該人為失誤致因進(jìn)行分析[3]，以此來提高船舶航行的安全系數(shù)。顧洵瑜等提出利用FP-growth算法，采用分治方式，不產(chǎn)生候選項集[4]，直接挖掘船舶滯留原因間的潛在關(guān)聯(lián)，分析滯留原因，進(jìn)行針對性檢查，提高安全檢查效率。

相對Apriori算法而言，F(xiàn)P-growth算法的效率明顯提升，但當(dāng)數(shù)據(jù)量快速增長時，該算法構(gòu)建的頻繁模式樹（Frequent Pattern tree，F(xiàn)P-tree）在橫向和縱向的維度上會越來越大，不僅容易造成FP-tree構(gòu)建過程中出錯，而且也會導(dǎo)致在頻繁項集的遞歸挖掘過程中花費(fèi)更多時間，造成挖掘效率低下。由于Spark采用了彈性分布式架構(gòu)的編程接口，ZHANG Feng等提出了基于Spark框架的分布式頻繁項集挖掘方法[5]，該方法能很好地適用于大數(shù)據(jù)挖掘。章志剛等提出并行挖掘算法FPPM，該算法首先在各分計算節(jié)點上挖掘頻繁項集，然后將各頻繁項集進(jìn)行合并得到全部的頻繁項集，最后對不滿足最小支持度要求的頻繁項集再次計算支持度[6]。

為了進(jìn)一步提高船舶管理中數(shù)據(jù)挖掘效率，本文提出基于負(fù)載平衡的并行FP-growth數(shù)據(jù)挖掘算法，將原來在一個分區(qū)節(jié)點對整個FP樹的挖掘轉(zhuǎn)換為在多個分區(qū)節(jié)點上對分組FP樹的挖掘，不僅簡化了頻繁項集的挖掘過程，減少了計算量，而且通過負(fù)載均衡技術(shù)，使多分區(qū)節(jié)點并行運(yùn)算，壓縮了挖掘時間。實驗表明，該算法能夠較好地提高船舶管理中數(shù)據(jù)挖掘的效率，并具有較好的可擴(kuò)展性。

1 FP-growth算法描述

FP-growth算法將數(shù)據(jù)映射到FP-tree上，通過遞歸的方法，挖掘出全部頻繁項集。FP-growth算法的基本過程分為2個步驟[7]：

步驟1構(gòu)建FP樹

1）遍歷數(shù)據(jù)集，統(tǒng)計各元素出現(xiàn)的次數(shù)，創(chuàng)建頭指針表；

2）將小于最小支持度的項從頭指針表中剔除；

3）再次對數(shù)據(jù)集遍歷，過濾和重排序每個元素項，并創(chuàng)建根節(jié)點為NULL的樹fp_t。

步驟2挖掘頻繁項集

1）從頭指針表中最下面的頻繁元素項開始，根據(jù)相同類型元素鏈表的指針，向上遍歷fp_t，得到其相應(yīng)的條件模式基α；

2）基于步驟1的數(shù)據(jù)，構(gòu)建FP樹，并將小于最小支持度的元素項剔除掉，從而挖掘出頻繁項集；

3）迭代重復(fù)步驟1和步驟2，挖掘獲取所有的頻繁項集β。

2 基于負(fù)載平衡的并行FP-growth算法研究

2.1 關(guān)聯(lián)規(guī)則相關(guān)概念

關(guān)聯(lián)規(guī)則是用于表示元素項之間關(guān)聯(lián)關(guān)系的一種形式，對于2個互斥的元素項X和Y，可以用X?Y來表示X出現(xiàn)將導(dǎo)致Y出現(xiàn)。可用支持度和置信度來實現(xiàn)對關(guān)聯(lián)規(guī)則的度量。

設(shè)I為m個互斥元素項組成的集合。

定義1對于關(guān)聯(lián)規(guī)則R：X?Y，其中X?I，Y?I。規(guī)則R的的支持度（Support）是數(shù)據(jù)集中X和Y同時出現(xiàn)的記錄數(shù)與所有記錄數(shù)之比，即

定義2對于關(guān)聯(lián)規(guī)則R：X?Y，其中X?I，Y?I。規(guī)則R的置信度（Confidence）是數(shù)據(jù)集中X和Y同時出現(xiàn)的記錄數(shù)與只有X出現(xiàn)的記錄數(shù)之比，即

定義3最小支持度和最小置信度，最小支持度（Minimum Support，minsup）從統(tǒng)計分析的角度表示元素項的最低重要性；最小置信度（Minimum Confidence，minconf）從統(tǒng)計分析的角度表示關(guān)聯(lián)規(guī)則的最低可靠性。

關(guān)聯(lián)規(guī)則的挖掘?qū)嶋H上就是從所有滿足最小支持度的項集中挖掘滿足最小置信度的規(guī)則的過程，也就是挖掘強(qiáng)關(guān)聯(lián)規(guī)則的過程[8]。

2.2 算法基本思想

本文提出的基于負(fù)載平衡的并行FP-growth數(shù)據(jù)挖掘算法基于以下結(jié)論：

1）頻繁項集的子集是頻繁的。

2）設(shè)元素i?I，support（i）≥ minsup，k-FItemS（i）為所有包含元素i的k項頻繁項集，則k-FItemS（i）的并集為項目集I的頻繁項集。

2.3 算法項目樹構(gòu)建

在對海量的船舶管理數(shù)據(jù)進(jìn)行關(guān)聯(lián)挖掘時，構(gòu)建的FP-Tree在橫向和縱向維度上會變的非常龐大，挖掘效率也會隨之而降低。為解決此問題，本文提出一種基于時間片段和TID的項目樹構(gòu)建方法。對任意滿足i?I的元素，系統(tǒng)按照一定的規(guī)則和順序分配一個唯一的TID，對任意T?I，首先，按照TID（i）對T中的元素進(jìn)行排序，將T存入數(shù)據(jù)庫的同時，按照系統(tǒng)事先設(shè)置的時間片段值，構(gòu)建項目樹，為壓縮樹存儲空間，相同前綴的路徑可以共用，通過鏈接，相同元素被連接成為一個鏈表。在構(gòu)建項目樹的同時，為項目樹構(gòu)建頭表節(jié)點，頭表中元素按照TID的升序排列，數(shù)據(jù)結(jié)構(gòu)為ItemName：TID：count：Node-Links，其中，Node-Links指向項目樹中與它同名的節(jié)點，如圖1所示。

圖1 項目樹Fig.1 Project tree

2.4 算法實現(xiàn)

BPFP-growth算法主要分為4個核心部分：

1）計算數(shù)據(jù)庫項目集中的1-項頻繁項集。

為了挖掘1-項頻繁項集，首先根據(jù)項目樹集的頭表htab值建立矩陣模型，通過式（3）計算1-項集支持度：

遍歷過濾掉小于最小支持度閾值的元素項，挖掘獲取所有的1-項頻繁項集α。

2）掃描項目樹，產(chǎn)生并行分組子項，結(jié)果存儲在單獨的數(shù)據(jù)庫文件中。

并行分組是該算法中最核心的一環(huán)，根據(jù)算法的基本思想，對上述挖掘獲取的1-項頻繁項集α中的元素項集{a1，a2，···，an}，循環(huán)掃描項目樹 ptree，通過對數(shù)據(jù)項進(jìn)行過濾、剪枝，構(gòu)建頭結(jié)點為ai的分組子項集pns_t。

3）計算負(fù)載因子，根據(jù)負(fù)載因子完成并行分組，結(jié)果存儲在分布式文件中。

并行挖掘中的分組是非常重要的環(huán)節(jié)，因為在并行挖掘中，各分區(qū)節(jié)點中最后一個完成挖掘任務(wù)節(jié)點的結(jié)束時間決定了整個系統(tǒng)最終的結(jié)束時間，因此，如何分配任務(wù)，使各分區(qū)節(jié)點的任務(wù)相對平衡，分組策略就顯得非常關(guān)鍵。

在構(gòu)建分組子項樹時，從根節(jié)點到葉子節(jié)點的支持度逐步降低，搜索路徑逐步減少，且分組中節(jié)點數(shù)量也不盡相同。本文綜合考慮節(jié)點數(shù)量和路徑長度，賦予不同的權(quán)重wi。若同一層搜索路徑內(nèi)的節(jié)點數(shù)量為bi，可通過下式計算分組子項的負(fù)載因子：

循環(huán)遍歷分組子項集pns_t，構(gòu)建生成對應(yīng)的FP樹分組子項集fp_pns_t，通過式（4）計算分組子項集fp_pns_t中每個分組子項的負(fù)載因子，根據(jù)負(fù)載因子完成負(fù)載平衡分組gr_fp_t。

4）挖掘頻繁項集。

在每個計算節(jié)點上，并行讀取分布式文件，循環(huán)遍歷挖掘負(fù)載平衡分組gr_fp_t中的各子項集，生成分組頻繁項集，匯總各計算節(jié)點挖掘結(jié)果求得全局頻繁項集β。

3 實驗與結(jié)果分析

為了驗證本文提出的BPFP-growth算法在船舶管理數(shù)據(jù)挖掘中的有效性和可擴(kuò)展性，構(gòu)建3個節(jié)點組成的并行計算平臺。隨機(jī)抽取10 000條數(shù)據(jù)作為實驗數(shù)據(jù)集，實驗測試結(jié)果如下：

1）BPFP-growth算法與FP-growth算法性能比較

在最小支持度為10的情況下，分別選取1 000條、2 000 條、3 000 條、······、10 000 條的數(shù)據(jù)集，將 BPFP-growth算法在2個并行分區(qū)計算節(jié)點和3個并行分區(qū)計算節(jié)點上的運(yùn)算性能與傳統(tǒng)的FP-growth算法進(jìn)行對比測試，實驗結(jié)果如圖2所示。

從圖2可以看出，不論采用何種挖掘算法，當(dāng)數(shù)據(jù)集增大時，挖掘的數(shù)據(jù)量增大，頻繁項集增多，遞歸挖掘所需要的資源和運(yùn)算次數(shù)增多，導(dǎo)致挖掘的復(fù)雜度增大，最終使整個系統(tǒng)的挖掘時間延長。

圖2 BPFP-growth算法與FP-growth算法性能比較Fig.2 Performance comparison between BPFP-growth algorithm and FP-growth algorithm

另外，從圖2還可以看出，當(dāng)并行分區(qū)計算節(jié)點增多時，數(shù)據(jù)被平衡分布到更多的計算節(jié)點，所以，對于單個計算節(jié)點而言，所要處理的數(shù)據(jù)量減少，相應(yīng)所花費(fèi)的挖掘時間也縮短，呈現(xiàn)線性下降趨勢。因此該算法具有較好的可擴(kuò)展性。

2）BPFP-growth算法自身性能分析

當(dāng)最小支持度為5，10，20的情況下，分別選取1 000 條、2 000 條、3 000 條、······、10 000 條的數(shù)據(jù)集在3個并行分區(qū)計算節(jié)點上進(jìn)行對比測試，實驗結(jié)果如圖3所示。

圖3 BPFP-growth算法自身性能分析Fig.3 Performance analysis of BPFP-growth algorithms

可以看出，當(dāng)選定的最小支持度增大時，被剔除掉的項目數(shù)將增多，這時剩余項目數(shù)減少，挖掘的數(shù)據(jù)集規(guī)模降低，使得遞歸挖掘所需要的資源和運(yùn)算的次數(shù)減少，計算復(fù)雜度降低，縮短了整個數(shù)據(jù)挖掘的時間。

4 結(jié) 語

本文提出的BPFP-growth算法基于鏡像重構(gòu)技術(shù)對數(shù)據(jù)集進(jìn)行切割，然后通過負(fù)載因子完成切割數(shù)據(jù)的并行分組與挖掘。實驗結(jié)果表明，該算法在面向船舶管理大數(shù)據(jù)的頻繁項集挖掘時，具有較好的可并行性和可伸縮性，可以有效挖掘出高度相關(guān)的頻繁項集，從而能夠利用該頻繁項集完成船舶運(yùn)營中的安全管理、事故原因分析等，大大降低事故發(fā)生率，提高資源的配置效率。