基于改進聚類算法的交通事故多發點識別方法

王藝霖　肖媛媛　左鵬飛　楊博　劉悅霞　段宗濤

摘 要：道路交通事故多發點事故發生頻率高且嚴重性突出，為提高道路通行的安全與效率，需要找到事故多發點所在位置。針對現有密度聚類算法對交通事故多發點識別時需要設置中心點個數以及容易擴大聚類范圍等問題，提出一種限制簇擴展的自適應搜索密度峰值聚類算法（limit cluster expansion and adaptive search clustering by fast search and find of density peaks，LA-CFDP）。LA-CFDP算法通過增加中心點限制條件自動確定中心點個數，引入參數擴展因子限制簇擴展范圍，從而提高算法對事故多發點識別的適應性和準確性。在英國四個城市2019年交通事故數據集上的實例分析表明，LA-CFDP算法對四個城市聚類結果的輪廓系數值達到0.72～0.92，DBI值均降低到0.37以下。聚類結果符合事故多發點的定義及特征，能夠為交通事故多發點治理提供可靠依據。

關鍵詞：交通事故分析； 數據挖掘； 密度聚類； 事故多發點識別

中圖分類號：TP391 文獻標志碼：A 文章編號：1001-3695（2023）10-017-2993-07

doi：10.19734/j.issn.1001-3695.2023.02.0086

Identifying method of traffic accident-prone spots based on

improved clustering algorithm

Wang Yilin， Xiao Yuanyuan， Zuo Pengfei， Yang Bo， Liu Yuexia， Duan Zongtao

（School of Information Engineering， Changan University， Xian 710018， China）

Abstract：Road traffic accidents occur frequently and seriously in the accident-prone spots. In order to improve the safety and efficiency of road traffic， it is necessary to find the location of accident-prone points. The existing density clustering algorithm needed to set the number of center points and was easy to expand the clustering range when identifying traffic accident-prone points， this paper proposed the limit cluster expansion and adaptive search clustering by fast search and find of density peaks（LA-CFDP） algorithm to solve these problems. LA-CFDP algorithm automatically determined the number of center points by increasing the restriction condition of center points， and introduced the parameter expansion factor to limit the cluster expansion range， so as to improve the adaptability and accuracy of the algorithm for accident-prone point identification. The case analysis on the 2019 traffic accident data set of four cities in United Kingdom shows that the Sihouette coefficient of the clustering results of LA-CFDP algorithm reaches 0.72～0.92， and the Davies-Bouldin index（DBI） are all reduced to below 0.37. The clustering results accord with the definition and characteristics of accident-prone spots， and can provide reliable basis for the management of accident-prone spots.

Key words：traffic accident analysis; data mining; density clustering; identification of accident-prone spot

0 引言

第16屆國際道路安全會議報告指出，事故多發點總長度占路網總長度的0.25%，發生在事故多發點的事故總數卻占整個路網事故總數的25%。交通事故多發點是指在一定時間段內發生交通事故相對聚集的點［1］，作為道路上交通事故相對集中的地方，事故多發點是交通事故防治的切入點。有效、準確地識別交通事故多發點是提高道路交通安全的一項關鍵而富有挑戰性的任務［2］。

交通事故多發點識別是交通事故防治的重要環節，是道路交通安全管理措施的可靠依據［3］。目前常用的事故多發點識別方法主要包括事故數量法、質量控制法、層次分析法、累計頻率法以及聚類方法等。事故數法和事故率法是最早提出的事故多發點識別方法。Wright等人［4］將事故數、死傷人數等綜合起來建立相對危險度模型，以此作為事故多發點的依據，但這種方法具有一定的局限性，只能表示危險程度，不能區分具體路段。質量控制法是運用概率論與數理統計確定事故多發點段的方法，Dereli等人［5］建立了一個基于模型的空間統計方法確定交通事故多發點，包括泊松回歸、負二項分布和經驗貝葉斯方法，通過比較得出經驗貝葉斯方法在準確性和一致性方面都有最好的結果；質量控制法雖然在實際操作中比較合理，但不能鑒別交通事故的嚴重性，也無法得到改善路段的順序［6］。孫元強［7］基于累計頻率曲線法分析不同路段單元劃分對識別精確度的影響，給出路段單元長度取值的合理建議，累計頻率法在識別事故多發點時具有一定的合理性，但該方法如果不能合理劃分單元，就容易漏掉一些事故多發點，雖然改進方法可以減少這種現象，但仍無法避免。層次分析法和模糊評價法也可以用于事故多發點的識別，張鵬［8］將模糊數學理論與層次分析法相結合對事故多發點進行安全評價，一定程度上實現了對高速公路的有效保護，但該方法計算復雜，對參數的確定主觀性較強。

