本文首次把决策树模型^{[12, 13]}应用于城市道路在线车型分类。决策树是一种非常有效的机器学习分类算法, 是用二叉树来表示处理逻辑的一种工具。决策树由决策结点、分支和叶子组成, 最上面的结点为根结点, 每个分支是一个新的决策结点, 或者是叶子; 每个决策结点代表一个问题或决策, 通常对应于待分类对象的一个特征量; 每一个叶子结点代表一种可能的分类结果^[13]。

本文采用基于最优最小划分样本数的CART算法^[12]建立决策树。CART算法采用二分递归分割技术, 将当前的样本集分为两个子样本集, 使得生成的决策树的每个非叶子结点都有两个分支^[12]。该算法生成的决策树是结构简洁的二叉树, CART算法流程如下:

(1)创建样本集 为叶子结点, 返回; 否则进入第(3)步。

(3)针对 计算该特征不同划分时的GINI系数, 并记特征 的最小GINI系数为GINI(i)。

(4)对于所有i, 求GINI(i)中最小者, 并把其对应的特征向量 的判别特征向量, 并记录该结点处的划分。

(5)依据第(4)步的划分, 把

(6)对 重复第(1)~(5)步。

(7)对 重复第(1)~(5)步。

本算法中参数 为最小划分样本数(Minimum number of split-samples, MNS)。当τ =1时, 得到训练样本的最优划分, 但有时会造成决策树的过度拟合, 不利于提高新样本的准确率。在实际应用中, 样本量有限且为离线寻优, 故计算不同 值。GINI系数衡量样本集 的GINI系数定义为:

式中: 类样本占总样本数的比例)。

依据样本集T某个特征的划分 两个集合, 则新划分后的GINI系数如下:

式中:

本文算法能够根据样本特征自学习, 选择最能有效进行分类的特征建立决策树, 省去了如神经网络、朴素Bayes分类算法剔除无效特征、计算不同特征相关性等步骤, 从而根据建立的最佳决策树得到最优特征组合。

利用已知样本对决策树模型进行训练, 建立能够对样本进行有效分类的最佳决策树。设样本数为 个车辆波形对应的车型。

确定最优 值后, 利用CART算法对模型输入X_{m× 8}、y进行训练, 得到最佳决策树Tree_opt。根结点都为一个判断, 通过某个特征都把样本集分为两个部分, 用于划分更精细的分类; 叶子结点都对应一个车型。

由于可能出现过拟合情况, 需要对最佳决策树Tree_opt进行剪枝, 得到最佳剪枝树PTree_opt, 提高样本鲁棒性。本文采用最小错误剪枝(Minimum error pruning, MEP)原则对最佳决策树进行剪枝, 定义使测试样本的分类准确率最大的剪枝树作为最佳剪枝树PTree_opt。

离线训练得到最佳剪枝树后, 在传感器节点上实现车型的在线分类。最佳剪枝树给出了车辆波形的最优特征组合, 为减小计算量, 在线分类时只需计算最优特征即可。在线车型分类是沿着决策树从上到下遍历的过程, 过程中根据遇到的决策结点的特征判别条件进行判断, 进入下一个分支, 最后到达一个叶子结点, 读取叶子结点信息即可得到新样本的一个分类。

用于采集实地车辆波形的传感器布设在北京市海淀区交大东路上某车道中央。样本为2009年5月~11月若干时间段采集的470辆小汽车和72辆公交车的车辆波形, 把这542个车辆波形作为样本集验证本文方法。

通过车辆波形获取和特征提取两个步骤得到了包含542个车辆波形样本的特征矩阵, 记作X_{542× 8}。为了对训练结果进行验证, 本文随机地把271个车辆波形(包括235辆小汽车样本和36辆公交车样本)样本作为训练样本, 训练样本特征矩阵记作X_train; 剩余271个车辆波形样本作为测试样本, 测试样本特征矩阵记作X_test。样本采集时利用视频记录并人工统计实际车型, 记1为小汽车, 2为公交车, 则得到X_train对应的车型向量y_train及X_test对应的车型向量y_test。

