读书笔记-机器学习实战

虽然想要做的事情太多，但是还是要踏踏实实的学，近来准备把几本书陆陆续续都看完，但是如果只是看的话，实在是容易走神，所以打算看书也用记笔记的形式好了，这里的笔记不会很详细，大都只是对个人认为重要的章节的一点总结和记录。

今天准备开始看的这本书叫《机器学习实战》，之前看过一遍西瓜书，所以这本书应该不会花很长时间。

第一部分 分类

第一章 机器学习基础

1.1 何谓机器学习

简单地说，机器学习就是把无序的数据转换成有用的信息。

第二章 k-近邻算法

2.1 k-近邻算法概述

简单地说，k-近邻算法采用测量不同特征值之间的距离方法进行分类。

优点：精度高、对异常值不敏感、无数据输入假定。
缺点：计算复杂度高、空间复杂度高。
使用数据范围：数值型和标称型。

一般流程：

收集数据：任何方法。
准备数据：计算距离所需要的数值，最好是结构化的数据格式。
分析数据：任何方法。
训练算法：不适合该分类方法。
测试算法：计算错误率。
使用算法：判断离哪个分类更近。

2.4 本章小结

k-近邻算法是最简单最有效的算法，它是基于实例的学习，使用算法时我们必须有接近实际数据的训练样本数据。k-近邻算法必须保存全部数据集，如果训练数据及很大，必须使用大量的存储空间。此外，由于必须对每个数据计算距离值，实际使用时可能非常耗时。
一个缺陷是它无法给出任何数据的基础结构信息，因此我们也无法知晓平均实例样本和典型实例样本具有什么特征。

第三章 决策树

3.1 决策树的构造

优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
缺点：可能会产生过度匹配问题。
适用数据类型：数值型和标称型。

要构建决策树，第一个要解决的问题就是当前数据集上，哪个特征在划分数据分类时起决定性作用，所以要评估每个特征。如果某个分支下的数据都属于同一类型，就无需再分，否则就要再分。

一般流程：

收集数据：任何方法。
准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化。
分析数据：任何方法，但构造完成后，应该检查图形是否符合预期。
训练算法：构造树的数据结构。
测试算法：使用经验树计算错误率。
使用算法：可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。

3.1.1 信息增益

划分数据集的大原则是：将无序的数据变得更加有序。我们可以在划分数据之前使用信息论量化度量信息的内容。
在划分数据集前后信息发生的变化称为信息增益，通过计算每个特征值划分数据集获得的信息增益，最高的那个就是最好的选择。

熵定义为信息的期望值，其中对于信息来说，如果待分类的事务可能划分在多个分类之中，则符号$x_{i}$的信息定义为：

$$l\left(x_{i}\right)=-\log _{2} p\left(x_{i}\right)$$

其中$p\left(x_{i}\right)$是选择该分类的概率。
为了计算熵，就需要计算所有类别所有可能值包含的信息期望值，通过下面的公式得到：

$$H=-\sum_{i=1}^{n} p\left(x_{i}\right) \log _{2} p\left(x_{i}\right)$$

其中$n$是分类的数目。
这里有个链接通俗理解决策树算法中的信息增益，能稍微帮助理解，主要就是选择一个特征，计算选择这个特征的各选择概率与最后的结果的关联程度，选择最小的那个，就能最大程度的减少不确定度，就可以得到最佳的选择。

3.1.2 划分数据集

遍历整个数据集，循环计算香农熵和splitDataSet()函数，找到最好的特征划分方式。

3.1.3 递归构建决策树

得到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，之后可以再划分，递归结束的条件：程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类

3.2 在Python中使用Matplotlib注释绘制树形图

决策树最重要的优点就是直观易于理解，但是要绘制光靠 Python 是不够的。所以

3.4 示例：使用决策树预测隐形眼镜类型

这是一个很经典的数据集，然而画出来的匹配选项太多了，称之为过度匹配，为了减少该问题，可以裁剪决策树，去掉不必要的叶子结点，如果叶子结点只能增加少许信息，则可以删除该结点，并到其它子节点里面。

3.5 本章小结

决策树分类器就像带有终止块的流程图，终止块表示分类结果。首先需要测量集合中数据的不一致性，也就是熵，然后寻找最优方案划分数据集，直到数据集中的所有数据属于同一分类(ID3算法)。
使用 Matplotlib 的注解功能，可以将储存的树结构(用 pickle 存储)转化为容易理解的图形，然而某些例子表明决策树可能会产生过多的数据集划分，从而产生过度匹配数据集的问题，所以可以通过裁剪决策树，合并相邻的无法产生大量信息增益的叶节点，从而消除过度匹配问题。

第四章 基于概率论的分类方法：朴素贝叶斯

因为分类器有时会产生错误结果，所以可以要求分类器给出一个最优的类别猜测结果，同时给出这个猜测的概率估计值。

4.1 基于贝叶斯决策理论的分类方法

朴素贝叶斯

优点：在数据较少的情况下仍然有效，可以处理多类别问题。
缺点：对于输入数据的准备方式较为敏感。
适用数据类型：标称型数据。

选择高概率对应的类别，这就是贝叶斯决策理论的核心思想，即选择具有最高概率的决策。

对于上图来说，可以使用以下方法：

(1) kNN，进行1000次距离计算。
(2) 决策树，分别沿着x轴，y轴划分数据。
(3) 计算数据点属于每个类别的概率，并进行比较。

(1)计算量大，(2)不会很成功。

4.2 条件概率

最重要的就是贝叶斯准则：

$$p(c | x)=\frac{p(x | c) p(c)}{p(x)}$$

4.3 使用条件概率来分类

真正要比较的是$p\left(c_{1} | x, y\right)$和$p\left(c_{2} | x, y\right)$，即，对于一个数据点，来自各个类别的概率分别是多少。
这可以用贝叶斯准则得到：

$$p\left(c_{i} | x, y\right)=\frac{p\left(x, y | c_{i}\right) p\left(c_{i}\right)}{p(x, y)}$$

使用贝叶斯准则，可以通过已知的三个概率值来计算未知的概率值。后面就可以利用以上公式计算概率。

4.4 使用朴素贝叶斯进行文档分类

一般流程：

收集数据：任何方法。
准备数据：需要数值型或布尔型数据。
分析数据：有大量特征时，绘制特征作用不大，此时使用直方图效果更好。
训练算法：计算不同的独立特征的条件概率。
测试算法：计算错误率。
使用算法：一个常见的朴素贝叶斯应用是文档分类。可以在任意的分类场景中使用朴素贝叶斯分类器，不一定非要是文本。

使用的特征数目增大，所需要的样本数也会随之增大。由统计学，若每个特征需要N个样本，那么对于10个特征就要$N^{10}$个样本。当然若特征之间相互独立，那么样本数可以从$N^{10}$减少到${10}*N$。这里的独立就是统计学的独立，就是假设单词A出现在单词B和单词C后面的概率相同，虽然不正确，但是这就是朴素一词的意思。
朴素贝叶斯分类器的另一个假设就是，每个特征同等重要，虽然这个假设也有问题，因为其实只要部分特征就能做出判断了。

4.5 使用Python进行文本分类

要从文本中获取特征，这些特征来自文本的词条(token)，一个词条是字符的任意组合，可以是单词，也可以是非单词词条。
首先获取词汇表，然后可以输出文档向量，每一元素为1或0，分别表示词汇表中的单词在输入文档中是否出现

4.5.2 训练方法：从词向量计算概率

如何从以上得到的一串数字中计算概率呢，可以重写贝叶斯准则：

$$p\left(c_{i} | w\right)=\frac{p\left(w | c_{i}\right) p\left(c_{i}\right)}{p(w)}$$

这里的w是一个向量，由多个数值组成(个数等于词汇表中的词个数)，这里用朴素贝叶斯假设，即特征相互独立，即可用$p\left(w_{0} | c_{1}\right) p\left(w_{1} | c_{1}\right) p\left(w_{2} | c_{1}\right) \dots p\left(w_{n} | c_{1}\right)$表示$\mathbf{p}\left(\mathbf{w}_{0}, w_{1}, w_{2}, \dots w_{n} | \mathbf{c}_{1}\right)$

4.5.3 测试算法：根据现实情况修改分类器

