《机器学习》（二）决策树算法

向右看齐 2023-07-14 10:36 12阅读 0赞

## 一、ID3算法 ##

ID3算法的核心要义是**在决策树各个结点上应用信息增益准则选择最好的特征，递归地构建决策树**。具体方法是：从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该结点的不同取值建立子结点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。最后得到一个决策树。  
***需要记住的两个公式：***

### 熵： ###

![\\large Entropy(S)=-\\sum\_\{i=1\}^\{c\}p\_\{i\}log\_\{2\}(p\_\{i\})][large Entropy_S_-_sum_i_1_c_p_i_log_2_p_i]

### 信息增益： ###

![\\large Gain(S,A)=Entropy(S)-\\sum\_\{v\\in A\}\\frac\{S\_\{v\}\}\{S\}Entropy(S\_\{v\})][large Gain_S_A_Entropy_S_-_sum_v_in A_frac_S_v_S_Entropy_S_v]

(Sv:属性A取“v”值时的子集)

### 用一个例子来理解： ###

### ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXllZWdhbw_size_16_color_FFFFFF_t_70][] ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXllZWdhbw_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXllZWdhbw_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXllZWdhbw_size_16_color_FFFFFF_t_70 3][]

**ID3算法的缺点**：ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。ID3采用的信息增益度量存在一个内在偏置,它优先选择有较多属性值的Feature,因为属性值多的Feature会有相对较大的信息增益。ID3算法没有考虑缺失值的情况。ID3算法没有考虑“过拟合”overfitting的问题。

## 二、C4.5算法 ##

C4.5算法总体思路与ID3类似，都是通过构造决策树进行分类，其区别在于分支的处理，在分支属性的选取上，ID3算法使用**信息增益**作为度量，而C4.5算法引入了**信息增益率**作为度量。

避免ID3不足的一个度量就是不用信息增益来选择Feature,而是用信息增益比率(gainratio),增益比率通过引入一个被称作分裂信息(Splitinformation)的项来惩罚取值较多的Feature,分裂信息用来衡量Feature分裂数据的广度和均匀性。

***同样需要记住的两个公式：***

### 分裂信息 ###

![\\large SplitInformation(S,A)=-\\sum\_\{i=1\}^\{c\}\\frac\{\\left | S\_\{i\} \\right |\}\{\\left | S \\right |\}log\_\{2\}\\frac\{\\left | S\_\{i\} \\right |\}\{\\left | S \\right |\}][large SplitInformation_S_A_-_sum_i_1_c_frac_left _ S_i_ _right _left _ S _right _log_2_frac_left _ S_i_ _right _left _ S _right]

### 信息增益率 ###

![\\large GainRatio(S,A)=\\frac\{Gain(S,A)\}\{SplitInformation(S,A)\}][large GainRatio_S_A_frac_Gain_S_A_SplitInformation_S_A]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXllZWdhbw_size_16_color_FFFFFF_t_70 4][]

**C4.5算法的缺点**：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。

## 三、CART算法 ##

CART算法采用的是一种二分循环分割的方法，每次都把当前样本集划分为两个子样本集，使生成的决策树的结点均有两个分支。如果分支属性有多于两个取值，在分裂时会对属性值进行组合，选择最佳的两个组合分支。ID3 和 C4.5两种算法都是用来解决**分类问题**的，我们使用CART算法（分类回归树）来解决**回归问题。**

***需要记住两个个公式：***

### 基尼指数 ###

![\\large Gini(S)=\\sum\_\{i=1\}^\{c\}p\_\{i\}(1-p\_\{i\})][large Gini_S_sum_i_1_c_p_i_1-p_i]

### 条件基尼指数 ###

![\\large Gini(S,A)=\\sum\_\{i=1\}^\{c\}\\frac\{S\_\{i\}\}\{S\}Gini(S\_\{i\})][large Gini_S_A_sum_i_1_c_frac_S_i_S_Gini_S_i]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXllZWdhbw_size_16_color_FFFFFF_t_70 5][]

[large Entropy_S_-_sum_i_1_c_p_i_log_2_p_i]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20%5Clarge%20Entropy%28S%29%3D-%5Csum_%7Bi%3D1%7D%5E%7Bc%7Dp_%7Bi%7Dlog_%7B2%7D%28p_%7Bi%7D%29
[large Gain_S_A_Entropy_S_-_sum_v_in A_frac_S_v_S_Entropy_S_v]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20%5Clarge%20Gain%28S%2CA%29%3DEntropy%28S%29-%5Csum_%7Bv%5Cin%20A%7D%5Cfrac%7BS_%7Bv%7D%7D%7BS%7DEntropy%28S_%7Bv%7D%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXllZWdhbw_size_16_color_FFFFFF_t_70]: /images/20230529/04501de9576d48188ddee92843bee24c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXllZWdhbw_size_16_color_FFFFFF_t_70 1]: /images/20230529/08da1b36113b4bd0af37908d28cac8ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXllZWdhbw_size_16_color_FFFFFF_t_70 2]: /images/20230529/7841b96a70a94e8ab89d1f4c9ac36b95.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXllZWdhbw_size_16_color_FFFFFF_t_70 3]: /images/20230529/2583c8de6f2343b2af13e30a427fb850.png
[large SplitInformation_S_A_-_sum_i_1_c_frac_left _ S_i_ _right _left _ S _right _log_2_frac_left _ S_i_ _right _left _ S _right]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20%5Clarge%20SplitInformation%28S%2CA%29%3D-%5Csum_%7Bi%3D1%7D%5E%7Bc%7D%5Cfrac%7B%5Cleft%20%7C%20S_%7Bi%7D%20%5Cright%20%7C%7D%7B%5Cleft%20%7C%20S%20%5Cright%20%7C%7Dlog_%7B2%7D%5Cfrac%7B%5Cleft%20%7C%20S_%7Bi%7D%20%5Cright%20%7C%7D%7B%5Cleft%20%7C%20S%20%5Cright%20%7C%7D
[large GainRatio_S_A_frac_Gain_S_A_SplitInformation_S_A]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20%5Clarge%20GainRatio%28S%2CA%29%3D%5Cfrac%7BGain%28S%2CA%29%7D%7BSplitInformation%28S%2CA%29%7D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXllZWdhbw_size_16_color_FFFFFF_t_70 4]: /images/20230529/2e91f355f27c437085be2c680d23f6df.png
[large Gini_S_sum_i_1_c_p_i_1-p_i]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20%5Clarge%20Gini%28S%29%3D%5Csum_%7Bi%3D1%7D%5E%7Bc%7Dp_%7Bi%7D%281-p_%7Bi%7D%29
[large Gini_S_A_sum_i_1_c_frac_S_i_S_Gini_S_i]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20%5Clarge%20Gini%28S%2CA%29%3D%5Csum_%7Bi%3D1%7D%5E%7Bc%7D%5Cfrac%7BS_%7Bi%7D%7D%7BS%7DGini%28S_%7Bi%7D%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXllZWdhbw_size_16_color_FFFFFF_t_70 5]: /images/20230529/b413b1cb5d544583a516e9a8af0149a2.png