从概念到案例：初学者须知的十大机器学习算法

姓名：周雪宁

学号：1702110196

转载：http://mp.weixin.qq.com/s/OW44XEI1t5-oJWmmq4gJvw

【嵌牛导读】：机器学习(Machine Learning, ML)是一门多领域交叉学科，涉及概率论、统计学、凸优化理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的性能。它是人工智能的核心，是使计算机具有智能的根本途径，其应用遍及人工智能的各个领域。机器学习作为科学研究的一大研究工具，是我们每个研究人员应该了解学习的知识，这里我们就将机器学习初学者须知的十大算法进行总结归纳。

【嵌牛鼻子】：人工智能，深度学习

【嵌牛提问】：机器学习具体包含拿些内容？具有什么特点？

【嵌牛正文】：

机器学习模型

       在《哈佛商业评论》发表「数据科学家是 21 世纪最性感的职业」之后，机器学习的研究广受关注。所以，对于初入机器学习领域的学习者，我们放出来一篇颇受欢迎的博文——《初学者必知的十大机器学习算法》，尽管这只是针对初学者的。

        机器学习算法就是在没有人类干预的情况下，从数据中学习，并在经验中改善的一种方法，学习任务可能包括学习从输入映射到输出的函数，学习无标签数据的隐含结构；或者是「基于实例的学习」，通过与存储在记忆中的训练数据做比较，给一个新实例生成一个类别标签。基于实例的学习（instance-based learning）不会从具体实例中生成抽象结果。

机器学习算法的类型

有三类机器学习算法：

1. 监督学习:

        可以这样来描述监督学习：使用有标签的训练数据去学习从输入变量（X）到输出变量（Y）的映射函数。

Y = f (X)

它分为两种类型：

a. 分类：通过一个给定的输入预测一个输出，这里的输出变量以类别的形式展示。例如男女性别、疾病和健康。

b. 回归：也是通过一个给定的输入预测一个输出，这里的输出变量以实数的形式展示。例如预测降雨量、人的身高等实数值。

      本文介绍的前 5 个算法就属于监督学习：线性回归、Logistic 回归、CART、朴素贝叶斯和 KNN。

        集成学习也是一种监督学习方法。它意味着结合多种不同的弱学习模型来预测一个新样本。本文介绍的第 9、10 两种算法--随机森林 Bagging 和 AdaBoost 提升算法就是集成学习技术。

2. 非监督学习:

        非监督学习问提仅仅处理输入变量（X），但不会处理对应的输出（也就是说，没有标签）。它使用无标签的训练数据建模数据的潜在结构。

非监督学习可以分为 2 种类型：

a. 关联：就是去发觉在同一个数据集合中不同条目同时发生的概率。广泛地用于市场篮子分析。例如：如果一位顾客买了面包，那么他有 80% 的可能性购买鸡蛋。

b. 聚类：把更加相似的对象归为一类，而不是其他类别对象。

c. 降维：顾名思义，降维就是减少数据集变量，同时要保证重要信息不丢失。降维可以通过使用特征提取和特征选择方法来完成。特征选择方法会选择原始变量的一个子集。特征提取完成了从高维空间到低维空间的数据变换。例如，主成分分析（PCA）就是一个特征提取方法。

         本文介绍的算法 6-8 都是非监督学习的例子：包括 Apriori 算法、K-均值聚类、主成分分析（PCA）。

3. 强化学习:

         强化学习是这样一种学习方法，它允许智能体通过学习最大化奖励的行为，并基于当前状态决定下一步要采取的最佳行动。

        强化学习一般通过试错学习到最佳行动。强化学习应用于机器人，机器人在碰到障碍物质之后会收到消极反馈，它通过这些消极反馈来学会避免碰撞；也用在视频游戏中，通过试错发现能够极大增长玩家回报的一系列动作。智能体可以使用这些回报来理解游戏中的最佳状态，并选择下一步的行动。

监督学习

1. 线性回归

        在机器学习中，我们用输入变量 x 来决定输出变量 y。输入变量和输出变量之间存在一个关系。机器学习的目标就是去定量地描述这种关系。

