基于DENCLUE 聚類算法的交通事故多發(fā)點(diǎn)鑒別方法

王鴻遙 孫 璐 游克思

1.煙臺(tái)公路局，山東，煙臺(tái) 264000

2.東南大學(xué)交通學(xué)院，南京 210096

3.美國(guó)華盛頓Catholic 大學(xué)，土木工程系，美國(guó)，華盛頓 20064

0 引 言

事故多發(fā)點(diǎn)是指在一定的時(shí)間內(nèi)交通事故在道路沿線呈現(xiàn)積聚的空間分布狀態(tài)。對(duì)事故多發(fā)點(diǎn)的合理診斷與改善能夠有效地降低交通事故率，提高道路安全水平。

現(xiàn)有事故多發(fā)點(diǎn)鑒別方法的差別主要體現(xiàn)在不同的定量化判別指標(biāo)[1-5]，常見的有基于事故數(shù)的絕對(duì)指標(biāo)（如累計(jì)頻率曲線法）；基于事故率的相對(duì)指標(biāo)（如意大利方法，質(zhì)量控制法等）；綜合事故數(shù)-事故率方法（如矩陣法等）。

目前，這些方法在事故多發(fā)點(diǎn)的鑒別應(yīng)用中主要表現(xiàn)在以下幾個(gè)方面的不足：（1）需要事先對(duì)要排查的道路進(jìn)行路段劃分，這樣容易將原本事故積聚的位置人為地分隔為兩個(gè)或多個(gè)排查路段，導(dǎo)致事故多發(fā)點(diǎn)的遺漏，又不能很好地反映出事故多發(fā)點(diǎn)在道路上分布長(zhǎng)度的任意性及對(duì)其進(jìn)行排查的隨機(jī)性。（2）單獨(dú)考慮事故多發(fā)點(diǎn)，忽略其對(duì)周邊環(huán)境危險(xiǎn)性的影響。事實(shí)上事故的發(fā)生是由于發(fā)生點(diǎn)周邊的道路交通環(huán)境與駕駛員等因素相互作用的結(jié)果。（3）項(xiàng)目級(jí)事故多發(fā)點(diǎn)的鑒別存在“小樣本、長(zhǎng)周期”的特點(diǎn)，采用傳統(tǒng)的事故多發(fā)點(diǎn)鑒別方法容易遺漏事故多發(fā)點(diǎn)。

針對(duì)上述存在的問(wèn)題，本文提出了一種基于DENCLUE 核密度聚類算法的事故多發(fā)點(diǎn)鑒別方法，算法中用影響函數(shù)來(lái)描述每個(gè)事故點(diǎn)對(duì)周圍的影響；在多發(fā)點(diǎn)識(shí)別中反映實(shí)際道路事故密集區(qū)域，避免了事先對(duì)路段進(jìn)行劃分，同時(shí)還能實(shí)現(xiàn)任意道路多發(fā)點(diǎn)長(zhǎng)度的聚類；能實(shí)現(xiàn)在小樣本情況下，充分凸顯道路沿線的危險(xiǎn)性，可以有效地應(yīng)用于事故多發(fā)點(diǎn)鑒別的研究。

本文首先介紹了 DENCLUE 聚類算法的基本思想、定義和計(jì)算步驟；然后分析該算法在事故多發(fā)點(diǎn)鑒別中的可行性；之后通過(guò)實(shí)例對(duì)比分析了DENCLUE 算法和傳統(tǒng)事故多發(fā)點(diǎn)鑒別方法；最后總結(jié)并指出了該算法進(jìn)一步的研究方向。

1 DENC LUE 聚類算法

DENCLUE 算法是一種泛化的基于核密度估計(jì)的聚類算法，其核心思想是每一個(gè)空間數(shù)據(jù)點(diǎn)通過(guò)影響函數(shù)事先對(duì)空間產(chǎn)生影響，影響值可以疊加，從而在空間形成一曲面，曲面的局部極大值點(diǎn)為一聚類吸引子，該吸引子的吸引域形成一類[6-9]。

