基于距离度量学习的交通警情等级预测方法

摘要

一种基于距离度量学习的交通警情等级预测方法，对已知天气数据、时间数据、环境数据等情况下的城市交通警情等级进行预测，将整理好的多维历史数据根据交警指挥部门要求进行分类，利用广义马氏距离度量方法对分类标记后的多维历史数据进行学习，则距离度量学习矩阵获得了各个特征属性对交通警情等级的权值，权值大的特征属性对分类贡献度大，根据带权值的欧氏距离计算当前的多维数据与历史数据的相似度，选择与当前数据最相似的K个历史数据进行警情等级投票，得票高的警情等级作为当前交通警情等级的预测结果。本发明有效实现预测、准确性较好。

说明书

技术领域

本发明属于智能交通领域，具体涉及一种城市交通警情等级预测方法。

背景技术

随着经济的迅速发展，城市交通系统中机动车保有量的快速增长导致发生交 通事故、交通拥堵的概率大大增加，当前城市交通状态发布和诱导都是针对单个 路段、局部区域，主要面对道路上的机动车驾驶者，对于交通管理人员更希望获 得宏观区域的交通警情等级，对未来某个时间段内的区域警情等级进行有效的预 测有助于交通管理部门优化警力部署、制定相应的预案，缓解重点地区的交通压 力。

专利201410610003.7采集包含工作日、非工作日且包含重大节假日交通流数 据，将相同连续时间段交通流数据重组为自然数，建立短时交通流数据库，将当 前交通流重组数据与短时交通流数据库中历史数据进行大小比对，截取相似样本 空间，利用偏差最小的两个样本进行预测，该方法仅侧重于考虑时间因素对交通 流数据的影响，没有引入天气因素且未揭示各个特征属性之间的内在联系；专利 200510113396.1通过观测交通流量和动态，以及诸如一天中的时间和一周中的日 子、假期、学校状况、诸如体育比赛等大型集会的时间安排和性质、天气预报、 交通事件报告、和建设与封路等其它环境数据，预测拥塞地点并用于离线和实时 的自动路线推荐和计划，该方法将交通系统抽象成一组随机变量来进行关于交通 流量和拥塞的预报，仅对交通参与者有效，不能对交通管理者提供决策支持。本 专利与上述专利有本质不同，数据来源方面综合考虑天气因素、时间因素、环境 因素等对城市交通警情等级的影响，并通过广义马氏度量学习方法提取各个特征 属性的权值，充分揭示各个属性对交通警情等级影响的重要程度，根据学习的特 征属性权值对交通警情等级进行预测。

发明内容

为了克服已有交通警情判别方式的无预测功能、准确性较差的不足,本发明提 供了一种有效实现预测、准确性较好的基于距离度量学习的交通警情等级预测方 法。

本发明解决其技术问题所采用的技术方案是：

一种基于距离度量学习的交通警情等级预测方法，包括以下步骤：

步骤1：多维数据整理和交通警情等级分类

采集历史天气数据、历史重大活动数据、建设和封路环境数据与工作日、节 假日和历史交通警情数共同构成关于交通警情的多维历史数据库，当前时刻的交 通流量和上一时刻的流量密切相关，将连续的历史交通警情数据按照等时间段切 分为n个片段作为训练样本，每个训练样本片段包括天气属性、重大活动属性、 环境因素属性、工作日和节假日属性，根据交通管理部门提供的交通警情阈值对 n个训练样本进行交通警情等级分类；

步骤2：距离度量学习提取分类后的交通警情样本所对应的多维特征属性权值

根据步骤1得出n个已标记训练样本构成的一个样本空间，该样本空间中各 个元素之间的距离称为度量，其中距离是定义在向量空间中的一种函数，指两个 元素在空间中相隔的长度，也就是说可以将某个空间中的所有对象投影到一个新 的度量空间中；选取n个训练样本构成包含多维特征属性的样本空间X，其中 X＝(x₁,x₂,x₃,…,x_n)，x_i对应第i个样本代表的多维特征属性，式(1)是样本空间X 中x_i和x_j样本点间的马氏距离，其中矩阵A是我们需要学习的距离度量矩阵，矩 阵A中的每一行代表一个历史样本，每一列对应样本中的一维特征属性

