算法

算法是完成分析任务所采纳或者遵循的一整套步骤和规则，它是计算机科学中一个基本概念，可视作计算机科学的基石。设计优雅高效的代码、准备和处理数据以至软件工程开发均以算法为基础。 排序、查找、基于图的计算等问题都是算法能够解决的。然而，对于同一个问题，基于效率和计算时间的考虑，可以选出某个相对最优的算法。当算法要解决的数据分析问题涉及海量数据，或者开发面向客户的产品时，基于效率选择最优的算法会变得尤为重要。 高效的算法是准备和处理数据的基础，算法的执行可以是顺序的，也可以是并发的。 就数据科学来说，以下三类算法是必须了解的。

1. 数据清理和预处理的算法。比如排序、MapReduce、Pregel。我们将这类算法称为数据工程。
2. 用于参数估计的最优化算法。比如Stochastic Gradient Descent（随机梯度下降）、 Newton’s Method（牛顿法）和 Least Squares（最小二乘法）。在本书中，我们会介绍这些算法。另外值得一提的是，在R软件中这些算法都有相应的实现函数。
3. 机器学习算法。

机器学习算法

机器学习算法的应用主要有三个大舞台：预测、分类和聚类。 一般来讲，机器学习是人工智能的基础，比如图像识别、语音识别、推荐系统、排名和个性化推荐系统技术——这些都是打造数据产品的基础。

关于参数的解释

在软件工程师或计算机科学家主要关心的是如何将算法（包含其中的参数）植入到数据产品中，模型有些可以很复杂，甚至难以解释。有些模型甚至被叫作黑匣子，因为们根本不知道模型内部到底是如何运作的。他们通常不会关注模型参数的意义。即便他们想要关注，也可能是只是为了提升模型的预测能力，而不是为了解释这些参数。

置信区间

在统计学中，置信区间和后验分布用来描述参数估计的不确定性。但是，有些机器学习算法，比如k均值算法（k-means）和k近邻算法（k-nearest neighbors），就不涉及置信区间和参数估计的不确定性问题。

显式假设的角色

统计模型会对数据的生成过程和数据的分布做出一些明确的假设（称作显式假设），统计推断的过程往往是建立在这些假设的基础之上。而本章稍后将要介绍的非参数检验方法，并不对概率分布做任何显式假设（可能是隐式的）。

三大基本算法

作为一个数据科学家，在熟练掌握各种算法之后，真正的挑战其实才刚刚开始。你需要根据特定问题和隐含的假设来推敲到底使用哪个算法或者模型。这种判断部分源自经验。 算法是完成某项任务时需要遵循的一组规则或步骤，而模型是对世界一种附有假设的描述。

线性回归模型

线性回归是统计学中最常用的统计方法之一。从根本上来说，当你想表示两个变量间的数学关系时，就可以使用线性回归。当你使用它时，你首先假设输出变量（有时称为响应变量、因变量或标签）和预测变量（有时称为自变量、解释变量或特征）之间存在线性关系。当然这种线性关系也可 能存在于一个输出变量和数个预测变量之间。 ¹

考虑随机函数，即便是对于数学功底不错的我们来说，也是一个新鲜的概念，但是在数据科学中却再常见不过了。然而，随机函数从根本上来说，还是建立在确定型函数的基础之上的。 可以从数学上证明，无论误差项的分布形态如何，最小二乘估计都具备同样优良的性质：它是无偏估计量，并且具有最小的估计方差。

均方误差

方差估计量也叫作均方误差（mean squared error），它衡量的是预测值偏离实际观测值的程度。对于预测问题来说，均方误差是被广泛使用的一个误差估计量。$\mathrm{MSE}=\frac{1}{n} \sum_{i=1}^{n}\left(Y_{i}-\hat{Y}_{i}\right)^{2}$

模型评估标准

R方 可以解释为数据中能够被模型所解释的方差占数据总方差的比重。将这个公式与之前均方误差的公式对比，我们会发现，均方误差实际上是R方公式中分式的分子部分，分母对应的是数据中的总方差，因此整个分式代表的是数据中未被模型解释的方差的比重。

p值

敏感度又叫作“真阳性率”（true positive rate）或者召回率（recall)。来自不同学术研究领域的研究人员会使用不同的术语，但是它们都代表的一个意思。特异度也叫“真阴性率”（true negative rate）。 既然有“真阳性率”和“真阴性率”，当然也有“伪阳性率”和“伪阴性率”，但是后两个术语没有其他的表述形式。

