基于DENCLUE 聚类算法的交通事故多发点鉴别方法

王鸿遥 孙 璐 游克思

1.烟台公路局，山东，烟台 264000

2.东南大学交通学院，南京 210096

3.美国华盛顿Catholic 大学，土木工程系，美国，华盛顿 20064

0 引 言

事故多发点是指在一定的时间内交通事故在道路沿线呈现积聚的空间分布状态。对事故多发点的合理诊断与改善能够有效地降低交通事故率，提高道路安全水平。

现有事故多发点鉴别方法的差别主要体现在不同的定量化判别指标[1-5]，常见的有基于事故数的绝对指标（如累计频率曲线法）；基于事故率的相对指标（如意大利方法，质量控制法等）；综合事故数-事故率方法（如矩阵法等）。

目前，这些方法在事故多发点的鉴别应用中主要表现在以下几个方面的不足：（1）需要事先对要排查的道路进行路段划分，这样容易将原本事故积聚的位置人为地分隔为两个或多个排查路段，导致事故多发点的遗漏，又不能很好地反映出事故多发点在道路上分布长度的任意性及对其进行排查的随机性。（2）单独考虑事故多发点，忽略其对周边环境危险性的影响。事实上事故的发生是由于发生点周边的道路交通环境与驾驶员等因素相互作用的结果。（3）项目级事故多发点的鉴别存在“小样本、长周期”的特点，采用传统的事故多发点鉴别方法容易遗漏事故多发点。

针对上述存在的问题，本文提出了一种基于DENCLUE 核密度聚类算法的事故多发点鉴别方法，算法中用影响函数来描述每个事故点对周围的影响；在多发点识别中反映实际道路事故密集区域，避免了事先对路段进行划分，同时还能实现任意道路多发点长度的聚类；能实现在小样本情况下，充分凸显道路沿线的危险性，可以有效地应用于事故多发点鉴别的研究。

本文首先介绍了 DENCLUE 聚类算法的基本思想、定义和计算步骤；然后分析该算法在事故多发点鉴别中的可行性；之后通过实例对比分析了DENCLUE 算法和传统事故多发点鉴别方法；最后总结并指出了该算法进一步的研究方向。

1 DENC LUE 聚类算法

DENCLUE 算法是一种泛化的基于核密度估计的聚类算法，其核心思想是每一个空间数据点通过影响函数事先对空间产生影响，影响值可以叠加，从而在空间形成一曲面，曲面的局部极大值点为一聚类吸引子，该吸引子的吸引域形成一类[6-9]。

1.1 基本定义

定义1 影响函数

式中，d(x,y)为点x 和点y 之间的广义距离（一般指欧氏距离）；ρ 为反映该点数据影响量，不同数据的影响量可能不完全相同；σ 为影响函数的窗宽，又称为辐射因子，反映了该点数据对周围影响能力，是个参量。

定义 2 密度函数给定数据集D 数据空间S 的任意一点P 的密度函数定义为，

定义3 梯度

定义4 密度吸引子和密度吸引 称x*∈S 为一密度吸引子，当且仅当x*是密度函数的一个局部极大值。x ∈S 被x*密度吸引，当且仅当 ∃k ∈N，d(xk,x*)≤ε。

定义5 中心聚类 对于密度吸引子x*，如果存在子集C ⊆D，使得 ∀x ∈C，x 都被x*密度吸引，且（ξ＞0 为预定义的密度门限值），则称S 为以x*为中心（关于ξ，σ 的）确定的聚类。

定义 6 噪声点 如果点x 被局部极大值点*x 密度吸引，但，则称x 为噪声点。

定义 7 任意形状聚类对于密度吸引子集合X如果存在子集C ⊆D，使得：（1）使得 ∀x ∈C，x 都被*x 密度吸引，且；（2）总存在从的路径P，满足 ∀y ∈P 有则称C 为由X 确定的关于ξ，σ 的任意形状聚类。

定义8 局部密度函数

1.2 算法步骤

Step 1 预聚类过程 初步确定高密度网格，对点数量大于一定值的高密度网格进行分析以加快运算速度。

（1）对空间数据D 以2 σ 为宽度进行网格划分，确定非空网格集Cp（只考虑非空网格），每个网格中数据数记为Nc；

（2）确定ξc，高密度网格

Step 2 聚类过程 对上述高密度网格以及与其相连的网格点构造密度函数，计算密度吸引子，最终确定聚类结果。

（1）确立局部计算区域

即只有高密度网格集以及与高密度网格相连接的网格用于聚类分析，其中h(cs,c)指聚类分析中的高密度网格 cs与网格c 相连接的函数。

（2）计算相连的高密度网格局部密度函数，以Gauss 函数为例，

式中，n(x)为点x 附近区域；m(c1)为网格c1的平均值；k 为正整数；h(c1,c)意思同上。

（3）根据局部密度函数，利用爬山法确定密度吸引子以及被密度吸引子所吸引的点集（将达到相同最大值的点归位一类）。

2 算法应用可行性分析

2.1 逻辑思想

基于核密度的 DENCLUE 算法通常用于处理高维海量数据的聚类分析，其核心思想是每一个空间数据点通过事先影响函数对空间产生影响，影响值可以叠加，从而在空间形成曲面，曲面的局部极大值点为密度吸引子，该吸引子的吸引域聚成一类。通过上面的分析，每个事故点对周围都有一定的影响，影响曲线近似认为正态分布曲线[9]，即数据点的影响函数为高斯函数。因此将DENCLUE 算法中所研究的点可以描述为事故发生的地点，维数是一维，即事故发生点位置；ξ 作为事故多发点的鉴别标准，当时，所聚类段位事故多发段，即多个事故点影响曲线综合叠加下的密度值大于预先的设定阈值ξ。因此，可以将DENCLUE 算法用于事故多发点排查具有一定的可行性。

