算法原理
背景知识
决策树（Decision Tree）是一个类似流程图的树结构，其中每个内部节点表示在一个属性上的测试，每个分支代表一个测试输出，而每个树叶节点代表类或类分布。
下图是一个简单的决策树：
他代表了概念buys_computer，指出某数据集上的顾客是否可能购买计算机。其中每个内部(非树叶)节点表示一个属性上的测试，每个树叶节点代表一个类(buys_computer=yes或者buys_computer=no)。
决策树归纳的基本算法是贪心算法，他以自顶向下递归的各个击破方式构造决策树。DMTree算法是根据决策树算法的原理得出的，同时参考了SLIQ算法、RainForest决策树框架的思想。
算法基于在不同属性的不同值上获得最大的信息获取率（可以是gini指标、information gain指标等等）对训练样本集不断地进行分裂，经过分裂之后得到的每一个子训练集会再次分裂，这个过程以广度优先的方式展开，重复进行，直到所有节点都满足停止继续分裂的条件。
在模型生长的过程中和过程结束之后，需要使用MDL算法对生成的模型结果进行裁剪，以避免训练数据中的噪声和孤立点样本影响模型最终的准确率，进而造成过度适应（over fit）。
在生成的模型结果方面，该算法与普通决策树不同的是，DMTree算法生成的结果是一个二叉树。每个内部节点只有两种分类原则：对于数值型字段，它代表左子树x<=A，右子树x>A，其中A是一个数值；对于种类型字段，它代表左子树xÎB，右子树xÏB，其中B是字段所有可能值的一个子集。生成的二叉树具有比普通的决策树模型更优秀的模型表述能力，同时通过自上而下的遍历，模型结果也很容易转换成容易理解的规则集。
算法原理
已知：
a) 每个数据样本用一个n维特征向量表示，分别描述n个属性样本的n个度量。
b) 有m个类
c) 每个训练样本有一个类型属性C，s个样本构成了训练数据集S
求解：
给出一个决策树分类模型，预测一个新的数据样本X所属的类。
算法的思路：
1. 算法概述
首先，扫描数据库中的数据集，将DBMS表中的数据转移到Disk上。以后一直对磁盘数据进行操作，这样比对直接DBMS进行读取速度要快很多，同时不需要将数据全部保存在内存中。
数据准备完成以后，输入数据集和被划分成训练数据集和测试数据集。挖掘算法将在此基础上运行。
算法主体使用了一个决策树，对于叶子节点维护了一个队列。算法使用广度优先策略一层一层的构造生长整个决策树的结构，每次都在新生长出来的那一层的每个叶子节点里面寻找最佳分割点，进而进行划分。
算法主体的结构如下：
Do A Sampling //按照参数指定比例进行抽样
while(当前叶子节点队列不为空) do //对训练集进行树生成的训练
For Each 叶子节点 do
Generate the AVC-Group From the DataPartition
For each 字段 do //最佳分割的计算
Call CL.find_best_partitioning(AVC-set of p);
End;
CL.decide-splitting_criterion();
Create LeftChild and RightChild;
End;
PruneWholeTree;
For Each 老的 叶子节点 do
If(的确需要分割)
Use best split to partition D into D1, D2;
Put LeftChild and RightChild Into New 叶子节点队列;
End;
End;
PruneWholeTree();
在测试集上进行打分，得出树的准确率;
其中，数据结构AVC_Group是对于输入的训练数据的压缩，它利用hash表分别压缩存放数值型和种类型字段。由于采用了先进的索引技术，AVC_Group的使用可以大大降低算法的内存消耗量，提高算法的运行效率。AVC_Group的计算需要利用在DBMS转存到File时候形成的一些统计信息，如Max, Min, 种类字段的不同值的个数等等。
总的来说，这种算法的好处：
1） 可以采用多种 分割指数：Gini,Entropy,Twoing Power-Modified Twoing，等等。
2） 潜在很大的并行化处理的可能。
3） 将修剪和生成结合起来，避免了树得太深扩张。同时使用MDL方法，免除了测试集的多次使用。
4） 消除了对于内存的巨大要求。只要能够将AVC-Group放入内容就可以了。
2. 修剪问题
在算法的运行过程中需要随时对决策树结构进行修剪，以避免“过度适应”，修建的原则称为MDL原则，使用MDL方法对决策树进行剪枝的目的就是寻找一棵能用最少的bit来对其进行描述的树。
对一棵决策树进行描述包括以下三方面的内容：
1) 对树的结构进行描述
2) 对每个内部节点中的分割进行描述，包括所选的属性和分割的值。
3) 对每个叶子节点中属于各个类的数据进行描述。
三方面的内容如下：
1. 对树的结构进行描述。只需要一个bit就可以区别是内部节点(1)还是叶子节点（0）。由于是二叉树，所以这些信息就可以足以表示树的结构了。
2．对分割的描述。首先是对属性的选择，假设一共有a个属性，那么需要log a个bit。然后是对分割值的描述。假设所选属性中有v个不同的值，那么对于数值字段需要log v-1个bit；对于种类字段，需要log 2v-2个bit。将两个相加就是对分割的描述（记为Csplit(N)）。
3．对每个叶子节点中数据的描述。假设所有数据中一共有k个类别。该结点中包含n条记录，每个类别包含ni条记录。则描述数据需要的bit计算如下：
注：最后一个符号为Gamma。定义如下：Gamma(x+1)=x*Gamma(x) (x>0)，Gamma(1/2)=sqrt(PI)，Gamma(1)=1；
从而Gamma(k/2)=(m-1)! 如果k=2m；Gamma(k/2)=(m-1)! * (1/2) * sqrt(PI) k=2m+1。
float ComputerCost&Prune(Node N)
{
if ( N is a leaf) return (C(S)+1)
//N1 and N2 are N’s Children
fMinCost1 =ComputerCost&Prune(N1);
fMinCost2=ComputerCost&Prune(N2);
fMinCostN =min(C(S)+1,Csplit(N)+1+fMinCost1+fMinCost2);
if(fMinCostN =C(S)+1)
Prune child nodes N1 and N2 from tree
Return fMinCostN
}
用于运行中修剪的算法
float ComputerCost&PruneDuringBuilding(Node N)
{
if N is a “yet to be expanded” leaf
return lower bound on subtree cost at N
if N is a “pruned” or “not expandable leaf return (C(S)+1)
//N1 and N2 are N’s Children
fMinCost1 =ComputerCost&PruneDuringBuilding (N1);
fMinCost2=ComputerCost&PruneDuringBuilding (N2);
fMinCostN =min(C(S)+1,Csplit(N)+1+fMinCost1+fMinCost2);
if(fMinCostN =C(S)+1)
{
Prune child nodes N1 and N2 from tree
Delete nodes N1 and N2 and all their children from tree
Mark node N as pruned
}
Return fMinCostN
}
lower bound on subtree cost at N 的计算可以分成不同的精细程度。
1） 就作为1计算
2） 更加精确的计算方法
当前版本采用SLIQ,SPRINT算法中使用的C(S)的计算方法，C(S) =等于节点中不属于大多数类别的记录一个之和。这里需要考虑 CostMatrix和Priors
3. CL的采用
当前采用类似 SLIQ的方法，分割指标使用Gini。今后的版本中，会不断的扩充可以采用的分割指标。
For each 字段
{
If 字段是 数值字段
{
遍历所有可能的分割，计算每种分割的 Gini
然后取得一个最佳的分割
}
if 字段是种类字段
{
if (种类的值 <K)
{
完全遍历所有的组合，计算每种的Gini
取得一个最佳的分割
}
if(种类的值 >=K)
{
采用贪心算法进行搜索，计算每次的Gini
取得一个最佳的分割
}
}
对于不同字段的分割中，选择出一个最佳的分割，作为该节点的分割。
}
4. 分割指标与最佳分割的计算
分割指标与最佳分割的计算参考下面的算法，
Int BestSplit_Gini()
begin
for( each 属性) do
if(数值字段或者日期字段) then
BestSplit_Gini_Numerical()
if(种类字段) then
BestSplit_Gini_Categorical()
计算是不是比当前最佳分割要好：这里需要将 ColumnAdjust
结合进来，其最后的GiniGain应该是
=原始的GiniGain / ColumnAdjust。
更新信息：最佳分割所在字段，最佳分割的值
end;
end;
BestSplit_Gini_Numerical()
begin
数值从小到大一个个进行计算
初始时，所有的记录都在右子树上，每次将这个数值的记录移动到左子树上
Calculate_Gini(本节点记录分布，
左子节点记录分布，右子节点记录分布)
如果Gini值更好，更新最好分割的数值和Gini值
end;
BestSplit_Gini_Categorical()
begin
使用贪心算法进行求解
end;
Calcaulate_Gini(本节点记录分布，左子节点记录分布，右子节点记录分布)
begin
//计算这种分割的Gini Gain
这种分割的Gini Gain =Gini_本节点
—(P1 * Gini左子节点 + P2 * Gini右节点)
p1,p2表示左右节点中记录的比率。
一个节点的Gini值= 。其中是某个类别出现的次数
这里需要将 Class的Prior结合进来，
设类别I的Prior为Ri，那么计算公式变成
Gini值=
end;
限制条件
输入数据，至少有一个字段是种类字段，用于输出类别标签。
输出结果
算法的最终输出结果为一棵可以导出分类准则的决策树，基于这棵树，用测试集进行打分，可以得到这个模型的准确率。
同时，基于这个结构，对于某个未知类别样本X，可以输出它的类别，形式为一个简短的report。
算法优点和缺点
优点：
a) 计算具体类别的工作放在运行期，用户使用该模型会相当的快。
b) 模型准确率比较高。
c) 直观的规则或者谓词表达模型结果。
缺点：
a) 建模速度比较慢。
可能的改进：
丢失值的处理。
算法举例
给定如下的表格作为算法的训练数据集：
需要给出类别字段：buys_computer
算法首先把训练集导入到磁盘文件中。然后，根据文件生成AVC_Group，一个AVCGroup包含若干个AVCSet，每个字段对应一个AVCSet，对于数值型和种类型字段，将生成不同类型的AVCSet：数值型字段的AVCSet是一个长度为BinCount（默认值1000）的hash表，表中存放着不同的值以及不同值的个数。当hash函数发生冲突的时候，解决冲突的方案是采用链表的方式。种类型字段不同的种类值存放在不同的AVCItem里面，没有使用hash。
当AVC_Group制作完成以后，再加上一些对输入数据集的校验工作，数据准备基本完成了，开始进入创建决策树结构的算法运行阶段。
初始的时候，只有一个节点：根结点。以后每次树生长一层，操作只针对当前所有的叶子节点。
对每一个节点而言，算法使用gini指标计算该在不同的属性上不同的划分准则下得到的节点的gini指数，对数值字段使用遍历的方法，对种类字段使用贪心算法，目的是为了寻找gini指标最高的（对数值字段而言是较高的）划分。
找到划分以后，执行节点分裂，同时进行运行期的修剪。
当所有的节点都达到了生长极限（满足预定的停止分裂标准），整个算法就宣告停止。在此之后，还将进行一次整体修剪，以优化结构。
当所有的任务完成之后，需要进行模型结果的打分，打分的结果（模型准确率）将作为结果返还给用户。