智能算法在交通事故分析上的應用

林穎

【摘 要】隨著計算機應用技術的不斷普及、發(fā)展和完善，利用數據挖掘技術、專家系統、計算機人工智能來對道路交通事故進行處理已經越來越廣泛。鑒于道路交通事故的過程具有系統性、強關聯性、復雜性等一系列特點，運用計算機人工智能技術對道路交通事故的突發(fā)性、致因性、規(guī)律性、模糊性進行分析和研究等已經成為現實。本文通過對智能算法在交通事故分析中應用的可行性研究，提出了利用聚類分析算法和關聯分析算法分別對事故黑點的排查及事故因素的關聯分析。

【關鍵詞】智能算法；事故信息；聚類分析；關聯分析

1.智能算法在交通事故分析上的應用

目前人們廣泛采用的智能計算方法主要有統計方法）、器學習方法、面向數據庫的方法、聚類分析方法、人工神經網絡方法、遺傳算法、近似推理和不確定性推理方法、基于證據理論和元模式的方法、現代數學分析方法、粗糙集或模糊集方法、集成方法、關聯規(guī)則算法、決策樹方法等。

發(fā)展智能交通的最終目標就是通過對各類的交通信息、數據進行分析，對交通系統的控制方案和策略予以優(yōu)化，通過調整各類交通參與者的行為以及道路交通設施設備的建設、改善，從而實現交通系統的優(yōu)化及高效運行的目的。因此，分析交通信息、制定控制策略是整個系統的關鍵。本文在總結和借鑒大量學者研究的基礎上，介紹兩種基于數據挖掘理論的智能算法DBSCAN及Apriori，分別用于交通事故黑點的排查及事故關聯因素的分析。

2.基于密度的聚類分析算法DBSCAN

2.1算法應用的數據類型與數據結構

數據挖掘不能直接把任何數據進行計算，要事先對數據進行預處理，構成算法能夠應用的數據類型，然后輸入到算法中的數據結構中去。基于內存的聚類算法通常都采用以下兩種數據結構[1]。

2.1.1數據矩陣

數據矩陣是一個對象-結構。它是由n個對象組成，如：人；這些對象是利用p個屬性來進行描述的，如：年齡、高度、體重等。數據矩陣的表達方式為n×p的矩陣。

2.1.2差異矩陣

差異矩陣是一個對象-對象結構。n個對象彼此之間的差異將存放于該矩陣中，采用n×n矩陣來表示。

由交警部門提供的交通事故數據經過整理后存放到數據矩陣中去保存。如：一個交通事故點可以占用一行，而它的每一個屬性可以占用這一行的每一個列元素。對于差異矩陣，可以反映每兩個事故數據的差異，它可以是兩個事故發(fā)生地點的距離，也可以是兩個事故發(fā)生情況的相似度倒數，還可以是兩個事故發(fā)生的時間差。總之，它可以靈活的反映事故之間的差異。在本系統中對于事故黑點的聚類分析采用事發(fā)地點的空間距離來構成差異矩陣。

2.2 DBSCAN算法在交通事故黑點排查上的應用

DBSCAN算法是一個比較典型的基于密度的聚類分析法，它能從含有噪聲的空間數據庫中發(fā)現任意形狀的聚類。關于該算法的2個基本概念：（1）一個給定對象的ε半徑內的近鄰就稱為該對象的ε-近鄰；（2）若一個對象的ε-近鄰至少包含一定數目（MinPts）的對象，該對象就稱為核對象。DBSCAN算法的基本思想就是通過不斷的搜索臨近點來使核對象周圍的密度逐漸增加，從而尋找到一個區(qū)域內所查找點或對象密度大的地方。算法中所要研究的點可以描述為交通事故發(fā)生的地點，對于算法中的ε-近鄰區(qū)域可以理解為道路的公里數，因此DBSCAN算法在道路交通事故黑點的智能排查上就可以理解為排查在半徑為ε公里內發(fā)生MinPts以上交通事故的地點或者路段。

3.關聯規(guī)則挖掘的算法分析

3.1關聯規(guī)則挖掘的過程

設I={i1，i2，.....im}是項的集合。設任務相關的數據D是數據事務的集合，其中每個事務T是項的集合，使得T?I。每一個事務有一個標識符，稱作TID。設A是一個項集，事務T包含A當且僅當A?T。關聯規(guī)則是形如A?B的蘊涵式，其中A?I，B?I，并且A∩B=?。規(guī)則A?B在事務集D中成立，具有支持度support，是指D中包含A和B的事務數與所有事務數之比它，即概率P（A∪B ）。規(guī)則A?B在事務集D中具有置信度confidence，是指D中包含A和B的事務數與包含A的事務數之比，即條件概率P（BA） [2]。

