c46决策树工具.txt

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

C45决策树工具 使用说明
1.    简介：
本文档给出了有关C45决策树方法相关的一些资料，面向对象是研究人员。本文档的内容安排如下：
1．    C45决策树方法的使用场合描述；
2．    C45决策树如何训练，即C45_VC.exe使用说明；
3．    C45决策树训练结果如何在代码中使用，即CAskC45编程说明；
4．    C45的外围工具简介；
5．    C45的原理说明；
6．    联系方式。

2.    适合用C45解决的问题
C45是一种决策树的算法，可以理解为数据挖掘算法的一种。从大规模的数据中挖掘规律，这里的大规模数据一般是用属性来描述，属性本身可以是连续量，如语音数据的基频值；也可以使离散量，如句子中词的个数；还可以使枚举量，如26个词类，声韵母类型等。属性分为输入属性，和结论属性（或称决策属性）。结论属性就是我们希望从输入属性中得到的结果，如希望从输入的词性序列中预测某个位置是不是L3边界，或者根据前后的音调、基频等预测当前的音节应该是哪一类的韵律曲线。结论属性必须是枚举量（当然包括布尔量）。而规律则以决策树的形式来表示，其形式如，在C45_VC.txt或者Screen.txt中可以看到类似的输出结果：
Decision Tree:
e_lv <= 47.6 :      如果e_lv属性值小于等于47.6的话
|   n_lv <= 45.8 : NeiWen (76.0/2.0)   如果n_lv值小于等于45.8，结论属性应该是NewiWen。
|   n_lv > 45.8 : NeiBuWen (44.0)        如果n_lv值大于45.8，结论属性应该是NewiBuWen。
e_lv > 47.6 :     如果e_lv属性值大于47.6的话
|   n_lv <= 45.8 : WaiWen (147.0)        …
|   n_lv > 45.8 : WaiBuWen (32.0)        …
注：n_lv <= 45.8 : NeiWen (76.0/2.0)中的76.0表示到这个决策分支的有76个例子，其中2.0是错误的例子数目。这里有可能出现小数，这是决策树根据概率计算过程中可能将一个例子划分到多个子分支，每个分支算是（0.几）个事例到此。
这里同时给出关于使用C45决策树方法的一些注意事项：
1）    C45是狂揉的，只要你给它输入属性和输出属性，即使输出和输入之间没有任何关系，决策树一样可以给出很不错的决策正确率，尤其是集内测试正确率。
2）    要避免上述问题，两个方面重要：（1）集外测试，集内测试不说明问题。集外测试也要有一定的数目，这样才可以得到比较可信的测试结果。（2）输入数据量，理论上训练例子的个数应该是所有属性空间大小的10倍。属性空间大小计算为：每个属性可能的取值的种类数的连乘积。比如输入属性是3个词类，而每个词类可能有32种可能，则理论上需要的训练例子数为：32×32×32＝32768个。当然考虑到有些词类组合不可能出现，所需训练例子数可以筹减。
3）    理论上，C45能自动排除那些不相关的属性，但是在训练数据稀疏的情况下，决策树一样会利用那些不相关的属性，得到一些结论。所以不能一咕脑儿把所有的属性扔给决策树，还是需要对输入属性与输出属性之间有没有关联进行仔细的分析。
4）    决策树的结论属性不宜太多。超过20就是很不好了，因为决策树认为结论属性完全是枚举类型的，结论属性之间的各个可能的取值没有任何关系，如果问题中结论属性有一定的连续意义，比如预测一个韵律环境下音节应该的长度，那么则决策树的效果就很有可能比其他的类似于拟合的算法差了。
5）    决策树在分析各个属性时，是完全独立的。比如如果其实数据中只需要一条规律：“属性A的值比属性B的值大的时候，输出为1，否则为0”的话，决策树无法给出这样的规律，因为它只会尝试属性A和某个常数的比较，属性B和某个常数的比较，而不会比较属性A和属性B的差值。如果觉得数据中可能存在这样的规律的话，可以将属性A和属性B的差值作为一个新的属性（记为C）输入决策树训练算法，那么决策树有可能得出这样一条简洁的规律：如果属性C大于0，那么输出为1，否则为0。