$d_m(x_i,x_j)=d_A(x_i,x_j)={\left|\right|x_i-x_j\left|\right|}_A=\sqrt{{(x_i-x_j)}^{T}A(x_i-x_j)}---\left(1\right)$

式(1)中的A是样本空间X的协方差矩阵，样本空间X中的每个样本均带有 交通警情等级标签，故在最小化相同警情等级S(S∈X)中样本之间的马氏距离平 方和的同时，约束不同警情等级D(D∈X)中样本之间的马氏距离和，马氏距离 和大于预设阈值，目标函数模型如式(2)，式(3)所示：

$s.t.\underset{(x_i,x_j)\in D}{\Sigma }{d}_A(x_i,x_j)\ge 1---\left(3\right)$

其中，表示A为半正定矩阵，由目标函数模型求取距离度量学习矩阵A的 过程是一个凸优化问题，采用牛顿法对上述凸优化问题进行求解，最终学习到的 距离度量矩阵为一个稀疏的对角阵；

步骤3：带权值的欧氏距离寻找与当前特征属性最相似的K个历史交通警情

使用欧氏距离计算K近邻需首先对各个特征属性进行归一化，假定样本空间 X中的样本点x包含k维特征属性，样本点之间的近邻一般由欧氏距离来度量， 设第i个样本点为其中表示第i个样本第l个特征属性值， 两个样本x_i和x_j之间的欧氏距离定义为公式(4)：

$d_o(x_i,x_j)=\sqrt{\underset{l=1}{\overset{k}{\Sigma }}{(x_l^i-x_l^j)}^2}---\left(4\right)$

给定一个待预测的交通警情样本x_q，由标准欧氏距离可计算出样本x_q与历史样本 空间中最近邻的K个样本x₁,x₂,…,x_K，样本之间的距离是根据样本的所有特征计 算的，步骤2中距离度量学习矩阵得出的权值对特征属性与交通警情等级之间的 权重关系进行了量化，定义含多维特征属性权值的交通警情相似度如公式(5)，式 中x_q为待预测的交通警情样本，x_h属于X＝(x₁,x₂,x₃,…,x_n)为n个历史交通警情 数据中的一个样本，每个样本包含k维特征属性，分母加上0.01是为了避免当与相等时出现分母为0的情况，

$s(x_q,x_h)=\frac{1}{d(x_q,x_h)}=\frac{1}{\sqrt{\underset{l=1}{\overset{k}{\Sigma }}{w}_l{(x_l^q-x_l^h)}^2}+0.01}---\left(5\right)$

其中w_l是第l个特征的权重，由步骤2中距离度量学习得到对角矩阵A，对角线 上的值即为特征属性权值，训练得到的权值根据特征属性一一对应，由公式(5)计 算当前特征属性与历史交通警情数据库中各个样本的相似度，相似度最大的前K 个历史交通警情数据x₁,x₂,…,x_K作为当前交通警情等级预测的参考；

步骤4：K近邻相似交通警情等级投票

x₁,x₂,…,x_K为步骤3得出的K个最相似历史交通警情样本，其中每一个样 本x_i所属的类别均已知，统计K个最相似历史交通警情等级，将出现频率最高的 类别作为交通警情等级预测结果，K值是一个自定义的常数。

进一步，随机将历史交通警情数据分为两部分，一部分作为训练样本，一部 分作为测试样本，训练样本中含有交通警情等级类别标签，测试样本中去除交通 警情等级类别标签，经步骤3计算出前K个最相似的交通警情等级，取出现频率 最高的警情等级与测试样本原有的警情等级进行对比，交叉验证本方法的准确率， 通过选取不同的K值，对每个K值做100次交叉验证计算出平均准确率，选择准 确率最大的K值作为交通警情等级预测的投票数。

