C4.5算法在工程質(zhì)量決策支持系統(tǒng)中的應(yīng)用研究

侯立鐸,葉 潔

(貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,貴州 貴陽 550025)

C4.5算法在工程質(zhì)量決策支持系統(tǒng)中的應(yīng)用研究

侯立鐸,葉 潔

(貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,貴州 貴陽 550025)

由于傳統(tǒng)的水利工程質(zhì)量監(jiān)督管理系統(tǒng)只是起到監(jiān)管的作用，難以發(fā)現(xiàn)并預(yù)測工程質(zhì)量上潛在的問題。針對這一現(xiàn)象，提出了采用決策樹C4.5算法對工程質(zhì)量進(jìn)行決策支持的解決方案。首先概述了決策樹算法和C4.5算法，然后詳細(xì)闡述了決策支持系統(tǒng)中數(shù)據(jù)預(yù)處理、利用C4.5算法進(jìn)行數(shù)據(jù)建模的過程，最后根據(jù)建立好的決策樹模型開發(fā)決策支持系統(tǒng)。實(shí)驗(yàn)結(jié)果表明：用C4.5算法建立的決策樹模型準(zhǔn)確率較高，開發(fā)的決策支持系統(tǒng)能很好地應(yīng)用到實(shí)際工程質(zhì)量監(jiān)督的過程中并達(dá)到了預(yù)期目的，能較好地對未來工程質(zhì)量進(jìn)行預(yù)測，給監(jiān)督部門提供決策支持。

C4.5算法；信息熵；工程質(zhì)量；Weka

0 引 言

“百年大計(jì)，質(zhì)量第一”，工程質(zhì)量是一個受到普遍關(guān)心和廣泛重視的問題。近年來，某省的紀(jì)檢監(jiān)察部門所使用的水利工程管理系統(tǒng)大多是面向業(yè)務(wù)的，很少是面向管理決策的。而且，這些監(jiān)管部門保留了大量的水利工程質(zhì)量監(jiān)督數(shù)據(jù)。因此，監(jiān)管部門急切希望能從海量的數(shù)據(jù)中找出水利工程建設(shè)過程中容易出現(xiàn)的問題。文中旨在以工程質(zhì)量評定數(shù)據(jù)為依據(jù)，采用C4.5決策樹算法對歷史數(shù)據(jù)進(jìn)行分析處理，提取隱含在其中的有價值的信息[1]，使紀(jì)檢監(jiān)察部門對全省工程有一個全方位、多角度的認(rèn)識，以利于監(jiān)管和決策的開展和進(jìn)行。

1 決策樹與C4.5算法簡介

1.1 決策樹算法

決策樹[2]是一種分類算法，其原理是根據(jù)已有的樣本數(shù)據(jù)集進(jìn)行訓(xùn)練和學(xué)習(xí)，挖掘出一系列分類規(guī)則，然后根據(jù)這些規(guī)則對新的數(shù)據(jù)進(jìn)行分類和預(yù)測。決策樹分類模型呈現(xiàn)為一種樹形結(jié)構(gòu)。在決策樹中，非葉子節(jié)點(diǎn)代表樣本數(shù)據(jù)的各個測試屬性，每一個非葉子節(jié)點(diǎn)又可以派生出多個分支，每一個分支則代表該測試屬性可以選取的一個屬性值。葉子節(jié)點(diǎn)則代表最終的分類結(jié)果，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的每一條路徑都被稱為決策樹的一條分類規(guī)則。目前較為經(jīng)典的決策樹算法有ID3算法、C4.5算法、CART算法等[3]。決策樹可以處理連續(xù)或離散數(shù)據(jù)，也可以處理較高維的數(shù)據(jù)。決策樹模型結(jié)構(gòu)簡單、直觀、易于理解、準(zhǔn)確度高[4]。決策樹算法已廣泛應(yīng)用于各個領(lǐng)域，如醫(yī)學(xué)、天文學(xué)、金融學(xué)、生物學(xué)等[5]。

1.2 C4.5算法

