1、C45 决策树工具 使用说明1. 简介：本文档给出了有关 C45 决策树方法相关的一些资料，面向对象是研究人员。本文档的内容安排如下：1 C45 决策树方法的使用场合描述；2 C45 决策树如何训练，即 C45_VC.exe 使用说明；3 C45 决策树训练结果如何在代码中使用，即 CAskC45 编程说明；4 C45 的外围工具简介；5 C45 的原理说明；6 联系方式。2. 适合用 C45 解决的问题C45 是一种决策树的算法，可以理解为数据挖掘算法的一种。从大规模的数据中挖掘规律，这里的大规模数据一般是用属性来描述，属性本身可以是连续量，如语音数据的基频值；也可以使离散量，如句子中词的个
2、数；还可以使枚举量，如 26 个词类，声韵母类型等。属性分为输入属性，和结论属性（或称决策属性） 。结论属性就是我们希望从输入属性中得到的结果，如希望从输入的词性序列中预测某个位置是不是 L3 边界，或者根据前后的音调、基频等预测当前的音节应该是哪一类的韵律曲线。结论属性必须是枚举量（当然包括布尔量） 。而规律则以决策树的形式来表示，其形式如，在 C45_VC.txt 或者 Screen.txt 中可以看到类似的输出结果：Decision Tree:e_lv 45.8 : NeiBuWen (44.0) 如果 n_lv 值大于 45.8，结论属性应该是 NewiBuWen。e_lv 47.6
3、: 如果 e_lv 属性值大于 47.6 的话| n_lv 45.8 : WaiBuWen (32.0) 注：n_lv n“, FileName);printf(“tFile stem n“, FileName);break;case b: BATCH = true;fprintf(fpScreen,“tWindowing disabled (now the default)n“);printf(“tWindowing disabled (now the default)n“);break;case u: UNSEENS = true;fprintf(fpScreen,“tTrees eval
4、uated on unseen casesn“);printf(“tTrees evaluated on unseen casesn“);break;case p: PROBTHRESH = true;fprintf(fpScreen,“tProbability thresholds usedn“);printf(“tProbability thresholds usedn“);break;case v: VERBOSITY = atoi(optarg);fprintf(fpScreen,“tVerbosity level %dn“, VERBOSITY);printf(“tVerbosity
5、 level %dn“, VERBOSITY);break;case t: TRIALS = atoi(optarg);fprintf(fpScreen,“tWindowing enabled with %d trialsn“, TRIALS);printf(“tWindowing enabled with %d trialsn“, TRIALS);BATCH = false;break;case w: WINDOW = atoi(optarg);fprintf(fpScreen,“tInitial window size of %d itemsn“, WINDOW);printf(“tIni
6、tial window size of %d itemsn“, WINDOW);BATCH = false;break;case i: INCREMENT = atoi(optarg);fprintf(fpScreen,“tMaximum window increment of %d itemsn“,INCREMENT);printf(“tMaximum window increment of %d itemsn“,INCREMENT);BATCH = false;break;case g: GAINRATIO = false;fprintf(fpScreen,“tGain criterion
7、 usedn“);printf(“tGain criterion usedn“);break;case s: SUBSET = true;fprintf(fpScreen,“tTests on discrete attribute groupsn“);printf(“tTests on discrete attribute groupsn“);break;case m: MINOBJS = atoi(optarg);fprintf(fpScreen,“tSensible test requires 2 branches with =%d casesn“,MINOBJS);printf(“tSe
8、nsible test requires 2 branches with =%d casesn“,MINOBJS);break;case c: CF = atof(optarg);fprintf(fpScreen,“tPruning confidence level %g%n“, CF);printf(“tPruning confidence level %g%n“, CF);CF /= 100;break;case ?: fprintf(fpScreen,“unrecognised optionn“);printf(“unrecognised optionn“);exit(1);3.3 训练
9、结果训练结果保存在 3 个文件中，还是以刚才的 yu 项目为例：3.3.1 Screen.txt用于给出决策树的显示和测试正确率的报告文件（文本格式） ，其中该文件最后有：Evaluation on training data (94299 items):Before Pruning After Pruning- -Size Errors Size Errors Estimate9110 7023( 7.4%) 303 11706(12.4%) (13.8%) Evaluation on test data (23574 items):Before Pruning After Pruning-
10、 -Size Errors Size Errors Estimate9110 3713(15.8%) 303 3118(13.2%) (13.8%) 这里面的几个数据表示：训练集的大小为 94299 items，裁减前的决策树有 9110 个分支，一共错了 7023 个 items，错误率为 7.4%，裁减后，决策树的决策分支为 303 个，错误个数和错误率分别为 11706 和 12.4%，C45_VC 估计开放测试的错误率为 13.8%，这个数据一般不是很准，主要是我们的训练不规范，训练数据往往达不到理论上所需的数据量。集外测试的大小为 23574 items，裁减前的测试错误率为 15.
11、8%，裁减后为 13.2%。这个例子也很好的说明了裁减对于提高集外测试正确率的意义：裁减后的错误率反而更低！3.3.2 yu.tre裁减之后的决策树（二进制形式） ，可以用于后面介绍的 CAskC45 中。3.3.3 yu.unpruned裁减之前的决策树（二进制形式） ，如果想使用裁减前的决策树，将这个文件换名为yu.tre，用于 CAskC45 中。4. CAskC45 编程说明C45 决策树训练结果需要在码中使用，CAskC45 就是提供这样功能的 C+封装的一个类。在发布版本的 Code 目录中有两个相关文件：AskC45.h 和 AskC45.cpp。调用 C45 非常的简单，步骤如
12、下：4.1 初始化申请一个 CAskC45 的实例，构造函数中给出工程名，例如：CAskC45 myAsk(“C:Testyu”)。这里有三个注意事项：1） 工程名中没有任何后缀，但是最好是全路径2） 在这个路径中必须有该工程名对应的.nam 文件和.tre 文件，而.dat 和.tes 则可以没有。如果没有，则会导致程序退出，因为 CAskC45 中一旦出错有个 exit(1)语句。4.2 AskOneCase初始化成功之后，就可以调用 AskOneCase 来获取对于一个 szCase，决策树给出的决策结果。注意这里 szCase 的格式也是逗号格开的每个属性的值，因为结论属性还不知，所以
13、可以看为空，对于 yu 这个工程，AskOneCase 中的 szCase 就应该是如下格式：myAsk.AskOneCase(“nan,12,32,43,12,”);AskOneCase 有返回值，返回值是结论属性中的第几个。假设结论属性有 N 种取值可能，则返回值可能的取值为 0,1,2,N-1。决策树总能给你一个最可信的答案。4.3 theAnswer调用 AskOneCase 后，就可以从 myAsk.theAnswer 结构中得到决策结果了。从myAsk.theAnswer 中不仅可以获得最可信的决策结果，也可以获得这一决策的可信度，也有可能获得次优的决策结果。typedef str
14、uct tagANSWER_TYPEint nBestClass;double dClassSum;double dLowClassSum;double dHighClassSum; ANSWER_TYPE;/回答的结构#define MAX_ANSWER_NUMBER 10 /回答的最大数目ANSWER_TYPE theAnswerMAX_ANSWER_NUMBER;int nAnswerCount;/记录可能的答案的个数最可信的决策结果就在 theAnswer0.nBestClass 中，其可信度为 theAnswer0.dClassSum，置信区间为 theAnswer0.dLowCla
15、ssSum theAnswer0.dHighClassSum。如果nAnswerCount 大于 1，表示还有次优的决策结论，其相关属性存在于 theAnswer1中。4.4 Demo在发布版本Demo TestC45Result 中给出的是一个示例程序，使用者可以参考。4.5 注意事项CAskC45 不支持多线程，如果需要实现多线程版本，可以使用临界区方式防止重入。CAskC45:AskOneCase 速度足够快，所以使用临界区基本不会影响系统的速度。5. C45 的外围工具简介上述介绍中也可以看出 C45 对于参数需要一些细致的调节，FeatureAnalysis 是提供一些方便的针对 C
16、45 的辅助功能的工具，它提供：1 运行 C45 功能；2 V-Fold 功能；3 属性重要性分析功能；4 属性合并功能；5 -c,-m 扫描功能。具体的可以参见文档C45 外围工具 FeatureAnalysis 使用说明 Ver1.1 。6. C4.5 算法原理介绍6.1 概述:C4.5 算法是机器学习算法中的一种分类决策树算法，其核心算法是 ID3 算法。而所谓的分类决策树算法就是指从大量事例中提取分类规则的自上而下的决策树的机器学习算法。决策树的各部分是:根: 学习的事例集.枝: 分类的判定条件.叶: 分好的各个类.6.2 ID3 算法6.2.1 概念提取算法 CLS1） 初始化参数
17、C=E，E 包括所有训练例，为根。2） IF C 中的任一元素 e 都属于同一个决策类，则创建一个该决策类的叶子节点并终止.ELSE 依启发式标准，选择特征 Fi=V1，V2，V3，Vn并创建判定节点（启发式标准在本节最后作重点讲解） 。V1 V2 V3 Vn划分 C 为互不相交的 n 个集合 C1,C2,C3, ,Cn；3）对任一个 Ci 递归.6.2.2 ID3 算法1） 随机选择 C 的一个子集 W (窗口)作为初始集合。2） 调用 CLS 生成 W 的分类树 DT。3） 顺序扫描 C 搜集 DT 的意外(即由 DT 无法确定的例子 ).4） 组合 W 与已发现的意外,形成新的 W。在这
18、里有两个策略：a) 原 W 加上固定的 n 个例外，|W|递增。b) 留下原 W 中与 DT 的每个叶节点对应的每一个示例，补充例外，保持|W| 不变。5） 重复 2)到 4)，直到无例外为止。6.2.3 ID3 算法对数据的要求1 所有属性的值必须为离散量，也就是说 ID3 算法所处理的都是枚举形式的量。2 每一个训练例的每一个属性必须有一个明确的值，如果训练例中的某一个属性的值丢失的话，那么整个训练例都将不能使用而成为被舍弃的例子。3 相同的因素必须得到相同的结论且训练例必须唯一，也就是说训练例必须唯一且不能有矛盾数据。6.3 C4.5 对 ID3 算法的改进:1 启发式标准的改进，这一点
19、在后面所附的启发式标准中将会作比较详尽的介绍。2 在输入数据上的改进。1) 因素属性的值可以是连续量，C4.5 在处理完所有的离散属性后，对连续量排序并找到所有的分界点，按照这些分界点将这些连续量分成不同的集合后进行处理。与处理离散量时不同的是，同一个连续量的属性在划分决策树时可以应用于决策树的不同层次，而离散量的属性只能应用于决策树的同一层次。但在结论属性上，它的值仍然必须是离散值。2) 训练例的因素属性值可以是不确定的，以 ? 表示，即 C4.5 可以处理数据部分丢失的数据。C4.5 将其归于最接近的一类，并算出可能的误差。但对于结论属性而言，其值却必须是确定的。3为了减小生成树的规模，C
20、4.5 对已生成的决策树进行裁剪。 启发式标准:作为 ID3 算法的启发式标准，应该只跟本身与其子树所包含的决策的信息量有关,故采取信息论中的熵来量度比其他启发式条件更合适。熵是选择事件时选择自由度的量度，其计算方法为1） 计算父节点的熵P j= freq(Cj,S)/|S|；/ P 是先验概率，其中 freq(Cj,S) 为 S 中属于类 Cj 的元素个数。/ m 为 S 中所包含的结论属性的值的数目。 / 并且当 P=0 时，PLOG2（P）=0；2） 计算划分后所得的熵/ 其中 n 为 S 所划分的子集的个数， Si 为 S 的子集。/ INFO（Si）即 1）中所介绍的熵。Gain(X
21、)=INFO(X)-INFOX(X)；为保证生成的决策树最小，ID3 算法在生成子树时，选取使生成的子树的熵(即 Gain(S)最大的的特征来生成子树。以上是 ID3 的处理办法，而 C4.5 在这方面作了进一步的改进。为了减少生成树的规模而进一步加进了子树的信息。其计算方法为：gain_ ratio(S) = Gain(S)/split_ info(S) / 其中 m 为划分的子树的数目。取使下面就怎么计算熵举一个例子：C4.5 例子OUTLOOK TEMP(F) HUMIDITY(%) WINDY(?) CLASS(PLAY)SUNNY 75 70 TRUE YESSUNNY 80 90
22、TRUE NOTSUNNY 85 85 FALSE NOTSUNNY 72 95 FALSE NOTSUNNY 69 70 FALSE YESOVERCAST 72 90 TRUE YESOVERCAST 83 78 FALSE YESOVERCAST 64 65 TRUE YESOVERCAST 81 75 FALSE YESRAIN 71 80 TRUE NOTRAIN 65 70 TRUE NOTRAIN 75 80 FALSE YESRAIN 68 80 FALSE YESRAIN 70 96 FALSE YES表 3.1-1作为 ID3 的例子不能有属性 TEMP 和 HUMIDIT
23、Y,但 C4.5 可以,先看 ID3 算法,不考虑属性 TEMP 和 HUMIDITY.为决定利用哪一个属性进行划分,分别计算每个属性的 Gain(X),取使 Gain(X)最小的属性划分决策树.为此由上表结论属性 CLASS 的熵为：P1=freq(C1,X)/|X|=9/14 ；CLASS=YES 的先验概率P2= 5/14 ；CLASS=NO 的先验概率CLASS 的熵 INFO(CLASS)=P1LOG2(P1)P2LOG2(P2)=0.940 bits再分别对各属性进行统计,以计算各个属性的 Gain(X) 如：CLASSOUTLOOK YES NOT 总计SUNNY 2 3 5OVERCAST 4 0 4RAIN 3 2 5表 3.1-2 CLASSWINDY YES NOT 总计TRUE 3 3 6FALSE 6 2 8表 3.1-3统计完成以后,就可以计算各属性的 Gain(X)OUTLOOK 的熵为：=(5/14)(2/5)LOG2(2/5) (3/5)LOG2(3/5) +(4/14)(4/4)LOG2(4/4) (0/4)LOG2(0/4) +(5/14)(3/5)LOG2(3/5) (2/5)LOG2(2/5) =0.694 bits利用 OUTLOOK 划分决策树后的熵 Gain(X)=INFO(X)INFOX(X)=0.246