對于應用聚類算法識別事故多發點，國內外學者也進行了很多研究。耿超等人［9］將累計頻率法與DBSCAN算法相結合，按照相鄰原則對道路進行動態劃分，并利用DBSCAN算法對事故多發點進行評價；王鴻遙等人［10］引入DENCLUE聚類算法來實現更高效的識別目的，該算法可以有效避免對識別位置的預分割，實現具有隨機形狀的簇的生成；曹陽等人［11］從空間聚類算法與GIS結合的角度分析發掘道路事故多發點問題，并對DBSCAN算法增加空間連通性判別，增強了算法的空間適用性；張云菲等人［12］考慮了事故周期性和交通事故嚴重程度，提供了一個基于空間密度聚類的高速公路事故多發路段識別方法，利用空間密度連接原理確定了不同空間維度的事故多發位置；Prasannakumar等人［13］借助地理信息技術研究事故多發點的定位和分布模式，根據空間自相關方法和核密度函數對事故進行空間聚類分析。本文基于現有密度聚類算法DBSCAN（density-based spatial clustering of applications with noise）［14］與快速搜索密度峰值聚類算法（clustering by fast search and find of density peaks，CFDP）［15］提出一種用于交通事故多發點識別的限制簇擴展的自適應搜索密度峰值聚類算法（LA-CFDP）。研究表明，DBSCAN算法在對交通事故數據聚類時容易擴大事故多發點范圍，不符合事故多發點定義，CFDP算法在中心點選取時需要根據決策圖人為指定簇數，而在事故多發點識別中簇數無法提前獲取，導致聚類效果不佳。因此，針對現有算法在中心點選取、簇擴展方式中存在的問題，通過自適應中心點選取、限制簇擴展范圍改進算法。實驗結果表明，LA-CFDP算法各項指標都高于現有算法，對不同分布的事故數據具有很好的適應性，能夠有效識別事故多發點。

1 密度聚類算法

1.1 DBSCAN算法

DBSCAN算法是一種經典的基于密度的聚類算法，通過尋找數據點密度相連的最大集合得到聚類的結果。

1.1.1 基本定義

給定數據集D={x1，x2，…，xn}，距離半徑ε，點數閾值MinPts，其中ε和MinPts為用戶指定參數，有如下定義：

定義1 ε鄰域。對xp∈D，若xp的ε鄰域表示為Nε（xp），則Nε（xp）={xi∈D|dist（xi，xp）≤ε}，即數據集D中滿足到xp的距離小于ε的任意樣本點xi的集合。

定義2 核心對象。對xp∈D，若xp的ε鄰域內的點的個數大于MinPts，即|Nε（xp）|≥MinPts，那么xp是一個核心對象。

定義3 直接密度可達。對xp，xq∈D，若xq在xp的ε鄰域內且xp為核心對象，則稱xq由xp直接密度可達。

定義4 密度可達。對xp，xq∈D，若有樣本p1，p2，…，pn1∈D，其中p1=xp，pn1=xq且pi+1由pi直接密度可達，那么稱xq由xp密度可達。

定義5 密度相連。對xp，xq∈D，若有xk∈D使得xp、xq均由xk密度可達，則xp與xq密度相連。

1.1.2 算法描述

輸入：數據集D={x1，x2，…，xn}，距離半徑ε，點數閾值MinPts。

a）掃描數據集，從中任意找到一個核心對象；

b）對該核心對象進行擴展，尋找從該核心點出發的所有密度相連的數據點；

c）遍歷該核心對象ε鄰域內的全部核心點，找到與這些核心點密度相連的點，直到無法擴充；

d）重新掃描數據集，尋找仍未聚類的核心對象，重復上述步驟，擴充該核心對象，直到沒有滿足條件的核心對象為止；

e）截至目前未被劃分到簇中的點即為噪聲點；

f）輸出簇劃分結果。

1.2 快速搜索密度峰值聚類算法