用于事故多发点鉴别时，只考虑事故数的位置，即属于一维数据的聚类分析问题，建立标准影响函数采用高斯函数，

则局部密度函数为，

式中，K 值用于描述事故严重性的指标，与事故本身密切相关，事故越严重，所造成的损失越大，K 值也就越大。根据文献[10]，将几种事故严重程度之间的换算比值如下：轻微事故∶一般事故∶重大事故∶特大事故=0.5∶1∶2∶3。N 为计算局部区域内事故总数；σ 为计算的窗宽；xi为事故数据点的位置信息即桩号。

2.2 关键参数讨论

算法中有两个重要参数，窗宽σ 和密度限值ξ 对聚类结果有重要的影响，其中，如果ξ 值太大，聚类结果容易丢失低密度的聚类；反之，如果ξ 值太小，多个邻近的高密度聚类将被划分到一个聚类中，使得聚类结果缺乏可解释性。σ 的选取会影响全局密度函数的估计结果，当σ→∞时，所有数据被聚类为一个类；当σ→0 时，所有数据被聚类为N 类，每个数据点自成一类，显然无法发现所有的聚类。将DENCLUE 算法用于事故多发点鉴别中时，ξ 值实质就是事故多发点鉴别标准，关于事故多发点的鉴别标准有绝对标准和相对标准，绝对标准可以根据相关部分的规定，如公安部交通管理局《全面排查交通事故多发点段工作方案》中采用的鉴别方法标准。相对标准是根据实际道路事故发生情况，不同路段间危险程度的横向比较以及综合考虑改善资金的约束情况，最终确定鉴别的标准。

3 实例应用

3.1 事故数据[11]

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

2.教学资源建设与应用。课程设置方面，干部网络学习平台通常将课程分为必修课和选修课，学员需修够规定的学时，在教学内容学习完成后通过考试测验才能获得相应的学分。课程内容方面，平台大多依据《干部教育培训工作条例》将课程分类为党性修养、政治理论、业务知识、科学人文素养等，部分地方会适当增添地方特色内容。课程形式当面，课程主要以录制视频、直播、交互课件、图文资讯等形式呈现。

表1 事故统计资料Tab.1 Accident statistics

3.2 计算结果

（1）传统基于事故数指标方法

起点为K16+000 m,按1 km 步长等距离划分为8个单元，分别作每段的频率直方图，如图1 所示。可以看出区间Q2—Q6 由于事故数相等，因此不能鉴别出最危险集中段。

图1 事故频率直方图Fig.1 Accident frequency histogram

改变起始位置，从K16+100 m，以1 km 步长重新划分8 个路段，所作频率直方图如图2 所示。可以看出区间Q5K20+100—K21+100 为最危险段，长度固定1 km。

图2 改变起始位置时事故频率直方图Fig.2 Accident frequency histogram with changing original location of the road section

（2）DENCLUE 聚类算法

计算区间边长为1 km，高密度区间设置事故数量阈值为2 件，邻近区域，事故多发点鉴别标准采用相对标准，即根据实际道路事故发生情况，不同路段间危险程度的横向比较以及考虑改善资金的约束情况下采用0.6 作为阈值ξ；不考虑事故的严重程度，令K=1。计算结果如图3 所示。从图中可以直观看出沿线危险路段，聚类结果为C1=｛Z2,Z3｝，C2=｛Z6,Z7,Z8,Z9｝，C3=｛Z10,Z11｝，其它点为噪声点。

图3 DENCLUE 聚类分析结果Fig.3 Results of DENCLUE clustering algorithms

从图（3）可以很清晰的看出最危险路段在桩号为K20 附近，这与传统的基于事故数指标方法确定的最危险路段一致，次之的危险路段分别是K17-K18和K21-K22 这两个路段。

4 结束语

从上述对基于 DENCLUE 聚类分析的事故多发点鉴别方法和传统的基于事故数指标方法实例分析中可以看出，当事故样本较少，各区间事故数基本相等时，利用传统频率直方图难以准确进行事故多发点鉴别，容易遗漏道路危险路段，而基于 DENCLUE聚类分析的事故多发点鉴别方法克服了上述缺点，可清晰地表征出道路中各路段危险度等级的情况，并且实现了事故多发点长度的任意性，体现了随机提取效果，适合事故多发点的空间分布特征的研究。同时将道路沿线危险性程度连续化，根据叠加后的局部密度函数极值大小的比较，实现不同是事故多发段的危险性大小比较，克服了传统频率直方图各区间危险程度的分明边界。

引入DENCLUE 聚类算法，考虑事故点对周围一定范围影响，有效的克服了目前事故多发点存在的问题，避免了事先对路段进行划分实现任意道路多发点长度的聚类；能实现在事故数据小样本情况下，充分凸显道路沿线的危险性，可以有效地应用于事故多发点鉴别的研究。DENCLUE 算法是以核估计理论为基础，算法在网格边长及窗宽σ 选择方面存在的不足会影响到最终结果，需要进一步研究，需要采取优化算法对其进行完善。

[1]邵祖峰.交通事故黑点鉴别方法研究综述[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]颜 峻，袁宏永，疏学明.社会安全事件空间分布研究[J].中国安全科学学报.2008，18(7)：39-42.

[7]张志兵.空间数据挖掘关键技术研究[D].华中科技大学，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]刘玉增.交通事故黑点的智能排查及整治对策的研究[D].成都：西南交通大学，2005.

[11]廖志高，柳本民，郭忠印.基于信息分配的道路黑点鉴别方法[J].中国公路学报，2007，20(4)：122-126.