基于改進FP算法的隧道交通事故關聯分析

劉云翔 韓貝

摘 要： 為了有效地對隧道交通事故進行預測，發現引起隧道交通事故的因素之間的潛在關系，針對隧道交通事故數據的特點，提出改進的FP?Growth算法，對事務與屬性賦予權重，從而能夠有效地挖掘出隱藏的、更有意義的關聯規則。并利用改進后的WFP?Growth算法建立關聯規則挖掘模型，通過挖掘采集的數據，找出導致隧道交通事故的頻繁因素組合，分析結果找出決策規則。

關鍵詞： 數據挖掘； 關聯規則； WFP?Growth算法； 權重； 公路隧道； 交通事故

中圖分類號： TN911.1?34； TP312 文獻標識碼： A 文章編號： 1004?373X（2018）17?0141?04

Abstract： In order to effectively predict the tunnel traffic accident and find the potential relationship between the factors causing the tunnel traffic accidents， an improved FP?Growth algorithm is proposed according to the data characteristic of tunnel traffic accident. The item and attribute are endowed with weight to effectively dig out the hidden and meaningful association rules. The improved WFP?Growth algorithm is used to establish the association rule mining model. The collected data is mined to find the factors combination causing the frequent tunnel traffic accidents， and decision rule by means of the analysis results.

Keywords： data mining； association rule； WFP?Growth algorithm； weight； highway tunnel； traffic accident

0 引 言

現如今，隨著我國經濟的快速發展，城市的公路隧道建設蓬勃發展，文獻[1]指出截至2016年初，全國公路隧道為14 006處、1 268.39萬米，公路隧道數量年增長率約為11.5%。隨著隧道建設條數的增多，從而引發的交通事故也相應增加[2]。我國對隧道交通事故數據的分析主要是運用數據統計，分析引起隧道交通事故的主要原因。因此，本文采用挖掘關聯規則[3]的FP?Growth算法，挖掘引發隧道事故各種屬性之間的關聯關系。

在頻繁模式挖掘FP?Growth算法的挖掘過程中，對數據的度量是事先設定好的最小支持度與最小置信度，若最小支持度與最小置信度設置得過高，會使得頻率較低的關鍵因素丟失，若設置得過低則會挖掘過多無用的關聯規則。針對引起交通事故的因素中某些出現頻率較低但是至關重要的因素，提出基于權重改進的FP?Growth算法，目的是挖掘出更加可靠的關聯規則，可以指導交通部門對預防隧道交通事故采取相應的措施。

1 FP?Growth算法

FP?Growth算法是一種基于頻繁模式樹[4]的算法，該算法的策略主要分為以下兩個步驟：首先，將代表頻繁項集的事務數據庫壓縮到頻繁模式樹上，減少候選項集的大小，但仍保留項集之間的關聯信息；然后，把這種壓縮后的數據庫劃分成一組條件數據庫，每個數據庫關聯一個頻繁項，并分別對每個條件數據庫進行挖掘。

FP?Growth算法的流程圖如圖1所示。

基于FP樹[5]的關聯規則挖掘FP?Growth算法是將挖掘長頻繁模式的過程轉變成在較小的條件數據庫中遞歸地挖掘一些短的模式，然后加上后綴。這樣使用出現次數較低的項作為后綴，增加了選擇性，降低了搜索花費時間。

2 基于權重改進的FP?Growth算法

由于FP?Growth算法[6?7]只是根據其各個項出現的頻率來確定該項的重要程度，沒有考慮到各個項本身的重要性，從而挖掘出來的規則都是些大量無意義的關聯規則，所以為了體現事務以及項的重要性，本文提出基于權重（Weight）[8]的WFP?Growth算法。

2.1 WFP?Growth算法思想

2.2 WFP?Growth算法的描述

經過上述描述的權重，對FP?Growth算法進行改進，具體步驟如下：

1） 掃描事務數據庫，計算出每個事務以及各個事務中項的權重，即[w（Ii）]和[wt（Tj）]。根據預先設置的最小支持度，得到頻繁項集后調整事務數據庫。

2） 建立頻繁項目頭表，再次掃描事務數據庫，并根據建立完成的頻繁項目頭表創建頻繁模式樹FP樹。之后，根據FP樹產生條件模式基，產生頻繁模式。

3） 根據產生的頻繁模式項集，計算每個項集的關鍵度量作為支持度。滿足最小支持度與置信度的項集就是最后挖掘得到的關聯規則。

3 改進的FP?Growth算法在公路隧道交通事故中的應用

3.1 數據準備與數據預處理

通過查看公安部交通管理局網站以及相關文獻等[9?10]，搜集了1 607起上海13座過江公路隧道交通事故資料。

