西瓜书笔记.md

目录

西瓜书笔记

• 1. 绪论
• 2. 线性模型
  • 2.1. 线性回归
  • 2.2. logistic回归
  • 2.3. 线性判别分析
  • 2.4. 多分类学习
    • 2.4.1. 一对一(OvO)
    • 2.4.2. 一对其余(OvR)
    • 2.4.3. 多对多(MvM)
• 3. 决策树
  • 3.1. 基本流程
  • 3.2. 划分选择
    • 3.2.1. 信息熵 (information entropy)
    • 3.2.2. ID3：信息增益 (information gain)
    • 3.2.3. ID4.5：增益率
    • 3.2.4. CART：基尼指数
      • CART分类树建立算法的具体流程
      • CART回归树
  • 3.3. 剪枝处理
    • 3.3.1. 预剪枝
    • 3.3.2. 后剪枝
    • 3.3.3. CART决策树的剪枝
  • 3.4. 连续与缺失值
    • 3.4.1. 连续值处理
    • 3.4.2. 缺失值处理
      • 3.4.2.1. 问题(1)划分属性选择
      • 3.4.2.2. 问题(2)属性值缺失样本的划分
• 4. 支持向量机
  • 4.1. 支持向量机与优化目标
  • 4.2. 用对偶问题解SVM优化目标
    • 4.2.1. 对偶问题
    • 4.2.2. 用SMO法解对偶问题
    • 4.2.3. 基于对偶问题的解得到最终解
  • 4.3. 解决非线性可分问题：核函数
    • 4.3.1. 非线性可分问题及解决策略：高维映射
    • 4.3.2. 解决高维映射带来的计算问题：构造核函数
      • 4.3.2.1. 核函数实现高效计算的例子
    • 4.3.3. 如何构造核函数
  • 4.4. 软间隔与正则化
    • 4.4.1. 引入软间隔
    • 4.4.2. 原始0/1损失函数与替代损失函数
    • 4.4.3. 基于hinge损失的常用“软间隔SVM”
    • 4.4.4. 不同软间隔SVM的共性
  • 4.5. 支持向量回归（SVR）
    • 4.5.1. SVR的基本思想
    • 4.5.2. SVR的优化目标与求解
• 5. 贝叶斯分类器
  • 5.1. 贝叶斯决策论
  • 5.2. 最小化分类错误率
  • 5.3. 如何获得后验概率P(c|x)？
    • 5.3.1. 判别式模型与生成式模型
    • 5.3.2. 估计类条件概率：极大似然估计
  • 5.4. 朴素贝叶斯分类器
    • 5.4.1. 什么是朴素贝叶斯分类器？
    • 5.4.2. 如何训练？
    • 5.4.3. 数据平滑：Laplacian修正
  • 5.5. 半朴素贝叶斯分类器
  • 5.6. 贝叶斯网
    • 5.6.1. 结构
    • 5.6.2. 学习
    • 5.6.3. 推断：吉布斯采样
  • 5.7. EM算法
• 6. 神经网络
  • 6.1. 神经元模型
  • 6.2. 感知机和多次网络
  • 6.3. 神经网络学习：BP算法
    • 6.3.1. 标准BP算法
    • 6.3.2. 累积BP算法
    • 6.3.3. 过拟合与解决方案
  • 6.4. 全局最小与全局极小
• 番外一：一小时打完一次比赛
• 番外二：sklearn包中logistic回归算法的使用
  • *2.1. 与logistic回归相关的类
  • *2.2. 优化算法
  • *2.3. 正则化参数的选择：penalty
  • *2.4. 分类方式选择参数：multi-class

西瓜书笔记

1. 绪论 ^目录

2. 线性模型 ^目录

2.1. 线性回归 ^目录

2.2. logistic回归 ^目录

2.3. 线性判别分析 ^目录

2.4. 多分类学习 ^目录

2.4.1. 一对一(OvO) ^目录

2.4.2. 一对其余(OvR) ^目录

2.4.3. 多对多(MvM) ^目录

3. 决策树 ^目录

3.1. 基本流程 ^目录

3.2. 划分选择 ^目录

3.2.1. 信息熵 (information entropy) ^目录

Ent(D)的值越小，则D的纯度越高

3.2.2. 信息增益 (information gain) ^目录

ID3算法的缺点：

• (1) ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途

• (2) ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大

• (3) ID3算法对于缺失值的情况没有做考虑

• (4) 没有考虑过拟合的问题

针对各个问题，发展出来了对应的处理策略：

• 对应(1)，连续值的处理：使用连续属性离散化技术——二分法

• 对应(2)，增益率

• 对应(3)，缺失值处理

• 对应(4)，剪枝处理

3.2.3. 增益率 ^目录

C4.5虽然改进或者改善了ID3算法的几个主要的问题，仍然有优化的空间