图 1：以一条直线的形式展示出来的线性回归：y = ax +b

        在线性回归中，输入变量 x 和输出变量 y 的关系可以用一个方程的形式表达出来：y=ax+b。所以，线性回归的目标就是寻找参数 a 和 b 的值。这里，a 是直线的斜率，b 是直线的截距。

        图 1 将一个数据集中的 x 和 y 用图像表示出来了。如图所示，这里的目标就是去寻找一条离大多数点最近的一条直线。这就是去减小一个数据点的 y 值和直线之间的距离。

2.Logistic 回归

        线性回归预测是连续值（如厘米级的降雨量），logistic 回归预测是使用了一种变换函数之后得到的离散值（如一位学生是否通过了考试）。

       Logistic回归最适合于二元分类问题（在一个数据集中，y=0 或者 1，1 代表默认类。例如：在预测某个事件是否会发生的时候，发生就是1。在预测某个人是否患病时，患病就是 1）。这个算法是拿它所使用的变换函数命名的，这个函数称为 logistics 函数（logisticsfunction，h(x)= 1/ (1 + e^x)），它的图像是一个 S 形曲线。在logistic 回归中，输出是默认类别的概率（不像线性回归一样，输出是直接生成的）。因为是概率，所以输出的值域是 [0,1]。输出值 y是通过输入值 x 的对数变换 h(x)= 1/ (1 + e^ -x) 得到的。然后使用一个阈值强制地让输出结果变成一个二元分类问题。

图 2：确定一个肿瘤是恶性的还是良性的回归。如果概率 h(x)>0.5，则是恶性的

       在图2 中，为了判断一个肿瘤是不是恶性，默认变量被设置为 y=1（肿瘤是恶性的）；变量 x可能是对一个肿瘤的检测结果，例如肿瘤的尺寸。如图中所示，logistics 函数将变量 x 的值变换到了 0 到 1 之间。如果概率超过了0.5（图中的水平线为界），肿瘤就被归类为恶性。

        logistic 回归的方程 P(x) = e ^ (b0 +b1*x) / (1 + e^(b0 + b1*x))可以被转换为对数形式： ln(p(x) / 1-p(x)) = b0 + b1*x。

       logistic 回归的目标就是使用训练数据来寻找参数 b0 和 b1 的值，最小化预测结果和实际值的误差。这些参数的评估使用的是最大似然估计的方法。

3. 分类和回归树

       分类和回归树（CART）是决策树的一种补充。

       非终端节点（non-terminal node）包含根节点 (root node) 和中间节点 (internal node)。每一个非终端节点代表一个单独的输入变量 x 和这个变量的分支节点；叶节点代表的是输出变量 y。这个模型按照以下的规则来作出预测：

图 3：决策树的一些部分

4. 朴素贝叶斯法

       在给定一个早已发生的事件的概率时，我们用贝叶斯定理去计算某个事件将会发生的概率。在给定一些变量的值时，我们也用贝叶斯定理去计算某个结果的概率，也就是说，基于我们的先验知识（d）去计算某个假设（h）为真的概率。计算方法如下：

P(h|d)= (P(d|h) * P(h)) / P(d)

其中，P(h|d) = 后验概率。就是假设 h 为真概率，给定的数据相当于先验知识 d。其中 P(h|d)= P(d1| h)* P(d2| h)*....*P(dn| h)* P(d)。

P(d|h) = 似然度。假设 h 正确时，数据 d 的概率。

P(h) = 类先验概率。假设 h 正确的额概率。(无关数据)

P(d) = 预测器先验概率。数据的概率（无关假设)

这个算法被称为「朴素」的原因是：它假设所有的变量是相互独立的，这也是现实世界中做出的一个朴素的假设。

图 4：使用朴素贝叶斯法来预测变量「天气」变化状态

以图 4 为例，如果天气=晴天，那么输出是什么呢？

       在给定变量天气=晴天时，为了判断结果是或者否，就要计算 P(yes|sunny) 和 P(no|sunny)，然后选择概率较大的结果。

计算过程如下：

->P(yes|sunny)= (P(sunny|yes) * P(yes)) / P(sunny)

= (3/9 * 9/14 ) / (5/14)

= 0.60

