廖雪花，唐思娩，任春華

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

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

廖雪花，唐思娩，任春華

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

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

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

1 引言

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

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

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

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

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

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

3 構(gòu)建決策樹

3.1 決策樹算法

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

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

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

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

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

3.2 決策樹的生成

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)一

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

4.2 實(shí)驗(yàn)二

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

4.3 實(shí)驗(yàn)分析

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

圖2 推送服務(wù)實(shí)驗(yàn)對(duì)比圖

5 總結(jié)

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

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

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

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

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

[5]王永梅,胡學(xué)鋼.決策樹中ID3算法的研究[J].安徽大學(xué)學(xué)報(bào):自然科學(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

四川省科技廳科技支撐項(xiàng)目（2012GZX0090，2014GZX0002）

廖雪花（1976-），通訊作者，女，碩士，副教授，研究方向：計(jì)算機(jī)網(wǎng)絡(luò)與信息系統(tǒng)、模式識(shí)別。