唐露新 張強(qiáng)武

（廣東工業(yè)大學(xué)信息工程學(xué)院 廣州 510006）

1 引言

數(shù)據(jù)挖掘就是在大量數(shù)據(jù)中提出或挖掘知識(shí)［1～2］。決策樹(shù)作為數(shù)據(jù)挖掘的一種預(yù)測(cè)分析模型，以高效的分析能力、簡(jiǎn)單明了的特點(diǎn)成為數(shù)據(jù)挖掘中最為廣泛的一種歸納分析方法。目前構(gòu)建決策樹(shù)的方法主要有ID3、C4.5、C5.0、CART（Classification and Regression Tree，分類回歸樹(shù)）等。ID3采用信息熵作為屬性選擇標(biāo)準(zhǔn)進(jìn)行構(gòu)建，其缺點(diǎn)是標(biāo)準(zhǔn)易于偏向取值多的候選屬性；C4.5繼承ID3全部?jī)?yōu)點(diǎn)發(fā)展而來(lái)，以信息增益率來(lái)選擇決策屬性克服了ID3多值偏向的問(wèn)題，但是對(duì)于大數(shù)據(jù)處理其效率較低，內(nèi)存消耗大；C5.0針對(duì)C4.5缺點(diǎn)，采用Boosting方式提高模型準(zhǔn)確率和計(jì)算速度，減少內(nèi)存資源［3］，適處理大數(shù)據(jù)集，但相對(duì)C4.5其方法難預(yù)測(cè)連續(xù)性的字段，此外類別多時(shí)易出錯(cuò)，其分類屬性也非全局最優(yōu)；CART樹(shù)是一種二叉樹(shù)，其優(yōu)點(diǎn)是它將模型的驗(yàn)證和最優(yōu)通用樹(shù)的發(fā)現(xiàn)嵌在了算法中，能夠克服過(guò)適應(yīng)性，得到最適應(yīng)未來(lái)數(shù)據(jù)的樹(shù)［4］。

SMT（Surface Mount Technology，表貼封裝技術(shù)）作為現(xiàn)代技術(shù)電子制造產(chǎn)業(yè)發(fā)展的關(guān)鍵技術(shù)之一，其工藝流程包括錫膏印刷、元件貼片和回流焊。合理地工藝流程中刮刀壓力、回流溫度、離板間隙等參數(shù)，保證良品率，減少損失，一直是當(dāng)前SMT焊接質(zhì)量技術(shù)研究的熱點(diǎn)與難點(diǎn)［5～6］。近年來(lái)，在SMT生產(chǎn)工藝中，數(shù)據(jù)挖掘技術(shù)逐漸被用于分析焊接過(guò)程中工藝參數(shù)對(duì)產(chǎn)品質(zhì)量的影響［7～8］。數(shù)據(jù)挖掘中的決策樹(shù)算法可以根據(jù)SMT的工藝參數(shù)分析預(yù)測(cè)出最終的焊接質(zhì)量，本文針對(duì)決策樹(shù)C4.5算法的特點(diǎn)，提出一種改進(jìn)算法，用于改善SMT焊接工藝中產(chǎn)品的質(zhì)量。

2 C4.5決策樹(shù)算法及其改進(jìn)算法

決策樹(shù)是用于分類和預(yù)測(cè)的主要技術(shù)，其過(guò)程是從一組無(wú)規(guī)則的實(shí)例推理出決策樹(shù)表示形式的分類規(guī)則。作為一種樹(shù)形結(jié)構(gòu)，采用自頂向下的遞歸方式，在部分搜索空間尋找搜索決絕方案［9］。

2.1 C4.5算法的實(shí)現(xiàn)

C4.5算法的核心思想是選擇信息增益率最大的屬性作為決策樹(shù)分類屬性，然后逐次構(gòu)造決策樹(shù)的分枝。其算法過(guò)程為：設(shè)實(shí)例訓(xùn)練集X，該實(shí)例具有m種屬性可分為n類，分別記為｛A1，A2，…，Am｝，｛C1，C2，…，Cn｝。由屬性可將訓(xùn)練集劃分為m個(gè)子集｛X1，X2，…，Xm｝，由類別可將其劃分為n個(gè)子集｛X1，X2，…，Xn｝，其中Xi對(duì)應(yīng)的屬性為Ai（i＝1，2，…，m），Xj對(duì)應(yīng)的類別為Cj（j＝1，2，…，n）。假設(shè)｜Ai｜代表Ai的個(gè)數(shù)，｜Cj｜為Cj的實(shí)例個(gè)數(shù)，｜Xij｜表示屬性為Ai具有類別Cj的個(gè)數(shù)。