CFDP算法結合密度聚類和劃分聚類的方法，通過密度和距離來確定聚類中心，再用劃分方法對非聚類中心進行分配，得到聚類結果［16］。CFDP聚類算法的核心是確定聚類中心，聚類中心應當符合高密度和遠距離兩個條件。具體來說，高密度是指該點周圍的數據點數量越多，密度越高；遠距離是指該點到密度更高的點的距離越遠，越有可能成為聚類中心［17］。

1.2.1 基本定義

定義6 局部密度ρ。ρ表示點周圍所處區域的樣本點分布的密集程度，一般有兩種方式來表示局部密度，截斷核密度和高斯核密度，截斷核密度的定義為

其中：trB（k）表示簇間平方誤差和;trW（k）表示簇內誤差平方和。CH指標越大，表示聚類效果越好。

2 限制簇擴展的自適應搜索密度峰值聚類算法

DBSCAN和CFDP算法是兩種常用的基于密度的聚類算法，然而傳統聚類算法對交通事故多發點的識別存在問題。

DBSCAN算法應用在交通事故多發點識別時，其參數鄰域半徑ε和點數閾值MinPts恰好符合交通事故多發點對范圍及最少事故數的定義，并且能夠識別任意形狀和大小的簇，對噪聲數據具有較好的魯棒性；但是DBSCAN算法在事故多發點識別過程中也存在一定的問題：a）DBSCAN算法在簇擴展過程中將所有密度相連的點都聚為一類，這種簇擴展方式會擴大事故多發點的范圍，偏離事故多發點定義，影響交通事故多發點識別的精確性；b）DBSCAN算法通過遍歷數據集判斷是否為核心點，然后擴展該核心點，這種先來者原則在處理簇的跨界點時會使一些跨界點不屬于最佳簇［18］，在識別事故多發點時可能將高密度區域劃分為兩個不同的簇。

CFDP算法對交通事故多發點識別的適應性主要在于其中心點選擇與剩余點分配方式，算法選擇密度大且距離其他密度大的點較遠的點作為聚類中心點，避免將高密度區域分開，剩余點分配到距離其最近的密度大于自己的中心點所在簇，很好地解決了邊界點的分配問題［19］。交通事故多發點的識別需要在事故多發點定義范圍內找到高密度區域，CFDP算法符合這一要求。CFDP算法應用在事故多發點識別中存在的問題包括：a）CFDP算法在聚類過程中需要根據截斷距離選擇簇的個數，而在交通事故多發點識別中，難以預先設定事故多發點的個數；b）在識別事故多發點時，事故多發點定義之外的事故數據點應該被標記為噪聲點，而CFDP算法對噪聲的識別不夠敏感，剩余點分配過程中會將其余點分配到距離其最近的中心點。

本文結合DBSCAN與CFDP算法在交通事故識別中的優勢，針對兩種算法的局限性，分別從中心點選擇與簇擴展方式兩個方面進行改進以提升交通事故多發點的識別效果。

2.1 基本定義

給定數據集、距離半徑ε、點數閾值MinPts、擴展因子exp，其中ε和MinPts為用戶指定參數，exp為實驗得出，有如下定義：

定義9 ε鄰域。同定義1。

定義10 擴展因子exp。控制簇擴展范圍大小的因素，可以根據實際情況設定，也可根據實驗得出最優取值。

定義11 擴展半徑expradio。表示核心對象ε鄰域內的點擴展的范圍，如式（7）所示。

2.2 中心點選擇

DBSCAN算法在選擇核心點時通過遍歷數據集判斷是否為核心點，若是核心點，則將該點鄰域內的樣本集合以及與其密度相連的所有點劃分為一個簇，這種方式在處理多個簇的跨界點時會使一些跨界點不屬于最佳簇。CFDP算法通過設置截斷距離，根據決策圖人工設置簇數，但在事故多發點聚類中，簇數無法提前獲取，且CFDP算法不能識別噪聲點，會將所有點分配到距離最近的中心點所在的簇［20］。

LA-CFDP算法從參數設置方面限制中心點的選擇，事故多發點聚類理想的中心點是密度大、與距離其他密度大的點距離相對遠的點，并且密度要大于閾值（ε鄰域半徑內MinPts以上的點）。所以對中心點的選取增加限制條件——密度必須大于MinPts/ε。此外，CFDP算法是先確定中心點個數再進行聚類，事故多發點聚類時難以確定聚類個數，所以選擇中心點和聚類同時進行。中心點選擇條件為滿足ρ>MinPts/ε 的點的ρ×δ 取值從大到小降序排列，從中不斷取出點聚類，直到遍歷完所有點。