C4.5算法[6]是決策樹算法中的一種，它是ID3算法[7]的改進(jìn)算法。它克服了ID3算法只能處理離散數(shù)據(jù)的缺點(diǎn)，并以信息增益率作為測試屬性選擇的標(biāo)準(zhǔn)。由于決策樹的生長是一個自上向下的過程，那么優(yōu)先選擇哪個屬性作為決策樹或者子樹的根節(jié)點(diǎn)就成為了關(guān)鍵的問題。為解決這個問題，文中引入了信息論中的信息熵[8]概念，以此來描述信息源的不確定度。C4.5算法的原理如下：

設(shè)樣本集合S中有n個樣本，假定分類屬性C有m個不同的取值，即Ci(i=1,2,…,m)。設(shè)ni為Ci中的樣本數(shù)，那么分類屬性C將樣本集S劃分為m個類的信息熵可以表示為：

式中，Pi表示任意樣本屬于分類Ci的概率，可以用ni/n來計(jì)算。

在樣本的眾多測試屬性中，選擇其中一個測試屬性A。假設(shè)A有k個不同的取值，同樣也可以利用測試屬性A將樣本集合S劃分為k個類別，即Sj(j=1,2,…,k)。此時Aij(i=1,2,…,m,j=1,2,…,k)表示為既屬于Sj分類又屬于Ci分類的樣本數(shù)量。那么屬性A劃分樣本集S導(dǎo)致的期望熵可以表示為：

其中，樣本子集Sj的信息熵可以表示為：

式中，Pij為Sj中的樣本屬于Ci分類的概率，可以用Aij/Aj來計(jì)算。

這樣就可以根據(jù)以上信息來計(jì)算屬性A的信息增益，如下式：

Gain(S,A)=E(S)-E(S,A)

有了測試屬性的信息增益，就可以利用信息增益率這個指標(biāo)來完成對測試屬性的選擇，信息增益率實(shí)際上就等于信息增益/熵。采用信息增益率可以防止決策樹傾向于那些屬性值種類較多的屬性。信息增益率的計(jì)算公式如下：

其中：

最后選取信息增益率最大的測試屬性作為決策樹根節(jié)點(diǎn)，并由這個節(jié)點(diǎn)產(chǎn)生多個分支，形成決策樹的子樹。對于每個子樹的根節(jié)點(diǎn)的選擇，則重復(fù)之前的工作，以遞歸的方式最終形成一棵完整的決策樹。C4.5算法采用后剪枝的技術(shù)[9]對生成的決策樹進(jìn)行剪枝操作，形成最終的決策樹模型。根據(jù)建立好的決策樹模型，生成一系列IF-THEN規(guī)則[10]，實(shí)現(xiàn)對樣本分類。

2 工程質(zhì)量監(jiān)督?jīng)Q策支持系統(tǒng)的應(yīng)用

2.1 數(shù)據(jù)準(zhǔn)備及數(shù)據(jù)預(yù)處理

文中研究所選取的數(shù)據(jù)為某省水利工程質(zhì)量監(jiān)督的歷史數(shù)據(jù)。以水利工程中一個單位工程即攔河壩工程為研究對象，將該工程下的子工程作為測試屬性，將該工程的評定結(jié)果作為分類屬性。由于抽取的歷史數(shù)據(jù)存在缺失值、錯誤值或者不規(guī)范等情況，因此要對數(shù)據(jù)進(jìn)行數(shù)據(jù)清洗，去掉“臟數(shù)據(jù)”。

首先，在收集數(shù)據(jù)的過程中，由于機(jī)器故障或者人為的原因，難免會有缺失數(shù)據(jù)的情況發(fā)生，因此要對缺失的數(shù)據(jù)進(jìn)行填充。此處采用最鄰近填補(bǔ)法，即選取除缺失值屬性以外的其他屬性與被填充樣本最相似的樣本，以它的屬性值來填充缺失值。其次在數(shù)據(jù)錄入的過程中，可能會出現(xiàn)誤將97分錄入成9分等類似的情況，這部分?jǐn)?shù)據(jù)也稱為噪聲數(shù)據(jù)。因此要清除噪聲數(shù)據(jù)，以免影響最后的實(shí)驗(yàn)結(jié)果。將樣本數(shù)據(jù)按照某一屬性的值從小到大進(jìn)行排列并將樣本數(shù)據(jù)四等分，將每一等分點(diǎn)的屬性值作為一個四分位數(shù)，記為Q1,Q2,Q3。一般認(rèn)為,將1.5倍Q1-Q3之外的數(shù)值作為離群點(diǎn)，所以此處將這部分?jǐn)?shù)據(jù)去除。最后，每個測試屬性的取值為紀(jì)檢監(jiān)察部門對該子工程的評分，在此將測試屬性的取值進(jìn)行數(shù)值規(guī)約[11]。對于工程的施工量，根據(jù)其大小分別規(guī)約為大型、中型、小型。將子工程評分為60-80分規(guī)約為合格，將評分為80-100分規(guī)約為優(yōu)良(子工程評分為60分以下的工程項(xiàng)目需要重新進(jìn)行質(zhì)量評定)。

