關(guān)聯(lián)規(guī)則挖掘在道路交通事故分析中的應(yīng)用

馬庚華, 鄭長江, 鄧評心, 李 銳

(1.河海大學(xué)港口海岸與近海工程學(xué)院， 江蘇 南京 210098； 2.河海大學(xué)土木與交通學(xué)院， 江蘇 南京 210098)

交通事故是全球所有國家面臨的共同難題[1]。在我國，隨著社會經(jīng)濟(jì)的不斷發(fā)展，居民機(jī)動車保有量連年上升，城市交通面臨前所未有的巨大壓力。2016年，我國共接報(bào)道路交通事故864.3萬起，同比增加65.9萬起，上升16.5%。其中涉及人員傷亡的道路交通事故212 846起，造成63 093人死亡、226 430人受傷，直接財(cái)產(chǎn)損失12.1億元[2]。利用交通大數(shù)據(jù)分析事故成因，采取針對措施減少交通事故是保障道路安全的有效手段。

關(guān)聯(lián)規(guī)則挖掘是一種有效的數(shù)據(jù)挖掘方法，它可以從海量的數(shù)據(jù)中發(fā)現(xiàn)不同類型數(shù)據(jù)之間的關(guān)聯(lián)[3]。針對數(shù)量巨大的交通事故數(shù)據(jù)，關(guān)聯(lián)規(guī)則挖掘可以得出事故原因(如駕駛員、車輛、道路、環(huán)境)與事故結(jié)果(如事故類型、嚴(yán)重程度)之間的關(guān)系，從而給交通決策者提供參考。國內(nèi)外學(xué)者對交通事故成因分析的方法有很多，如貝葉斯網(wǎng)絡(luò)[4]、決策樹[5]、FP-Growth[6]、Apriori算法[7-10]等。他們對關(guān)聯(lián)規(guī)則的篩選都是使用“支持度-置信度”框架，規(guī)則評選標(biāo)準(zhǔn)單一，模式評估度量數(shù)量不足，難以找出更加合理且易于應(yīng)用的關(guān)聯(lián)規(guī)則。

本文在以上研究的基礎(chǔ)上，采用改進(jìn)的Apriori算法對交通事故數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘，并結(jié)合支持度、Kulc、平衡比3個(gè)模式評估度量[11]，引入相關(guān)值，進(jìn)一步篩選出有價(jià)值的關(guān)聯(lián)規(guī)則，得出相應(yīng)結(jié)論，為交通管理部門提供參考。

1 數(shù)據(jù)預(yù)處理

1.1 數(shù)據(jù)描述

本文研究所使用的數(shù)據(jù)為某市2015年全年的交通事故數(shù)據(jù)與天氣數(shù)據(jù)。交通事故數(shù)據(jù)表包括事故發(fā)生的時(shí)間、事故違法類型、性別、身份證號碼、車牌號碼、車身顏色、畢業(yè)駕校名稱、駕照初次發(fā)放日期、車輛品牌等屬性，共56 651條記錄。天氣表包括天氣狀況、氣溫、風(fēng)力風(fēng)向等屬性，共365條記錄。

1.2 數(shù)據(jù)清理

首先要確定關(guān)聯(lián)規(guī)則挖掘所需要的不同屬性。基礎(chǔ)數(shù)據(jù)中有著大量的屬性，對于關(guān)聯(lián)規(guī)則挖掘中不需要的屬性進(jìn)行刪除，如交通事故數(shù)據(jù)表中的車牌號碼以及天氣表中的風(fēng)力風(fēng)向。除了原始數(shù)據(jù)已經(jīng)具有的部分屬性之外，一些屬性需要對原始數(shù)據(jù)進(jìn)一步提取，如從身份證號碼獲得年齡、從駕照初次發(fā)放日期獲得駕齡、從車輛品牌獲得車輛類型。還有一些屬性需要從其他表獲得，如按照日期將天氣表和事故表連接，獲得事故發(fā)生時(shí)的天氣狀況、氣溫等屬性。

