以下内容摘选自
1、决策数的定义
决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。
2、决策树的构造
决策树的构造中最关键的部分就是选择最优的特征进行划分数据集，其目的是将无序的数据变得更有序，其目标是让各个分裂子集尽可能地“纯”。尽可能“纯”就是尽量让一个分裂子集中待分类项属于同一类别（label相同）。分裂属性分为三种不同的情况：
1、属性是离散值且不要求生成二叉决策树。此时用属性的每一个划分作为一个分支。
2、属性是离散值且要求生成二叉决策树。此时使用属性划分的一个子集进行测试，按照“属于此子集”和“不属于此子集”分成两个分支。
3、属性是连续值。此时确定一个值作为分裂点split_point，按照>split_point和<=split_point生成两个分支。
构造决策树的关键性内容是进行属性选择度量，属性选择度量是一种选择分裂准则，是将给定的类标记的训练数据D“最好”地分成个体类的启发式方法，它决定了拓扑结构及分裂点split_point的选择。
属性选择度量的方法有很多中，机器学习实战上以ID3算法，此外常见的还有C4.5以及CART的方法。同时对于特征来说一般采取不放回的选择每个属性只能被选择一次，选择完成该属性后该特征在就被剔除出数据集，算是一种不回溯的贪心算法。
2.1 ID3算法
ID3算法采用香农熵作为度量信息度量方式，并且按照信息增益划分数据集，选择具有最高的信息增益进行划分。
香农熵定义为信息的期望值计算公式如下：
计算代码如下：
from math import log def calcShnnonEnt(dataSet): numEnties = len(dataSet)#训练数据的个数 labelCount = {}#新建字典记录每个分类下的数据个数 for featVec in dataSet:#统计每个分类的个数 currentLabel = featVec[-1] if currentLabel not in labelCount.keys(): labelCount[currentLabel] = 0 labelCount[currentLabel] += 1 for key in labelCount:#针对分类进行计算香农熵 prob = float(labelCount[key]) / numEntris shannonEnt -= prob * log(prob, 2) return shannonEnt