為了方便下文表示，此處將各個子工程用代號表示，整理結(jié)果見表1。

最終整理出的質(zhì)量監(jiān)督數(shù)據(jù)見表2。

2.2 Weka數(shù)據(jù)挖掘平臺

Weka[12]是基于Java環(huán)境下可以用于機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘的一款開源軟件。它不但集成了多種經(jīng)典的數(shù)據(jù)挖掘算法，而且還提供了二次開發(fā)的接口，用戶可以使用自己的算法進(jìn)行數(shù)據(jù)挖掘分析。分析結(jié)果以可視化的方式展示，并可以對多種算法進(jìn)行性能測試，包括建模速度、準(zhǔn)確率等。與很多軟件類似，Weka處理的數(shù)據(jù)集為一個二維表，使用的數(shù)據(jù)集文件為ARFF格式的文件，這是一種ASCII文本文件，如圖1所示。Weka是目前較為完備的數(shù)據(jù)挖掘工具之一，受到用戶的青睞。

表1 樣本屬性及取值

表2 質(zhì)量監(jiān)督數(shù)據(jù)表

圖1 ARFF格式文件

2.3 數(shù)據(jù)建模

在對數(shù)據(jù)進(jìn)行預(yù)處理之后，在Weka平臺上利用C4.5算法對數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘建模。C4.5算法首先要確定決策樹的根節(jié)點(diǎn)，套用前文所給出的公式，可以計(jì)算出每一個測試屬性的信息增益率，如下所示：

GainRatio(施工量)=0.000 156 883 102 685 457

GainRatio(①)=0.038 032 058 076 706 7

GainRatio(②)=0.039 343 957 869 997 6

GainRatio(③)=0.037 491 840 623 890 4

GainRatio(④)=0.028 785 633 863 634 9

GainRatio(⑤)=0.051 133 153 135 862 1

GainRatio(⑥)=0.036 479 484 701 691 5

GainRatio(⑦)=0.032 572 342 234 994 7

通常選取信息增益率最大的屬性作為決策樹的根節(jié)點(diǎn)，所以這里決策樹的根節(jié)點(diǎn)是代號為⑤的屬性，也就是復(fù)合土工膜斜(心)墻土石壩。將此屬性兩個取值作為決策樹的兩個分支，重復(fù)之前的操作。左右兩棵子樹同樣選出信息增益率最大的測試屬性作為子樹的根節(jié)點(diǎn)，遞歸生成決策樹的左子樹和右子樹，最后采用后剪枝的技術(shù)對決策樹進(jìn)行剪枝。為了進(jìn)一步精簡決策樹，此處去掉葉子節(jié)點(diǎn)實(shí)例數(shù)小于100的節(jié)點(diǎn)，來完成決策樹的建模過程。

決策樹模型建立完成之后，還要利用十折交叉驗(yàn)證[13]來測試決策樹分類的準(zhǔn)確率。即將訓(xùn)練數(shù)據(jù)平均分成10份，輪流將其中的1份作為測試數(shù)據(jù)，將其余的9份作為訓(xùn)練數(shù)據(jù)。每次試驗(yàn)都會得出決策樹的準(zhǔn)確率，將10次的結(jié)果取平均值，作為最終結(jié)果，以使結(jié)果更加精確。通過以上步驟建立的決策樹模型如圖2所示。

圖2 決策樹模型

算法的執(zhí)行結(jié)果如圖3所示。