部分基礎(chǔ)數(shù)據(jù)存在著不正確、不完整、不一致等問題，需要采取適當(dāng)?shù)姆椒ㄟM(jìn)行處理。車身顏色出現(xiàn)的亂碼，刪除之后按照出現(xiàn)最多的顏色填充。年齡的缺失值分性別按照平均值填充。駕齡的缺失值根據(jù)年齡來預(yù)測。對于大量缺失的數(shù)據(jù)另歸為一類，如車輛類型未知?dú)w為一類。

1.3 數(shù)據(jù)編碼

數(shù)據(jù)經(jīng)過清理已經(jīng)準(zhǔn)確、完整和一致之后，為了方便存儲和數(shù)據(jù)挖掘，需要對部分屬性進(jìn)行概念分層，并將數(shù)據(jù)的表達(dá)形式進(jìn)行統(tǒng)一描述，因此對各個(gè)屬性值編碼，如表1所示。

表1 屬性值編碼

2 Apriori算法及改進(jìn)

2.1 Apriori算法描述

Apriori算法是關(guān)聯(lián)規(guī)則挖掘頻繁項(xiàng)集的經(jīng)典算法。Apriori算法采用的是逐層搜索的迭代方法，k項(xiàng)集用于探索(k+1)項(xiàng)集。首先，通過掃描數(shù)據(jù)庫，累計(jì)每個(gè)項(xiàng)的計(jì)數(shù)，并收集滿足最小支持度的項(xiàng)，找出頻繁1項(xiàng)集的集合，記為L1。然后，使用L1找出頻繁2項(xiàng)集的集合L2，使用L2找到L3，如此下去，直到不能再找到頻繁k項(xiàng)集。其中，使用Lk-1找出Lk的過程由連接和剪枝組成。

1)連接。

為找出Lk，通過將Lk-1與自身連接產(chǎn)生候選k項(xiàng)集的集合，記為Ck。假設(shè)l1和l2是Lk-1中的項(xiàng)集，記li[j]表示li的第j項(xiàng)。假定項(xiàng)集中的項(xiàng)按照字典序排序，即對于(k-1)項(xiàng)集li，其項(xiàng)滿足li[1]

2)剪枝。

Ck是Lk的超集，其成員可以是也可以不是頻繁的。掃描事務(wù)數(shù)據(jù)庫，確定Ck中每個(gè)候選項(xiàng)集的計(jì)數(shù)，若小于最小支持度計(jì)數(shù)，則從Ck中刪除；若不小于最小支持度計(jì)數(shù)，則保留，最終得出Lk。

為了提高剪枝的效率，可以采用先驗(yàn)性質(zhì)對Ck進(jìn)行壓縮。任何非頻繁的(k-1)項(xiàng)集都不是頻繁k項(xiàng)集的子集。因此，如果一個(gè)候選k項(xiàng)集的(k-1)項(xiàng)子集不在Lk-1中，則該候選也不可能是頻繁的，從而可以從Ck中刪除。

Apriori算法的優(yōu)點(diǎn)在于使用先驗(yàn)性質(zhì)，大大提高了頻繁項(xiàng)集逐層產(chǎn)生的效率，算法整體簡單易理解，同時(shí)對數(shù)據(jù)集要求低。但是算法也存在缺點(diǎn)：如當(dāng)事務(wù)數(shù)據(jù)庫很大時(shí)，候選頻繁k項(xiàng)集數(shù)量巨大；在驗(yàn)證候選頻繁k項(xiàng)集的時(shí)候，需要對整個(gè)數(shù)據(jù)庫進(jìn)行掃描，非常耗時(shí)。

2.2 Apriori改進(jìn)算法

