基于改進(jìn)的C4.5算法對車輛加速性能分類研究

陸寶紅+陳晨+曹曦文+陳眺+曾潔+史昇+宋雪樺

摘要：

車輛加速性能是衡量駕駛員對車輛駕駛舒適性的一個標(biāo)準(zhǔn)。傳統(tǒng)的車輛加速性能是通過判斷加速踏板開度衡量的，加速踏板出廠時設(shè)置為不能自動調(diào)整。采用改進(jìn)的C4.5算法對車輛加速性能分類，實現(xiàn)自動調(diào)整加速踏板開度。首先通過泰勒中值定理對C4.5算法進(jìn)行簡化，然后對車聯(lián)網(wǎng)數(shù)據(jù)進(jìn)行特征提取，生成判斷加速性能的決策樹分類規(guī)則，測試特征提取的并行化運行效率。通過特征提取后的數(shù)據(jù)集驗證了改進(jìn)的C4.5算法效率和準(zhǔn)確率。測試結(jié)果表明，改進(jìn)算法在不降低分類準(zhǔn)確率的前提下，有效提高了分類效率。

關(guān)鍵詞：

車聯(lián)網(wǎng)；HBase；MapReduce；C4.5

DOIDOI：10.11907/rjdk.172155

中圖分類號：TP391

文獻(xiàn)標(biāo)識碼：A文章編號文章編號：1672-7800（2018）001-0184-04

Abstract：Vehicle acceleration performance is a measure of the drivers comfort in driving a vehicle and improving driving comfort is a matter of concern. The traditional vehicle acceleration performance is determined by judging the accelerator pedal opening degree， and the accelerator pedal can not be adjusted automatically when the factory is set up. Therefore， the paper adopts the improved C4.5 algorithm to automatically adjust the accelerator pedal opening degree to the vehicle acceleration performance classification. Firstly， the algorithm of C4.5 is simplified by Taylors mean value theorem， and then the feature extraction of car network data is carried out to generate decision tree classification rules to judge the acceleration performance， parallel operation efficiency of test feature extraction， and finally the data extracted by feature Set to verify the efficiency and accuracy of the improved C4.5 algorithm. The test results show that the improved algorithm effectively improves the efficiency of classification and the classification accuracy is not reduced.

Key Words：car networking； HBase； MapReduce； C4.5

0引言

分類問題在數(shù)據(jù)挖掘領(lǐng)域研究和應(yīng)用較為廣泛[1]。決策樹算法分類速度快、精度高、生成的分類規(guī)則易于理解。其中，決策樹C4.5算法最為經(jīng)典，具有以下優(yōu)點：分類規(guī)則易于理解，準(zhǔn)確率較高；基本解決了ID3存在的多值偏向性問題；可以處理連續(xù)數(shù)值型屬性；可以處理缺失值；能夠在決策樹構(gòu)造過程中進(jìn)行剪枝[2]，但C4.5存在構(gòu)造決策樹效率較低的缺陷。

車輛的加速性能以及踏板的開度使用情況反映了駕駛的舒適性，提高加速性能的關(guān)鍵是如何通過整車參數(shù)判斷加速性能不足，以及油門踏板加速過深或加速過淺。通過設(shè)置閾值來判斷加速性能的傳統(tǒng)方法無法證明其合理性，閾值由于環(huán)境及人為因素影響不好準(zhǔn)確界定。本文采用改進(jìn)后的C4.5分類算法對車輛加速性能分類，提高了分類效率。根據(jù)C4.5算法分類結(jié)果對map進(jìn)行改進(jìn)，可有效提高判斷的準(zhǔn)確性，從而提高駕駛舒適性。

1加速性能分類實現(xiàn)原理

（1）MapReduce是基于批處理的分布式計算框架[3]，可并行處理大量原始數(shù)據(jù)，如合并網(wǎng)絡(luò)日志，用于模擬用戶和網(wǎng)站互動。這項工作如果用串行編程技術(shù)處理需要花費很長時間，但是使用MapReduce僅僅需要幾分鐘就可處理完。

（2）HBase是一個分布式數(shù)據(jù)庫，具有高可靠、高性能、面向列、可伸縮的特點，可在廉價PC上搭建大數(shù)據(jù)存儲集群。HBase源自于谷歌的BigTable， HDFS作為HBase的文件存儲系統(tǒng)， MapReduce可以基于HBase進(jìn)行批量數(shù)據(jù)處理， HBase采用ZooKeeper作為協(xié)調(diào)組件[4]。HBase基于橫向擴(kuò)展的設(shè)計模式，通過增加廉價的服務(wù)器增加集群的存儲能力。

