基于决策树的分类
决策树(Decision tree)是一种树形分类器，每个节点表示某种属性测试条件，每个分支代表一个测试输出（即将满足条件的样本子集分配到不同分枝上）。
如此递归直到将样本子集分配到叶子节点上。
从本质上来看，决策树是通过一系列特征对数据分类的过程。
使用决策树进行分类时，需要的过程有： ● 决策树学习：利用样本数据训练生成决策树模型；决策树学习是一种逼近离散值目
标函数的方法，它将从一组训练数据中学习到的函数表示为一棵决策树。
决策树的学习过程采用自顶向下的贪婪搜索遍历所有可能的决策树空间，其核心算法是ID3和C4.5。
● 修剪决策树：去掉一些噪音数据； ● 使用决策树对未知数据进行分类
决策树算法的属性度量选择标准有三种，即信息增益（ID3）、增益比率（C4.5）和基尼指数（Gini Index ）。
决策树算法是建立在信息熵上的。
例如，随机事件会产生高的信息增益，越是偶然的事件带来的信息量越多，越是司空见惯的事情信息量越少。
即信息量的多少与随机事件发生的概率有关，是概率的函数f(p)，相互独立的两个随机事件同时发生引起的信息量是分别引起的信息量之和，即f(pq)=f(p)+f(q)。
具有这一性质的函数是对数函数，即：
I(P)=-log 2P 如果训练集合（样本集）S 有c 个不同的类（这是需要分的类），pi 是S 中属于类i 的概率。
则S 相对于c 个状态分类的熵为：
Inf(S)=-∑p i log 2(p i )c i=1
如果C 为2，我们可以看到S 对于c 个状态分类的熵如下图所示：
即只有在样本集中，两类样本数量相同时，其熵才最高为1，如果只有一种，则熵为0。
我们假设对于S 而言，有n 个条件（检验T ）将S 分为n 个子集s1、s2、s3等，则这些条件得到的信息增益为：
Gain(S,T)=Inf(S)-∑|S i |
S Inf(S i )n i=1
条件（检验结构）分为两种：
● 离散型检验，即对于每个检验都有一个分支和输出； ● 连续型检验，即它的值是一个连续型值（数值），此时可以对其进行排序后，选择
相应的阀值Z。
对于m个连续型值，理论上阀值有m-1个；
ID3算法
ID3决策树的每个节点对应一个非类别属性，每条边对应该属性的每个可能值。
以信息熵的下降速度作为选取测试属性的标准，即所选的测试属性是从根到当前节点的路径上尚未被考虑的具有最高信息增益的属性。
上面的例子中，最后分为买和不买两种，买的人数为640，不买的人为384，总人数为1024。
我们首先计算对于此样本S而言两个状态的熵：
Inf(S)=-(640
1024log2640
1024
+ 384
1024
log2384
1024
)=0.9553
下面我们按照年龄、收入、学生和信誉四个检验T来检测它们对类别的影响：●年龄
➢年轻人中128买，256不买，其Inf(S1)=0.9183
➢中年人中256买，0不买，Inf(S2)=0
➢老年人中256买，128不买，Inf(S3)=0.9183
➢信息增益值为：
Gain(Age)=Inf(S)-|S1|
|S|inf(s1)−|S2|
|S|
inf(s2)−|S3|
|S|
inf (s3)= 0.9553 -384
1024
∗0.9183−
256 1024∗0− 384
1024
∗0.9183 =0.9553 – 0.75*0.9183 = 0.2657
●收入
➢高，160，128，Inf(s1)=0.9911
➢中，160，192，Inf(s2)=0.9940
➢低，192，64，Inf(s3)=0.8113
➢信息增益值
×0.9940 −Gain(income)=0.9544 -（（160+128）/1025）×0.9911 -352
1024
256
×0.8113=0.1311
1024
●学生：0.1697
●信誉：0.0462
我们可以看到，年龄这个因素的信息增益量最大，因此首先使用该检测属性，其结果为：
我们接下来在对子节点进行信息增益的计算：
我们可以看到，按学生分后，就剩下二元的买或不买了。
这个决策依据作出了。
接下来对年龄为老的进行分类，最后结果是：
我们可以看到，根据选择属性的顺序不同和值的不同，最后年龄、信誉和学生与否就作出了最后的决策（每个节点只有一个值），而信誉与否没有参与到决策中去。
我们可以看到，上述决策树的属性值并不是太多，当某个属性的值有很多种时，采用信息增益选择属性就会有很多的问题。
最极端的情况是编号属性，即n个样本有n个值。
ID3算法采用信息增益的方式，而对于一个属性而言，值越多，其信息看起来越纯，熵越高，导致了决策容易偏向多值属性，而直接导致过学习问题（即属性对于判断并无帮助）。
C4.5算法
C4.5算法对于ID3的改进之处在于：
●采用增益比率而不是增益值
●合并连续值属性（不再局限离散值）
●缺乏属性值时也能对样本进行训练
●K次迭代交叉验证
●产生规则
设训练集合S中属性A有c个不同的值，则其分裂信息定义为：
SpInfo(A,S)=-∑|s i|
|S|log2(|s i|
|S|
)
c
i=1
信息比率定义GainRatio(S,A) = Gain(S,A)
Splinfo(S,A)下面是一个训练例子：
●按年龄分为三组（青384，中256，老384）Gain(Age)=0.2657
SpInfo(Age) = -2*3
8log23
8
− 1
4
log21
4
= 1.5613
GainRation(Age)=0.1702
●按收入GainRation(Income) = 0.0849
●按是否学生GainRation(Student)=0.1702
●按信誉GainRation(Credit)=0.0498
对于连续值（编号顺序）的处理，C4.5是采用一个阀值的形式：
对于温度值，我们可以以1/3和2/3处作为阀值点Z，即第一个阀值为（48+60）/2，第二个阀值为（72+80）/2，以此将该值转换为二值。
对于缺失样本的情况，可以通过期望概率值进行处理：
以概率赋值来缺失数据，如A的概率为5/13，B的概率为3/13，C的概率为5/13。