算法-决策树

决策树基础知识：

决策树是一种监督学习算法 ，在机器学习与数据挖掘领域常用，用于分类和回归任务 ，可直观呈现决策逻辑，像流程图一样逐步对样本分类或预测数值

根节点：起始点，包含全部样本，全部数据

叶子节点：终点，输出最终决策结果，最后输出为0就不可分了

构造决策树的核心难点是 “如何选特征、切分数据”，需通过熵和信息增益量化特征的分类价值

算法：

熵：熵是表示随机变量不确定性的度量；不确定性越大，得到的熵值也就越大，所以熵值越小越好

熵计算公式：H(X)=- ∑ pi * logpi, （i=1,2, ... , n）

信息增益：表示特征X使得类Y的不确定性减少的程度。熵值越大越好。

信息增益：用特征 A 分类后，数据不确定性（熵）的下降幅度。增益越大，特征分类价值越高，优先选作节点。

例如：

由图可知，play为标签，剩下的为特征，总熵根据上边的计算公式为：-（9/14log2 9/14+5/14log2 5/14）=0.94

特征一

(sunny)熵：-（2/5log2 2/5+3/5log2 3/5）=0.971

(overcast)熵为0，纯类别，没有不确定性

(rainy)熵：-(3/5log2 3/5+2/5log2 2/5)=0.971

加权为：5/14*0.971+4/14*0+5/14*0.971=0.694

信息增益为：0.94-0.694=0.246

特征二特征三特征四，同理

最后比较信息增益，信息增益最大的为大当家（决策树里为了方便我们把第一个节点称为大当家，第二个称为二当家以此类推）

这里我们以第一个特征为例，假设第一个特征为大当家，我们求二当家：

temperature中对应大当家sunny有hot（2个）,mild（2个）,cool(1个)，当sunny对应hot时，特征为yes的有0个熵为0，sunny对应mild的有1个yes1个no，所以熵为1,SUNNY对应cool的有1个yes,所以熵为0，加权为：5/14（2/5*0+2/5*1*+1/5*0）=0.14，信息增益为：0.694-0.14=0.554

以此类推，求接下来的信息增益，那个信息增益最大，便将他作为二当家，注意的是：二当家加权时要加两遍权。

例：

总体熵为：-（2/5log2/5+3/5log3/5）=0.971

特征一熵：-（2/3log2/3+1/3log1/3）=0.918，否的为0，纯类别

                加权平均为：3/5*0.918+2/5*0=0.551

                信息增益为：0.971-0.551=0.420

特征二熵为：-（2/4log2/4+2/4log2/4）=1，否的为0，

               加权平均为：4/5*1+1/5*0=0.8

               信息增益为：0.971-0.8=0.171

根据信息增益比较，我们选择特征一作为大当家可以更好地划分。

求二当家：熵为0，否的已经纯了，就不用计算了

所以信息增益为：0.918-0=0.918

分层选筛子，每层选当前最能筛纯的特征，让最终结果清晰、可解释！