决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。
之前介绍的K-近邻算法可以完成很多分类任务，但是它最大的缺点就是无法给出数据的内在含义，决策树的主要优势就在于数据形式非常容易理解。
决策树算法能够读取数据集合，构建类似于上面的决策树。决策树很多任务都是为了数据中所蕴含的知识信息，因此决策树可以使用不熟悉的数据集合，并从中提取出一系列规则，机器学习算法最终将使用这些机器从数据集中创造的规则。专家系统中经常使用决策树，而且决策树给出结果往往可以匹敌具有几十年工作经验的人类专家
2 决策树分类
分类树
分类树用于分类标签值，如晴天/阴天、用户性别、网页是否是垃圾页面,分类的值是定性的
回归树
回 归树用于预测实数值，如明天的温度、用户的年龄、网页的相关程度,回归树的值是定量的
3 构造决策树
构造决策树的关键步骤是分裂属性。所谓分裂属性就是在某个节点处按照某一特征属性的不同划分构造不同的分支，其目标是让各个分裂子集尽可能地“纯”。尽可能“纯”就是尽量让一个分裂子集中待分类项属于同一类别。
分裂属性分为三种不同的情况：
1、属性是离散值且不要求生成二叉决策树。此时用属性的每一个划分作为一个分支。
2、属性是离散值且要求生成二叉决策树。此时使用属性划分的一个子集进行测试，按照“属于此子集”和“不属于此子集”分成两个分支。
3、属性是连续值,此时确定一个值作为分裂点split_point，按照>split_point和<=split_point生成两个分支
构造决策树的关键性内容是进行属性选择度量，属性选择度量是一种选择分裂准则，它决定了拓扑结构及分裂点split_point的选择。
属性选择度量算法有很多，一般使用自顶向下递归分治法，并采用不回溯的贪心策略。这里介绍常用的ID3算法。
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。即不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解.
4 ID3算法
ID3算法就是在每次需要分裂时，计算每个属性的增益率，然后选择增益率最大的属性进行分裂
划分原则: 将无序的数据变得更加有序.
熵: 用于度量无序程度
一个系统越是有序，信息熵就越低，反之一个系统越是混乱，它的信息熵就越高。所以信息熵可以被认为是系统有序化程度的一个度量。
信息增益
组织杂乱无章数据的一种方法就是使用信息论度量信息，信息论是量化处理信息的分支科学。
在划分数据集之前之后信息发生的变化称为信息增益，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。
(1) 计算公式: p(x)是选择该分类的概率
(2) 为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值，通过下面的公式得到：
n是分类的数目
(3) 在决策树当中，设D为用类别对训练元组进行的划分，则D的熵（entropy）表示为：
其中pi表示第i个类别在整个训练元组中出现的概率，可以用属于此类别元素的数量除以训练元组元素总数量作为估计。熵的实际意义表示是D中元组的类标号所需要的平均信息量
(4) 现在我们假设将训练元组D按属性A进行划分，则A对D划分的期望信息为:
则信息增益为两者的差值: