统计学习方法决策树

偏执的太偏执、 2022-04-08 14:11 385阅读 0赞

决策树（decision tree） 是一种**基本的分类与回归方法**。决策树模型呈树形结构， 在分类问题中， 表示基于**特征对实例**进行**分类**的过程。 它可以**认为是if-then规则**的集合， 也可以认为是**定义在特征空间与类空间上的条件概率分布**。 其主要优点是模型具有**可读性， 分类速度快**。 学习时， 利用训练数据， 根据**损失函数最小化的原则**建立决策树模型。 预测时， 对新的数据， 利用决策树模型进行分类。 决策树学习通常包括3个步骤： **特征选择、 决策树的生成和决策树的修剪**。 这些决策树学习的思想主要来源于由Quinlan在1986年提出的ID3算法和1993年提出的C4.5算法， 以及由Breiman等人在1984年提出的CART算法。

### 1. 决策树模型与学习 ###

**分类决策树模型是一种描述对实例进行分类的树形结构**。 决策树由**结点（node） 和有向边（directed edge） 组成**。 结点有两种类型： **内部结点（internalnode） 和叶结点（leaf node）** 。 **内部结点表示一个特征或属性**， **叶结点表示一个类**。用决策树分类， 从根结点开始， 对实例的某一特征进行测试， 根据测试结果， 将实例分配到其子结点； 这时， 每一个子结点对应着该特征的一个取值。 如此**递归地对实例进行测试并分配， 直至达到叶结点**。 最后将实例分到叶结点的类中。图5.1是一个决策树的示意图。 图中圆和方框分别表示内部结点和叶结点。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70][]

**决策树和归纳算法**  
决策树技术发现数据模式和规则的核心是归纳算法。归纳是**从特殊到一般的过程**。  
归纳推理从**若干个事实中表征出的特征、 特性和属性中，通过比较、 总结、 概括而得出一个规律性的结论**。  
归纳推理试图从对象的一部分或整体的特定的观察中**获得一个完备且正确的描述**。 即从特殊事实到普遍性规律的结论。  
归纳对于认识的发展和完善具有重要的意义。 人类知识的增长主要来源于归纳学习。  
归纳学习由于**依赖于检验数据， 因此又称为检验学习**。  
归纳学习存在一个基本的假设：  
       任一假设如果**能够在足够大的训练样本集中很好的逼近目标函数， 则它也能在未见样本中很好地逼近目标函数**。该假定是归纳学习的有效性的前提条件。  
归纳过程就是在描述空间中进行搜索的过程。  
归纳可分为自顶向下， **自底向上和双向搜索**三种方式：  
       自底向上法一次处理一个输入对象。 将描述逐步一般化。直到最终的一般化描述。  
       自顶向下法对可能的一般性描述集进行搜索， 试图找到一些满足一定要求的最优的描述。  
**决策树算法**  
与决策树相关的重要算法包括：  
**CLS, ID3， C4.5， CART**  
**算法的发展过程**  
Hunt,Marin和Stone 于1966年研制的CLS学习系统， 用于学习单个概念。  
1979年, J.R. Quinlan 给出ID3算法， 并在1983年和1986年对ID3 进行了总结和简化， 使其成为决策树学习算法的典型。  
Schlimmer 和Fisher 于1986年对ID3进行改造， 在每个可能的决策树节点创建缓冲区， 使决策树可以递增式生成， 得到ID4算法。  
1988年， Utgoff 在ID4基础上提出了ID5学习算法， 进一步提高了效率。  
1993年， Quinlan 进一步发展了ID3算法， 改进成C4.5算法。  
另一类决策树算法为CART， 与C4.5不同的是， CART的决策树由二元逻辑问题生成， 每个树节点只有两个分枝， 分别包括学习实例的正例与反例。  
如图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 1][]

根据这些信息，可以构建如右图所示决策树。

决策树的基本组成部分： **决策结点、 分支和叶子**。决策树中**最上面的结点称为根结点**。是整个决策树的开始。 **每个分支是一个新的决策结点， 或者是树的叶子**。**每个决策结点代表一个问题或者决策**，**通常对应待分类对象的属性**。**每个叶结点代表一种可能的分类结果**。在沿着决策树从上到下的遍历过程中， 在每个结点都有一个测试。 对每个结点上问题的不同测试输出导致不同的分枝， 最后会达到一个叶子结点。 这一过程就是利用决策树进行分类的过程，利用若干个变量来判断属性的类别。  
**决策树与条件概率分布**  
决策树表示给定特征条件下类的**条件概率分布**。  
条件概率分布定义在特征空间的一个划分(partition)上。将特征空间划分为互不相交的单元(cell)或区域(region),并在每个单元定义一个类的概率分布就构成了一个条件概率分布。  
决策树的**一条路径对应于划分中的一个单元**。  
决策树所表示的**条件概率分布由各个单元给定条件下类的条件概率分布组成。**  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 2][]

