# 决策树

决策树可以看作是一个分段函数，是对特征空间的划分，每个划分区域对应一个分类预测结果

**概念**

* 定义：数据均D，|D|数据集大小，有K个类$$C\_1,C\_2,...,C\_K$$，$$|D|=\sum\_{k=1}^{K}|C\_k|$$，

  特征（属性）`A有n个`不同取值$${a\_1,a\_2,...,a\_n}$$，可划分为n个集合$$D\_1,D\_2,...,D\_n$$，子集$$D\_i$$中第$$C\_k$$类样本集合为$$D\_{ik}$$
* 熵：$$P(X=x\_i)=p\_i,i=1,2,..,n$$，则X的熵为：$$H(X)=-\sum\_{i=1}^{n}p\_ilogp\_i$$
* 经验熵：$$H(D)=-\sum\_{k=1}^{K}\frac{|C\_k|}{|D|}log\_2\frac{|C\_k|}{|D|}$$
* A对D的经验条件熵：$$H(D|A)=\sum\_{i=1}^{n}\frac{|D\_i|}{|D|}H(D\_i)=-\sum\_{i=1}^{n}\frac{|D\_i|}{|D|}\sum\_{k=1}^{K}\frac{|D\_{ik}|}{|D\_i|}log\_2\frac{|D\_{ik}|}{|D\_i|}$$
* 信息增益：得知特征X的信息而使得类Y信息的不确定性减少的程度 $$g(D,A)=H(D)-H(D|A)$$
* 信息增益比：校正选取值时`偏向取值较多的那些特征`的问题，

  $$g\_R(D,A)=\frac{g(D,A)}{H\_A(D)}$$

  $$H\_A(D)=-\sum\_{i=1}^{n}\frac{|D\_i|}{|D|}log\_2\frac{|D\_i|}{|D|}$$

## ID3

* 输入：D、A、和阀值$$\epsilon$$
* 输出：决策树
* 1）D中所有样本为同一类$$C\_k$$，则T为单节点树，类为$$C\_k$$，返回T
* 2）若A空，则返回D中最多的那个类作为T的节点类返回
* 3）计算信息增益，选择信息增益最大的特征$$A\_g$$作为划分
* 4）若$$A\_g$$小于阀值$$\epsilon$$，则T为单节点树，D中类最多的作为标记返回T
* 5）否则正式对$$A\_g$$中每个取值$$a\_i$$，将D分为$$A\_g$$不同取值数那么多个子集$$D\_i$$，子集中最多的类作为当前节点的类标记，则此处分裂多个子节点
* 6）对第i个子节点，以$$D\_i$$为新的数据集，以$$A-{A\_g}$$为特征集，构建决策树

## C4.5

对ID3算法中对`信息增益`替换为`信息增益比`，抑制取值较多特征的偏向问题

## 剪枝

* 设置最大深度、设置阀值
* 自底向上不断剪断一个结点，构成新树，计算损失，损失降低就保留本次剪枝

## CART（classification and regression tree）

是二叉树，每次划分把空间分为两个（左、右两个子节点）

* 回归树：`用平方误差`确定分裂点
* 分类树：`基尼指数`确定分裂点，$$Gini(p)=\sum\_{k=1}^{K}p\_k(1-p\_k)=1-\sum\_{k=1}^{K}p\_k^2$$，表示不确定性

### 回归树

* 输入X，Y，Y是连续变量：$$D={(x\_1,y\_1),(x\_2,y\_2),...,(x\_N,y\_N)}$$
* 决策树是在输入空间上划分M个单元$$R\_1,R\_2,...,R\_M$$，每个对应一个输出$$c\_1,c\_2,...,c\_m$$，
* 回归中输出值$$c\_i=avg(y\_i|x\_i \in R\_i)$$，也就是那个节点下样本的均值作为这个节点的输出
* 回归模型表示为：$$f(x)=\sum\_{m=1}^{M}c\_mI(x \in R\_m)$$
* 训练误差表示为：$$\sum\_{x\_i \in R\_m}(y\_i-f(x\_i))^2$$
* 划分点：第j个变量的第s个值作为划分，把空间划分为两个区域：

$$R\_1(j,s)={x|x^{(j)} \le s},R\_2(j,s)={x|x^{(j)}>s }$$

* 两个区域（暂时）的输出标记：

