读书笔记 | 《机器学习》的算法总结 - AI产品经理需要知道的

机器学习.jpg

-- 原创，未经授权，禁止转载 2017.11.06 --

传送门：
机器学习的基本概念（一）：http://www.jianshu.com/p/10fc7e397a3e
机器学习的基本概念（二）：http://www.jianshu.com/p/b3edf9c9f2c8
机器学习模型评估与选择：http://www.jianshu.com/p/c5111d585367

一、算法类别

机器学习的算法繁多，分类方式也很多，如：

• 生成模式 与 判别模式
• 参数 与 非参数 模式
• 监督 与 非监督 模式
• 基于学习任务

最有效的算法分类，是基于学习任务的，它在实践中使用广泛。那么，如何选择合适的算法呢？

通常，我们根据算法的优缺点、训练数据规模、数据质量、任务目标，等等问题综合考虑。当然，选择大家认可度高的算法，更容易得到“不错”的结果。

• 算法总结图

算法按功能类别大致分为13种，下图总结了不同类别算法的优缺点，以及著名代表算法。

算法.png

二、基于学习任务的算法分类

上篇文章讲到，机器学习中，学习方式我们主要分两大类：

• 监督学习 ：训练数据【有】标记信息。
• 无监督学习：训练数据【没有】标记信息。

（其实还会分为半监督学习，强化学习等类型。这里不做过多探讨。）

image image

• 监督学习中，最有代表性的任务是：

  • 分类：对指定的模式进行识别，预测值是离散的。
  • 回归：对指定的模式进行识别，预测值是连续的。

• 无监督学习中，最有代表性的任务是：

  • 聚类：基于数据的内部结构寻找观察样本的自然族群（即集群）。
  • 降维：在保留数据结构和有用性的同时对数据进行压缩。

这里想讨论的，是基于不同的学习任务，常用的算法有哪些，优缺点是什么。
如下图：

监督学习.png

1）分类任务

a）概述

通过对已知分类的数据进行训练和学习，找到这些不同类的特征，再对未分类的数据进行分类。

分类算法通常适用于预测一个类别（或类别的概率），而不是连续的数值。

• 分类算法的流程：
  训练：训练集——>特征选取——>训练——>分类器
  分类：新样本——>特征选取——>分类——>判决

b）应用：

• 判断用户的性别
• 预测用户是否会购买给定的品类
• 判断一条评论是正面的还是负面的

c）算法解释

• 逻辑回归（Logistic Regression）
  简单来说，逻辑回归是一种用于解决二分类（0 or 1）问题的机器学习方法，用于估计某种事物的可能性。它通过 Logistic 函数（即 Sigmoid 函数）将预测映射到 0 到 1 中间，不仅可以预测类别，还可得到近似概率的预测，这对许多需要利用概率辅助的任务很有用。

  介绍一下Sigmoid函数，也称为逻辑函数（Logistic function）：

  

  其函数曲线如下：

  
  

  从上图可以看到sigmoid函数是一个s形的曲线，它的取值在[0, 1]之间，在远离0的地方函数的值会很快接近0或者1。它的这个特性对于解决二分类问题十分重要。

  求解过程：
  1.首先假设误差存在且为高斯分布，等价于真实数据的概率分布。
  2.求出联合概率分布，也就是似然函数。
  3.进行取对数运算，得到对数似然函数l(θ)。
  4.求l(θ)的最大值，得到了最小二乘的策略。
  5.使用梯度下降，让参数逐渐逼近最小二乘法中的最优解。

  • 优点：

    • 实现简单，广泛的应用于工业问题上；
    • 分类时计算量非常小，速度快，存储资源低；
    • 输出有很好的概率解释，算法可以正则化而避免过拟合；

  • 缺点：

    • 在多条或非线性决策边界时性能比较差；
    • 容易欠拟合，一般准确度不太高；
    • 只能处理两分类问题（在此基础上衍生出来的softmax可以用于多分类），且必须线性可分；