**决策树学习本质上是从训练数据集中归纳出一组分类规则， 与训练数据集不相矛盾的决策树**。  
能对训练数据进行正确分类的决策树可能有多个， 也可能 一个也没有.我们需要的是一个与训练数据矛盾较小的决策树， 同时具有很好的泛化能力。  
决策树学习是由**训练数据集估计条件概率模型**.基于特征空间划分的类的条件概率模型有无穷多个。  
我们选择的条件概率模型**应该不仅对训练数据有很好的拟合， 而且对未知数据有很好的预测**。

###    2. 特征选择 ###

**决策树的CLS算法**

CLS（Concept Learning System） 算法  
CLS算法是早期的决策树学习算法。 它是许多决策树学习算法的基础  
CLS基本思想  
从一棵空决策树开始， 选择某一属性（分类属性） 作为测试属性。 该测试属性对应决策树中的决策结点。 根据该属性的值的不同， 可将训练样本分成相应的子集：  
       如果该子集为空， 或该子集中的样本属于同一个类， 则该子集为叶结点，  
       否则该子集对应于决策树的内部结点， 即测试结点， 需要选择一个新的分类属性对该子集进行划分， 直到所有的子集都为空或者属于同一类。

**算法步骤：**

生成一颗空决策树和一张训练样本属性集;  
若训练样本集T 中所有的样本都属于同一类,则生成结点T , 并终止学习算法;否则  
根据某种策略从训练样本属性表中选择属性A 作为测试属性, 生成测试结点A  
若A的取值为v1,v2,…,vm, 则根据A 的取值的不同,将T 划分成 m个子集T1,T2,…,Tm;  
从训练样本属性表中删除属性A;  
转步骤2, 对每个子集递归调用CLS;  
  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 4][]

CLS的算法相对简单，其实就是构建一棵树，每行数据就是一条路径。

CLS算法问题：  
根据某种策略从训练样本属性表中选择属性A作为测试属性。 **没有规定采用何种测试属性**。 实践表明，**测试属性集的组成以及测试属性的先后对决策树的学习具有举足轻重的影响**。

**信息增益**  
Shannon在1948年提出的信息论理论：  
熵(entropy)： 信息量大小的度量， 即表示随机变量不确定性的度量。  
熵的通俗解释： 事件![20181218155142732.png][]的信息量![2018121815512515.png][]可如下度量：

![20181218155100690.png][]  
其中![20181218155157869.png][]表示事件![20181218155142732.png][]发生的概率。  
假设有n个互不相容的事件a1,a2,a3,….,an,它们中有且仅有一个发生， 则其平均的信息量(熵)可如下度量：

![20181218155235524.png][]  
**熵的理论解释**  
设X是一个取有限个值的离散随机变量， 其概率分布为：

![20181218155344701.png][]  
则随机变量X的熵定义为：![20181218155359112.png][]  
对数以2为底或以e为底(自然对数)， 这时熵的单位分别称作比特(bit)或纳特(nat),熵只依赖于X的分布， 与X的取值无关：  
![201812181554209.png][]  
熵越大， 随机变量的不确定性越大：![2018121815554388.png][]  
当X为1,0分布时：![20181218155557123.png][]  
熵：![20181218155649136.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 5][]

设有随机变量(X,Y),其联合概率分布为：![20181218160417827.png][]  
条件熵H(Y|X)： 表示在己知随机变量X的条件下随机变量Y的不确定性， 定义为X给定条件下Y的条件概率分布的熵  
对X的数学期望：![20181218160440755.png][]  
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时， 所对应的熵与条件熵分别称为经验熵（empirical  
entropy)和经验条件熵（empirical conditional entropy )  
**信息增益定义**:特征A对训练数据集D的信息增益，g(D,A), 定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差， 即![20181218160609518.png][]  
(Information gain)表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。  
—般地， 熵H(Y)与条件熵H(Y|X)之差称为互信息（mutual information)。  
决策树学习中的信息增益等价于训练数据集中类与特征的互信息  
**信息增益的算法**  
设训练数据集为D  
|D|表示其样本容量， 即样本个数  
设有K个类Ck, k = 1,2， …K，  
|Ck |为属于类Ck的样本个数  
特征A有n个不同的 取值\{a1,a2…an\}根据特征A的取值将D划分为n个子集D1.。 。 Dn  
|Di|为 Di的样本个数  
记子集Di中属于类Ck的样本集合为Dik  
|Dik|为Dik的样本个数  
输入： 训练数据集D和特征A；  
输出： 特征A对训练数据集D的信息增益g(D,A)  
1、 计算数据集D的经验熵H(D)![20181218160820357.png][]  
2、 计算特征A对数据集D的经验条件熵H(D|A)![20181218160833816.png][]  
3、 计算信息增益![20181218160851453.png][]

