摘??要： 根據數據挖掘技術中的關聯規則理論，提出“道路交通事故屬性”的定義，并建立一種新的道路交通事故數據挖掘模型，利用改進的多維多數據類型的Apriori算法，從記錄交通事故的數據庫中發現潛在的、有價值、有聯系的規律，用以指導交通管理部門找出道路黑點，并做出決策，杜絕事故隱患、減少事故發生，保障人們的生命和財產的安全。
　　關鍵詞： 道路交通事故屬性； 關聯規則； 數據挖掘； Apriori算法

?

　　智能交通系統ITS（Intelligent Transportation System）是先進的信息技術、數據通訊傳輸技術、電子傳感技術、電子控制技術及計算機處理技術等多種高新技術與傳統交通運輸融合的集成和應用。改善道路交通環境。
　　關聯規則是數據挖掘的主要方法，是指在數據集中支持度和置信度分別滿足給定閾值的規則,反映一個事物與其他事物之間的相互依存性和關聯性。關聯規則挖掘的Apriori算法是根據有關頻繁項集特性的先驗知識而命名的，算法中蘊含的一條基本性質是一個頻繁項集的任一子集均應是頻繁的。借助一定的專業領域知識，關聯規則可以直接用于分析數據的因果關系，做出規則預測。從大量的數據中發現其關聯關系在市場定位、決策分析和商業管理等領域極為有用。
　　本文提出“道路交通事故屬性”的定義，并且采用“星型全連接數據模型”對道路交通事故屬性的數據組織建模。結合對經典單維單層的Apriori算法進行改進，實現挖掘多維多數據類型關聯規則的新算法。通過對某市區的道路交通事故數據進行關聯規則提取分析，產生大量具有支持度和置信度的強關聯規則，可有效地分析交通事故發生的主要原因，為決策者提供切實可行的治理方案和預防措施。
1 關聯規則理論
1.1 關聯規則的基本概念
　　

