Python实现决策树算法（一）

1.概念明晰

决策树是一种树状结构，它的每一个叶节点对应着一个分类，非叶节点对应着在某个属性上的划分，根据样本在该属性上的不同取值将其划分为若干个自己。对于非纯的叶节点，多数类的标号给出到达这个节点的样本所属的类。构造决策树的和性问题是在每一步如何选择适当的属性对样本做拆分。对一个分类问题，从已知类标记的训练样本中学习并构造出决策树是一个自上而下，分而治之的过程。

2.决策树的相关算法

ID3算法：核心是在决策树的各级节点上，使用信息增益方法作为属性的选择标准，来帮助确定生成每个节点时所应采用的核实属性。

C4.5算法：C4.5决策树生成算法相对于IO3算法的重要改进是使用信息增益律来选择节点属性。ID3算法只适用于离散的描述属性，而C4.5算法技能处理离散，也能处理连续的描述属性。

CART算法：CART算法是一种十分有效的，非参数分类和回归方法，通过构建树、修剪树、评估树来构建一个二叉树，当终结点是连续变量时，该树为回归树，当终结点是分类变量，该树为分类树。

3.ID3算法简介及基本原理

ID3算法是基于信息熵来选择最佳测试属性， 它选择当前样本集中具有最大信息增益的属性作为测试属性，样本集的划分则依据测试属性的取值进行，测试属性有多少不同取值就将样本集划分为多少子样本集，同时决策树上相应该样本集的节点长出新的叶子节点。ID3算法根据信息论理论，采用划分后样本集的不确定性作为衡量划分好坏的标准，用信息增益值度量不确定性，信息增益度越大，不确定性越小。

4.ID3算法流程

（1）对当前样本集合，计算所有属性的信息增益

（2）选择信息增益最大的属性作为测试属性，把测试属性取值相同的样本划为同一个子样本集

（3）若子样本集的类别属性只含有单个属性，则分支为叶子节点，判断其属性值并标上相应的符号，然后返回调用处，都这对子样本集递归调用本算法。

5.实例

结合餐饮案例试试，分析天气、是否周末、是否有促销活动对销量的影响。

初始数据集如下：

实现步骤：

①跟你局公式，计算总的信息熵，其中，数据总记录数为34，而销售数量为“高”的数据有18

②根据公式，计算每个测试属性的信息熵

③根据公式，计算各个属性的信息增益值

④选择根节点分支，根据前三个步骤循环

代码示例：

import pandas as pd
#参数初始化
filename = 'F:/fenxiyuwajue/dataandcode/chapter5/chapter5/demo/data/sales_data.xls'
data = pd.read_excel(filename,index_col = u'序号')#导入数据
#数据是类别标签，要将它转化为数据
#用1表示“好”“是”‘高’三个属性，-1表示对应的消极属性
data[data ==u'好']=1
data[data ==u'是']=1
data[data ==u'高']=1
data[data !=1] = -1
x = data.iloc[:,:3].as_matrix().astype(int)
y = data.iloc[:,3].as_matrix().astype(int)
from sklearn.tree import DecisionTreeClassifier as DTC
dtc = DTC(criterion='entropy')#建立决策树模型，基于信息熵
dtc.fit(x,y)#训练模型
#导入相关函数，可视化决策树
#导出的结果是dot格式文件
from sklearn.tree import export_graphviz
x = pd.DataFrame(x)
from sklearn.externals.six import StringIO
x = pd.DataFrame(x)
with open("C:/Users/Administrator/Desktop/datatree.dot",'w') as f:
    f = export_graphviz(dtc,feature_names = x.columns,out_file = f)

运行后得出dat文件如下：

digraph Tree {

node [shape=box] ;

0 [label="1 <= 0.0\nentropy = 0.998\nsamples = 34\nvalue = [16,18]"] ;

1 [label="2 <= 0.0\nentropy = 0.934\nsamples = 20\nvalue = [13,7]"] ;

0 -> 1 [labeldistance=2.5, labelangle=45, headlabel="True"] ;

2 [label="0 <= 0.0\nentropy = 0.544\nsamples = 8\nvalue = [7,1]"] ;

1 -> 2 ;

3 [label="entropy = 0.0\nsamples = 4\nvalue = [4, 0]"] ;

2 -> 3 ;

4 [label="entropy = 0.811\nsamples = 4\nvalue = [3, 1]"] ;

2 -> 4 ;

5 [label="0 <= 0.0\nentropy = 1.0\nsamples = 12\nvalue = [6,6]"] ;

1 -> 5 ;

6 [label="entropy = 0.971\nsamples = 5\nvalue = [3, 2]"] ;

5 -> 6 ;

7 [label="entropy = 0.985\nsamples = 7\nvalue = [3, 4]"] ;

5 -> 7 ;

8 [label="0 <= 0.0\nentropy = 0.75\nsamples = 14\nvalue = [3,11]"] ;

0 -> 8 [labeldistance=2.5, labelangle=-45, headlabel="False"];

9 [label="2 <= 0.0\nentropy = 0.954\nsamples = 8\nvalue = [3,5]"] ;

8 -> 9 ;

10 [label="entropy = 0.918\nsamples = 3\nvalue = [2, 1]"] ;

9 -> 10 ;

11 [label="entropy = 0.722\nsamples = 5\nvalue = [1, 4]"] ;

9 -> 11 ;

12 [label="entropy = 0.0\nsamples = 6\nvalue = [0, 6]"] ;

8 -> 12 ;

最终我们可以利用Graphviz进行编译产出相应的图、