交叉验证

还有另外一种评估模型的方法，它大概要遵循这样的程序：分割数据，80%用作训练数据集，20%用作测试。在训练数据及上拟合模型并估计模型的参数，并在测试数据集上计算出模型的均方误差，并与训练数据集上模型的均方误差进行比较。如果两种均方误差的差异很小，那么可以认为
模型具有不错的扩展性，其过拟合的风险较小。我们也建议大家尝试改变一下训练数据集的大小，看看两者之间有何联合变动关系，这样的模型验证过程叫作“交叉验证法”。

其他类型的模型误差测度

均方误差属于“损失函数”的一种，在线性回归中均方误差是最常使用的误差指标，它能够很好地测度模型的拟合效果。它的另外一项优点就是，如果假设误差项是正态分布的，那么模型的估计可以完全依赖最大似然函数法。其他类型的模型误差测度还有很多，比如基于绝对值误差。人们甚至可以根据研究的目的和个人的偏好设计和使用相应的误差测度指标。

增加预测变量

在一个自变量以及一个因变量模型的基础之上，我们可以增加预测变量（自变量）的个数，从而得到多元回归模型。 之前的模型表达式在这里也同样适用，因为我们之前用了矩阵表达式，增加一个变量无非是在矩阵上增加一列而已，模型的表达形式不会改变。 在确定到底使用哪些预测变量时，散点图通常是一个很好的工具。我们可以画出预测变量与每一个自变量之间的散点图，以及自变量之间的散点图，以找到或确认可能有用的预测变量和变量之间的交叉变动关系。基于预测变量的每一个值，画出因变量的条件分布$(y|x)$直方图也会有所帮助。在选定了预测变量之后，同简单线性回归模型一样，我们仍然可以使用R方、p值和交叉验证的方法评价模型的质量。

变换

使用x的高阶项。多项式回归模型不是线性回归模型。但是如果把x的高阶项看成新的变量，上式的表达形式仍然保持着“线性”的模样。也就是说，我们可以把多项式回归模型看成线性模型，前提是把变量做一下适当的变换。比如，我们可以假设$z=x^2$，$w=x^3$，这样上面的模型就是一个基于三个预测变量$(x, z, w)$的线性回归模型了。这样的变量变换在线性回归中经常会用到，其他的变换方法还包括取对数、离散化、二元化等。

在构建模型和拟合模型的时候做过的诸多假设：

• 线性假设；
• 误差项是正态分布的，并且均值为0；
• 误差项是相互独立的；
• 误差项具有恒定的条件方差；
• 预测变量都是有用的。 我们应用线性回归模型，主要基于以下两个目的：
• 用作预测，在知道自变量值的情况下，预测因变量的可能值；
• 用作变量关系的解释，比如确定两个变量之间可能的相关关系或者联合变动关系等。

k近邻模型(k-NN)

k近邻模型是一个分类算法，在给定一个已经做好分类的数据集之后，k近邻可以学习其中的分类信息，并自动给尚未分类的类似数据分好类。 分类是建模的基本问题之一。 k近邻的主要想法是，根据属性值的相似度找到某个对象的相似对象们，并让其相似对象们一起“投票”决定该对象到底应该属于哪一类。如果有某两个或者更多个的类别投票数相同，那么就从这些类别中随机挑选一个作为该对象的类别值。 k近邻方法需要解决两个核心问题：其一是如何根据属性定义个体之间的相似性或者紧密程度。一旦有了明确的定义，我们就可以把某个带预测个体的“近邻”们找出来，让它们投票决定该个体的类别属性。 k近邻方法工作的详细步骤。

1. 首先确定相似性定义，这通常也叫作“距离”。
2. 将数据分割成训练数据和测试数据集。
3. 选择一个模型评价标准。（对于分类问题来说，误分率是个不错的选择，我们会在稍后章节详细讨论。）
4. 选择不同的k值，并应用k近邻模型，看哪个模型的效果最好。
5. 基于选定的模型评价标准，选出最优的k值。
6. 选定k之后，就可以做样本外测试了。

相似性/距离测度 相似性测度的选择在很大程度上要取决于问题的背景和数据本身的特征。所以，变量的取值都应大致在同一个水平上，通过变换单位的方式。 变量的计量方式以及变量之间距离的定义方式，在统计学中我们叫作“先验信息”，它们都可能会影响到模型最终的效果。 欧几里得距离又叫欧氏距离，对于在实数轴上取值以及能够在平面或者多维空间中描绘出来的变量来说，它是一个不错的距离量度，它是在m维空间中两个点之间的真实距离。