1.1 基本定義

定義1 影響函數(shù)

式中，d(x,y)為點(diǎn)x 和點(diǎn)y 之間的廣義距離（一般指歐氏距離）；ρ 為反映該點(diǎn)數(shù)據(jù)影響量，不同數(shù)據(jù)的影響量可能不完全相同；σ 為影響函數(shù)的窗寬，又稱為輻射因子，反映了該點(diǎn)數(shù)據(jù)對(duì)周圍影響能力，是個(gè)參量。

定義 2 密度函數(shù)給定數(shù)據(jù)集D 數(shù)據(jù)空間S 的任意一點(diǎn)P 的密度函數(shù)定義為，

定義3 梯度

定義4 密度吸引子和密度吸引 稱x*∈S 為一密度吸引子，當(dāng)且僅當(dāng)x*是密度函數(shù)的一個(gè)局部極大值。x ∈S 被x*密度吸引，當(dāng)且僅當(dāng) ?k ∈N，d(xk,x*)≤ε。

定義5 中心聚類 對(duì)于密度吸引子x*，如果存在子集C ?D，使得 ?x ∈C，x 都被x*密度吸引，且（ξ＞0 為預(yù)定義的密度門限值），則稱S 為以x*為中心（關(guān)于ξ，σ 的）確定的聚類。

定義 6 噪聲點(diǎn) 如果點(diǎn)x 被局部極大值點(diǎn)*x 密度吸引，但，則稱x 為噪聲點(diǎn)。

定義 7 任意形狀聚類對(duì)于密度吸引子集合X如果存在子集C ?D，使得：（1）使得 ?x ∈C，x 都被*x 密度吸引，且；（2）總存在從的路徑P，滿足 ?y ∈P 有則稱C 為由X 確定的關(guān)于ξ，σ 的任意形狀聚類。

定義8 局部密度函數(shù)

1.2 算法步驟

Step 1 預(yù)聚類過(guò)程 初步確定高密度網(wǎng)格，對(duì)點(diǎn)數(shù)量大于一定值的高密度網(wǎng)格進(jìn)行分析以加快運(yùn)算速度。

（1）對(duì)空間數(shù)據(jù)D 以2 σ 為寬度進(jìn)行網(wǎng)格劃分，確定非空網(wǎng)格集Cp（只考慮非空網(wǎng)格），每個(gè)網(wǎng)格中數(shù)據(jù)數(shù)記為Nc；

（2）確定ξc，高密度網(wǎng)格

Step 2 聚類過(guò)程 對(duì)上述高密度網(wǎng)格以及與其相連的網(wǎng)格點(diǎn)構(gòu)造密度函數(shù)，計(jì)算密度吸引子，最終確定聚類結(jié)果。

（1）確立局部計(jì)算區(qū)域

即只有高密度網(wǎng)格集以及與高密度網(wǎng)格相連接的網(wǎng)格用于聚類分析，其中h(cs,c)指聚類分析中的高密度網(wǎng)格 cs與網(wǎng)格c 相連接的函數(shù)。

（2）計(jì)算相連的高密度網(wǎng)格局部密度函數(shù)，以Gauss 函數(shù)為例，

式中，n(x)為點(diǎn)x 附近區(qū)域；m(c1)為網(wǎng)格c1的平均值；k 為正整數(shù)；h(c1,c)意思同上。

（3）根據(jù)局部密度函數(shù)，利用爬山法確定密度吸引子以及被密度吸引子所吸引的點(diǎn)集（將達(dá)到相同最大值的點(diǎn)歸位一類）。

2 算法應(yīng)用可行性分析

2.1 邏輯思想

