决策树 笔记
对决策树的学习 以及 决策树在文本分类中的应用。
(1) 生活实例
通俗来说，决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：
女儿：多大年纪了？
母亲：26。
女儿：长的帅不帅？
母亲：挺帅的。
女儿：收入高不？
母亲：不算很高，中等情况。
女儿：是公务员不？
母亲：是，在税务局上班呢。
女儿：那好，我去见见。
这个女孩的决策过程就是典型的分类树决策。相当于通过年龄、长相、收入和是否公务员
对将男人分为两个类别：见和不见。
上图完整表达了这个女孩决定是否见一个约会对象的策略，其中绿色节点表示判断条件，
橙色节点表示决策结果，箭头表示在一个判断条件在不同情况下的决策路径，
图中红色箭头表示了上面例子中女孩的决策过程。
这幅图基本可以算是一颗决策树，说它“基本可以算”是因为图中的判定条件没有量化，如收入高中低等等，
还不能算是严格意义上的决策树，如果将所有条件量化，则就变成真正的决策树了。
(2) 定义
决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，
每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，
测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。
(3) 决策树分类步骤
使用决策树进行文本分类时，通常包含3个步骤：特征选择、决策树生成、决策树的修剪。以下分别介绍这3个步骤。
(3.1) 特征选择
特征选择的常用方法就不说了，直接说结果。
通过参考论文和测试，发现使用CHI进行特征选择选择出的特征效果较好。本案例中采用的是CHI改进版。
CHI的主要思想是认为特征和类别关系符合X2分布，X2统计量的值越高，就认为特征和类别间的差异性越小，
则两者的相关性就越高，就可以认为特征对类别的贡献度越大。
X2公式：
n表示特征频数总和
n11 表示特征i在类别j中出现的频数
n12 表示特征i在除类别j外的其它类别出现的频数
n21 表示除特征i外其他特征在类别j中出现的频数
n22 表示除特征i外的其他特征在除类别j外的其他类别出现的频数
但是CHI有一个缺点，在统计时只关系否出现特征，却不管特征在该文档中出现了几次，这会使得他对低频特征
有所偏袒（因为它夸大了低频特征的作用）。为了解决这个问题，对CHI公式进行改进。
X2改进版公式：
从公式可以看到，X2改进版不仅可以看出特征对类别的贡献度，还可以看到特征和类别的相关性。
在改进的X2统计量的值上规定特征i的CHI值为：
s为文本类别的数量
|X2|是X2的绝对值
使用X2改进版进行特征提取后，特征个数较多，假设为M个，为了进一步降维，同时为了各个特征对
各个类别的贡献是否一致，必须将每个特征特征的X2统计量统一处理到一个固定的区间，为[-1, 1]，按公式
其中，max_i min_i 为特征i对各个类别X2统计的最大值和最小值。
这样会得到新的特征个数，假设为L个，L要远小于M
(3.2) 决策树生成
决策树生成是决策树中比较重要的一步。决策树生成的算法有ID3, C45, CART。
(3.2.1) ID3
ID3算法的核心思想就是以信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂。
从信息论知识中我们知道，期望信息越小，信息增益越大，从而纯度越高。
3.2.1.1 熵
在信息论与概率统计中，熵(entropy)是随机变量不确定性的度量。设X是一个取有限个值的离散随机变量，其概率分布为
P(X=xi) = pi i=1,2,…,n
则随机变量X的熵定义为
熵越大，随机变量的不确定性就越大。
3.2.1.2 条件熵
设有随机变量(X,Y),其联合概率分布为
P(X=xi, Y=yi)=pij, i=1,2,…n; j=1,2,…m
条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。随机变量C给定条件下
随机变量Y的条件熵(conditional entropy) H(Y|X)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望
pi = P(X=xi), i=1,2,…,n
3.2.1.3 信息增益
特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即
g(D,A) = H(D) - H(D|A)
3.2.1.4 ID3原理及步骤
ID3算法使用信息增益来分裂训练数据集，选择信息增益值最大的特征，根据该特征的取值来划分数据集。被划分的数据集重复此过程，直到信息增益很小或没有特征选择为止。
H(D)表示数据集D的不确定性
pi表示第i个类别在整个训练数据集(语料)D中出现的概率
Di表示类别i的文档个数
D代表所有文档个数
n代表训练数据集(语料)D的类别个数
H(D|A)表示加入特征A后，数据集D的不确定性
n为特征X的取值个数
Di为特征A取值为i对应的值时的文档个数
D代表所有文档个数
g(D,A) = H(D) - H(D|A)
g(D,A)表示引入特征A后，数据集D减少的不确定程度
ID3算法步骤：
输入：训练数据集D，特征集A，阀值f
输出：决策树T
(1) 若D中所有实例属于同一类Ck，则T为单结点树，并将类Ck作为该结点的类标记，返回T；
(2) 若A为空集，则T为单结点数，并将D中实例数最大的类Ck作为该结点的类标记，返回T；
(3) 否则，计算A中各特征对D的信息增益，选择信息增益最大的特征Ag；
(4) 如果Ag的信息增益小于阀值f，则T为单结点树，并将D中实例数最大的类Ck作为该节点的类标记，返回T；
(5) 否则，对Ag的每一可能值ai，依Ag=ai将D分割为若干非空子集Di，将Di中实例数最大的类作为标记，
构建子结点，由结点及其子结点构成树T，返回T；
(6) 对第i个子结点，以Di为训练集，以A - {Ag}为特征集，递归调用步骤(1) - 步骤(5),得到子树T，返回Ti。
(3.2.2) C4.5
C45算法与ID3算法相似，C45算法对ID3算法进行了改进，C45在生成的过程中，用信息增益比来选择特征。
3.2.2.1 信息增益比
信息增益比的大小是相对于训练数据集而言的，并没有绝对意义。在分类问题困难时，也就是训练数据集
的经验熵大的时候，信息增益值会偏大。反之，信息增益值会变小。使用信息增益值会对这一问题进行校正。
特征A对训练数据集D的信息增益比gr(D,A)定义为其信息增益g(D,A)与训练数据集D的经验熵H(D)之比:
gr(D, A) = g(D, A) / H(D)
gr(D,A)表示引入特征A后使数据集D减少的不确定程度 相比 数据集D的不确定性 的值。
这么做避免了在部分数据集上某些特征信息增益较大的情况，使所有特征的信息增益在整个数据集上做比较，分类效果更好。
3.2.2.2 C45原理及步骤
C45算法使用信息增益比来分裂训练数据集，选择信息增益比最大的特征，根据该特征的取值来划分数据集。
被划分的数据集重复此过程，直到信息增益比很小或没有特征选择为止。
C45算法步骤：
输入：训练数据集D，特征集A，阀值f
输出：决策树T
(1) 若D中所有实例属于同一类Ck，则T为单结点树，并将类Ck作为该结点的类标记，返回T；
(2) 若A为空集，则T为单结点数，并将D中实例数最大的类Ck作为该结点的类标记，返回T；
(3) 否则，计算A中各特征对D的信息增益比，选择信息增益比最大的特征Ag；
(4) 如果Ag的信息增益比小于阀值f，则T为单结点树，并将D中实例数最大的类Ck作为该节点的类标记，返回T；
(5) 否则，对Ag的每一可能值ai，依Ag=ai将D分割为若干非空子集Di，将Di中实例数最大的类作为标记，
构建子结点，由结点及其子结点构成树T，返回T；
(6) 对第i个子结点，以Di为训练集，以A - {Ag}为特征集，递归调用步骤(1) - 步骤(5),得到子树T，返回Ti。
(3.3) 决策树的剪枝
决策树生成算法递归地产生决策树，直到不能继续下去为止，这样产生的树往往对训练数据的分类很准确，
但是对未知测试数据的分类却没有那么准确，即出现过拟合现象。过拟合的原因在于学习时过多地考虑
如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。解决这个问题的办法是考虑决策树的复杂度，
对已生成的决策树进行简化。
决策树很容易发生过拟合，过拟合的原因在于学习的时候过多地考虑如何提高对训练数据的正确分类，
从而构建出过于复杂的决策树。解决这个问题的办法就是简化已生成的决策树，也就是剪枝。
决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。
设决策树T的叶节点有|T|个，
t是某个叶节点，
t有Nt个样本点，
其中归入k类的样本点有Ntk个，
Ht(T)为叶节点t上的经验熵，
α≥0为参数，则损失函数可以定义为：
其中经验熵为
如果剪枝后的损失函数的值小于剪枝前的损失函数的值，则可以剪枝。
C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，
|T|表示模型复杂度，参数α≥0控制两者之间的影响，α越大，模型越简单，α=0表示不考虑复杂度。
剪枝，就是当α确定时，选择损失函数最小的模型。
子树越大C(T)越小，但是α|T|越大，损失函数反映的是两者的平衡。
决策树的生成过程只考虑了信息增益或信息增益比，只考虑更好地拟合训练数据，
而剪枝过程则考虑了减小复杂度。前者是局部学习，后者是整体学习。
References
决策树
[1]《统计学习方法》 李航
[2] df.pdf
[3] 码农场 决策树介绍
[4] decision-tree
[5] 我们为什么需要信息增益比，而不是信息增益
[6] IBM 决策树算法介绍及应用
[7] decisiontree
[8] 决策树
[9] Learning to Classify Text
[10] 决策树+文本分类
决策树 文本分类
[11] 江苏科技大学2011年硕士论文
[12] 东北大学2008年硕士论文
[13] 博客 决策树
特征提取:
[14] 基于类内词频改进互信息特征选择算法
[15] 文本挖掘之特征选择
[16] 特征选择
[17] 特征选择