由于從得到的隧道交通事故的原始數據中無法直接獲取有效信息，需要對搜集到的數據進行處理，保留有效的數據字段，將無效的數據刪除，以減少每條數據的字段數。另外，對剩下的屬性進行預處理，將屬性映射為對應的編碼，產生新的事故數據庫。現有的公路隧道交通事故數據可以分為兩大類：一類是量化型數據，一般由連續值來表示，如駕齡，時間等；另一類則是枚舉類型數據，如事故發生區段，事故原因，事故形態等。根據不同的數據特點，對數據進行預處理。對于時間這樣的量化屬性，可以通過離散化來處理。例如，將隧道事故發生的時間分為[T1]：0：00—6：00，[T2]：6：00—9：00，[T3]：9：00—12：00，[T4]：12：00—15：00，[T5]：15：00—17：00，[T6]：17：00—20：00，[T7]：20：00—24：00等7個區間，用1個編碼代表1個區間。根據隧道的自身特點，隧道的內外光線差異大，很大地影響到駕駛者的視覺，容易引發交通事故。文獻[11]將隧道劃分為4個路段進行數據分析。路段S1對應隧道出入口向外的50 m區域，路段S2對應隧道出入口向內50 m區域，路段S3對應隧道出入口向內50～100 m區域，路段S4對應剩余的中間路段。需進行預處理的屬性字段還有駕齡、天氣、車輛類型、事故原因、事故形態、事故類別等。

駕齡分為：B1，一年以內；B2，1～3年；B3，3～5年；B4，5年以上。

天氣分為：W1，晴；W2，雨；W3，霧。

車輛類型分為：C1，小轎車；C2，大型客車；C3，小型貨車；C4，大型貨車。

事故原因分為：R1，超速；R2，違章超車；R3，酒駕；R4，道路故障；R5，占道；R6，車輛故障。

事故類型分為：D1，追尾；D2，刮蹭；D3，翻車；D4，碾壓；D5，墜車。

事故等級分為：G1，車輛損壞；G2，人員受傷；G3，人員死亡。

3.2 數據挖掘

1） 構建隧道事故的FP樹

實驗中先設置最小支持度為15%。首先掃描隧道事故事務數據庫得到頻繁項的集合，計算事務和各個項的權重以及項的關鍵度量，將項的關鍵度量作為該項的支持度，之后將頻繁項的集合按其支持度遞減排序。結果集可標記為[L]。創建樹的根節點，以“null”標記，以及頻繁項目頭表，如表1所示。

再次掃描隧道事故事務數據庫，其中每個事務的項按[L]次序處理，并對每個事務建立一個分支。當一個事務需要增加分支時共同前綴上的每個節點的計數增加1，構建出隧道事故的FP樹。

2） 根據FP樹找出頻繁項集

根據隧道事故FP樹的頻繁項目頭表，由長度為1的頻繁模式開始，遍歷FP樹，構造出隧道事故的條件模式基。使用這些產生的條件模式基，構造出頻繁模式的條件FP樹，其只包含單個路徑。然后連接后綴，產生頻繁模式的所有組合。

3.3 挖掘關聯規則

由于頻繁模式產生關聯規則需要同時滿足設定好的最小支持度與最小置信度。預設最小支持度為15%，最小置信度為40%，得到一些有意義的關聯規則表達式。列出每個關聯規則的支持度與置信度以便訪問，則產生的關聯規則如表2所示。

4 實驗結果分析

通過分析上述隧道事故挖掘出來的關聯規則結果，可以總結出隧道事故發生時其各個屬性之間的關聯關系。

1） 規則①：超速?汽車損壞（sup=35.93%，conf=78.25%）。

規則⑤：小轎車?超速?人員受傷（sup=17.96%，conf=74.32%）。

規則⑧：超速?時間20：00—24：00?人員受傷（sup=15.56%，conf=41.02%）。

規則①表明，隧道交通事故中發生汽車損害是由超速引起的，該關聯規則的置信度達到78.25%。規則⑤表明，駕駛小轎車并且超速行駛引發人員受傷，其置信度為74.32%。規則⑧表明，駕駛者在時間20：00—24：00超速行駛引發人員受傷，其置信度為41.02%。根據這些找到的關聯規則，引起隧道交通事故的絕大多數原因為車輛超速所致。而其中小轎車的占有率比較大，發生車禍的時間在夜晚居多，交警人員應多注意對隧道出入口車輛車速進行控制，并在隧道中設置相應的警示牌。在夜晚時分也需要加強車速管理，盡量降低車輛進出隧道時的車速，避免車速過快使得駕駛員沒有反應的時間，從而引起車禍的發生。

2） 規則②：違章超車?刮蹭（sup=23.95%，conf=65.46%）。

規則⑦：隧道出入口向內50 m?追尾 （sup=16.16%，conf=45.87%）。

規則②表明駕駛者違章超車引發隧道追尾事故，該關聯規則的置信度為65.46%，規則⑦表明在隧道出入口向內50 m處發生汽車追尾事故，其關聯規則的置信度為45.87%。這兩個關聯規則表明在隧道事故中引起追尾事故的主要原因是違章超車，而引發追尾的事故大部分是在隧道出入口向內50 m，由于隧道入口處和出口處光線強度與隧道外的光線強度有反差，容易擾亂駕駛者的視覺，使其看不清道路狀況。為了避免這樣的情況發生，駕駛員應盡量避免出入口超車。結合具體情況在隧道出入口設置照明燈和遮陽棚，盡可能避免隧道出入口與洞內外的光線強度差異。

