基于FP-tree算法的船舶滯留原因關聯性分析

顧洵瑜， 胡甚平， 吳建軍， 陳興偉,2

(1. 上海海事大學 商船學院，上海 201306; 2. 浙江交通職業技術學院 海運學院，杭州 311112)

?

基于FP-tree算法的船舶滯留原因關聯性分析

顧洵瑜1， 胡甚平1， 吳建軍1， 陳興偉1,2

(1. 上海海事大學 商船學院，上海 201306; 2. 浙江交通職業技術學院 海運學院，杭州 311112)

為提高船舶安全檢查的效率，提出對港口國監督(Port State Control,PSC)中船舶安全檢查要素之間關聯性的研究.引入關聯規則進行相關性分析，從給定的數據中尋找頻繁的項目知識模式，通過置信度和重要性閾值的約束，挖掘出船舶滯留原因間的潛在規律.算例結果表明，通過關聯規則對船舶滯留原因的分析，可以直觀地發現滯留原因間的關聯，利于港口主管機關在實際工作中采取更具針對性的方法進行檢查.

港口國監督(PSC)； 數據挖掘； 關聯規則； 滯留； 缺陷

0 引 言

港口國監督(Port State Control，PSC)被人們譽為海上安全的最后一道防線[1]，是由國際海事組織(International Maritime Organization, IMO)建立，由港口國政府的海事主管機關針對抵港外籍船舶實施的專門性檢查.PSC檢查以限制低標準船舶為手段，目的是將低標準船舶從市場中清除，保證船舶航行安全，防止船舶污染海洋環境.借助現存的10個港口國區域備忘錄體系，PSC已經可以覆蓋全球絕大部分重要港口.[2]

近年來，隨著相關國際公約以及修正案的生效，全球范圍內PSC檢查的依據已發生巨大改變，不斷修訂的公約對船舶以及PSC檢查提出更高的要求.與此同時，隨著航運競爭的日益激烈，航運業對船舶營運效率的要求日益提高，同時也要求PSC檢查具有更高的效率，高效的航運已經成為IMO追求的新內容.[3]

對于PSC檢查而言，信息界的決策支持和數據挖掘理念仍屬于新鮮課題，業界一直在探索.楊丹等[4]介紹美國采用的“選擇登輪打分表”和巴黎備忘錄國家采用的“綜合目標因素法”，提出新的綜合評估等級法.尤慶華等[5]介紹船舶安全檢查的質量船體系和模型設計的基本思路、理論基礎、體系結構和實施步驟.戴耀存等[6]運用關聯規則挖掘技術對PSC檢查滯留數據進行研究，通過頻繁項集和關聯規則挖掘船舶滯留缺陷的潛在規律.孫墨林等[7]提出基于正反饋修正-支持向量機的PSC選船模型，得到合理的結果.孫忠華[8]提出基于粗糙集和層次分析法的PSC選船系統目標因素算法，并進一步提出基于改進粒子群-BP神經網絡算法的PSC選船模型.陳晶等[9]設計編制船舶滯留規律挖掘與表達算法，通過缺陷代碼組合的復雜化呈現船舶的各種滯留規律.

隨著PSC數據的擴展，采用現代決策支持技術及數據挖掘的方法，可以對PSC檢查的記錄進行更科學、高效的信息揀選與處理，從而提取船舶缺陷的內在規律.[7]本文利用船舶安全檢查的歷史數據，采用數據挖掘技術，通過對船舶滯留原因間的關系進行關聯強度分析，確定原因間的關聯性，引導PSC檢查官從已發現的某一缺陷確定下一步重點檢查因素，“順藤摸瓜”，從而提高安全檢查效率，推進PSC檢查技術的發展.

1 PSC檢查要素體系

結合國內航行海船實際情況和我國海事管理機關的檢查實踐，船舶安全檢查體系包含14個要素，見圖1.

2 PSC檢查方法的發展

自20世紀80年代以來，備忘錄的實施推進了安全檢查全球化的發展，也使得安全檢查的標準化、規范化成為業內人員討論的問題之一.[10]依據PSC檢查數據的積累以及大量的數據分析技術的引入，PSC檢查總體上經歷了3個階段.

圖1 船舶安全檢查體系