2.3 簇擴展方式

如果不對簇進行擴展，可能會使距離相近的兩個點被分到不同簇中，或有些點被認為是噪聲點；如果按照DBSCAN算法中簇擴展方式，所有密度相連的點都會被聚為一類，擴大了事故多發點范圍，不符合事故多發點的定義。因此需要設置一個參數限制簇擴展的范圍，在合理范圍內對簇進行擴展，從而在滿足現實定義的情況下得到更好的聚類效果。簇擴展改進方式主要是限制簇擴展的范圍，距離核心點越近的數據點擴展范圍越大，越遠的點擴展范圍越小。簇擴展方式的改進使用式（4），其中exp為人為指定，數值的選取通過繪圖觀察各聚類效果評價指標來判定，或根據實際情況設定。

2.4 算法流程

給定數據集D={x1，x2，…，xn}，使用LA-CFDP算法進行聚類的過程如下：a）根據距離計算公式計算數據集的距離矩陣；b）根據數據集的距離矩陣和參數ε與MinPts計算所有數據點的密度ρi、最小距離δi以及每個數據點的上級；c）將ρi×δi的大小降序排列，選擇其中最大值作為類簇中心（cluster center），標記為一個簇；d）遍歷每一個數據點，將上級是當前中心點且與當前中心點距離小于鄰域半徑ε的點標記為當前簇；e）簇擴展，遍歷簇內點，按照式（4）擴展簇，將擴展后的點標記為該簇；f）選擇下一個ρi×δi最大的點作為下一個中心點，重復步驟c～f），直到所有點都被標記；g）遍歷所有簇，將簇中點數小于MinPts的簇的所有點都標記為噪聲點，聚類完成。

2.5 算法主要函數偽代碼

1）聚類過程偽代碼

輸入：數據集D={x1，x2，…，xn}，中心點集合centers，上級nearest_neiber，鄰域半徑ε，點數閾值MinPts，擴展半徑exp。

輸出：簇劃分結果，即xi∈D，cluster（xp）。

初始化簇標號k=0，對xi∈D，訪問標記visited（xi）=0（0代表未訪問，1代表已訪問）；

for center∈centers，visited（center）=0

k=k+1;

將center標記為中心點，visited（center=1），cluster（center）=k;

for xj∈D，xjcenters

if visited（xj）=0，nearest_neiber（xj）=center，deltas（xj）<ε

cluster（xj）=k，visited（xj）=1;

cluster_expand（all_points，xj，ε，exp，k）；

end if

end for

end for

重復運行以上步驟，直到滿足xi∈D，visited（xi）=1。

2）簇擴展函數偽代碼

計算當前點擴展半徑exp_radio=（ε-dists［：xj］）*exp；

for xk∈D，xkcenters

if visited（xk）=0，dists［：xj］<=exp_radio

visited（xk）=1；

cluster（xk）=k；

end if

end for

3 算法應用與結果分析

本文中聚類算法所使用的實驗環境：系統為Windows 10，處理器為Intel CoreTM i7-6700 CPU@3.40 GHz，內存為16 GB，算法基于Python 3.8實現。

實驗使用英國2019年交通事故數據集，選擇事故數據分布的不同城市來分析對于不同分布數據各算法的適應性。選取city1威斯敏斯特（Westminster）、city8南華克（Southwark）、city300伯明翰（Birmingham）和city390劍橋（Cambridge）這四個城市的交通事故數據進行實驗。首先對數據進行預處理，篩除有空白字段以及沒有標明具體位置的數據，預處理后剩余事故數據情況如表1所示。

英國對道路交通事故多發點段及地區的定義是：0.1 km2范圍內，1年發生超過4次交通事故的地區叫做危險點;0.3 km長的路段，3年發生超過12次交通事故的地區稱為事故多發路段;1 km2范圍內，1年發生超過40次交通事故的地方稱為事故多發地區。本文選擇事故多發點的定義作為標準，對事故數據進行聚類。

3.1 DBSCAN算法事故數據聚類

使用DBSCAN算法對四個城市的事故數據city1、city8、city-300、city390進行聚類。DBSCAN算法需要指定鄰域半徑ε和點數閾值MinPts這兩個參數，同時還需要根據實驗需求選擇合適的距離度量方式。