　　式中：support(AYB)為包含項集AYB的交易記錄數目，support(A)為包含項集A的交易記錄數目。
規則的支持度和置信度是兩個規則的度量， 它們分別反映發現規則的實用性和確定性。這兩個閾值均在0%~100%之間，而不是0～1之間。
　　給定一個交易集D，挖掘關聯規則問題就是產生支持度和置信度分別大于用戶給定的最小支持度min-sup(minimum support count)和最小置信度min-con(minimum confidence count)的關聯規則。前者即用戶規定的關聯規則必須滿足的最小支持度，表示了一組物品集在統計意義上需滿足的最低程度；后者即用戶規定的關聯規則必須滿足的最小置信度，反應了關聯規則的最低可靠度。
　　如果不考慮關聯規則的支持度和置信度，則在事務數據庫中存在無窮多的關聯規則。事實上，人們一般只對滿足一定的支持度和置信度的關聯規則感興趣。一般把同時滿足最小支持度閾值和最小置信度閾值的規則稱為強規則。給定一個事務集D，挖掘關聯規則問題就是產生支持度和置信度分別大于用戶給定的最小支持度和最小置信度的關聯規則，也就是強規則的問題。
　　因此，關聯規則挖掘可定義為：給定一個事務數據庫D，尋找出所有滿足support>min-sup，confidence>min-con的關聯規則AB。
??? 具體產生關聯規則的操作說明如下：
　　(1) 對于每個頻繁項集l，產生l的所有非空子集。
　　(2) 對于每個l的非空子集s，若support(l)/support(s)>=min-con，則產生一個關聯規則“s(l-s)”。
　　項的集合稱為項集(Item set),包含k個數據項的項集稱為k-項集。
　　項集的出現頻率是在整個交易數據集D中包含該項集的交易記錄數，簡稱為項集的頻率、支持度或計數。
如果項集的出現頻率大于或等于min-sup與D中事務總數的乘積，稱項集滿足最小支持度min-sup。如果項集滿足最小支持度，則稱它為頻繁項集(Frequent Item set)，簡稱頻集。頻繁k-項集的集合通常記作Lk。
1.2 Apriori算法
　　Apriori算法是由AGRAWAL R等人提出的。該算法利用一個層次順序搜索的循環方法完成頻繁項集的挖掘工作。利用k-項集來產生(k+1)-項集。核心思想是把發現關聯規則的工作分為兩步：第一步通過迭代檢索出事務數據庫中的所有頻繁項集，即頻繁項集的支持度不低于用戶設定的閾值；第二步從頻繁項集中構造出滿足用戶最低信任度的規則。挖掘或識別所有頻繁項集是Apriori算法的核心，占整個計算量的大部分。后來的許多算法多是對Apriori算法的改進研究。
　　為提高按層次搜索并產生相應頻繁項集的處理效率，Apriori算法利用了一個稱為Apriori的重要性質,來幫助有效縮小頻繁項集的搜索空間。Apriori算法的性質：頻繁項集中所有非空子集也都必須是頻繁項集。
　　這一性質是由AGRAWAL和SRIKANT提出并證明的，若一個集合不能通過測試，該集合的所有超集也不能通過同樣的測試。根據這一性質，進行第k遍掃描之前，可先產生候選集C_k，C_k可以分兩步來產生，設前一步(第k-1步）已生成(k-1)-頻繁集L_k-1，則首先可以通過對L_k-1中的成員進行聯接來產生候選，L_k-1中的兩個成員必需滿足在兩個成員的項目中有k-2個項目是相同的這個條件方可連接，即：
　　　　

　　然后再從C_k中刪除所有包含不是頻繁的(k-1)-子集的成員項目集即可^[2]。也可以根據定義，如果項集I不滿足最小支持度閾值min-sup，則I不是頻繁的，即P(I)[3]。
2 基于關聯規則的道路交通事故數據挖掘模型
2.1建立數據模型
　　實際上,交通管理部門在道路交通事故預防工作中，主要是根據不同時期、不同地點道路交通事故的態勢做出相應的管理對策，從管理上減少事故。要做到這一點，首先要對事故發生的情況進行數據分析，從中發現規律性的東西，做到有的放矢。道路交通事故研究主要建立在大量事故統計分析資料的基礎上，由于道路交通事故難以現場直接觀測其發生過程，需要通過事后的數據資料分析來研究其發生規律。因此，針對交通事故基礎數據資料的整理顯得尤為重要。如何從大量的道路交通事故的誘發因素中發現它們之間聯系的內在規律，進行人為控制和干預，以減少交通事故發生的概率是大家所關注的焦點。結合對實際情況的分析，提出以下問題：
　　在以往關聯規則理論研究中，主要集中在單維單層布爾型關聯規則上，即每一條規則包括一個多次出現的謂詞。如果把典型的單維單層布爾型的數據挖掘的Apriori算法直接作用于此次項目中的數據，則Apriori算法只能解決針對多維數據列表中的某一列屬性的關聯規則的挖掘，而不能解決多個屬性集之間的數據挖掘。例如，只能挖掘道路交通事故屬性中的事故主要原因的關聯規則：酒后駕車，疲勞駕車，超速行駛，逆向行駛，違章超車，違章轉彎，違章裝載……。但是如果要挖掘駕駛員因素與道路因素之間的關聯規則，此算法則無法直接應用。
　　如果把道路交通事故屬性集的所有屬性不分類別地全部放到一個屬性集合中，使其成為一個混合內容的單維數據集合，就可以直接利用Apriori算法。例如，把天氣屬性：沙塵、雨、雪、霧、晴、大風、陰、其他的每個元素都作為整體事故屬性集合中的屬性值，存在如下問題：(1) 每次數據庫掃描的信息過于龐大，降低效率;(2) 同一類型的屬性被拆開，不利于做統計分析;(3) 得到的結果很可能是沒有意義的;(4) 數據庫將變得雜亂無章等。
　　人們已提出了挖掘單層與多層的布爾型關聯規則、多維多層數據類型關聯規則的許多算法，最著名的是單層布爾型Apriori挖掘算法。許多算法都是基于Apriori的，其缺陷是掃描數據庫的次數正比于最大模式的長度。而挖掘多維多層關聯規則過程中發現的模式長度在20左右的情況并不少見，算法代價非常高。其次，已有的多維多層關聯規則挖掘算法只能通過合并相鄰的數值型屬性區間來建立有限的概念層次，不能滿足實際應用的需要。
　　針對以上問題，本文基于多維多層的關聯規則的挖掘算法,著重研究數據挖掘技術在決策分析系統中的應用，針對道路交通事故這一實際問題對典型的單維單層布爾型Apriori算法進行改進，實現挖掘多維多層多數據類型關聯規則的新算法。
2.2 道路交通事故屬性的定義
　　道路交通事故屬性PRTA(Property of the Road Traffic Accident)是指道路交通事故發生時，駕駛員、車輛、道路、天氣和時間的狀態，以及事故本身的特點,即：駕駛員屬性、車輛屬性、道路屬性、天氣屬性、時間屬性和事故本身屬性的集合。這樣，就可以將大量的道路交通事故數據按照道路交通事故屬性組織為信息進行數據挖掘。
2.3 道路交通事故屬性的數據模型
　　在大規模的數據庫中，由于多維數據空間的稀疏性，若要在低層和原始層的數據項之間發現強的和有趣的關聯規則比較困難，因為好多項集沒有足夠的支持度。在較高的概念層發現的強關聯規則可能提供普遍意義的知識，對于一個用戶代表普遍意義的知識，對于另一個用戶可能是新穎的。這樣，數據挖掘系統可在多個抽象層挖掘關聯規則，且容易在不同的抽象空間轉換。
　　概念層次樹是數據庫中各屬性值和概念依據抽象程度不同而構成的一個層次結構,如圖1所示。

　　圖中,PRTA為道路交通事故屬性; D(Driver)為駕駛員屬性; V(Vehicle)為車輛屬性; R(Road)為道路屬性; W(Weather)為天氣屬性; T(Time)為時間屬性; A(Accident)為事故本身屬性。
　　多層關聯規則的挖掘一般采用自頂向下的策略，由概念層1開始向下，到較低的更特定的概念層，對每個概念層的計算頻繁項集累加計數，直到不能再找到頻繁項集，即：一旦找到概念層1的所有頻繁項集，就開始在第2層找頻繁項集，如此下去，就可以在每一層使用發現頻繁項集的多維多數據類型Apriori算法。
　　在進行多維數據挖掘時，將數據按一定的結構組織起來，通常的數據建模方法有多維數據結構、星型模型、雪花模型以及超立方體等?；趯Φ缆方煌ㄊ鹿蕦傩缘姆治?，這里建立星型全連接結構的數據模型如圖2所示。

　　定義了道路交通事故屬性的概念層次樹和星型全連接的數據模型后， 就可以對發生道路交通事故的各個因素進行定性的分析。
　　道路交通事故屬性的數據來自“道路交通事故信息采集項目表”，每一個道路交通事故屬性是表的維，每個維連接著一個維表。要對D[D₁,D₂,…,D_n]維進行關聯規則的挖掘，每個維Di表示一個屬性，每個維包含|D_i|(i=1，2，…，n)個不同的數值，在這里|D_i|為維Di具有的不同屬性的個數。在這些維的每個單元中存儲的是原始數據的計數值。一般情況下，可以把一個n維的數據映射成一個具有n個屬性的表。
　　交通事故屬性具有概念分層，主要有三層：
　　第一層是道路交通事故屬性。
　　第二層是第一層的細化：駕駛員屬性、車輛屬性、道路屬性、天氣屬性、時間屬性、事故本身的屬性。
　　第三層是對第二層的更進一步細化，主要是對道路交通事故每一屬性維的刻度(也就是粒度)進行分析：性別、年齡、駕齡、駕照種類、駕駛員類型、出行目的、車輛使用性質、交通方式、行駛狀態、所屬行業、公路行政等級、地形、路面情況、路面類型、道路橫斷面、路口路段類型、道路線形、道路類型、交通控制方式、照明條件、小時、星期、月份、事故類型、事故主要原因、事故形態、現場。
2.4 提取道路交通事故屬性的關聯規則
　　從以上分析可以看出，道路交通事故屬性模型是多維多層的。由于Apriori算法只是在單維單層的數據模型上進行挖掘，不適合對多維多層的數據模型進行挖掘，要想對上述的道路交通事故屬性的數據模型進行分析，Apriori算法必須進行一定的改進。將數據模型的每個維看成是一個謂詞，就可以挖掘多維關聯規則，在多維關聯規則的挖掘中，搜索頻繁謂詞集。對于多層數據模型，在設定各層的支持度大小時有多種方法，再進行多維多層的數據挖掘是比較繁瑣的，這里對其進行了簡化。在進行關聯規則分析前，預先指定該維的那一個層次參與關聯分析，其他層次不參與關聯分析，從而將問題簡化為單純的多維數據模型的挖掘。在進行挖掘之前，對事故主要原因選擇第三層，其他維都是單層的。通過這樣的指定，就可以得到多維單層道路交通事故屬性數據，便于關聯分析。
　　通過選定要分析的交通事故本身與駕駛員、車輛、道路、天氣、時間等具體選項信息，利用多維多數據類型Apriori算法作關聯分析，發現各個因素之間的聯系，結果采用文本形式來描述，形如（A，B，C）D（sup；con）。其中,A、B、C分別代表規則的前提條件，D代表規則的結果，sup和con表示該規則的支持度和置信度，取值均為0 %～100 %之間。支持度描述的是在所有的記錄中，A、B、C同時出現的概率；置信度表示在A、B、C同時出現的條件下，發生情況D的概率。當一條規則滿足一定的最小支持度和最小置信度時，可以認為該規則是比較常見的，可信度是較高的。
　　對多維數據關聯分析需對Apriori算法進行改進，數據挖掘簡要流程圖如圖3所示。

3 道路交通事故數據的分析
　　實驗使用的是對某市市區2002年12月21日至2007年7月20日的道路交通事故數據進行測試。采取星型全連接的數據模型對道路交通事故屬性數據按照上述數據建模進行組織。對該市區的道路交通事故數據進行關聯規則提取分析，得出許多具有實際意義的結論。
　　以分析2003年12月至2004年7月某市市區事故原因為例，首先得到的是各種事故原因發生的比例（事故數據個數為2 401)如:不按規定讓行(27.66%)、未保持安全距離(12.16%)、超速行駛(8.79%)、違章拐彎(7.58%)、其他機動車原因(5.46%)、逆向行駛(4.91%)、違章變更車道(4.33%)等，其他事故原因比例較小，可視為“噪音”而省略。
假設用戶想了解導致“不按規定讓行”這一結果，設置最小支持度閾值為5%，最小置信度閾值為40%。產生以下規則：
　　(1)條件：道路因素
　　規則：
　?、俚缆窓M斷面：混合式 & 道路類型：主干路不按規定讓行（6.01%，36.65%）。
　　②路口路段類型：四枝分叉口不按規定讓行（7.04%，42.66%）。
　?、勐访骖愋停簽r青&道路橫斷面：混合式 & 照明條件：白天 &交通控制方式:無控制不按規定讓行(9.79%，36.40%)。
　　(2)條件：天氣因素、道路因素
　　規則：
　　①天氣：晴 & 地形：平原 & 道路橫斷面：混合式 & 照明條件：白天&道路線形：平直&交通控制方式：無控制不按規定讓行（9.27%，36.31%）。
　?、谔鞖猓呵?& 路面類型：瀝青 & 道路橫斷面：混合式&照明條件：白天不按規定讓行（11.84%，36.34%）。
　?、厶鞖猓呵?路面情況：平坦&道路橫斷面：混合式 & 照明條件：白天 & 道路線形：平直 & 交通控制方式：無控制不按規定讓行（8.67%，36.33%）。
　?、芴鞖猓呵?& 地形：平原&道路橫斷面：混合式 &　照明條件：白天 & 道路線形：平直 & 交通控制方式：無控制不按規定讓行（9.27%，36.31%）。
　　對2002年12月至2007年7月該市區交通事故情況進行分析,得出以下結果：
　　(1) 機動車駕駛人違章駕車行為導致交通事故的發生率占到事故總數的85.79%，而死亡率占67.14%。
　　(2)平直道路事故頻繁：其上事故發生率占總數的75.63%，死亡率占81.34%。
　　(3) 晴天事故占絕大比例：事故發生率占總數的90.24%，死亡事故占89.27%。
　　(4) 從月統計周期分布來看，6～9月為事故多發時段，9月事故致人死亡較為突出。
　　(5) 從24小時事故分布情況看，中午、傍晚和下午時分是交通事故的多發時段。
　　以上實驗所得到的結論與交警的經驗數據基本一致。
　　本文基于關聯規則理論，針對道路交通的實際問題，建立了基于關聯規則理論的星型全連接數據模型，并提出一種改進的多維多數據類型Apriori算法，用來分析道路交通事故歷史數據，并且完成了系統決策分析模塊的實現。實踐證明，關聯規則的挖掘能夠發現大量數據的屬性之間有趣的關聯關系，利用關聯規則挖掘技術在關聯性發現方面有著強大的優勢。關聯規則最重要的特點是關聯是自然組合的，這對發現所有屬性的子集存在的模式是非常適用的。

參考文獻
[1] ?LIU Zheng Jiang, WU Zhao Lin. Data mining to human factors based on ship collision accident survey reports.?Navigation of China, Jun, 2004(2).
[2] ?YANG Xue Bing.A high efficient multi-dimensional association rules mining algorithm. Computer Development,2002(6）.
[3] ?SONG Zhong shan. Research on the algorithm apriori of?mining association rules. Journal of South-Central University fox Nationalities(Nat. Set Edition), Mar. 2003,22(1）.

?