Apriori算法中從Ck到Lk要經(jīng)過兩次篩選：第一次是利用先驗(yàn)性質(zhì)，通過Lk-1篩選，判斷Ck中候選k項(xiàng)集的(k-1)項(xiàng)子集是否在Lk-1中，如不存在則刪除，這樣每產(chǎn)生一個(gè)候選k項(xiàng)集都要掃描一遍Lk-1；第二次是根據(jù)最小支持度計(jì)數(shù)篩選，項(xiàng)集的頻數(shù)若小于最小支持度計(jì)數(shù)則刪除。改進(jìn)算法的思路是只需要掃描一遍Lk-1[12]。Lk-1通過與自身連接得到Ck，掃描一次Lk-1，對于Lk-1中的每一個(gè)頻繁(k-1)項(xiàng)集，判斷它是否為Ck中各候選項(xiàng)集的子集，如果是，那么該候選項(xiàng)集的計(jì)數(shù)加一。掃描完成后，對于候選項(xiàng)集計(jì)數(shù)為k的保留，小于k的刪除。然后，再根據(jù)最小支持度計(jì)數(shù)進(jìn)行第二次篩選即可得出Lk。

2.3 改進(jìn)算法性能分析

為了驗(yàn)證改進(jìn)Apriori算法的效能，在支持度為0.1、置信度為0.3的條件下，分別取經(jīng)典算法和改進(jìn)算法在不同數(shù)據(jù)記錄數(shù)下的運(yùn)行時(shí)間對比，結(jié)果如表2所示。

表2 不同數(shù)據(jù)記錄數(shù)下算法用時(shí)

從表2可以清晰地看出經(jīng)典Apriori算法和改進(jìn)Apriori算法在處理不同數(shù)據(jù)記錄數(shù)時(shí)的耗時(shí)情況。實(shí)驗(yàn)結(jié)果表明，隨著數(shù)據(jù)記錄數(shù)的不斷增加，改進(jìn)Apriori算法的搜索時(shí)間始終低于經(jīng)典Apriori算法的搜索時(shí)間，算法整體效率提高約4%?？梢姼倪M(jìn)算法的搜索效率要優(yōu)于經(jīng)典算法，在大數(shù)據(jù)的情況下，改進(jìn)算法更加適用。

3 關(guān)聯(lián)規(guī)則

3.1 關(guān)聯(lián)規(guī)則簡介

假設(shè)I={I1,I2,…,Im}是項(xiàng)的集合。任務(wù)相關(guān)的數(shù)據(jù)D是數(shù)據(jù)庫事務(wù)的集合，其中每個(gè)事務(wù)T是一個(gè)非空項(xiàng)集，T?I。A是一個(gè)項(xiàng)集，事務(wù)T包含A，當(dāng)且僅當(dāng)A?T。關(guān)聯(lián)規(guī)則形如A?B，其中A?I，B?I，A≠?，B≠?，且A∩B=?。規(guī)則A?B在事務(wù)集D中成立，具有支持度support和置信度confidence。其中，support(A?B)=P(A∪B)，confidence(A?B)=P(B|A)。同時(shí)滿足最小支持度閾值(min_sup)和最小置信度閾值(min_conf)的規(guī)則成為強(qiáng)規(guī)則，即用戶所感興趣的規(guī)則。

挖掘關(guān)聯(lián)規(guī)則分兩步：第一步找出所有的頻繁項(xiàng)集，其頻繁出現(xiàn)的次數(shù)≥min_sup；第二步由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，其置信度≥min_conf。

本文在關(guān)聯(lián)分析之后加入相關(guān)分析產(chǎn)生強(qiáng)規(guī)則，關(guān)聯(lián)規(guī)則挖掘模型如圖1所示。

圖 1 關(guān)聯(lián)規(guī)則挖掘模型

3.2 相關(guān)性度量

大部分關(guān)聯(lián)規(guī)則挖掘的研究之中，都采用支持度和置信度來過濾關(guān)聯(lián)規(guī)則，從而保證所得到的關(guān)聯(lián)規(guī)則是用戶感興趣的。然而，僅僅使用支持度和置信度兩個(gè)評判標(biāo)準(zhǔn)太少，不足以過濾掉無趣的關(guān)聯(lián)規(guī)則，甚至有時(shí)會產(chǎn)生有誤導(dǎo)的“強(qiáng)”關(guān)聯(lián)規(guī)則，因此有部分研究人員加入了一個(gè)新的相關(guān)性度量：提升度lift。A和B出現(xiàn)之間的提升度由公式(1)計(jì)算。