计算$p\left(w_{0} | c_{1}\right) p\left(w_{1} | c_{1}\right) p\left(w_{2} | c_{1}\right) \dots p\left(w_{n} | c_{1}\right)$时，若其中一个概率值为0，最后结果也为0了，为减低这种影响，可初始化为1，并将分母初始化为2。
另一问题是下溢出，因为太多很小的数相乘，所以会下溢出或得到不正确的答案。一种解决办法是对乘积取自然对数，而由于$f(x)$与$\ln (f(x))$在相同区域内同增同减，并在相同点上取到极值，它们虽然取值不同，但不影响最终结果。

4.8 本章小结

对于分类而言，使用概率要比硬规则更有效，而贝叶斯准则提供了一种利用已知值来估计未知概率的有效方法。
尽管条件独立性假设并不正确，但是朴素贝叶斯仍然是一种有效的分类器。

第五章 Logistic回归

从这一章开始，将接触到最优化算法。
而至于回归，假设现在有一些数据点，我们用一条直线对这些点进行拟合（该线称为最佳拟合直线），这个拟合过程就称作回归。
而利用 Logistic 回归进行分类的主要思想即：根据现有数据对分类边界线建立回归公式，以此进行分类。这里的回归源于最佳拟合，表示要找到最佳拟合参数集。

一般流程：

收集数据：采用任意方法收集数据。
准备数据：由于需要进行距离计算，因此要求数据类型为数值型。且结构化数据格式则最佳。
分析数据：采用任意方法对数据进行分析。
训练算法：大部分时间将用于训练，目的是为了找到最佳的分类回归系数。
测试算法：一旦训练步骤完成，分类将会很快。
使用算法：首先，需要输入一些数据，并将其转换成对应的结构化数值；接着基于训练好的回归系数就可以对这些数值进行简单的回归计算，判定它们属于哪个类别；在这之后，我们就可以在输出的类别上做一些其他分析工作。

5.1 基于 Logistic 回归和 Sigmoid 函数的分类

Logistic 回归

优点：计算代价不高，易于理解和实现。
缺点：容易欠拟合，分类精度可能不高。
使用数据类型：数值型和标称型数据。

需要的函数是，能接受所有的输入，然后预测出类别(eg. 两个类)，输出0或1，比如海维赛德阶跃函数(单位阶跃函数)，但是若在跳跃点直接从0跳到1，这不太好处理，所以可以用 Sigmoid 函数：

$$\sigma(z)=\frac{1}{1+\mathrm{e}^{-z}}$$

其特性如下所示：

确定了分类器的函数形式后，就要确定最佳回归系数了。

5.2 基于最优化方法的最佳回归系数确定

记 Sigmoid 函数的输入记为z，可由以下公式得出：

$$z=w_{0} x_{0}+w_{1} x_{1}+w_{2} x_{2}+\cdots+w_{n} x_{n}$$

如果用向量的写法，就可以为$z=w^{T} x$，其中x为分类器的输入数据，向量w就是要找的最佳参数。

5.2.1 梯度上升法

主要思想：要找到某函数的最大值，最好的方法是沿着该函数的梯度方向探寻。若梯度记为$\nabla$，则函数$f(x, y)$的梯度可为：

$$\nabla f(x, y)=\left(\begin{array}{c}{\frac{\partial f(x, y)}{\partial x}} \\ {\frac{\partial f(x, y)}{\partial y}}\end{array}\right)$$

这个梯度的意思就是要沿着x的方向移动$\frac{\partial f(x, y)}{\partial x}$，沿y的方向移动$\frac{\partial f(x, y)}{\partial y}$。其中函数$f(x, y)$必须要在待计算的点上有定义并且可微：

可由上图发现，梯度算子总是指向函数值增长最快的方向，而至于移动量的大小，该量值称为步长，记做$\alpha$。用向量来表示，即梯度算法的迭代公式如下：

$$w=w+a \nabla_{w} f(w)$$

一直执行迭代，直到某个停止条件为止，比如迭代数达到某个指定值或算法达到某个可以允许的误差范围。

至于梯度下降算法：
相反是用来求函数的最小值，$w=w-a \nabla_{w} f(w)$

5.2.2 训练算法：使用梯度上升找到最佳参数

伪代码如下：

每个回归系数初始化为1
重复R次：
计算整个数据集的梯度
使用alpha * gradient更新回归系数的向量
返回回归系数

5.2.4 训练算法：随机梯度上升

由已知，梯度上升算法在每次更新回归系数时，都需要遍历整个数据集，这在数据集很大时，太不现实了，其中一种改进方法是一次仅用一个样本点来更新回归系数，称为随机梯度上升算法。这样的话，可以在新样本到来时对分类器进行增量式更新，因此随机梯度上升算法是一个在线学习算法。与之对应，一次处理所有数据被称为是“批处理”。
随机梯度上升算法：

所有回归系数初始化为1
对数据集中每个样本
计算该样本的梯度
使用α*gradient更新回归系数值
返回回归系数值
迭代过程中，局部系数的变化如下所示：

有些系数很快收敛，有些不是，且大的波动停止后，还有一些小的周期性波动，显然，因为数据集并非线性可分，有一些不能正确分类的样本点，所以每次迭代时会引发系数的剧烈改变。

所以有了改进的随机梯度上升算法：

一方面，α 在每次迭代的时候都会调整（由迭代次数，样本下标决定），这能减少高配波动。

$$\alpha = 4/(1.0+3+i)+0.01$$

虽然 α 在减少，但是始终在一个阈值之上，来保证在多次迭代之后，新数据仍有一定的影响。
另一方面，通过随机选取样本来更新回归函数，这将减少周期性的波动

5.4 本章小结

Logistic 回归的目的是找到一个非线性的函数 Sigmoid 的最佳拟合函数，求解时，可以用最优化算法来完成，其中最常用的是梯度上升算法，而它又可以简化为随机梯度上升算法。其效果相当，但是占用更少资源，且其为一个在线算法，可以在新数据到来时就完成参数更新。

第六章 支持向量机(support vector machines)

有些人认为，SVM是最好的现成的分类器，因为它不加修改即可直接使用。同时也意味着在数据上应用基本形式的SVM分类器就可以得到低错误率的结果。对训练集之外的数据点做出很好的分类决策。

6.1 基于最大间隔分割数据

优点：泛化错误率低，计算开销不大，结果易解释。
缺点：对参数调节和核函数的选择敏感，原始分类器不加修改仅适用于处理二类问题。
适用数据类型：数值型和标称型数据。

将数据集分隔开的直线称为分割超平面，当然，这是由于数据点都在二维平面上，若数据集是1024维，就需要一个1023维的某某对象来对数据进行分割。该对象就是超平面(hyperplane)，就是分类的决策界面。
现在就是基于这样的方式来构建分类器，即若数据点离决策边界越远，则其预测结果就越可信。

由上图，三条直线都能将它分开，但是哪个最好呢，但是如果用最小化数据点到分割超平面的平均距离，这就又和寻找最佳拟合直线一样了，但这并不是最佳方案，这里希望找到离分割超平面最近的点，确保它们离分割面的距离尽可能远，这个距离被称为间隔(margin)。目的就是间隔尽可能大。
支持向量(support vector)，就是离分割超平面最近的那些点，那么接下来就要试着最大化支持向量到分割面的距离。

6.2 寻找最大间隔

由已知分割超平面可以写为$w^{T} \mathbf{x}+b$，b就是截距，所以向量w和常数b就一起描述了所给数据的分割线或超平面。

6.2.1 分类器求解的优化问题

与 Logistic 回归不同，它使用海维赛德阶跃函数的函数来处理，当u<0，f(u)输出-1，反之输出+1，而不是0或1，这样方便处理（用label * $w^{T} \mathbf{x}+b$来计算）。
现在的目标就是找出分类器定义中的w和b，所以要找到具有最小间隔的数据点，即支持向量，一旦找到了，就需要对该间隔最大化:

$$\arg \max _{w, b}\left\{\min _{n}\left(\operatorname{label} \cdot\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b\right)\right) \cdot \frac{1}{\|\boldsymbol{w}\|}\right\}$$