3.    C45_VC.exe使用说明：
3.1    数据准备工作：
而对于使用者来说，最重要的是要知道C4.5的输入数据格式，下面就详细介绍一下：
现在假设我们所要研究的项目的名称是yu，则对于C4.5训练而言就至少需要两个文件yu.nam和yu.dat，其中yu.nam是输入数据的格式文件，它定义了输入数据文件的格式，而yu.dat则是严格按照这个格式所生成的输入数据文件。在 C45发布版本中有这个例子，在Demo\Test目录中。下面就这两个文件举一个例子，并同时对其中的符号的意义作一下解释：
下面是格式文件yu.nam

NeiBuWen,NeiWen,WaiBuWen,WaiWen.
xing_bei:                  nan , nv.
e_lv:                      continuous.
n_lv:                      ignore.
p_lv:                      discrete  6.
l_lv:                     continuous.
在文件yu.nam中，第一行是输入数据的决策类，必须是枚举量，也就是说每个值本身对C4.5而言并没有什么特殊的意义，仅仅是作为一个枚举量处理而已。以后几行是属性定义部分，以一个属性名和一个冒号开头，后根一个类型和一个句号，一行说明一个属性。如上，xing_bei是一个枚举型的属性，后面是它所能取的值；e_lv是一个连续量，用C45的关键字continuous表征，可以是整型或浮点型；n_lv这个属性是被忽略不考虑的属性，用关键字ignore表征；p_lv是不大于6的自然数；l_lv又是一个连续量。发布版本中的yu.nam文件中则所有的lv都是continuous类型的。注意：最后一个continuous.之后，还需要一个回车符号，这是因为C45_VC.exe的Bug导致的。
    相应的有yu.dat为：