2改進(jìn)的C4.5算法

（1）基于中值定理對C4.5算法進(jìn)行改進(jìn)。在C4.5算法中計算熵和信息增益時，都涉及對數(shù)的運算，每次都要調(diào)用系統(tǒng)函數(shù)，運算量較大。通過泰勒中值定理簡化計算熵和信息增益，進(jìn)而改進(jìn)C4.5算法，從效率方面提升C4.5算法性能[5]。

改進(jìn)的C4.5算法簡要說明：假設(shè)訓(xùn)練數(shù)據(jù)集S分為兩類，兩類的個數(shù)分別為M和N，假設(shè)屬性A的取值分別為a1，a2，a3，…，al；endprint

把A=ai所得的實例數(shù)據(jù)集寫做Pj，則子集中兩個類中的實例個數(shù)分別為Mi和Ni。利用泰勒中值定理經(jīng)過一系列推導(dǎo)，可以計算出按屬性A劃分S后的樣本子集信息熵為：

由此求出信息增益率為：

式（2）消除了所有的對數(shù)運算，由加減乘除四則運算組成，算法效率會明顯提升。C4.5算法通過比較不同屬性之間信息增益率的大小決定決策樹的分裂點，而不需要得到信息增益率具體大小，只要找到信息增益率最大值的對應(yīng)屬性。所以，可消除式（2）中相同的部分，也就是固定的那一部分，從而進(jìn)一步簡化信息增益率公式，提高算法運行效率。式（2）可簡化為：

（2）C4.5算法并行化實現(xiàn)。MapReduce并行編程模型包括Map和Reduce兩個部分。基于MapReduce可以實現(xiàn)大規(guī)模數(shù)據(jù)處理，能在普通的機(jī)器集群上處理大規(guī)模數(shù)據(jù)集。通過分析C4.5算法可知，決策樹生成的關(guān)鍵是屬性選擇度量計算，它占用了整個計算過程中的絕大部分計算資源?；贛apReduce對屬性選擇度量的計算是C4.5算法并行化設(shè)計的主要工作。

C4.5算法中，每個屬性的信息增益率計算相互獨立，完全可以利用并行的MapReduce統(tǒng)計和計算與信息增益率相關(guān)的每個屬性信息，最后利用這些信息快速計算信息增益率，構(gòu)造出決策樹。

C4.5算法的Map階段：在生成決策樹時，Map階段的主要任務(wù)是對大規(guī)模訓(xùn)練樣本按照決策樹中的某一層節(jié)點的劃分條件進(jìn)行切分，劃分條件就是該樹節(jié)點在決策樹中已經(jīng)生成的路徑[6]。本算法中，決策樹路徑的構(gòu)造方法是基于層次切分?jǐn)?shù)據(jù)的廣度優(yōu)先策略。假設(shè)對輸入的待劃分訓(xùn)練集D，劃分在決策樹同一層的n個節(jié)點為：D1，D2，…，Dn，則必定滿足D-D0=D1∪D2∪…∪Dn。其中，D0為已生成為葉節(jié)點的部分子訓(xùn)練集，且滿足：D1∩D2∩…∩Dn=。即Map函數(shù)主要負(fù)責(zé)以單個元組的形式分解數(shù)據(jù)，并以的形式輸出D1，D2，…，Dn，以方便在Reduce階段對其進(jìn)行統(tǒng)計計算。key由用于標(biāo)記不同樹節(jié)點的臨時ID、訓(xùn)練集的某個屬性S、該元組對應(yīng)屬性S的值s以及該元組的所屬決策類c組成，而value值為1即可。

C4.5算法的Reduce階段設(shè)計：Reduce階段的任務(wù)相對清晰，即完成對Map輸出的進(jìn)行整理，將帶有相同key值的value值累加到value-sum。同時，將統(tǒng)計好的輸出到分布式文件系統(tǒng)HDFS中，以供主程序計算各個屬性的信息增益率時使用。主控程序在讀取這些信息后，會生成一個哈希表，從哈希表中，可以容易查到對于某個節(jié)點i，在落在其中的子訓(xùn)練樣本集中，在屬性S上的取值是s且類標(biāo)號為c的樣本有多少個[7]。利用這些信息，可以很容易地計算出某個節(jié)點i在某個屬性S上的信息增益率，從而找出最佳分裂屬性。

C4.5決策樹算法的主程序功能分為兩部分：①串行構(gòu)造決策樹C4.5算法執(zhí)行；②在決策樹構(gòu)造算法需要計算信息增益率時，調(diào)用MapReduce程序在大規(guī)模訓(xùn)練樣本上進(jìn)行統(tǒng)計，獲得各個屬性的統(tǒng)計信息，然后利用這些信息計算出屬性的信息增益率[8]。

