决策树与集成算法

举例&＃xff1a;判断是否喜欢玩游戏

机器学习算法并没有哪个好哪个不好&＃xff0c;而是哪个算法更适合于那种数据类型

决策顺序&＃xff1a;先按照重要的&＃xff0c;然后次重要的&＃xff0c;依次类推

即针对每个特征&＃xff0c;都做一次切割分类&＃xff0c;特征越多越好吗&＃xff1f;

根据什么依据去选择根节点&＃xff1f;如何切分&＃xff1f;

希望透过一次分支后&＃xff0c;熵值越小越好。

pi&＃xff1a;取到某一个类别的概率

对数函数曲线如下&＃xff0c;由于概率值pi属于【0-1】区间&＃xff0c;因此对数值恒为负数&＃xff0c;H&＃xff08;x&＃xff09;函数中的-p*lg(p) 负号就负责将结果变为正数&＃xff1b; 概率越小&＃xff0c;对数值负的越厉害&＃xff0c;即概率越小&＃xff0c;熵越大

信息增益最大的为大当家&＃xff0c;其次二当家&＃xff0c;三当家&＃xff0c;以此类推

Outlook&＃61;summy时&＃xff0c;H(x) &＃61; - [2/5 * lg(2/5) &＃43; 3/5 * lg(3/5)] &＃61; 0.971

Outlook&＃61;overcast时&＃xff0c;H(x) &＃61; - [0 * lg(0) &＃43; 1 * lg(1)] &＃61; 0  特别纯粹的一个单一结果&＃xff0c;必然发生&＃xff0c;熵值为0

Outlook&＃61;rainy时&＃xff0c;H(x) &＃61; - [2/5 * lg(2/5) &＃43; 3/5 * lg(3/5)] &＃61; 0.971

上式的熵值为&＃xff0c;把Outlook作为根节点的熵值

ID3

原始数据中&＃xff0c;除了outlook/temperature/humidity/windy 四个特征&＃xff0c;还有一个ID编号&＃xff0c;每个样本都有一个唯一的编号。14行这14个数据&＃xff0c;每行一个ID&＃xff0c;对应一个特征。

如果以ID为特征&＃xff0c;作为根节点&＃xff0c;进行遍历&＃xff0c;则ID1遍历后对应的是自己&＃xff0c;ID2对应的也是自己&＃xff0c;。。。&＃xff0c;一直到ID14&＃xff0c;对应的都是自己那一个样本&＃xff1b;即以ID为根节点遍历后&＃xff0c;每个样本都是一个独立的子节点&＃xff0c;每个叶子节点对应的熵值都是0&＃xff0c;即最终的熵值也是0&＃xff0c;即信息增益最大&＃xff0c;即以ID为特征进行遍历最佳。

ID只是一个编号&＃xff0c;对最终结果没有影响&＃xff0c;即ID对应的属性非常稀疏&＃xff0c;每个样本的结果又是固定的&＃xff0c;熵值很低

C4.5:

ID3 算法信息增益很大&＃xff0c;那它自身的熵值又是什么样呢&＃xff1f;

ID[1,2,3,...,14], 熵值 &＃61; - 1/14 * lg(1/14) , 得到自身的熵值是一个极大的熵值。信息增益率&＃xff1a;信息增益/自身的熵值

CART

越纯&＃xff0c;概率越接近于1&＃xff0c;基尼系数越小

如果拿到的原始数据是连续值&＃xff0c;最好先进行离散化&＃xff0c;即进行二分&＃xff0c;遍历所有的值&＃xff0c;找出在哪个点进行二分更合理。

假如有100个特征&＃xff0c;每次按照每个特征进行切分&＃xff0c;问题是这棵树是否过大&＃xff1f;

如果特征多&＃xff0c;每次都用到每个特征&＃xff0c;则会导致这棵树过大&＃xff0c;则需要修整一下&＃xff0c;剪枝&＃xff0c;防止过拟合。

假设有100个数据样本&＃xff0c;构造一棵树&＃xff0c;可以将100个样本都落在对应的叶子节点上&＃xff0c;每个叶子节点无休止的分割下去&＃xff0c;可能有些叶子节点有两个&＃xff0c;则继续切割&＃xff0c;所有样本都会落到唯一的叶子节点上面&＃xff0c;每个叶子节点只有一个样本&＃xff0c;即所有的叶子节点都极度纯净&＃xff0c;理论上&＃xff0c;决策树可以把每一个数据完全分开。但效果不佳&＃xff0c;泛化能力较弱

过拟合&＃xff1a;训练集上表现很好&＃xff0c;测试集上表现很差。

预剪枝&＃xff1a;N个特征对应决策树的深度为N&＃xff0c;透过限制特征个数来限制决策树的深度

SVM/神经网络等算法&＃xff0c;无法做可视化展示&＃xff0c;且计算复杂

决策树算法便于分析/可视化展示&＃xff0c;效果还不错。

根节点算第一级深度&＃xff0c;每向下加一层&＃xff0c;深度加1

不可分给的节点为叶子节点。

如果限制深度为3&＃xff0c;则效果如下&＃xff0c;只保留前三层&＃xff0c;第三层以下均不再继续切分

1- 限制叶子节点个数&＃xff1a;如下图&＃xff0c;所有不可分割的最终节点就是叶子节点&＃xff0c;限制的条件为限制圈起来的叶子节点的总书目

2- 如果限制叶子结点个数为5&＃xff0c;则子节点个数到达5个时&＃xff0c;就不会继续分裂&＃xff0c;若下图&＃xff0c;只有编号为1-5 5个子节点。深度为第3层切割完成后<到了第4层>&＃xff0c;由于叶子节点的数目达到5个&＃xff0c;则停止切割

3- 限制叶子节点样本数&＃xff1a;每个叶子节点都有对应的各自的样本数。

如果限制的最小样本数为10&＃xff0c;当某叶子节点样本数为8&＃xff0c;小于10&＃xff0c;则不再继续分裂

4- 限制信息增益&＃xff1a;基尼系数差值

后剪枝

C(T): 当前损失&＃xff1a;叶子节点的样本数 * 熵值或基尼系数

计算每个叶子节点的<叶子节点的样本数 * 熵值或基尼系数>,然后再把它们累加在一起

alpha * |Tleaf|&＃xff1a;限制叶子节点个数

将alpha * |Tleaf| 加入到损失函数中&＃xff0c;目的是让整体损失值越小越好(叶子节点越多&＃xff0c;损失越大)