菜鸡的机器学习笔记

机器学习 python

---

决策树Decision Tree

决策树算法的目的

如何选择最优划分属性，即分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”(purity)越来越高

经典的属性划分方法包括：

• 信息增益
• 增益率
• 基尼指数

信息增益划分

• 信息熵Ent(D): information entropy
  定义为：

$$Ent(D) = - \sum_{k=1}^{|y|}p_k log_2 p_k$$

其中，如果p=0，则$plog_2p$=0

例如，要计算根节点的信息熵Ent(D)：
$Ent(D) = - (p_1 log_2p_1 + p_2 log_2p_2)$
其中，$p_1$表示结果为真占的比例，$p_2$表示结果为假占的比例

• 信息增益Gain(D,a):information gain
  定义为：

$$Gain(D,a) = Ent(D) - \sum_{v=1}^V \frac{|D^V|} {|D|} Ent (D^V)$$

该式子计算了某种属性a的信息增益Gain(D,a)，而$D^V$则是该属性a的其中一种状态

• 判断真假的决策树的建立
  

  $P_T$为真例的概率，$P_F为假例的概率$
  1.计算$Ent(D)$:
  $$Ent(D) = - (P_T log_2 P_T + P_F log_2 P_F)$$
  2.计算$Ent(D_i)$:
  $$Ent(D_i) = - (P_{i,T} log_2 {P_i,T} + P_{i,F} log_2 P_{i,F})$$
  3.计算$Gain(D,属性i)$:
  $$Gain(D,属性i) = Ent(D) - (Ent(D_i) × P_i + ... + ...)$$
  计算出各个属性的Gain值之后，选择Gain值最大的作为一级指标
  选择好一级指标后，再在此基础上计算新的Gain值，再依此选择新的指标

增益率建立决策树

增益率定义:

$$GainRatio(D,a) = \frac{Gain(D,a)}{IV(a)}$$
其中：
$$IV(a) = - \sum_{v = 1}^V \frac{|D^V|}{|D|} log_2 \frac{|D^V|}{|D|}$$
IV(a)称为属性a的固有值(intrinsic value)

CART决策树

划分标准：基尼指数(Gini index)
基尼值定义:

$$Gini(D) = \sum_{k = 1}^{|y|} \sum_{k' = k} p_k p_{k'} = 1 - \sum_{k=1}^{|y|}p_k^2$$
基尼指数定义：
$$GiniIndex(D,a) = \sum_{k = 1}^{|y|} \frac{|D^V|}{|D|} Gini(D^V)$$

预剪枝

判断标准：分别计算该节点划分前后的验证集精度，如果该节点划分前后的验证集精度差别较大,则预剪枝决策为划分

预剪枝的优缺点

优点：降低过拟合风险；显著减少训练时间和测试时间开销
缺点：欠拟合风险

后剪枝

判断标准：自下而上考察非叶子结点的分类性能，即将之替换为叶子节点能带来的泛化性能提升的程度。如果将该节点替换为叶子节点，能够带来验证集精度的提升，则后剪枝决策为剪枝

后剪枝的优缺点

优点：欠拟合风险小，泛化性能往往优于预剪枝决策树
缺点：训练时间开销大，因为后剪枝是在决策树完全建立之后进行的，需要自下向上对所有非叶子节点逐一考察

朴素贝叶斯分类器

计算步骤

1.估计类的先验概率P(c):

计算出P(True)和P(False)

2.为每个属性估计条件概率$P(X_i|c)$：

即

$$P(x_i|c) = P(x=x_i | c =True)$$
$$P(x_i|c) = P(x=x_i|c = False)$$
对于数值类的属性，条件概率的计算方法为：
$$P(x_i|c) = \frac{1}{\sqrt{2\pi} \sigma_{c,i}} e^{- \frac{(x_i - \mu_{c,i})^2}{2 \sigma^2_{c,i}}}$$
其中$\sigma_{c,i}$为标准差，$\mu_{c,i}$为均值

3.计算：为真的概率和为假的概率：

真概率 = $P(True) × P(X_i|c = True)...$
假概率 = $P(False) × P(X_i|c = False)...$

4.判断：

若：为真的概率>为假的概率，则判定结果为真

拉普拉斯修正

对于样本量较少的情况，需要采用拉普拉斯修正，来避免样本数量较少影响训练结果：

$$\hat{P}(c) = \frac{|D_c| + 1}{|D| + N}$$
N表示真、假的情况个数(如果只有真假，则N=2)
$$\hat{P}(x_i|c) = \frac{|D_{c,x_i}| + 1}{|D_c| + N_i}$$
N_i表示该属性取值的个数