而为了最大化以上公式，可以是固定其中一个因子而最大化其他因子。比如令所有支持向量的
label × $w^{T} \mathbf{x}+b$都为1，但是这不太现实，所以可以给定一些约束条件然后求最优值，所以是一个带约束条件的优化问题，这里的约束条件就是label × $w^{T} \mathbf{x}+b \geqslant 1.0$，对于这类优化问题，可引入拉格朗日乘子，由于这里的约束条件都是基于数据点的，因此我们可以将超平面写成数据点的形式：

$$\max _{\alpha}\left[\sum_{i=1}^{m} \alpha-\frac{1}{2} \sum_{i, j=1}^{m} \operatorname{label}^{(i)} \cdot \operatorname{label}^{(j)} \cdot a_{i} \cdot a_{j}\left\langle x^{(i)}, x^{(j)}\right\rangle\right]$$

尖括号表示两个向量的内积。
约束条件为：

$$\alpha \geqslant 0, \sum_{i=1}^{m} \alpha_{i} \cdot \operatorname{label}^{(i)}=0$$

但是以上方程有一个假设：数据必须100%线性可分，但是这也是不可能的，这时就要引入松弛变量(slack variable)，来允许部分数据点错误，这时变为

$$C \geqslant \alpha \geqslant 0, \sum_{i=1}^{m} \alpha_{i} \cdot \operatorname{label}^{(i)}=0$$

常数C用于控制“最大化间隔”及“保证大部分点的函数间隔小于1.0”这两个目标的权重。

6.2.2 SVM应用的一般框架

SVM的一般流程：

收集数据：任意方法。
准备数据：需要数值型数据。
分析数据：有助于可视化分隔超平面。
训练算法：SVM的大部分时间都源自训练，该过程主要实现两个参数的调优。
测试算法：十分简单的计算过程就可以实现。
使用算法：几乎所有分类问题都可以使用SVM，其实它本身是一个二类分类器，对多类问题应用SVM需要对代码做一些修改。

6.3 SMO高效优化算法

现在的目的是对上面提出的两个公式进行优化：最小化的目标函数和在优化过程中必须遵循的约束条件。

6.3.1 Platt的SMO算法

SMO表示序列最优化(Squential Minimal Optimization)，而 Platt 的 SMO 算法是将大优化问题分解为多个小优化问题来求解，其结果不变且小优化问题往往很容易求解。
SMO 算法的目标是求出一些列 α 和 b，一旦求出来就很容易求出权重向量w，进而得到分割超平面。
工作原理即：每次循环中选择两个 α 进行优化处理，一旦找到“合适”的 α，就同时增大一个减小另一个，而“合适”就是指两个 α 必须满足一定的条件，条件之一就是这两个 α 必须要在间隔边界之外，而第二个条件就是这两个 α 还没有进行过区间化处理或者不在边界上。
之所以会出现要同时改变两个 α 的情况，是因为 α 之间要满足以下条件：

$$\sum_{i=1}^{m} \alpha_{i} \cdot \operatorname{label}^{(i)}=0$$

只改变一个 α 会导致条件失效，所以需要同时改变两个 α，

6.5 在复杂数据上应用核函数

如下图所示：

它描述了非线性可分的情况，显然该数据中存在某种可以识别的模式，但是能否像线性情况一样，利用工具来捕捉数据中的这种模式，这里的工具就是核函数(kernel)，它能将数据转换成易于分类器理解的形式。

6.5.1 利用核函数将数据映射到高维空间

对于分类器而言，它只能识别分类器的结果是大于0还是小于0，如果只是在x和y轴构成的坐标系中插入直线进行分类的话，不会得到理想的结果，所以或许可以对圆中的数据进行某种形式的转换，即从一个特征空间到另一个特征空间的映射，通常是将低维特征空间映射到高维空间。
SVM 优化的一个特点就是，所有的运算都可以写成内积(inner product)，即点积，可以将内积运算替换成核函数，而不必做简化处理。

6.5.2 径向基和函数

这是一个采用向量作为自变量的函数，能后基于向量距离运算输出一个标量，这个距离可以是从<0,0>向量或者其他向量还是计算的距离。其高斯版本的具体公式为：

$$k(x, y)=\exp \left(\frac{-\|x-y\|^{2}}{2 \sigma^{2}}\right)$$

其中，$\sigma$是用户定义的用于确定达到率(函数值跌落到0的速度参数)。
上述高斯核函数将数据从其特征空间映射到更高维(无穷维)的空间，

6.7 本章小结

支持向量机是一种分类器，会产生一个二值决策结果，所以说是一种决策“机”。支持向量机的泛化错误率较低，即具有良好的学习能力，且学习到的结果具有很好的推广性。
其实求解过程可以类似求解一个二次优化问题，即求解凸二次规划的最优化算法，

第七章 利用AdaBoost元算法提高分类性能

既然已经介绍了这么多算法了，那么怎么将这些算法组合到一起，就涉及到元算法(meg-algorithm)-对其他算法进行组合的一种方式，本章就集中于一个很流行的元算法- AdaBoost。

7.1 基于数据集多重抽样的分类器

元算法也可以叫集成方法：可以是不同算法的集成，也可以是同一算法，也可以是同一算法在不同算法在不同设置下的集成，还可以是数据集不同部分分配给不同分类器之后的集成。

AdaBoost

优点：泛化错误率低，易编码，可以应用在大部分分类器上，无参数调整。
缺点：对离群点敏感。
适用数据类型：数值型和标称型数据。

7.1.1 bagging：基于数据随机重采样的分类器构建方法

Bagging 也可以叫作自举汇聚法(bootstrap aggregating)，在从原始数据集选择S次后得到S个新数据集的一种技术。新数据集和原数据集的大小相等。其中每个数据集都是通过在原始数据集中随机选择一个样本来进行替换而得到的。替换是可以多次选择同一样本：新数据集中可以有重复的值，而某些值不会出现。
在S个数据集建好后，用某个学习算法分别作用于每个数据集记得到了S个分类器，用的时候就可以得到S个结果，最后选用最多的类别作为最后的分类结果。
更先进的 bagging 方法，比如随机森林(random forest)。

7.1.2 boosting

与 bagging 类似，它们所使用的多个分类器的类型都是一致的，但是在 bagging 当中，不同的分类器是通过串行训练获得的，每个新分类器都根据已训练出来的分类器的性能来进行训练，但是 boosting 是通过集中关注被已有分类器错分的那些数据来获得新的分类器。
另外 bagging 分类器权重是相等的，但是 bagging 的分类器权重并不相等，是所有分类器的加权求和结果的，每个权重代表的是其对应分类器在上一轮迭代中的成功度。
本章集中于 AdaBoost。

AdaBoost 的一般流程

收集数据：任何方法。
准备数据：依赖于所使用的弱分类器类型，本章使用了单层决策树，可以处理任何数据类型，当然也可以用任何分类器作为弱分类器(简单分类器的效果更好)。
分析数据：可使用任何方法。
训练算法：AdaBoost 的大部分时间都用在训练上，分类器将多次在同一数据集上训练弱分类器。
测试算法：计算分类的错误率。
使用算法：同SVM一样，AdaBoost 预测两个类别中的一个。要预测多个类别，也需要像多类SVM那样进行修改。

7.2 训练算法：基于错误提升分类器的性能

如何用弱分类器和多个实例构建一个强分类器？
弱：比随机猜测略好，但是不会好太多(总之大于50%)，而“强”分类器的错误率将会低很多。

AdaBoost (adaptive boosting)，自适应boosting，训练数据中的每个样本，并赋予其一个权重，这些权重构成了向量$D$，并初始化成相等值。
首先在训练数据上训练出一个弱分类器并计算该分类器的错误率，然后在同一数据集上再次训练弱分类器。
而在第二次训练中，将会重新调整每个样本的权重，其中第一次分对的权重的权重将会降低，分错的权重将会提高。
AdaBoost 为每个分类器都分配了一个权重值 alpha，基于每个弱分类器的错误率进行计算的。错误率$\boldsymbol{\varepsilon}$的定义如下：

$$\boldsymbol{\varepsilon}=\frac{未正确分类的样本数目}{所有样本数目}$$

而 alpha 的计算公式如下：

$$\alpha=\frac{1}{2} \ln \left(\frac{1-\varepsilon}{\varepsilon}\right)$$

