【数据挖掘】1. 决策树、Hunt算法、泛化定理[通俗易懂]

• 决策树——Hunt’s algorithm（贪心）

  

  • 红色语句加上后减轻过拟合，下边的GINI系数解决 Hunt’s algorithm 第五行如何寻找最好的划分方法

• GINI Index

  1减训练集S中yes占比和no占比的平方和，取值范围0-0.5
  $$GINI(S)=1-(p_y^2+p_n^2)$$

• GINI split

  划分质量：GINI split 越小，划分越好
  $$GIN{I}_{split}=\frac{|S_1|}{|S|}GINI(S_1)+\frac{|S_2|}{|S|}GINI(S_2)$$

• Candidate split 候选划分

  • 对于有序（ordinal）的属性，其候选划分为 $A\le v$ 和 $A>v$ ，$v$ 是属性中的一个值（必须是），并且保证两个划分中都至少有一个符合条件的 object
  • 对于无序（Nominal）的属性，其候选划分为 $A\in S$ 和 $A\notin S$ , $S$ 是属性的子集，并且保证两个划分中都至少有一个符合条件的 object

• Gain 增益
  $$Gain=GINI(S)-GIN{I}_{split}$$

• 经验误差和泛化误差

  • 经验误差：训练集上被 $h(x)$预测错误的概率
    $$er{r}_{\mathcal{S}}(h)=\frac{|\{(x,y)\in \mathcal{S}|h(x)\ne y\}|}{|\mathcal{S}|}$$

  • 泛化误差：在一个相当相当大的训练集，或者无穷大，包含了所有可能出现的情况的集合，被 $h(x)$预测错误的概率
    $$er{r}_{\mathcal{D}}(h)=P{r}_{(x,y)\sim D}[h(x)\ne y]$$

  其中 $h$ 为一个 $\mathcal{X}\to \mathcal{Y}$ 上的函数，$\mathcal{D}$ 是 $\mathcal{X}\times \mathcal{Y}$ 上的概率分布

• 最终目标：最小化泛化误差

  但是我们不可能知道所有关于 $\mathcal{D}$ 的准确信息，所以我们只能用从 $\mathcal{D}$ 中拿出的训练集 $\mathcal{S}$ 寻找一个泛化误差比较小的分类器 $h$ ，当训练集的大小相当大时，分类器的可靠性才足够好

• Generalization Theorem 泛化理论

  $\mathcal{H}$ 是可能返回的分类器的集合，下边的声明具有至少 $1-\delta$ （$0<\delta \le 1$）的概率成立：

  对于任意 $h\in \mathcal{H}$ :
  $$er{r}_{\mathcal{D}}(h)\le er{r}_{\mathcal{S}}(h)+\sqrt{\frac{\ln (1/\delta )+\ln |\mathcal{H}|}{2|\mathcal{S}|}}$$
  我们应该：

  • 寻找在训练集上足够准确并且比较小的决策树
  • 尽可能增加 $\mathcal{S}$ 的大小

• 泛化理论的证明

  • 有 Hoeffding Bounds 定理如下（不需要证明）：

    对于 $X_1,\dots ,X_n$ 个独立的满足伯努利分布的随机变量： $Pr[X_i=1]=p$ ， $i\in [1,n]$ ；令 $s={\sum }_{i=1}^n{X}_i$ ，则任意 $0\le \alpha \le 1$：
    $$Pr[s/n>p+\alpha ]\le e^{-2n{\alpha }^2}$$

    $$Pr[s/n<p-\alpha ]\le e^{-2n{\alpha }^2}$$

  • 对于一个训练集分类器的经验误差表示为：
    $$er{r}_{\mathcal{S}}(h)=\frac{1}{n}\sum _{i=1}^n{X}_i$$

  • $Pr[X_i=1]=p$ 即为泛化误差 $er{r}_{\mathcal{D}}(h)$

  • 令 $\alpha =\sqrt{\frac{\ln (1/\delta )+\ln |\mathcal{H}|}{2|\mathcal{S}|}}$ ，可得：
    $$Pr\left[er{r}_{\mathcal{S}}(h)<er{r}_{\mathcal{D}}(h)-\sqrt{\frac{\ln (1/\delta )+\ln |\mathcal{H}|}{2|\mathcal{S}|}}\right]\le \frac{\delta }{|\mathcal{H}|}$$
    即为：
    $$Pr\left[er{r}_{\mathcal{D}}(h)>er{r}_{\mathcal{S}}(h)+\sqrt{\frac{\ln (1/\delta )+\ln |\mathcal{H}|}{2|\mathcal{S}|}}\right]\le \frac{\delta }{|\mathcal{H}|}$$
    每一个分类器失败的概率最多为 $\frac{\delta }{|\mathcal{H}|}$ ，那么至少一个分类器失败的概率为最多 $\delta$ ，所以没有分类器失败的概率为最少 $1-\delta$

• 所有可能的分类器数量

  • 每一个分类器需要用一个参数集合来表示，参数需要用一系列的二进制数表示，这就是数字如何在计算机中存储的。如果一个分类器有 $10^6$ 个参数，每一个参数都是用一个浮点数（64bits）表示的。那么一共需要 $64\times 10^6$ bits，所有可能的分类器数量，也就是 $|\mathcal{H}|\le 2^{64\times 10^6}$ ， $\ln |\mathcal{H}|\le 64\times 10^6$

今天的文章【数据挖掘】1. 决策树、Hunt算法、泛化定理[通俗易懂]分享到此就结束了，感谢您的阅读。