文档介绍：决策树
第一页，讲稿共三十六页哦
决策树和决策规则是解决实际应用中分类问题的数据挖掘方法。
一般来说，分类是把数据项映射到其中一个事先定义的类中的这样一个学****函数的过程。由一组输入的属性值向量(也叫属性向量)和相应的类，用基于归的加权和：
infox1(T)=5/14(-2/5log2(2/5)-3/5log2(3/5))
+4/14(-4/4log2(4/4)-0/4log2(0/4))
+5/14(-3/5log2(3/5)-2/5log2(2/5))
=
相应的增益: Gain(x1)=-=
第十六页，讲稿共三十六页哦
按属性3分区可得子集的熵的加权和：
infox2(T)=6/14(-3/6log2(3/6)-3/6log2(3/6))
+8/14(-6/8log2(6/8)-2/8log2(2/8))
=
相应的增益: Gain(x2)=-=
由于属性2是数值型的连续数据，不能简单按上面方式计算。：
“标准”检验，对属性的每个可能值有一个分枝和输出。
第十七页，讲稿共三十六页哦
，通过将该值和阈值Z比较，用输出Y≤Z和Y＞Z定义二元检验。
，该检验中属性的每个可能值被分配到许多易变的组中，每组都有一个输出和分枝。
数值型属性检验：
对于属性Y，按训练样本进行分类，分类顺序用{v1,v2,…,vm}表示，因此对Y仅有m-1个分区，要系统在检查所有分区以求得最优分区。通常选择区间的中点为阈值。
第十八页，讲稿共三十六页哦
{vi,vi+1}的最小值vi为阈值。这确保出现结果中阈值属于数据库的一个值。
对于上例，属性2的值的集合是:
{65,70,75,78,80,85,90,95,96}
可能的阈值Z的集合是:
{65,70,75,78,80,85,90,95}。
从这8个值里选择最优的阈值(最高信息增益)，最优的Z=80。(如果计算?)
第十九页，讲稿共三十六页哦
对应属性2的检验3(属性2≤80和属性2＞80)的信息增益计算：
infox3(T)=9/14(-7/9log2(7/9)-2/9log2(2/9))
+5/14(-2/5log2(2/5)-3/5log2(3/5))
=
相应的增益: Gain(x3)=-=
属性1的增益最高，选择该属性进行首次分区。每个属性值具有一个分枝，产生3个分枝，如图7-4所示.
第二十页，讲稿共三十六页哦
对每个分枝重复上述步骤选择检验和最优化过程。对于子节点T2子集，4个样本都是类1，该节点是叶节点。
第二十一页，讲稿共三十六页哦
对于余下的节点，在T1中有5个样本，最优检验有两个选择：属性2≤70和属性2＞70的检验x4。
info(T1)=-2/5log2(2/5)-3/5log2(3/5)
=
infox4(T1)=2/5(-2/2log2(2/2)-0/2log2(0/2))
+3/5(-0/3log2(0/3)-3/3log2(3/3))
=0
Gain(x3)=-0=
产生两个分枝为最终叶节点，分枝中的数据子集属于同一类。
第二十二页，讲稿共三十六页哦
对根节点下的T3子集进行同样的计算，按属性3=真和属性3=假检验，产生两个叶节点。图7-5表示数据库T的最终决策树。
第二十三页，讲稿共三十六页哦
另外，决策树可以用可执行代码（或伪代码）的形式表示。图7-6用伪代码给出了上面例子的决策树。
第二十四页，讲稿共三十六页哦
增益标准对具有许多输出的检验有严重的偏差，根据info(S)的定义，指定一个附加的参数：
这表示通过把集T分区成n个子集Ti而生成的潜在信息。现在，定义一个新的增益标准：
Gain-radio(X)=gain(X)/Split-info(X)
第二十五页，讲稿共三十六页哦
未知属性值
。但是在一个数据库，经常会缺少某些样本的一些属性。由于该属性值与某个样本是不相关