• 余弦度（Cosine Similarity） 余弦度同样可以用于度量两个实数向量 和 之间的相似程度，而且余弦度是一个介于-1和1之间的数。如果取值为-1则代表完全不同，1代表完全一样，而0则代表两个向量之间相互独立。回顾一下余弦度的定义：$\cos (\vec{x}, \vec{y})=\frac{\vec{x} \cdot \vec{y}}{\|\vec{x}\|\|\vec{y}\|}$
• Jaccard距离或相似度 Jaccard距离通常用作衡量两个集合之间的相似度——比如说Cathy的朋友集合表示为A = {Kahn, Mark, Laura, …}， Rachel的朋友集合表示为B = {Mladen, Kahn, Mark, …}， 那么这两个朋友集合的Jaccard相似度为$J(A, B)=\frac{|A \cap B|}{|A \cup B|}$。
• Mahalanobis距离 也称作马氏距离，同样适用于两个实数向量。相比于欧氏距离，马氏距离考虑了两个变量之间的相关关系，并且不用担心变量取值水平的问题。可以应对高维线性分布的数据中各维度间非独立同分布的问题。马氏距离的定义为：$d(\vec{x}, \vec{y})=\sqrt{(\vec{x}-\vec{y})^{T} S^{-1}(\vec{x}-\vec{y})}$，其中S是两个向量间的协方差矩阵。
• Hamming 距离 Hamming距离主要用来衡量两个字符串，字组或者具有相同长度的DNA序列之间的相似程度。比如，单词olive和ocean的Hammning距离为4，因为除了第一个字母o相同之外，这两个单词包含的其他四个字母都不相同。同理，单词shoe和hose之间的Hamming距离是3，这是因为除了最后一个字母e相同之外，其他三个字母在对应位置上均不相同。因此，Hamming距离的计算方式其实十分简单，按照位置顺序比对两个单词字母之间是否相同，每个位置上字母的不同，相应Hamming距离的值都增加1。 • Manhattan距离 Manhattan距离（曼哈顿距离）也用来测度两个k维实数向量之间的距离。之所以叫作Manhattan距离，是因为要把这个距离想象成城市中两点之间，如果用计程车行走的路线来算的话，应该为多长。（在城市中行走或者行车需要遵循一定的路线规定，譬如大型建筑要绕行，不能穿墙而过。）曼哈顿距离的定义为：$d(\vec{x}, \vec{y})=\sum_{i}^{k}\left|x_{i}-y_{i}\right|$，i代表向量中元素的位置。

训练和测试数据集 对于所有的机器学习算法来说，将数据集分成训练数据集和测试数据集是最为通用的做法。数据集用来“训练”模型，而测试数据用来独立地测试“训练好”的模型在实际问题上的真实表现。 对于k近邻模型来说，训练阶段的数据是包含因变量（信用等级）的标签值的。在模型测试阶段，我们假装不知道因变量的真实标签值，并用在训练阶段得到的k近邻模型预测这些标签值。 要想实现测试的目的，我们必须从原始数据中保留一些数据出来，这些数据不用于模型训练而只用于测试。通常来说，我们会随机抽取20%的数据出来作为测试用数据集。

选择一个模型评价标准 就像我们之前反复说的，模型的评价是非常灵活和主观的，并没有普适的标准。对于某个实际问题，你可能觉得高误分率的严重性要大于其他的误差测度，或者你会觉得伪阴性的严重性要大于伪阳性。因此，在确定一个模型的评价标准时，你可能要和某个问题领域的专家好好交流一番。 举例来说，如果分类模型的对象是人们是否患癌，那么模型的伪阴性当然越小越好（伪阴性指的是某人实际患癌，但是模型却告诉我们他没有患癌）。在确定合理的模型评价标准之前，我们最好与癌症领域的专家医生做好交流沟通，以更深入地了解手中数据所涉及的实际问题背景。 但是对于伪阴性，有一个极端的问题是：如果你想确保伪阴性为0，你可以把所有的病人都分类为癌症患者。这当然也不合理，因为相应的伪阳性率会增加。在分类问题中，这叫作敏感度(sensitivity)与特异度(specificity)的权衡。敏感度指的是所有的患癌病人实际被诊断为患癌的概率，而特异度指的是未患癌的病人被诊断为未患癌的概率。理想的模型需要具备高敏感度和高特异度。