• 朴素贝叶斯(Naive Bayes, NB)
  朴素贝叶斯是一种基于贝叶斯定理和特征条件独立假设的分类方法。

  本质上朴素贝叶斯模型就是一个概率表，通过训练数据更新这张表中的概率。为了预测一个新的观察值，朴素贝叶斯算法就是根据样本的特征值在概率表中寻找最大概率的那个类别。

  之所以称之为「朴素」，是因为该算法的核心就是特征条件独立性假设（每一个特征之间相互独立），而这一假设在现实世界中基本是不现实的。

  • 优点：

    • 容易实现并能随数据集的更新而扩展；
    • 对小规模的数据表现很好，能个处理多分类任务，适合增量式训练；
    • 对缺失数据不太敏感，算法也比较简单，常用于文本分类。

  • 缺点：

    • 需要计算先验概率；
    • 需要条件独立假设，分类决策存在错误率；

  • 应用场景：

    • 情感分析、消费者分类

• AdaBoost

  首先要解释一个名词，【集成学习】，就是将多个弱的学习器结合起来组成一个强的学习器。

  目前主要有两种生成方式：

  • Boosting：个体学习器间存在强依赖关系，必须串行生成。
  • Bagging与随机森林：个体之间不存在强依赖关系，可并行生成。

  Boosting族算法最著名的代表就是AdaBoost。

  工作机制类似于：
  1）给定初始训练数据，由此训练出第一个基学习器；
  2）根据基学习器的表现对样本进行调整，在之前学习器做错的样本上投入更多关注；
  3）用调整后的样本，训练下一个基学习器；
  4）重复上述过程 T 次，将 T 个学习器加权结合。

  

  • 优点：

    • 可以自动组合弱分类器，且分类精度很高；
    • 在Adaboost的框架下，可以使用各种回归分类模型来构建弱学习器，非常灵活；
    • 作为简单的二元分类器时，构造简单，结果可理解；
    • 不易发生过拟合；

  • 缺点：

    • 对异常样本敏感，异常样本在迭代中可能会获得较高的权重，影响最终的强学习器的预测准确性；
    • 训练比较耗时；

• 支持向量机SVM
  对于分类学习最基本的想法就是基于训练集的样本空间中，找到一个划分超平面，将不同类别的样本分开。

  超平面有很多，我们希望能找到一个边界，在边界范围之内，都存在划分超平面。如下图中虚线所示，在虚线之内的任意超平面，都能完全划分出不同类别。

  而处于虚线之上的向量，我们称为【支持向量】。因为这两个向量之间的距离，就是我们能找到的具有“最大间隔”的划分超平面。

  SVM

  SVM算法其实就是靠支持向量来计算最大Margin的一个算法，因此将其命名为支持向量机。

  • 优点：
    • 解决小样本下机器学习问题；
    • 解决非线性问题；
    • 无局部极小值问题（相对于神经网络等算法）；
    • 可以很好的处理高维数据集；
    • 泛化能力比较强；
  • 缺点：
    • 对于核函数的高维映射解释力不强，尤其是径向基函数；
    • 对缺失数据敏感；
    • 很难调参，也不能扩展到较大的数据集中；
  • 应用：
    • 文本分类、图像识别；
    • 目前在工业界中，随机森林通常优于支持向量机算法；

• K近邻（K-nearest neighbors, KNN）
  KNN即最近邻算法，其主要过程为：

  1. 计算训练样本和测试样本中每个样本点的距离（常见的距离度量有欧式距离，马氏距离等）；
  2. 对上面所有的距离值进行排序；
  3. 选前k个最小距离的样本；
  4. 根据这k个样本的标签进行投票，得到最后的分类类别；

  

  如何选择一个最佳的K值，这取决于数据。一般情况下，在分类时较大的K值能够减小噪声的影响,但会使类别之间的界限变得模糊。

  近邻算法具有较强的一致性结果。随着数据趋于无限，算法保证错误率不会超过贝叶斯算法错误率的两倍。对于一些好的K值，K近邻保证错误率不会超过贝叶斯理论误差率。

  • 优点：
    • KNN是一种在线技术，新数据可以直接加入数据集而不必进行重新训练;
    • KNN理论简单，容易实现;
  • 缺点：
    • 对于样本容量大的数据集计算量比较大;
    • 样本类别不平衡时，预测偏差比较大;
    • KNN每一次分类都会重新进行一次全局运算，训练时间复杂度为O(n)；
    • k值大小的选择难；
  • 应用：
    • 文本分类、模式识别、聚类分析，多分类领域

