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

廖雪花，唐思娩，任春華

（四川師范大學(xué) 計算機科學(xué)學(xué)院，四川 成都 610101）

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

廖雪花，唐思娩，任春華

（四川師范大學(xué) 計算機科學(xué)學(xué)院，四川 成都 610101）

將決策樹算法引入到線上貨車推送服務(wù)體系中，采用ID3算法，通過計算訓(xùn)練樣本中的各節(jié)點數(shù)據(jù)，準確構(gòu)建決策樹。經(jīng)實驗表明，該決策樹能較好地運用到貨車推送服務(wù)體系中，從而向貨主推送更高質(zhì)量的服務(wù)。

貨車；決策樹算法；推送服務(wù)

1 引言

隨著運輸行業(yè)的不斷發(fā)展，傳統(tǒng)線下運輸服務(wù)逐步轉(zhuǎn)向線上結(jié)合線下進行運輸服務(wù)。國內(nèi)線上提供貨運服務(wù)的平臺也越來越多，比如中國物通網(wǎng)、手機APP運滿滿等。但是，這些平臺的服務(wù)宗旨都是滿足貨主運輸需求，增加貨車司機收益。同時，貨運平臺希望與貨主、司機建立緊密的合作關(guān)系，達到“三贏”效果。而這種“三贏”局面是建立在貨運平臺向貨主提供優(yōu)質(zhì)的運輸服務(wù)基礎(chǔ)上的，而如何向貨主提供優(yōu)質(zhì)的貨車服務(wù)是重要參考因素之一。所以本文結(jié)合影響貨車運輸?shù)亩鄠€重要指標，利用決策樹算法向貨主推送合適的貨車，提高服務(wù)質(zhì)量。

2 決策樹算法（ID3）

構(gòu)造決策樹算法有很多，ID3是其中的一種，它最早由J Ross Quinlan在悉尼大學(xué)提出。該算法采用從上到下、分而治之的方法來構(gòu)造決策樹。決策樹算法需要原始訓(xùn)練集樣本作為輸入，訓(xùn)練集樣本由多條數(shù)據(jù)構(gòu)成，每條數(shù)據(jù)可以表示成（A1，A2，A3...An，C），其中Ai表示特征屬性，C表示類別[1]。建立決策樹算法主要分為兩步：第一步將訓(xùn)練集樣本通過遞歸的方法構(gòu)建決策樹。第二步利用剪枝的方法，使用非訓(xùn)練集樣本數(shù)據(jù)去檢驗生產(chǎn)的決策樹，同時剪去受影響的分枝。

本文采用某物流企業(yè)的運力數(shù)據(jù)集，經(jīng)過數(shù)據(jù)預(yù)處理等轉(zhuǎn)換過程，選取了其中900條數(shù)據(jù)作為樣本，每條數(shù)據(jù)由5個字段組成。其中前4個字段是對車輛評價指標的描述，最后一個字段是該車輛是否推送的定義[2]。數(shù)據(jù)樣本字段描述見表1。

表1 數(shù)據(jù)樣本字段描述

通過為每個字段編號，并描述每個字段取值范圍以及取值說明，建立了數(shù)據(jù)樣本集合的相關(guān)信息，見表2。

表2 數(shù)據(jù)樣本集合字段信息

選取三分之二的數(shù)據(jù)作為訓(xùn)練集樣本生成決策樹，剩余的數(shù)據(jù)集作為該決策樹的檢驗樣本。

3 構(gòu)建決策樹

3.1 決策樹算法

（1）計算對給定樣本數(shù)據(jù)分類的期望信息。設(shè)S是由s個訓(xùn)練樣本組成。假定類編號屬性有m個不同的取值，定義m個不同類Ci（i=1,2,3,...,m）。si是Ci中的樣本數(shù)[3]。公式（1）表示一個給定樣本分類的期望信息。

其中，pi是樣本屬于Ci的概率，可用Si/s來估計。

（2）計算每個屬性信息熵。設(shè)屬性A把樣本數(shù)據(jù)集S劃分為v個子集（s1，s2，...,sv）。子集Sj中的樣本數(shù)為sj，分類屬性值為（c1，c2，...，cm）的樣本數(shù)分別為（s1j，s2j，...，smj）[4]。公式（2）表示屬性A劃分為子集的熵。

其中，（s1j+s2j+...+smj）/s項是第j個子集的權(quán)，并且等于子集中的樣本數(shù)除以S中的樣本總數(shù)。熵值越小，子集劃分的純度更高[5]。

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

3.2 決策樹的生成

（1）類別屬性“是否推送”有兩個值，即推送貨車或不推送貨車。給定的樣本分類期望信息為：I（s1，s2）= 0.971。

（2）分別計算運單次數(shù)、回城車、路況熟悉程度、車輛服務(wù)星級的熵：

E（運單次數(shù)）=0.646 3，Gain（運單次數(shù)）=0.324 7；

E（回城車）=0.969 4，Gain（回城車）=0.001 6；

E（路況熟悉程度）=0.567 25，Gain（路況熟悉程度）=0.403 75；

E（車輛服務(wù)星級）=0.604 88，Gain（車輛服務(wù)星級）=0.366 12。

