基于改进聚类算法的交通事故多发点识别方法

王艺霖　肖媛媛　左鹏飞　杨博　刘悦霞　段宗涛

摘 要：道路交通事故多发点事故发生频率高且严重性突出，为提高道路通行的安全与效率，需要找到事故多发点所在位置。针对现有密度聚类算法对交通事故多发点识别时需要设置中心点个数以及容易扩大聚类范围等问题，提出一种限制簇扩展的自适应搜索密度峰值聚类算法（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会员，主要研究方向为大数据智能、交通大数据分析.