决策树作为处理分类问题最经常被用到的算法，它有着优于其他机器学习算法的简明性特征，即无需了解机器学习的原理知识也能够轻松的了解这个算法是如何工作的。
举例：
完成测试，原始数据被划分成几个子集，如果某个分支下的所有数据已经属于同一子集，则无需继续划分。如果数据集合中的数据仍然不属于同一类型，则需要继续划分。划分原则同划分原始数据，该过程将一直持续直到所有数据子集都属于同一类型。createBranch() Check whether data belong to the same class: if return class_label else find the optimal feature to divide the dataset divide dataset create branch node for every divided subset call function createBranch() and add return result to branch node return branch_node 《Data Mining Concepts and Techniques》Third Edition（数据挖掘:概念与技术 第三版）
在本书中阐述了属性选择的三个度量，分别为信息增益，增益率和基尼指数（Gini 指数）
由于我们不使用增益率和基尼指数构建决策树，所以在这里不再阐述。 信息增益定义为一个特征能够为分类系统带来多少信息，带来的信息越多，该特征越重要，所以我们将选择信息增益大的作为划分属性.假设节点N存放D的元组，那么选择信息增益最高的作为N的划分属性
对于D中的元组所需要的期望信息由下表示
Info(D)是识别D中元组的类标号所需要的平均信息量，又称为D的熵(entropy)。
假设我们按照属性A分D元组，其中A可以取v个不同值{a1, a2, … aV}。可以用A属性来划分D划分称v个分区或子集 {D1,D2,…,DV}, 每一个子集 Dj 都包含D中的元组，他们的A的值是aj。这些分区对应于从结点N生找出来的分支。
考虑一个例子：我们可以按照年龄（也就是上述的A 年龄可以分为三个离散的区间0~30 31~40 40~100这三个离散区间分别代表三个值 年轻人a1 中年人a2 年长者a3）那么可以将给定的一组人（也即上述的D元组）按照A（年龄）来划分成v个子集理想情况下，我们希望划分出来的元组是准确分类的，但是往往分区并不是绝对纯净的（意思就是，分区可能包含了来自不同类的元组，也即有一些不同类别的被分在了同一子集里）为了得到准确的分类，我们所需要的信息量是
其中 |Dj|/|D| 是第j个分区的权重。 InfoA(D) 基于A的划分准则，划分D元组所需要的期望信息，所需要的期望信息越少，分区的纯度就越高，同一子集里出现不同类的就越少。
信息增益定义为 原来的信息需求(仅仅基于类的比例) 减去 新的信息需求 (基于A来划分)
Gain(A) 表示我们通过A这个属性来划分我们得到了多少。我们选择增益最大的作为N的划分属性，因为这样可以使完成元组划分还需要的信息量能够最小化(也就是最小化 InfoA(D) )
举例：使用信息增益进行决策树归纳
Table 1 ALLElectronics 顾客数据库标记类的训练元组
那么我们根据第一个公式计算出D中元组分类所需要的期望信息:
下一步我们需要计算每个属性的期望信息需求，从表中我们可以获得4个属性，分别是 age, income, student, credit_rating。
以age为例， age中一共有三类 分别是 youth, middle_age, senior. 对于 youth 有两个 正（yes） 三个 负（no）元组。 对于 middle_age， 有四个 正（yes） 零个 负（no）， 对于senior 有三个 正（yes） 两个 负（no）所以按照age划分的所需要的期望信息为：
其信息增益为
Gain(income) = 0.029位
Gain(student) = 0.151位
Gain(credit_rating) = 0.048位可以看出 age 是其中信息增益最大的，所以我们选择 age 进行划分
from math import logdef calcShannonEnt(dataSet) numEntries = len(dataSet) labelCounts = {} for featVec in dataSet: currentLabel = fearVec[-1] if currentLabel not in labelCounts.keys(): labelCounts[currrentLabel] = 0 labelCounts[currentLabel] += 1 shannonEnt = 0.0 for key in labelCounts: prob = float(labelCounts[keys])/numEntries shannonEnt -= prob * log(prob,2) return shannonEnt首先我们统计键值，以及键值中记录的当前类别出现的次数。接着我们使用所有类标签的发生频率计算类别出现的概率，并用这个概率计算熵联系客服