###    3. 决策树的生成 ###

**ID3算法**

ID3算法是一种经典的决策树学习算法， 由Quinlan于1979年提出。  
ID3算法主要针对属性选择问题。 是决策树学习方法中最具影响和最为典型的算法。  
该方法使用信息增益度选择测试属性。  
当获取信息时， 将不确定的内容转为确定的内容， 因此信息伴着不确定性。  
从直觉上讲， 小概率事件比大概率事件包含的信息量大。 如果某件事情是“百年一见” 则肯定比“习以为常” 的事件包含的信息量大。  
 如何度量信息量的大小？  
答： 信息增益  
在决策树分类中， 假设S是训练样本集合， |S|是训练样  
本数， 样本划分为n个不同的类C1,C2,….Cn， 这些类的  
大小分别标记为|C1|， |C2|， …..,|Cn|。 则任意样本S属  
于类Ci的概率为：  
![20181218161205418.png][]

∑是属性A的所有可能的值v, Sv是属性A有v值的S子集  
|Sv|是Sv 中元素的个数； |S|是S中元素的个数。  
下面举例计算信息增益：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 6][]

第1步：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 7][]

第二步：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 8][]

第三步：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 9][]

第四步：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 10][]

第五步：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 11][]

直接上代码：

import math
    data_list = [
    [64, '青', '高', '否', '良', '不买'],
    [64, '青', '高', '否', '优', '不买'],
    [128, '中', '高', '否', '良', '买'],
    [60, '老', '中', '否', '良', '买'],
    [64, '老', '低', '是', '良', '买'],
    [64, '老', '低', '是', '优', '不买'],
    [64, '中', '低', '是', '优', '买'],
    [128, '青', '中', '否', '良', '不买'],
    [64, '青', '低', '是', '良', '买'],
    [132, '老', '中', '是', '良', '买'],
    [64, '青', '中', '是', '优', '买'],
    [32, '中', '中', '否', '优', '买'],
    [32, '中', '高', '是', '良', '买'],
    [63, '老', '中', '否', '优', '不买'],
    [1, '老', '中', '否', '优', '买']
    ]
    
    # 选取某列的相同特征的数据
    def get_same_column_value(column_index,value,data_list):
    	new_data_list = []
    	for i in data_list:
    		if i[column_index] == value :
    			new_data_list.append(i)
    	return new_data_list
    # 计算总计数
    def get_total_count(data_list):
    	count = 0
    	for i in data_list:
    		count += i[0]
    	return count
    
    # 计算熵公式
    def get_entropy(p1,p2):
        if p1 == 1 and p2 == 0 or p1 == 0 and p2 == 1:
    		return 0.0
    	return -(p1*math.log(p1, 2)+p2*math.log(p2, 2))
    
    # 第1步计算决策属性的熵
    c5_1,c5_2 = get_total_count(get_same_column_value(5, '买',data_list)),get_total_count(get_same_column_value(5, '不买',data_list))
    p5_1,p5_2 = c5_1/(c5_1 + c5_2), c5_2/(c5_1 + c5_2)
    Hd_5 = get_entropy(p5_1,p5_2)
    print(Hd_5)
    # 第2步计算条件属性的熵，以年龄为例
    # 计算年龄中青年的熵
    c0_1_1,c0_1_2 = get_total_count(get_same_column_value(1, '青',get_same_column_value(5, '买',data_list))
    ),get_total_count(get_same_column_value(1, '青',get_same_column_value(5, '不买',data_list)))
    p0_1_1,p0_1_2 = c0_1_1/(c0_1_1 + c0_1_2), c0_1_2/(c0_1_1 + c0_1_2)
    Hd_0_1 = get_entropy(p0_1_1,p0_1_2)
    print(Hd_0_1)
    # 计算年龄中中年的熵
    c0_2_1,c0_2_2 = get_total_count(get_same_column_value(1, '中',get_same_column_value(5, '买',data_list))
    ),get_total_count(get_same_column_value(1, '中',get_same_column_value(5, '不买',data_list)))
    p0_2_1,p0_2_2 = c0_2_1/(c0_2_1 + c0_2_2), c0_1_2/(c0_2_1 + c0_2_2)
    Hd_0_2 = get_entropy(p0_2_1,p0_2_2)
    print(Hd_0_2)
    # 计算年龄中老年的熵
    c0_3_1,c0_3_2 = get_total_count(get_same_column_value(1, '老',get_same_column_value(5, '买',data_list))
    ),get_total_count(get_same_column_value(1, '老',get_same_column_value(5, '不买',data_list)))
    p0_3_1,p0_3_2 = c0_3_1/(c0_3_1 + c0_3_2), c0_3_2/(c0_3_1 + c0_3_2)
    Hd_0_3 = get_entropy(p0_3_1,p0_3_2)
    print(Hd_0_3)
    # 计算年龄的平均信息期望
    E = get_total_count(get_same_column_value(1, '青',data_list))/get_total_count(data_list)*Hd_0_1 + \
    	get_total_count(get_same_column_value(1, '中',data_list))/get_total_count(data_list)*Hd_0_2 + \
    	get_total_count(get_same_column_value(1, '老',data_list))/get_total_count(data_list)*Hd_0_3
    print(E)
    # 年龄信息增益
    G = Hd_5 - E
    print(G)