$$c\_1=avg(y\_i|x\_i \in R\_1(j,s)),c\_2=avg(y\_i|x\_i \in R\_2(j,s))$$

然后计算以此作为本次（尝试）划分的训练误差

* 遍历的划分选择$$(j,s)$$，最终选择误差最小的那个为最终真正的划分点，公式化就是，找到最优j、s：

$$min\_{j,s}\[min\_{c\_1}\sum\_{x\_i \in R\_1(j,s)}(y\_i-c\_1)^2+min\_{c\_2}\sum\_{x\_i \in R\_2(j,s)}(y\_i-c\_2)^2]$$

* 然后一直这样下去，进行划分，直到满足一些策略条件：结点样本数量少于某个参数、深度太大了、误差下降小于阀值

### 分类树

* 分裂结点时用基尼指数，给定样本集合D，基尼指数为：

$$Gini(D)=1-\sum\_{k=1}^{k}(\frac{|C\_k|}{|D|})^2$$

表示D的不确定性

* 对于特征A，取值n个$$a\_1,a\_2,...,a\_n$$，每个可以分为取$$a\_i$$和不取$$a\_i$$两个空间，作为左右子结点：

$$D\_1={ (x,y) \in D|A=a\_i },D\_2={ (x,y) \in D|A \neq a\_i }$$

* 特征A下的基尼指数为：

$$Gini(D,A)= \frac{|D\_1|}{|D|}Gini(D\_1)+\frac{|D\_2|}{|D|}Gini(D\_2)$$

* 所以问题变为n个取值中取那个作为本次的划分，显然**选择不确定性（Gini指数）最小的作为划分**
* 有了划分策略后，其它和之前的一样

### CART剪枝

* 对于树内任意某个要（尝试）剪枝的点t（$$\alpha$$为调节经验、模型复杂度权衡）：
  * 剪了的损失：$$C\_\alpha(t)=C(t)+\alpha$$
  * 不剪还是树的损失：$$C\_\alpha(T\_t)=C(T\_t)+\alpha|T\_t|$$
  * 可见$$\alpha$$偏大时最优子树规模会偏小
* 令两式相等，得$$\alpha$$关系：

  $$\alpha=\frac{C(t)-C(T\_t)}{|T\_t|-1}=g(t)$$

  **可见**：$$\alpha \to 0+$$时，$$C(t)>C(T\_t) \to C\_\alpha(T\_t)\<C\_\alpha(t)$$，（$$|T\_t|$$怎么也会大于1，所以分子肯定>0）

  ​ $$\alpha$$慢慢增大，存在刚好相等$$C\_\alpha(T\_t)=C\_\alpha(t)$$

  ​ $$\alpha$$再继续增大，则超过$$C\_\alpha(T\_t)>C\_\alpha(t)$$

  **因此**：只要两式相等时得到的这个关系$$g(t)$$时存在，`那么剪枝就比不剪枝更可取，因为剪枝的结点更少`，却满足同样的损失计算。
* 那么这个$$g(t)$$可以表示剪枝后损失函数减少的程度
* 最终过程
  * 首先可以令$$\alpha$$非常大
  * 然后自底向上对于所有父结点t，计算剪枝和不剪枝的损失关系$$g(t)$$，（剪枝损失下降程度）
  * 更新阀值让损失下降阀值越来越小：$$\alpha=min(\alpha,g(t))$$，此时$$\alpha$$是全局最新值
  * 损失最小的那一批父结点（也就是$$g(t)= \alpha$$）剪掉，剪枝损失下降度和上面那个值相等的结点都剪掉
  * 然后本轮剪掉得到的树保留，下一轮基于这棵树，继续剪枝，得到新的树，新的也保留.....，直到剪到根部
  * 这样就得到了不同的树集合$$\[T\_0,T\_1,...,T\_n]$$，对应基于不同下降度阀值$$\alpha$$（此值不断减少，一开始是无穷的）剪枝得到的树
  * 然后在这堆树中，交叉验证、计算测试误差，等待（麻烦），选出最佳树
* 总结来说就是，按照不同阀值剪树，得到不同阀值的树，然后交叉验证等选择最好的（毕竟你也不知道这样剪枝就是好的，就是还得靠验证）


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://im-qianuxn.gitbook.io/pytorch/ji-suan-ji/ml/5-jue-ce-shu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.