论文部分内容阅读
[摘要]将决策树算法引入到线上货车推送服务体系中，采用ID3算法，通过计算训练样本中的各节点数据，准确构建决策树。经实验表明，该决策树能较好地运用到货车推送服务体系中，从而向货主推送更高质量的服务。
[关键词]货车；决策树算法；推送服务
[中图分类号]U469.2；F253.9 [文献标识码]A [文章编号]1005-152X（2017）02-0082-03
1引言
随着运输行业的不断发展，传统线下运输服务逐步转向线上结合线下进行运输服务。国内线上提供货运服务的平台也越来越多，比如中国物通网、手机APP运满满等。但是，这些平台的服务宗旨都是满足货主运输需求，增加货车司机收益。同时，货运平台希望与货主、司机建立紧密的合作关系，达到“三赢”效果。而这种“三赢”局面是建立在货运平台向货主提供优质的运输服务基础上的，而如何向货主提供优质的货车服务是重要参考因素之一。所以本文结合影响货车运输的多个重要指标，利用决策树算法向货主推送合适的货车，提高服务质量。
2决策树算法（ID3）
构造决策树算法有很多，ID3是其中的一种，它最早由J Ross Quinlan在悉尼大学提出。该算法采用从上到下、分而治之的方法来构造决策树。决策树算法需要原始训练集样本作为输入，训练集样本由多条数据构成，每条數据可以表示成（A1，A2，A3…An，C），其中Ai表示特征属性，C表示类别。建立决策树算法主要分为两步：第一步将训练集样本通过递归的方法构建决策树。第二步利用剪枝的方法，使用非训练集样本数据去检验生产的决策树，同时剪去受影响的分枝。
本文采用某物流企业的运力数据集，经过数据预处理等转换过程，选取了其中900条数据作为样本，每条数据由5个字段组成。其中前4个字段是对车辆评价指标的描述，最后一个字段是该车辆是否推送的定义。数据样本字段描述见表1。
通过为每个字段编号，并描述每个字段取值范围以及取值说明，建立了数据样本集合的相关信息，见表2。
选取三分之二的数据作为训练集样本生成决策树，剩余的数据集作为该决策树的检验样本。
3构建决策树
3.1决策树算法
（1）计算对给定样本数据分类的期望信息。设s是由s个训练样本组成。假定类编号属性有m个不同的取值，定义m个不同类Ci（i=1，2，3，...，m）。si是Ci中的样本数。公式（1）表示一个给定样本分类的期望信息。
（1）
其中，pi是样本属于Ci的概率，可用Sis来估计。
（2）计算每个属性信息熵。设属性A把样本数据集S划分为v个子集（s1，s2，…，sv）。子集Sj中的样本数为sj，分类属性值为（c1，c2，…，cm）的样本数分别为（s1j，s2j…，smj）。公式（2）表示属性A划分为子集的熵。
（2）
其中，（s1j+s2j+s…+smj）/s项是第j个子集的权，并且等于子集中的样本数除以S中的样本总数。熵值越小，子集划分的纯度更高。
（3）计算属性信息的增益。属性信息增益可由期望信息和信息熵得到，公式（3）表示在A上分枝获取的信息增益。
（3）
3.2决策树的生成
（1）类别属性“是否推送”有两个值，即推送货车或不推送货车。给定的样本分类期望信息为：I（s1，s2）=0.971。
（2）分别计算运单次数、回城车、路况熟悉程度、车辆服务星级的熵：
E（运单次数）=0.646 3，Gain（运单次数）=0.324 7；
E（回城车）=0.969 4，Gain（回城车）=0.001 6；
E（路况熟悉程度）=0.567 25，Gain（路况熟悉程度）=0.403 75；
E（车辆服务星级）=0.604 88，Gain（车辆服务星级）=0.366 12。
由于“路况熟悉程度”属性具有最高信息增益，因此它被选作一个根节点，并对其它属性引出分枝，再分别计算分枝的信息增益。最终的决策树如图1所示。
3.3提取决策树的关联规则
通过图1分析，可以提取到的关联规则如下：
IF路况熟悉=“熟悉”THEN推送情况=“推送”；
IF路况熟悉=“一般熟悉”AND回程车=“是"”ND运单次数=“多”THEN推送情况=“推送”；
IF路况熟悉=“一般熟悉”AND回程车=“是”AND运单次数=“中等”THEN推送情况=“推送”；
IF路况熟悉=“一般熟悉”AND回程车=“是”AND运单次数=“少”THEN推送情况=“不推送”；
IF路况熟悉=“一般熟悉”AND回程车=“否”AND服务星级=“五星”THEN推送情况=“推送”；
IF路况熟悉=“一般熟悉”AND回程车=“否”AND服务星级=“四星”THEN推送情况=“推送”；
IF路况熟悉=“一般熟悉”AND回程车=“否”AND服务星级=“三星及以下”THEN推送情况=“不推送”；
IF路况熟悉=“不熟悉”AND服务星级=“五星”THEN推送情况=“推送”；
IF路况熟悉=“不熟悉”AND服务星级=“四星”AND回程车=“是”THEN推送情况=“推送”；
IF路况熟悉=“不熟悉”AND服务星级=“四星”AND回程车=“否”THEN推送情况=“不推送”；
IF路况熟悉=“不熟悉”AND服务星级=“三星及以下”AND运单次数=“多”THEN推送情况=“推送”；
IF路况熟悉=“不熟悉”AND服务星级=“三星及以下”AND运单次数=“中等”THEN推送情况=“不推送”；
IF路况熟悉=“不熟悉”AND服务星级=“三星及以下”AND运单次数=“少”THEN推送情况=“不推送”。
4实验分析
4.1实验一
本实验选取了实验数据为100辆已有多次运输记录的货车，运输地点范围为四川省成都市，货主需求12辆货车。通过原始推送服务，能推送出20辆满足货主需求的货车，但是货主实际选择运输的货车只有8辆。但是通过该决策树算法，只能推送出16辆满足货主需求的货车，货主实际选择了10辆货车。
4.2实验二
本实验选取了實验数据为50Ne，有多次运输记录的货车，运输地点范围为四川省成都市到重庆市，货主需求10辆货车。通过原始推送服务，能推送出18辆满足货主需求的货车，但是货主实际选择运输的货车只有6辆。但是通过该决策树算法，能推送出15辆满足货主需求的货车，货主实际选择了9辆货车。实验对比如图2所示。
4.3实验分析
通过两次实验对比，虽然通过决策树算法减少了推送的货车，但是货主实际选择货车数量比在原始推送服务中有明显增加。同时，推送货车实际利用率增比可达到22%。由此可以说明，该决策树算法能有效运用到线上货车推送服务中，进而使货主得到更优质的服务。
5总结
本文提出了将决策树算法应用到线上货车推送服务过程中的新思路，能有效预测线上货车是否推送给货主，进一步为货主提供高质量服务。该方法可以快速提取出简洁、准确度高的关联规则。通过分析决策树算法，并准确预测推送的车辆，能使企业、司机以及货主建立紧密的合作关系，从而达到“三赢”的效果。
[关键词]货车；决策树算法；推送服务
[中图分类号]U469.2；F253.9 [文献标识码]A [文章编号]1005-152X（2017）02-0082-03
1引言
随着运输行业的不断发展，传统线下运输服务逐步转向线上结合线下进行运输服务。国内线上提供货运服务的平台也越来越多，比如中国物通网、手机APP运满满等。但是，这些平台的服务宗旨都是满足货主运输需求，增加货车司机收益。同时，货运平台希望与货主、司机建立紧密的合作关系，达到“三赢”效果。而这种“三赢”局面是建立在货运平台向货主提供优质的运输服务基础上的，而如何向货主提供优质的货车服务是重要参考因素之一。所以本文结合影响货车运输的多个重要指标，利用决策树算法向货主推送合适的货车，提高服务质量。
2决策树算法（ID3）
构造决策树算法有很多，ID3是其中的一种，它最早由J Ross Quinlan在悉尼大学提出。该算法采用从上到下、分而治之的方法来构造决策树。决策树算法需要原始训练集样本作为输入，训练集样本由多条数据构成，每条數据可以表示成（A1，A2，A3…An，C），其中Ai表示特征属性，C表示类别。建立决策树算法主要分为两步：第一步将训练集样本通过递归的方法构建决策树。第二步利用剪枝的方法，使用非训练集样本数据去检验生产的决策树，同时剪去受影响的分枝。
本文采用某物流企业的运力数据集，经过数据预处理等转换过程，选取了其中900条数据作为样本，每条数据由5个字段组成。其中前4个字段是对车辆评价指标的描述，最后一个字段是该车辆是否推送的定义。数据样本字段描述见表1。
通过为每个字段编号，并描述每个字段取值范围以及取值说明，建立了数据样本集合的相关信息，见表2。
选取三分之二的数据作为训练集样本生成决策树，剩余的数据集作为该决策树的检验样本。
3构建决策树
3.1决策树算法
（1）计算对给定样本数据分类的期望信息。设s是由s个训练样本组成。假定类编号属性有m个不同的取值，定义m个不同类Ci（i=1，2，3，...，m）。si是Ci中的样本数。公式（1）表示一个给定样本分类的期望信息。
（1）
其中，pi是样本属于Ci的概率，可用Sis来估计。
（2）计算每个属性信息熵。设属性A把样本数据集S划分为v个子集（s1，s2，…，sv）。子集Sj中的样本数为sj，分类属性值为（c1，c2，…，cm）的样本数分别为（s1j，s2j…，smj）。公式（2）表示属性A划分为子集的熵。
（2）
其中，（s1j+s2j+s…+smj）/s项是第j个子集的权，并且等于子集中的样本数除以S中的样本总数。熵值越小，子集划分的纯度更高。
（3）计算属性信息的增益。属性信息增益可由期望信息和信息熵得到，公式（3）表示在A上分枝获取的信息增益。
（3）
3.2决策树的生成
（1）类别属性“是否推送”有两个值，即推送货车或不推送货车。给定的样本分类期望信息为：I（s1，s2）=0.971。
（2）分别计算运单次数、回城车、路况熟悉程度、车辆服务星级的熵：
E（运单次数）=0.646 3，Gain（运单次数）=0.324 7；
E（回城车）=0.969 4，Gain（回城车）=0.001 6；
E（路况熟悉程度）=0.567 25，Gain（路况熟悉程度）=0.403 75；
E（车辆服务星级）=0.604 88，Gain（车辆服务星级）=0.366 12。
由于“路况熟悉程度”属性具有最高信息增益，因此它被选作一个根节点，并对其它属性引出分枝，再分别计算分枝的信息增益。最终的决策树如图1所示。
3.3提取决策树的关联规则
通过图1分析，可以提取到的关联规则如下：
IF路况熟悉=“熟悉”THEN推送情况=“推送”；
IF路况熟悉=“一般熟悉”AND回程车=“是"”ND运单次数=“多”THEN推送情况=“推送”；
IF路况熟悉=“一般熟悉”AND回程车=“是”AND运单次数=“中等”THEN推送情况=“推送”；
IF路况熟悉=“一般熟悉”AND回程车=“是”AND运单次数=“少”THEN推送情况=“不推送”；
IF路况熟悉=“一般熟悉”AND回程车=“否”AND服务星级=“五星”THEN推送情况=“推送”；
IF路况熟悉=“一般熟悉”AND回程车=“否”AND服务星级=“四星”THEN推送情况=“推送”；
IF路况熟悉=“一般熟悉”AND回程车=“否”AND服务星级=“三星及以下”THEN推送情况=“不推送”；
IF路况熟悉=“不熟悉”AND服务星级=“五星”THEN推送情况=“推送”；
IF路况熟悉=“不熟悉”AND服务星级=“四星”AND回程车=“是”THEN推送情况=“推送”；
IF路况熟悉=“不熟悉”AND服务星级=“四星”AND回程车=“否”THEN推送情况=“不推送”；
IF路况熟悉=“不熟悉”AND服务星级=“三星及以下”AND运单次数=“多”THEN推送情况=“推送”；
IF路况熟悉=“不熟悉”AND服务星级=“三星及以下”AND运单次数=“中等”THEN推送情况=“不推送”；
IF路况熟悉=“不熟悉”AND服务星级=“三星及以下”AND运单次数=“少”THEN推送情况=“不推送”。
4实验分析
4.1实验一
本实验选取了实验数据为100辆已有多次运输记录的货车，运输地点范围为四川省成都市，货主需求12辆货车。通过原始推送服务，能推送出20辆满足货主需求的货车，但是货主实际选择运输的货车只有8辆。但是通过该决策树算法，只能推送出16辆满足货主需求的货车，货主实际选择了10辆货车。
4.2实验二
本实验选取了實验数据为50Ne，有多次运输记录的货车，运输地点范围为四川省成都市到重庆市，货主需求10辆货车。通过原始推送服务，能推送出18辆满足货主需求的货车，但是货主实际选择运输的货车只有6辆。但是通过该决策树算法，能推送出15辆满足货主需求的货车，货主实际选择了9辆货车。实验对比如图2所示。
4.3实验分析
通过两次实验对比，虽然通过决策树算法减少了推送的货车，但是货主实际选择货车数量比在原始推送服务中有明显增加。同时，推送货车实际利用率增比可达到22%。由此可以说明，该决策树算法能有效运用到线上货车推送服务中，进而使货主得到更优质的服务。
5总结
本文提出了将决策树算法应用到线上货车推送服务过程中的新思路，能有效预测线上货车是否推送给货主，进一步为货主提供高质量服务。该方法可以快速提取出简洁、准确度高的关联规则。通过分析决策树算法，并准确预测推送的车辆，能使企业、司机以及货主建立紧密的合作关系，从而达到“三赢”的效果。