运行：

![20181218204817834.png][]

下面循环计算所有属性的信息增益：

结果：

![20181218211532548.png][]从左到右分别是年龄、收入、学生、信誉的信息增益，和手动计算的一致：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 12][]

得到信息增益后，对其进行排序，信息增益最大的属性将作息树的根结点。此时初步构建如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 13][]

可以看到中年都买，于是无需判断，作为叶子结点。到青年这个结点，我们又要重新计算买与不买的熵，同时从feature\_set移除属性年龄，即移除青中老年，然后再按上边的流程重新计算信息增益并排序，直到结点是叶子结点。下面来算下青年中买与不买的熵：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 14][]

如果选择收入作为节点：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 15][]

![20181219115216509.png][]

可以看到，此时计算信息增益时，用的是青年中买与不买的熵，也就是说，只要作为结点不是叶节点，在构建时就要重新计算熵，并以此熵作为新的熵作信息增益的计算。下面通过代码求出年龄结点下老，中，青的三个结点的信息增益，代码在之前的代码作了一些调整：

import math
    data_list = [
    [64, '青', '高', '否', '良', '不买'],
    [64, '青', '高', '否', '优', '不买'],
    [128, '中', '高', '否', '良', '买'],
    [60, '老', '中', '否', '良', '买'],
    [64, '老', '低', '是', '良', '买'],
    [64, '老', '低', '是', '优', '不买'],
    [64, '中', '低', '是', '优', '买'],
    [128, '青', '中', '否', '良', '不买'],
    [64, '青', '低', '是', '良', '买'],
    [132, '老', '中', '是', '良', '买'],
    [64, '青', '中', '是', '优', '买'],
    [32, '中', '中', '否', '优', '买'],
    [32, '中', '高', '是', '良', '买'],
    [63, '老', '中', '否', '优', '不买'],
    [1, '老', '中', '否', '优', '买']
    ]
    data_labels = ['计数','年龄','收入','学生','信誉','归类']
    # 选取某列的相同特征的数据
    def get_same_column_value(column_index,value,data_list):
    	new_data_list = []
    	for i in data_list:
    		if i[column_index] == value :
    			new_data_list.append(i)
    	return new_data_list
    # 计算总计数
    def get_total_count(data_list):
    	count = 0
    	for i in data_list:
    		count += i[0]
    	return count
    
    # 计算熵公式
    def get_entropy(p1,p2):
    	if p1 == 1 and p2 == 0 or p1 == 0 and p2 == 1 or p1 == 0 and p2 ==0:
    		return 0.0
    	return -(p1*math.log(p1, 2)+p2*math.log(p2, 2))
    
    # 计算每个属性的特征集合
    def get_features_set(data_list):
    	attr_set_dict = {}
    	for i in range(1,5):
    		attr_set = []
    		for j in data_list:
    			attr_set.append(j[i])
    		attr_set_dict[i] = list(set(attr_set))
    	return attr_set_dict
    
    # 计算p1,p2
    def get_p1_p2(calculate_data_list1,calculate_data_list2):
    	c1,c2 = get_total_count(calculate_data_list1),get_total_count(calculate_data_list2)
    	if c1 == c2 and c1 == 0:
    		return 0.0, 0.0
    	p1,p2 = c1/(c1 + c2), c2/(c1 + c2)
    	return p1,p2	
    # 计算每个属性的信息增益
    def get_attrs_G(features_set,data_list_):
    	'''
    	features_set:字典列表，所有属性的每个特征
    	data_list:待计算的数据列表
    	return: 排序好的元组列表
    	'''
    	# 计算结点的熵
    	p1p2 = get_p1_p2(get_same_column_value(5, '买',data_list_),get_same_column_value(5, '不买',data_list_))
    	Hd = get_entropy(p1p2[0],p1p2[1])
    	G_dict= {}
    	# 遍历每个属性计算信息增益
    	for i in features_set.keys():
    		E = 0
    		for j in features_set[i]:
    			p1p2_ = get_p1_p2(get_same_column_value(i , j, get_same_column_value(5, '买',data_list_)),get_same_column_value(i , j, get_same_column_value(5, '不买',data_list_)))
    			Hd_ = get_entropy(p1p2_[0],p1p2_[1])
    			E1 = get_total_count(get_same_column_value(i , j, data_list_))/get_total_count(data_list_)*Hd_
    			E += E1
    		G_dict[data_labels[i]] = Hd - E		
    	return sorted(G_dict.items(), key=lambda d: d[1])
    # 得到每个属性下的特征列表
    features_set = get_features_set(data_list)
    # 得到作为根结点的属性元组
    remove_feature_g = get_attrs_G(features_set,data_list)[-1]
    # 得到作为根结点的属性名称
    remove_attr = remove_feature_g[0]
    # 得到作为根结点的属性索引
    remove_attr_index = data_labels.index(remove_attr)
    # 得到作为根结点的属性特征列表
    remove_attr_features = features_set[remove_attr_index]
    # 得到每个属性下的特征列表下删除根结点属性特征列表
    del features_set[remove_attr_index]
    for i in remove_attr_features:
    	print(i +' 的信息增益：' + str(get_attrs_G(features_set,get_same_column_value(remove_attr_index,i,data_list))))