第一階段：要素檢查.要素檢查是在對整個系統的構成要素進行逐一檢查時，主要檢查構成要素的符合性，也就是檢查是否具有安全系統的組成要素.若組成要素有缺失，則認為不符合安全標準的要求.東京備忘錄的檢查要素與第1節中提到的14個要素有相同的部分，也有一些差異.比如，東京備忘錄中提出19個要素，包括警報信號、貨物、事故預防、船舶保安及其他等.要素檢查是一種符合性檢查.

第二階段：缺陷檢查.缺陷檢查是在對整個系統的構成要素進行逐一檢查時，主要檢查構成要素的有效性，也就是檢查安全系統的組成要素是否有缺陷.若缺陷形成鏈式反應，則認為整個系統具有缺陷，不能達成系統安全的標準要求.對于船舶安全檢查而言，整個船舶安全系統要素中某些缺陷之間形成鏈式，則認為系統失效.現階段PSC檢查仍處于這個階段.

第三階段：關聯性檢查.關聯性檢查是在對整個系統的構成要素進行抽查時，主要檢查構成要素之間的關聯性，也就是檢查這些缺陷之間是否相互影響,若相互影響，且在系統中具有很重要的地位，對系統安全的影響很大，則認為系統失效的跡象明顯.該階段主要是基于第二階段檢查結果數據的積累實現基于大數據的數據挖掘，動態地、實時地反映檢查的重點，提高檢查的績效和針對性.

從第二階段發展到第三階段，需要有數據的支持，也需要數據挖掘技術平臺.

3 基于關聯規則的數據挖掘

數據挖掘可以用于發現決策所需要的知識模式.而關聯分析就是從給定的數據中發現頻繁出現的項目知識模式，又稱關聯規則.關聯規則廣泛應用于事務分析領域.在大量用戶的數據中，存在很多關聯規則，但并非所有的關聯規則對用戶都是有用的.在實際應用中，一般采取支持度(Support)和置信度(Confidence)篩選有用的規則.

為分析PSC檢查中船舶滯留原因間的關聯性，運用數據挖掘中的關聯規則進行對應的分析，找出各滯留原因間的關系，便于有關部門在實際工作中更有針對性地檢查船舶.

3.1 關聯規則

設I是數據項的集合，D為與其相關的數據集合，在D中每個事務T(Transaction)都是I的非空子集，即T?I，每個事務都有對應的識別號，稱為TID(Transaction ID).

若A和B為項目集，且A∩B=?，則定義關聯規則A?B的支持度(Support)為D中事務同時包含A和B的概率P(A∪B)，其置信度(Confidence)為當D中事務已包含A的同時包含B的百分比，即條件概率P(B|A).

(1)

(2)

支持度大于最小支持度的項集稱為頻繁項集.當關聯規則同時滿足大于最小支持度閾值(min_sup)和最小置信度閾值(min_conf)的要求時，該關聯規則稱為強關聯規則，反之稱為弱關聯規則.以上閾值需要根據數據挖掘自行設定.為便于計算，支持度和置信度的值一般用0～100%之間的值而不是0～1.0之間的值表示.[11]

3.2 關聯規則挖掘

Apriori算法是關聯規則數據挖掘中的經典算法.該算法通過挖掘數據產生布爾關聯規則所需要的頻繁項集，而關聯規則挖掘算法的核心就是尋找出頻繁項集.

Apriori算法的基本性質是：一個頻繁項集的任一子集都是頻繁的.該算法采用逐層搜索的迭代方法對頻繁項集進行挖掘，利用k-項集的挖掘結果產生(k+1)-項集.

該算法首先統計所有只含1個元素的項集出現的頻率，由此決定一維頻繁項集L1；然后開始循環處理，由L1挖掘L2，由L2挖掘L3，直至再也沒有頻繁項集產生.該算法的循環過程：逐層搜索數據庫以計算候選項集的支持度，將其與最小支持度進行比較，找到k維的最大項集.為使候選項集中項目支持度的計算更加快捷，可以利用subset函數進行計算.該方法要求預先自行設定閾值來控制支持度，并且需要遍歷數據庫多次，因此該算法的復雜度是呈指數級增加的.因此，如果有n個項目，那么就有2n個可能的頻繁項集，這構成項集I上的可能解空間.[12]