本发明的技术构思为：对已知天气数据、时间数据、环境数据等情况下的城 市交通警情等级进行预测，将整理好的多维历史数据根据交警指挥部门要求进行 分类，利用广义马氏距离度量方法对分类标记后的多维历史数据进行学习，则距 离度量学习矩阵获得了各个特征属性对交通警情等级的权值，权值大的特征属性 对分类贡献度大，根据带权值的欧氏距离计算当前的多维数据与历史数据的相似 度，选择与当前数据最相似的K个历史数据进行警情等级投票，得票高的警情等 级作为当前交通警情等级的预测结果。

本发明的有益效果主要表现在：(1)全面系统地考虑天气因素、时间因素、环 境因素对交通警情等级的影响，采用距离学习矩阵将特征属性与交通警情等级之 间的关系进行量化描述，这一度量方法综合考虑到了多维数据集的特征和各个样 本之间的关系，使对交通警情等级影响大的特征属性权值变大，对交通警情等级 贡献度小的特征属性权值变小，更多的权重加在关键的因素上，通过历史数据片 段加上权重系数预测未来的交通警情等级。

(2)采用的基于广义马氏距离的度量学习矩阵能够根据历史数据自动获取各 个样本的特征属性加权值，再根据该权值对交通警情等级进行预测，基于历史数 据动态更新权值能使经由它预测出来的交通警情等级符合交通管理者所期望的要 求。

(3)由历史交通警情数据提取的特征属性权值对影响交通警情等级的各种因 素进行重要性重新排序，减小噪声特征对交通警情等级的影响，特征属性权值包 含交通警情数据特性，使各项因素对交通警情等级的影响更加符合规律，最大程 度地改善交通警情等级的预测精度。

附图说明

图1是基于距离度量学习的交通警情等级预测方法的流程图。

具体实施方式

下面结合附图对本发明作进一步描述。

参照图1.一种基于距离度量学习的交通警情等级预测方法，包括以下步骤：

步骤1：多维数据整理和交通警情等级分类

采集历史天气数据、历史重大活动数据、建设和封路等其它环境数据与工作 日、节假日和历史交通警情数共同构成关于交通警情的多维历史数据库，真实的 城市交通网络中，当前时刻的交通流量和上一时刻的流量密切相关，将连续的历 史交通警情数据按照等时间段切分为n个片段作为训练样本，每个训练样本片段 包括天气属性、重大活动属性、环境因素属性、工作日和节假日属性，根据交通 管理部门提供的交通警情阈值对n个训练样本进行交通警情等级分类。

步骤2：距离度量学习提取分类后的交通警情样本所对应的多维特征属性权值

根据步骤1得出n个已标记训练样本构成的一个样本空间，该样本空间中各 个元素之间的距离称为度量，其中距离是定义在向量空间中的一种函数，指两个 元素在空间中相隔的长度，也就是说可以将某个空间中的所有对象投影到一个新 的度量空间中，新的度量空间中，同类的或相似的元素之间的距离很小，而不同 类的或不相似的元素之间的距离较大，本方法选取n个训练样本构成包含多维特 征属性的样本空间X，其中X＝(x₁,x₂,x₃,…,x_n)，x_i对应第i个样本代表的多维特 征属性，式(1)是样本空间X中x_i和x_j样本点间的马氏距离，其中矩阵A是我们 需要学习的距离度量矩阵，矩阵A中的每一行代表一个历史样本，每一列对应样 本中的一维特征属性

$d_m(x_i,x_j)=d_A(x_i,x_j)={\left|\right|x_i-x_j\left|\right|}_A=\sqrt{{(x_i-x_j)}^{T}A(x_i-x_j)}---\left(1\right)$

