决策树原理及代码实现

1.树模型

        决策树：从根节点开始一步步走到叶子节点（决策）

        所有的数据最终都会落到叶子节点，既可以做分类也可以做回归

2.树的组成  

        根节点：第一个选择点

        非叶子节点与分支：中间过程

        叶子节点：最终的决策结果

 

3.决策树的训练与测试         

        训练阶段：从给定的训练集构造出来一棵树（从跟节点开始选择特征， 如何进行特征切分）

        测试阶段：根据构造出来的树模型从根节点一直走到叶子节点

        如何切分特征（选择节点） 

        目标：通过一种衡量标准，来计算通过不同特征进行分支选择后的分类情况，找出来最好的那个当成根节点

        衡量标准-熵  

        熵：熵是表示随机变量不确定性的度量 （解释：物体内部的混乱程度，比如杂货市场里面什么都有那肯定混乱呀，专卖店里面只卖一个牌子的那就稳定多啦）

        公式：H(X)=- ∑ pi * logpi, i=1,2, ... , n

        比如：

        A集合[1,1,1,1,1,1,1,1,2,2] 、B集合[1,2,3,4,5,6,7,8,9,1]

        显然A集合的熵值要低，因为A里面只有两种类别，相对稳定一些而B中类别太多了，熵值就会大很多

        熵：不确定性越大，得到的熵值也就越大，当p=0或p=1时，H(p)=0,随机变量完全没有不确定性，当p=0.5时，H(p)=1,此时随机变量的不确定性最大

        

        如何决策一个节点的选择呢？

        信息增益：表示特征X使得类Y的不确定性减少的程度。（分类后的专一性，希望分类后的结果是同类在一起）

决策树构造实例

        数据：14天打球情况

        特征：4种环境变化

        目标：构造决策树

 

 划分方式：4种

问题：谁当根节点呢？

依据：信息增益

         在历史数据中（14天）有9天打球，5天不打球，所以此时的熵应为：

4个特征逐一分析，先从outlook特征开始：

Outlook = sunny时，熵值为0.971

Outlook = overcast时，熵值为0

Outlook = rainy时，熵值为0.971

根据数据统计，outlook取值分别为sunny,overcast,rainy的概率分别为：5/14, 4/14, 5/14

熵值计算：5/14 * 0.971 + 4/14 * 0 + 5/14 * 0.971 = 0.693

（gain(temperature)=0.029 gain(humidity)=0.152 gain(windy)=0.048）

信息增益：系统的熵值从原始的0.940下降到了0.693，增益为0.247，同样的方式可以计算出其他特征的信息增益，那么我们选择最大的那个就可以了

决策树算法

ID3：信息增益

 问题：当数据存在一个ID特征，那么，决策树在id特征的熵为0，就会根据ID进行分支，但是ID特征毫无意义。决策树无法处理矩阵稀疏，种类比较多的id特征

C4.5：信息增益率（解决ID3问题，考虑自身熵）

用信息增益除以本身的熵值

CART：使用GINI系数来当做衡量标准

GINI系数：

（和熵的衡量标准类似，计算方式不相同） 

连续值怎么办？

 

决策树剪枝策略  

        为什么要剪枝：决策树过拟合风险很大，理论上可以完全分得开数据

（想象一下，如果树足够庞大，每个叶子节点就只有1个数据了）

剪枝策略：预剪枝，后剪枝

预剪枝：边建立决策树边进行剪枝的操作（更实用）

后剪枝：当建立完决策树后来进行剪枝操作

预剪枝：限制深度，叶子节点个数，叶子节点样本数，信息增益量等

后剪枝：通过一定的衡量标准

（叶子节点越多，损失越大）