一種改進型C4.5算法在SMT焊接質(zhì)量中的應用研究＊

唐露新 張強武

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

1 引言

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

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

2 C4.5決策樹算法及其改進算法

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

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

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

1）一個實例屬性為Ai的概率為

2）一個實例屬于j類的概率為

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

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

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

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

屬性A的分裂信息為

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

2.2 C4.5算法的改進

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

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

修正的信息增益為：

修正的信息增益率為：

平衡因子λ定義為：

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

改進型C4.5算法的偽代碼描述如下：

算法：由給定訓練集X生成決策樹；

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

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

輸出：一棵決策樹

1）創(chuàng)建一個節(jié)點N；

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

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

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

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

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

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

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

圖1 改進C4.5算法的決策樹

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

3 兩種算法應用對比

3.1 實例分析

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

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

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

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

圖3 改進C4.5算法的決策樹

3.2 決策樹性能測試分析

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

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

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

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

表3 改進的C4.5決策樹各類別識別率

4 結(jié)語

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

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

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

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

［4］宋廣玲，郝忠孝.一種基于CART的決策樹改進算法［J］.哈爾濱理工大學學報，2009，14（2）：17－20.

［5］周德儉，吳兆華，李春泉.SMT產(chǎn)品組裝質(zhì)量管理系統(tǒng)設計［J］.制造業(yè)自動化，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］.第二版.北京：清華大學出版社，2013：131－133.

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

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