-> P(no|sunny)= (P(sunny|no) * P(no)) / P(sunny)

= (2/5 * 5/14 ) / (5/14)

= 0.40

所以，天气=晴天时，结果为是。

5.KNN

        KNN 使用了整个数据集作为训练集，而不是将它分为训练集和测试集。

        当给定的一个数据实例时，KNN 算法会在整个数据集中寻找 k 个与其新样本距离最近的，或者 k 个与新样本最相似的，然后，对于回归问题，输出结果的平均值，或者对于分类问题，输出频率最高的类。k 的值是用户自定义的。

        样本之间的相似性是用欧氏距离或者汉明（Hamming）距离来计算的。

非监督学习算法

6.Apriori 算法

        Apriori 算法被用来在交易数据库中进行挖掘频繁的子集，然后生成关联规则。常用于市场篮子分析，分析数据库中最常同时出现的交易。通常，如果一个顾客购买了商品 X 之后又购买了商品 Y，那么这个关联规则就可以写为：X -> Y。

        例如：如果一位顾客购买了牛奶和甜糖，那他很有可能还会购买咖啡粉。这个可以写成这样的关联规则： {牛奶，甜糖} -> 咖啡粉。关联规则是交叉了支持度（support）和置信度（confidence）的阈值之后产生的。

图 5： 关联规则 X→Y 支持度、置信度和提升度的公式表示。

        支持度的程度帮助修改在频繁的项目集中用来作为候选项目集的数量。这种支持度的衡量是由 Apriori 原则来指导的。Apriori 原则说明：如果一个项目集是频繁的，那么它的所有子集都是频繁的。

7.K-均值聚类算法

       K-均值是一个对相似的数据进行聚类的迭代算法。它计算出 k 个聚类的中心点，并给某个类的聚类分配一个与其中心点距离最近的数据点。

图 6：K-均值算法的步骤

步骤 1：K-均值初始化

a) 选择一个 k 值。这里我们令 k=3。

b) 将数据点随机地分配给三个聚类。

c) 计算出每个聚类的中心点。图中的红色、蓝色和绿色的星分别代表三个聚类的中心点。

步骤 2：将每一个观测值与一个聚类关联起来

将每一个数据点重新分配给离它最近的一个聚类中心点。如图所示，上边的五个数据点被分配给了蓝星代表的聚类。按照相同的步骤将数据点分配给红色和绿色星代表的聚类中心点。

步骤 3：重新计算中心点

计算新聚类的中心点。如图所示，旧中心点是灰色的，新中心点是红色、蓝色和绿色的。

步骤 4：迭代，然后在数据点所属的聚类不变的时候退出整个过程

重复步骤 2-3，直至每一个聚类中的点不会被重新分配到另一个聚类中。如果在两个连续的步骤中不再发生变化，那么就退出 K-均值算法。

8. 主成分分析（PCA）

        主成分分析（PCA）通过减少变量的数目来使数据变得更加易于探索和可视化。这通过将数据中拥有最大方差的数据抽取到一个被称为「主成分」的新坐标系中。每一个成分都是原始变量的一个新的线性组合，且是两两统计独立的。统计独立意味着这些成分的相关系数是 0。

        第一主成分捕获的是数据中最大方差的数据。第二主成分捕获的是剩下的数据中方差最大但是与第一主成分相互独立的数据。相似地，后续的主成分（例如 PC3、PC4）都是剩下的数据中方差最大的但是与之前的主成分保持独立的数据。

图 7：使用主成分分析方法（PCA），三种初始变量（基因）被降为两种新变量

集成学习技术

        集成意味着通过投票或者取平均值的方式，将多个学习器（分类器）结合起来以改善结果。在分类的时候进行投票，在回归的时候求平均值。核心思想就是集成多个学习器以使性能优于单个学习器。有三种集成学习的方法：装袋（Bagging）、提升（Boosting）和堆叠（Stacking）。本文不涉及堆叠。