这一度量考虑到了数据集的特征和各个样本之间的关系，能使经由它计算出来的 距离值符合我们所期望的要求，在理想的情况下，同类点之间的距离比不同类点 之间的距离小得多。式(1)中的A是样本空间X的协方差矩阵，样本空间X中的 每个样本均带有交通警情等级标签，故在最小化相同警情等级S(S∈X)中样本之 间的马氏距离平方和的同时，约束不同警情等级D(D∈X)中样本之间的马氏距 离和(令其大于某个阈值)，利用这种方式构建的目标优化函数，使得在新的度量 空间中相同警情等级样本更加紧凑，而不同警情等级样本更加分离，目标函数模 型如式(2)，式(3)所示：

$s.t.\underset{(x_i,x_j)\in D}{\Sigma }{d}_A(x_i,x_j)\ge 1---\left(3\right)$

其中，表示A为半正定矩阵。由目标函数模型求取距离度量学习矩阵A的 过程是一个凸优化问题，本方法采用牛顿法对上述凸优化问题进行求解，最终学 习到的距离度量矩阵为一个稀疏的对角阵，当A为单位阵时马氏距离褪化为欧氏 距离，而本方法训练得出A矩阵为对角矩阵，属于广义马氏距离。距离度量学习 矩阵对角线上的元素即为多维特征属性的权值，该方法可以使更多的权重加在对 交通警情等级影响关键的特征属性上，当某个特征属性对交通警情等级贡献度更 大时，意味着同类样本间距较近，相应的权值经过大量样本计算变大，如果某个 特征属性对交通警情等级贡献度较小时，相应的权值经过大量样本计算应较小甚 至趋于零，训练得到的特征属性权值具有交通警情数据的特性，并反映出各种因 素对交通警情等级的不同影响，能够代表交通警情数据的特点。

步骤3：带权值的欧氏距离寻找与当前特征属性最相似的K个历史交通警情

使用欧氏距离计算K近邻需首先对各个特征属性进行归一化，传统的K近邻 算法选择的相似性度量通常是欧氏距离的倒数，也就是说两者的距离越小表示两 者的相似性越大，反之则相似性越小，假定样本空间X中的样本点x包含k维特 征属性，样本点之间的近邻一般由欧氏距离来度量，设第i个样本点为 其中表示第i个样本第l个特征属性值，两个样本x_i和x_j之 间的欧氏距离定义为公式(4)：

$d_o(x_i,x_j)=\sqrt{\underset{l=1}{\overset{k}{\Sigma }}{(x_l^i-x_l^j)}^2}---\left(4\right)$

给定一个待预测的交通警情样本x_q，由标准欧氏距离可计算出样本x_q与历史样本 空间中最近邻的K个样本x₁,x₂,…,x_K，但每个特征属性的作用都是相同的，样本 之间的距离是根据样本的所有特征计算的，在这些特征属性中，有些特征属性与 交通警情等级是强相关的，有些特征属性与交通警情等级是弱相关的，还有一些 特征属性与交通警情等级不相关，寻找与当前特征属性相似的交通警情历史数据 时，按所有特征属性作用相同来计算样本相似度会导致较大的计算误差，针对这 一缺陷，在交通警情相似度的距离公式中给特征属性赋予不同的权重，步骤2中 距离度量学习矩阵得出的权值对特征属性与交通警情等级之间的权重关系进行了 量化，从而使欧氏空间中相同交通警情等级的样本欧氏距离更接近，不同交通警 情等级的样本欧氏距离更远，定义含多维特征属性权值的交通警情相似度如公式 (5)，式中x_q为待预测的交通警情样本，x_h属于X＝(x₁,x₂,x₃,…,x_n)为n个历史交 通警情数据中的一个样本，每个样本包含k维特征属性，分母加上0.01是为了避 免当与相等时出现分母为0的情况，

$s(x_q,x_h)=\frac{1}{d(x_q,x_h)}=\frac{1}{\sqrt{\underset{l=1}{\overset{k}{\Sigma }}{w}_l{(x_l^q-x_l^h)}^2}+0.01}---\left(5\right)$