若某个样本被正确分类，其权重更改为：

$$D_{i}^{(t+1)}=\frac{D_{i}^{(t)} \mathrm{e}^{-\alpha}}{\operatorname{Sum}(D)}$$

若某个样本被错误分类，其权重更改为：

$$D_{i}^{(t+1)}=\frac{D_{i}^{(t)} \mathrm{e}^{\alpha}}{\operatorname{Sum}(D)}$$

一直到错误率为0或者弱分类器的数目达到用户的指定值为止。

7.3 基于单层决策树构建弱分类器

单层决策树(decision stump 决策树桩)，因为它只有一个分裂过程。

7.7 非均衡分类问题

本书之前谈论的例子都是理论上的分类情况，但是实际上的分类比这个要复杂许多，这体现在大多数情况下不同类别的分类代价并不相等，有时候情愿选择A，都不会尽量不会选择B。

7.7.1 其他分类性能度量指标：正确率、召回率及ROC曲线

有时候不能只基于错误率来衡量分类器任务的成功程度的。
错误率：在所有测试样例中错分的样例比例。但是这种度量掩盖了样例如何被分错的事实，要解决这样的问题可以考虑使用混淆阶矩阵(confusion matrix)：

这样很好地显示了其中的错误。

以二分类为例：
在分类时，当某些类别的重要性高于其他类别，就可以定义一些其它的新的指标：
正确率(precision)：等于TP/(TP+FP)，给出的是预测为正例的样本中的真正正例的比例。
召回率(recall)：等于TP/(TP+FN)，给出的是预测为正例的真正正例占所有真实正例的比例。
（这两者都很好实现，但是要构建一个这两个指标都很高的分类器，就很难了。）
ROC曲线(ROC curve)：代表接受者操作特征(receiver operating characteristic)，如下所示：

其中横轴是伪正例的比例(FP/(FP+TN))，而纵轴是真正例的比例(TP/(TP+FN))，所以ROC曲线给出的是当阈值变化时，伪正率和真正率的变化情况。
ROC曲线不但可以用于比较分类器，还可以基于成本效益(cost-versus-benefit)分析来做出决策。理想状态下，最佳的分类器应该尽可能在于左上角。
为了画出ROC曲线，分类器必须提供每个样例被判为阳性或者阴性的可信程度值，朴素贝叶斯可以这么做，首先要将分类样例按照其预测强度排序，先从排名最低的样例开始，所有排名更低的样例都被判为反例，而所有排名更高的样例都被判为正例。然后，将其移到排名次低的样例中去，如果该样例属于正例，则修改真阳率，反之，修改假阳率。

7.7.2 基于代价函数的分类器决策控制

像如下的代价矩阵(代价不是0就是1)：

可以基于第一张表的矩阵计算总代价：TP0 + FN\1 + FP*1 + TN*0，第二张表为：TP*(-5) + FN*1 + FP*50 + TN*0，这两张表是不一样的。同样的，这两种正确分类所获得的收益也不一样。根据这些代价值就可以训练对应的分类器。
相同的，在AdaBoost中，也可以基于代价函数来调整错误权重向量$D$。在朴素贝叶斯中，也可以选择具有最小期望代价而不是最大概率的类别作为最后的结果。在SVM中，可以在代价函数中对于不同的类别选择不同的参数c。

7.7.3 处理非均衡问题的数据抽样方式

这主要是对于分类器的训练数据进行改造。分为欠抽样(undersampling)和过抽样(oversampling)，过抽样意味着复制样例，欠抽样则指删除样例。
比如在正例类别属于罕见类别，就要对反例进行欠抽样处理。但是不能确定用哪些样例进行剔除，因为在选择剔除的样例中可能携带了剩余样例中并不包含的有价值信息。

7.8 本章小结

除了将同一类分类器集成到一起，也可以将多种分类器组合。
多个分类器组合可能会进一步凸显出单分类器的不足，比如过拟合。且如果分类器之间差别显著，则多个分类器组合就可能缓解这一问题。分类器之间的差别可以是算法本身或者是应用于算法上的数据的不同。

第二部分 利用回归预测数值型数据

第八章 预测数值型数据：回归

分类的目标变量是标称型数据，而本章的目标变量将是连续型的数据。

8.1 用线性回归找到最佳拟合直线

优点：结果易于理解，计算上不复杂。
缺点：对非线性的数据拟合不好。
适用数据类型：数值型和标称型数据。

回归的目的是预测数值型的目标值。比如直接写出一个目标值的计算公式。这就是回归方程(regression equation)，其中的参数就是回归系数(regression weights)，求这些回归系数的过程就是回归。(这里的回归一般都是线性回归(linear regression))。

回归的一般方法：

收集数据：采用任意方法收集数据。
准备数据：回归需要数值型数据，标称型数据将被转成二值型数据。
分析数据：绘出数据的可视化二维图将有助于对数据做出理解和分析。
训练算法：找到回归系数。
测试算法：使用R2或者预测值和数据的拟合度，来分析模型的效果。
使用算法：使用回归，可在给定输入的时候预测出一个数值，这是一种提升，因为这可以预测连续型数据而不仅仅是离散的类别标签。

预测结果通过$Y_{1}=X_{1}^{T} w$给出，目的就是根据x和对应的y，找到w。常用的方法就是找出使误差最小的w，误差是通过平方误差求出的：

$$\sum_{i=1}^{m}\left(y_{i}-x_{i}^{\tau} w\right)^{2}$$

用矩阵表示可为$(\mathrm{y}-\mathrm{X} \mathrm{w})^{\mathrm{T}}(\mathrm{y}-\mathrm{X} \mathrm{w})$，如果对w求导，得到$\mathbf{x}^{\T}(\mathbf{Y}-\mathbf{x} \mathbf{w})$，令其为零，解出：

$$\hat{w}=\left(\boldsymbol{X}^{\top} \boldsymbol{X}\right)^{-1} \boldsymbol{X}^{\top} y$$

最佳拟合直线方法将数据视为直线进行建模，表现很好，但是若数据还存在其他的模式，就需要进行局部调整了。

8.2 局部加权线性回归

线性回归的一个问题是有可能出现欠拟合现象，因为是利用最小均方误差的无偏估计。若欠拟合将不能取得最好的预测结果。所以有些方法允许在估计中引入一些偏差，从而降低预测的均方误差。
比如局部加权线性回归(Locally Weighted Linear Regression, LWLR)，即给待遇测点附近的每个点赋予一定的权重。在这个子集上基于最小均方差来进行普通的回归。与kNN一样，这种算法每次预测都需要事先选取出对应的数据子集。该算法解出回归系数w的形式如下：

$$\hat{w}=\left(\boldsymbol{X}^{\top} \boldsymbol{W X}\right)^{-1} \boldsymbol{X}^{\top} \boldsymbol{W} \boldsymbol{y}$$

LWLR使用“核”来对附近的点赋予更高的权重。核的类型可以自由选择，最常用的核就是高斯核，对应的权重如下：

$$w(i, i)=\exp \left(\frac{\left|x^{(i)}-x\right|}{-2 k^{2}}\right)$$

这样就构建了一个只含对角元素的权重矩阵w，并且点x和x(i)越近，w(i,i)将会越大。其中的参数k需要用户指定，它决定了对附近的点赋予多大的权重，权重k与权重的关系如下：

8.4 缩减系数来“理解”数据

若数据的特征比样本点还多应该怎么办？自然就不能再使用线性回归和之前的方法来做预测，因为在计算$\left(\mathbf{x}^{\mathrm{T}} \mathbf{X}\right)^{-1}$时会出错(求不出逆矩阵，因为特征比样本点多，输入数据的矩阵x不是满秩矩阵，非满秩矩阵在求逆时会出现问题)。
为了解决问题，出现了岭回归(ridge regression)。

8.4.1 岭回归

岭回归就是在矩阵$\mathbf{x}^{\mathrm{T}} \mathbf{x}$上加上一个$\lambda \mathbf{I}$，使它非奇异，进而能对$\mathbf{x}^{r} \mathbf{x}+\lambda \mathbf{I}$求逆。其中矩阵I是一个m*m的单位矩阵，回归系数的计算公式为：

