尚 弘，徐平平，姚 湘

(1.無錫太湖學(xué)院 江蘇省物聯(lián)網(wǎng)應(yīng)用技術(shù)重點(diǎn)建設(shè)實(shí)驗(yàn)室，江蘇 無錫 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)能中的積極作用，從而推動(dòng)整個(gè)行業(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)生候選項(xiàng)集[4]，直接挖掘船舶滯留原因間的潛在關(guān)聯(lián)，分析滯留原因，進(jìn)行針對性檢查，提高安全檢查效率。

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

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

1 FP-growth算法描述

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

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

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

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

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

步驟2挖掘頻繁項(xiàng)集

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

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

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

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

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

關(guān)聯(lián)規(guī)則是用于表示元素項(xiàng)之間關(guān)聯(lián)關(guān)系的一種形式，對于2個(gè)互斥的元素項(xiàng)X和Y，可以用X?Y來表示X出現(xiàn)將導(dǎo)致Y出現(xiàn)?？捎弥С侄群椭眯哦葋韺?shí)現(xiàn)對關(guān)聯(lián)規(guī)則的度量。

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

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

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

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

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

2.2 算法基本思想

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

1）頻繁項(xiàng)集的子集是頻繁的。

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

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

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

圖1 項(xiàng)目樹Fig.1 Project tree

2.4 算法實(shí)現(xiàn)

BPFP-growth算法主要分為4個(gè)核心部分：

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

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

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

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

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

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

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

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

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

4）挖掘頻繁項(xiàng)集。

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

3 實(shí)驗(yàn)與結(jié)果分析

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語

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