为了得到最优参数 值时的决策树对训练样本和测试样本进行分类的准确率, 结果见表1。 较小时, 能够实现100%的分类准确率, 但此时对测试样本的鲁棒性较差; 随着 的增加, 训练样本分类准确率会不断下降, 而测试样本分类准确率会有所提高。原则上, 值不应大于最少类别的样本数, 否则不利于此类样本的分类。为了确定最优的 值, 计算各 值下的决策树对训练和测试样本的平均分类准确率, 具有最大平均分类准确率的 值即为最优 值。

表1

Table 1

表1(Table 1)

表1 不同τ 值时的决策树对样本进行分类的准确率 Table 1 Accuracy rates of samples with different τ 参数τ 集内测试分类准确率/% 集外测试分类准确率/% 公交车 小汽车 均值 公交车 小汽车 均值 1~3 100.0 100.0 100.0 75.0 98.7 86.9 4~9 100.0 99.6 99.8 77.8 98.7 88.3 10 97.2 99.6 98.4 77.8 99.6 88.7 11~20 94.4 99.6 97.0 77.8 100.0 88.9

表1 不同τ 值时的决策树对样本进行分类的准确率 Table 1 Accuracy rates of samples with different τ

由表1可以看出, 当 取4、5、6、7、8或9时, 平均分类准确率最大。而且 越大, 算法收敛越快, 故本文的最优 值取9。

当τ =9时, 利用CART算法对X_train和y_train进行训练, 得到图3所示的最佳决策树Tree_opt。其中三角形为决策结点, 圆形为叶子结点, 叶子结点上的1表示分类结果为小汽车, 2表示分类结果为公交车。

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 基于CART算法的最佳决策树TreeoptFig.3 CART-based optimal decision tree Treeopt

Tree_opt是基于训练样本的最佳决策树, 可得最优特征组合 四个特征, 减小了特征提取时的计算量。根据图3所示的最佳决策树Tree_opt得到本实例的在线车型分类算法(决策树算法)如下:

(1)Node 1:若x₁< 5.5, 进入第(2)步; 否则进入第(3)步。

(2)Node 2:若x₂< 0.898613, 进入第(4)步; 否则进入第(5)步。

(3)Node 3:若x₈< 1.12183, 进入第(6)步; 否则进入第(7)步。

(4)Node 4:若x₂< 0.0938607, 进入第(8)步; 否则进入第(9)步。

(5)Node 5:class=2, 结束。

(6)Node 6:class=1, 结束。

(7)Node 7:class=2, 结束。

(8)Node 8:若x₂< 0.0926934, 进入第(10)步; 否则进入第(11)步。

(9)Node 9:class=1, 结束。

(10)Node 10:若x₆< 2480.33, 进入第(12)步; 否则进入第(13)步。

(11)Node 11:class=2, 结束。

(12)Node 12:class=1, 结束。

(13)Node 13:class=2, 结束。

利用决策树算法, 分别对训练样本和测试样本进行集内测试和集外测试。表2和表3分别为集内测试和集外测试的分类准确率。

表2

Table 2

表2(Table 2)

表2 基于Treeopt的集内测试结果 Table 2 Test results of Xtrain based on Treeopt 视频标定数据 分类结果 准确率/% 小汽车 公交车 小汽车(235个) 234 1 99.6 公交车(36个) 0 36 100.0 平均准确率 99.8

表2 基于Treeopt的集内测试结果 Table 2 Test results of Xtrain based on Treeopt

表3

Table 3

表3(Table 3)

表3 基于Treeopt的集外测试结果 Table 3 Test results of Xtest based on Treeopt 视频标定数据 分类结果 准确率/% 小汽车 公交车 小汽车(235个) 232 3 98.7 公交车(36个) 8 28 77.8 平均准确率 88.3

表3 基于Treeopt的集外测试结果 Table 3 Test results of Xtest based on Treeopt

为了进一步提高测试样本的分类准确率, 基于MEP原则对Tree_opt进行剪枝, 得到图4所示的最佳剪枝树PTree_opt。

根据图4的最佳剪枝树PTree_opt得到本实例的改进在线车型分类算法(剪枝树算法)如下:

(1)Node 1:若x₁< 5.5, 进入第(2)步; 否则进入第(3)步。

(2)Node 2:若x₂< 0.898613, 进入第(4)步; 否则进入第(5)步。