a）距離度量方式。聚類算法常用的距離度量方式為歐氏距離，在交通事故多發點識別時，使用的是經緯度數據，距離是實際地理位置之間的距離，因此在實驗過程中采用半正矢公式，將經緯度距離轉換為兩點之間的距離來替換歐氏距離，便于對參數的設置。

b）鄰域半徑ε。參考英國交通事故多發點定義，“0.1 km2范圍內”表示距離范圍，DBSCAN算法中鄰域半徑ε為圓的半徑，因此將0.1 km2范圍轉換為圓的面積，根據公式S=πr2將0.1 km2范圍轉換為圓的面積得到r=178 m，因此將鄰域半徑ε設置為178。

c）點數閾值MinPts。參考英國交通事故多發點定義，“1年發生超過4次交通事故”表示交通事故多發點最少包含的事故數量，因此將點數閾值MinPts設置為4。

圖1為四個城市聚類結果圖，圖中每種顏色和形狀分別代表一個聚類簇，黑色點表示噪聲點（參見電子版）。表2為四個城市聚類效果評價指標，列出簇數、輪廓系數、CHI、DBI四個值驗證實驗效果。從圖1和表2所示結果以及各城市事故數據分布特點可以看出，DBSCAN算法對city300和city390這樣分布較為分散、密度相連的數據點較少的數據集聚類效果較好，輪廓系數能達到0.5以上，DBI值降低到0.5以下，CHI也明顯高于其他兩個城市;而對于city1和city8這樣數據分布較密集且大量數據點密度相連的數據集而言，DBSCAN算法的聚類效果很差，輪廓系數為負值，DBI接近1，說明聚類結果不合理，將不應該在同一個簇中的點劃分到一個簇中，或將本該劃分在一個簇中的點分開。

DBSCAN算法在簇擴展時，容易將密度相連的大多數數據點聚為一個簇，如圖1（a）中紅色方塊部分以及圖1（b）中粉色圓部分，大面積的數據點被聚類為同一個簇，這樣會降低聚類準確率。事故多發點是指一定時間、一定距離范圍內發生事故數量的累計程度，大范圍的擴展使結果背離事故多發點的定義。

在實際應用中，DBSCAN算法的重點在于尋找密度相連的最大集合，而交通事故多發點識別的重點在于指定范圍內精準尋找事故多發點的位置。由于DBSCAN算法在數據點密度相連的情況下會不斷擴大簇的范圍，其在事故多發點識別中存在一定的局限性，在識別事故多發點時范圍不應該被無限擴大，所以應用DBSCAN算法進行交通事故多發點識別時，需要對DBSCAN算法的簇擴展方式進行一定的改進和優化。

3.2 CFDP算法事故數據聚類

使用CFDP算法對四個城市的事故數據city1、city8、city-300、city390進行聚類。CFDP算法的參數包括截斷距離以及根據決策圖選定的簇數。

a）距離度量方式。同DBSCAN算法距離度量方式。

b）截斷距離dc。CFDP算法中數據點密度為與樣本點i的距離小于截斷距離dc的點的數量，截斷距離與DBSCAN算法中鄰域半徑ε含義相近，因此將截斷距離dc設置為178，與DBSCAN算法鄰域半徑ε設置原理類似。

c）簇數。CFDP算法在運算過程中需要由用戶根據決策圖及實際情況來指定簇的個數，對于這幾個城市的事故數據，使用輪廓系數、CHI以及DBI三個聚類評價指標，根據指標大小選擇最優簇數，選擇使兩個指標最優的簇數作為CFDP算法聚類簇數。

根據DBSCAN算法聚類結果，簇數范圍應當在200以內，因此設定初始簇數區間為［0，200］，通過實驗觀察指標變化趨勢，選擇指標最大的范圍縮小簇數區間，得到四個城市的簇數最佳區間分別為［25，30］，［30，35］，［190，200］，［75，80］。圖2為四個城市事故數據簇數最佳區間內指標變化圖，在這個區間內選擇使評價指標最優的參數。觀察圖中曲線趨勢，可得簇數設置為表3中列出的數據時，聚類效果最好。

使用CFDP算法對四個城市的事故數據集進行聚類，用表3中的簇數作為聚類簇數，聚類結果如圖3所示。圖中每種顏色和形狀分別代表一個聚類簇（參見電子版），“+”表示聚類中心。表4為各個城市聚類結果評價指標。