结果：

![20181219120342196.png][]

可以看到，青年在收入属性下的信息增益为0.4591，和手动算的一样，中年结点就是叶子结点，而老年结点应该选择信誉作为下一个属性结点，青年将选择学生作为下一个属性结点。在下个结点寻找信息增益继续做循环即可。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 16][]  
**ID3算法-流程**

**1 决定分类属性；  
2 对目前的数据表， 建立一个节点N  
3 如果数据库中的数据都属于同一个类， N就是树叶， 在树叶上标出所属的类  
4 如果数据表中没有其他属性可以考虑， 则N也是树叶， 按照少数服从多数的原则在树叶上标出所属类别  
5 否则， 根据平均信息期望值E或GAIN值选出一个最佳属性作为节点N的测试属性  
6 节点属性选定后， 对于该属性中的每个值：  
从N生成一个分支， 并将数据表中与该分支有关的数据收集形成分支节点的数据表， 在表中删除节点属性那一栏如果分支数  
据表非空， 则运用以上算法从该节点建立子树。**  
  
**ID3算法-实际使用需要注意：**

**Data cleaning **删除/减少noise，补填missing values  
**Data transformation**  
数据标准化（data normalization）  
数据归纳（generalize data to higher-level concepts using concept hierarchies）  
例如： 年龄归纳为老、 中、 青三类，控制每个属性的可能值不超过七种（最好不超过五种）  
**Relevance analysis**  
对于与问题无关的属性： 删  
对于属性的可能值大于七种又不能归纳的属性： 删  
**ID3算法-小结**

ID3算法的基本思想是， 以**信息熵为度量**， **用于决策树节点的属性选择**， **每次优先选取信息量最多的属性**， 亦即能**使熵值变为最小的属性**， 以构造一颗熵值下降最快的决策树， 到**叶子节点处的熵值为0**。 此时， 每个叶子节点**对应的实例集中的实例属于同一类**。  
关于ID3决策树构建的代码，我就不重新给了，网上到处都是，理解信息增益的算法，自己构造决策树应该问题不大，Node class应该要有root结点，属性，属性特征，已有的树，还在结果表现形式就行。实在不行就参考这个大神的[https://github.com/wzyonggege/statistical-learning-method/blob/master/DecisonTree/DT.ipynb][https_github.com_wzyonggege_statistical-learning-method_blob_master_DecisonTree_DT.ipynb]

**C4.5的生成算法**  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 17][]

### 4. 决策树的剪枝 ###