基于核密度的 DENCLUE 算法通常用于處理高維海量數(shù)據(jù)的聚類分析，其核心思想是每一個(gè)空間數(shù)據(jù)點(diǎn)通過(guò)事先影響函數(shù)對(duì)空間產(chǎn)生影響，影響值可以疊加，從而在空間形成曲面，曲面的局部極大值點(diǎn)為密度吸引子，該吸引子的吸引域聚成一類。通過(guò)上面的分析，每個(gè)事故點(diǎn)對(duì)周圍都有一定的影響，影響曲線近似認(rèn)為正態(tài)分布曲線[9]，即數(shù)據(jù)點(diǎn)的影響函數(shù)為高斯函數(shù)。因此將DENCLUE 算法中所研究的點(diǎn)可以描述為事故發(fā)生的地點(diǎn)，維數(shù)是一維，即事故發(fā)生點(diǎn)位置；ξ 作為事故多發(fā)點(diǎn)的鑒別標(biāo)準(zhǔn)，當(dāng)時(shí)，所聚類段位事故多發(fā)段，即多個(gè)事故點(diǎn)影響曲線綜合疊加下的密度值大于預(yù)先的設(shè)定閾值ξ。因此，可以將DENCLUE 算法用于事故多發(fā)點(diǎn)排查具有一定的可行性。

用于事故多發(fā)點(diǎn)鑒別時(shí)，只考慮事故數(shù)的位置，即屬于一維數(shù)據(jù)的聚類分析問(wèn)題，建立標(biāo)準(zhǔn)影響函數(shù)采用高斯函數(shù)，

則局部密度函數(shù)為，

式中，K 值用于描述事故嚴(yán)重性的指標(biāo)，與事故本身密切相關(guān)，事故越嚴(yán)重，所造成的損失越大，K 值也就越大。根據(jù)文獻(xiàn)[10]，將幾種事故嚴(yán)重程度之間的換算比值如下：輕微事故∶一般事故∶重大事故∶特大事故=0.5∶1∶2∶3。N 為計(jì)算局部區(qū)域內(nèi)事故總數(shù)；σ 為計(jì)算的窗寬；xi為事故數(shù)據(jù)點(diǎn)的位置信息即樁號(hào)。

2.2 關(guān)鍵參數(shù)討論

算法中有兩個(gè)重要參數(shù)，窗寬σ 和密度限值ξ 對(duì)聚類結(jié)果有重要的影響，其中，如果ξ 值太大，聚類結(jié)果容易丟失低密度的聚類；反之，如果ξ 值太小，多個(gè)鄰近的高密度聚類將被劃分到一個(gè)聚類中，使得聚類結(jié)果缺乏可解釋性。σ 的選取會(huì)影響全局密度函數(shù)的估計(jì)結(jié)果，當(dāng)σ→∞時(shí)，所有數(shù)據(jù)被聚類為一個(gè)類；當(dāng)σ→0 時(shí)，所有數(shù)據(jù)被聚類為N 類，每個(gè)數(shù)據(jù)點(diǎn)自成一類，顯然無(wú)法發(fā)現(xiàn)所有的聚類。將DENCLUE 算法用于事故多發(fā)點(diǎn)鑒別中時(shí)，ξ 值實(shí)質(zhì)就是事故多發(fā)點(diǎn)鑒別標(biāo)準(zhǔn)，關(guān)于事故多發(fā)點(diǎn)的鑒別標(biāo)準(zhǔn)有絕對(duì)標(biāo)準(zhǔn)和相對(duì)標(biāo)準(zhǔn)，絕對(duì)標(biāo)準(zhǔn)可以根據(jù)相關(guān)部分的規(guī)定，如公安部交通管理局《全面排查交通事故多發(fā)點(diǎn)段工作方案》中采用的鑒別方法標(biāo)準(zhǔn)。相對(duì)標(biāo)準(zhǔn)是根據(jù)實(shí)際道路事故發(fā)生情況，不同路段間危險(xiǎn)程度的橫向比較以及綜合考慮改善資金的約束情況，最終確定鑒別的標(biāo)準(zhǔn)。