lift(A,B)=P(B|A)/P(B)

(1)

若提升度小于1，那么A出現(xiàn)與B出現(xiàn)是負(fù)相關(guān)的，即一個(gè)出現(xiàn)會導(dǎo)致另外一個(gè)不出現(xiàn)。若提升度大于1，那么A出現(xiàn)與B出現(xiàn)是正相關(guān)的，即一個(gè)出現(xiàn)會導(dǎo)致另外一個(gè)出現(xiàn)。若提升度等于1，那么A出現(xiàn)與B出現(xiàn)是相互獨(dú)立的，即一個(gè)出現(xiàn)和另一個(gè)出現(xiàn)之間沒有聯(lián)系。提升度可以在一定程度上反映出A和B兩者的相關(guān)性。

但是，僅加入提升度衡量相關(guān)性來進(jìn)行關(guān)聯(lián)規(guī)則挖掘仍然不完善。因?yàn)閮H使用一個(gè)相關(guān)性度量，導(dǎo)致相關(guān)性判斷標(biāo)準(zhǔn)單一，缺乏說服力，更為重要的是，用提升度衡量相關(guān)性存在缺陷。在事務(wù)數(shù)據(jù)庫中，定義零事務(wù)為不包含任何考察項(xiàng)集的事務(wù)。對于一條關(guān)聯(lián)規(guī)則，零事務(wù)的個(gè)數(shù)可能會大大超過包含關(guān)聯(lián)規(guī)則中項(xiàng)集的事務(wù)的個(gè)數(shù)，而提升度這個(gè)度量從定義上看，它的值會受到零事務(wù)的影響。因此需要新的相關(guān)性度量來衡量相關(guān)性，在此引入Kulczynski(Kulc)度量和平衡比(Balance Ratio, BR)。

(2)

BR(A,B)=(P(A|B))/(P(B|A))

(3)

Kulc度量由公式(2)定義，可以看作兩個(gè)置信度的平均值，其值可以遍取0～1，并且值越大，A和B的聯(lián)系越密切。平衡比(BR)由公式(3)定義，是兩個(gè)置信度的比率，它表示A和B之間相關(guān)性的平衡，越接近1則越平衡，當(dāng)兩個(gè)置信度中的任何一個(gè)等于零時(shí)，BR也等于零。以上兩個(gè)度量僅受P(A|B)和P(B|A)的影響，不受零事務(wù)的影響，也不受事務(wù)總數(shù)的影響。

在相關(guān)性分析中，本文選用支持度(support)、Kulc、平衡比(BR)3個(gè)度量進(jìn)行判斷?？紤]到?jīng)]有前者參考來確定支持度、Kulc和平衡比的閾值應(yīng)當(dāng)脫離閾值確定的模式或至少能夠減少閾值的數(shù)量，試圖找到三者的統(tǒng)一表示。要做到這一點(diǎn)，BR首先轉(zhuǎn)變?yōu)槠胶舛?balance)，采用公式(4)，使其與支持度和Kulc具有相同的正相關(guān)性。

(4)

平衡度曲線如圖2所示。平衡度越大代表兩個(gè)事件越平衡，當(dāng)平衡度取最大值1時(shí)，表示完全平衡。

在支持度為5%，置信度為30%的條件下，采用改進(jìn)的Apriori算法，共得出強(qiáng)關(guān)聯(lián)規(guī)則141條。這些規(guī)則的支持度、Kulc和平衡度分布如圖3所示。由圖3可以看出，位于右上方的點(diǎn)具有相對較高的支持度和Kulc，并且顏色越深代表平衡度越高。這3個(gè)值呈正相關(guān)，因此使用3個(gè)值的乘積作為相關(guān)值(correlation)可以簡單地用于表示相關(guān)性，如公式(5)所示：

correlation=Kulc·support·balance

(5)

圖 2 平衡度曲線

3.3 結(jié)果及分析

