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

李建磊，劉鳳娟

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

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

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

1 ID3算法

1.1 ID3算法的概述

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

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

1.2 機車檢修的影響因素

通常決策者可以根據經驗知識來確定一些影響因素。而在機車檢修計劃的制定中，主要考慮：基本影響因子X、走行公里因素Y以及動態因素Z對機車檢修規定的影響，即：檢修評定因子W= F（X，Y，Z）?，F假定一輛較好的機車運行在中等路況下，機車的基本影響因子是0.5?；居绊懸蜃涌刹閳D1。根據基本影響因子、走行公里因素和動態因素等，再加上機務段實際的狀況統計，得出檢修評定因子。具體影響因素情況見表1。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表2 機車檢修數據集

2 改進的ID3算法在機車檢修中的實現

2.1 實現方法

（1）建立機車檢修的數據集，將數據編排小組，也就是建模的過程；（2）對數據集分析，確定類別表示屬性和決策屬性集；（3）生成決策樹，對決策樹進行適當的剪枝。

2.2 具體應用

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

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

“檢修內容”的信息增益：

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

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

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

2.2.2 第2級改進

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

2.2.3 機車檢修決策樹

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

圖2 機車檢修決策樹

2.2.4 頻繁故障的提取規則

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

if（ 部件為“轉向架”、班組為“臺車”、小組為“分解組裝組” ）then檢修內容；

if（ 部件為“轉向架”、班組為“臺車”、小組為“輔件組” ）then檢修內容；

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

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

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

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

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

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

2.2.5 頻繁的機車檢修路徑

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

a.大電機→牽引電動機→組裝組→檢修內容；

b.臺車→轉向架→組裝分解組→檢修內容；

c.柴組裝→柴油機→左側組→檢修內容；

d.柴組裝→柴油機→底部組→檢修內容；

e.柴分解→柴油機→前后端→檢修內容。

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

3 結束語

建立機車檢修數據集，找出頻繁發生的故障信息，達到“早預測、早報警、早檢修”的目的，使機車檢修便捷，提高鐵路運輸的安全。本來可以通過查找歷史數據來人工或計算機統計處理，但沒有一個相對合理的理論解釋，通過數據挖掘的方法進行合理分類，提供了一個理論性的支撐。

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

[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 .巴斯蒂安.數據倉庫與數據挖掘[M].北京：冶金工業出版社，2003.

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

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

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