• 决策树（Decision Tree, DT）
  其本质是一颗由多个判断节点组成的树，根据特征集取值不同，将样本逐层划分并建立规则，直到某一个样本集合内的所有样本属于同一类。

  在使用模型进行预测时，根据输入参数依次在各个判断节点进行判断游走，最后到叶子节点即为预测结果。

  

  • 分类树
    如果目标变量是标称的，称为分类树；如果目标变量是连续的，称为回归树。分类树是使用树结构算法将数据分成离散类的方法。
    它们通常都是指决策树，或更严谨一点地称之为「分类回归树（CART）」，这也就是非常著名的 CART 的算法。

  • 优点：

    • 决策树易于理解和解释，可以可视化分析，容易提取出规则；
    • 可以同时处理标称型和数值型数据；
    • 测试数据集时，运行速度比较快；
    • 决策树可以很好的扩展到大型数据库中，同时它的大小独立于数据库大小；

  • 缺点：

    • 对缺失数据处理比较困难；
    • 容易出现过拟合问题；
    • 忽略数据集中属性的相互关联；

  • 改进：

    • 对决策树进行剪枝。可以采用交叉验证法和加入正则化的方法；
    • 使用基于决策树的combination算法，如bagging算法，randomforest算法，可以解决过拟合的问题；

  • 应用：

    • 企业管理实践，企业投资决策；

• 深度学习
  深度学习是指能学习极其复杂模式的多层神经网络。该算法使用在输入层和输出层之间的隐藏层对数据的中间表征建模，这也是其他算法很难学到的部分。
  [图片上传失败...(image-e97650-1510761156182)]
  深度学习还有其他几个重要的机制，如卷积和 drop-out 等，这些机制令该算法能有效地学习到高维数据。然而深度学习相对于其他算法需要更多的数据，因为其有更大数量级的参数需要估计。

  • 优点：

    • 在图像、音频和文本等数据上表现优异；
    • 容易对新数据使用反向传播算法更新模型参数；
    • 它们的架构（即层级的数量和结构）能够适应于多种问题，并且隐藏层也减少了算法对特征工程的依赖。

  • 缺点：

    • 需要大量的数据；
    • 难调参；

• 随机森林（Random Forest）RF
  首先要讲一个概念，Bagging(bootstrap aggregation)封袋算法。

  前面讲AdaBoost算法，是Boosting的代表。随机森林是Bagging的代表。

  Bagging：并行式集成学习方法最著名的代表。它抽取训练样本采用自助采样法（bootstrap），所以就叫bootstrap aggregation算法。

  

  1.从原始样本集中抽取训练集。每轮从原始样本集中使用Bootstraping的方法抽取n个训练样本（有放回）。
  共进行k轮抽取，得到k个训练集。（k个训练集之间是相互独立的）
  2.每次使用一个训练集得到一个模型，k个训练集共得到k个模型。
  3.对分类问题：将上步得到的k个模型采用投票的方式得到分类结果；
  对回归问题：计算上述模型的均值作为最后的结果。

  随机森林（RF），顾名思义，是用随机的方式建立一个森林，森林里面有很多的决策树组成，随机森林的每一棵决策树之间是没有关联的。

  在得到森林之后，当有一个新的输入样本进入的时候，就让森林中的每一棵决策树分别进行一下判断，看看这个样本应该属于哪一类（对于分类算法），然后看看哪一类被选择最多，就预测这个样本为那一类。

  在建立每一棵决策树的过程中，有两点需要注意--采样与完全分裂。这是两个随机采样的过程，RF对输入的数据进行 行和列 的采样。

  1.对于行采样，采用有放回的方式，也就是在采样得到的样本集合中，可能有重复的样本。
  假设输入样本为N个，那么采样的样本也为N个。这样使得在训练的时候，每一棵树的输入样本都不是全部的样本，使得相对不容易出现over-fitting。
  2.进行列采样，从M个feature中，选择m个(m << M)。
  3.对采样之后的数据使用完全分裂的方式建立出决策树。
  这样决策树的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本的都是指向的同一个分类。

  一般决策树算法都需要--剪枝，但随机森林不需要，因为两个随机采样过程保证了随机性，所以不剪枝，也不会出现过拟合。

  • 优点：

    • 不容易出现过拟合，因为选择训练样本的时候就不是全部样本。
    • 既可以处理属性为离散值的量，比如ID3算法来构造树，也可以处理属性为连续值的量，比如C4.5算法来构造树。
    • 对于高维数据集的处理能力令人兴奋，它可以处理成千上万的输入变量，并确定最重要的变量，因此被认为是一个不错的降维方法。此外，该模型能够输出变量的重要性程度，这是一个非常便利的功能。
    • 分类不平衡的情况时，随机森林能够提供平衡数据集误差的有效方法

  • 缺点：

    • 随机森林在解决回归问题时并没有像它在分类中表现的那么好，这是因为它并不能给出一个连续型的输出。当进行回归时，随机森林不能够作出超越训练集数据范围的预测，这可能导致在对某些还有特定噪声的数据进行建模时出现过度拟合。
    • 对于许多统计建模者来说，随机森林给人的感觉像是一个黑盒子——你几乎无法控制模型内部的运行，只能在不同的参数和随机种子之间进行尝试。