通过极小化决策树整体的损失函数或代价函数来实现。  
设树T的叶结点个数为|T|,t是树T的叶结点， 该叶结点有Nt个样本点， 其中k类的样本点有Ntk个， k=1,2..K,Ht(T)为叶结点t上的经验熵， α≥0为参数， 损失函数：  
经验熵：![20181219151221920.png][]  
原式第一项：![20181219151233688.png][]  
则：![20181219151242362.png][]

树的剪枝算法：![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 18][]  
设一组叶结点回缩到其父结点之前与之和的损失函数分别为：![20181219151356296.png][]  
如果： ![20181219151406609.png][]则进行剪枝![20181219151427139.png][]

###    5. ＣＡＲＴ算法 ###

**决策树面临的问题**  
理想的决策树有三种：  
(1)**叶子结点数最少**；  
(2)**叶子结点深度最小**；  
(3)**叶子结点数最少且叶子结点深度最小**。  
然而， 洪家荣等人已经证明了要找到这种最优的决策树是NP难题。 因此， 决策树优化的目的就是要找到尽可能趋向于最优的决策树。  
过度拟合  
决策树算法增长树的每一个分支的深度， 直到恰好能对训练样例比较完美地分类。 实际应用中， 当数据中有噪声或训练样例的数量太少以至于不能产生目标函数的有代表性的采样时， 该策略可能会遇到困难。  
 在以上情况发生时， 这个简单的算法产生的树会过渡拟合训练样例（过渡拟合： Over Fitting）  
对学习算法是否成功的真正测试是看它对于训练中未见到的数据的执行性能。 训练过程应该包含训练样本和验证样本。 验证样本用于测试训练后的性能。 如果验证结果差， 则需要考虑采用不同的结构重新进行训练， 例如使用更大的样本集， 或者改变从连续值到离散值得数据转换等。  
通常应该建立一个验证过程， 在训练最终完成后用来检测训练结果的泛化能力。  
一般可以将分类模型的误差分为：  
1、 训练误差（Training Error） ；  
2、 泛化误差（Generalization Error）  
训练误差是在训练记录上误分类样本比例；  
泛化误差是模型在未知记录上的期望误差；  
一个好的模型不仅要能够很好地拟合训练数据， 而且对未知样本也要能够准确地分类。  
 一个好的分类模型必须具有低的训练误差和泛化误差。 因为一个具有低训练误差的模型， 其泛化误差可能比具有较高训练误差的模型高。 （训练误差低， 泛化误差高， 称为过渡拟合）  
决策树算法比较适合处理离散数值的属性。 实际应用中属性是连续的或者离散的情况都比较常见。  
在应用连续属性值时， 在一个树结点可以将属性Ai的值划分为几个区间。 然后信息增益的计算就可以采用和离散值处理一样的方法。 原则上可以将Ai的属性划分为任意数目的空间。 C4.5中采用的是二元分割（BinarySplit） 。需要找出一个合适的分割阈值。  
**CART树**  
目标变量是类别的 --- 分类树  
目标变量是连续的 --- 回归树  
**CART与ID3的不同**  
**二元划分**：  
二叉树不易产生数据碎片， 精确度往往也会高于多叉树  
**CART中选择变量的不纯性度量：**  
分类目标： Gini指标、 Towing、 order Towing  
连续目标： 最小平方残差、 最小绝对残差  
**剪枝：**  
用预剪枝或后剪枝对训练集生长的树进行剪枝

**树的建立**：  
如果目标变量是标称的， 并且是具有两个以上的类别， 则CART可能考虑将目标类别合并成两个超类别（双化） ；  
如果目标变量是连续的， 则CART算法找出一组基于树的回归方程来预测目标变量。  
**CART算法**由两部分组成：  
决策树生成  
决策树剪枝  
回归树： 平方误差最小化  
分类树： Gini Index  
回归树的生成

**CART生成**  
设Y是连续变量， 给定训练数据集：![20181219152007950.png][]  
假设已将输入空间划分为M各单元R1,R2..Rm,并且每个单元Rm上有一个固定的输出Cm， 回归树表示为：![20181219152034603.png][]  
平方误差来表示预测误差， 用平方误差最小准则求解每个单元上的最优输出值：![2018121915205326.png][]  
Rm上的Cm的最优值：![20181219152117155.png][]

**最小二乘回归树生成算法**  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 19][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 20][]

分类树的生成：  
基尼指数  
分类问题中， 假设有k个类， 样本点属于k的概率Pk，则概率分布的基尼指数：![20181219152520780.png][]  
二分类问题：![20181219152533140.png][]  
对给定的样本集合D， 基尼指数：![20181219152551799.png][]