實驗結果表明，CFDP算法對幾個城市數據聚類結果相似，輪廓系數在0.3～0.4，DBI超過0.65時聚類效果較差。實際應用中，CFDP算法在對交通事故數據進行聚類時需要指定簇的個數，而對于交通事故多發點來說，簇的個數難以提前設定。此外，CFDP算法在為聚類中心分配剩余點時，將每個點分配到距離最近的中心點所在簇，沒有考慮到該點與中心點間的距離，不符合事故多發點的定義。

3.3 LA-CFDP算法事故數據聚類

使用LA-CFDP算法對四個城市的事故數據city1、city8、city300、city390進行聚類。LA-CFDP算法需要設置鄰域半徑ε和點數閾值MinPts兩個參數，同時還需要根據聚類效果評價指標設置擴展因子值。

a）距離度量方式。同DBSCAN算法距離度量方式。

b）鄰域半徑ε和點數閾值MinPts。同DBSCAN算法。

c）擴展因子。擴展半徑表示核心對象ε鄰域內的點擴展的范圍，擴展因子用來限制簇的擴展，使簇在一定范圍內擴展，距離中心點越近的點擴展范圍越大，反之越小，如式（7）所示。擴展因子的設置可以依據實際值，也可以根據聚類效果選擇使聚類效果達到最好的值作為擴展因子。本文根據三個聚類評價指標值來設置，將擴展因子設置為使聚類效果評價指標中兩個以上達到最優的值。

首先，將初始擴展因子范圍設置為［0，2］，通過實驗觀察指標輪廓系數、CHI、DBI的變化趨勢，選擇指標最大的范圍縮小擴展因子區間，得到city1、city8、city300、city390的擴展因子最佳區間分別為［0，0.5］，［0.15，0.25］，［0.1，0.4］，［0.1，0.4］。圖4為四個城市事故數據擴展因子最佳區間內指標變化圖，在這個區間內選擇使評價指標最優的參數，由此得到擴展因子最優取值，當擴展因子取值如表5所示時聚類效果最好。

設置擴展因子后對事故數據進行聚類，得到如圖5所示的聚類圖。圖中灰色點為噪聲點，其余每種顏色與形狀表示一個事故簇（參見電子版）。從聚類結果圖可以看出，LA-CFDP算法避免了將大部分數據歸為一類，能夠有效根據定義識別交通事故多發點，同時能從事故數據中識別出噪聲數據，避免噪聲點對實驗結果的影響，提高事故多發點識別的準確性。

表6為LA-CFDP算法聚類效果評價指標，在四個數據集上，LA-CFDP算法都得到較好的實驗結果，各項指標明顯提高。

表7列出了DBSCAN、CFDP以及LA-CFDP算法的實驗結果對比，從對比結果可以看出，相比DBSCAN算法，LA-CFDP算法的輪廓系數增長了48%以上，CHI值增長了4.6倍以上，DBI值至少降低了55%，且對于DBSCAN算法聚類效果較差的城市如city1，輪廓系數值由-0.31增長到0.73，CHI值提高了62倍，DBI值降低了63%。輪廓系數、CHI、DBI都是通過樣本點與聚類中心之間的距離來衡量聚類結果的優劣，DBSCAN算法在簇擴展過程中擴大了簇的范圍，同時擴大了簇內各樣本點與聚類中心之間的距離，導致評價指標較低；而LA-CFDP算法限制簇的擴展范圍，增加了簇的凝聚度，從而提高了評價指標值。此外，簇擴展范圍的限制也滿足交通事故多發點的定義，LA-CFDP算法有效提高了交通事故多發點識別結果的準確性。相比CFDP算法，LA-CFDP算法的輪廓系數增長了1.3倍以上，CHI值增長了1.9倍以上，最高增長了11.4倍，DBI值至少降低了129%，最高達378%。CFDP算法在剩余點分配時沒有限制中心點與剩余點之間的距離，致使評價指標較低，而LA-CFDP算法限制了分配距離，有效識別出噪聲點，提高了評價指標值。在交通事故多發點識別中，簇內的點應當符合交通事故多發點定義范圍，其余點則被識別為噪聲點，因此對剩余點分配的改進同樣適用于交通事故多發點的識別，同時LA-CFDP算法無須設定簇的個數，對交通事故多發點識別具有很好的適用性。

