改進的ID3算法在機車檢修作業(yè)流程中的應用

李建磊，劉鳳娟

（1.蘭州交通大學 機電技術研究所，蘭州 730070；2.西安鐵路職業(yè)技術學院 電氣工程系，西安 710014）

隨著鐵路高速化、重載化、信息化的發(fā)展，機車檢修的任務變得越來越重，如何從龐大的故障數(shù)據(jù)中提取出有價值的檢修信息，顯得格外重要。機車檢修要嚴格按照鐵道部機務局頒布的標準，如機統(tǒng)28、機統(tǒng)6等標準，這樣才能夠全面掌握機車檢修作業(yè)情況。但是，面對繁重的檢修任務，特別是針對一些頻繁發(fā)生的故障，就要通過合理的方法進行分類，找到頻繁檢修路徑，予以重點關注，進而提高檢修效率。

在數(shù)據(jù)挖掘中，分類挖掘技術的方法很多，其中ID3算法是決策樹方法中最常用的具體實現(xiàn)算法。最先由Quinlan[1]在1986年提出，后來許多研究者發(fā)現(xiàn)ID3算法具有“偏向于取值較多的屬性，產(chǎn)生了大數(shù)據(jù)掩蓋小數(shù)據(jù)的現(xiàn)象”的缺點，為了克服這一缺點， Konenko等人提出了“限制決策樹為二叉樹”的方法，曲開社等[2]提出了添加“用戶興趣度”的方法，這些都是對ID3算法的改進。文章結(jié)合機車檢修計劃中的“基本影響因子”和“檢修評定因子”來改進ID3算法，對機車檢修作業(yè)流程進行合理的優(yōu)化，達到在短時間內(nèi)獲得有價值的機車檢修作業(yè)內(nèi)容的目的。

1 ID3算法

1.1 ID3算法的概述

ID3算法是決策樹生成最常用的具體實現(xiàn)算法。其算法采用信息論中熵的概念，用信息增益（Information Gain）作為決策屬性分類判別能力的度量，進行決策樹節(jié)點屬性的選擇。在決策樹的生成過程中選擇具有最大信息增益的決策屬性作為決策樹的當前節(jié)點。通過這種方式選擇節(jié)點屬性可以保證決策樹具有最小的分支數(shù)量，使得到的決策樹冗余最小。但是，這種算法往往在樹節(jié)點分支階段趨向于取值較多的屬性，許多學者懷疑其分類效果。例如，文獻[2]中指出的“穿衣指數(shù)”是一個主觀因素，相同的天氣情況下，老、弱、幼相對于年輕、健壯的人群來說，可能會穿的多一些。雖然“穿衣指數(shù)”的取值較多，信息增益較大，而依據(jù)實情不能作為決策樹的根節(jié)點。

在機車檢修中，一般來說，存在繁多的檢修內(nèi)容，其取值最多，按照ID3算法，得到屬性“檢修內(nèi)容”的信息增益最大， 以此作為決策樹的根節(jié)點。實際機車檢修作業(yè)流程步驟是：（1）找到哪些部件有故障；（2）把檢修作業(yè)分配到相應的班組；（3）班組的工長再把具體的檢修任務下達到每個小組中。總之，在調(diào)度人員下達任務后，檢修作業(yè)流程是按照班組來具體施修的，而不是按照具體的施修內(nèi)容來進行作業(yè)的。這是作業(yè)流程的具體步驟。

1.2 機車檢修的影響因素

通常決策者可以根據(jù)經(jīng)驗知識來確定一些影響因素。而在機車檢修計劃的制定中，主要考慮：基本影響因子X、走行公里因素Y以及動態(tài)因素Z對機車檢修規(guī)定的影響，即：檢修評定因子W= F（X，Y，Z）。現(xiàn)假定一輛較好的機車運行在中等路況下，機車的基本影響因子是0.5。基本影響因子可查圖1。根據(jù)基本影響因子、走行公里因素和動態(tài)因素等，再加上機務段實際的狀況統(tǒng)計，得出檢修評定因子。具體影響因素情況見表1。

表1 某機務段中修的影響因素