采用上文提出的相關(guān)值(correlation)作為度量指標(biāo)，對141條強(qiáng)關(guān)聯(lián)規(guī)則進(jìn)行篩選。將相關(guān)值從大到小排序，相關(guān)值越大，意味著二者之間的關(guān)系越密切，從而對應(yīng)的關(guān)聯(lián)規(guī)則更加有意義。篩選出的部分關(guān)聯(lián)規(guī)則如表3所示。

圖 3 支持度、Kulc和平衡度分布

表3 基于相關(guān)值篩選的強(qiáng)關(guān)聯(lián)規(guī)則

通過對關(guān)聯(lián)規(guī)則挖掘所得出的結(jié)果進(jìn)行深入分析，可以得出一些有意義的結(jié)論以及相應(yīng)的改進(jìn)措施：

1)在所有的事故類型中，未按規(guī)定讓行和未保持安全距離造成的事故數(shù)最多，占總數(shù)的70.0%。需要采取多種方式進(jìn)行預(yù)防，如在駕駛員培訓(xùn)中增加此類事故的理論知識學(xué)習(xí)；在事故高發(fā)地點(diǎn)有針對性地設(shè)置更加合理的標(biāo)志標(biāo)線；加強(qiáng)交通管理，在高峰時(shí)段對此類事故給予重視。

2)交通事故絕大多數(shù)都是由于人為原因造成的，從駕駛員特征上看，男性駕駛員事故風(fēng)險(xiǎn)是女性駕駛員的4倍；駕齡為1～5年以及11～15年的駕駛員更容易發(fā)生事故。新駕駛員技術(shù)不嫻熟、經(jīng)驗(yàn)不足；老駕駛員自恃經(jīng)驗(yàn)豐富，思想上麻痹。駕駛員的整體素質(zhì)亟待提高，應(yīng)加強(qiáng)對駕駛員的行為干預(yù)，嚴(yán)格執(zhí)行懲戒制度。

3)在所有的車輛類型中，小汽車發(fā)生的事故數(shù)最多，占總數(shù)的54.5%；摩托車、電動車引發(fā)的交通事故也占有一定比例，占總數(shù)的14.2%。電動車的出現(xiàn)極大方便了人們的生活，然而電動車駕駛員駕照類型以自培和未知為主，沒有接受過系統(tǒng)的交通規(guī)則學(xué)習(xí)，很容易發(fā)生事故，交管部門應(yīng)加強(qiáng)對電動車的引導(dǎo)。從車輛顏色看，白色車輛發(fā)生的事故數(shù)最多，這看似與車輛顏色和事故關(guān)系的相關(guān)研究結(jié)果不符，實(shí)則是因?yàn)槿藗兏鼉A向于購買白色車，造成白色車輛基數(shù)大，從而事故數(shù)多。

4)從交通環(huán)境屬性上看，20～25℃和陰雨天更容易發(fā)生交通事故，且女性駕駛員在不良天氣下事故率會發(fā)生較大變化。此時(shí)能見度低、路面潮濕、輪胎打滑，很容易因?yàn)橹苿硬患皶r(shí)發(fā)生事故。這要求駕駛員在不良?xì)夂驐l件下更應(yīng)該集中注意力、小心謹(jǐn)慎，尤其是遇到意外情況時(shí)處理能力較差的女性駕駛員，同時(shí)交管部門要積極做好引導(dǎo)工作。

4 結(jié)語

本文以交通事故大數(shù)據(jù)為基礎(chǔ)，采用改進(jìn)的Apriori算法挖掘關(guān)聯(lián)規(guī)則，提高了數(shù)據(jù)挖掘的效率。通過一個(gè)結(jié)合支持度、Kulc、平衡比三者的綜合性度量——相關(guān)值對關(guān)聯(lián)規(guī)則進(jìn)行篩選，使篩選出的關(guān)聯(lián)規(guī)則更加合理，得出的結(jié)論更有價(jià)值，從而能夠?yàn)榻煌ü芾聿块T采取相應(yīng)措施，制定相關(guān)規(guī)章制度提供參考。