nan,23.8,62.5,21.7,60,NeiBuWen.
nan,61.9,25,17.4,65,WaiWen.
nv,81,29.2,34.8,65,WaiWen.
nv,57.1,29.2,34.8,50,WaiWen.
nan,42.9,83.3,34.8,40,NeiBuWen.
nan,52.4,12.5,13,45,WaiWen.
nan,42.9,41.7,17.4,60,NeiBuWen.
nan,66.7,50,4.3,40,WaiBuWen.
nv,23.8,41.7,8.7,65,NeiBuWen.
如上，在输入数据文件中，每一个训练例占一行；在一行中，按照先因素属性后决策属性的顺序，因素属性按照说明先后的顺序依次输入属性值，中间用逗号隔开，以句号结束。
从上述讨论可以看到，对C4.5的应用的关键就在于如何组织输入的格式文件和数据文件，也就是数据的预处理。yu.tes文件格式和yu.dat完全一样，但理论上数据应该不一样，因为一个是训练数据，一个是用于测试开放正确率。如果用到C45辅助工具：FeatureAnalysis.exe，则很可能还需要一个文件：yu.crs，这个文件格式和yu.dat还是一样，用于交叉集的测试。训练集:交叉集:测试集的例子数目之比一般为：4:1:1。
3.2    训练过程
C45的训练过程利用C45_VC.exe。这是一个控制台（Console）程序，其最基本的调用格式为：
C45_VC.exe –f yu
其中-f表示后面接了项目名称，这里是yu。C45_VC.exe还支持多个参数，这些参数的设置对效果有很多好处，请多加利用，下面一个一个说明，按使用频度排序：
3.2.1    –f 项目名
后接项目名称，注意不要.nam后缀名
3.2.2    –u
利用训练生成的决策树检测对应的.tes文件。
3.2.3    –s
尝试对枚举类型的属性进行聚类分析，比如某个属性（记为CiLei）是词类属性，有：a,b,c,d,e,f,…,z共26种可能，如果不用-s参数，则一旦用到CurrentCiLei属性，那么会把决策树一下子生成26个子分支，而用到-s参数之后，则C45_VC自动尝试可能的词类组合，生成的子分支可能是：
|   |   CurrentCiLei = p: 1 (2.0/1.0)
|   |   CurrentCiLei in {b,e,g,h,i,j,k,l,r,u,w,x,y,z,new,old,{,0} 1 (0.0)
|   |   CurrentCiLei in {a,c,d,f,m,n,o,q,s,t,v,ngp}
这样有助于提高训练的效果。
3.2.4    –m 数字
-m后面接的数字表示当一个决策分支中必须有大于等于数字个支撑事例时才可能继续往下细分。比如-m 5表示，如果到这个分支的时候，还有超过5个实例，那么才尝试是不是继续往下分。
这个参数有助于提高集外测试正确率。
3.2.5    –c 数字
-c 后面接的数字表示裁减到的比例，决策树有个裁减的概念，先会生成一个完整的决策树，然后进行裁减，裁减有助于提高决策树的集外测试正确率，缺省裁减到25%。注意是裁减到原先的25％。后面的数字必须是整型，-c 5就表示裁减到原先的5%。裁减越多一般来说集内测试正确率降低而集外测试效果上升。
3.2.6    –v 数字
输出调试信息的级别，数字的范围是0,1,2,3,4,5。0表示输出最少（当然也是最重要的调试信息），而5表示输出最多的信息，缺省为1
3.2.7    –b
决策树裁减过程中允不允许使用窗口的设置选项，训练中使用窗口是为了提高训练速度，窗口有两个相关属性：WINDOW和INCREMENT。下面是关于WINDOW和INCREMENT意义的说明：
/*  Construct a classifier tree using the data items in the                 */
/*  window, then test for the successful classification of other            */
/*  data items by this tree.  If there are misclassified items,             */
/*  put them immediately after the items in the window, increase         */
/*  the size of the window and build another classifier tree, and        */
/*  so on until we have a tree which successfully classifies all             */
/*  of the test items or no improvement is apparent.                     */
-b表示不使用WINDOW机制，训练效率可能会下降，缺省情况下是使用窗口的，缺省值定义如下：
/*  If necessary, set initial size of window to 20% (or twice
    the sqrt, if this is larger) of the number of data items,
    and the maximum number of items that can be added to the
    window at each iteration to 20% of the initial window size  */
3.2.8    –w
设置初始的窗口WINDOW的大小。
3.2.9    –i
设置初始的最大INCREMENT值。
3.2.10    –p
在裁减决策树时使用概率的方式，即Soft的裁减方式，不是硬性规定是哪个分支。
3.2.11    –g
在决策树训练过程中，决策树采用Gain值的概念，可以有两种方式的Gain值定义：
/************************************************************************    */
/*                                                                           */
/*  Determine the worth of a particular split according to the                           */
/*  operative criterion                                                          */
/*                                                                           */
/*          Parameters:                                                      */
/*              SplitInfo:      potential info of the split                              */
/*              SplitGain:      gain in info of the split                            */
/*              MinGain:        gain above which the Gain Ratio                  */
/*                              may be used                                  */
/*                                                                           */
/*  If the Gain criterion is being used, the information gain of                             */
/*  the split is returned, but if the Gain Ratio criterion is                                */
/*  being used, the ratio of the information gain of the split to                            */
/*  its potential information is returned.                                           */
/*                                                                           */
/************************************************************************    */
-g选项表示使用 the ratio of the information gain的方式，否则使用the information gain的值的方式，这一选项影响的是判断是否继续往下分时候的结论可能不同。
缺省为使用the information gain方式。
3.2.12    –t 数字
当TRAILS达到数字后，开始使用窗口机制。
3.2.13    下面的是C45_VC.exe的代码中的相关部分：
switch (o)
    {
    case 'f':   FileName = optarg;
            fprintf(fpScreen,"tFile stem <%s>n", FileName);
            printf("tFile stem <%s>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 evaluated 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 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("tInitial 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 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("tSensible 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    训练结果
训练结果保存在3个文件中，还是以刚才的yu项目为例：
3.3.1    Screen.txt