数据库技术·Ｄａｔａ Ｂａｓｅ Ｔｅｃｈｎｉｑｕｅ 一种改进的０４．５决策树算法 文／王志春 刘丽娜 本不依赖于任何专业领域的知识，所以在分 类，预测和规则提取等领域都被广泛的应用。 Ｃ４ ２ ０４．５算法 ２．１信息增益和信息增益率 ７０年代末，Ｊ．ＲＯＳＳ Ｑｕｉｎｌａｎ提出了ＩＤ３算法后， 该 是 足 在机器学习和知识发现领域决策树算法都得到 了进一步应用和发展。 ＩＤ３算法的核心是选择属性时，用信息增 益（ｉｎｆｏｒｍａｔｉｏｎ ｇａｉｎ）作为选择属性的度量标 准，在测试每一个非叶子结点时，能获得关于 被测试记录最大的类别信息。虽然ＩＤ３算法具 设Ｄ是ｍ个不同值的训练集有ｍ个不同 类Ｃ，（ｉ＝ｌ，２，…，ｍ），设Ｃ＿＿ｄ是元组的集合，Ｄ 和Ｃ．ｄ中的元组个数是ｌＤｌ和Ｃｉｄ［。 ２．】ｌｌ信息增益 ，改 Ｃ４ 提 奎 ＩＤ３算法中选择具有最高信息增益的属性 有算法清晰，方法简单和学习能力较强的优点， 但是ＩＤ３算法不能处理连续的属性值，并且依 赖于训练数据集的质量，只对数据集较小的情 况有效，训练数据集在逐渐变大时，决策树可 能会随之改变。由于ＩＤ３算法存在着许多需要 改进的地方，为此，Ｊ．ＲＯＳＳ．Ｑｕｉｎｌａｎ于１９９３ 提出了ｃ４．５算法，对ＩＤ３算法进行了补充和 改进。Ｃ４．５算法具有ＩＤ３算法优点的同时也 改进和扩展了算法，使其产生易于理解和准 确率较高的分类规则。相比于ＩＤ３算法，Ｃ４．５ 算法用信息增益率来选择属性，而不是ＩＤ３算 法所用的信息增益；在ＩＤ３算法的基础上还增 加了对连续属性的离散化、对不完整属性的处 理能力和产生规则等功能。 作为节点Ｎ的分裂属性，使元组分类的信息 量最小。期望信息为： Ｉｎｆｏ（Ｄ）＝一 一ｌｏｇ （ ） ｆ１１ 【关键词】数据挖掘决策树ｃ４．５算法信息 增益率 ｉ＝１ 用ｌＣ Ｉ／Ｉｎｌ估计Ｄ中任意元组属于类ｃ 的概率Ｐｉ。ｌｎｆｏ（Ｄ）为Ｄ的熵。 若Ｄ的元组用属性Ａ可分成ｖ个不同的 类｛Ｄ ，Ｄ ，…，Ｄ ｝，Ｄ 包含Ｄ中的元组且在 Ａ上有值ａ，，则属性Ａ的信息熵为： １ｎ ｌ ，。 （ （２） １引言 数据挖掘中决策树是解决分类问题的方 法之一，是一种归纳学习算法。通过一组属性 值向量和相应的类，采用归纳学习算法构造分 类器和预测模型，能够从一组无序和无规则的 数据中生成决策树形式的分类规则。决策树基 Ａ属性上该划分的获得的信息增益为： Ｇａｉｎ（Ａ）＝＿ｒｎ￣ｏ（ｍ）一厂力 （ ）（３） ２．１．２信息增益率 信息增益率用“分裂信息”值将信息增益 ＜＜上接１８１页 功读到数据的标识 Ｏ＝ＯＸ， ｄ＝一５２．７９ＲＳＳＩ一２９０３．７４ 拟合后得到ＲＦＩＤ标签到天线的距离和相对角 度，由于ＲＳＳＩ值得噪声较大，每次测量的结 果都有一定差距，误差控制并不特别有效。 以此公式估计ＲＳＳ１值对应的标签位置， ｄａｔａ＝［ｄａｔａ；ｏ（６）］； ｅｎｄ； ｅｎｄ； 所得到的距离估计误差如表１所示，最大的估 计误差为２９．７ｌｍｍ，定位精度较高。 ５结论 在已有ＲＦＩＤ天线特性研究基础上，分析 了ＲＦＩＤ标签信号强度的等值线表达形式，提 出通过旋转天线来进行ＲＦＩＤ标签定位的方法， 给出了连续旋转天线定位法，建立了使用步进 电机驱动的旋转天线定位系统，试验表明该方 法具有良好的定位精度，可以用于物体的精确 针对旋转天线方法，如果能够设计一个 ｆｃｌｏｓｅ（ｓ）；ｄｅｌｅｔｅ（ｓ）；ｃｌｅａｒ ｓ； ４旋转天线定位试验 用ｍａｔｌａｂ编程控制步进电机转动角度， ＲＦＩＤ天线安装在步进电机上其角度随着步进 电机转动而转动。 由于读到的ＲＦＩＤ标签ＲＳＳＩ值有一定的 随机性，需要多次进行读取，取其平均值为测 量值。 在步进电机控制天线旋转过程中，部分角 度无法读取到标签数据，因此试验中在每个角 度下读取标签２０次，仅保存读到的有效数据， 舍弃其中没有有效测量数据的角度测量结果。 ３．３直线距离下ＲＳＳＩ与距离之间的关系 标签的信号强度ＲＳＳＩ在标签与天线之间 过试验可以获得这个关系。通过前述试验系统， 在每个标签位置下读取１００次数据做平均，消 步进电机转动一步，对ＲＦＩＤ测量２０次， 分析测量的结果，舍弃没有ＲＳＳＩ值的无效数 位置时，所测的标签ＲＳＳＩ值与天线角度的关 据。如此反复进行，对于标签在（５５０ｍｍ，０ｍｍ） 定位。 系如图２所示，其中的点位测量值。对这些数 波束稍窄的高性能天线，可以更加有效的测量 据进行拟合，拟合为一个二次方程，其表示为 得到标签的位置。 红色的线。这个二次方程具有最大值，最大 得到的标签到天线的距离ｄ＝５６７ｍｍ，角度为 一的角度为０。时与距离有良好的线性关系，通 值点即为标签所在的位置。对于这次测量， 作者简介 鲍天翼（１９９９一），男，黑龙江省哈尔滨市人。 ２．０６。，计算得到坐标为（５６６ｍｍ，一２０ｍｍ）， 对更多的标签位置进行测量，测量结果 除ＲＳＳＩ的随机量后作为ＲＳＳＩ的真值。 对试验中的天线和标签，其信号强度和 与实际位置差２０ｍｍ。 现为哈尔滨市第三中学学生。研究方向为物联 网、智能家居及智能控制算法。 标签距离的关系数据如表１所示。 关系如下关系式： 误差基本都在５０ｍｍ之内，具有较高的测量精 对以上数据进行拟合得到ＲＳＳＩ与距离的 度。 应当指出的是，本方法对试验数据进行 作者单位 哈尔滨第三中学黑龙江省哈尔滨市 １ ５０００１ １８２·电子技术与软件工程Ｅｌｅｃｔｒｏｎｉｃ Ｔｅｃｈｎｏｌｏｇｙ＆Ｓｏｆｔｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ Ｄａｔａ Ｂａｓｅ Ｔｅｃｈｎｉｑｕｅ·数据库技术 假设用Ｄ代表当前样本集，当前候选属 较。实验所需数据来自于ＵＣＩ数据集中ＩＲＩＳ 性集用Ａ表示，则Ｃ４．５算法的流程图如图Ｉ 所示。 的样本实例。算法执行效率及分类正确率实验 结果如图２、３所示。 随着样本实例数的增加，改进算法的执 行效率得到提高的同时分类的正确率也有一定 的提升，因此改进的Ｃ４．５算法缩短了数据分 析的等待时间，提高工作效率，保障了分类正 确率。 ３ ０４．５算法的改进 ３．１ Ｃ４．５算法改进原理 Ｃ４．５算法得到很好的应用，但是还存在 一些不足，Ｃ４．５算法因为要对数据集进行多 次的扫描和排序所以算法的效率降低。根据信 ４结束语 息量计算公式的特点，改进划分函数的属性选 择度量计算公式和连续属性处理方法，简化信 息量的计算复杂度，提高Ｃ４．５算法的执行效 率。 本文通过对决策树分类算法Ｃ４．５的分析， 在此基础上，针对该算法所存在的不足之处， 改进了熵值的计算和连续属性最优分割点的计 算，并用实验验证，得到较好的验证结果。 Ｃ４．５算法由于大量使用了对数函数进行 熵值运算，增加了计算机的运算时间，降低了 每一次属性选择时算法的运算效率，所以为了 参考文献 ［１】Ｑｕｉ ａ１ ａｎ Ｊ Ｒ．ｈｄｕｅｔｉ ｏｎ ｏｆｄｅｃｉ ｓｉｏｎ ｔｒｅｅ ｓ［Ｍ】．Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ，１９８６，（１）： ８１—１０６． 解决这个问题，引入泰勒中值定理和麦克劳林 展开式，对熵值中的对数运算进行变换，优化 熵值运算，缩短其运算时间。 ｌｏｇ２（ ）＝ ２（ｍ一１）一（用一１）。 ２上 （２） （６） Ｃ４．５算法对每个分割点都要计算相应的 熵值，才能得到最优的分割点，所以在选择最 佳的属性分割点时效率较低。为了解决这个问 图１：Ｃ４．５算法流程图 规范化，假设以属性Ａ的值为基准对样本进 行分割，训练数据集Ｄ用分类信息Ｓｐｌｉｔｌｎｆｏ 作为初始信息量划分成对应于属性Ａ的有ｖ 个输出的ｖ个划分信息。定义如下： 题，引入边界点定义和Ｆａｙｙａｄ定理。 边界点定义：设序列Ｌ＝｛ｘ ，Ｘ２，…，Ｘ ）为 升序排列的有序序列，实例ｘ所属的类为 Ｃ 。如果有实例Ｘ 和ｘ （其中ｊ＝ｉ＋１），且 Ｃ ≠Ｃ 则边界点Ｂ。＝（ｘ ＋ｘｊ）／２。 Ｆａｙｙａｄ定理：连续属性ｘ各个候选分割 ［２］陈青山．决策树算法在高校教学质量评价 系统中的应用研究［ｃ］．西南交通大学硕 士论文．２０１０． ［３］Ｑｕｉａｌａｎ Ｊ Ｒ．Ｃ４．５：Ｐｒｏｇｒａｍｓ ｆｏｒ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ［Ｍ】．ＮｅｗＹｏｒｋ：Ｍｏｒｇａｎ Ｋａｕｆｎａｎ， １９９ ３． ［４】黄爱辉．决策树ｃ４．５算法的改进及应用 ［Ｊ］．科学技术与工程．２００９，９（１）：３４—３６． ［５】杨学兵，张俊．决策树算法及其核心技术 ［¨．计算机技术与发展，２００７，１ ７（１）：４４－ ４６． 点对应的信息熵值的最小值一定在边界点Ｂ 上取得。 （４） ｎ ）＿－￣ ［ＤＪ ［ｘ ｌｏｇ２‘ 信息增益率定义为信息增益与初始信息 量的比值： 作者简介 王志春（１９７ ６－），男，陕西省洋县人。硕士学位。 由以上定理可知，连续属性的最优分割 现为河西学院讲师。研究方向为数据挖掘、嵌 点在计算时，只需要通过比较属性值序列在边 入式系统。 界点的最小信息熵值，就可以计算出该属性的 ６ａｉｎＲａｔｉｏ（Ａ）＝ Ｇａｉｎ（Ａ） Ｓｐｌｉｔｌｎｆｏ（Ａ）（５） Ｃ４．５算法选取信息增益比最高的属性为 最大修正信息增益率，减少了候补分割点，因 此可以大大提高了计算的效率。 ３．２实验及结果分析 作者单位 １．河西学院信息技术与传媒学院 甘肃省张 掖市７３４０００ 集合Ｄ的测试属性，创建一个节点并为每个 属性创建分支划分样本。 ２．２ Ｃ４．５算法实现 ？２．兰州理工大学科技处 甘肃省兰州市 使用Ｗｅｋａ作为数据挖掘平台，对改进 Ｃ４．５算法与传统Ｃ４．５算法的分类性能进行比 ７３００００ 算法效率｝ 较图 ＋改逃算法＋传统算法 —算法正确率 较圈 —一改进算法－Ｏ－－传统算法 ８０ 一 ６０ ， 鼹 落 ！黧４Ｏ 麓 ２０ Ｏ Ｏ １０００ Ｏ ｌ∞０ 数搭实例 数据实钢 图２：算法执行效率图 图３：算法分类正确率比较图 ·基金：甘肃省软科学项目（１４４ＺＣＲＡ１ ５７）。 Ｅｌｅｃｔｒｏｎｉｃ Ｔｅｃｈｎｏｌｏｇｙ＆Ｓｏｆｔｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ电子技术与软件工程·１８３