結(jié)合“基本影響因子”和“檢修評定因子”，對ID3算法進行改進，目的是減少取值較多的屬性對決策樹形成的影響，進而更加符合實際的機車檢修作業(yè)流程。

1.3 改進ID3算法的具體計算方法

設S是數(shù)據(jù)訓練集，S中類別標識屬性有n個不同取值，即定義了n個類Ci， i =1，2，...，n，Ri為數(shù)據(jù)集S中屬于Ci類的子集，用ri表示子集Ri中元組中數(shù)量。

集合S中的類別表示屬性的期望信息量：

式中，Pi是表示任意樣本屬于Ci類的概率。

假設屬性A中共有m個不同的取值{a1，a2，...,am}，則通過屬性A的取值可將數(shù)據(jù)集S劃分為m個子集，用sj表示數(shù)據(jù)集S中屬性A的取值為aj的子集，j=1，2，...，m。

如果A被作為決策屬性，則這些子集將對應點的不同分枝。用sij表示sj子集中屬于Ci類元組的數(shù)量，則屬性A對于分類Ci的熵：

式中，加入基本影響因子α，來增大機車檢修中相關屬性因素的權重，減小取值較多屬性的影響。此為第1級的改進。

對于屬性A每個取值對分類Ci期望信息量：

式中，Pij表示在sj子集中屬于Ci類的比重。

通過上述可得到對屬性A作為決策分類屬性的信息增益：

式中，加入檢修評定因子β，來對每一個屬性進行機車檢修的綜合評定。此為第2級的改進。

通過兩級改進，有效地避免ID3算法決策樹節(jié)點偏向于取值較多的屬性，從而能夠得到與實際機車檢修作業(yè)流程相符的較為合理的檢修步驟。

表2 機車檢修數(shù)據(jù)集

2 改進的ID3算法在機車檢修中的實現(xiàn)

2.1 實現(xiàn)方法

（1）建立機車檢修的數(shù)據(jù)集，將數(shù)據(jù)編排小組，也就是建模的過程；（2）對數(shù)據(jù)集分析，確定類別表示屬性和決策屬性集；（3）生成決策樹，對決策樹進行適當?shù)募糁Α?/p>

2.2 具體應用

取表2（數(shù)據(jù)集進行了預整理）作為訓練集，進行決策樹的建立，將“無故障”視為正例集，“有故障”視為反例集。選取“故障狀態(tài)”為類別表示屬性，進行ID3算法的改進，探討機車檢修中頻繁發(fā)生的故障信息，找到重點關注的機車檢修路徑。

2.2.1 第1級改進

通過計算得到每一屬性的信息增益為：

“部件”的信息增益：

IG(部件)=I(r1, r2)－E(部件)=0.0303

“班組”的信息增益：

IG(班組)=I(r1, r2)－E(班組)=0.0477

“小組”的信息增益：

IG(小組)=I(r1, r2)－E(小組)=0.1954

“檢修內(nèi)容”的信息增益：

IG(檢修內(nèi)容)=I(r1, r2)－E(檢修內(nèi)容)=0.9710

對機車檢修中的相關屬性，且取值較多的屬性進行改進，屬性“小組”相對于“部件”“班組”的取值較多，在“小組”熵值公式中加入基本影響因子α=0.5。

這樣就減小了取值較多屬性對于生成目標決策樹的影響，避免了大數(shù)據(jù)掩蓋小數(shù)據(jù)的現(xiàn)象。通過第1級的改進，避免了 ID3算法偏向于取值較多的屬性。

2.2.2 第2級改進

屬性“檢修內(nèi)容”的信息增益最大，根據(jù)機車檢修作業(yè)流程的具體狀況，需要加以改進，符合實際情況。檢修評定因子，對每一個屬性的影響是不一樣的。“部件”、“班組”、“小組”都對檢修作業(yè)有直接的影響，而“檢修內(nèi)容”是檢修的結(jié)果，對作業(yè)流程來說，不會產(chǎn)生影響。定義“檢修內(nèi)容”的檢修評定因子β=－∞，得到“檢修內(nèi)容”的信息增益：通過第2級改進，對屬性不能夠影響作業(yè)流程的環(huán)節(jié)，從定義檢修評定因子上合理進行篩選，提高了有效屬性對于機車檢修作業(yè)流程的重要度。

