唐露新 张强武

（广东工业大学信息工程学院 广州 510006）

1 引言

数据挖掘就是在大量数据中提出或挖掘知识［1～2］。决策树作为数据挖掘的一种预测分析模型，以高效的分析能力、简单明了的特点成为数据挖掘中最为广泛的一种归纳分析方法。目前构建决策树的方法主要有ID3、C4.5、C5.0、CART（Classification and Regression Tree，分类回归树）等。ID3采用信息熵作为属性选择标准进行构建，其缺点是标准易于偏向取值多的候选属性；C4.5继承ID3全部优点发展而来，以信息增益率来选择决策属性克服了ID3多值偏向的问题，但是对于大数据处理其效率较低，内存消耗大；C5.0针对C4.5缺点，采用Boosting方式提高模型准确率和计算速度，减少内存资源［3］，适处理大数据集，但相对C4.5其方法难预测连续性的字段，此外类别多时易出错，其分类属性也非全局最优；CART树是一种二叉树，其优点是它将模型的验证和最优通用树的发现嵌在了算法中，能够克服过适应性，得到最适应未来数据的树［4］。

SMT（Surface Mount Technology，表贴封装技术）作为现代技术电子制造产业发展的关键技术之一，其工艺流程包括锡膏印刷、元件贴片和回流焊。合理地工艺流程中刮刀压力、回流温度、离板间隙等参数，保证良品率，减少损失，一直是当前SMT焊接质量技术研究的热点与难点［5～6］。近年来，在SMT生产工艺中，数据挖掘技术逐渐被用于分析焊接过程中工艺参数对产品质量的影响［7～8］。数据挖掘中的决策树算法可以根据SMT的工艺参数分析预测出最终的焊接质量，本文针对决策树C4.5算法的特点，提出一种改进算法，用于改善SMT焊接工艺中产品的质量。

2 C4.5决策树算法及其改进算法

决策树是用于分类和预测的主要技术，其过程是从一组无规则的实例推理出决策树表示形式的分类规则。作为一种树形结构，采用自顶向下的递归方式，在部分搜索空间寻找搜索决绝方案［9］。

2.1 C4.5算法的实现

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的个数，｜Cj｜为Cj的实例个数，｜Xij｜表示属性为Ai具有类别Cj的个数。

1）一个实例属性为Ai的概率为

2）一个实例属于j类的概率为

3）属性Ai的实例中，含有类别Cj的概率为

由式（2）可求出决策树划分C的不确定度为

由式（1）和式（4）得，每个属性为Ai的叶节点的分类信息熵为：

属性A的信息增益率为属性A的分类互信息量：

属性A的分裂信息为

前面式（1）～式（7）实现ID3算法。C4.5算法在ID3算法基础上，采用“分而治之”的策略，用信息增益率代替信息增益对属性进行分类选择，克服了ID3算法中因信息增益导致在选择属性时偏向多值属性的不足。这种策略只是构造树选取内部节点的一种局部最优探索方式，虽然有一比较可观的准确率，但可能达不到全局最优结果［10］。此外，在C4.5算法中，大类分类信息可能隐藏不够明显的小类分类信息，尽管改用信息增益率的方式解决了多值偏向问题但其信息理论含义变模糊且可解释性降低［11］。对此，本文引入平衡因子，对C4.5算法进行了算法改进。

2.2 C4.5算法的改进

改进的C4.5算法是针对属性选择标准进行改进，C4.5改进算法的基本原理：在实例集进行最佳属性划分时，通过在属性选择度量中引入平衡因子替代传统C4.5算法中只依据最高信息增益率进行属性选择，进而降低某些属性的信息熵，调整属性值得信息增益率，对决策树进行改善。在符合属性A平衡条件下，其修正的分类信息熵为

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

修正的信息增益为：

修正的信息增益率为：

平衡因子λ定义为：

由平衡因子λ的定义知，其值取决于当前分裂

改进型C4.5算法的伪代码描述如下：

算法：由给定训练集X生成决策树；

输入：具有类别C区分的训练集X；训练集属性集A；

属性选择函数F（A，X）：最佳分裂属性选择依据信息增益率；

输出：一棵决策树

1）创建一个节点N；

2）If实例X都为同一类CThenN作为叶节点返回，并记N为C类；

3）If属性集为空ThenN作为叶节点返回，并记N为X中的多数类；

调用F（A，X），依据最大信息增益率从属性集A选出属性Ai，并统计个数最多的属性；

4）／＊判断是否需要修正，并执行相应操作属性A和类属性C两个变量，其分裂属Si＊和S＊j分别为分裂属性Ai的实例总数，类别为Cj的实例总数，N为该数据集的实例总数，Sij为类别Cj中属性Ai的实例总数，属性和类别无关的期望值为

5）For each属性集A的Ai值／＊依据属性集A将样本集X划分m子集｛X1，X2，…，Xm｝＊／

2.3 经典实例下两种算法对比