$$\hat{w}=\left(\boldsymbol{X}^{\mathrm{T}} \boldsymbol{X}+\lambda \boldsymbol{I}\right)^{-1} \boldsymbol{X}^{\mathrm{T}} \boldsymbol{y}$$

这样的操作不仅能应付特征数更多的情况，也可以用于在估计中加入偏差，从而得到更好的估计。通过限制所有w之和，引入了惩罚项，能减少不重要的参数，即缩减(shrinkage)。
缩减能去掉不重要的参数，所以能去掉不重要的参数，而能更好地理解数据。
$\lambda$：数据获取后，先抽一部分数据用于测试，剩余的作为训练集用于训练参数w。训练完毕后在测试集上测试预测性能。通过选取不同的$\lambda$重复上述过程，最终得到一个使预测误差最小的$\lambda$。

8.4.2 lasso

如果增加如下约束：

$$\sum_{k=1}^{n} w_{k}^{2} \leqslant \lambda$$

普通的最小二乘法回归将会得到与岭回归一样的公式。这是因为上式限定了所有回归系数的平方和不能大于$\lambda$。使用普通的最小二乘法回归在当两个会更多的特征相关时，可能会得出一个很大的正(负)系数。使用上式则可以避免。
而lasso则用了以下限定：

$$\sum_{k=1}^{n}\left|w_{k}\right| \leqslant \lambda$$

区别在于用绝对值代替了平方和，结果却大相径庭：在$\lambda$足够小的时候，一些系数会因此被迫缩减到0，这能帮助更好地理解数据。

8.4.3 前向逐步回归

前向逐步回归算法比lasso更加简单，属于贪心算法，每一步都尽可能减少误差。所有的权重刚开始都设为1，然后每一步都是对某个权重增加或减少一个很小的值。然后如果得到更小的误差，则记录当前的w。
逐步线性回归的主要优点在于它可以帮助理解现有模型并做出改进。当构建了一个模型，可以运行该算法找出重要的特征，然后就能及时停止对不重要特征的收集。
用缩减方法(以上两种)时，模型虽然增加了偏差(bias)，与但是却减小了模型的方差。

8.5 权衡偏差与方差

当模型中的“噪声”或误差出现时，必须考虑其来源：比如对复杂的过程简化时产生，同样若无法理解数据产生的真实过程，也会导致差异，且在测量过程本身也可能产生“噪声”或问题。
以下是训练误差和测试误差的曲线图：

上面的曲线是测试误差，下面的曲线是训练误差。从左到右，核逐渐减少，训练误差将变小。

一般认为，上述两种误差由三个部分组成：偏差、测量误差和随机噪声。通过引入了三个越来越小的核来不断增大模型的方差。

如果随机选取两个样本集，分别训练得到一组回归系数，这些系数间的差异大小也就是模型方差大小的反映。

本章小结

虽然都是预测目标值，但是回归与分类的不同点在于，前者预测连续型变量，而后者预测离散型变量。
岭回归是缩减法的一种，相当于对回归系数的大小施加了限制。另一种方法是lasso，它难以求解，但是可以使用计算简便的逐步线性回归方法来求得近似结果。
缩减法在对一个模型增加偏差的同时能减少方差。将两者折中能帮助改进现有模型。

第九章 树回归

当数据拥有过多的特征且特征之间关系复杂时，构建全局模型就太难了，且实际生活的很多问题都是非线性的，不可能使用全局线性模型来拟合任何数据。
一种可行的方法是将数据集切分成很多份易建模的数据，然后利用线性回归技术来建模。但是如果首次切分后仍然难以拟合线性模型就继续切分。这时，树结构和回归法就相当有用了。

9.1 复杂数据的局部性建模

之前的决策树是一种贪心算法，它要在给定时间内做出最佳选择，但并不关心能否达到全局最优。

树回归：

优点：可以对复杂和非线性的数据建模。
缺点：结果不易理解。
使用数据类型：数值型和标称型数据。

之前的树构建算法是ID3，每次选取当前最佳的特征来分割数据，根据该特征的所有可能取值来切分。按某特征切分后，该特征在之后的算法执行过程中将不会再起作用。所以有观点认为这种切分方式过于迅速。另一种方法是二元切分法，每次把数据集切成两份，若数据的某特征值等于切分所要求的值，则这些数据进入左子树，反之进入右子树。
另外ID3还不能直接处理连续型特征，还必须将其转换成离散型，才能在ID3算法中使用。且显然这种转换过程会破坏连续型变量的内在性质。但是二元切分法反而易于对树构建过程进行调整以处理连续性特征：如果特征值大于给定值就走左子树，否则走右子树。
CART是树构建算法之一，使用二元切分来处理连续型变量。

树回归的一般方法：

收集数据：采用任意方法收集数据。
准备数据：需要数值型的数据，标称型数据要映射成二值型数据。
分析数据：绘出数据的二维可视图显示结果，以字典方式生成树。
训练算法：大部分时间都花费在叶节点树模型的构建上。
测试算法：使用测试数据上的R2值来分析模型的效果。
使用算法：使用训练出的树做预测。

9.2 连续和离散型特征的树的构建

代码里面使用一部字典来储存树的数据结构：

待切分的特征。
待切分的特征值。
右子树。当不再需要切分的时候，也可以是单个值。
左子树。同上。

9.3 将CART算法用于回归

如何切分数据？如何知道是否充分切分？
为了成功构建以分段常数为叶节点的树，需要度量出数据的一致性。之前使用树进行分类，会在给定节点时计算数据的混乱度。那么对于连续型数值的混乱度，首先要计算所有数据的均值，然后计算每条数据的值到均值的差值(用绝对值或平方值来代替差值)，但是不同的是这里是平方误差的总值(总方差)。

9.3.1 构建树

需要知道的是，找到最佳的二元切分方式，以及什么时候停止切分。
最佳切分：

对每个特征:
对每个特征值：
将数据集切分成两份
计算切分的误差
如果当前误差小于当前最小误差，那么将当前切分设定为最佳切分并更新最小误差
返回最佳切分的特征和阈值

最佳切分也就是使得切分后能达到最低误差的切分。若切分数据集后效果提升不够大，就不应进行切分操作而直接构建叶节点(根据用户设定的参数tolS：容许的误差下降值，用于控制函数的停止时机)。且还应该检查两个切分后的子集大小，若小于用户指定参数(tolN：切分的最少样本数)，也不应该切分。若这些提前终止条件都不满足，那么就返回切分特征和特征值，继续进行剪枝。

9.4 树剪枝

若树的节点过多，很显然就过拟合了，之前使用了测试集某种交叉验证技术来发现过拟合。
通过降低决策树的复杂度来避免过拟合的过程叫作剪枝，而构建树之前的提前终止条件其实也是在进行一种预剪枝。另一种则需要使用测试集和训练集，称为后剪枝。

9.4.1 预剪枝

树构建算法对于用户输入的两个参数非常敏感，但是，通过不断修改停止条件来得到合理结果并不是很好的办法。且用户也不好指定参数。

9.4.2 后剪枝

使用后剪枝方法需要将数据集分成测试集和训练集。首先指定参数，使得构建出的树足够大、足够复杂，便于剪枝。然后从上到下找到叶节点，用测试集来判断这些叶节点合并是否能降低测试误差，是的哈就合并。
伪代码如下：

基于已有的树切分测试数据：
如果存在任一子集是一棵树，则在该子集递归剪枝过程
计算将当前两个叶节点合并后的误差
计算不合并的误差
如果合并会降低误差的话，就将叶节点合并

9.5 模型树

用树来建模，除了把叶节点简单地设定为常数值之外，也可以把叶节点设定为分段线性函数，分段线性(piecewise linear)是指模型由多个线性片段组成。
如以下这个例子：

很显然，如果用两条直线拟合会比一组常数来建模好一些，可以分别设计两条从0.0~0.3、从0.3~1.0的直线，于是就可以得到两个线性模型。很显然，两条直线会比很多节点组成一棵大树更容易解释。
下一个问题就是，为了找到最佳切分，应该怎么计算误差？
对于给定的数据集，应该先用线性的模型来对它进行拟合，然后计算真实的目标值与模型预测值间的差值。最后将这些差值的平方求和就得到了所需的误差。

9.8 本章小结

