决策树

决策树是一种常见的if-then规则的集合。在某种程度上反应空间联合概率密度分布，关于if-then结构这又一篇不错的arXiv文章
ATOMIC: An Atlas of Machine Commonsense for If-Then Reasoning
决策树大致分为3步：(1)特征选择，(2)决策树的生成，(3)决策树的剪枝。
if-then规则的重要性质：互斥且完备。每一个实例只被一条规则和路径覆盖。

决策树的条件概率分布

在此吐槽一下李航，写的确实不如周志华大佬的好，很多问题的表达都不明确，图画的也很糟糕，理解起来确实麻烦。

图中A，B是并列关系，A为基础的划分空间，B为A的概率分布，即$F(x_1,x_2)$F(x1​,x2​)的值，如果$F(x_1,x_2) >0.5$F(x1​,x2​)>0.5则记为1，否则记为0，得到图A中的+1，-1的关系。树在不进行放缩的情况下，进行的是垂直超平面划分空间，k-d树的划分方式也是一样的，最后得到每个区域的结果分类。

特征选择

特征选择的基本方法为选择有利于区分数据集的特征。通常有信息增益和信息增益比以及基尼系数等

1.信息熵

信息的不确定性可以用熵来表示：
对于一个取有限个值的随机变量X，如果其概率分布为：
$P(X=x_i)=p_i,i=1,2,⋯,n$P(X=xi​)=pi​,i=1,2,⋯,n
那么随机变量X的熵可以用以下公式描述：
$H(X)=−\sum_{i=1}^{n}p_ilogp_i$H(X)=−i=1∑n​pi​logpi​

2.条件熵(Conditional Entropy)与信息增益（Information Gain）

信息的不确定性我们用熵来进行描述。很多时候，我们渴望不确定性，但是又有很多时候，我们也讨厌不确定性，所以在这种情况下，我们又要竭力去消除系统的不确定性。

那怎么样去消除系统的不确定性呢？当我们知道的信息越多的时候，自然随机事件的不确定性就越小。举个简单的例子：
如果投掷一枚均匀的筛子，那么筛子出现1-6的概率是相等的，此时，整个系统的熵可以表述为：
$H(c)=−\frac{1}{6}log_2\frac{1}{6}×6=log_26$H(c)=−61​log2​61​×6=log2​6

如果我们加一个特征，告诉你掷筛子的结果出来是偶数，因为掷筛子出来为偶数的结果只可能为2,4,6，那么此时系统的熵为:
$H(c)=−\frac{1}{3}log_2\frac{1}{3}×3=log_23$H(c)=−31​log2​31​×3=log2​3
因为我们加了一个特征x：结果为偶数，所以整个系统的熵减小，不确定性降低。
来看下条件熵的表达式：
1.当特征$x$x被固定为值$x_i$xi​时，条件熵为: $H(c|x=x_i)$H(c∣x=xi​)
2.当特征$X$X的整体分布情况被固定时，条件熵为:$H(c|X)$H(c∣X)
应该不难看出：
$H(c|X)=−p(x=x_1)H(c|x=x_1)⋯−p(x=x_n)H(c|x=x_n) \\ =−∑_{i=1}^{n}p(x=x_i)H(c|x=x_i) \\ =−∑_{i=1}^np(x=x_i)p(c|x=x_i)log_2p(c|x=x_i) \\ =−∑_{i=1}^np(c,x_i)log_2p(c|x=x_i)$H(c∣X)=−p(x=x1​)H(c∣x=x1​)⋯−p(x=xn​)H(c∣x=xn​)=−i=1∑n​p(x=xi​)H(c∣x=xi​)=−i=1∑n​p(x=xi​)p(c∣x=xi​)log2​p(c∣x=xi​)=−i=1∑n​p(c,xi​)log2​p(c∣x=xi​)
其中，n为特征XX所出现所有种类的数量。

那么因为特征X被固定以后，给系统带来的增益(或者说为系统减小的不确定度)为：
$IG(X)=H(c)−H(c|X) \\ =−∑_{i=1}^np(c_i)log_2p(c_i)+∑_{i=1}^np(x=x_i)H(c|x=x_i)$IG(X)=H(c)−H(c∣X)=−i=1∑n​p(ci​)log2​p(ci​)+i=1∑n​p(x=xi​)H(c∣x=xi​)

3.信息增益做特征选择的优缺点

先来说说优点：
1.信息增益考虑了特征出现与不出现的两种情况，比较全面，一般而言效果不错。
2.使用了所有样例的统计属性，减小了对噪声的敏感度。
3.容易理解，计算简单。

主要的缺陷：
1.信息增益考察的是特征对整个系统的贡献，没有到具体的类别上，所以一般只能用来做全局的特征选择，而没法针对单个类别做特征选择。
2.只能处理连续型的属性值，没法处理连续值的特征。
3.算法天生偏向选择分支多的属性，容易导致overfitting。