9. 随机森林 Bagging

        随机森林（多个学习器）是在装袋决策树（单个学习器）上做的改进。

        Bagging：Bagging的第一步就是在使用 Bootstrap采样方法得到的数据库中创建多个模型，每个生成的训练集都是原始数据集的子集。每个训练集都有相同的大小，但是有些样本重复出现了很多次，有些样本一次未出现。然后，整个原始数据集被用为测试集。那么，如果原始数据集的大小为N，则每个生成的训练集的大小也是 N，唯一（没有重复）样本的大小大约是 2*N/3；测试集的大小也是 N。

         Bagging的第二步就是使用同一个算法在不同的数据集上生成多个模型。然后，我们讨论一下随机森林。在决策树中，每个节点都在最好的、能够最小化误差的最佳特征上进行分支，而随机森林与之不同，我们选择随机分支的特征来构建最佳的分支。进行随机处理的原因在于：即便使用了Bagging，当决策树选择最佳特征来分支的时候，它们最终会有相似的模型和相关联的预测结果。但是用随机子集上的特征进行分支意味着子树做的预测是没有多少相关性的。

10. AdaBoost 提升算法

a）Bagging 是并行集成，因为每个模型都是独立建立的。然而，提升是一个顺序性集成，每个模型都要纠正前面模型的错误分类。

b）Bagging

主要涉及到「简单投票」，每个分类器都投票得到一个最终结果，这个分类结果是由并行模型中的大多数模型做出的；提升则使用「权重投票」。每个分类器都会投票得到一个由大多数模型做出的结果—但是建立这些顺序性模型的时候，给之前误分类样本的模型赋予了较大的权重。Adaboost 指的是适应性提升。

图 9：一个决策树的 Adaboost

        在图9 中，步骤 1、2、3 指的是被称为决策桩（decision stump）的弱学习器（是一个仅依靠一个输入作出决策的 1级决策树；是一种根节点直接连接到叶节点的决策树）。构造决策树的过程会一直持续，直到用户定义了一个弱学习器的数目，或者训练的时候再也没有任何提升的时候。步骤4 结合了之前模型中的 3 个决策桩（所以在这个决策树中就有 3 种分支规则）。

步骤 1：开始用 1 个决策桩来根据 1 个输入变量做决策

数据点的大小说明我们应用了等权重来将它们分为圆形或者三角形。决策桩在图的上半部分用一条水平线来对这些点进行分类。我们可以看到，有两个圆被误分为三角形。所以，我们会赋予这两个圆更大的权重，然后使用另一个决策桩（decision stump）。

步骤 2：转向下一个决策桩，对另一个输入变量进行决策

我们可以看到，之前的步骤中误分类的两个圆要比其余数据点大。现在，第二个决策桩要尝试正确地预测这两个圆。赋予更大权重的结果就是，这两个圆被左边的竖线正确地分类了。但是这又导致了对上面 3 个小圆的误分类。因此，我们要在另一个决策桩对这三个圆赋予更大的权重。

步骤 3：训练另一个决策桩对下一个输入变量进行决策。

上一步误分类的 3 个圆要比其他的数据点大。现在，在右边生成了一条竖线，对三角形和圆进行分类。

步骤 4：结合决策桩

我们结合了之前 3 步的决策桩，然后发现一个复杂的规则将数据点正确地分类了，性能要优于任何一个弱学习器。

结语

回顾一下，本文主要学到的内容：

1. 5 种监督学习技术：线性回归、Logistic 回归、CART（分类和决策树）、朴素贝叶斯法和 KNN。

2. 3 种非监督学习技术：Apriori 算法、K-均值聚类、主成分分析（PCA）。

3. 两种集成学习方法：Bagging 随机森林、AdaBoost 提升。

综上所述，机器学习的基本属性可以总结为以下：

机器学习是（使用样本获取近似函数的）统计学的一个分支。我们有一个确实存在的理论函数或分布用以生成数据，但我们目前不知道它是什么。我们可以对这个函数进行抽样，这些样本选自我们的训练集。

以图片描述任务为例：函数：f⋆（图片）→图片描述，样本：data∈（image，description）。注意：由于一个物体有许多有效的描述，所以描述是文本空间中的一个分布：图片描述〜文本。

机器的目标是找到模型：有足够的表现力来逼近真正的函数，找到一个高效的算法，它使用训练数据找到函数最优解。而且此最优解必须对未知输入有良好的泛化能力。