采用经典天气14组实例数据对两种算法进行对比。数据集X有 Outlook、Temp、Humidity、Windy四种属性，由式（4）～式（8）分别计算四种属性的各数据量，对属性的信息增益率进行大小排序：GainRatio（Outlook）＞GainRatio（Humidity）＞GainRatio（Windy）＞GainRatio（Temp）。属性中信息增益率最大为Outlook，其属性取值也最多，符合引入平衡因子的条件。根据属性Outlook与类表的关联信息和式（12）计算出属性和类别无关的期望值，由式（13）得λ＝0.204，结合所求平衡因子λ，代入式（9）～式（11）中，对属性的信息增益率进行调整，得到调整后的属性Outlook的信息熵为Info＊Outlook（X）＝1.090，修正信息增益为Gain＊（Outlook）＝0.150，修正信息增益率 GainRatio＊（Outlook）＝0.095。此时有GainRatio（Humidity）＞GainRatio＊（Outlook）＞GainRatio（Windy）＞GainRatio（Temp）。根据改进C4.5算法所求的信息增益率制出决策树，如图1所示。

图1 改进C4.5算法的决策树

将图1和不做修改下的决策树进行对比可知，改进型C4.5算法相对原始算法改变了决策树的根节点，降低了Outlook的信息增益率，提高了Humidity属性的重要性，使得分类结果更为准确（如Overcast下不一定就适合运动，可以结合湿度等因素作判断），便于决策者作准确的判断。此外，根据叶子节点，可以看出改进型算法提高了决策树的健壮性。

3 两种算法应用对比

3.1 实例分析

本实验样本来源于珠海某电子公司SPC系统记录其生产设备工艺参数和AOI检测的数据。数据共有547组，其中每组数据可分为组件偏移、立碑、锡洞、锡桥、锡珠、空焊、锡尖、锡渣。表1中的焊接质量是根据每批次出现焊接缺陷的产品个数评定的，其焊接质量可划分为A（很好）、B（好）、C（一般）、D（较差）、E（差）等五个级别。

在调用C4.5算法之前对样本属性进行离散化，有利于更好地反馈出各个工艺参数对SMT焊接质量的影响，其八种属性的划分值按照实际操作经验获取，如刮刀压力（bar）控制在1.4～5.6、离板间隙控制在0.93mm～1.45mm、回流温度控制在263℃～269℃、贴装精度控制在90等。首先将60%的数据（即328组）数据作为训练样本，40%（即219组）作为测试样本。接着，使用传统的C4.5算法和改进的C4.5算法分别生成决策树，其对应的决策树如图2和图3所示。

表1 处理后的样本数据

图2 传统C4.5算法的决策树

图3 改进C4.5算法的决策树

3.2 决策树性能测试分析

219组测试样本其实例的类别分布为：A很好（196）、B好（4）、C一般（7）、D 较差（3）、E 差（9）。传统和改进的决策树C4.5算法分类性能的测试结果如表2所示，其中A／A′分别代表传统的和改进型算法的测试结果。

表2 传统的和改进型决策树C4.5算法分类结果

由表2计算出传统的和改进的C4.5决策树的分类准确率，分别为91.3%、92.2%。实验说明：1）改进的C4.5算法其分类准确率较传统有所提高，但其幅度不大，表明C4.5算法本身具有一定的准确率；2）改进的算法相对原始算法增加的离板间隙属性的重要性，降低了回流温度的重要性；3）平衡因子的引入将在一定范围内对树的结构进行调整，提高树结构平衡性，进而提高了准确率。

由表2计算出决策树C4.5改进算法各类别的识别率如表3所示。数据表示决策分类树在预测过程中，测试结果为A，其真正为A的可能性为93.2%，为B的可能性为6.8%，其它可能性为0。

表3 改进的C4.5决策树各类别识别率

4 结语

通过经典天气实例对比分析，使用传统的C4.5算法和改进的C4.5算法分别构建焊接质量决策树，引入平衡因子的C4.5算法决策树具有更好的分类性能，增加了叶子节点，提高的决策树的健壮性，有利于做出更加准确的判断。在SMT实际应用中，在219组数据中运用平衡因子人工协调了回流温度属性的信息增益率，构建出来的决策树其分类准确率提高了0.9%，决策树结构也变得更加合理。此外，也可以判断出回流温度和离板间隙是影响焊接质量的最主要的参数，结合实际经验对回流温度和离板间隙的参数做出适当的调整，可得到最佳生产参数。但是，对于大数据集的决策树构，此算法在处理速度和内存消耗方面还有待进一步提高。

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

［2］黎洪生，卓祯雨.数据挖掘及其在过程监控中的应用［J］.自动化与信息工程，2002，34（3）：4－6.

［3］李强.创建决策树算法的比较研究—ID3，C4.5，C5.0算法的比较［J］.甘肃科学学报，2006，18（4）：84－87.

［4］宋广玲，郝忠孝.一种基于CART的决策树改进算法［J］.哈尔滨理工大学学报，2009，14（2）：17－20.

［5］周德俭，吴兆华，李春泉.SMT产品组装质量管理系统设计［J］.制造业自动化，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.数据挖掘：概念、模型、方法和算法［M］.第二版.北京：清华大学出版社，2013：131－133.

［10］章兢，张小刚.数据挖掘算法及其应用［M］.北京：机械工业出版社，2006：45－56.

［11］李瑞，程亚楠.一种改进的 C4.5算法［J］.计算机技术，2010，10（27）：70－74.