Machine learning notes (二)
上一篇文章链接：传送门
文章目录
前言
引用博客：
https://blog.****.net/qq_20412595/article/details/82048795
一、决策树
1.1 什么是决策树？
决策树模型是运用于分类以及回归的一种树结构。决策树由节点和有向边组成，一般一棵决策树包含一个根节点、若干内部节点和若干叶节点。
1.2 决策过程
决策树的决策过程需要从决策树的根节点开始，待测数据与决策树中的特征节点进行比较,并按照比较结果选择下一比较分支，直到叶子节点作为最终的决策结果。
1.3 树结构分析
● 内部节点:对应于一个属性测试。
● 叶节点:对应于决策结果。
● 根节点包含样本全集;
● 每个节点包括的样本集合根据属性测试的结果被划分到子节点中;
● 根节点到每个叶节点的路径对应了一个判定测试路径;
1.4 决策树生成过程
-
特征选择: 特征选择是指从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准, 如何选择特征有着很多不同量化评估标准标准,从而衍生出不同的决策树算法。
-
决策树生成: 根据选择的特征评估标准，从上至下递归地生成子节点,直到数据集不可分则停止决策树停止生长。树结构来说， 递归结构是最容易理解的方式。
-
剪枝: 决策树容易过拟合, 一般来需要剪枝,缩小树结构规模、缓解过拟合。剪枝技术有预剪枝和后剪枝两种。
二：决策树常用的三种算法
2.1 ID3算法
核心思想是在决策树各个节点上根据信息增益来选择进行划分的特征，然后递归地构建决策树。
ID3的具体方法如下：
-
从根节点开始,对节点计算所有可能的特征的信息增益，选择信息增益值最大的特征作为节点的划分特征;
-
由该特征的不同取值建立子节点;
-
再对子节点递归地调用以上方法，构建决策树;
-
到所有特征的信息增益都很小或者没有特征可以选择为止，得到最终的决策树。
ID3的局限性：
● 没有剪枝
● 采用信息增益作为选择最优划分特征的标准，然而信息增益会偏向那些取值较多的特征(这也是C4.5采用信息增益率的原因)
举例：
ID3采用信息增益作为选择最优的分裂属性的方法，选择熵作为衡量节点纯度的标准,根据以上公式对上述的例子的根节点进行分裂，分别计算每一个属性的信息增益， 选择信息增益最大的属性进行分裂。
本例中正例(好瓜)占8/17,反例占9/17，根结点的信息熵为:
计算各个特征的信息增益，选取最大的计算当前属性集合{色泽，根蒂，敲声,纹理，脐部，触感}中每个属性的信息增益。色泽有3个可能的取值: {青绿，乌黑，浅白}
D1(色泽=青绿)={1,4, 6, 10, 13, 17},正例3/6,反例3/6
D2(色泽=乌黑)={2,3, 7,8,9, 15}，正例4/6,反例2/6
D3(色泽=浅白)={5, 11, 12, 14, 16},正例1/5,反例4/5
计算出用”色泽”划分之后所获得的3个分支结点的信息熵为:
由此可得“色泽”的信息增益为：
类似的，我们可以计算出其他属性的信息增益，选取信息增益最大的进行划分，依次类推，最终得到决策树:
2.2 C4.5算法
C4.5与ID3相似，但对ID3进行了改进，在这里不再详细描述C4.5的实现， 就讲一下有哪些基于ID3的改进:
主要改进：
● 用信息增益率来选择划分特征，克服了用信息增益选择的不足
● 在构造树的过程中进行剪枝
● 可对连续值与缺失值进行处理
2.3 CART算法
CART(classification and regression tree),分类回归树算法，既可用于分类也可用于回归，在这一部分我们先主要将其分类树的生成。区别于ID3和C4.5,CART假设决策树是二叉树，内部节点特征的取值为"是”和"否”，左分支取值为”是”的分支，右分支取值为”否"的分支。
这样的决策树等价于递归地二分每个特征，将输入空间(即特征空间)划分为有限个单元。CART的分类树用基尼指数来选择最优特征的最优划分点。
CART算法具体实现过程如下：
1.从根节点开始，对节点计算现有特征的基尼指数，对每一个特征， 例如AA,再对其每个可能的取值如aa,根据样本点对A=aA=a的结果的"是"与’否"划分为两个部分,利用下面公式进行计算。
2.在所有可能的特征AA以及该特征所有的可能取值aa中,选择基尼指数最小的特征及其对应的取值作为最优特征和最优切分点。然后根据最优特征和最优切分点，将本节点的数据集二分，生成两个子节点。
3.对两个子节点递归地调用上述步骤，直至节点中的样本个数小于阈值，或者样本集的基尼指数小于阈值，或者没有更多特征后停止。
4.生成CART分类树