如果样本集合D根据特征A是否为a被分割成D1和D2，即![20181219152639753.png][]  
则在特征A的条件下， 集合D的基尼指数：![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 21][]

**CART生成算法**  
输入： 训练数据集D， 停止计算条件  
输出： CART决策树  
从根节点开始， 递归对美国结点操作  
1、 设结点数据集为D， 对每个特征A， 对其每个值a，根据样本点对A=a的测试为是或否， 将D分为D1， D2，计算A=a的基尼指数  
2、 在所有的特征A以及所有可能的切分点a中， 选择**基尼指数最小**的特征和切分点， 将数据集分配到**两个子结点中**。  
3、 对两个子结点递归调用1， 2步骤  
4、 生成CART树  
**CART剪枝**  
1、 **从生成算法产生的决策树T0底端开始不断剪枝， 直到T0的根结点， 形成子树序列\{T0,T1..Tn\}**,  
2、 **通过交叉验证法在独立的验证数据集上对子树序列进行测试， 从中选择最优子树**  
1、 剪枝， 形成子树序列  
剪枝过程中， 计算子树的损失函数：![20181219152845329.png][]  
对固定的a一定存在损失函数最小的子树， 表示为Ta，当a变大时， 最优子树Ta偏小，a=0时， 整体树最优， a趋近无穷大， 单结点最优。将a从小增大， 0=![20181219152917842.png][]![20181219152935989.png][]

具体： 从T0开始剪枝， 以t为单结点树的损失函数：![20181219153017813.png][]  
以t为根结点的子树Tt的损失函数：![2018121915302922.png][]  
当a=0及a很小时，![20181219153058574.png][]  
不断增大a， 当![2018121915310848.png][]![20181219153119375.png][]  
Tt与t有相同损失函数值， 但t结点更少， 所以剪枝Tt。

对T0中每个内部结点t， 计算：![20181219153153236.png][]  
在T0中剪去g(t)最小的Tt， 将得到的子树作为T1， 同时将最小的g(t)设为a1， T1为区间\[a1,a2) 的最优子树  
如此剪枝下去， 直到根节点， 不断增加a的值， 产生新的区间。

2、 在剪枝得到的子树序列\{T0,T1…Tn\}中通过交叉验证选取最优子树Ta  
利用独立的验证数据集， 测试子树序列中各子树的平方误差或基尼指数， 最小的决策树就是最优决策树。