1）一個(gè)實(shí)例屬性為Ai的概率為

2）一個(gè)實(shí)例屬于j類的概率為

3）屬性Ai的實(shí)例中，含有類別Cj的概率為

由式（2）可求出決策樹(shù)劃分C的不確定度為

由式（1）和式（4）得，每個(gè)屬性為Ai的葉節(jié)點(diǎn)的分類信息熵為：

屬性A的信息增益率為屬性A的分類互信息量：

屬性A的分裂信息為

前面式（1）～式（7）實(shí)現(xiàn)ID3算法。C4.5算法在ID3算法基礎(chǔ)上，采用“分而治之”的策略，用信息增益率代替信息增益對(duì)屬性進(jìn)行分類選擇，克服了ID3算法中因信息增益導(dǎo)致在選擇屬性時(shí)偏向多值屬性的不足。這種策略只是構(gòu)造樹(shù)選取內(nèi)部節(jié)點(diǎn)的一種局部最優(yōu)探索方式，雖然有一比較可觀的準(zhǔn)確率，但可能達(dá)不到全局最優(yōu)結(jié)果［10］。此外，在C4.5算法中，大類分類信息可能隱藏不夠明顯的小類分類信息，盡管改用信息增益率的方式解決了多值偏向問(wèn)題但其信息理論含義變模糊且可解釋性降低［11］。對(duì)此，本文引入平衡因子，對(duì)C4.5算法進(jìn)行了算法改進(jìn)。

2.2 C4.5算法的改進(jìn)

改進(jìn)的C4.5算法是針對(duì)屬性選擇標(biāo)準(zhǔn)進(jìn)行改進(jìn)，C4.5改進(jìn)算法的基本原理：在實(shí)例集進(jìn)行最佳屬性劃分時(shí)，通過(guò)在屬性選擇度量中引入平衡因子替代傳統(tǒng)C4.5算法中只依據(jù)最高信息增益率進(jìn)行屬性選擇，進(jìn)而降低某些屬性的信息熵，調(diào)整屬性值得信息增益率，對(duì)決策樹(shù)進(jìn)行改善。在符合屬性A平衡條件下，其修正的分類信息熵為

用增益比率代替增益，其增益比率為

修正的信息增益為：

修正的信息增益率為：

平衡因子λ定義為：

由平衡因子λ的定義知，其值取決于當(dāng)前分裂

改進(jìn)型C4.5算法的偽代碼描述如下：

算法：由給定訓(xùn)練集X生成決策樹(shù)；

輸入：具有類別C區(qū)分的訓(xùn)練集X；訓(xùn)練集屬性集A；

屬性選擇函數(shù)F（A，X）：最佳分裂屬性選擇依據(jù)信息增益率；

輸出：一棵決策樹(shù)

1）創(chuàng)建一個(gè)節(jié)點(diǎn)N；

2）If實(shí)例X都為同一類CThenN作為葉節(jié)點(diǎn)返回，并記N為C類；

3）If屬性集為空ThenN作為葉節(jié)點(diǎn)返回，并記N為X中的多數(shù)類；

調(diào)用F（A，X），依據(jù)最大信息增益率從屬性集A選出屬性Ai，并統(tǒng)計(jì)個(gè)數(shù)最多的屬性；

4）／＊判斷是否需要修正，并執(zhí)行相應(yīng)操作屬性A和類屬性C兩個(gè)變量，其分裂屬Si＊和S＊j分別為分裂屬性Ai的實(shí)例總數(shù)，類別為Cj的實(shí)例總數(shù)，N為該數(shù)據(jù)集的實(shí)例總數(shù)，Sij為類別Cj中屬性Ai的實(shí)例總數(shù)，屬性和類別無(wú)關(guān)的期望值為

5）For each屬性集A的Ai值／＊依據(jù)屬性集A將樣本集X劃分m子集｛X1，X2，…，Xm｝＊／

2.3 經(jīng)典實(shí)例下兩種算法對(duì)比