对于有着复杂相互关系数据集来说，输入数据和目标变量之间呈现非线性关系，可用树来预测值分段，包括分段常数和分段直线。
CART算法可处理离散型数据或连续型数据，但是往往过于复杂，这时可以用剪枝技术来简化它。

第三部分 无监督学习

在无监督学习中，之前章节里面的目标变量事先并不存在，这里要知道的是，从数据X中能发现什么呢？

第十章 利用K-均值聚类算法对未标注数据分组

聚类是一种无监督的学习，它将相似的对象归到同一个簇中，像全自动分类，簇内的对象越相似，聚类的效果越好。

10.1 K-均值聚类算法

K-均值聚类

优点：容易实现。
缺点：可能收敛到局部最小值，在大规模数据集上收敛较慢。
适用数据类型：数值型数据。

K-均值是发现给定数据集的k个簇的算法。簇个数k是用户给定的，每一个簇通过其质心(centroid)，即簇中的所有点的中心来描述。
伪代码：

创建k个点作为起始质心(一般为随机选择)
当任意一个点的簇分配结果发生改变时
对数据集中的每个数据点
对每个质心
计算质心与数据点之间的距离
将数据点分配到距其最近的簇
对每一个簇，计算簇中所有点的均值并将均值作为质心

K-均值聚类的一般流程

收集数据：采用任意方法收集数据。
准备数据：需要数值型的数据来计算距离，也可以将标称型数据映射为二值型数据再用于距离计算。
分析数据：使用任意方法。
训练算法：无监督学习没有训练过程。
测试算法：使用量化的误差指标(误差平方和)来评价算法的结果。
使用算法：可以用于所希望的任何应用。

按照上述方式反复迭代，直到所有数据点的簇分配结果不在改变为止。

10.2 使用后处理来提高聚类性能

如何选择k？如何知道生成的簇比较好？
K-均值算法收敛但是聚类效果较差的原因是，K-均值算法收敛到了局部最小值，而非全局最小值。
SSE(Sum of Squared Error，误差平方和)是一种度量聚类效果的指标，越小则表示数据点越接近于它们的质心，效果就越好。增加簇肯定能降低SSE值，所以聚类的目标就是在保持簇数目不变的情况下提高簇的质量。
一般可以对生成的簇进行后处理来进行改进：将具有最大SSE值的簇划分为两个簇。而为了保持簇总数不变，可以将某两个簇进行合并，比如合并最近的质心，或者合并两个使得SSE增幅最小的质心。

10.3 二分K-均值算法

该算法用于防止算法收敛于局部最小值：首先将所有点作为一个簇，然后将之一分为二。之后选择其中一个簇继续进行划分(取决于对哪一个簇进行划分可以最大程度降低SSE的值)，不断重复上述过程，直到得到指定的簇数目。
伪代码：

将所有点看成一个簇
当簇数目小于k时
对于每一个簇
计算总误差
在给定的簇上面进行K-均值聚类(k=2)
计算将该簇一分为二之后的总误差
选择使得误差最小的那个簇进行划分操作

或者直接选择SSE最大的簇进行划分，直到簇数目达到指定数目。

10.5 本章小结

聚类是一种无监督的学习方法，无监督学习就是事先不知道要寻找的内容，没有目标变量。
K-均值算法非常简单有效但是也容易受到初始簇质心的影响，所以可以用到二分K-均值的聚类算法。

第十一章 使用Apriori算法进行关联分析

通过查看商店的会员会经常将哪些商品一起购买，可以帮助商店了解用户的购买行为。这种从数据海洋中抽取的知识可以用于商品定价、市场促销、存货管理等环节。从大规模数据集中寻找物品间的隐含关系被称作关联分析(association analysis)或者关联规则学习(association rule learning)，寻找物品的不同组合是一项十分耗时的任务，代价很高，所以就需要用更智能的方法在合理的时间范围内找到频繁项集。

11.1 关联分析

Apriori算法

优点：易编码实现。
缺点：在大数据集上可能较慢。
适用数据类型：数值型或者标称型数据。

关联分析是一种在大规模数据集中寻找有趣关系的任务。关系可为频繁项集或者关联规则。
频繁项集(frequent item sets)是经常出现在一块的物品的集合。
关联规则(association rules)则是暗示两种物品之间可能存在很强的关系。

由上图：
这里引入两个概念：
支持度(support)：数据集中包含该项集的记录所占的比例。比如{豆奶}的支持度为4/5。{豆奶，尿布}的支持率为3/5。
可信度或置信度(confidence)：针对一条诸如{尿布}->{葡萄酒}的关系规则，可以被定义为“支持度({尿布，葡萄酒})/支持度({尿布})”，等于0.75，所以“尿布->葡萄酒”的可信度为0.75，这意味着对于包含“尿布”的所有记录，我们的规则对其中的75%的记录都适用。

11.2 Apriori原理

对于商品来说，对那些经常在一起被购买的商品非常感兴趣，不是某人买了几件商品，而是购买了一种或多种商品。

Apriori算法的一般过程

收集数据：任意方法。
准备数据：任何数据类型都可以，因为我们只保存集合。
分析数据：使用任意方法。
训练算法：使用Apriori算法来找到频繁项集。
测试算法：不需要测试过程。
使用算法：用于发现频繁项集以及物品之间的关联规则。

可以发现仅仅是4个项目，就可以循环很久，而项目越多，组合将越来越多了。
而Apriori原理可以帮助减少可能感兴趣的项集：Apriori原理表示如果某个项集是频繁的，那它的所有的子集也都是频繁的。反过来看就有用了，也就是说如果一个项集是非频繁集，那么它的所有超集也是非频繁的。

如上图，就可以快速排除大量的非频繁项集。

11.3 使用Apriori算法来发现频繁集

Apriori算法的两个输入参数分别是最小支持度和数据集。该算法首先会生成所有单个物品的项集列表。然后扫描交易记录查看哪些项集满足在最小支持度要求，不满足的去掉，然后对生下来的集合进行组合以生成包含两个元素的项集，然后重新扫描交易记录，去掉不满足的。重复进行直到所有项集都被去掉。

11.4 从频繁项集中挖掘关联规则

首先从一个频繁项集开始，因为集合中的元素是不重复的，某个元素或者某个元素集合可能会推导出另一个元素。比如有一个频繁项集{A, B}，那么就有可能有一条关联规则“A -> B”。意味着如果有人购买了A，那么在统计上他会购买B的概率较大。但是反过来并不总是成立。也就是说，即使“A -> B”统计上显著，那么“B->A”也不一定成立(箭头左边的叫前件，右边的叫后件)。
同样的，可信度也有最小要求值。根据Apriori原理也可得出，若规则A->B并不满足最小可信度要求，那么就知道任何左部为A子集的规则也不会满足最小可信度要求。

11.7 本章小结

每次增加频繁项集的大小，Apriori算法都会重新扫描整个数据集。当数据集很大时，这会显著降低频繁项集发现的速度。

第十二章 使用FP-growth算法来高效发现频繁项集

对于搜索引擎，输入一个单词或单词的一部分，搜索引擎就会自动补全查询词项。这就需要一种高效发现频繁集的方法：FP-growth。基于Apriori构建，只需对数据库进行两次扫描。

(1) 构建FP树
(2) 从FP树中挖掘频繁项集

12.1 FP树：用于编码数据集的有效方式

FP-growth算法

优点：一般要快于Apriori。
缺点：实现比较困难，在某些数据集上性能会下降。
适用数据类型：标称型数据。

FP-growth算法将数据储存在一种称为FP树的紧凑数据结构中。FP为频繁模式(Frequent Pattern)。它通过链接(link)来连接相似元素，被连起来的元素项可以看成一个链表，如下：

与搜索树不同，一个元素项可以在一颗FP树中出现多次，FP树会存储项集的出现频率，而每个项集会以路径的方式存储在树中。存在相似元素的集合会共享树的一部分。只有当集合之间完全不同时，树才会分叉。树节点上给出集合中的单个元素及其在序列中的出现次数，路径会给出该序列的出现次数。
相似项之间的链接即节点链接(node link)，用于快速发现相似项的位置。
以下是上图中数据的表：