給定一個事務集D，挖掘關聯規(guī)則問題就是產生支持度和置信度分別大于用戶給定的最小支持度（Minimum Support Count，簡稱min_sup）和最小置信度 （Minimum Confidence Count，簡稱min_conf）的關聯規(guī)則[3]。

項的集合稱為項集（Itemset），包含k個項的項集稱為k-項集。項集的出現頻率是在整個事務數據集D中包含該項集的事務數，簡稱為項集的頻率、支持計數或計數。如果項集的出現頻率大于或等于min_sup與D中事務總數的乘積，稱項集滿足最小支持度min_sup。如果項集滿足最小支持度，則稱它為頻繁項集（Frequent Itemset），簡稱頻集[3]。頻繁k-項集的集合通常記作Lk。

3.2 Apriori算法在交通事故關聯因素分析上的應用

Apriori算法是根據頻繁項集中所有非空子集都必須也是頻繁項集這一性質[4，5]，對目標進行第k遍掃描之前，可先產生候選集Ck，Ck可以分兩步來產生，設前一步（第k-1步）已生成（k-1）-頻繁集Lk-1，則首先可以通過對Lk-1中的成員進行連接來產生候選，Lk-1中的兩個成員必需滿足在兩個成員的項目中有（k-2）個項目是相同的這個條件方可連接，即：Ck=Lk-1ΘLk-1={AΘB│A，B?Lk-1，│A∩B=k-2}。接著，再從Ck中刪除所有包含不是頻繁的（k-1）-子集的成員項目集即可。

發(fā)生道路交通事故的原因是由多方面因素決定的，與駕駛員、車輛、道路、時間、天氣等都是有一定聯系的，是綜合共同作用的結果。具體思路是利用多維Apriori算法得出各種事故相關因素的關聯規(guī)則，以“條件集合?結果”的方式顯示，條件集合包括駕駛員因素、車輛因素、天氣因素、時間因素、照明因素中的某一個或幾個因素，即可能引發(fā)道路交通事故的原因因素。結果包括事故本身因素中的事故類型、事故主要原因、事故形態(tài)、傷害程度，即導致道路交通事故的結果因素。通過得到的每條規(guī)則的支持度和置信度來判斷規(guī)則對道路交通事故影響的程度及規(guī)則的重要性和有效性。 （下轉第98頁）

（上接第86頁）具體描述：通過選定要分析的交通事故本身與駕駛員、車輛、道路、天氣、時間等具體選項信息，利用多維Apriori算法作關聯分析。發(fā)現各個因素之間的聯系，結果采用文本形式來描述，形如（A，B，C）?D（min_sup；min_conf），其中A、B、C分別代表規(guī)則的前提條件，D代表規(guī)則的結果，min_sup和min_conf表示該規(guī)則的支持度和置信度，取值均為0%到100%之間。支持度描述的是在所有的記錄中，A、B、C同時出現的概率；置信度表示在A、B、C同時出現的條件下，發(fā)生情況D的概率。當一條規(guī)則滿足一定的最小支持度和最小置信度時，可以認為該規(guī)則是比較常見的，可信度比較高的。如：天氣：晴&照明條件：白天&駕駛員：無證駕駛?傷人事故（12.7%；29.8%），表示在所有的事故記錄中，同時滿足晴、白天和無證駕駛條件的記錄占12.7%，由于這3個條件而出現傷人事故的占29.8%。 [科]

【參考文獻】

[1]鮑海濤.聚類分析在交通事故黑點智能排查中的應用[D].吉林大學，2004：25-35.

[2]毛國君，段立娟，王實，等.數據挖掘原理與算法[M].北京：清華大學出版社，2005：65-68，280-290.

[3]陳文偉.數據倉庫與數據挖掘教程[M].北京：清華大學出版社，2006：123-125.

[4]Yang Xue-bing.A High Efficient Multi-dimensional Association Rules Mining Algorithm [J].Computer Development，2012（6）：33-39.

[5]Qin Feng，Yang Xue-bing.Research and analysis of multi-dimensional association rules mining [J].Anhui University of Technology，2013，20（2）：66-69.