决策树：判别模型问题描述：假设要对一批样本分K类。其中这些样本又有A个特征。如何生成一个树形结构，按照特征一层一层往下分。
决策树生成思路：有A个特征可供分类，但是先选哪个特征作为分类标准呢？决策树为了解决这个问题，首先会判断该特征的对样本的区分能力，比如在男宿舍这样一个条件下判断谁有ipad，如果用性别作为一个特征来判断分类，收益很小；如果我们用生活费多少来判断，那么对这个分类就有很大的帮助。决策树这里用信息增益来判断特征Ai对分类的影响大小，先选择对分类区分度大的特征，在用其他特征依次往下分。信息增益：
熵：混乱程度的度量 一个随机变量的熵可以由其各种取值的概率定义为：
H
(
X
)
=
−
∑
i
=
1
n
p
i
log
p
i
H(X)=-\sum_{i=1}^{n} p_{i} \log p_{i}
H(X)=−∑i=1npilogpi信息增益：定义特征 A 对训练数据集 D 的信息增益 g (D,A)，定义为 集合 D 的经验熵 H(D) 与特征 A 给定条件下 D 的经验条件嫡
H
(
D
∣
A
)
H(D \mid A)
H(D∣A) 之差，即
g
(
D
,
A
)
=
H
(
D
)
−
H
(
D
∣
A
)
g(D, A)=H(D)-H(D \mid A)
g(D,A)=H(D)−H(D∣A) 根据特征
A
A
A 的取值将 D 划分为
n
n
n 个子集
D
1
,
D
2
,
⋯
,
D
n
D_{1}, D_{2}, \cdots, D_{n}
D1,D2,⋯,Dn，
H
(
D
∣
A
)
=
∑
i
=
1
n
∣
D
i
∣
∣
D
∣
H
(
D
i
)
H(D \mid A)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} H\left(D_{i}\right)
H(D∣A)=i=1∑n∣D∣∣Di∣H(Di)信息增益比：
g
R
(
D
,
A
)
=
g
(
D
,
A
)
H
A
(
D
)
g_{R}(D, A)=\frac{g(D, A)}{H_{A}(D)}
gR(D,A)=HA(D)g(D,A)，分母表示以特征A代替类别在数据集上计算熵。 决策树生成算法：
ID3算法：以信息增益为特征判断标准C4.5：以信息增益比为特征判断标准 决策树剪枝算法：
剪枝原因：分类分的太细，对训练数据拟合很好，但是对未知数据的分类效果不好，也就是过拟合。考虑了树的复杂度因素。先剪枝（也就是在生成过程中剪枝）：
设定决策树高度，到高度了停止继续分设定叶节点包含的最小样本数计算每增一个节点对系统带来的性能，设定阈值予以停止 后剪枝（先生成完整的树再剪枝）：
计算剪枝前后的损失函数，比较观察是否剪枝。还有多种剪枝算法。 随机森林：训练集产生多个决策树，输入预测数据后，每个决策树上都产生一个分类。对分类问题多数表决，对回归问题，求平均值。
如何产生多个决策树，也就是随机的含义：
训练时，也就是生成决策树时，使用数据的N%（每次都是N%，但是具体数据不一样，可重复取样单个样本。生成决策树时，可以多次选择不同的特征组作为生成树的条件。
