決策樹算法在線上貨車推送服務中的運用

廖雪花，唐思娩，任春華

（四川師范大學 計算機科學學院，四川 成都 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-），通訊作者，女，碩士，副教授，研究方向：計算機網絡與信息系統、模式識別。