2）回归

回归

a）概述

回归算法用于连续型分布预测，针对的是数值型的样本，使用回归，可以在给定输入的时候预测出一个数值，这是对分类方法的提升，因为这样可以预测连续型数据而不仅仅是离散的类别标签。

回归的目的就是建立一个回归方程用来预测目标值，回归的求解就是求这个回归方程的回归系数。

b）应用：

房价预测、股票走势或测试成绩等连续变化的案例。

c）算法解释：

• 线性回归（Linear Regression）
  线性回归是处理回归任务最常用的算法之一。该算法的形式十分简单，它期望使用一个超平面拟合数据集（只有两个变量的时候就是一条直线）。如果数据集中的变量存在线性关系，那么其就能拟合地非常好。

  [图片上传失败...(image-13b723-1510761156182)]
  在实践中，简单的线性回归通常被使用正则化的回归方法（LASSO、Ridge 和 Elastic-Net）所代替。正则化其实就是一种对过多回归系数采取惩罚以减少过拟合风险的技术。当然，我们还得确定惩罚强度以让模型在欠拟合和过拟合之间达到平衡。

  • 优点：

    • 实现简单，计算简单；
    • 解释性好，还能通过正则化来降低过拟合的风险；
    • 容易使用随机梯度下降和新数据更新模型权重；

  • 缺点：

    • 不能拟合非线性数据；

  • 逻辑回归与线性回归的关系？
    逻辑回归（Logistic Regression）与线性回归（Linear Regression）都是一种广义线性模型（generalized linear model）。逻辑回归假设因变量 y 服从伯努利分布，而线性回归假设因变量 y 服从高斯分布。
    因此与线性回归有很多相同之处，去除Sigmoid映射函数的话，逻辑回归算法就是一个线性回归。
    可以说，逻辑回归是以线性回归为理论支持的，但是逻辑回归通过Sigmoid函数引入了非线性因素，因此可以轻松处理0/1分类问题。

• 回归树
  回归树（决策树的一种）通过将数据集重复分割为不同的分支而实现分层学习，分割的标准是最大化每一次分离的信息增益。这种分支结构让回归树很自然地学习到非线性关系。

  集成方法，如随机森林（RF）或梯度提升树（GBM）则组合了许多独立训练的树。

  这种算法的主要思想就是组合多个弱学习算法而成为一种强学习算法。在实践中 RF 通常很容易有出色的表现，而 GBM 则更难调参，不过通常梯度提升树具有更高的性能上限。

  • 优点：
    • 参考决策树；
  • 缺点：
    • 参考决策树；

3）聚类

无监督学习.png

a）概述

聚类，就是根据数据的"相似性"将数据分为多类的过程。
所有的聚类算法都试图找到数据的内在结构，以便按照最大的共同点将数据进行归类。

b）应用：

细分客户、新闻聚类、文章推荐等。

