c46决策树工具.txt

One kind of decision-making tree algorithm, can be seen as one kind data mining algorithm ,find the

用于给出决策树的显示和测试正确率的报告文件（文本格式），其中该文件最后有：
Evaluation on training data (94299 items):
     Before Pruning           After Pruning
    ----------------   ---------------------------
    Size      Errors   Size      Errors   Estimate
    9110  7023( 7.4%)    303  11706(12.4%)    (13.8%)   <<
Evaluation on test data (23574 items):
     Before Pruning           After Pruning
    ----------------   ---------------------------
    Size      Errors   Size      Errors   Estimate
    9110  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.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非常的简单，步骤如下：
4.1    初始化
申请一个CAskC45的实例，构造函数中给出工程名，例如：CAskC45 myAsk(“C:\Test\yu”)。这里有三个注意事项：
1）    工程名中没有任何后缀，但是最好是全路径
2）    在这个路径中必须有该工程名对应的.nam文件和.tre文件，而.dat和.tes则可以没有。如果没有，则会导致程序退出，因为CAskC45中一旦出错有个exit(1)语句。
4.2    AskOneCase
初始化成功之后，就可以调用AskOneCase来获取对于一个 szCase，决策树给出的决策结果。注意这里szCase的格式也是逗号格开的每个属性的值，因为结论属性还不知，所以可以看为空，对于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 struct tagANSWER_TYPE
{
        int     nBestClass;
        double   dClassSum;
        double   dLowClassSum;
        double   dHighClassSum;    
}ANSWER_TYPE;//回答的结构
#define MAX_ANSWER_NUMBER 10  //回答的最大数目

    ANSWER_TYPE theAnswer[MAX_ANSWER_NUMBER];
int nAnswerCount;//记录可能的答案的个数
最可信的决策结果就在theAnswer[0].nBestClass中，其可信度为theAnswer[0].dClassSum，置信区间为theAnswer[0].dLowClassSum ～ theAnswer[0].dHighClassSum。如果nAnswerCount大于1，表示还有次优的决策结论，其相关属性存在于theAnswer[1]中。
4.4    Demo
在发布版本\Demo\ TestC45Result中给出的是一个示例程序，使用者可以参考。
4.5    注意事项
CAskC45不支持多线程，如果需要实现多线程版本，可以使用临界区方式防止重入。CAskC45::AskOneCase速度足够快，所以使用临界区基本不会影响系统的速度。

5.    C45的外围工具简介
上述介绍中也可以看出C45对于参数需要一些细致的调节，FeatureAnalysis是提供一些方便的针对 C45的辅助功能的工具，它提供：
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    概念提取算法CLS
1） 初始化参数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。在这里有两个策略：
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．    启发式标准的改进，这一点在后面所附的启发式标准中将会作比较详尽的介绍。
2．    在输入数据上的改进。
1)    因素属性的值可以是连续量，C4.5在处理完所有的离散属性后，对连续量排序并找到所有的分界点，按照这些分界点将这些连续量分成不同的集合后进行处理。与处理离散量时不同的是，同一个连续量的属性在划分决策树时可以应用于决策树的不同层次，而离散量的属性只能应用于决策树的同一层次。但在结论属性上，它的值仍然必须是离散值。
2)    训练例的因素属性值可以是不确定的，以 ? 表示，即C4.5可以处理数据部分丢失的数据。C4.5将其归于最接近的一类，并算出可能的误差。但对于结论属性而言，其值却必须是确定的。
   3．为了减小生成树的规模，C4.5对已生成的决策树进行裁剪。

● 启发式标准:
   作为ID3算法的启发式标准，应该只跟本身与其子树所包含的决策的信息量有关,故采取信息论中的熵来量度比其他启发式条件更合适。
   熵是选择事件时选择自由度的量度，其计算方法为

1）    计算父节点的熵
P j= freq(Cj,S)/|S|；
//  P是先验概率，其中freq(Cj,S) 为S中属于类Cj的元素个数。
//  m为S中所包含的结论属性的值的数目。  
  //  并且当P=0时，P×LOG2（P）=0；



2）    计算划分后所得的熵
//  其中n为S所划分的子集的个数，Si为S的子集。
//   INFO（Si）即1）中所介绍的熵。
   Gain(X)=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    YES
SUNNY    80    90    TRUE    NOT
SUNNY    85    85    FALSE    NOT
SUNNY    72    95    FALSE    NOT
SUNNY    69    70    FALSE    YES
OVERCAST    72    90    TRUE    YES
OVERCAST    83    78    FALSE    YES
OVERCAST    64    65    TRUE    YES
OVERCAST    81    75    FALSE    YES
RAIN    71    80    TRUE    NOT
RAIN    65    70    TRUE    NOT
RAIN    75    80    FALSE    YES
RAIN    68    80    FALSE    YES
RAIN    70    96    FALSE    YES
                                表3.1-1
作为ID3的例子不能有属性TEMP和 HUMIDITY,但 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)=－P1×LOG2(P1)－P2×LOG2(P2)=0.940 bits
再分别对各属性进行统计,以计算各个属性的Gain(X) 如：

        CLASS
OUTLOOK    YES    NOT    总计
SUNNY    2    3    5
OVERCAST    4    0    4
RAIN    3    2    5
             表3.1-2 
        CLASS
WINDY    YES    NOT    总计
TRUE    3    3    6
FALSE    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
同样可得利用WINDY所得的熵　　Gain(X)=0.048
由于Gain(WINDY) ＜Gain(OUTLOOK) 故第一步选用OUTLOOK作为第一步划分的属性,以下各步类推.

以上是ID3的处理办法，而对于C4.5来说，对于离散量要多算一步，即：
gain_ ratio(S) = Gain(S)/split_ info(S)
相对于上例有  
split_ info(OUTLOOK)=－(5/14)×LOG2(5/14)－(4/14)×LOG2(4/14) 
                    －(5/14)×LOG(5/14)
　　　　　　　　　＝1.577
gain_ ratio(X)=Gain(OUTLOOK)/split info(OUTLOOK)
           =0.246/1.577=0.156
同理可以得到其他属性的gain_ration(X)，取其中最大的属性作为划分的特征。