針對以上Apriori算法的固有缺陷，HAN等[13]提出頻繁模式樹(Frequent Pattern tree, FP-tree)算法.該算法可以在不產生候選項集的情況下挖掘頻繁項集.采用分治的方法，在完成對數據庫的第一次掃描后，把提供頻繁項集的數據庫壓縮進一個FP-tree中，但同時保留其中的項集關聯信息，隨后再將FP-tree分化成一些條件數據庫，對這些條件數據庫進行挖掘.因此，當原始數據量很大時，可以結合劃分數據庫的方法，使一個FP-tree可以放入主存中.由此可知，FP-growth不僅能處理不同長度的規則，并且在效率上遠高于Apriori算法.

3.3 重要性閾值

已有的關聯規則挖掘算法大部分都使用支持度-置信度閾值的框架.雖然這樣的閾值框架能夠排除大量無趣的規則，但仍會有一些存在，為此使用相關性度量來擴充這一框架.為保證關聯規則挖掘結果的準確性，引入重要性閾值以進一步屏蔽無趣的規則.定義重要性(Importance)為

(3)

重要性的取值范圍為(-∞，+∞).當重要性為0時，表明A和B是相互獨立的項，它們之間沒有關聯；當重要性大于0時，表明當A發生時，B發生的概率會上升；當重要性小于0時，表明當A發生時，B發生的概率會下降.[13]

4 算例分析

采用2011年1月至2014年6月某轄區PSC檢查數據.共滯留船舶321艘次,獲得缺陷要素數據4 643個.限于篇幅，表1僅列出2011年該轄區外籍船舶滯留情況的部分數據.

4.1 船舶滯留原因分布

表1 2011年某轄區外籍船舶滯留情況部分數據

圖2 2011年1月至2014年6月某轄區PSC檢查中船舶滯留原因分布

為使有關主管機關更有針對性地進行PSC檢查，首先將2011年1月至2014年6月某轄區PSC檢查中船舶滯留原因以條形圖(見圖2)展示，這樣可以更加直觀地表現出在此期間哪些滯留原因出現的頻數最多，有關部門可以從這些方面開始檢查.

從圖2可以清晰地發現2011年1月至2014年6月該轄區PSC檢查中船舶滯留原因出現頻數最大的3項為消防設備、救生設備、主動力及輔助設備.相關港口主管當局在實施船舶PSC檢查時，可以從出現頻數較大的滯留原因著手進行初次檢查.

4.2 滯留原因間的關聯性分析結果

采用SAS軟件中關聯規則的功能，運用FP-tree算法進行數據分析，采用置信度-重要性閾值的框架約束無趣規則的產生，結果見表2(置信度≥60%，重要性≥0).表2展示出不同滯留原因間的規則.

數據表明因素之間的關聯有明顯差異：(1)有些滯留因素與其他因素的關聯度較強.比如，在船舶證書為滯留原因的案例中，91.36%的案例中也包含航行設備這項滯留原因.在錨泊及系泊設備為滯留原因的案例中，97.30%的案例中也包含救生設備這項滯留原因.(2)因素之間的關聯形成網絡拓撲關系.比如，在救生設備為滯留原因的案例中，首先表現為與航行設備、消防設備、錨泊及系泊設備、主動力及輔助設備的強關聯關系，而錨泊及系泊設備、主動力及輔助設備均與載重線有強關聯性，該數據也能反映救生設備與載重線有較強關聯性.由此，因素之間形成可拓的網絡結構，替代以往的層次結構.(3)在安全檢查實施過程中，可以按照關聯程度進行檢查，從而提高檢查的針對性.也就是說，當PSC檢查發現船舶某項因素未達標時，應當對與其相關較大的因素進行檢查，以排除各類隱患，減小船舶發生事故的概率.

根據圖2和表2，將各項滯留原因按照發生的頻數和置信度進行排列.將發生頻數小的項排列在靠邊緣的位置，將發生頻數大的項排列在相互靠近中心的位置；將置信度大，即相關性大的項排列在靠近的位置，將置信度小，即相關性小的項排列在相隔較遠的位置.結果見圖3.

圖3 滯留原因間的關聯性

因此，基于數據挖掘的因素關聯分析可以將滯留因素之間的關聯情況進行完整分析，得出因素之間的關聯關系，從而為PSC進行關聯性檢查提供服務.PSC檢查官在檢查中可以根據圖3優先檢查位于中心位置的項目.若該項存在缺陷，可以再檢驗與其相關較大的項，即與該項相鄰的其他項.然后，根據各項之間的相關性確定需要檢查的項，增大檢查出船舶缺陷的概率，增大船舶滯留比例，減小低標準船舶在海上航行時發生事故的概率.