3 實(shí)例應(yīng)用

3.1 事故數(shù)據(jù)[11]

事故資料收集如表（1）所示。

2.教學(xué)資源建設(shè)與應(yīng)用。課程設(shè)置方面，干部網(wǎng)絡(luò)學(xué)習(xí)平臺(tái)通常將課程分為必修課和選修課，學(xué)員需修夠規(guī)定的學(xué)時(shí)，在教學(xué)內(nèi)容學(xué)習(xí)完成后通過(guò)考試測(cè)驗(yàn)才能獲得相應(yīng)的學(xué)分。課程內(nèi)容方面，平臺(tái)大多依據(jù)《干部教育培訓(xùn)工作條例》將課程分類為黨性修養(yǎng)、政治理論、業(yè)務(wù)知識(shí)、科學(xué)人文素養(yǎng)等，部分地方會(huì)適當(dāng)增添地方特色內(nèi)容。課程形式當(dāng)面，課程主要以錄制視頻、直播、交互課件、圖文資訊等形式呈現(xiàn)。

表1 事故統(tǒng)計(jì)資料Tab.1 Accident statistics

3.2 計(jì)算結(jié)果

（1）傳統(tǒng)基于事故數(shù)指標(biāo)方法

起點(diǎn)為K16+000 m,按1 km 步長(zhǎng)等距離劃分為8個(gè)單元，分別作每段的頻率直方圖，如圖1 所示?？梢钥闯鰠^(qū)間Q2—Q6 由于事故數(shù)相等，因此不能鑒別出最危險(xiǎn)集中段。

圖1 事故頻率直方圖Fig.1 Accident frequency histogram

改變起始位置，從K16+100 m，以1 km 步長(zhǎng)重新劃分8 個(gè)路段，所作頻率直方圖如圖2 所示。可以看出區(qū)間Q5K20+100—K21+100 為最危險(xiǎn)段，長(zhǎng)度固定1 km。

圖2 改變起始位置時(shí)事故頻率直方圖Fig.2 Accident frequency histogram with changing original location of the road section

（2）DENCLUE 聚類算法

計(jì)算區(qū)間邊長(zhǎng)為1 km，高密度區(qū)間設(shè)置事故數(shù)量閾值為2 件，鄰近區(qū)域，事故多發(fā)點(diǎn)鑒別標(biāo)準(zhǔn)采用相對(duì)標(biāo)準(zhǔn)，即根據(jù)實(shí)際道路事故發(fā)生情況，不同路段間危險(xiǎn)程度的橫向比較以及考慮改善資金的約束情況下采用0.6 作為閾值ξ；不考慮事故的嚴(yán)重程度，令K=1。計(jì)算結(jié)果如圖3 所示。從圖中可以直觀看出沿線危險(xiǎn)路段，聚類結(jié)果為C1=｛Z2,Z3｝，C2=｛Z6,Z7,Z8,Z9｝，C3=｛Z10,Z11｝，其它點(diǎn)為噪聲點(diǎn)。

圖3 DENCLUE 聚類分析結(jié)果Fig.3 Results of DENCLUE clustering algorithms

從圖（3）可以很清晰的看出最危險(xiǎn)路段在樁號(hào)為K20 附近，這與傳統(tǒng)的基于事故數(shù)指標(biāo)方法確定的最危險(xiǎn)路段一致，次之的危險(xiǎn)路段分別是K17-K18和K21-K22 這兩個(gè)路段。

4 結(jié)束語(yǔ)

