review
- linear regression
模型：\(\hat{y} = h_{\theta} (\textbf{x}) = \theta^{T} \cdot \textbf{x}\)
策略：\(J(\theta) = \textbf{MSE} = \frac{1}{m} \sum_{i=1}^{m} (\theta^{T}\cdot\textbf{x}^i - y^i)^2\)
算法：normal equation、 Gradiend desent
desicion tree
- model
决策树模型
desicion tree
- entropy
熵
- 香农信息论里最基本的概念
度量的是随机变量的不确定性
假设X是一个离散型随机变量，有n个不同的取值，概率分布情况是：
$$P(X = x_i) = p_i, i =1,2,...,n$$
那么，X的熵为
$$H(X) = -\sum_{i=1}^{n}p_ilogp_i$$
当随机变量只有两个离散值时（比如0和1）\(P(X=1) = p, P(X=0) = 1-p\)
$$H(p) = -p log_2p - (1-p)log_2(1-p)$$
举例： 地球明天会不会毁灭、抛一枚硬币出现的正面还是反面
desicion tree
- loss
怎么利用熵来度量决策树的拟合训练数据集的好坏？
\(Ht(T) = -\sum_{k=1}^{K}\frac{|C_k|}{|D|}log\frac{|C_k|}{|D|}\)
\(Cost(T) = \sum_{t=1}^{|T|}N_tHt(T)\)
desicion tree
algorithm
- pruning
剪枝
预剪枝：在生成决策树过程中就采取策略防止模型过复杂，比如限制树的最大深度、设置子数据集的熵阈值
后剪枝：在生成完决策树后对树进行修剪。
$$C_α(T) = Cost(T)+α|T|$$
算法思想
- 计算树每个叶子结点的经验熵。
- 递归地从叶节点向上回缩：设一叶结点回缩到父结点之前和之后，树分别是TB和TA，其对应的损失函数值分别是Cα(TB)与Cα(TA)，如果Cα(TA)≤Cα(TB)，则剪枝，即将父节点变成新的叶结点。
desicion tree
algorithm
- CART
CART（分类与回归树）
更为通用和广泛，可以用于分类也可以用于回归，分类树和回归树
二叉树，分支都是是和否（类似于把特征做onehot编码）
算法思想：选择特征和划分，递归生成决策树，剪枝
desicion tree
algorithm
- CART
回归树
回归树适用于那些输入和输出都是连续变量的回归问题
生成一颗树模型，将输入空间划分成M个子单元\(R_1,R_2,..., R_m\)，每个子单元上有个固定的输出值\(c_m\) 因此，回归树的模型可以用数学语言表示成：
$$ f(x) = \sum_{m=1}^{M}c_mI(x \in R_m) $$
