第２８卷第３期 ２０１２年５月 齐齐哈尔大学学报 Ｊｏｕｒｎａｌ ｏｆ Ｑｉｑｉｈａｒ Ｕｎｉｖｅｒｓｉｔｙ Ｖ０１．２８．Ｎｏ．３ Ｍａｙ，２０１２ 基于决策树ｌＤ３算法研究与实现 王胜 （安徽国防科技职业学院，安徽六安，２３７０１１） 摘要：阐述数据挖掘的决策树算法，对Ｉｔ）３算法基本理论和原理进行介绍。运用该算法对教师教学质量测评数据 进行分析，构造出质量测评数据决策树模型。 关键词：数据挖掘；决策树；ＩＤ３算法 中图分类号：ＴＰ３１ ｌ 文献标志码：Ａ 文章编号：１００７—９８４Ｘ（２０１２）０３－００６４—０５ １决策树简介 决策树通过使用信息论知识原理对获取到样本的众多属性进行解析和归纳，并最终形成类似于流程图 的树型结构形式。树型结构节点为样本的属性，分支为属性取值，其中树的根节点为样本中信息量最大的 属性，树的中间节点则为每个子树包含子集样本中信息量最大的属性，将样本类别取值作为树的叶节点。 一条合取规则就是从树根到叶结点的一条通路，整个树就是由一组析取表达式规则所构成。决策树构造可 以分２步进行： 第１步是树的生成，由训练样本集采用递归的方式生成决策树的过程。 第２步是树的修剪，即对上一阶段生成的决策树进行检验、校正和修正的过程。采用非训练集的事例 检验，将一些可能是噪音或者异常的数据剪去。 ２ ＩＤ３算法 ２．１ ＩＤ３算法基本思想 ＩＤ３由概念学习系统ＣＬＳ发展而来，ＣＬＳ的工作过程为：先从数据中找出最具判别力的因素，再根据 此因素将数据划分成多个子集，接着每个子集再找出最有判别力的因素进行进一步的划分，最终使得每个 子集中只含同类型的数据，生成一棵树，使用它可以分类新的样例集。 Ｒ．Ｑｕｉｎｌａｎ于１９８６年引进了信息论中的信息增益，作为特征判别能力的度量，并提出了ＩＤ３算法” 。这 种算法对对象分类所需要的期望测试数目实现最小，从而得到一个简单的树。 ＩＤ３算法是基于信息熵 的决策树分类算法，为了获得具有最大信息增益的属性，需要对每个属性的信 息增益进行计算并比较其大小。设 是拥有．ｓ｜个数据样本的集合。假设类标号属性具有／７１个不同取值 （ｆ＝１，２，…， ）。设是． 类 中的样本数。对于一个给定的样本分类所需的期望信息由式（１）给出 ＝Ｊ” ，（ ， ，…，ｓ）＝－Ｅｐ，ｌｏｇ （ ） ｉ＝ｌ （１） 其中ｐ 是任意样本属于 的概率，可用 来估算。ｔ－ 。 ｖ 设一个属性ｊ，具有玎个不同取值 ， ，…， ）。可以用属性 将 划分为 个不同子集｛ ， ，．．．’ ）， 其中 ，中的样本在属性Ｙ上具有相同的值 ，（．，＝ｌ，２，…， ）。若属性Ｊ，被选为测试属性，设 ，是子集Ｓ，中 类 的样本数。有属性】，划分成子集的信息熵（信息期望）由式（２）计算出 ｎ Ｅ（】，）＝ ｌ，＋ ２，＋‘‘斗 朋，）／ ×（ ｌｆ， ２，，…， ｍｊ）） （２） 收稿日期：２０１１－１２—１５ ． 作者简介：王胜（１９７９一），男，安徽六安人，讲师，硕士，主要从事计算机网络和数据挖掘方面的研究工作，ｊａｃｋｅｎ＿７９＠１２６．ｃｏｍ。 第３期 基于决策树ＩＤ３算法研究与实现 其中（ｓｌ，＋ｓ２，＋・・＋ ，）／ｓ被当做第Ｊ个子集的权值。 由上述计算可得：若对子集划分的纯度越高，就要求熵值越小。 对于一个给定的子集Ｓ，其信息期望为 （ 。Ｊ， ： ，…， ）＝一至 ｌｏｇ：（ ）；Ｐ ＝号是 中样本属于 样本的概率。 属性】，上分支将获得的信息增益是 Ｇａｉｎ（Ｙ）＝ｌ（ｓ Ｓ２ “， ，）一Ｅ（】，） （３） 由式（３）可知：如果熵的取值越小，其所对应的信息增益就会越大。 ２．２ ＩＤ３算法描述 主算法描述为： ①随机从数据训练集中挑选含有正、反例的子集（称之为“窗Ｅｌ”）； ②对上述随机选择的子集使用“ＩＤ３建树算法”构建一棵决策树； ③使用上述构建的决策树对训练集中除窗Ｅｌ以外的实例进行类别判定，从而找到错判的实例； ④如果出现判断出错的实例，就将其放入到窗口中，并跳转②执行，否则结束此算法。 建树算法描述为： ①对随机从数据训练集中挑选出来的含有正、反例的子集，进行各个属性特征的互信息计算； ②将互信息最大的特征 选为树的根或者是子树的根； ③把在 。处取值相同的例子归于同一子集，并将该值作为树的分支； ④对仅含正例或反例的子集则返回调用处； ⑤对于既含正例又含反例的子集，则递归调用建树算法，返回②，重复构建子树。 ２．３ ＩＤ３算法的改进 在多数实际应用中，由于获得的数据不能达到此算法要求的条件，同时ＩＤ３算法存在计算信息增益时 只选择取值较多的属性，对连续属性不能处理等不足。这就要求在使用决策树算法时，对数据先进行预处 理或者对ＩＤ３算法进行改进。 ２．３．１决策树剪枝 实际应用中，在决策树创建过程中，如果训练样本集的规模较大，对应生成决策树的分枝和层数就较 多。另外，由于训练样本集中存在不同的异常和噪声，致使部分分枝反映的是异常现象。建立的决策树就 出现过度拟合训练样本集。为了解决这种过度拟合问题，就需要对决策树进行剪枝。剪枝是克服噪声的一 种技术，采用统计度量减去最不可靠的分支，从而提高决策树独立于测试数据的正确分类能力，决策树得 以简化。 ． ２．３．２对定量属性的处理 在实际工作中，数据挖掘既要能处理定性属性（即离散属性）的数据又要能处理定量属性（即连续属 性）的数据，这就要求对算法进行扩展，使之能够处理定量属性。 要使算法能够处理定量属性，就需要对其值进行划分，关键性的问题是分裂点的选择。ＩＤ３算法通过 对连续属性计算得到最优阈值 ，依据 将定量属性的取值进行分区，ｌｉｌＪ／Ｊ，于等于 和大于 两个区。 再计算出该屙陛的增益比率，通过比较其它属性的增益比率，获得最大的信息增益比率。通过这种方法较 好的解决了定量属性的离散化处理问题。 １９９３年Ｊ．Ｒ．Ｑｕｉｎｌａｎ提出了ｃ４．５算法ｐＬＩＤ３算法的改进版本，该算法就增加了对连续屙Ｉ生离散化等 功能。 ３ ＩＤ３算法实例分析 通过实例介绍ＩＤ３算法的过程，实例是根据职称、性别、学历和年龄的指标因素来认定教师教学质量 是否优秀。列举部分教师的基本情况及其最后评估是否优秀的结果，其全￣－０１１练数据见表１。 ・６６・ 齐齐哈尔大学学报 ２０１２拄 表１教师数据库训练数据元组 序号 职称 ｌ ２ ３ ４ ５ ６ 初级职称 中级职称 初级职称 高级职称 中级职称 属性 性别 学历 年龄 男 女 男 男 女 本科 ３ ４５ 硕士 ３０～４５ 本科 ≤３０ 硕士 ＞４５ 本科 ＞４５ 是否优秀 序号 职称 否 是 否 是 否 否 ８ ９ 属性 性别 学历 年龄 博士 ３０—４５ 硕士 ３０—４５ 是否优秀 否 是 否 是 是 否 高级职称 男 初级职称 女 ｌＯ 初级职称 ｌ１ １２ 高级职称 中级职称 男．硕士 ≤３０ 女 本科 男 女 ＞４５ 硕士 ≤３Ｏ 本科 ≤３Ｏ 中级职称 女 本科 ３０－４５ １３ 初级职称 ７ 高级职称 男 博士 ＞４５ 是 ｌ４ 中级职称 男 硕士 ３Ｏ一４５ 否 ３．１计算信思熵 信息熵为 Ｈ（Ｕ）＝∑Ｐ（ ） （ ）＝一Ｅｒ（ｕ ）ｌｏｇ Ｐ（ ） ＝ ， ｌ＇２）。 由表Ｉ可以得到初始时刻属于“优秀”类的实例个数为６个（１ Ｕｔ １＝６），“非优秀”类的实例个数为８ 个（１ Ｕ：１＝８），对于６个正例和８个反例分别有 Ｐ（ｕ。）＝ ６，尸（ ：）＝百８ 故初始时刻的熵值为 ）＝一（吾・。ｇ 鲁＋ －。ｇ： ）＝。．９８５ ３．２计算条件熵 条件熵为 Ｈ（Ｕ Ｉ Ｖ）＝一∑尸（ ）∑尸（ ｌ Ｖｊ）ｌｏｇＰ（Ｕｉ Ｉ ） 当詹陛４＝性别，取值 ＝男， ＝女。在４处取值男的例子８个，取值女的例子６个，故 尸（ ）＝ ８，尸（ ）＝ ６ 取值为男的８个例子中有３个正例（“优秀”），５个反例，可得到 尸（ｕ－ｌ ） 盖，Ｐ（ Ｉ ） 舌 同理可得 尸（ １ ） 言，尸（ １ ） 因此如果选取眭别作为测试属性，条件熵为 Ｈ（ＵＩ ）＝一百８‘虿３ｌＤｇ：吾＋言ｌ。ｇ： ５）一百６‘ ３１ｏｇ：詈＋ｌｏｇ： ３）＝。．９７４ ３．３计算互信息 当属性４＝性别时：，（性别）＝Ｈ（Ｕ）一Ｈ（Ｕｌ ）＝０．９８５—０．９７４＝０．０１１。 第３期 基于决策树ＩＤ３算法研究与实现 同理可得：Ｉ（职称）＝Ｏ．１４９；，（学历）＝ｏ．１７；１（年龄）＝Ｏ．１２８ ３．４建立决策数的树根和分支 可以看出当属性取值为“学历”时，，（学历）最大，所以应该选择学历属性作为测试屙陛。将“学历” 特征为树根，将其属性的３个不同取值作为分支，分支所对应的３个子集为 Ｍ１＝｛１，３，５，６，１ １，１３｝，Ｍ２＝｛２，４，９，１０，１２，１４｝，Ｍ３：｛７，８） ３．５递归建树 “学历”特征为树根，所得到３个子集均包含有正例和反例，这就需要对各子集分别使用ＩＤ３算法， 通过对子集中的各特征计算求的互信息，并产生相应的分支。直至所产生的分支包含的实例均属于某一类 为止。 在“学历”特征选择本科时所求各子集的条件熵。 如果下一个节点将职称选择为测试属性，则条件熵为 Ｈ（ＵＩＶ）＝一詈（０＋１。ｇ２ ３）一詈（０＋１。ｇ： ２）一吉（｛Ｉ。ｇ：｛＋０）＝０ 如果下一个节点选择性别作为测试属性，则条件熵为 Ｈ（ＵＩＶ）＝一吾（ｏ＋詈ｌ。ｇ：争一詈（ １。ｇ １＋＿３４ｌ。ｇ： ３）＝０．５４・ 如果下一个节点选择年龄作为测试属性，则条件熵为 （ ｌ ）一言（ｏ＋１ｏｇ２主）一言（０＋主 。ｇ２专）一 ｏｇ２壶＋ｏ）＝０－ｌ６７ 可以看出，选择职称作为测试属性得到的Ｈ（ＵＩ ）最小，所以Ｉ（职称）最大，故当“学历”特征选 择本科时，应选择“职称”作为下个结点的测试属性。由“学历”特征为本科所引申出的结点到此完成， 此决策树分支含有３个叶子结点。在“学历”特征选择硕士时所求各子集的条件熵。 如果下一个节点将职称选择为测试屙陛，则条件熵为 删熏 嫩Ｈ（ＵＩＶ ＝一詈ｃ ・。ｇ：吉＋ ｔ。ｇ： 一吾ｃ詈・。ｇ：吾＋ ，。ｇ 一吉ｃ｛ｔ。ｇ ｛＋。 ＝。．７９２ 如果下一个节点选择性别作为测试属性，则条件熵为 （ ｌ ）：一詈 －。ｇ： ＋ －。ｇ： ２）一．詈（吾．ｏｇ： ２＋ｏ）＝０．６６７ 如果下一个节点选择年龄作为测试属性，则条件熵为 Ｈ（ＵＩＶ）＝一詈（ 一ｏｇ２ Ｉ＋ｌｌｏｇ２ Ｉ）一詈 ・。ｇ：詈＋ 一。ｇ ）一 磷 ／ Ｉ ｜ 否 ÷（二１ｏｇ２÷＋ｏ）＝０．７９２ 由于选择性别作为测试属性得到的Ｈ（Ｕ ｌ ）最小，所以 性 别）最大，故当“学历”特征选择硕士时，应选择“性别”作为 磷＜耍 ／ Ｉ／ ｉ ＼ 魁 下个结点的测试属性。 专釜３Ｏ ３Ｏ—噜５ 按照这种算法思路，通过递归的建树方法将得到一棵基于 ／ ＼ 荫 是 ＩＤ３算法的决策树，最终产生一棵完整的决策树，如图１所示。 图１ ＩＤ３算法生成的决策树 参考文献 【１】马秀红，宋建社，董晟飞．数据挖掘中决策树的探讨【Ｊ】．计算机工程与应用，２００４（１）：１８５，２１４． 【２】李华．基于决策树ＩＤ３算法的改进研究嘲．成都：电子科技大学硕士学位论文，２００９． 【３】高阳，廖家平，吴伟．基于决策树的ＩＤ３算法与Ｃ４．５算法【Ｊ】．湖北工业大学学报，２０１１，２６（２）：５４—５６ 『４１王永梅，胡学钢．决策树中ＩＤ３算法的研究【Ｊ】．安徽大学学报，２０１１，３５（３）：７１—７５． ［５】陆秋．基于决策树ＩＤ３算法的数据挖掘技术研究与应用【Ｄ】．桂林：桂林工学院硕士学位沦文，２００７． Ｓｔｕｄｙ ａｎｄ ｒｅａｌｉｚａｔｉｏｎ ｏｆ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｄｅｃｉｓｉｏｎ－ｔｒｅｅ ｌ Ｄ３ 一 ；｝ ・６８・ 齐齐哈尔大学学报 ２０１２钜 ＷＡＮＧ Ｓｈｅｎｇ （Ａｎｈｕｉ Ｖｏｃａｔｉｏｎａｌ Ｃｏｌｌｅｇｅ ｏｆ Ｄｅｆｅｎｓｅ Ｔｅｃｈｎｏｌｏｇｙ。Ａｎｈｕｉ Ｌｉｕ’ａｎ ２３７０１ １。Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｉｓ ｐａｐｅｒ ｍａｉｎｌｙ ｄｅｓｃｒｉｂｅｓ ｔｈｅ ｄａｔａ ｍｉｎｉｎｇ ｏｎ ｔｈｅ ｄｅｃｉｓｉｏｎ ｔｒｅｅ ａｌｇｏｒｉｈｔｍ，ｄｉｓｃｕｓｓｅｄ ｔｈｅ ｂａｓｉｃ ｔｈｅｏｒｉｅｓ ａｎｄ ｐｒｉｎｃｉｐｌｅ ｃｏｎｃｅｒｎｉｎｇ ＩＤ３ ａｌｇｏｒｉｈｔｍ．ｔｈｅ ｕｓｅ ｏｆ ｈｔｅ ａｌｇｏｒｉｈｔｍ ｔｏ ｔｈｅ ｔｅａｃｈｅｒｓ’ｔｅａｃｈｉｎｇ ｑｕａｌｉｔｙ ｅｖａｌｕａｔｉｏｎ ｄａｔａ ｆｏｒ ａｎａｌｙｓｉｓ，ｃｏｎｓｔｒｕｃｔｉｎｇ ｑｕａｌｉｔｙ ｅｖａｌｕａｔｉｏｎ ｄａｔａ ｄｅｃｉｓｉｏｎ ｔｒｅｅ ｍｏｄｅ１． Ｋｅｙ ｗｏｒｄｓ：ｄａｔａ ｍｉｎｉｎｇ；ｄｅｃｉｓｉｏｎ ｔｒｅｅ；ＩＤ３ ｌａｇｏｒｉｈｔｍ 数控车床变频器故障的解决方法 以沈阳机床厂生产的ＣＡＫ６１３６Ｖ／３５０数控车床为例。探讨数控车床变频器故障的解决方法。其系统是ＦＡＮＩＣ—Ｏｉ ＭａｔｅＴＣ， 在使用过程中出现主轴转数达不到设定转数，只有１００ ｄｍｉｎ左右，并且运行不到１ ｍｉｎ，荧光屏显示报警１００３ ＳＰＩＮＤＬＥ ＤＲＩＶＥＲ ＮＯＴ ＲＥＡＤＹ（主轴驱动器没准备），复位后，手动启动主轴，主轴不转，下电后，数分钟，重新上电，手动启 动主轴，主轴运转仍为１Ｏ０ｄｒａｉｎ左右。 １原因分析 其数控机床主轴是由变频器控制的（南京日立产机有限公司生产）。参照机床使用说明书中的机床报警信息内容及解决 方法，发现变频器警示灯亮，其主轴驱动模块显示报警号为Ｅｌ４．６，查看 变频器使用手册，说是上电时检测变频器输出和电机之间有接地故障。检 查变频器输入及输出电压，发现输入电压正常，输出电压只有００Ｖ左右， 将负荷摘下，其输出电压仍为６ｏＶ左右。同时测量电机绕组，发现电机 绕组接地。因此，故障应出现在变频器上和主轴电机上，可能是电机绕组 接地引起变频器的损坏。 ２故障排除 图１电路图 将电机线拆下，电机更换绕组进行修复；去掉变频器的电源线（Ｒ， 表Ｉ测量结果 ｓ，Ｔ），与电机的连线（ｕ、Ｖ、ｗ），再生制动电阻（Ｐ和ＲＢ）和其它控 制线。将变频器拆下，打开外壳，将滤波电容器完全放电，通过改变万用 表极性，测量变频器端子Ｒ，Ｓ，Ｔ，Ｕ，Ｖ，Ｗ，ＲＢ，Ｐ和Ｎ的导通状态， 内部电路，如图１所示。但对变频器的逆变电路ＴＲ３进行测量时，发现 端子ｗ和端子Ｐ之间正、负均导通，说明驱动光ｗ相光偶烧坏。更换该 相光偶，再次测量，端子ｗ和端子Ｐ之间不导通，端子Ｐ和端子ｗ之间 导通。将该变频器安装到设备上，接好控制线路和电源后，送电，用万用 表测量输出电压，三相电压正常。断电后，接上主轴电机连线，送电启动， 设定主轴３００ｒ／ａｒｉｎ，发现主轴转数达到３０００ｒ／ｍｉｎ，按降速按钮，不降速。 由于主轴电机的转数是由变频器的参数进行调整的，所以按说明书中的方 法，对变频器进行整定，通过变频器自整定后，主轴转数仍为３０００ｄｍｉｎ， 并且不降速。调取变频器自整定后参数，发现变频器自整定后的终止频率 Ａ０１２置０（相当于最大频率），频率上限Ａ０６１置１５２（置０相当于最大 频率）。对其频率进行手动调整，将终止频率Ａ０１２设定为１５２．００，频率 上限Ａ０６１设定为Ｏ。存储数据后，启动主轴，转数为３００ｄｍｉｎ左右。升 降速正常。机床运行也正常。 （谷瑞波。齐齐哈尔金车公司制动机厂，黑龙江齐齐哈尔１６１０００）