采用經(jīng)典天氣14組實(shí)例數(shù)據(jù)對(duì)兩種算法進(jìn)行對(duì)比。數(shù)據(jù)集X有 Outlook、Temp、Humidity、Windy四種屬性，由式（4）～式（8）分別計(jì)算四種屬性的各數(shù)據(jù)量，對(duì)屬性的信息增益率進(jìn)行大小排序：GainRatio（Outlook）＞GainRatio（Humidity）＞GainRatio（Windy）＞GainRatio（Temp）。屬性中信息增益率最大為Outlook，其屬性取值也最多，符合引入平衡因子的條件。根據(jù)屬性O(shè)utlook與類表的關(guān)聯(lián)信息和式（12）計(jì)算出屬性和類別無(wú)關(guān)的期望值，由式（13）得λ＝0.204，結(jié)合所求平衡因子λ，代入式（9）～式（11）中，對(duì)屬性的信息增益率進(jìn)行調(diào)整，得到調(diào)整后的屬性O(shè)utlook的信息熵為Info＊Outlook（X）＝1.090，修正信息增益為Gain＊（Outlook）＝0.150，修正信息增益率 GainRatio＊（Outlook）＝0.095。此時(shí)有GainRatio（Humidity）＞GainRatio＊（Outlook）＞GainRatio（Windy）＞GainRatio（Temp）。根據(jù)改進(jìn)C4.5算法所求的信息增益率制出決策樹(shù)，如圖1所示。

圖1 改進(jìn)C4.5算法的決策樹(shù)

將圖1和不做修改下的決策樹(shù)進(jìn)行對(duì)比可知，改進(jìn)型C4.5算法相對(duì)原始算法改變了決策樹(shù)的根節(jié)點(diǎn)，降低了Outlook的信息增益率，提高了Humidity屬性的重要性，使得分類結(jié)果更為準(zhǔn)確（如Overcast下不一定就適合運(yùn)動(dòng)，可以結(jié)合濕度等因素作判斷），便于決策者作準(zhǔn)確的判斷。此外，根據(jù)葉子節(jié)點(diǎn)，可以看出改進(jìn)型算法提高了決策樹(shù)的健壯性。

3 兩種算法應(yīng)用對(duì)比

3.1 實(shí)例分析

本實(shí)驗(yàn)樣本來(lái)源于珠海某電子公司SPC系統(tǒng)記錄其生產(chǎn)設(shè)備工藝參數(shù)和AOI檢測(cè)的數(shù)據(jù)。數(shù)據(jù)共有547組，其中每組數(shù)據(jù)可分為組件偏移、立碑、錫洞、錫橋、錫珠、空焊、錫尖、錫渣。表1中的焊接質(zhì)量是根據(jù)每批次出現(xiàn)焊接缺陷的產(chǎn)品個(gè)數(shù)評(píng)定的，其焊接質(zhì)量可劃分為A（很好）、B（好）、C（一般）、D（較差）、E（差）等五個(gè)級(jí)別。

在調(diào)用C4.5算法之前對(duì)樣本屬性進(jìn)行離散化，有利于更好地反饋出各個(gè)工藝參數(shù)對(duì)SMT焊接質(zhì)量的影響，其八種屬性的劃分值按照實(shí)際操作經(jīng)驗(yàn)獲取，如刮刀壓力（bar）控制在1.4～5.6、離板間隙控制在0.93mm～1.45mm、回流溫度控制在263℃～269℃、貼裝精度控制在90等。首先將60%的數(shù)據(jù)（即328組）數(shù)據(jù)作為訓(xùn)練樣本，40%（即219組）作為測(cè)試樣本。接著，使用傳統(tǒng)的C4.5算法和改進(jìn)的C4.5算法分別生成決策樹(shù)，其對(duì)應(yīng)的決策樹(shù)如圖2和圖3所示。

表1 處理后的樣本數(shù)據(jù)

圖2 傳統(tǒng)C4.5算法的決策樹(shù)

圖3 改進(jìn)C4.5算法的決策樹(shù)

3.2 決策樹(shù)性能測(cè)試分析

219組測(cè)試樣本其實(shí)例的類別分布為：A很好（196）、B好（4）、C一般（7）、D 較差（3）、E 差（9）。傳統(tǒng)和改進(jìn)的決策樹(shù)C4.5算法分類性能的測(cè)試結(jié)果如表2所示，其中A／A′分別代表傳統(tǒng)的和改進(jìn)型算法的測(cè)試結(jié)果。

表2 傳統(tǒng)的和改進(jìn)型決策樹(shù)C4.5算法分類結(jié)果

