侯立鐸,葉 潔

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

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

侯立鐸,葉 潔

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

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

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

0 引 言

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

1 決策樹(shù)與C4.5算法簡(jiǎn)介

1.1 決策樹(shù)算法

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

1.2 C4.5算法

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

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

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

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

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

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

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

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

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

其中：

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

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ù)。以水利工程中一個(gè)單位工程即攔河壩工程為研究對(duì)象，將該工程下的子工程作為測(cè)試屬性，將該工程的評(píng)定結(jié)果作為分類屬性。由于抽取的歷史數(shù)據(jù)存在缺失值、錯(cuò)誤值或者不規(guī)范等情況，因此要對(duì)數(shù)據(jù)進(jìn)行數(shù)據(jù)清洗，去掉“臟數(shù)據(jù)”。

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

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

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

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

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

表1 樣本屬性及取值

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

圖1 ARFF格式文件

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

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

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

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

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

圖2 決策樹(shù)模型

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)果分析

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

4 結(jié)束語(yǔ)

文中通過(guò)C4.5算法對(duì)水利工程質(zhì)量監(jiān)督的歷史數(shù)據(jù)進(jìn)行建模，生成的決策樹(shù)模型簡(jiǎn)單易懂，準(zhǔn)確率較高，可以有效地幫助工程建設(shè)單位改進(jìn)工程質(zhì)量。監(jiān)管部門(mén)通過(guò)決策支持系統(tǒng)也可以對(duì)未來(lái)的工程質(zhì)量進(jìn)行預(yù)測(cè)，以達(dá)到防患于未然的目的。但C4.5算法在進(jìn)行數(shù)據(jù)挖掘建模時(shí)，需要多次掃描樣本集并進(jìn)行排序，使得該算法在建模的速度上有一定的缺陷。今后的工作主要是針對(duì)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ù)開(kāi)采與知識(shí)發(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算法在保險(xiǎn)客戶流失分析中的應(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平臺(tái)的Web事務(wù)聚類算法的研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009，30(6)：1332-1334.

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

[14] 陳文偉，廖建文.決策支持系統(tǒng)及其開(kāi)發(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

時(shí)間：2016-01-26

貴州省科技計(jì)劃項(xiàng)目(黔科合GY字(2011)3050)作者簡(jiǎn)介：侯立鐸(1988-)，男，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘技術(shù)；葉 潔，副教授，研究方向?yàn)閿?shù)據(jù)庫(kù)與應(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