(3)Node 3:若x₈< 1.12183, 进入第(6)步; 否则进入第(7)步。

(4)Node 4:class=1, 结束。

(5)Node 5:class=2, 结束。

(6)Node 6:class=1, 结束。

(7)Node 7:class=2, 结束。

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 基于MEP原则的最佳剪枝树PTreeoptFig.4 MEP-based optimal pruning tree PTreeopt

与决策树算法相比, 剪枝树算法更加简洁, 执行速度更高, 这对计算和存储能力有限的传感器节点非常重要。由于采用基于MEP原则对Tree_opt进行剪枝, 剪枝树算法比决策树算法的分类准确率更高, 对新样本的鲁棒性更高。利用剪枝树算法, 得到新的集外测试结果见表4。

表4

Table 4

表4(Table 4)

表4 基于最佳剪枝树PTreeopt的集外测试结果 Table 4 Test results of Xtest based on PTreeopt 视频标定数据 分类结果 准确率/% 小汽车 公交车 小汽车(235个) 235 0 100.0 公交车(36个) 8 28 77.8 平均准确率 88.9

表4 基于最佳剪枝树PTreeopt的集外测试结果 Table 4 Test results of Xtest based on PTreeopt

为了进一步验证本文方法的有效性, 从分类准确率、样本鲁棒性和算法执行时间等方面对本文方法与多种现有常用分类算法进行了对比。基于本实例的测试样本X_test, 表5给出了本文方法与人工神经网络(ANN)、支持向量机(SVM)、朴素Bayes分类(NBayes)、模板匹配(TPM)等算法在分类准确率方面的测试结果。可以看出基于最优MNS的CART算法表现出较高的准确率。由于公交车样本量较少, 算法学习不够充分, 多种算法的公交车分类准确率较低, 仅CART和SVM算法能够给出较好的分类结果。在样本学习中, CART算法能够得到更高拟合度的决策树模型。为了验证CART算法的样本鲁棒性, 把训练样本X_train和测试样本X_test互换(本文把互换前称正向测试, 互换后称反向测试), 以分析各算法分类结果受样本特殊性的影响程度。表6给出了各分类器反向测试结果。CART算法仍能得到较高的分类准确率, 其次是SVM算法。从表5和表6知, 基于最优MNS的CART算法在车型分类中能够得到较高的分类准确率和较好的样本鲁棒性。

表5

Table 5

表5(Table 5)

表5 不同算法的正向测试结果 Table 5 Test results of original samples by different methods 方法 分类准确率/% 小汽车 公交车 平均 TPM 79.1 19.4 49.3 ANN 100.0 69.4 84.7 SVM 100.0 77.8 88.9 NBayes 99.6 66.7 83.1 CART 100.0 77.8 88.9

表5 不同算法的正向测试结果 Table 5 Test results of original samples by different methods

表6

Table 6

表6(Table 6)

表6 不同算法的反向测试结果 Table 6 Test results of exchange samples of different methods 方法 分类准确率/% 小汽车 公交车 平均 TPM 100.0 0.0 50.0 ANN 99.6 80.6 90.2 SVM 100.0 77.8 88.9 NBayes 99.1 63.9 81.5 CART 97.0 91.7 94.4

表6 不同算法的反向测试结果 Table 6 Test results of exchange samples of different methods

图5

Fig.5

	Figure Option ViewDownloadNew Window
	图5 不同方法完成实例样本分类占用的CPU时间 (10次测试的平均值)Fig.5 CPU time of different methods(average of ten test values)

由于本文方法的学习和优化都是离线进行的, 不需要考虑实时性问题。但决策树算法或剪枝树算法是在能量和计算资源都有限的传感器节点上进行实时在线分类的, 故在算法执行时间方面, 本文重点研究在线分类时的算法执行时间。图5给出了不同方法完成实例样本分类占用的计算机CPU时间。测试使用的计算机配置如下:操作系统为Windows VistaTM Business; 处理器为Intel Core(TM)2 Duo, CPU为E6750@2.66 GHz; 内存为4.00 GB。ANN和TPM算法运算时间较长, 在线分类速度较慢; CART、SVM和NBayes算法在线分类速度较快, 在运算时间上具有优势, 但考虑到车型分类的准确率, CART算法的优势更加明显, SVM算法次之。