3改進(jìn)的C4.5算法對車輛加速性能分類

大部分傳感器采集的原始數(shù)據(jù)都會出現(xiàn)數(shù)據(jù)冗余或缺失等問題，為了保證數(shù)據(jù)分析結(jié)果的有效性和可靠性，必須對原始數(shù)據(jù)進(jìn)行數(shù)據(jù)清洗，也就是數(shù)據(jù)預(yù)處理。本文的原始數(shù)據(jù)包括標(biāo)號、車輛加速踏板開度和轉(zhuǎn)速。其中標(biāo)號相當(dāng)于每輛車的ID，作為每輛車唯一的標(biāo)識，時間精確到秒級。

僅僅根據(jù)原始數(shù)據(jù)無法正確判斷油門踏板加速情況，因此需要提取每輛車原始數(shù)據(jù)的數(shù)字特征作為新的屬性。原始數(shù)據(jù)包括加速踏板開度、行車速度。加速踏板開度和加速時間特征值和加速性能息息相關(guān)，行車速度用來判斷加速過程，數(shù)字特征提取的關(guān)鍵是提取加速時間的數(shù)字特征。數(shù)據(jù)預(yù)處理流程如圖1所示。

圖1為特征提取流程，主要提取加速踏板開度和加速時間的典型數(shù)字特征，通過車輛行駛速度識別車輛加速過程，并且計算加速時間的平均值以及最大值。原始數(shù)據(jù)從HBase分布式數(shù)據(jù)庫中提取。為了保證數(shù)據(jù)的可靠性，采集的數(shù)據(jù)規(guī)模要盡可能大，采集1～3天的歷史數(shù)據(jù)生成一個訓(xùn)練集。

訓(xùn)練集均為連續(xù)性屬性，類標(biāo)號分為正常加速、加速過深、加速過淺3種加速工況。開度均值指所有時間范圍內(nèi)開度的平均值，用Oavg表示；開度最大值指每次加速過程中的開度最大值的平均值，用Omax表示。時間均值指加速時間的平均值，用Tavg表示，時間最大值指加速時間的最大值，用Tmax表示。其中，開度均值取四舍五入后的近似整數(shù)，時間均值近似到小數(shù)點后面一位。

利用C4.5算法和訓(xùn)練集、測試集，可以完成車輛加速性能分類，從而判斷車輛驅(qū)動map是否需要改進(jìn)。首先，利用訓(xùn)練數(shù)據(jù)集和改進(jìn)的C4.5算法完成分類決策樹構(gòu)建，如圖2所示。

4實驗及分析

實驗數(shù)據(jù)來源于恒馳公司一年的車聯(lián)網(wǎng)傳感數(shù)據(jù)，共計1GB，上百萬條，這些數(shù)據(jù)包含不同環(huán)境、不同路況以及不同駕駛情況下采集的數(shù)據(jù)。這些數(shù)據(jù)是原始數(shù)據(jù)，不能直接用決策樹算法進(jìn)行分類，首先需要進(jìn)行數(shù)字特征提取，預(yù)處理整理出5 000多條數(shù)據(jù)集記錄。利用改進(jìn)的C4.5算法對預(yù)處理后的數(shù)據(jù)集進(jìn)行分類，實驗從算法運行效率和分類準(zhǔn)確率兩方面進(jìn)行驗證分析。將采集的數(shù)據(jù)經(jīng)過數(shù)據(jù)預(yù)處理，提取出表1中的屬性作為數(shù)據(jù)集屬

性。將數(shù)據(jù)分為訓(xùn)練集和測試集，訓(xùn)練集用來構(gòu)造決策樹，測試集用來通過計算分類準(zhǔn)確率評價決策樹。數(shù)據(jù)集按照5/5劃分，訓(xùn)練集和測試集各占50%。

4.1數(shù)據(jù)分類準(zhǔn)確率

選擇數(shù)據(jù)預(yù)處理后的5 500條數(shù)據(jù)記錄作為測試樣本，分析分類準(zhǔn)確率，分別對比傳統(tǒng)C4.5算法和改進(jìn)的C4.5算法的準(zhǔn)確率。本文將基于泰勒中值定理簡化的C4.5算法稱為MC4.5算法，基于MapReduce并行化的算法稱為HC4.5算法，基于MapReduce并行化的MC4.5算法稱為HMC4.5算法。將5 500條數(shù)據(jù)組成的樣本分為5等分，分別計算4個小數(shù)據(jù)集的分類準(zhǔn)確率，并計算各個算法的平均準(zhǔn)確率。4種算法處理車聯(lián)網(wǎng)數(shù)據(jù)的準(zhǔn)確率如表2所示。