5 結束語

隨著PSC檢查歷史數據的積累，以往要素性檢查可以發展為關聯性檢查，提高安全檢查的效率，提升針對性.這需要數據支持，也需要數據挖掘技術平臺.本文從船舶滯留缺陷的大數據中尋找規律，運用關聯規則等數據挖掘方法發現滯留缺陷間的相關性.對某轄區2011年1月至2014年6月的PSC檢查數據的分析表明,該轄區目前核心因素是航行設備、救生設備、船體結構、無線電通信設備等硬件設施設備部分，操作性檢查還在外圍要素部分.這將為船舶管理人員和PSC檢查官在實際工作中提供指導性方法，對降低船舶尤其是無限航區的遠洋船舶海上事故的發生率起到積極的作用.

[1]曾向明，張善杰，陳寶忠，等. 世界主要區域港口國檢查組織實施情況[J]. 中國航海， 2007(4)： 13-16，28.

[2]傅俊杰，劉昌祿. 基于數據統計的港口國監督效能評估[J]. 世界海運， 2011， 34(7)： 50-52.

[3]傅俊杰，周馳. 港口國監督檢查在外籍船舶綜合管理中的應用[J]. 中國航海， 2013(3)： 106-111.

[4]楊丹，吳兆麟. 運用綜合評估等級法確定PSC檢查的重點[J]. 大連海事大學學報， 1998， 24(3)： 35-37.

[5]尤慶華，高德毅，耿鶴軍. 船舶安全檢查的質量船體系和模型設計[J]. 中國航海， 2004(1)： 8-13， 24.

[6]戴耀存，陳興偉，陳雪峰. 船舶港口國監督的滯留原因分析[J]. 中國航海， 2010(3)： 64-68.

[7]孫墨林,鄭中義.基于正反饋修正-支持向量機的PSC選船模型[J].大連海事大學學報, 2014, 40(2): 31-33, 38.

[8]孫忠華. 基于智能優化算法的港口國監督選船模型研究[D]. 大連: 大連海事大學，2013.

[9]陳晶，金永興，陳錦標，等. 基于辨識度關聯的船舶滯留規律挖掘與表達[J]. 交通運輸系統工程與信息，2014，14(1)：102-108.

[10]馬雪梅，羅衛華. 論船級社檢驗、船旗國監督與港口國監督三者關系[J]. 航海技術， 2007(1)： 74-75.

[11]趙晨. 關聯規則挖掘算法的研究及應用[D]. 西安: 西安電子科技大學， 2011.

[12]HAN J, KAMBER M. Data mining: concepts and techniques[M].Beijing: China Machine Press, 2012: 160-166.

[13]劉剛. 數據挖掘技術與分類算法研究[D]. 鄭州: 中國人民解放軍信息工程大學， 2004.

(編輯 趙勉)

Correlation analysis of ship detention reasons based on FP-tree algorithm

GU Xunyu1, HU Shenping1, WU Jianjun1, CHEN Xingwei1,2

(1. Merchant Marine College, Shanghai Maritime Univ., Shanghai 201306, China; 2. Sea Transportation Faculty, Zhejiang Institute of Communication, Hangzhou 311112, China)

To improve the efficiency of ship safety inspection, the correlations among ship safety inspection elements of Port State Control are studied. By introducing association rules to analyze the correlations, the frequent project knowledge models are found out from the given data. Then through the constraints of confidence and importance threshold values, the potential laws in ship detention reasons are mined. The result from a case shows that the correlations among ship detention reasons can be directly found out through the association rule analysis, which helps port authorities to take more effective measures in the practical work.

Port State Control (PSC); data mining; association rule; detention; deficiency

10.13340/j.jsmu.2015.02.011

1672-9498(2015)02-0060-05

2014-11-22

2015-03-17

浙江海事局項目(201425)

顧洵瑜(1992—)，女，江蘇南通人，碩士研究生，研究方向船舶安全與管理，(E-mail)jsntqdgxy@163.com； 胡甚平(1974—)，男，湖北通城人，教授，博士，研究方向為載運工具運用工程、安全工程、水上交通風險管理， (E-mail)sphu@shmtu.edu.cn

U691.6

A