• 1. 由于决策树算法非常容易过拟合，因此对于生成的决策树必须要进行剪枝。剪枝的算法有非常多，C4.5的剪枝方法有优化的空间。
• 2. C4.5生成的是多叉树，即一个父节点可以有多个节点。很多时候，在计算机中二叉树模型会比多叉树运算效率高。如果采用二叉树，可以提高效率。
• 3. C4.5只能用于分类，如果能将决策树用于回归的话可以扩大它的使用范围
• 4. C4.5由于使用了熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算。如果能够加以模型简化可以减少运算强度但又不牺牲太多准确性的话，那就更好了

这4个问题在CART树里面部分加以了改进

3.2.4. 基尼指数 ^目录

CART分类树建立算法的具体流程 ^目录

算法输入是训练集D，基尼系数的阈值，样本个数阈值

• 1. 对于当前节点的数据集为D，如果样本个数小于阈值或者没有特征，则返回决策子树，当前节点停止递归。
• 2. 计算样本集D的基尼系数，如果基尼系数小于阈值，则返回决策树子树，当前节点停止递归。
• 3. 计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数，对于离散值和连续值的处理方法和基尼系数的计算见第二节。缺失值的处理方法和上篇的C4.5算法里描述的相同。
• 4. 在计算出来的各个特征的各个特征值对数据集D的基尼系数中，选择基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值，把数据集划分成两部分D1和D2，同时建立当前节点的左右节点，做节点的数据集D为D1，右节点的数据集D为D2.
• 5. 对左右的子节点递归的调用1-4步，生成决策树。

CART回归树 ^目录

CART决策树与回归树的区别：

两者的区别在于样本输出，如果样本输出是离散值，那么这是一颗分类树。如果果样本输出是连续值，那么那么这是一颗回归树。

除了概念的不同，CART回归树和CART分类树的建立和预测的区别主要有下面两点：

1. 连续值的处理方法不同

2. 决策树建立后做预测的方式不同

• 连续值的处理

CART分类树采用的是用基尼系数的大小来度量特征的各个划分点的优劣情况。这比较适合分类模型

但是对于回归模型，我们使用了常见的和方差的度量方式，CART回归树的度量目标是，对于任意划分特征A，对应的任意划分点s两边划分成的数据集D1和D2，求出使D1和D2各自集合的均方差最小，同时D1和D2的均方差之和最小所对应的特征和特征值划分点

• 预测的方式

对于决策树建立后做预测的方式，上面讲到了CART分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别，它采用的是用最终叶子的均值或者中位数来预测输出结果

3.3. 剪枝处理 ^目录

3.3.1. 预剪枝 ^目录

3.3.2. 后剪枝 ^目录

3.3.3. CART决策树的剪枝 ^目录

对CART树进行剪枝，类似于线性回归的正则化，来增加决策树的泛化能力

CART采用的办法是后剪枝法，即先生成决策树，然后产生所有可能的剪枝后的CART树，然后使用交叉验证来检验各种剪枝的效果，选择泛化能力最好的剪枝策略

首先，我们看看剪枝的损失函数度量

在剪枝的过程中，对于任意的一刻子树T,其损失函数为：

C_α(T_t)=C(T_t)+α|T_t|

其中，α为正则化参数，这和线性回归的正则化一样。C(Tt)为训练数据的预测误差，分类树是用基尼系数度量，回归树是均方差度量。|Tt|是子树T的叶子节点的数量

当α=0时，即没有正则化，原始的生成的CART树即为最优子树。当α=∞时，即正则化强度达到最大，此时由原始的生成的CART树的根节点组成的单节点树为最优子树。当然，这是两种极端情况。一般来说，α越大，则剪枝剪的越厉害，生成的最优子树相比原生决策树就越偏小。对于固定的α，一定存在使损失函数Cα(T)最小的唯一子树

剪枝的思路

对于位于节点t的任意一颗子树Tt，如果没有剪枝，它的损失是

C_α(T_t)=C(T_t)+α|T_t|

如果将其剪掉，仅仅保留根节点，则损失是

C_α(T)=C(T)+α

当α=0或者α很小时，Cα(Tt)<Cα(T) , 当α增大到一定的程度时

C_α(T_t)=C_α(T)

当α继续增大时不等式反向，也就是说，如果满足下式：

Tt和T有相同的损失函数，但是T节点更少，因此可以对子树Tt进行剪枝，也就是将它的子节点全部剪掉，变为一个叶子节点T

最后，我们看看CART树的交叉验证策略

可以计算出每个子树是否剪枝的阈值α，如果我们把所有的节点是否剪枝的值α都计算出来

然后分别针对不同的α所对应的剪枝后的最优子树做交叉验证。这样就可以选择一个最好的α，有了这个α，我们就可以用对应的最优子树作为最终结果。

CART树的剪枝算法过程

