廖雪花，唐思娩，任春华

（四川师范大学 计算机科学学院，四川 成都 610101）

决策树算法在线上货车推送服务中的运用

廖雪花，唐思娩，任春华

（四川师范大学 计算机科学学院，四川 成都 610101）

将决策树算法引入到线上货车推送服务体系中，采用ID3算法，通过计算训练样本中的各节点数据，准确构建决策树。经实验表明，该决策树能较好地运用到货车推送服务体系中，从而向货主推送更高质量的服务。

货车；决策树算法；推送服务

1 引言

随着运输行业的不断发展，传统线下运输服务逐步转向线上结合线下进行运输服务。国内线上提供货运服务的平台也越来越多，比如中国物通网、手机APP运满满等。但是，这些平台的服务宗旨都是满足货主运输需求，增加货车司机收益。同时，货运平台希望与货主、司机建立紧密的合作关系，达到“三赢”效果。而这种“三赢”局面是建立在货运平台向货主提供优质的运输服务基础上的，而如何向货主提供优质的货车服务是重要参考因素之一。所以本文结合影响货车运输的多个重要指标，利用决策树算法向货主推送合适的货车，提高服务质量。

2 决策树算法（ID3）

构造决策树算法有很多，ID3是其中的一种，它最早由J Ross Quinlan在悉尼大学提出。该算法采用从上到下、分而治之的方法来构造决策树。决策树算法需要原始训练集样本作为输入，训练集样本由多条数据构成，每条数据可以表示成（A1，A2，A3...An，C），其中Ai表示特征属性，C表示类别[1]。建立决策树算法主要分为两步：第一步将训练集样本通过递归的方法构建决策树。第二步利用剪枝的方法，使用非训练集样本数据去检验生产的决策树，同时剪去受影响的分枝。

本文采用某物流企业的运力数据集，经过数据预处理等转换过程，选取了其中900条数据作为样本，每条数据由5个字段组成。其中前4个字段是对车辆评价指标的描述，最后一个字段是该车辆是否推送的定义[2]。数据样本字段描述见表1。

表1 数据样本字段描述

通过为每个字段编号，并描述每个字段取值范围以及取值说明，建立了数据样本集合的相关信息，见表2。

表2 数据样本集合字段信息

选取三分之二的数据作为训练集样本生成决策树，剩余的数据集作为该决策树的检验样本。

3 构建决策树

3.1 决策树算法

（1）计算对给定样本数据分类的期望信息。设S是由s个训练样本组成。假定类编号属性有m个不同的取值，定义m个不同类Ci（i=1,2,3,...,m）。si是Ci中的样本数[3]。公式（1）表示一个给定样本分类的期望信息。

其中，pi是样本属于Ci的概率，可用Si/s来估计。

（2）计算每个属性信息熵。设属性A把样本数据集S划分为v个子集（s1，s2，...,sv）。子集Sj中的样本数为sj，分类属性值为（c1，c2，...，cm）的样本数分别为（s1j，s2j，...，smj）[4]。公式（2）表示属性A划分为子集的熵。

其中，（s1j+s2j+...+smj）/s项是第j个子集的权，并且等于子集中的样本数除以S中的样本总数。熵值越小，子集划分的纯度更高[5]。

（3）计算属性信息的增益。属性信息增益可由期望信息和信息熵得到，公式（3）表示在A上分枝获取的信息增益。

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回程车=“是”AND运单次数=“多”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推送情况=“不推送”。

图1 货车推送服务的决策树

4 实验分析

4.1 实验一

本实验选取了实验数据为100辆已有多次运输记录的货车，运输地点范围为四川省成都市，货主需求12辆货车。通过原始推送服务，能推送出20辆满足货主需求的货车，但是货主实际选择运输的货车只有8辆。但是通过该决策树算法，只能推送出16辆满足货主需求的货车，货主实际选择了10辆货车。

4.2 实验二

本实验选取了实验数据为50辆已有多次运输记录的货车，运输地点范围为四川省成都市到重庆市，货主需求10辆货车。通过原始推送服务，能推送出18辆满足货主需求的货车，但是货主实际选择运输的货车只有6辆。但是通过该决策树算法，能推送出15辆满足货主需求的货车，货主实际选择了9辆货车。实验对比如图2所示。

4.3 实验分析

通过两次实验对比，虽然通过决策树算法减少了推送的货车，但是货主实际选择货车数量比在原始推送服务中有明显增加。同时，推送货车实际利用率增比可达到22%。由此可以说明，该决策树算法能有效运用到线上货车推送服务中，进而使货主得到更优质的服务。

图2 推送服务实验对比图

5 总结

本文提出了将决策树算法应用到线上货车推送服务过程中的新思路，能有效预测线上货车是否推送给货主，进一步为货主提供高质量服务。该方法可以快速提取出简洁、准确度高的关联规则。通过分析决策树算法，并准确预测推送的车辆，能使企业、司机以及货主建立紧密的合作关系，从而达到“三赢”的效果。

[1]谢榕.数据挖掘与决策支持系统[J].计算机系统应用,1999,3 (8):25-30.

[2]郭鹏文,王东.物流货运交易网站信用评价模型研究[J].计算机应用与软件,2010,5(2):36-41.

[3]廖卫,王如龙,王莹.决策树算法在第三方物流企业信用评级中的研究与应用[J].物流科技,2013,36(10):79-82.

[4]陆瑞兴,杨颖,张毅.决策树算法在物流仓库中的研究与应用[J].微计算机信息,2010,26(30):198-200.

[5]王永梅,胡学钢.决策树中ID3算法的研究[J].安徽大学学报:自然科学版,2011,(3):71-75.

[6]王国庆.决策树算法ID3的应用研究[J].科技视界,2014,（34）: 100.

Application of Decision Tree Algorithm in Online Push of Trucking Services

Liao Xuehua,Tang Simian,RenChunhua
(School of Computer Science,Sichuan Normal University,Chengdu 610101,China)

In this paper,we introduced the decision tree algorithm into the online push of the trucking services,adopted the ID3 algorithm which,with the nodal data of the training sample,could accurately yield the decision tree,and at the end,demonstrated its validity through an empirical case.

truck;decisiontree algorithm;pushservice

U469.2;F253.9

A

1005-152X(2017)02-0082-03

10.3969/j.issn.1005-152X.2017.02.020

2016-12-12

四川省科技厅科技支撑项目（2012GZX0090，2014GZX0002）

廖雪花（1976-），通讯作者，女，硕士，副教授，研究方向：计算机网络与信息系统、模式识别。