3.4 交通事故多發點應用分析

將聚類結果可視化在地圖上（圖6）可以看出，交通事故多發點位置大多位于交叉口、十字路口等位置。通過分析事故數據其余字段驗證聚類結果（表8）可以得出，在聚類得到的事故多發點中，位于道路特殊位置的簇數占總簇數的70%以上，道路特殊位置包括交叉口、十字路口、環島、T型交錯口等特殊交通位置，說明聚類結果與現實情況相符，證明了LA-CFDP算法識別交通事故多發點段的合理性。

識別出交通事故多發點之后，可以結合事故數據其他字段對交通事故多發點的原因進行深入分析，包括道路設計不合理、交通信號不暢、駕駛員行為不當等方面，找出事故發生的主要原因，交管部門根據這些原因可以制定相應的解決方案，包括加強交通信號的設置、完善道路設計、加強對駕駛員的監管等；還可以基于歷史交通事故數據和交通狀態數據，結合交通事故多發點位置建立交通事故多發點預測模型，為交通管理提供科學依據。

4 結束語

本文提出了一種適用于交通事故多發點識別的聚類算法，將DBSCAN算法的參數及簇擴展思想引入到CFDP算法中，使CFDP算法能夠自適應確定簇數。LA-CFDP算法的參數對應交通事故多發點的定義，具有很好的適用性。本文實例使用英國交通事故數據集，分別用DBSCAN、CFDP以及LA-CFDP算法對英國四個城市的事故數據進行聚類，并且使用輪廓系數、CHI、DBI三個評價指標來評價各算法的實驗結果，結果表明，LA-CFDP算法可以克服DBSCAN和CFDP算法存在的局限性，在對不同分布的交通事故數據進行聚類時有很好的聚類效果。分析實驗結果與事故數據其他字段可以得出聚類得到事故易發位置大多位于道路上交通狀況較為復雜的位置，確定事故多發點后可以利用多發點其他字段信息進行不同角度的分析。本研究后續將聚焦事故多發點事故多發原因分析，使用事故數據其他字段信息，結合數據挖掘、機器學習與深度學習方法，全面挖掘事故數據，從中發現事故多發的原因，為交通事故多發點治理提供科學依據。

參考文獻：

[1]Aziz S， Ram S. A meta-analysis of the methodologies practiced worldwide for the identification of road accident black spots［J］.Transportation Research Procedia，2022，62：790-797.

［2]Wang Dianhai， Huang Yulang， Cai Zhengyi. A two-phase clustering approach for traffic accident black spots identification： integrated GIS-based processing and HDBSCAN model［J］.International Journal of Injury Control and Safety Promotion，2023，30（2）：270-281.

［3]Cui Hongjun， Dong Jianguo， Zhu Minqing， et al. Identifying accident black spots based on the accident spacing distribution［J］.Journal of Traffic and Transportation Engineering，2022，9（6）：1017-1026.

［4]Wright C C， Abbess C R， Jarrett D F. Estimating the regression-to-mean effect associated with road accident black spot treatment： towards a more realistic approach［J］.Accident Analysis & Prevention，1988，20（3）：199-214.

［5]Dereli M A， Erdogan S. A new model for determining the traffic accident black spots using GIS-aided spatial statistical methods［J］.Transportation Research Part A：Policy and Practice，2017，103（9）：106-117.

［6]顏茜，吳志敏，李明國.高速公路事故多發路段的鑒別及成因分析［J］.廣東公路交通，2018，44（5）：28-30，53.（Yan Qian， Wu Zhimin， Li Mingguo. Identification and cause analysis on expressway accident-prone sections［J］.Guangdong Highway Communications，2018，44（5）：28-30，53.）

［7]孫元強.基于改進累計頻率曲線法的交通事故黑點鑒別及智能識別平臺構建［D］.西安：長安大學，2021.（Sun Yuanqiang. Identification of black spots in traffic accidents based on improved cumulative frequency curve method and intelligent recognition platform construction［D］.Xian：Changan University，2021.）

［8]張鵬.基于模糊層次分析法的某高速公路事故多發路段安全性綜合評價［J］.黑龍江交通科技，2021，44（7）：199-200.（Zhang Peng. Comprehensive safety evaluation of accident-prone section of a freeway based on fuzzy analytic hierarchy process［J］.Communications Science and Technology Heilongjiang，2021，44（7）：199-200.）