在树中，元素项z出现了5次，集合{r,z}出现了1次。所以z一定是自己本身或者和其他符号出现了4次，然后集合{t,s,y,x,z}出现了2次，集合{t,r,y,x,z}出现了1次。所以剩下的z它一定单独出现过一次。
另外看表中005号记录却是{y,r,x,z,q,t,p}，很显然，这两个元素的支持度低于了最小阈值，被认为是不频繁的，所以没有。
所以FP-growth算法的工作流程如下：首先构建FP树，然后利用它来挖掘频繁项集。为了构建FP树，需要对原始数据集扫描两遍，第一遍对所有元素项的出现次数进行计数(用Apriori原理，快)。第二遍就只考虑那些频繁元素。

FP-growth的一般流程

收集数据：任意方法。
准备数据：由于存储的是集合，所以需要离散数据。如果要处理连续数据，需要将它们量化为离散值。
分析数据：使用任意方法。
训练算法：构建一个FP树，并对树进行挖掘。
测试算法：没有测试过程。
使用算法：可用于识别经常出现的元素项，从而用于制定决策、推荐元素或进行预测等应用中。

12.2 构建FP树

在第二次扫描数据集时会构建一棵FP树。为构建一棵树，需要一个容器来保存树。

由上图所示，除了之前的FP树之外，还需要一个头指针表来指向给定类型的第一个实例。使用它，可以快速访问FP树中一个给定类型的所有元素。
第一遍遍历数据集会得到每个元素项的出现频率，去掉不满足最小支持率的元素项。构建时，读入每个项集并将其添加到一条已经存在的路径中。若不存在，则创建一条新路径(需要事先对每个集合进行排序)。

12.3 从一棵FP树中挖掘频繁项集

这里与Apriori算法大致类似，首先从单元素项集合开始，然后在此基础上逐步构建更大的集合。这里将利用FP树来做实现上述过程，不再需要原始数据集了。
从FP树中抽取频繁项集的三个基本步骤如下：

(1)从FP树中获得条件模式基；
(2)利用条件模式基，构建一个条件FP树；
(3)迭代重复步骤(1)步骤(2)，直到树包含一个元素项为止。

12.3.1 抽取条件模式基

对于每一个元素项，获得对应的条件模式基：以所查找元素项为结尾的路径集合。每一条路径其实都是一条前缀路径(prefix path)。即一条前缀路径是介于所查找元素项与树根节点之间的所有内容。比如根据FP树，符号r的前缀路径是{x,s}、{z,x,y}和{z}。每一条前缀路径都与一个计数值关联。该计数值等于起始元素项的计数值，给出了每条路径上r的数目。比如下图：

为了获取前缀路径，可以对树进行穷举式搜索，或者使用一个更有效的方法来加速搜索过程：利用先前创建的头指针来得到一个更有效的方法。

12.3.2 创建条件FP树

对于每一个频繁项，都要创建一棵条件FP树。可以使用刚才发现的条件模式基作为输入数据，并通过相同的建树代码来构建这些树，递归的发现频繁项、发现条件模式基，以及发现另外的条件树。比如假定为t创建一个条件FP树，然后对{t,y}、{t,x}、…重复该过程。

注意在上图中，元素项s以及r是条件模式基的一部分，但是它们并不属于条件FP树。实际上单独来看它们都是频繁项，但是在t的条件树中，它们却不是频繁的，也就是说，{t,r}及{t,s}是不频繁的。
然后就对集合{t,z}、{t,x}以及{t,y}来挖掘对应的条件树。这回产生更复杂的频繁项集。该过程重复进行，直到条件树中没有元素为止。

12.6 本章小结

可以使用FP-growth算法在多种文本文档中查找频繁单词或者购物交易、医学诊断及大气研究等。

第四部分 其他工具

这一部分包括了对前三部分中任一算法的输入数据进行预处理的降维技术，而降维的目标就是对输入的数目进行削减，由此剔除数据中的噪声并提高机器学习方法的性能。

第十三章 利用PCA来简化数据

在看电视的时候，对于人来说，很自然的，就实时地将显示器上的百万像素转换成一个三维图像，该图像就给出了运动场上球的位置。这时，人就已经将数据从一百万维降至了三维。
只有球的三维位置才最重要，这就被称为降维(dimensionality reduction)。在低维下，数据更容易进行处理。
在降维中，要对数据进行预处理。之后再用其它机器学习技术对其进行处理。

13.1 降维技术

数据显示是大规模特征下的难题，另外对数据进行简化还有如下一系列的原因：

使得数据集更易使用；
降低很多算法的计算开销；
去除噪声；
使得结果易懂。

这里主要将降维技术用于未标注数据上的降维技术。

第一种降维的方法称为主成分分析(Principal Component Analysis，PCA)。在PCA中，数据从原来的坐标系转换到了新的坐标系，新坐标是由数据本身决定的。第一个新坐标轴选择的是原始数据中方差最大的方向，第二个的选择和第一个坐标轴正交且具有最大方差的方向。该过程一直重复，重复次数为原始数据中特征的数目。可以发现，大部分方差都包含在最前面的几个新坐标轴中。因此，可以忽略余下的坐标轴，即对数据进行了降维处理。
另一种降维技术是因子分析(Factor Analysis)。在因子分析中，我们假设在观察数据的生成中有一些观察不到的隐变量(latent variable)。假设观察数据是这些隐变量和某些噪声的线性组合。那么隐变量的数据可能比观察数据的数目少，也就是说通过找到隐变量就可以实现数据的降维。
还有一种就是独立成分分析(Independent Component Analysis，ICA)。ICA假设数据是从N个数据源生成的，这一点和因子分析有些类似。假设数据为多个数据源的混合观察结果，这些数据源之间在统计上是相互独立的，而在PCA中只假设数据是不相关的。同因子分析一样，如果数据源的数据少于观察数据的数目，则可以实现降维。

13.2 PCA

主成分分析

优点：降低数据的复杂性，识别最重要的多个特征。
缺点：不一定需要，且有可能损失有用信息。
适用数据类型：数据型数据。

13.2.1 移动坐标轴

由上图中的大量数据点，如果要求画一条直线，尽可能覆盖这些点，那么最长的线是哪条？如B。在PCA中，对数据的坐标进行了旋转，旋转过程取决于数据的本身。第一条坐标轴旋转到覆盖数据的最大方差位置，即直线B(数据的最大方差给出了数据的最重要的信息)。
至于第二条坐标轴，假如该坐标轴与第一条坐标轴垂直，它就是覆盖数据次大差异性的坐标轴。也就是正交，即直线C。利用PCA，可以将数据坐标轴旋转至数据角度上的那些最重要的方向。
坐标轴旋转后，就要开始降维，因为坐标轴的旋转并没有减少数据的维度，以如下图为例：

其中的数据来自于之前的图经过PCA转换之后绘制而成的。如果仅使用原始数据，那么这里的间隔会比决策树的间隔更大。另外若只需要一维信息，数据就可以通过比SVM简单得多的很容易采用的规则进行区分。
对于上图来说，只需要一维信息即可，因为另一维信息只是对分类缺乏贡献的噪声数据。这在高维空间下则意义重大。
之前的第一个主成分和第二个主成分，通过数据集的协方差矩阵及其特征值分析，就可以求得成分值。一旦得到了协方差矩阵的特征向量，就可以保留最大的N个值。这些特征向量也给出了N个最重要特征的真实结构，然后就可以通过将数据乘上这N个特征向量而将它转换到新的空间。

将数据转换成前N个主成分的伪码大致如下：

去除平均值
计算协方差矩阵
计算协方差矩阵的特征值和特征向量
将特征值从大到小排序
保留最上面的N个特征向量
将数据转换到上述N个特征向量构建的新空间中

13.4 本章小结

降维技术使得数据变得更易使用，并且它们往往能够去除数据中的噪声，使得其他机器学习任务更加精确。降维往往作为预处理步骤，在数据应用到其他算法之前清洗数据。

第十四章 利用SVD简化数据

餐馆可划分为很多类别，如何才能知道到底有多少类餐馆呢，还是从数据着手吧，并从中提取出背后的因素。
提取这些信息的方法称为奇异值分解(Singular Value Decomposition，SVD)，是提取信息的强大工具。

14.1 SVD的应用

奇异值分解