3） 規則④： 霧天?追尾?人員受傷（sup=18.56%，conf=81.30%）。

規則⑥：駕齡在一年以內?雨天?車輛損壞（sup=17.36%，conf=40.50%）。

規則④表明車輛在霧天時，發生追尾后，造成人員受傷，其置信度為81.30%。規則⑥表明駕駛者駕駛年齡在一年以內，在雨天發生事故造成車輛損壞，其置信度為40.50%。這兩個規則表明雨霧天氣時，容易引發交通事故，駕駛員則需要在駕駛時提高注意力。同樣，當一些駕駛技能還不夠熟練的新手遇到天氣不好的情況則更加容易發生交通事故，其中發生車輛刮擦的居多。因此，交通部門應增加駕駛考試的課時，使得新手可以得到足夠的時間去練習，以減少事故的發生。

4） 規則③： 晴天?酒駕?人員死亡（sup=19.16%，conf=56.31%）。

該規則表明天晴時，駕駛員醉酒駕車引發交通事故，其置信度為56.31%。根據該規則，交通部門應加強對醉酒駕駛及其他違規駕駛行為的管理，對醉酒駕駛提起高度重視。應加大關于酒駕相關的處罰力度，以減少酒駕引起的交通事故。

5 結 語

本文針對隧道交通事故的特點，以及之前相關研究者的單面性和模糊性，提出WFP?Growth算法，該算法通過權重定義項在事務中的重要性，從而分析隧道交通事故預防措施。實驗結果表明，該算法能夠挖掘出隧道交通事故發生的時間、路段、駕齡、天氣、車輛類型、事故原因、事故類型、事故等級等屬性之間的相關性，產生出符合實際情況、更加有意義的關聯規則，可以為交通部門預防隧道事故的發生，出臺相關政策提供決策支持。

參考文獻

[1] 交通運輸部.2015年交通運輸行業發展統計公報[N].中國交通報，2016?05?05（002）.

Ministry of Transport of the People′s Republic of China. 2015 statistics bulletin of transportation industry [N]. China transport news， 2016?05?05（002）.

[2] 云建平.高速公路隧道群交通事故分布特點及預防對策[J].科技與創新，2016（18）：60.

YUN Jianping. Distribution characteristics and preventive measures of traffic accidents in freeway tunnel group [J]. Technology and innovation， 2016（18）： 60.

[3] 李仕瓊.數據挖掘中關聯規則挖掘算法的分析研究[J].電子技術與軟件工程，2015（4）：200.

LI Shiqiong. Analysis and research of association rules mining algorithm in data mining [J]. Electronic technology and software engineering， 2015（4）： 200.

[4] ALAVI F， HASHEMI S. DFP?SEPSF： a dynamic frequent pattern tree to mine strong emerging patterns in streamwise features [J]. Engineering applications of artificial intelligence， 2015， 37： 54?70.

[5] 石芹芹.基于FP樹的極大頻繁項集的挖掘方法[J].現代計算機（專業版），2015（36）：7?10.

SHI Qinqin. Mining method of maximal frequent itemsets based on FP tree [J]. Modern computer （professional edition）， 2015（36）： 7?10.

[6] 王艷輝，王淑君，李曼，等.基于改進FP?Growth算法的CRHX型動車組牽引系統關聯失效模型研究[J].鐵道學報，2016，38（9）：72?80.

WANG Yanhui， WANG Shujun， LI Man， et al. Research on correlative failure model of CRHX EMU traction system based on improved FP?Growth algorithm [J]. Railway journal， 2016， 38（9）： 72?80.

[7] 鄭志成，姜昌金.基于FP?Growth的改進算法[J].工業控制計算機，2015，28（5）：105?106.

ZHENG Zhicheng， JIANG Changjin. Improved algorithm based on FP?Growth [J]. Industrial control computers， 2015， 28（5）： 105?106.

[8] 趙遠東，方正華.帶有權重函數學習因子的粒子群算法[J].計算機應用，2013，33（8）：2265?2268.

ZHAO Yuandong， FANG Zhenghua. Particle swarm optimization algorithm with weight function learning factor [J]. Journal of computer applications， 2013， 33（8）： 2265?2268.

[9] JIAN S Y， WONG Y D. Road traffic accidents in Singapore expressway tunnels [J]. Tunnelling & underground space technology， 2013， 38： 534?541.

[10] AMUNDSEN F H， RANES G. Studies on traffic accidents in Norwegian road tunnels [J]. Tunnelling & underground space technology， 2000， 15（1）： 3?11.

[11] LU L J， LU J， XING Y， et al. Statistical analysis of traffic accidents in Shanghai river crossing tunnels and safety countermeasures [J]. Discrete dynamics in nature & society， 2014（2）： 1?7.