决策树的概念
决策树算法的简单了解
决策树概念
- 决策树是一棵树(可以是二叉树,也可以是非二叉树),非叶子结点存放测试属性值,叶子结点是输出的结果
- 决策树帮助我们做出判断(或者得出结果),根据一系列属性的判断,在叶子结点得到我们想要的结果
- 决策树的主要不在于使用决策树,而是要构建出一颗合适的决策树
实例:
上面对是否能偿还银行贷款是一个典型的决策树:根据判断对象的一些属性(房产、结婚、收入),得出结论 判断对象时候有能力偿还贷款。
决策树的类别
- 分类树: 输出类别。分类树的输出是定性的,比如天气,网页是否为垃圾网页等。常用C4.5,ID3。
- 回归树: 输出值。回归树的输出是定量的, 比如根据气候,季节等条件输出水位可能上涨多少。
决策树的构建过程
决策树的特征选择
决策树的生成
决策树的剪枝
决策树的特征选择
本质就是帮助我们做出决策的属性(房款,结婚,月收入。。。),在书面上专业用语——信息增益(信息增益比)。
信息增益:
- 输入:训练集 和 特征集
- 输出:特征值对于 训练集的信息增益g(D,A)
(1)计算出训练集的经验熵
(2)计算特征值A 对数据集的经验条件熵
H(D/A)
(3)计算信息增益熵
g(D,A) = H(D) - H(D/A)
信息增益的缺点:会偏向取值更多的点。改进——信息增益比
信息增益比:gR(D,A) = g(D,A) / HA (D)
决策树的生成
本质就是对选择的特征进行定位,哪个是根节点,哪些节点是哪些节点的父节点,根据信息增益进行构建——ID3,根据信息增益比——C4.5 ,越重要的特征,它的信息增益或者信息增益比就越大。构建完成后,就相当于模拟人的判断过程。
决策树的剪枝
我们比不是使用所有的数据进行构建决策树,我们根据一部分训练集进行构建,因此会可能出现一些问题。比如这个决策树只适用于这个训练集,而不适用于其他数据集,专业用语——出现过拟合状态。 我们将极端的“树枝树叶”剪去。增强泛化能力。本质: 第二步(决策树的生成)只达到了一个局部最优化,要通过剪枝达到全局最优化——从当前最好,去实现人生的最优化。
决策树生成:学习局部的模型
决策树的剪枝:学习整体的模型
决策树基本算法
简单介绍算法的基本概念
主要涉及ID3,C4.5
ID3算法
一个分类决策树算法
输入:数据集D,特征集A,阈值E
输出:决策树T
含义:
阈值:当两次迭代的结果都相近时候,就不用了继续迭代了。阈值控制迭代的次数。
过程:
- D 中所有的实例都属于同一类,T为单节点,将该类作为该节点的类标记。
- A=空(没有特征集)。选择D中类别最多的类作为该节点的类标记。
- 否则,计算 A中的所有特征,对于D 的特征增益,得到最大的特征Ag;
- 如果Ag < E :T为单节点数,因为特征没有足够的划分性。
- 否则:对于Ag中的每一个值,将D划分成非空子集,每个自己中最多的类作为标记该子节点的类,由节点和子节点构成树返回。
- 迭代,递归生成
C4.5
与ID3 算法的区别:只有计算信息增益比,而不是信息增益。
分类回归树 CART
基本概念:CART知识构造一个二叉树,每一步只能有两个分支。
回归树的生成:最小二乘回归树生成算法。找到最优切分变量j 和最优切分点S(本质就是找到j变量j和s使式子值最小)
分类树的生成:基于*基尼指数(类似于信息增益)
分类树的剪枝:
1)形成子树序列
2)在子树序列中通过交叉验证,选怎最优子树
only介绍一个大概知识框架
如果能考研成功,再继续学习,将所有模块补全吧