從上述對(duì)基于 DENCLUE 聚類分析的事故多發(fā)點(diǎn)鑒別方法和傳統(tǒng)的基于事故數(shù)指標(biāo)方法實(shí)例分析中可以看出，當(dāng)事故樣本較少，各區(qū)間事故數(shù)基本相等時(shí)，利用傳統(tǒng)頻率直方圖難以準(zhǔn)確進(jìn)行事故多發(fā)點(diǎn)鑒別，容易遺漏道路危險(xiǎn)路段，而基于 DENCLUE聚類分析的事故多發(fā)點(diǎn)鑒別方法克服了上述缺點(diǎn)，可清晰地表征出道路中各路段危險(xiǎn)度等級(jí)的情況，并且實(shí)現(xiàn)了事故多發(fā)點(diǎn)長(zhǎng)度的任意性，體現(xiàn)了隨機(jī)提取效果，適合事故多發(fā)點(diǎn)的空間分布特征的研究。同時(shí)將道路沿線危險(xiǎn)性程度連續(xù)化，根據(jù)疊加后的局部密度函數(shù)極值大小的比較，實(shí)現(xiàn)不同是事故多發(fā)段的危險(xiǎn)性大小比較，克服了傳統(tǒng)頻率直方圖各區(qū)間危險(xiǎn)程度的分明邊界。

引入DENCLUE 聚類算法，考慮事故點(diǎn)對(duì)周圍一定范圍影響，有效的克服了目前事故多發(fā)點(diǎn)存在的問(wèn)題，避免了事先對(duì)路段進(jìn)行劃分實(shí)現(xiàn)任意道路多發(fā)點(diǎn)長(zhǎng)度的聚類；能實(shí)現(xiàn)在事故數(shù)據(jù)小樣本情況下，充分凸顯道路沿線的危險(xiǎn)性，可以有效地應(yīng)用于事故多發(fā)點(diǎn)鑒別的研究。DENCLUE 算法是以核估計(jì)理論為基礎(chǔ)，算法在網(wǎng)格邊長(zhǎng)及窗寬σ 選擇方面存在的不足會(huì)影響到最終結(jié)果，需要進(jìn)一步研究，需要采取優(yōu)化算法對(duì)其進(jìn)行完善。

[1]邵祖峰.交通事故黑點(diǎn)鑒別方法研究綜述[J].道路交通與安全，2008，8(2)：44-49.

[2]Geurts K.,Wets G.,Black spot analysis methods:literature review[R].Diepenbeek,Belgium:Flemish Research Center for Traffic Safety,2003.

[3]Geurts K.,Wets G.,Brijs T.and Vanhoof K.Profiling high frequency accident locations using association rules[C].In Proceedings of Transportation Research Board(CD-ROM),Washington,USA:Transportation Research Board,2003.

[4]Deacon J.A.,Zeeger C.V.and Deen R.C.Identification of hazardous rural highway locations[J].Transportation Research Record,1975,543:16-33.

[5]Saccomanno Frank,Fu Liping,Ren Congming and Miranda Luis.Identifying highway-railway grade crossing blackspots[M].Canada:Department of Civil Engineering University of Waterloo,2003:45-60.

[6]顏 峻，袁宏永，疏學(xué)明.社會(huì)安全事件空間分布研究[J].中國(guó)安全科學(xué)學(xué)報(bào).2008，18(7)：39-42.

[7]張志兵.空間數(shù)據(jù)挖掘關(guān)鍵技術(shù)研究[D].華中科技大學(xué)，2004.

[8]Sayed Tarck,Abdelwahab Walid,Navin Frank.Identifying accident-prone locations using fuzzy pattern recognition[J].Journal of Transportation Engineering,1996,121(4):352-353.

[9]Hinneburg D.A.Keim.An efficient approach to clustering in large multimedia databases withnoise[C].New York USA:Proc.1998 Int.Con f.Knowledge Discovery and Data Mining,1998.

[10]劉玉增.交通事故黑點(diǎn)的智能排查及整治對(duì)策的研究[D].成都：西南交通大學(xué)，2005.

[11]廖志高，柳本民，郭忠印.基于信息分配的道路黑點(diǎn)鑒別方法[J].中國(guó)公路學(xué)報(bào)，2007，20(4)：122-126.