2.2.3 機車檢修決策樹

因為屬性“班組”的信息增益最大，所以以此作為根節(jié)點，建立決策樹。得到機車檢修決策樹，如圖2。

圖2 機車檢修決策樹

2.2.4 頻繁故障的提取規(guī)則

if（ 部件為“牽引電動機”、班組為“大電機”、小組為“組裝組” ）then檢修內(nèi)容；

if（ 部件為“轉(zhuǎn)向架”、班組為“臺車”、小組為“分解組裝組” ）then檢修內(nèi)容；

if（ 部件為“轉(zhuǎn)向架”、班組為“臺車”、小組為“輔件組” ）then檢修內(nèi)容；

if（ 部件為“柴油機”、班組為“柴組裝”、小組為“左側(cè)組” ）then檢修內(nèi)容；

if（ 部件為“柴油機”、班組為“柴組裝”、小組為“右側(cè)組” ）then檢修內(nèi)容；

if（ 部件為“柴油機”、班組為“柴組裝”、小組為“底部組” ）then檢修內(nèi)容；

if（ 部件為“柴油機”、班組為“柴組裝”、小組為“中部組” ）then檢修內(nèi)容；

if（ 部件為“柴油機”、班組為“柴分解”、小組為“左側(cè)組” ）then檢修內(nèi)容；

if（ 部件為“柴油機”、班組為“柴分解”、小組為“前后端” ）then檢修內(nèi)容。

2.2.5 頻繁的機車檢修路徑

設定頻繁系數(shù)為0.2，進行剪枝后，從提取規(guī)則中得出符合條件的頻繁機車檢修路徑：

a.大電機→牽引電動機→組裝組→檢修內(nèi)容；

b.臺車→轉(zhuǎn)向架→組裝分解組→檢修內(nèi)容；

c.柴組裝→柴油機→左側(cè)組→檢修內(nèi)容；

d.柴組裝→柴油機→底部組→檢修內(nèi)容；

e.柴分解→柴油機→前后端→檢修內(nèi)容。

文章中所選的數(shù)據(jù)集中，這5條路徑是比較繁忙，是機車檢修作業(yè)流程中重點作業(yè)路徑，在有限的作業(yè)情況下，可以重點關注。

3 結(jié)束語

建立機車檢修數(shù)據(jù)集，找出頻繁發(fā)生的故障信息，達到“早預測、早報警、早檢修”的目的，使機車檢修便捷，提高鐵路運輸?shù)陌踩１緛砜梢酝ㄟ^查找歷史數(shù)據(jù)來人工或計算機統(tǒng)計處理，但沒有一個相對合理的理論解釋，通過數(shù)據(jù)挖掘的方法進行合理分類，提供了一個理論性的支撐。

文章在檢修歷史數(shù)據(jù)中，針對繁重的機車檢修任務，從數(shù)據(jù)挖掘的角度考慮，找出繁忙路徑，特別是在時間緊張情況下，迅速調(diào)集人力、物力來完成檢修作業(yè)。這對機車檢修作業(yè)是一種新的探究。

[1]Quinlan J R. Induction of decision tree[J]．Machine Learning，Springer，1986，1（1）：81-106．

[2]曲開社，成文麗，王俊紅. ID3算法的一種改進算法[J]. 計算機工程與應用，2003（25）：104-107.

[3]武 森，高學東，M .巴斯蒂安.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘[M].北京：冶金工業(yè)出版社，2003.

[4]王銳鋒，趙俊霞，齊金平，等. 鐵路機車檢修計劃生成系統(tǒng)的研究[J]. 計算機應用與軟件，2009，26（2）：175-177.

[5]李賢鵬，何松華，趙孝敏，等. 改進的ID3算法在客戶流失預測中的應用[J].計算機工程與應用，2009，45（10）：242-244.

[6]朱 明. 數(shù)據(jù)挖掘[M]. 2版 合肥：中國科學技術大學出版社，2008，11.