從表2可知，對于不同的數(shù)據(jù)子集，4種算法的準(zhǔn)確率在70%左右，MC4.5、HC4.5、HMC4.5與傳統(tǒng)C4.5算法在分類準(zhǔn)確率方面基本沒有差別。

4.2數(shù)據(jù)分類效率對比實驗

取原始數(shù)據(jù)整理后的5 000條記錄，由于數(shù)據(jù)量不是太大，無法驗證C4.5算法并行化的優(yōu)勢，所以本文將5 000條記錄復(fù)制，增加數(shù)據(jù)量。C4.5算法和MC4.5算法單機(jī)運行，HC4.5算法和HMC4.5算法將在5節(jié)點的Hadoop集群上運行。比較C4.5算法和MC4.5算法以及C4.5算法和HMC4.5算法在處理不同數(shù)據(jù)量時的效率。表3記錄了幾個算法在處理不同數(shù)據(jù)量時的運行時間。為保證實驗數(shù)據(jù)的可靠性，排除外部環(huán)境干擾，實驗的結(jié)果取多次實驗的平均值。

表3給出了4種算法運行效率的對比結(jié)果。從表中可以看出，基于泰勒中值定理改進(jìn)的C4.5算法（MC4.5）在運行效率上有一定的提升，在處理相同數(shù)據(jù)集的情況下，算法執(zhí)行時間略低于傳統(tǒng)的C4.5算法，平均提升約5%左右。從基于泰勒中值定理改進(jìn)的C4.5算法（MC4.5）和其并行化實現(xiàn)的算法（HMC4.5）對比情況看，并行化實現(xiàn)的處理效率遠(yuǎn)遠(yuǎn)高于串行實現(xiàn)，幾乎隨著集群中計算節(jié)點數(shù)量成倍增長。但是效果不是很理想，因為并行算法在處理過程中會因為I/O而消耗一部分計算資源。綜上所述，在對車輛加速性能分類的應(yīng)用中，本文改進(jìn)的C4.5算法（HMC4.5）在效率方面遠(yuǎn)遠(yuǎn)高于傳統(tǒng)的C4.5算法。

5結(jié)語

本文基于改進(jìn)的C4.5算法對車輛加速性能進(jìn)行分類?；谔├罩兄刀ɡ韺鹘y(tǒng)C4.5算法進(jìn)行了改進(jìn)，簡化了屬性選擇度量的計算，從而提高了C4.5算法的運行效率。對改進(jìn)的C4.5算法并行化設(shè)計，對Map階段、Reduce階段以及主函數(shù)3個部分進(jìn)行了詳細(xì)設(shè)計，進(jìn)一步提高了算法的執(zhí)行效率。對原始數(shù)據(jù)基于MapReduce進(jìn)行特征提取，生成數(shù)據(jù)集。將改進(jìn)后的C4.5算法應(yīng)用在加速性能判斷上，生成決策樹模型，并對決策樹規(guī)則進(jìn)行闡述。與原C4.5算法相比，在分類準(zhǔn)確率沒有降低的情況下，改進(jìn)后的C4.5算法提高了分類效率。

參考文獻(xiàn)：

[1]吳旖雯.分類規(guī)則挖掘在金融中的應(yīng)用[D].杭州：浙江大學(xué)，2016.

[2]JIAWEI HAN. Data mining：concepte and techniques[M]. America：Elsevier Inc，2012.

[3]TOM， WHITE. Hadoop：the definitive guide[M]. America：O'Reilly Media，Inc，2010.

[4]LARS， GEORGE. HBase：the definitive guide[M]. America：Posts&Telecom Press，2011.

[5]WATHIQ， LAFTAH， AI YASEEN. Hybrid modified K-Means with C4.5 for intrusion dectection systems in multiagent systems[J]. The Scientific World Journal，2015（4）：33-34.

[6]PIERO， GIACOMELLI. Mahout cookbook[M]. America：Packt Publishing， 2014.

[7]毛國君，胡殿軍，謝松燕.基于分布式數(shù)據(jù)流的大數(shù)據(jù)分類模型和算法[J].計算機(jī)學(xué)報，2017（1）：9-12.

[8]CHONGQING WU. MReC4.5：C4.5 ensemble classify-cation with MapReduce[C]. Fourth ChinaGrid Annual Conference，2013：250-251.

（責(zé)任編輯：杜能鋼）endprint