其中w_l是第l个特征的权重，由步骤2中距离度量学习得到对角矩阵A，对角线 上的值即为特征属性权值，训练得到的权值根据特征属性一一对应，由公式(5)计 算当前特征属性与历史交通警情数据库中各个样本的相似度，相似度最大的前K 个历史交通警情数据x₁,x₂,…,x_K作为当前交通警情等级预测的参考。

步骤4：K近邻相似交通警情等级投票

x₁,x₂,…,x_K为步骤3得出的K个最相似历史交通警情样本，其中每一个样 本x_i所属的类别均已知，统计K个最相似历史交通警情等级，将出现频率最高的 类别作为交通警情等级预测结果，K值是一个自定义的常数(一般为奇数)，本方 法中随机将历史交通警情数据分为两部分，一部分作为训练样本，一部分作为测 试样本，训练样本中含有交通警情等级类别标签，测试样本中去除交通警情等级 类别标签，经步骤3计算出前K个最相似的交通警情等级，取出现频率最高的警 情等级与测试样本原有的警情等级进行对比，交叉验证本方法的准确率，通过选 取不同的K值，如选择K＝1,2,3,…,9，对每个K值做100次交叉验证计算出平 均准确率，选择准确率最大的K值作为交通警情等级预测的投票数。

以杭州为例，基于距离度量学习的交通警情等级预测方法的实施过程如下：

步骤1：多维数据整理和交通警情等级分类

从相关气象部门获取历史天气数据，从大型活动场馆主页或中超联赛赛程表 获取重大活动日数据，从城市道路交通建设相关单位获取道路维修、建设与封路 等环境数据，与交通警情发生数共同构成多维历史数据库，当由特征属性预测交 通警情等级时，数据库的多样性能够保证提取到足够多的相似样本，从而在相应 的特征属性出现时进行精确预测。将整理好的多维历史数据按照等时间段切分为 n个片段，构成包含n个样本的历史数据空间X，其中X＝(x₁,x₂,x₃,…,x_n)，样本 空间X中的每个样本点x包含k维特征属性，本实施例中该样本数据的特征属性 具体是指与交通警情有关的温度等级、可见度等级、降雨量等级、是否工作日、 是否节假日、星期几、第几个三小时段、月份等数据，本实施例中，根据交通警 情发生次数划分的警情等级是交通管理部门根据经验预先设置的，该交通警情等 级的划分可以对交通指挥者提前进行警力部署和勤务优化提供有效的数据支撑。 整理好的多维特征属性表如表1所示，数据库中存储形式如图1所示，表1与图 1中特征属性维度从左至右均一一对应。

表1

步骤2：距离度量学习提取分类后的交通警情样本所对应的多维特征属性权值 样本空间X＝(x₁,x₂,x₃,…,x_n)中包含n个已标记警情等级的样本，本实施例中每 个样本包含9个特征属性，即x_i∈X为包含9维特征属性的一个样本，假设x_i和x_j为样本空间X中两个相同等级的交通警情，通过公式(1)可以计算出两个样本点间 的马氏距离，其中A是我们需要学习的距离度量矩阵，

$d_m(x_i,x_j)=d_A(x_i,x_j)={\left|\right|x_i-x_j\left|\right|}_A=\sqrt{{(x_i-x_j)}^{T}A(x_i-x_j)}---\left(1\right)$

故最小化相同警情等级S(S∈X)中样本之间的马氏距离平方和的同时，约束不同 警情等级D(D∈X)中样本之间的马氏距离和(令其大于某个阈值)，利用这种方式 构建的目标优化函数，构建的目标函数模型如式(2)、式(3)所示：

$s.t.\underset{(x_i,x_j)\in D}{\Sigma }{d}_A(x_i,x_j)\ge 1---\left(3\right)$

求取目标函数模型的距离度量学习矩阵A的过程是一个凸优化问题，本方法采用 牛顿法对上述凸优化问题进行求解，将上述目标函数模型优化问题变形为求式(7) 的最小值问题：