关于敏感度和特异度的其他说法 敏感度又叫作“真阳性率”（true positive rate）或者召回率（recall)。来自不同学术研究领域的研究人员会使用不同的术语，但是它们都代表的一个意思。特异度也叫“真阴性率”（true negative rate）。 既然有“真阳性率”和“真阴性率”，当然也有“伪阳性率”和“伪阴性率”，但是后两个术语没有其他的表述形式。

还有一种模型评价标准叫作“准确度”，指的是所有被正确分类的标签数占总标签数的比例。因此，误分率 = 1 - 准确度。最小化模型的“误分率”就等同于最大化模型的“准确度”。

k均值算法

之前介绍的算法都属于监督性学习算法，它适用于y的观测值（对于分类问题来说就是待预测变量的标签值）已知的情况。在这个背景下，我们总是希望模型对y的预测越精确越好，这也是在监督性学习中存在模型评价标准的原因。 “非监督性学习算法”的典型代表是聚类分析，在聚类分析中y的真实标签值是未知的。k均值是我们要接触到的第一个“非监督学习算法”。

1. 每个用户都可以表示成某些特征变量的组合，比如年龄、性别和收入等。
2. 我们的任务是根据用户变量信息的不同把用户分成几组。这个任务也有很多其他的名字，比如分层、分组、聚类等。但是它们都指的是一个意思，那就是根据用户特征的信息把相似的用户组合起来形成类别。
3. 在建模过程中，我们经常需要对某些特征变量（属性变量）进行离散化或者分块化（分组）。可能会得到非常多种不同的组合。这对于建模来说，已经是很大规模的分组了。
4. 在一个五维空间中，每个变量都对应一个坐标轴：因此，有性别轴、收入轴等。每个分组都对应相应的坐标轴点。这样做的结果是这些坐标轴交织形成的网将包含每一个可能的属性变量的组合值。
5. 每个数据点都在这个空间中对应坐标轴系统内的某一个组合点。在这种情形下，你想在建模之前进行分组，却又不想得到上万个不同的组别。这就是k均值聚类可以做的事情：k就是这个聚类算法最后所得到的类别数。

在二维空间的散点图可以看出，数据自然地聚成了几类。对于二维空间的数据来说，如果数据点不多，我们很容易就可以通过肉眼判断出数据大概聚成了多少类。当数据维数增加或者数据量变大之后，就不可能依赖于肉眼判断了，你需要一个类似于k均值聚类的算法帮助你判断数据中到底有多少类别。k均值聚类可以在d维空间中找到聚类，其中d是数据空间的维度，也是每个数据点所具有的特征变量的个数。 聚类有四步：

1. 首先，在数据空间中随机挑选k个点（叫作中心点，centroid）。这也叫k均值聚类的初始化操作，要尽量让中心点靠近数据点，并且各个中心点之间要明显不同。
2. 将数据点分类到离它最近的中心点。
3. 重新计算中心点的位置。
4. 重复上述两步直到数据中心点的位置不再变动，或者变动幅度很小为止。

至于如何确定算法已经迭代完毕也没有绝对的标准。甚至对于k的选择也没有标准，毕竟这是一个非监督性的学习方法，k的大小要通过不断地尝试，以确定一个较为合适的值。 这是一个典型的非监督性学习的例子，因为所有的数据点都没有事先做好的标签类别值，都是通过算法来发现。

k均值聚类算法有一些已知的缺点。

• k的选择是颇具艺术性的。当然，k的取值也是有上下限的，需要满足$1\le k\le n$，其中n是数据的样本量。
• 收敛性问题：可能不存在唯一解，导致算法在两种可能解之间来回迭代而无法收敛。
• 可解释性问题：也许最终的聚类结果很难给出合理的解释。这通常是k均值聚类最棘手的问题。 尽管有很多问题，但是k均值聚类算法因为其逻辑简单，运行速度非常快，因此在实际中得到了广泛的应用：包括市场营销、计算机视觉（图像分割）等领域都有较多的应用。k均值聚类还可以与其他监督性学习算法结合起来使用，作为某些模型的起始估计值。

在大多数情况下，大型数据都可以拆分为一系列小数据集之后再分别独立建模（甚至可以使用同一个模型）。这通常叫作大数据的“碎片化”（sharding，碎片化就是指将大数据分割成很多小的部分并分配给不同的计算机进行建模，模型的参数估计会以分布的形式返回给建模者） 碎片化固然是大规模数据建模的一个较为简单和直接的解决方案。然而，当数据的规模达到一定的级别，模型本身就需要优化以解决计算量过大的问题。