由于“路況熟悉程度”屬性具有最高信息增益，因此它被選作一個根節(jié)點，并對其它屬性引出分枝，再分別計算分枝的信息增益。最終的決策樹如圖1所示。

3.3 提取決策樹的關(guān)聯(lián)規(guī)則

通過圖1分析，可以提取到的關(guān)聯(lián)規(guī)則如下：

IF 路況熟悉=“熟悉”THEN推送情況=“推送”；

IF 路況熟悉=“一般熟悉”AND回程車=“是”AND運單次數(shù)=“多”THEN推送情況=“推送”；

IF 路況熟悉=“一般熟悉”AND回程車=“是”AND運單次數(shù)=“中等”THEN推送情況=“推送”；

IF 路況熟悉=“一般熟悉”AND回程車=“是”AND運單次數(shù)=“少”THEN推送情況=“不推送”；

IF 路況熟悉=“一般熟悉”AND回程車=“否”AND服務(wù)星級=“五星”THEN推送情況=“推送”；

IF 路況熟悉=“一般熟悉”AND回程車=“否”AND服務(wù)星級=“四星”THEN推送情況=“推送”；

IF 路況熟悉=“一般熟悉”AND回程車=“否”AND服務(wù)星級=“三星及以下”THEN推送情況=“不推送”；

IF 路況熟悉=“不熟悉”AND服務(wù)星級=“五星”THEN 推送情況=“推送”；

IF 路況熟悉=“不熟悉”AND服務(wù)星級=“四星”AND回程車=“是”THEN推送情況=“推送”；

IF 路況熟悉=“不熟悉”AND服務(wù)星級=“四星”AND回程車=“否”THEN推送情況=“不推送”；

IF 路況熟悉=“不熟悉”AND服務(wù)星級=“三星及以下”AND運單次數(shù)=“多”THEN推送情況=“推送”；

IF路況熟悉=“不熟悉”AND服務(wù)星級=“三星及以下”AND運單次數(shù)=“中等”THEN推送情況=“不推送”；

IF路況熟悉=“不熟悉”AND服務(wù)星級=“三星及以下”AND運單次數(shù)=“少”THEN推送情況=“不推送”。

圖1 貨車推送服務(wù)的決策樹

4 實驗分析

4.1 實驗一

本實驗選取了實驗數(shù)據(jù)為100輛已有多次運輸記錄的貨車，運輸?shù)攸c范圍為四川省成都市，貨主需求12輛貨車。通過原始推送服務(wù)，能推送出20輛滿足貨主需求的貨車，但是貨主實際選擇運輸?shù)呢涇囍挥?輛。但是通過該決策樹算法，只能推送出16輛滿足貨主需求的貨車，貨主實際選擇了10輛貨車。

4.2 實驗二

本實驗選取了實驗數(shù)據(jù)為50輛已有多次運輸記錄的貨車，運輸?shù)攸c范圍為四川省成都市到重慶市，貨主需求10輛貨車。通過原始推送服務(wù)，能推送出18輛滿足貨主需求的貨車，但是貨主實際選擇運輸?shù)呢涇囍挥?輛。但是通過該決策樹算法，能推送出15輛滿足貨主需求的貨車，貨主實際選擇了9輛貨車。實驗對比如圖2所示。

4.3 實驗分析

通過兩次實驗對比，雖然通過決策樹算法減少了推送的貨車，但是貨主實際選擇貨車數(shù)量比在原始推送服務(wù)中有明顯增加。同時，推送貨車實際利用率增比可達到22%。由此可以說明，該決策樹算法能有效運用到線上貨車推送服務(wù)中，進而使貨主得到更優(yōu)質(zhì)的服務(wù)。

圖2 推送服務(wù)實驗對比圖

5 總結(jié)

本文提出了將決策樹算法應(yīng)用到線上貨車推送服務(wù)過程中的新思路，能有效預(yù)測線上貨車是否推送給貨主，進一步為貨主提供高質(zhì)量服務(wù)。該方法可以快速提取出簡潔、準確度高的關(guān)聯(lián)規(guī)則。通過分析決策樹算法，并準確預(yù)測推送的車輛，能使企業(yè)、司機以及貨主建立緊密的合作關(guān)系，從而達到“三贏”的效果。

[1]謝榕.數(shù)據(jù)挖掘與決策支持系統(tǒng)[J].計算機系統(tǒng)應(yīng)用,1999,3 (8):25-30.

[2]郭鵬文,王東.物流貨運交易網(wǎng)站信用評價模型研究[J].計算機應(yīng)用與軟件,2010,5(2):36-41.

[3]廖衛(wèi),王如龍,王瑩.決策樹算法在第三方物流企業(yè)信用評級中的研究與應(yīng)用[J].物流科技,2013,36(10):79-82.

[4]陸瑞興,楊穎,張毅.決策樹算法在物流倉庫中的研究與應(yīng)用[J].微計算機信息,2010,26(30):198-200.

[5]王永梅,胡學(xué)鋼.決策樹中ID3算法的研究[J].安徽大學(xué)學(xué)報:自然科學(xué)版,2011,(3):71-75.

[6]王國慶.決策樹算法ID3的應(yīng)用研究[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-），通訊作者，女，碩士，副教授，研究方向：計算機網(wǎng)絡(luò)與信息系統(tǒng)、模式識別。