由表2計(jì)算出傳統(tǒng)的和改進(jìn)的C4.5決策樹(shù)的分類準(zhǔn)確率，分別為91.3%、92.2%。實(shí)驗(yàn)說(shuō)明：1）改進(jìn)的C4.5算法其分類準(zhǔn)確率較傳統(tǒng)有所提高，但其幅度不大，表明C4.5算法本身具有一定的準(zhǔn)確率；2）改進(jìn)的算法相對(duì)原始算法增加的離板間隙屬性的重要性，降低了回流溫度的重要性；3）平衡因子的引入將在一定范圍內(nèi)對(duì)樹(shù)的結(jié)構(gòu)進(jìn)行調(diào)整，提高樹(shù)結(jié)構(gòu)平衡性，進(jìn)而提高了準(zhǔn)確率。

由表2計(jì)算出決策樹(shù)C4.5改進(jìn)算法各類別的識(shí)別率如表3所示。數(shù)據(jù)表示決策分類樹(shù)在預(yù)測(cè)過(guò)程中，測(cè)試結(jié)果為A，其真正為A的可能性為93.2%，為B的可能性為6.8%，其它可能性為0。

表3 改進(jìn)的C4.5決策樹(shù)各類別識(shí)別率

4 結(jié)語(yǔ)

通過(guò)經(jīng)典天氣實(shí)例對(duì)比分析，使用傳統(tǒng)的C4.5算法和改進(jìn)的C4.5算法分別構(gòu)建焊接質(zhì)量決策樹(shù)，引入平衡因子的C4.5算法決策樹(shù)具有更好的分類性能，增加了葉子節(jié)點(diǎn)，提高的決策樹(shù)的健壯性，有利于做出更加準(zhǔn)確的判斷。在SMT實(shí)際應(yīng)用中，在219組數(shù)據(jù)中運(yùn)用平衡因子人工協(xié)調(diào)了回流溫度屬性的信息增益率，構(gòu)建出來(lái)的決策樹(shù)其分類準(zhǔn)確率提高了0.9%，決策樹(shù)結(jié)構(gòu)也變得更加合理。此外，也可以判斷出回流溫度和離板間隙是影響焊接質(zhì)量的最主要的參數(shù)，結(jié)合實(shí)際經(jīng)驗(yàn)對(duì)回流溫度和離板間隙的參數(shù)做出適當(dāng)?shù)恼{(diào)整，可得到最佳生產(chǎn)參數(shù)。但是，對(duì)于大數(shù)據(jù)集的決策樹(shù)構(gòu)，此算法在處理速度和內(nèi)存消耗方面還有待進(jìn)一步提高。

［1］Jiawei Han，Michelinekamber，Jianpei.DATA MINING－Concepts and Techniques（Third Edition）［M］.Canada：Morgan Kaufmann Publishers，2012：5－6.

［2］黎洪生，卓禎雨.數(shù)據(jù)挖掘及其在過(guò)程監(jiān)控中的應(yīng)用［J］.自動(dòng)化與信息工程，2002，34（3）：4－6.

［3］李強(qiáng).創(chuàng)建決策樹(shù)算法的比較研究—ID3，C4.5，C5.0算法的比較［J］.甘肅科學(xué)學(xué)報(bào)，2006，18（4）：84－87.

［4］宋廣玲，郝忠孝.一種基于CART的決策樹(shù)改進(jìn)算法［J］.哈爾濱理工大學(xué)學(xué)報(bào)，2009，14（2）：17－20.

［5］周德儉，吳兆華，李春泉.SMT產(chǎn)品組裝質(zhì)量管理系統(tǒng)設(shè)計(jì)［J］.制造業(yè)自動(dòng)化，2008，30（3）：52－56.

［6］Tsung－Nan Tsai.Thermal parameters optimization of a reflow soldering profile in printed circuit board assembly：A comparative study［J］.Applied Soft Computing，2012，12（8）：2601－2613.

［7］Harding J.A.，Srinivas S.M.，Kusiak A.Data mining in manufacturing：A review［J］.Journal of Manufacturing Science and Engineering，2006，128（4）：969－976.

［8］Meyer S.，Wohlrabe H，Wolter K.－J.Data mining in electronics packaging［C］／／Electronics Technology，32nd International Spring Seminar，2009：1－7.

［9］Mehmed Kantardzic.數(shù)據(jù)挖掘：概念、模型、方法和算法［M］.第二版.北京：清華大學(xué)出版社，2013：131－133.

［10］章兢，張小剛.數(shù)據(jù)挖掘算法及其應(yīng)用［M］.北京：機(jī)械工業(yè)出版社，2006：45－56.

［11］李瑞，程亞楠.一種改進(jìn)的 C4.5算法［J］.計(jì)算機(jī)技術(shù)，2010，10（27）：70－74.