4.信息增益比(Infomation Gain Ratio)

前面提到，信息增益的一个大问题就是偏向选择分支多的属性导致overfitting，那么我们能想到的解决办法自然就是对分支过多的情况进行惩罚(penalty)了。于是我们有了信息增益比，或者说信息增益率：
特征X的熵：
$H(X)=−\sum_{i=1}^{n}p_ilogp_i$H(X)=−i=1∑n​pi​logpi​

特征XX的信息增益 ：
$IG(X)=H(c)−H(c|X)$IG(X)=H(c)−H(c∣X)

那么信息增益比为：
$gr=\frac{H(c)−H(c|X)}{H(X)}$gr=H(X)H(c)−H(c∣X)​
在决策树算法中，ID3使用信息增益，c4.5使用信息增益比。可以考虑引入λ来调节H(X)的比重。

5.Gini系数

Gini系数是一种与信息熵类似的做特征选择的方式，可以用来数据的不纯度。在CART(Classification and Regression Tree)算法中利用基尼指数构造二叉决策树。
Gini系数的计算方式如下：
$Gini(D)=1−∑_{i=1}^np^2_i \\ Gini-index(D)=\sum_{v=1}^V\frac{|D_v|}{|D|}Gini(D)$Gini(D)=1−i=1∑n​pi2​Gini−index(D)=v=1∑V​∣D∣∣Dv​∣​Gini(D)

其中，D表示数据集全体样本，$p_i$pi​表示每种类别出现的概率。取个极端情况，如果数据集中所有的样本都为同一类，那么有$p_0=1\quad Gini(D)=0$p0​=1Gini(D)=0，显然此时数据的不纯度最低。
与信息增益类似，我们可以计算如下表达式：
$ΔGini-index(X)=Gini-index(D)−Gini-indexX(D)$ΔGini−index(X)=Gini−index(D)−Gini−indexX(D)
很明显，在做特征选择的时候，我们可以取$ΔGini-index(X)$ΔGini−index(X)最大的那个。基尼系数和信息熵有相同的特点，也容易陷入过拟合。

决策树生成

ID3算法

输入：训练集D，特征集A，阈值ε
输出：决策树T
if D中的值 is 同一类 Ck：
	return 单节点树T ，特征标记Ck
if A is None：
	Ck = D中最大一类
	return 单节点树T ， 特征Ck
计算 A 中的特征对D的信息熵，并计算信息增益。
选择最大的信息增益Ag
if Ag<ε：
	Ck = D中最大一类
	return 单节点树T ， 特征Ck
else
	#划分子集
	for i in 特征集Ag
	DA子集 = D[Ag特征 = i]
	return i ，DA子集
	由Ag i 构成树，
	新的训练集 = DA1，...DAi
	新的特征集 = A-Ag
	对新的特征集递归调用。	

C4.5算法

C4.5除了更换了比较对象，其余的没有任何变化。

决策树的减枝

设树的叶节点个数为|T|，t是T树的叶节点该叶节点有$N_{t}$Nt​个样本点，其中k类样本点有$N_{tk}$Ntk​,则损失函数的经验公式为
$C_a(T) = \sum_{t=1}^{|T|}N_t(-\sum_k \frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t})+α|T|$Ca​(T)=t=1∑∣T∣​Nt​(−k∑​Nt​Ntk​​logNt​Ntk​​)+α∣T∣
α能有效地控制叶节点的个数并且去掉那些对于划分结果有害的点。

CART算法

回归树的生成

对于特征空间，对于每个特征，将$(X_i,Y_i)$(Xi​,Yi​)独立，取一个特征$X^j$Xj划分，将空间划分为两个平面$R_1(j,s) = (x^j&lt;X_i)$R1​(j,s)=(xj<Xi​)和大于的平面，则最优划分点为使$C_1 =ave(Y_i,R_1)\quad C_2$C1​=ave(Yi​,R1​)C2​也是另一个平面的平均值，计算输出与之的关系使得
$min_{js}[min_{c1}\sum_{R1}(y_i-C_1)^2+min_{c1}\sum_{R1}(y_i-C_2)^2]$minjs​[minc1​R1∑​(yi​−C1​)2+minc1​R1∑​(yi​−C2​)2]
寻扎到最佳切分特征，划分之后，寻找第二个特征，递归到M个空间划分完为止。
总的来说就是对每个特征进行一次最优点寻找，找到最优特征，然后划分，再将剩下的子区域进行划分。

分类树的生成

1. 对每个特征的每个点找寻基尼指数，记为最优切分特征，和最优切分点。与上面的算法类似。
2. 将最优切分特征作为节点条件，将另一个作为切分点分成两个数据集。
3. 对数据集递归调用切分，最后得到满足条件的数据集。