圖3 算法執(zhí)行結(jié)果圖

結(jié)果顯示：對10 000個實(shí)例進(jìn)行建模，得出的決策樹共有27個節(jié)點(diǎn)，其中葉子節(jié)點(diǎn)14個。正確分類的實(shí)例數(shù)為9 129個，錯誤的分類實(shí)例為871個，建模時間為0.19 s，模型的準(zhǔn)確率為91.29%。

2.4 決策支持系統(tǒng)

工程質(zhì)量監(jiān)督?jīng)Q策支持系統(tǒng)[14]設(shè)計(jì)的主要目的是使施工單位能夠了解到如何提高子工程的建設(shè)質(zhì)量，才可以使最終的評定結(jié)果達(dá)到優(yōu)良的評級。根據(jù)決策樹模型得到一系列的IF-THEN規(guī)則，選取該模型中最終分類為優(yōu)良的4個規(guī)則進(jìn)行展示，其結(jié)果如下：

IF ⑤=合格 AND ②=優(yōu)良 AND ⑥=優(yōu)良 AND ⑦=優(yōu)良 AND ④=優(yōu)良 AND ①=優(yōu)良 THEN 評定結(jié)果=優(yōu)良

IF ⑤=優(yōu)良 AND ①=合格 AND ③=優(yōu)良 AND ④=優(yōu)良 AND ⑦=優(yōu)良THEN 評定結(jié)果=優(yōu)良

IF ⑤=優(yōu)良 AND ①=優(yōu)良 AND ⑥=優(yōu)良 THEN 評定結(jié)果=優(yōu)良

IF ⑤=優(yōu)良 AND ①=優(yōu)良 AND ⑥=合格 AND ②=優(yōu)良 AND ⑦=優(yōu)良 THEN 評定結(jié)果=優(yōu)良

根據(jù)決策樹得出的IF-THEN規(guī)則進(jìn)行決策支持系統(tǒng)的設(shè)計(jì)，其界面展示如圖4所示。

圖4 決策支持系統(tǒng)界面

監(jiān)管部門只要填選相應(yīng)的子工程的評定等級并點(diǎn)擊預(yù)測按鈕，即可在結(jié)果展示區(qū)域內(nèi)看到預(yù)測結(jié)果。在工程建設(shè)質(zhì)量的改進(jìn)過程中，父節(jié)點(diǎn)屬性的優(yōu)先級要高于子節(jié)點(diǎn)屬性的優(yōu)先級。相關(guān)建設(shè)單位只要按照這一關(guān)系逐一改進(jìn)子工程的工程質(zhì)量，就可以使整個工程的評定結(jié)果達(dá)到優(yōu)良等級，進(jìn)而做到對風(fēng)險的預(yù)測和避免。

3 結(jié)果分析

在創(chuàng)建決策樹的根節(jié)點(diǎn)時，代號為⑤的子工程即復(fù)合土工膜斜(心)墻土石壩計(jì)算出的信息增益率最高，因此將該子工程作為決策樹的根節(jié)點(diǎn)。也就是說該子工程相對于其他子工程來講更為重要。并且模型最后給出的4條IF-THEN規(guī)則中，有3條是建立在該子工程評分為優(yōu)良的情況下的。所以監(jiān)管部分應(yīng)著力加強(qiáng)這一子工程的建設(shè)監(jiān)督，這樣可以使整個工程項(xiàng)目朝著優(yōu)良的方向發(fā)展。在生成的模型中，工程量這一測試屬性并沒有出現(xiàn)在決策樹中，說明這一測試屬性對整個工程質(zhì)量的走向影響并不是很大，因此無論工程大小，監(jiān)管部門都應(yīng)一視同仁。

4 結(jié)束語

文中通過C4.5算法對水利工程質(zhì)量監(jiān)督的歷史數(shù)據(jù)進(jìn)行建模，生成的決策樹模型簡單易懂，準(zhǔn)確率較高，可以有效地幫助工程建設(shè)單位改進(jìn)工程質(zhì)量。監(jiān)管部門通過決策支持系統(tǒng)也可以對未來的工程質(zhì)量進(jìn)行預(yù)測，以達(dá)到防患于未然的目的。但C4.5算法在進(jìn)行數(shù)據(jù)挖掘建模時，需要多次掃描樣本集并進(jìn)行排序，使得該算法在建模的速度上有一定的缺陷。今后的工作主要是針對C4.5算法的這一缺點(diǎn)進(jìn)行改進(jìn)，使之達(dá)到更好的效果。