c）算法解释：

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

  简单来说，是将相似的对象归到同一个蔟中。蔟内的对象越相似，聚类的效果就越好。

  聚类的度量基于样本点之间的几何距离（即在坐标平面中的距离）。集群是围绕在聚类中心的族群，而集群呈现出类球状并具有相似的大小。

  聚类和分类最大的不同在于，分类的目标事先已知，而聚类则不一样。其产生的结果和分类相同，而只是类别没有预先定义。

  步骤
  1.创建k个点作为k个簇的起始质心（经常随机选择）。
  2.分别计算剩下的元素到k个簇中心的相异度（距离），将这些元素分别划归到相异度最低的簇。
  3.根据聚类结果，重新计算k个簇各自的中心，计算方法是取簇中所有元素各自维度的算术平均值。
  4.将D中全部元素按照新的中心重新聚类。
  5.重复第4步，直到聚类结果不再变化。
  6.最后，输出聚类结果。

  [图片上传失败...(image-18be97-1510761156182)]

  • 优点：

    • 聚类问题的经典算法，算法简单、快速。
    • 对处理大数据集，该算法是相对可伸缩的和高效率的，因为它的复杂度大约是O(nkt)，其中n是所有对象的数目，k是簇的数目,t是迭代的次数。通常k<<n。这个算法通常局部收敛。
    • 算法尝试找出使平方误差函数值最小的k个划分。当簇是密集的、球状或团状的，且簇与簇之间区别明显时，聚类效果较好。

  • 缺点：

    • k-平均方法只有在簇的平均值被定义的情况下才能使用，且对有些分类属性的数据不适合。
    • 要求用户必须事先给出要生成的簇的数目k。
    • 对初值敏感，对于不同的初始值，可能会导致不同的聚类结果。
    • 不适合于发现非凸面形状的簇，或者大小差别很大的簇。
    • 对于"噪声"和孤立点数据敏感，少量的该类数据能够对平均值产生极大影响。

• 层次聚类

  试图在不同层次对数据集进行划分，从而形成树形的聚类结构。数据集的划分可采用“自底向上”的聚合策略，也可采用“自顶向下”的分拆策略。 代表算法：AGNES

  算法过程：

  1、将每个对象归为一类, 共得到N类, 每类仅包含一个对象. 类与类之间的距离就是它们所包含的对象之间的距离.
  2、 找到最接近的两个类并合并成一类, 于是总的类数少了一个.
  3、 重新计算新的类与所有旧类之间的距离.
  4、重复第2步和第3步, 直到最后合并成一个类为止(此类包含了N个对象).

  [图片上传失败...(image-3d2ef-1510761156182)]

  • 优点：
    • 集群不再需要假设为类球形，也可以扩展到大数据集。
  • 缺点：
    • 需要设定集群的数量（即在算法完成后需要保留的层次）。

4）降维

a）概述

降维，通过某种数学变换将原始高维属性空间转变为一个低维子空间，在这个子空间中样本密度大幅提高，距离计算也变得更加容易。

降维的方法可以分为：

• 线性方法：PCA、LDA；
• 非线性方法：核PCA、多层自动编码；

说到维度，其目的是用来进行特征选择和特征提取，注意特征选择和特征提取这二者的不同之处：
【特征选择】：选择重要特征子集，删除其余特征。
【特征提取】：由原始特征形成较少的新特征。

• 降维的作用：
  • 降低时间复杂度和空间复杂度；
  • 节省了提取不必要特征的开销；
  • 去掉数据集中夹杂的噪声；
  • 较简单的模型在小数据集上有更强的鲁棒性；
  • 当数据能有较少的特征进行解释，我们可以更好的解释数据，使得我们可以提取知识；
  • 实现数据可视化；

c）算法解释

• 主成分分析算法 （Principal Component Analysis） PCA
  主成分分析算法是最常用的线性降维方法，它的目标是通过某种线性投影，将高维的数据映射到低维的空间中表示，并期望在所投影的维度上数据的方差最大，以此使用较少的数据维度，同时保留住较多的原数据点的特性。

  通俗的理解，如果把所有的点都映射到一起，那么几乎所有的信息（如点和点之间的距离关系）都丢失了，而如果映射后方差尽可能的大，那么数据点则会分散开来，以此来保留更多的信息。

  可以证明，PCA是丢失原始数据信息最少的一种线性降维方式。（实际上就是最接近原始数据，但是PCA并不试图去探索数据内在结构）

  image

  • 优点：

    • 可处理大规模数据集
    • 无需在数据上进行假设

  • 缺点：

    • 难以搞定非线性数据
    • 难以理解结果的意义

结束

算法还有很多，且学且珍惜~~

最后，我的目的是成为一名ai pm，求推荐~

• 参考文章：
  http://blog.jobbole.com/60809/
  http://blog.csdn.net/starzhou/article/details/72614795
  http://www.jianshu.com/p/a0e405dffa3a

-- 原创，未经授权，禁止转载 2017.11.06 --