以上内容均出自李航老师的《统计学习方法》。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70]: /images/20220404/5223244321594cff8cfaf4ab324c6c47.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 1]: /images/20220404/513a64f20f364a70b7065f60759b4fc4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 2]: /images/20220404/0fa6357e24d4467493d80be681bef2fe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 3]: /images/20220404/ef87dc8910904c8fadd9c16bcb8cabd3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 4]: /images/20220404/b3c2f8c23f6b478abfbc97108e38b4e1.png
[20181218155142732.png]: /images/20220404/5f860f67b38f4161ac6d46c97d7dbcad.png
[2018121815512515.png]: /images/20220404/340aef89b7cf41649fefe27cc88cab83.png
[20181218155100690.png]: /images/20220404/344804f825f04aba86db5faafb3760cd.png
[20181218155157869.png]: https://img-blog.csdnimg.cn/20181218155157869.png
[20181218155235524.png]: /images/20220404/ae65db87fc0c4cd9bd82c1d1b32bb5f3.png
[20181218155344701.png]: /images/20220404/480ae895845f404f88a609796f4d57b5.png
[20181218155359112.png]: /images/20220404/8fe1beffa0a340a282951e5d16ccb55d.png
[201812181554209.png]: /images/20220404/18a2fa7a50b04281be2aefacd19cca60.png
[2018121815554388.png]: /images/20220404/1cd733578f8d462ebf60645e0bd83a29.png
[20181218155557123.png]: /images/20220404/f95ceee9440841e184e2a16661ee75c6.png
[20181218155649136.png]: /images/20220404/6fe141d820d44c4d959e44071abf7f2b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 5]: /images/20220404/8e4efbb901c34a6b91d9a6a384e1ada9.png
[20181218160417827.png]: /images/20220404/cdc277a7bb3041ec8aead86d4ff3cb6a.png
[20181218160440755.png]: /images/20220404/3cd82a94bd9f4adfabed88d5fa4d5c33.png
[20181218160609518.png]: /images/20220404/a7299185116f4e3b8765c4445d72bdcf.png
[20181218160820357.png]: /images/20220404/6e87bd1706044d4fa92ccd68f6a415f5.png
[20181218160833816.png]: /images/20220404/2090028883734871855fe0a76a3d73b0.png
[20181218160851453.png]: /images/20220404/e1fabc95532c4eeeab98990941ea197c.png
[20181218161205418.png]: /images/20220404/586a6200704b4dce91903989bca6a6ec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 6]: /images/20220404/21512c27bb89477aab101ffb73eff4f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 7]: /images/20220404/86b95a47d5634797b1f55d15d5cc72dc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 8]: /images/20220404/ed04a12255454957895b5944af4031a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 9]: /images/20220404/633c0a7c8ac04d0298390dbb9f863505.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 10]: /images/20220404/ca0add42d4454430972ab8720680f8d7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 11]: /images/20220404/dda713a5f08645af823775bb724b82a6.png
[20181218204817834.png]: /images/20220404/65851225177443e293a68ef9a46951ab.png
[20181218211532548.png]: /images/20220404/9f975213eda14d77842b3af6bdac4105.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 12]: /images/20220404/e77e4e1e6c274441b56721d859df2f84.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 13]: /images/20220404/3ef8b95cfa704406916f56cd98225e35.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 14]: /images/20220404/94aeb93bd4fb4d08acf222b67311c630.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 15]: /images/20220404/93db3f9bde0f4241a4da3c49f7489825.png
[20181219115216509.png]: /images/20220404/6c2c54439ca34db5af80211d2f0faeb3.png
[20181219120342196.png]: /images/20220404/4cd9bc177dc84a76a98d8ac68bddf319.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 16]: /images/20220404/fc6e61acf0ab4ce197089769e0b511c3.png
[https_github.com_wzyonggege_statistical-learning-method_blob_master_DecisonTree_DT.ipynb]: https://github.com/wzyonggege/statistical-learning-method/blob/master/DecisonTree/DT.ipynb
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 17]: /images/20220404/89565676079f43ccbe65118559b96fe5.png
[20181219151221920.png]: /images/20220404/300ca43afc2a4f46a9a9a5470026fa68.png
[20181219151233688.png]: /images/20220404/80ba37ca2ede4769a62186a54ac59401.png
[20181219151242362.png]: /images/20220404/201d8e7722b04d00adcdf2088291f542.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 18]: /images/20220404/c32508b6e19b4bf79ce6c0708a3fae93.png
[20181219151356296.png]: /images/20220404/fa74157243e341fe8edbbe558fec0aba.png
[20181219151406609.png]: https://img-blog.csdnimg.cn/20181219151406609.png
[20181219151427139.png]: /images/20220404/e246bc0d2f1b4a22a4d8006a25c3c306.png
[20181219152007950.png]: /images/20220404/f97fe02d2db948ef824ee2f79e4ba9c6.png
[20181219152034603.png]: /images/20220404/b9d5dc88643c4f3ca251733e57734de8.png
[2018121915205326.png]: /images/20220404/355529ddfb4640a9bae4c108083a9c16.png
[20181219152117155.png]: /images/20220404/f1abd0cf10034aa0adf51d66a36b4440.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 19]: /images/20220404/aaa070bef790477ba4a1fc35a94172ba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 20]: /images/20220404/94db13d94eb94762a792400178c75846.png
[20181219152520780.png]: /images/20220404/61dee4df6f7c49dd99053473b675efcf.png
[20181219152533140.png]: /images/20220404/80d1ad6fd23d40f3afa55c10272b4230.png
[20181219152551799.png]: /images/20220404/fcfc22b59cfb4880864b8e4f1527fb53.png
[20181219152639753.png]: /images/20220404/9e491e12c2e744dc88a4bbb13c454510.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 21]: /images/20220404/8956b6c5884f46e8a5e7b42a98779730.png
[20181219152845329.png]: /images/20220404/db285e1625144ddc905a70e276673819.png
[20181219152917842.png]: https://img-blog.csdnimg.cn/20181219152917842.png
[20181219152935989.png]: /images/20220404/d6a1c46153734619b088e15ebc911be1.png
[20181219153017813.png]: /images/20220404/4c4fbd8d6beb429295170df064daf8d6.png
[2018121915302922.png]: /images/20220404/44ac35bb7d9248cb9c6d606169616e9d.png
[20181219153058574.png]: /images/20220404/b1e731ebf5144fed9f790a6e2d528be7.png
[2018121915310848.png]: https://img-blog.csdnimg.cn/2018121915310848.png
[20181219153119375.png]: /images/20220404/07377961d8e5489b8163aa5d6217fd36.png
[20181219153153236.png]: /images/20220404/c72b16638e9346e98cea0181267d65b8.png