[1] 羅 可,林睦綱,郗東妹.數(shù)據(jù)挖掘中分類算法綜述[J].計(jì)算機(jī)工程，2005，31(1)：3-5.

[2] 李 航.統(tǒng)計(jì)學(xué)習(xí)方法[M].北京：清華大學(xué)出版社，2012.

[3] 陳文偉，鄧 蘇，張維明.數(shù)據(jù)開采與知識發(fā)現(xiàn)綜述[M].北京：機(jī)械工業(yè)出版社，2003.

[4] Tsang S,Kao B,Yip K Y,et al.Decision trees for uncertain data[C]//Proc of IEEE international conference on data engineering.Shanghai,IEEE,2009:441-444.

[5] 桂現(xiàn)才，彭 宏，王小華.C4.5算法在保險客戶流失分析中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2005，41(17)：197-199.

[6] 劉 兵.Web數(shù)據(jù)挖掘[M].俞 勇，譯.北京：清華大學(xué)出版社，2009.

[7] Chen Jin,Luo Delin,Mu Fenxiang.An improved ID3 decision tree algorithm[C]//Proc of 4th international conference on IEEE computer science and education.Chengdu:IEEE,2009:127-130.

[8] Barnum H,Barrett J,Clark L O,et al.Entropy and information causality in general probabilistic theories[J].New Journal of Physics,2010,12(3):1-32.

[9] Kantardzic M.Data mining:concepts,models,and algorithms[M].New York:John Wiley and IEEE Press,2003.

[10] Zhou Chi,Xiao Weimin,Tirpak T M,et al.Evolving accurate and compact classification rules with gene expression programming[J].IEEE Transactions on Evolutionary Computation,2003,7(6):519-531.

[11] Han Jiawei,Kamber M.數(shù)據(jù)挖掘概念與技術(shù)[M].范 明，孟小峰,譯.北京：機(jī)械工業(yè)出版社，2012.

[12] 孟曉明，陳慧萍，張 濤.基于WEKA平臺的Web事務(wù)聚類算法的研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009，30(6)：1332-1334.

[13] 牛曉太.基于KNN算法和10折交叉驗(yàn)證法的支持向量選取算法[J].華中師范大學(xué)學(xué)報:自然科學(xué)版，2014,48(3):335-338.

[14] 陳文偉，廖建文.決策支持系統(tǒng)及其開發(fā)[M].第3版.北京：清華大學(xué)出版社，2008.

Applied Research of C4.5 Algorithm in Engineering Quality Decision Support System

HOU Li-duo,YE Jie

(College of Computer Science and Technology,Guizhou University,Guiyang 550025,China)

As traditional hydraulic engineering quality supervision and management system just playing the role of regulation,it is difficult to detect and predict potential problems on the quality of the project.Aiming at this phenomenon,a solution about using the C4.5 algorithm to make decision on project quality was proposed.First provided an overview of the algorithm and C4.5 decision tree algorithm and then elaborated data preprocessing and the process about data modeling used with C4.5 algorithm in decision support system.Finally developed the decision support system according to the decision tree model.The experimental results show that the decision tree model established by C4.5 algorithm has high accuracy.The developed decision support system can be well applied to practical engineering quality supervision process and achieves the desired results.It can be better for the future project quality prediction,providing decision support to the supervision department.

C4.5 algorithm;entropy;project quality;Weka

2015-05-25

2015-08-28

時間：2016-01-26

貴州省科技計(jì)劃項(xiàng)目(黔科合GY字(2011)3050)作者簡介：侯立鐸(1988-)，男，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘技術(shù)；葉 潔，副教授，研究方向?yàn)閿?shù)據(jù)庫與應(yīng)用系統(tǒng)。

http://www.cnki.net/kcms/detail/61.1450.TP.20160126.1521.066.html

TP301.6

A

1673-629X(2016)02-0132-04

10.3969/j.issn.1673-629X.2016.02.030