输入是CART树建立算法得到的原始决策树T

输出是最优决策子树Tα

• 1. 初始化α_min=∞， 最优子树集合ω={T}
• 2. 从叶子节点开始自下而上计算各内部节点 t 的训练误差损失函数 C_α(T_t)（回归树为均方差，分类树为基尼系数）， 叶子节点数|Tt|，以及正则化阈值α=min{C(T)−C(Tt)|Tt|−1,αmin}， 更新α_min=α
• 3. 得到所有节点的α值的集合M
• 4. 从M中选择最大的值αk，自上而下的访问子树t的内部节点，如果C(T)−C(Tt)/|Tt|−1≤αk时，进行剪枝。并决定叶节点t的值。如果是分类树，则是概率最高的类别，如果是回归树，则是所有样本输出的均值。这样得到αk对应的最优子树Tk
• 5. 最优子树集合ω=ω∪Tk， M=M−{αk}
• 6. 如果M不为空，则回到步骤4。否则就已经得到了所有的可选最优子树集合ω
• 7. 采用交叉验证在ω选择最优子树Tα

3.4. 连续与缺失值 ^目录

3.4.1. 连续值处理 ^目录

3.4.2. 缺失值处理 ^目录

3.4.2.1. 问题(1)划分属性选择 ^目录

3.4.2.2. 问题(2)属性值缺失样本的划分 ^目录

4. 支持向量机 ^目录

4.1. 支持向量机与优化目标 ^目录

4.2. 用对偶问题解SVM优化目标 ^目录

4.2.1. 对偶问题 ^目录

4.2.2. 用SMO法解对偶问题 ^目录

4.2.3. 基于对偶问题的解得到最终解 ^目录

假设我们有S个支持向量，则对应我们求出S个b^∗,理论上这些b^∗都可以作为最终的结果， 但是我们一般采用一种更健壮的办法，即求出所有支持向量所对应的b^∗_s，然后将其平均值作为最后的结果

4.3. 解决非线性可分问题：核函数 ^目录

4.3.1. 非线性可分问题及解决策略：高维映射 ^目录

4.3.2. 解决高维映射带来的计算问题：构造核函数 ^目录

4.3.2.1. 核函数实现高效计算的例子 ^目录

4.3.3. 如何构造核函数 ^目录

4.4. 软间隔与正则化 ^目录

4.4.1. 引入软间隔 ^目录

有时候本来数据的确是可分的，也就是说可以用 线性分类SVM的学习方法来求解，但是却因为混入了异常点，导致不能线性可分，比如下图，本来数据是可以按下面的实线来做超平面分离的，可以由于一个橙色和一个蓝色的异常点导致我们没法按照线性支持向量机中的方法来分类

另外一种情况没有这么糟糕到不可分，但是会严重影响我们模型的泛化预测效果，比如下图，本来如果我们不考虑异常点，SVM的超平面应该是下图中的红色线所示，但是由于有一个蓝色的异常点，导致我们学习到的超平面是下图中的粗虚线所示，这样会严重影响我们的分类模型预测效果。

4.4.2. 原始0/1损失函数与替代损失函数 ^目录

4.4.3. 基于hinge损失的常用“软间隔SVM” ^目录

4.4.4. 不同软间隔SVM的共性 ^目录

4.5. 支持向量回归（SVR） ^目录

4.5.1. SVR的基本思想 ^目录

4.5.2. SVR的优化目标与求解 ^目录

5. 贝叶斯分类器 ^目录

5.1. 贝叶斯决策论 ^目录

5.2. 最小化分类错误率 ^目录

5.3. 如何获得后验概率P(c|x)？ ^目录

5.3.1. 判别式模型与生成式模型 ^目录

5.3.2. 估计类条件概率：极大似然估计 ^目录

5.4. 朴素贝叶斯分类器 ^目录

5.4.1. 什么是朴素贝叶斯分类器？ ^目录

5.4.2. 如何训练？ ^目录

5.4.3. 数据平滑：Laplacian修正 ^目录

5.5. 半朴素贝叶斯分类器 ^目录

5.6. 贝叶斯网 ^目录

5.6.1. 结构 ^目录

5.6.2. 学习 ^目录

5.6.3. 推断：吉布斯采样 ^目录

5.7. EM算法 ^目录

6. 神经网络 ^目录

6.1. 神经元模型 ^目录

6.2. 感知机和多次网络 ^目录

6.3. 神经网络学习：BP算法 ^目录

BP算法（error BackPropagation， BP)，误差反向传播算法

6.3.1. 标准BP算法 ^目录

6.3.2. 累积BP算法 ^目录

6.3.3. 过拟合与解决方案 ^目录

6.4. 全局最小与全局极小 ^目录

---

参考资料：

(1) 周志华《机器学习》

(2) 刘建平Pinard系列博客