优点：简化数据，去除噪声，提高算法的结果。
缺点：数据的转换可能难以理解。
适用数据类型：数值型数据。

SVD可以看成是从噪声数据中抽取相关特征，而不是去除信息。

14.1.1 隐性语义索引

最早的SVD应用之一就是信息检索，一般称利用SVD的方法为隐性语义索引(Latent Semantic Indexing，LSI)或隐性语义分析(Latent Semantic Analysis，LSA)。
在LSI中，一个矩阵是由文档和词语组成的。当在该矩阵上应用SVD时，就会构建出多个奇异值，代表了文档中的概念或主题，这一特点可以用于更高效的文档搜索。比如在词语拼写错误时，只基于词语存在与否的简单搜索会遇到问题，且由于同义词的使用，当查找一个词时，其同义词所在的文档可能并不会匹配上。但是如果从上千篇相似的文档中抽取出概念，那么同义词就会映射为同一概念。

14.1.2 推荐系统

SVD的另一个应用是推荐系统。从计算项或者人之间的相似度，到先利用SVD从数据中构建一个主题空间，然后再在该空间下计算其相似度。

对上述矩阵进行SVD处理，会得到两个奇异值。因此，就会应该有两个概念或主题与此数据集相关联。也可以把奇异值想象成一个新空间，最终的矩阵只有两维，分别对应图中给出的两个组，右图中标示了其中的一个组。就可以基于每个组的共同特征来命名这二维。
SVD是矩阵分解的一种类型，而矩阵分解是将数据矩阵分解为多个独立部分的过程。

14.2 矩阵分解

很多时候，数据中的一小段携带了数据集中的大部分信息，而其余的要么是噪声，要么就是毫不相关的信息。而矩阵分解可以将原始矩阵表示成新的易于处理的形式，这种新形式是两个或多个矩阵的乘积。比如12分解成(1,12)、(2,6)。
SVD是矩阵分解技术的一种，将原始的数据集矩阵Data分解成三个矩阵$\mathbf{U}, \mathbf{\Sigma}$和$\mathbf{v}^{\mathbf{T}}$。如果原始矩阵Data是m行n列，那么$\mathbf{U}, \mathbf{\Sigma}$和$\mathbf{v}^{\mathbf{T}}$就分别是m行m列、m行n列和n行n列：

$$\operatorname{Data}_{m \times n}=U_{m \times m} \Sigma_{m \times n} V_{n \times n}^{\mathrm{T}}$$

上述分解中会构建出一个矩阵$\Sigma$，该矩阵只有对角元素，其他元素均为0。且一般$\Sigma$的对角元素是从大到小排列的。这些对角元素称为奇异值(Singular Value)，它们对应了原始数据集矩阵Data的奇异值，即矩阵的特征值，告诉了数据集中的重要特征。$\Sigma$中的奇异值也是这样。这里的奇异值就是矩阵$\operatorname{Data}$ * $\operatorname{Data}^{\mathrm{T}}$特征值的平方根。
另外在某个奇异值的数目(r个)之后，其他的奇异值都置为0(对角元素从大到小排列)，就意味着数据集中仅有r个重要特征，而其余特征则都是噪声或冗余特征。

14.4 基于协同过滤的推荐引擎

协同过滤(collaborative filtering)是通过将用户和其他用户的数据进行对比来实现推荐的技术。
这里的数据是从概念上组织成了类似如下：

的矩阵形式。当数据采用这种方式进行组织时，就可以比价用户或物品之间的相似度了，之后就可以利用已有的数据来预测未知的用户喜好。比如推荐未看过的电影，若用户相似度高，喜好也会接近类似。

14.4.1 相似度计算

不利于专家所给出的重要属性来描述物品从而计算它们之间的相似度，而是利用用户对它们的意见来计算相似度。他并不关心物品的描述属性，而是严格地按照许多用户的观点来计算相似度。
比如计算手撕猪肉和烤牛肉的欧氏距离为：

$$\sqrt{(4-4)^{2}+(3-3)^{2}+(2-1)^{2}}=1$$

距离越小，说明更为相似。所以可以用“相似度=1/(1+距离)”来计算相似度。
另外还可以用皮尔逊相关系数(Pearson correlation)，它对于欧氏距离的一个优势在于，它对用户评级的量级并不敏感，比如A对所有物品的评分都是5分，而B都是1分，皮尔逊相关系数会认为这两个向量是相等的。
还有一种方法是余弦相似度(cosine similarity)，其计算了两个向量夹角的余弦值。夹角为90度，则相似度为0，方向相同，则为1.0。范围在-1到+1之间，为了方便就计算余弦相似度值：

$$\cos \theta=\frac{A \cdot B}{\|A\|\|B\|}$$

14.4.3 推荐引擎的评价

将某些已知的评分值去掉，然后对它们进行预测，最后计算预测值和真实值之间的差异。
通常用于推荐引擎评价的指标称为最小均方根误差(Root Mean Squared Error，RMSE)，首先计算均方误差的平均值，然后取其平方根。

14.7 本章小结

可以利用SVD这个强大的降维工具，来逼近矩阵并从中提取重要特征。通过保留矩阵80%~90%的能量，就可以得到重要的特征并去掉噪声，其中一个成功的案例就是推荐引擎。

第十五章 大数据与MapReduce

有时候数据太大了，即使算法可以，训练算法要好几天的时间，这种时候就需要一些工具包。

15.1 MapReduce：分布式计算的框架

MapReduce

优点：可在短时间内完成大量工作。
缺点：算法必须经过重写，需要对系统工作有一定的理解。
适用数据类型：数值型和标称型数据。

MapReduce可以将单个计算作业分配给多台计算机执行，因此可以缩短运行时间。
MapReduce在大量节点组成的集群上运行：单个作业被分成很多小份，输入数据也被切片分发到每个节点，每个节点只在本地数据上做运算，对应的运算代码称为mapper，这个过程被称作map阶段，每个mapper的输出通过某种方式组合(一般还会排序)，之后的结果再被分成小份分发到各个节点进行下一步工作。第二步的处理阶段被称为reduce阶段，对应的代码被称为reducer，reducer的输出就是程序的最终执行结果(比如为了统计近100年中国国内的最高气温)。
以最高气温为例，所有同一年的数据要传递给同一个reducer，这由map和reduce阶段中间的sort阶段来完成，所以数据会以key/value对的形式传递。且reducer的数量并不是固定的。

如上图，每台机器都有两个处理器，可以同时处理两个map或者reduce任务，map任务之间不做数据交流，reduce任务也一样，在map和reduce阶段中间，有一个sort或combine阶段。主节点控制MapReduce的作业流程，若机器0在map阶段宕机，主节点就会发现这一点，就会将机器0移出集群，并在剩余的节点上继续执行作业。另外在多个机器上都会保存有数据的多个备份。

15.2 Hadoop流

Hadoop是一个开源的Java项目，为运行MapReduce作业提供了大量所需的功能。

15.4 MapReduce上的机器学习

在10台机器上使用MapReduce并不能等价于当前机器10倍的处理能力。

15.6 实例：分布式SVM的Pegasos算法

简单贝叶斯可以用于处理文档，但是在海量文档上做文本分类也是很大的挑战，如果能将算法分成并行的子任务，那么MapReduce框架就能帮助。

在MapReduce框架上使用SVM的一般方法

收集数据：数据按文本格式存放。
准备数据：输入数据已经是可用的格式，所以不需任何准备工作。
分析数据：无。
训练算法：与普通的SVM一样，在分类器训练上仍需花费大量的时间。
测试算法：在二维空间上可视化之后，观察超平面，判断算法是否有效。
使用算法：该算法的其中一个应用场景就是文本分类，通常在文本分类里可能有大量的文档和成千上万的特征。

15.6.1 Pegasos算法

指的是原始估计梯度求解器(Primal Estimated sub-GrAdient Solver)，它使用某种形式的随机梯度下降方法来解决SVM所定义的优化问题。其迭代次数取决于用户所期望的精确度而不是数据集的大小。
伪代码：

将w初始化为0
对每次批处理
随机选择k个样本点(向量)
对每个向量
如果该向量被错分：
更新权重向量w
累加对w的更新

15.8 本章小结

很多机器学习算法都可以很容易地写成MapReduce作业。