$g\left(A\right)=g(A_{11},...,A_{\mathrm{nn}})=\underset{(x_i,x_j)\in S}{\Sigma }{\left|\right|x_i-x_j\left|\right|}_A^2-\log \left(\underset{(x_i,x_j)\in D}{\Sigma }{\left|\right|x_i-x_j\left|\right|}_A\right)---\left(7\right)$

式(9)中A＝diag(A₁₁,A₂₂,…,A_nn)为希望求得的距离度量学习矩阵，即我们希望找 到一个矩阵A使函数g(A)最小，在函数g(A)取最值的地方导数g'(A)＝0，则牛 顿法的迭代规则如式(8)，迭代的终止条件如式(9)，其中A为距离度量学习矩阵：

$A:=A-\frac{▿g\left(A\right)}{{▿}^{2}g\left(A\right)}---\left(8\right)$

$|▿g\left(A\right)|\le ϵ---\left(9\right)$

最终学习到的距离度量矩阵为一个稀疏的对角阵，本实施例中根据多维特征属性 学习到的距离度量矩阵如下所示：

距离度量矩阵中，分别对应活动日、工作日、节假日、星期几、第几个三小 时、温度等级、降雨量等级共7个特征属性权值。

步骤3：带权值的欧氏距离寻找与当前特征属性最相似的K个历史交通警情

首先对各个特征属性进行归一化处理，运用公式(10)：

$x_l^i=\frac{x_l^i-\min (x_l^1,x_l^2,...,x_l^n)}{\max (x_l^1,x_l^2,...,x_l^n)-\min (x_l^1,x_l^2,...,x_l^n)}---\left(10\right)$

式(10)中i＝1,2,…,n，l＝1,2,…,7，n是数据集中样本个数，l是特征属性个数， 即本方法中的每个样本包含7个特征属性，对应的原始数据都将划归为[0,1]区间 的数。然后利用交通警情相似度公式(5)计算当前特征属性与历史交通警情数据库 中各个样本的相似度，

$s(x_q,x_h)=\frac{1}{d(x_q,x_h)}=\frac{1}{\sqrt{\underset{l=1}{\overset{k}{\Sigma }}{w}_l{(x_l^q-x_l^h)}^2}+0.01}---\left(5\right)$

式(13)中w_l是样本第l个特征的权重，步骤2中计算出的距离度量学习矩阵包括7 个特征属性权值，权值大小代表特征属性对于交通警情等级影响的重要程度，权 值大说明当前特征属性对交通警情等级分类的贡献度更大，权值较小甚至趋于零 说明当前特征属性对交通警情等级分类的贡献度小，将7个特征属性权值代入公 式(12)中计算当前待预测交通警情等级样本与历史数据库中每个样本的相似度， 按照相似度从大到小的顺序排列输出前K个最相似的历史交通警情。

步骤4：K近邻相似交通警情等级投票

统计步骤3中计算出的K个最相似历史交通警情等级，将出现频率最高的类 别作为当前特征属性的交通警情等级预测结果，本方法中K值是一个自定义的奇 数，如果K太小，则交通警情等级预测容易受到训练数据中的噪声影响，相反如 果K太大，可能会误分类测试样本，因为K个最近邻列表中可能会包含远离其近 邻的数据点，本方法中随机将历史交通警情数据分为两部分，一部分作为训练样 本，一部分作为测试样本，训练样本中含有交通警情等级类别标签，测试样本中 去除交通警情等级类别标签，经本方法预测后的交通警情等级与测试样本原有的 交通警情等级进行对比，等级标签不同即为错误，设acc_i是第i次迭代的模型准 确率，总准确率是通过选取不同的K值，计算本方法的分 类准确率，本实施例中分别计算K＝1,3,5,7时的交通警情等级预测准确率，见表 2.由预测准确率可知当K＝5时预测准确率最高，故预测交通警情等级时应选择前 5个最相似的历史交通警情。表2为K与交通警情等级预测准确率：

表2。