看完书后，我参考了机器学习实战里面的一些函数，自己用Python实现了决策树。我在实现过程中并没有很好地利用好数据结构中树的概念，代码还有很多需要改进的地方。接下来我就简单总结下我的代码实现。

代码整体的算法参考课本的74-80页。我是先实现基于信息熵进行划分选择的决策树算法，先完整生成一棵决策树，再逐步修改代码，实现预剪枝等。

数据集如下：

数据集

假设训练集为D，属性集为A，决策的实现在于从属性集A中挑选出最优属性a，根据属性a划分数据集，然后再继续在划分好的数据集中继续寻找最优属性，多次迭代，生成一棵树。迭代的终止条件为：（1）当前数据集同属一类别，例如划分好的数据集全为好瓜（2）当前属性集A为空，或者数据集在所有属性上的取值相同（3）当前数据集为空

决策算法的关键在于如何选择最优属性（包括如何选择最优属性（基于信息熵，基于基尼指数等）进行划分，是否进行划分（预剪枝，后剪枝等））

下面用基于信息熵的算法实现决策树：

1.对数据进行读取

数据文件名为waterMelonData.txt,编码格式为utf-8，用全局变量dataset存储所有数据，continusAttr存储连续属性名集    合，attrAll存储数据的第一行

数据读取

2.计算信息熵：

计算信息熵：要统计数据dataset里的类别，用resultDict存储类别（好瓜，坏瓜），再计算各类别的概率，最后算出信息熵

计算信息熵

3.计算信息增益

属性为不连续属性时：

计算信息增益

函数：

getAxis(attrChoose,attrAll)

attrChoose表示属性，通过getAxis函数获得数据文件的第几列数据表示属性attrChoose的描述，例如

attrChoose = “色泽”

得到axis = 1

splitDataSet(dataset,axis,key)

根据属性的位置axis，找出属性值为key的所有数据

getAxis函数

splitDataset函数

连续性属性：

a.要先对该属性的所有取值排序

b.计算候选划分点集合

c.分别计算候选划分点的信息增益

d.得到最大信息增益，得到最优划分点

连续性属性的信息增益计算

连续属性的数据只需要根据最优划分点，划分为两部分（data_small,data_large）即可

数据划分

到这里已经能分别算出每个属性的信息增益了，接下来就是遍历未被使用过的属性，选出信息增益最大的属性，进行数            据划分

4.根据最优属性划分

5.最后一步，整合所有函数，迭代生成树

生成树1

生成树2 

补充：countAttrKey(dataset,attr,axis)函数

countAttrKey函数

6.运行结果：

运行结果我只截取了部分

下面是根据运行结果手动画的树：

整棵生成树

7.代码修改，实现预剪枝，后剪枝等总结

a.个人觉得整体代码处于较混乱状态，在修改为预剪枝的时候，总觉得部分函数有重合，或者是函数的划分不太合理。

b.书本中是将数据集认为划分为训练集和测试集,未思考如何划分训练集合测试集

c.尴尬的是，在每个生成结点后，并没有将每个结点存储，以致于在后剪枝时出现了一定的问题。考虑用树的思想，修改代码