决策树是基于特征对实例进行分类的树形结构。 决策树学习算法包括：特征选择、树的生成和树的剪枝。
2.1.ID3 (1)、针对当前的集合，计算每个特征的信息增益 (2)、选择信息增益最大的特征作为当前节点的决策决策特征 (3)、根据特征不同的类别划分到不同的子节点（比如年龄特征有青年，中年，老年，则划分到3颗子树） (4)、继续对子节点进行递归，直到所有特征都被划分
g(D|A)=H(D)−H(D|A) H(D)=−∑k=1k|Ck|Dlog2|Ck|D H(D|A)=∑i=1nDiDH(Di) 其中数据集为D, Di 是D的子集，H(D)是数据集D的熵， H(Di) 是数据集 Di 的熵，H(D|A)是数据集D对特征A的条件熵. Ck 是D中属于第k类的样本子集。n是特征A取值的个数，k是类的个数。举个栗子： 当前特征是天气状况，分类是明天是否会下雨 现在天气特征阴天是7个，4个是明天会下雨，3个是明天不下雨 现在天气特征多云是3个，1个是明天会下雨，2个是明天不下雨
H(阴天)= −(47log247+37log237) H(多云)= −(47log247+37log237) H(D)= −(510log2510+510log2510) H(D|天气状况) = −(710H(阴天)+310H(多云)) g(D|天气状况) = H(D)-H(D|天气状况)
2.2.C4.5 样本集合D对特征A的信息增益比
gr(D,A)=g(D,A)H(D) 其中g(D,A)是信息增益，H(D)是数据集D的熵。 优缺点： 准确率高，但是子构造树的过程中需要进行多次的扫描和排序，所以它的运算效率较低 2.3.CART 样本集合D的基尼指数 Gini(D)=1−∑k=1K(g(D,A)H(D))2 特征A条件下集合D的基尼指数: Gini(D,A)=|D1||D|Gini(D1)+|D2||D|Gini(D2)通常使用信息增益最大、信息增益比最大或基尼指数最小为特征选择的准则。从根节点开始递归生成决策树。
剪枝前置剪枝：在分裂节点的时候设计比较苛刻的条件，如不满足则直接停止分裂（这样干决策树无法到最优，也无法得到比较好的效果） 后置剪枝：在树建立完之后，用单个节点代替子树，节点的分类采用子树中主要的分类（这种方法比较浪费前面的建立过程） 交叉验证随机森林
优点： 计算量简单，可解释性强，比较适合处理有缺失属性值的样本，能够处理不相关的特征； 缺点： 单颗决策树分类能力弱，并且对连续值变量难以处理； 容易过拟合（后续出现了随机森林，减小了过拟合现象）；