［9]耿超，彭余華.基于動態分段和DBSCAN算法的交通事故黑點路段鑒別方法［J］.長安大學學報：自然科學版，2018，38（5）：131-138.（Geng Chao， Peng Yuhua. Identification method of traffic accident black spots based on dynamic segmentation and DBSCAN algorithm［J］.Journal of Chang an University：Natural Science Edition，2018，38（5）：131-138.）

［10]王鴻遙，孫璐，游克思.基于DENCLUE聚類算法的交通事故多發點鑒別方法［J］.交通運輸工程與信息學報，2013，11（2）：5-10.（Wang Hongyao， Sun Lu， You Kesi. Accident-prone location identification method based on DENCLUE clustering algorithm［J］.Journal of Transportation Engineering and Information，2013，11（2）：5-10.）

［11]曹陽，陳天滋，柴勇.基于GIS的道路事故黑點聚類應用研究［J］.微計算機信息，2006，22（31）：253-255.（Cao Yang， Chen Tianzi， Chai Yong. Study on application of clustering in highway accident spot based on GIS［J］.Microcomputer Information，2006，22（31）：253-255.）

［12]張云菲，張澤旭，朱芳琪.利用時空密度聚類的高速公路交通事故黑點路段鑒別［J］.測繪通報，2022（10）：73-79.（Zhang Yunfei， Zhang Zexu， Zhu Fangqi. Identification of highway accident black spots based on spatio-temporal density clustering［J］.Bulletin of Surveying and Mapping，2022（10）：73-79.）

［13]Prasannakumar V， Vijith H， Charutha R， et al. Spatio-temporal clustering of road accidents：GIS based analysis and assessment［J］.Procedia-Social and Behavioral Sciences，2011，21（2）：317-325.

［14]Ester M， Kriegel H P， Sander J， et al. A density-based algorithm for discovering clusters in large spatial databases with noise［C］//Proc of the 2nd International Conference on Knowledge Discovery and Data Mining.Palo Alto，CA：AAAI Press，1996：226-231.

［15]Rodriguez A， Laio A. Machine learning： clustering by fast search and find of density peaks［J］.Science，2014，344（6191）：1492-1496.

［16]Guan Junyi， Li Sheng， He Xiongxiong， et al. Clustering by fast detection of main density peaks within a peak digraph［J］.Information Sciences，2023，628（5）：504-521.

［17]黃學雨，向馳，陶濤.基于MapReduce和改進密度峰值的劃分聚類算法［J］.計算機應用研究，2021，38（10）：2988-2993，3024.（Huang Xueyu， Xiang Chi， Tao Tao. Partition clustering algorithm based on MapReduce and improved density peak［J］.Application Research of Computers，2021，38（10）：2988-2993，3024.）

［18]Zhang Runfa. An adjusting strategy after DBSCAN［J］.IFAC-Papers OnLine，2022，55（3）：219-222.

［19]王森，邢帥杰，劉琛.密度峰值聚類算法研究綜述［J］.華東交通大學學報，2023，40（1）：106-116.（Wang Sen， Xing Shuaijie， Liu Chen. Survey of density peak clustering algorithm［J］.Journal of East China Jiaotong University，2023，40（1）：106-116.）

［20]劉美，王全民.基于密度可達的密度峰值聚類算法［J］.計算機仿真，2022，39（11）：371-375.（Liu Mei， Wang Quanmin. Density peak clustering algorithm based on density reachable［J］.Computer Simulation，2022，39（11）：371-375.）

收稿日期：2023-02-24；修回日期：2023-04-28

基金項目：陜西省特支計劃科技創新領軍人才資助項目（TZ0336）

作者簡介：王藝霖（1999-），女（通信作者），山西太原人，碩士研究生，CCF會員，主要研究方向為數據挖掘、交通事故分析（wylin@chd.edu.cn）；肖媛媛（1997-），女，陜西西安人，博士研究生，主要研究方向為機器學習、數據挖掘；左鵬飛（1997-），女，山西大同人，碩士研究生，主要研究方向為機器學習；楊博（1999-），男，山西運城人，碩士研究生，主要研究方向為機器學習、數據挖掘；劉悅霞（1999-），女，山西臨汾人，碩士研究生，主要研究方向為數據挖掘；段宗濤（1977-），男，陜西鳳翔人，教授，博導，博士，CCF會員，主要研究方向為大數據智能、交通大數據分析.