Decision tree principle and code implementation

1.树模型

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

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

2.树的组成  

        根节点：第一个选择点

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

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

 

3.决策树的训练与测试         

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

        测试阶段：According to the constructed tree model, it goes from the root node to the leaf node

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

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

        衡量标准-熵  

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

        公式：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里面只有两种类别,relatively stableB中类别太多了,熵值就会大很多

        熵：不确定性越大,得到的熵值也就越大,当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,同样的方式可以计算出其他特征的信息增益,Then we can choose the largest one

决策树算法

ID3：信息增益

 问题：When data exists oneID特征,那么,决策树在idThe entropy of the feature is0,就会根据ID进行分支,但是IDFeatures are meaningless.Decision trees cannot handle matrix sparsity,There are more kindsid特征

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

Divide the information gain by its own entropy value

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

GINI系数：

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

连续值怎么办？

 

决策树剪枝策略  

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

（想象一下,如果树足够庞大,Each leaf node has only 1个数据了）

剪枝策略：预剪枝,后剪枝

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

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

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

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

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