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

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

摘要：

車輛加速性能是衡量駕駛員對車輛駕駛舒適性的一個標準。傳統的車輛加速性能是通過判斷加速踏板開度衡量的，加速踏板出廠時設置為不能自動調整。采用改進的C4.5算法對車輛加速性能分類，實現自動調整加速踏板開度。首先通過泰勒中值定理對C4.5算法進行簡化，然后對車聯網數據進行特征提取，生成判斷加速性能的決策樹分類規則，測試特征提取的并行化運行效率。通過特征提取后的數據集驗證了改進的C4.5算法效率和準確率。測試結果表明，改進算法在不降低分類準確率的前提下，有效提高了分類效率。

關鍵詞：

車聯網；HBase；MapReduce；C4.5

DOIDOI：10.11907/rjdk.172155

中圖分類號：TP391

文獻標識碼：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引言

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

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

1加速性能分類實現原理

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

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

2改進的C4.5算法

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

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

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

由此求出信息增益率為：

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

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

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

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

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

C4.5決策樹算法的主程序功能分為兩部分：①串行構造決策樹C4.5算法執行；②在決策樹構造算法需要計算信息增益率時，調用MapReduce程序在大規模訓練樣本上進行統計，獲得各個屬性的統計信息，然后利用這些信息計算出屬性的信息增益率[8]。

3改進的C4.5算法對車輛加速性能分類

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

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

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

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

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

4實驗及分析

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

性。將數據分為訓練集和測試集，訓練集用來構造決策樹，測試集用來通過計算分類準確率評價決策樹。數據集按照5/5劃分，訓練集和測試集各占50%。

4.1數據分類準確率

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

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

4.2數據分類效率對比實驗

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

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

5結語

本文基于改進的C4.5算法對車輛加速性能進行分類。基于泰勒中值定理對傳統C4.5算法進行了改進，簡化了屬性選擇度量的計算，從而提高了C4.5算法的運行效率。對改進的C4.5算法并行化設計，對Map階段、Reduce階段以及主函數3個部分進行了詳細設計，進一步提高了算法的執行效率。對原始數據基于MapReduce進行特征提取，生成數據集。將改進后的C4.5算法應用在加速性能判斷上，生成決策樹模型，并對決策樹規則進行闡述。與原C4.5算法相比，在分類準確率沒有降低的情況下，改進后的C4.5算法提高了分類效率。

參考文獻：

[1]吳旖雯.分類規則挖掘在金融中的應用[D].杭州：浙江大學，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]毛國君，胡殿軍，謝松燕.基于分布式數據流的大數據分類模型和算法[J].計算機學報，2017（1）：9-12.

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

（責任編輯：杜能鋼）endprint