改進的Apriori算法在交通事故分析中的應(yīng)用_圖文

1、郵局訂閱號:82-946360元/年技術(shù)創(chuàng)新 軟件天地PLC 技術(shù)應(yīng)用200例您的論文得到兩院院士關(guān)注改進的Apriori 算法在交通事故分析中的應(yīng)用Application of Improved Aproiri Algorithm in Traffic Accident Analysis(北京航空航天大學(xué)熊桂喜劉謝XIONG Gui-xi LIU Xie摘要:針對當(dāng)前交通管理工作中交通事故分析的特點與需求,為了有效地對事故發(fā)生時各方面因素關(guān)聯(lián)分析,本文采用一種改進的基于Hash Tree 的Apriori 算法提取交通事故歷史數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則,得到導(dǎo)致交通事故各因素的具體特征,發(fā)現(xiàn)多方面的

2、深層規(guī)律。根據(jù)這些規(guī)律,交通管理者能制定有針對性的事故預(yù)防和管理措施。并對具體應(yīng)用過程中數(shù)據(jù)準(zhǔn)備過程、數(shù)據(jù)預(yù)處理方法進行了闡述,重點介紹了改進的Apriori 算法的實現(xiàn)。關(guān)鍵詞:交通事故分析;關(guān)聯(lián)規(guī)則;關(guān)聯(lián)規(guī)則發(fā)現(xiàn);Hash Tree;Apriori 中圖分類號:TP391.1文獻標(biāo)識碼:AAbstract:To effectively perform association analysis of various factors of traffic accident,this paper make use of an improved Aproiri algorithm to mine

3、association rules in the database of traffic accident and find the detail features Deep-seated laws of factors leading to traffic accidents.According to these laws,traffic manager can develop targeted measures for accident prevention and man -agement.And the process of data preparation,data preproce

4、ssing in specific applications are described,highlighting the improved Apriori algorithm.Key words:Traffic Accident Analysis;Association Rules;Association Rules Mining;Hash Tree;Apriori文章編號:1008-0570(201009-1-0205-031引言交通事故分析是交通數(shù)據(jù)綜合分析與預(yù)報系統(tǒng)的重要組成部分,主要是分析事故發(fā)生的原因,目的在于找出事故的典型形態(tài),發(fā)現(xiàn)交通事故發(fā)生規(guī)律,對交通管理者提供警力配置、事故

5、預(yù)防宣傳、培訓(xùn)考核等決策支持。交通事故的發(fā)生不僅和駕駛員的行為有關(guān),而且與道路環(huán)境條件、天氣條件、交通狀況等有一定的聯(lián)系,是綜合因素共同作用的結(jié)果。全面系統(tǒng)地分析交通事故的成因,并用發(fā)現(xiàn)的有用知識和規(guī)律調(diào)整交通安全管理措施、改進道路交通安全設(shè)施,已成為交通管理工作的一項重要任務(wù)。目前,對于交通事故數(shù)據(jù)的分析,主要是運用多元統(tǒng)計分析和數(shù)據(jù)挖掘的相關(guān)方法來研究事故成因以及事故多發(fā)點段的特征。文獻用主成分分析理論對引起道路交通事故的天氣、交通違法行為等因素進行分析;文獻采用灰色關(guān)聯(lián)分析法,對個主元素的事故指標(biāo)進行統(tǒng)計分析,從而確定與事故相關(guān)的主因素;文獻是利用粗糙集的思想對道路交通中的不利因素進行篩

6、選,找到導(dǎo)致交通數(shù)據(jù)的最大誘因;文獻采用模糊聚類法實現(xiàn)道路交通事故成因的聚類分析,找到事故多發(fā)的主要原因、誘導(dǎo)原因以及潛在的事故隱患。這些方法都是對于單個影響因素進行分析和評估,沒有將事故發(fā)生時各方面因素關(guān)聯(lián)起來進行多方面的分析。文獻和提出用關(guān)聯(lián)規(guī)則發(fā)現(xiàn)技術(shù),從人、車、路、環(huán)境各方面著手,將各因素關(guān)聯(lián)分析,但是對關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法和它在交通事故分析中的具體實現(xiàn)過程沒有作詳細(xì)討論。2關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的過程可以分解為兩個子問題:1.找到所有出現(xiàn)頻度大于最小支持度的頻繁項目集2.由頻繁項目集生成需要的規(guī)則,即同時滿足最小支持度和最小置信度的強關(guān)聯(lián)規(guī)則。支持度和置信度的定義如下:Suppor

7、t(A B=P(A B;支持度揭示了A 和B 同時出現(xiàn)的頻率Confidence(A B=P(A |B;置信度則揭示了A 出現(xiàn)時,B 是否一定會出現(xiàn)2.1生成頻繁項目集頻繁項目集的生成是關(guān)聯(lián)規(guī)則發(fā)現(xiàn)的關(guān)鍵問題,也是算法時間開銷最大的部分。目前已提出大量的發(fā)現(xiàn)頻繁項集的算法,其中最重要的是R.Agrawal 等人提出的Apriori 算法,該算法是一種發(fā)現(xiàn)頻繁項集的基本算法。經(jīng)典的Apriori 算法需要頻繁掃描數(shù)據(jù)庫,對于大規(guī)模數(shù)據(jù)而言,開銷過大;并且在候選頻繁項集Ck 計數(shù)中要多次掃描Lk-1,當(dāng)C k 很大時,效率并不理想。對Apriori 算法的相關(guān)改進大多是在這兩個方面的工作。文獻提出

8、利用Hash Tree 存儲候選頻繁項集C k ,本文提出一種基于Hash Tree 的Apriori 算法,將在3.2節(jié)具體討論。2.2發(fā)現(xiàn)強關(guān)聯(lián)規(guī)則在得到頻繁項集后,生成強關(guān)聯(lián)規(guī)則的步驟是:對每個頻繁項集,找到它的所有非空子集,對每個非空子集,可以得到一條強關(guān)聯(lián)規(guī)則“”如果的支持度比上的比值大于minconf 。3關(guān)聯(lián)規(guī)則發(fā)現(xiàn)在交通事故分析中的應(yīng)用應(yīng)用關(guān)聯(lián)規(guī)則發(fā)現(xiàn)技術(shù)對交通事故的分析流程如圖1所示。本文的目標(biāo)是充分結(jié)合交通管理領(lǐng)域的交通事故數(shù)據(jù)分析要求,圍繞著人、車、路和環(huán)境各方面因素,采用關(guān)聯(lián)分析(發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的方法,對交通事故歷史數(shù)據(jù)庫提取關(guān)聯(lián)規(guī)則,從中找出熊桂喜:副教授205-技術(shù)創(chuàng)

9、新微計算機信息(測控自動化2010年第26卷第9-1期360元/年郵局訂閱號:82-946現(xiàn)場總線技術(shù)應(yīng)用200例軟件天地可能導(dǎo)致交通事故的相關(guān)人員特征、什么情況下的哪些交通違法行為最可能導(dǎo)致交通事故、具有哪些典型特征的路口路段是潛在的交通事故多發(fā)點等規(guī)律,同時將這些方面的事故誘因組合,更充分揭示導(dǎo)致交通事故的深層規(guī)律。圖1應(yīng)用關(guān)聯(lián)規(guī)則發(fā)現(xiàn)技術(shù)對交通事故的分析流程3.1數(shù)據(jù)準(zhǔn)備和數(shù)據(jù)預(yù)處理本文分析的主要數(shù)據(jù)源為歷年的交通事故數(shù)據(jù)。交通事故數(shù)據(jù)記錄了交通事故發(fā)生時,駕駛員、車輛、道路、天氣和時間的狀態(tài),以及事故本身的特點。本文采用星形模型構(gòu)筑交通事故多維數(shù)據(jù)結(jié)構(gòu)。在該結(jié)構(gòu)中,交通事故情況為事實表

10、,存放了6個維表的主碼,事實表的每個部分與一個維表的主碼相對應(yīng),查詢時利用這種對應(yīng)關(guān)系,返回查詢結(jié)果,得到交通事故影響要素集合。形如:男,24,2,工人,私用,摩托車,躲避障礙,窄路,積水,瀝青,一般坡,其他城市路,無控制,白天,雨,星期三,12,傷人事故,其他意外,側(cè)面相撞。數(shù)據(jù)預(yù)處理的過程主要有兩個階段:數(shù)據(jù)清理和格式變換。數(shù)據(jù)清理主要是檢驗數(shù)據(jù)字段的有效值,本文采用SQL 中的CHECK 約束來進行交通事故信息記錄集中各字段的有效值檢查。以下為CHECH 約束的具體實現(xiàn)。ALTER TABLE TrafficAccidentADD CONSTRAINT chk_TrafficAccide

11、nt CHECK (TrafficAc -cident .age BETWEEN 1AND 80and TrafficAccident.StreetLine in('一般彎','一般坡','急彎','陡坡','一般彎坡','急彎陡坡','一般坡急彎','一般彎陡坡','平直'and 格式變換是為了算法處理的需要,本文采用對數(shù)值型數(shù)據(jù)進行數(shù)量離散化,對非數(shù)值型數(shù)據(jù)進行代碼標(biāo)識的方法。如駕齡離散化為JL1:1年及以下,JL2:2年,JL3:3年,JL4:4

12、年,JL 5:5-10年,JL6:10-20年,JL7:20年以上,路面情況按照潮濕、積水、漫水、冰雪、泥濘、翻漿、泛油、坑槽、塌陷、路障、平坦、其他依次標(biāo)識成代碼LQ1-LQ12。最終得到的是面向分析主題的格式化的記錄集合。前述的記錄格式化為XB2,NL6,JL2,RL4,CS12,JF6,XZ8,LL9,LQ2,LM1,DX2,DL11,JK7,ZM1,TQ1,TW3,TH12,SL2,SY21,SX2。3.2關(guān)聯(lián)規(guī)則發(fā)現(xiàn)過程生成頻繁項目集:本文采用基于Hash Tree 的發(fā)現(xiàn)頻繁項集的Apriori 算法,算法描述如下:下面對算法中的三個關(guān)鍵步驟:建立Hash Tree 、支持度計數(shù)和

13、掃描Hash Tree 得到頻繁k-項集進行描述。Hash Tree 相關(guān)概念:Hash Tree 是一種多叉的無序樹,在層和層之間采用的是Hash 查找的思想。一般采用除余法作為Hash 函數(shù),如:Hash(key=key mod m,其中key 為關(guān)鍵字,m 是分支結(jié)點的度。Hash Tree 的詳細(xì)結(jié)構(gòu)請參見文獻。文獻提供了兩種構(gòu)建Hash Tree 的方法,具體討論了候選頻繁項插入溢出的解決方法,指出關(guān)鍵在于內(nèi)部節(jié)點的Hash 表的大小m 的取值。本文用L k -1中所包含的不同項的總數(shù)作為構(gòu)建Hash Tree 中Hash 表的大小。在本文的算法實現(xiàn)中,Hash Tree 的結(jié)點結(jié)構(gòu)

14、定義如下。建立Hash Tree 算法:算法的相關(guān)說明:(1C k 中的候選項集c 中的項均按字典序升序排列。(2用Hash 函數(shù)處理時,c 中的每個項是經(jīng)過預(yù)處理的代碼標(biāo)識,如XB2,NL6,JL2,RL4,需先將其轉(zhuǎn)化為整數(shù),為盡可能的減少Hash 沖突,采用如下轉(zhuǎn)換方法:把項中每個字符的ASC 碼累加到變量h 上,并在每次累加前把h 的值左移一位,即擴大兩倍。(3Hash Tree 的樹高與候選項集c 的項目數(shù)k 相等,葉子節(jié)點的存儲閾值基于Hash Tree 的支持度計數(shù)算法:表1事故類型為死亡事故的頻繁項集掃描Hash Tree 得到L k 的算法也采取同樣的思想,這里不再贅述。本文

15、設(shè)定minsupport 為100,在1000條交通事故記錄集合共得到4個頻繁項集L 1、L 2、L 3和L 4。郵局訂閱號:82-946360元/年技術(shù)創(chuàng)新 軟件天地PLC 技術(shù)應(yīng)用200例您的論文得到兩院院士關(guān)注由頻繁項集生成關(guān)聯(lián)規(guī)則:如用戶想了解造成人員傷亡的重大交通事故的影響因素,可在頻繁項集中搜索含有項SL1(死亡事故的項集,得到表1所示的頻繁項集。本文設(shè)定最小置信度minconf=10%。以頻繁4項集XB2,JL1,SY21,SL1為例來說明生成關(guān)聯(lián)規(guī)則的過程,由于在這里我們只關(guān)心結(jié)果為SL1的規(guī)則,所以只需用XB2,JL1,SY21,SL1的支持度比上XB2,JL1,SY3的支持

16、度,比值大于10%,作為強關(guān)聯(lián)規(guī)則輸出XB2,JL21,SY21SL1,支持度為11.3%(1000個樣本,113個數(shù)據(jù)出現(xiàn)了這種情況,置信度為40.2%,這說明駕齡在1年及以下的男性駕駛員出現(xiàn)操作不當(dāng)而導(dǎo)致交通死亡事故的可能性為40.2%。表2為最終生成的結(jié)果為SL1(死亡事故的強關(guān)聯(lián)規(guī)則一部分。表2事故類型為死亡事故的強關(guān)聯(lián)規(guī)則3.3結(jié)果分析與應(yīng)用本文的目的就是找出人、車、路、環(huán)境與交通事故結(jié)果間的關(guān)聯(lián)關(guān)系,發(fā)現(xiàn)各方面因素對交通事故的影響程度。在關(guān)聯(lián)規(guī)則分析的過程中,可以對前件為人員信息的關(guān)聯(lián)規(guī)則分析,包括性別、年齡、駕齡、人員類型等項進行組合,從中找出可能導(dǎo)致交通事故的相關(guān)人員特征,如在

17、3.2節(jié)得到的規(guī)律:駕齡在1年及以下的男性駕駛員出現(xiàn)操作不當(dāng)而導(dǎo)致交通死亡事故的可能性為40.2%,得到這些特征從而可以提出有針對性的教育宣傳、培訓(xùn)考核等預(yù)防方法。根據(jù)交通環(huán)境和事故原因的組合為前件進行分析,得到天氣為晴、照明條件為夜間有路燈照明的情況下超速行駛、不按規(guī)定讓行等導(dǎo)致的交通事故占很大比例,可以針對這些交通違法行為,提出對應(yīng)的處理對策。還可以把道路信息屬性中的路口路段類型,路面情況,路面類型等屬性組合,根據(jù)關(guān)聯(lián)規(guī)則中發(fā)現(xiàn)的具體道路特征,直接根據(jù)地理位置信息數(shù)據(jù)庫得到符合條件的路口路段,這些路口路段就是潛在的交通事故多發(fā)點。4結(jié)論在交通事故分析中,為將事故發(fā)生時各方面因素關(guān)聯(lián)起來,本

18、文運用關(guān)聯(lián)規(guī)則發(fā)現(xiàn)技術(shù)來分析人、車、路、環(huán)境等多方面因素對事故發(fā)生的影響程度,以充分展示導(dǎo)致事故發(fā)生的潛在的深層次規(guī)律。給出了具體運用過程中的數(shù)據(jù)準(zhǔn)備過程、數(shù)據(jù)預(yù)處理方法,重點介紹了基于Hash Tree 的發(fā)現(xiàn)頻繁項集的Apri -ori 算法,該算法解決了頻繁項集發(fā)現(xiàn)過程中效率不高的問題。由于樣本數(shù)據(jù)的隨機性和波動性,并不是所有的關(guān)聯(lián)規(guī)則都能形成有指導(dǎo)意義的知識,需要交通管理人員和交通領(lǐng)域?qū)＜疫M行甄別和修正。同時,采用統(tǒng)一最小支持度和最小置信度的限制方法也是導(dǎo)致產(chǎn)生大量無意義的關(guān)聯(lián)規(guī)則的重要原因,如何增加其他限制和約束來提高關(guān)聯(lián)規(guī)則發(fā)現(xiàn)的效率,這個問題值得做進一步的研究。本文作者創(chuàng)新點:將

19、關(guān)聯(lián)規(guī)則發(fā)現(xiàn)技術(shù)應(yīng)用到交通事故分析中來,采用一種改進的基于Hash Tree 的Apriori 算法對交通事故歷史數(shù)據(jù)庫提取關(guān)聯(lián)規(guī)則,得到導(dǎo)致交通事故的人、車、路、環(huán)境各方面影響因素之間的關(guān)聯(lián)關(guān)系,為交通管理者制定有針對性的交通事故預(yù)防和管理措施提供決策支持。參考文獻1許卉瑩,包勇強等.道路交通事故數(shù)據(jù)分析挖掘研究J.中國人民公安大學(xué)學(xué)報,2008(4:69-732過秀成,盛玉剛.公路交通事故黑點分析技術(shù)M.南京:東南大學(xué)出版社,2009:253-2623林忠,宇仁德.基于主成分分析理論的交通事故成因研究J.山東交通學(xué)院學(xué)報,2006,14(1:55-574潘昭宇,過秀成,盛玉剛等.灰色關(guān)聯(lián)分

20、析法在公路交通事故黑點成因分析中的應(yīng)用J.交通運輸工程與信息學(xué)報,2008,6(3:96-1015董立巖,劉光遠(yuǎn),范淼淼等.數(shù)據(jù)挖掘技術(shù)在交通事故分析中的應(yīng)用J.吉林大學(xué)學(xué)報,2006,44(6:951-9556張鵬,張靖,劉玉增等.粗集在交通事故黑點成因分析中的應(yīng)用J.電子科技大學(xué)學(xué)報,2007,36(2:267-2707肖慎,過秀成,徐建東.糊聚類法在交通事故黑點成因分析中的應(yīng)用J.交通運輸系統(tǒng)工程與信息,2002,2(8:40-438顏躍進,李舟軍,陳火旺.頻繁項目集挖掘算法J.計算機科學(xué),2004,31(3:112-1149Jiawei Han,Jian Pei,Yiwen Yin,Runying Mao.Mining Frequent Patterns without Candidate Generation:A Frequent-Pattern T