精华内容
下载资源
问答
  • 机器学习算法总结

    2021-02-25 01:18:25
    本文来自于网络,本文主要介绍了机器学习领域涉及到很多的算法和模型中一些常见的算法机器学习(MachineLearning,ML)是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。专门...
  • 机器学习算法总结ppt

    2018-03-13 20:53:27
    机器学习算法总结ppt机器学习算法总结ppt机器学习算法总结ppt机器学习算法总结ppt
  • 十大常用机器学习算法总结(持续完善).pdf
  • 此资源为自己编写,主要讲述了传统机器学习的k近邻、朴素贝叶斯、svm、感知机、逻辑回归等算法,对其的思想和优缺点做了总结。 由于此文档仅为学习时笔记,若有问题还请见谅,也希望读者能够指出。
  • 机器学习算法概述 “机器智能是人类永远需要的一项发明。”— Nick Bostrom. ​ 如果您可以回顾几年前的AI并将其与现在的AI进行比较,您会惊讶地发现AI的发展速度随着时间的增长呈指数级增长。 ​ 它已扩展到...

    机器学习算法概述

    “机器智能是人类永远需要的一项发明。”— Nick Bostrom.

    ​ 如果您可以回顾几年前的AI并将其与现在的AI进行比较,您会惊讶地发现AI的发展速度随着时间的增长呈指数级增长。

    ​ 它已扩展到各种领域,例如ML,Expert Systems,NLP等数十个领域。

    ​ 尽管AI的思路是构建可以自行思考和执行的更智能的系统,但仍然需要对其进行训练。

    ​ AI的ML领域是为实现非常精确的目标而创建的,它引入了多种算法,从而可以更顺畅地进行数据处理和决策。

    什么是机器学习算法?

    机器学习算法是任何模型背后的大脑,可让机器学习并使其更智能。

    ​ 这些算法的工作方式是,为它们提供第一批数据,并且随着时间的流逝和算法的准确性的提高,额外的数据也被引入到算法中。

    ​ 定期将算法应用于新数据和新经验的过程可提高机器学习的整体效率。

    ​ 机器学习算法对于与分类,预测建模和数据分析相关的各种任务至关重要。

    “机器学习方面的突破将价值十个微软。”- Bill Gates

    机器学习算法的类型

    ​ 在本节中,我们将重点介绍现有的各种ML算法。 ML算法的三个主要范例是:

    监督学习

    ​ 顾名思义,监督算法通过定义一组输入数据和预期结果来工作。 通过在训练数据上迭代执行功能并让用户输入控制参数来改进模型。 如果发现其映射的预测正确,则认为该算法是成功的。

    监督学习

    无监督学习

    ​ 在监督算法在用户标记的数据上进行输出预测时,将这些训练结果在没有用户干预的情况下来训练未标记数据。

    ​ 这个算法可以对数据进行分类和分组,以识别一些隐藏或未发现的类别,通常用作监督学习的初步步骤。

    无监督学习

    强化学习

    ​ 强化学习算法旨在在探索和开发之间找到完美的平衡,而无需标记数据或用户干预。

    ​ 这些算法通过选择一个动作并观察结果来工作,在此基础上,它了解结果的准确程度。 反复重复此过程,直到算法选择正确的策略为止。

    流行的机器学习算法

    ​ 在熟悉了几种类型的ML算法之后,我们继续演示一些流行的算法。

    1.线性回归

    ​ 线性回归是一种监督型ML算法,可帮助找到点集合的近似线性拟合。

    ​ 线性回归的核心是识别两个变量之间关系的线性方法,其中两个值之一是从属值,另一个是独立的。

    ​ 其背后的原理是要理解一个变量的变化如何影响另一个变量,从而导致正或负的相关关系。

    线性回归以y = a + bx的形式表示为一条线

    ​ 该线称为回归线,由线性方程Y = a * X + b表示。

    ​ 在此等式中:

    • Y —因变量
    • a —坡度
    • X-自变量
    • b-截距

    ​ 该算法适用于预测输出是连续的并且具有恒定斜率的情况,例如:

    • 估算销售额
    • 评估风险
    • 天气数据分析
    • 预测分析
    • 客户调查结果分析
    • 优化产品价格

    1. Logistic回归

    ​ Logistic回归算法通常用于二进制分类问题,在这些情况下,事件通常会导致通过或失败,正确或错误这两个值中的任何一个。

    ​ 最适合需要预测因变量将属于两类之一的概率的情况。

    ​ 该算法的常见用例是确定给定的笔迹是否与所讨论的人匹配,或未来几个月的油价是否会上涨。

    ​ 通常,回归可用于实际应用中,例如:

    • 信用评分
    • 癌症检测
    • 地理图像处理
    • 手写识别
    • 图像分割与分类
    • 衡量营销活动的成功率
    • 预测某种产品的收入
    • 特定日子会发生地震吗?
    1. 决策树

    决策树算法属于监督型机器学习,用于解决回归和分类问题。 目的是使用决策树从观察并处理每个级别的结果。

    ​ 决策树是一种自上而下的方法,其中从训练数据中选择最合适的属性作为根,并对每个分支重复该过程。 决策树通常用于:

    • 建立知识管理平台
    • 选择要旅行的航班
    • 预测酒店的入住高峰日期
    • 向客户建议要买什么车
    • 预测预测并确定各个领域的可能性

    决策树算法
    1. Apriori机器学习算法

    它是几种在线平台上经常推荐的算法。

    ​ 它通过在数据集中搜索通用的数据进行操作,然后在它们之间建立关联。

    ​ 它通常用于数据挖掘和从关系数据库学习关联规则。

    ​ 该算法背后的思想是保持相关项目尽可能扩展到更大的集合,以创建更有用的关联。

    ​ 该算法的应用包括突出显示市场中的购买趋势。

    ​ 此外,它更易于实现,并且可以用于大型数据集。

    1. 朴素贝叶斯

    朴素贝叶斯分类器被归类为高效的监督ML算法,并且是最简单的贝叶斯网络模型之一。

    ​ 它通过对数据应用贝叶斯定理,并假设给定变量的值的情况下,每对特征之间都具有条件独立性。

    朴素贝叶斯分类

    ​ 简而言之,考虑到事件B已经发生,用它来找到事件A发生的可能性。 朴素贝叶斯最适合-

    • 过滤垃圾邮件
    • 推荐系统,例如Netflix
    • 对有关技术,政治或体育的新闻文章进行分类
    • 社交媒体上的情感分析
    • 面部识别软件
    1. 人工神经网络

    ​ 仿照人脑建模的人工神经网络实现了神经元的巨大迷宫,或者说简化并模拟了节点之间相互传递信息的过程。

    ​ 这些相互连接的节点通过边缘将数据瞬时传递给其他节点,以进行快速处理,从而使学习更加顺畅。

    ​ 人工神经网络从数据集中学习,而不是通过一组特定的规则进行编程。 能够对非线性过程进行建模,它们可以在以下领域中实施:

    • 模式识别
    • 网络安全
    • 数据挖掘
    • 检测患者的癌症种类

    人工神经网络算法
    1. K-Means聚类

    ​ k-均值聚类是一种迭代的无监督学习算法,可将n个观察值划分为k个簇,每个观察值均属于最近的簇均值。

    K-means算法的步骤

    ​ 简而言之,该算法基于数据点的相似性来聚合数据点的集合。 它的应用范围包括在Python,SciPy,Sci-Kit Learn和data mining等编程语言和库中聚集相似和相关的网络搜索结果。

    K均值聚类的实际应用-

    1. 识别假新闻

    2. 垃圾邮件检测和过滤

    3. 按类型对书籍或电影进行分类

    4. 规划城市时的热门交通路线

    5. 支持向量机

    ​ 支持向量机被归类为监督机器学习算法,主要用于分类和回归分析

    ​ 该算法通过建立一个可以将新示例和新数据分配给一个类别的模型来工作,每个类别间可以容易地区别开来。

    ​ 在维数大于样本数的情况下,SVM非常有效,并且存储效率极高。

    高效的支持向量机算法

    ​ SVM应用程序可以在以下领域找到:

    • 人脸检测
    • 影像分类
    • 文本和超文本分类
    • 手写识别
    • 药物疗法的发现
    • 生物信息学-蛋白质,基因,生物学或癌症分类。
    1. K近邻算法

    ​ K近邻是一种用于回归和分类问题的监督ML算法。

    ​ 通常用于模式识别,该算法首先存储并使用距离函数识别数据中所有输入之间的距离,选择最接近中心点的k个指定输入并输出:

    • 最经常出现的标签(用于分类)
    • k个最近邻居的平均值(用于回归)

    K近邻算法

    ​ 该算法的实际应用包括:

    • 指纹检测
    • 信用评级
    • 预测股市
    • 分析洗钱
    • 银行破产
    • 汇率
    1. 降维算法

    ​ 降维算法通过使用两种主要方法(特征选择或特征提取)之一减少数据集中的维度空间或随机变量的数量来工作。

    ​ 此算法通常用于预处理数据集并删除冗余特征,从而使算法更容易训练模型。

    ​ 此算法还具有一些不错的好处,例如:

    • 内储需求低
    • 所需的计算能力更少
    • 精度更高
    • 降低噪音

    ​ 一些著名的降维算法是:

    • 主成分分析
    • 线性判别分析
    • 局部线性嵌入
    • 多维缩放
    1. 主成分分析

    ​ 主成分分析是ML的无监督算法之一,主要用于通过使用特征消除或特征提取来缩小特征空间的维数

    ​ 它也是探索性数据分析和建立预测模型的工具。 需要标准化的数据,PCA可以作为帮助:

    • 图像处理
    • 电影推荐系统
    • 计算数据协方差矩阵
    • 对协方差矩阵执行特征值分解
    • 优化多个通信通道中的功率分配

    主成分分析法

    ​ PCA旨在减少数据集中的冗余,使其更简单而又不影响准确性。 它通常部署在图像处理和风险管理领域。

    1. 随机森林

    ​ 随机森林通过实现决策树使用多种算法来解决分类,回归和其他类似问题

    ​ 它的工作方式是,创建带有随机数据集的决策树堆,并在其上反复训练模型以获得接近准确的结果。

    ​ 最后,将来自这些决策树的所有结果组合在一起,以识别出最常出现在输出中的最合适的结果。

    随机森林

    ​ 可以在以下领域找到“随机森林”应用程序:

    1. 银行账户,信用卡欺诈检测

    2. 检测并预测药物的药物敏感性

    3. 通过分析患者的病历来识别患者的疾病

    4. 预测购买特定股票时的估计损失或利润

    5. 梯度增强和Ada增强

    ​ 增强是一种用于集成ML算法的技术,可将弱学习者转换为强学习者。 当数据丰富时,需要使用增强算法,并且我们试图减少监督学习中的偏差和方差。 以下是两种流行的增强算法。

    • 梯度增强

    ​ 通常以迭代方式(例如决策树)构建预测模型,将梯度增强算法用于分类和回归问题。 通过对强者的错误进行培训,从而提高了弱者的学习能力,从而获得了一个比较准确的学习者。

    • Ada增强

    ​ AdaBoost是Adaptive Boosting的缩写,当弱学习者失败时,它会改进模型。 它通过修改附加到样本中实例的权重以将精力更多地集中在困难实例上来实现,然后,弱学习者的输出将被合并以形成加权总和,并被视为最终的提升后的输出。

    结论:

    ​ 机器学习算法对于数据科学家来说至关重要,因为它们在现实世界中的应用日益广泛。 使用上述各种算法,您可以找到最适合解决问题的算法。 尽管这些算法有有监督也有无监督,但它们可以处理各种任务,并且能够与其他算法同步工作。

    作者:Claire D.

    deephub翻译组:孟翔杰

    展开全文
  • 上一篇 机器学习算法总结之Boosting family:AdaBoost提到Boost但是没说它的整个框架及分类,在这里记一下。 Boosting(提升方法) = 加法模型 + 前向分步算法 + 损失函数 AdaBoost = Boosting + 损失函数是指数...

    写在前面

    上一篇 机器学习算法总结之Boosting family:AdaBoost 提到Boost但是没说它的整个框架及分类,在这里记一下。

    • Boosting(提升方法) = 加法模型 + 前向分步算法 + 损失函数
    • AdaBoost = Boosting + 损失函数是指数函数(基函数任意)
    • Boosting Tree(提升树) = Boosting + 基函数是决策树(损失函数任意)

    所以从上面的结构可以看出Boosting是一个大的概述性的框架/算法,而AdaBoost 和Boosting Tree是其中的子集/特例。

    常用的损失函数主要包括:

    1)指数损失函数:决定了Adaboost必须进行加权取样(权重由错误率决定),以进行下一个模型的参数学习,并且决定了最终模型也是加权累计

    2)平方误差损失函数:决定了BRT的下一个模型应该学习前一个模型的残差

    3)一般损失函数:决定了GBRT/GBDT的下一个模型应该学习前一个模型的梯度(残差近似)

     

    1.提升树(Boosting Tree)简介

    提升树是以分类树或者回归树为基本分类器的提升方法。对分类问题决策树是二叉分类树,对回归问题决策树是二叉回归树。

    提升树模型可以表示为决策树的加法模型:

    f_{M}(x)=\sum_{m=1}^{M} T\left(x ; \Theta_{m}\right)

    其中T(x;theta)表示决策树;theta为决策树的参数,M为树的个数

     

    提升树算法采用的也是前向分步算法(具体可以参考之前的一篇:机器学习算法总结之Boosting:AdaBoost),首先确定初始提升树f0(x)=0,第m步的模型为:

    \LARGE f_{m}(x)=f_{m-1}(x)+T\left(x ; \Theta_{m}\right)

    通过经验风险极小化确定下一棵树的参数

    \LARGE \hat{\Theta}_{m}=\arg \min _{\Theta_{m}} \sum_{i=1}^{N} L\left(y_{i}, f_{m-1}\left(x_{i}\right)+T\left(x_{i} ; \Theta_{m}\right)\right)

    2.提升树算法

    根据前述Boosting框架中三个条件的不同,可以将提升树细分为几种情况:

    (1)BDT(提升决策树,二分类):二叉分类树 + 指数函数 → 加权

             可以发现其实就是讲AdaBoost中的基本分类器限定为二分类模型,可以说是AdaBoost的特例。

            下面就不再赘述了

    (2)BRT(提升回归树):二叉回归树 + 平方误差函数 → 残差

    (3)GBDT(梯度提升决策树):二叉回归树(或分类树) +普通损失函数 → 损失函数的负梯度

            当损失函数式平方误差函数时,就等于BRT

    2.1  BRT算法推导

    已知一个训练数据集T={(x1,y1),(x2,y2),…,(xN,yN)},X为输入空间,Y为输出空间。如果将输入空间X划分为J个不相交的区域R1,R2…,RJ,并且在每个区域上确定输出的常量cj,那么树可以表示为:

    \LARGE T(x ; \Theta)=\sum_{j=1}^{J} c_{j} I\left(x \in R_{j}\right)

    其中,参数:\Theta=\left\{\left(R_{1}, c_{1}\right),\left(R_{2}, c_{2}\right), \cdots,\left(R_{J}, c_{J}\right)\right\}表示树的区域划分和各个区域上的常数,J是回归树的复杂度即叶结点个数。BRT采用的前向回归算法已在第一部分给出,当采用平方误差作为损失函数时:

    \LARGE L(y, f(x))=(y-f(x))^{2}

    \LARGE \begin{aligned} L(y,& f_{m-1}(x)+T\left(x ; \Theta_{m}\right) ) \\ &=\left[y-f_{m-1}(x)-T\left(x ; \Theta_{m}\right)\right]^{2} \\&=\left t[r-T\left(x ; \Theta_{m}\right)\right]^{2} \end{aligned}

    其中:r=y-f(x)为模型拟合数据的残差。

    给出提升回归树算法的具体步骤:

    2.2 举个栗子(统计学习方法P149)

     

    3.  梯度提升树(GBDT)

    GBDT也是Boosting家族的一个重要成员,GBDT有很多简称,有GBT(Gradient Boosting Tree) GTB(Gradient Tree Boosting ) GBRT(Gradient Boosting Regression Tree) MART(Multiple Additive Regression Tree) 其实都是一种算法。 

    GBDT的弱学习器限定了只能使用CART回归树模型,在GBDT的迭代中,假设我们前一轮迭代得到的强学习器是ft−1(x), 损失函数是L(y,ft−1(x)), 我们本轮迭代的目标是找到一个CART回归树模型的弱学习器ht(x),让本轮的损失损失L(y,ft(x))=L(y,ft−1(x)+ht(x))最小。也就是说,本轮迭代找到决策树,要让样本的损失尽量变得更小。从上面的描述可以看出,GBDT也是使用的前向分布算法和加法模型。

    当损失函数时确定的平方损失或者指数损失时,每一步优化是很简单的。但是在多种多样的损失函数条件下,怎么找到这个合适的拟合量?

    3.1 GBDT的负梯度拟合

    针对一个一般损失函数,Freidman提出了梯度提升的算法,利用损失函数的负梯度在当前模型的值

    \LARGE -\left[\frac{\partial L\left(y, f\left(x_{i}\right)\right)}{\partial f\left(x_{i}\right)}\right]_{f(x)=f_{m, 1}(x)}

    来拟合本轮损失的近似值,进而拟合一个回归树。

    3.2 GBDT回归算法

    我们知道了怎么去找到这个拟合值,接下来就可以生成GBDT模型了。

    输入:训练集样本T=\left\{\left(x, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots\left(x_{m}, y_{m}\right)\right\}, 最大迭代次数T, 损失函数L。

    输出:强学习器f(x)

    (1)初始化弱学习器:(是只有一个根节点的树)

                                     \LARGE f_{0}(x)=\arg \min _{\boldsymbol{c}} \sum_{i=1}^{N} L\left(y_{i}, c\right)

    (2)对迭代次数t= 1~T:

            (a)对样本i = 1~m,计算负梯度:(也就是常说的“残差”,但是这里度梯度计算的是残差的近似值)

                                    \LARGE r_{t i}=-\left[\frac{\partial L\left(y_{i}, f\left(x_{i}\right)\right)}{\partial f\left(x_{i}\right)}\right]_{f(x)=f_{t-1}(x)}

     

       (b)利用\large \left(x_{i}, r_{t i}\right)拟合一个回归树,得到第t颗树的叶结点区域\large R_{t j}(j=1,2,...,J,其中J为叶结点个数)

            (c)对j=1,2,...,J,计算最佳拟合值:(线性搜索估计叶节点区域的值,使得损失函数极小化)

                                      \LARGE c_{m j}=\arg \min _{c} \sum_{x_{i} \in R_{w}} L\left(y_{i}, f_{m-1}\left(x_{i}\right)+c\right)

           (d)更新学习器:

                                      \LARGE f_{m}(x)=f_{m-1}(x)+\sum_{i=1}^{J} c_{m j} I\left(x \in R_{m j}\right)

    (3)得到强学习器表达式:

                                    \LARGE \hat{f}(x)=f_{M}(x)=\sum_{m=1}^{M} \sum_{j=1}^{J} c_{m j} I\left(x \in R_{m j}\right)

     

    3.3  GBDT分类算法

    首先明确一点,GBDT无论用于分类还是回归问题一直都是使用CART回归树。GBDT的分类算法从思想上和GBDT的回归算法没有区别,但是由于样本输出不是连续的值,而是离散的类别,导致我们无法直接从输出类别去拟合类别输出的误差。为了解决这一问题,可以用类似于逻辑回归的对数似然函数,也就是用的是类别的预测概率值和真实概率值的差来拟合。

    3.3.1 GBDT二元分类算法

    对于二元分类GBDT问题,

    • 可以选择损失函数为:

                                              \large L(y, f(x))=\log (1+\exp (-y f(x)))

    • 则此时的负梯度误差为:

                                              \large r_{t i}=-\left[\frac{\partial L\left(y, f\left(x_{i}\right)\right) )}{\partial f\left(x_{i}\right)}\right]_{f(x)=f_{t-1}(x)}=y_{i} /\left(1+\exp \left(y_{i} f\left(x_{i}\right)\right)\right)

    • 各个叶节点的最佳残差拟合值为:

                                             ​​​​​​​\large c_{t j}=\underbrace{\arg \min }_{c} \sum_{x_{i} \in R_{t j}} \log \left(1+\exp \left(-y_{i}\left(f_{t-1}\left(x_{i}\right)+c\right)\right)\right)

    • 由于上式比较难优化,一般选择使用近似值替代:

                                             ​​​​​​​\large c_{t j}=\sum_{x_{i} \in R_{t j}} r_{t i} / \sum_{x_{i} \in R_{t j}}\left|r_{t i}\right|\left(1-\left|r_{t i}\right|\right)

    3.3.2  GBDT多元分类算法

    对于多元分类问题

    • 假设有K类,则此时对数似然函数为:

                                            \large L(y, f(x))=-\sum_{k=1}^{K} y_{k} \log p_{k}(x)​​​​​​​

    • 其中如果样本输出类别为k, 则yk = 1。第k类的概率为:

                                           \large p_{k}(x)=\exp \left(f_{k}(x)\right) / \sum_{l=1}^{K} \exp \left(f_{l}(x)\right)

     

    • 结合上述两式,可以算出第t轮的第i个样本对应类别 l 的负梯度误差为

                                          \large r_{t i l}=-\left[\frac{\partial L\left(y_{i}, f\left(x_{i}\right)\right) )}{\partial f\left(x_{i}\right)}\right]_{f_{k}(x)=f_{l, t-1}(x)}=y_{i l}-p_{l, t-1}\left(x_{i}\right)

     

      观察可以发现,其实这里的误差啊就是样本i对应类别l 的真实概率和(t-1)轮预测概率的差值。

    • 叶节点的最佳残差拟合值为

                                          \large c_{t j l}=\underbrace{\arg \min }_{c_{j l}} \sum_{i=0}^{m} \sum_{k=1}^{K} L\left(y_{k}, f_{t-1, l}(x)+\sum_{j=0}^{J} c_{j l} I\left(x_{i} \in R_{t j}\right)\right)

     

    • 由于上式比较难优化,一般选择使用近似值代替:

                                          ​​​​​​​\large c_{t j l}=\frac{K-1}{K} \frac{\sum_{x_{i} \in R_{t j}} r_{t i l}}{\sum_{x_{i} \in R_{i l}}\left|r_{t i l}\right|\left(1-\left|r_{t i l}\right|\right)}

    关于GBDT多分类问题的实践可以参考:机器学习算法GBDT的面试要点总结-上篇


    3.4 GBDT常用损失函数

    差不多前面重要的算法也都讲完了,接下来稍微总结一下。

    对于分类算法,其损失函数一般有对数损失函数和指数损失函数两种

    对于回归算法,其损失函数一般有均方差、绝对损失、Huber损失、分位数损失四种。

    ps.(1)Huber损失(Huber Loss wiki),它是均方差和绝对损失的折中,即对于远离中心的异常点,采用绝对损失,而中心附近的点采用均方差。这个界限一般用分位数点度量。

    pps.(2)分位数损失:

                                              \large L(y, f(x))=\sum_{y \geq f(x)} \theta|y-f(x)|+\sum_{y<f(x)}(1-\theta)|y-f(x)|

    其中theta为分位数,需要我们在回归前指定。对应的负梯度误差为:

                                             \large r\left(y_{i}, f\left(x_{i}\right)\right)=\left\{\begin{array}{ll}{\theta} & {y_{i} \geq f\left(x_{i}\right)} \\ {\theta-1} & {y_{i}<f\left(x_{i}\right)}\end{array}\right.

    ppps. 对于Huber损失和分位数损失,只要用于健壮回归,也就是减少异常点对损失函数的影响。

    3.5 GBDT正则化

    和所有机器学习算法一样,GBDT也免不了会出现过拟合风险,需要正则化来减弱,主要有三种形式:

    • 第一种是和Adaboost类似的正则化项,即步长(learning rate)。定义为ν,对于前面的弱学习器的迭代

                                            \large f_{k}(x)=f_{k-1}(x)+h_{k}(x)

           如果我们加上了正则化项,则有

                                          \large f_{k}(x)=f_{k-1}(x)+\nu h_{k}(x)

        ν的取值范围为0<ν≤1。对于同样的训练集学习效果,较小的ν意味着我们需要更多的弱学习器的迭代次数。通常我们用步长和迭代最大次数一起来决定算法的拟合效果。

    • 第二种正则化的方式是通过子采样比例(subsample)。取值为(0,1]。注意这里的子采样和随机森林不一样,随机森林使用的是放回抽样,而这里是不放回抽样。如果取值为1,则全部样本都使用,等于没有使用子采样。如果取值小于1,则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差,即防止过拟合,但是会增加样本拟合的偏差,因此取值不能太低。推荐在[0.5, 0.8]之间。使用了子采样的GBDT有时也称作随机梯度提升树(Stochastic Gradient Boosting Tree, SGBT)。由于使用了子采样,程序可以通过采样分发到不同的任务去做boosting的迭代过程,最后形成新树,从而减少弱学习器难以并行学习的弱点。
    • 第三种是对于弱学习器即CART回归树进行正则化剪枝。与之前一篇决策树内容讲过的相同。(机器学习中树模型算法总结之 决策树(下)

     

    小结

    GBDT主要的优点有:

    1) 可以灵活处理各种类型的数据,包括连续值和离散值。

    2) 在相对少的调参时间情况下,预测的准备率也可以比较高。这个是相对SVM来说的。

    3)使用一些健壮的损失函数,对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。

    GBDT的主要缺点有:

    1)由于弱学习器之间存在依赖关系,难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行。

    由于GBDT算法的卓越性,使其成为机器学习研究必须掌握的算法之一,很多面试的问题也都会涉及这个方面,包括其原理、实现以及参数调优等。目前GBDT的算法比较好的库是xgboost,sklearn。

     

    reference

    统计学习方法

    梯度提升树(GBDT)原理小结

    以上~

    2018.04.18

    展开全文
  • 对《统计学习方法》这本书中介绍的各种算法进行了总结
  • 机器学习算法总结--GBDT

    万次阅读 2017-02-23 17:09:55
    机器学习常见算法个人总结(面试用) xgboost入门与实战(原理篇) 简介 GBDT是一个基于迭代累加的决策树算法,它通过构造一组弱的学习器(树),并把多颗决策树的结果累加起来作为最终的预测输出。 算法介绍GBDT是...

    参考如下

    简介

    GBDT是一个基于迭代累加的决策树算法,它通过构造一组弱的学习器(树),并把多颗决策树的结果累加起来作为最终的预测输出。

    算法介绍

    GBDT是希望组合一组弱的学习器的线性组合,即有:

    F=argminEx,y[L(y,F(x))]F(x;pm,am)=m=0Mpmh(x;am)

    上述公式中 pm 表示步长,我们可以在函数空间形式上使用梯度下降法求解,首先固定 x ,然后对F(x)求其最优解。下面先给出框架流程:

    这里写图片描述

    我们需要做的是估计 gm(x) ,它是梯度方向;通过使用决策树实现来逼近 gm(x) ,使得两者之间的距离尽可能的近,而距离的衡量方式有多种,包括均方误差和LogLoss误差。下面给出使用LogLoss损失函数的具体推导:

    L(y,F)=log(1+exp(2yF))y[1,1]

    Step1 首先求解初始值 F0 ,令其偏导为0。(实现时是第1棵树需要拟合的残差):

    这里写图片描述

    Step 2 估计 gm(x) ,并用决策树对其进行拟合。 gm(x) 是梯度,实现时是第 m 棵树需要拟合的残差:

    这里写图片描述

    Step 3 使用牛顿法求解下降方向步长。rjm是拟合的步长,实现时是每棵树的预测值。(通常实现中这一步是被省略的,改为使用Shrinkage的策略通过参数设置步长,避免过拟合。

    这里写图片描述

    Step 4 预测时只需要把每棵树的预测值乘以缩放因子然后相加即可得到最终的预测值:

    p=predict(0)+m=1Mshrinkagepredict(dm)

    若需要预测值输出区间在 [0,1] ,可作如下转换:
    probability=11+e2predict

    GBDT中的树是回归树,不是分类树。

    RF与GBDT对比

    (1)RF中树的棵树是并行生成的;GBDT中树是顺序生成的;两者中过多的树都会过拟合,但是GBDT更容易过拟合

    (2)RF中每棵树分裂的特征比较随机;GBDT中前面的树优先分裂对大部分样本区分的特征,后面的树分裂对小部分样本区分特征;

    (3)RF中主要参数是树的棵数;GBDT中主要参数是树的深度,一般为1

    Shrinkage

    Shrinkage认为,每次走一小步逐步逼近的结果要比每次迈一大步逼近结果更加容易避免过拟合。

    y(1i)=y(1i1)+stepyi

    优缺点

    优点

    1. 精度高
    2. 能处理非线性数据
    3. 能处理多特征类型
    4. 适合低维稠密数据
    5. 模型可解释性好
    6. 不需要做特征的归一化,可以自动选择特征
    7. 能适应多种损失函数,包括均方误差和LogLoss

    缺点

    1. boosting是个串行的过程,所以并行麻烦,需要考虑上下树之间的联系
    2. 计算复杂度大
    3. 不使用高维稀疏特征

    调参

    1. 树的个数 100~10000
    2. 叶子的深度 3~8
    3. 学习速率 0.01~1
    4. 叶子上最大节点树 20
    5. 训练采样比例 0.5~1
    6. 训练特征采样比例 (n)

    xgboost

    xgboost是boosting Tree的一个很牛的实现,它在最近Kaggle比赛中大放异彩。它 有以下几个优良的特性:

    1. 显示的把树模型复杂度作为正则项加到优化目标中。
    2. 公式推导中用到了二阶导数,用了二阶泰勒展开。
    3. 实现了分裂点寻找近似算法。
    4. 利用了特征的稀疏性。
    5. 数据事先排序并且以block形式存储,有利于并行计算。
    6. 基于分布式通信框架rabit,可以运行在MPI和yarn上。(最新已经不基于rabit了)
    7. 实现做了面向体系结构的优化,针对cache和内存做了性能优化。

    在项目实测中使用发现,Xgboost的训练速度要远远快于传统的GBDT实现,10倍量级。

    特点

    这部分内容参考了知乎上的一个问答—机器学习算法中GBDT和XGBOOST的区别有哪些?,答主是wepon大神

    1.传统GBDT以CART作为基分类器,xgboost还支持线性分类器,这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归(分类问题)或者线性回归(回归问题)。 —可以通过booster [default=gbtree]设置参数:gbtree: tree-based models/gblinear: linear models

    2.传统GBDT在优化时只用到一阶导数信息,xgboost则对代价函数进行了二阶泰勒展开,同时用到了一阶和二阶导数。顺便提一下,xgboost工具支持自定义代价函数,只要函数可一阶和二阶求导。 —对损失函数做了改进(泰勒展开,一阶信息g和二阶信息h)

    3.xgboost在代价函数里加入了正则项,用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲,正则项降低了模型variance,使学习出来的模型更加简单,防止过拟合,这也是xgboost优于传统GBDT的一个特性
    —正则化包括了两个部分,都是为了防止过拟合,剪枝是都有的,叶子结点输出L2平滑是新增的。

    4.shrinkage and column subsampling —还是为了防止过拟合

    (1)shrinkage缩减类似于学习速率,在每一步tree boosting之后增加了一个参数n(权重),通过这种方式来减小每棵树的影响力,给后面的树提供空间去优化模型。

    (2)column subsampling列(特征)抽样,说是从随机森林那边学习来的,防止过拟合的效果比传统的行抽样还好(行抽样功能也有),并且有利于后面提到的并行化处理算法。

    5.split finding algorithms(划分点查找算法):
    (1)exact greedy algorithm—贪心算法获取最优切分点
    (2)approximate algorithm— 近似算法,提出了候选分割点概念,先通过直方图算法获得候选分割点的分布情况,然后根据候选分割点将连续的特征信息映射到不同的buckets中,并统计汇总信息。
    (3)Weighted Quantile Sketch—分布式加权直方图算法
    这里的算法(2)、(3)是为了解决数据无法一次载入内存或者在分布式情况下算法(1)效率低的问题,以下引用的还是wepon大神的总结:

    可并行的近似直方图算法。树节点在进行分裂时,我们需要计算每个特征的每个分割点对应的增益,即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下,贪心算法效率就会变得很低,所以xgboost还提出了一种可并行的近似直方图算法,用于高效地生成候选的分割点。

    6.对缺失值的处理。对于特征的值有缺失的样本,xgboost可以自动学习出它的分裂方向。 —稀疏感知算法

    7.Built-in Cross-Validation(内置交叉验证)

    XGBoost allows user to run a cross-validation at each iteration of the boosting process and thus it is easy to get the exact optimum number of boosting iterations in a single run.
    This is unlike GBM where we have to run a grid-search and only a limited values can be tested.

    8.continue on Existing Model(接着已有模型学习)

    User can start training an XGBoost model from its last iteration of previous run. This can be of significant advantage in certain specific applications.
    GBM implementation of sklearn also has this feature so they are even on this point.

    9.High Flexibility(高灵活性)

    **XGBoost allow users to define custom optimization objectives and evaluation criteria.
    This adds a whole new dimension to the model and there is no limit to what we can do.**

    10.并行化处理 —系统设计模块,块结构设计等

    xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的?注意xgboost的并行不是tree粒度的并行,xgboost也是一次迭代完才能进行下一次迭代的(第t次迭代的代价函数里包含了前面t-1次迭代的预测值)。xgboost的并行是在特征粒度上的。我们知道,决策树的学习最耗时的一个步骤就是对特征的值进行排序(因为要确定最佳分割点),xgboost在训练之前,预先对数据进行了排序,然后保存为block结构,后面的迭代中重复地使用这个结构,大大减小计算量。这个block结构也使得并行成为了可能,在进行节点的分裂时,需要计算每个特征的增益,最终选增益最大的那个特征去做分裂,那么各个特征的增益计算就可以开多线程进行。

    此外xgboost还设计了高速缓存压缩感知算法,这是系统设计模块的效率提升。
    当梯度统计不适合于处理器高速缓存和高速缓存丢失时,会大大减慢切分点查找算法的速度。
    (1)针对 exact greedy algorithm采用缓存感知预取算法
    (2)针对 approximate algorithms选择合适的块大小

    代码使用

    下面给出简单使用xgboost这个框架的例子。

    # 划分数据集
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.01, random_state=1729)
    print(X_train.shape, X_test.shape)
    
    #模型参数设置
    xlf = xgb.XGBRegressor(max_depth=10, 
                            learning_rate=0.1, 
                            n_estimators=10, 
                            silent=True, 
                            objective='reg:linear', 
                            nthread=-1, 
                            gamma=0,
                            min_child_weight=1, 
                            max_delta_step=0, 
                            subsample=0.85, 
                            colsample_bytree=0.7, 
                            colsample_bylevel=1, 
                            reg_alpha=0, 
                            reg_lambda=1, 
                            scale_pos_weight=1, 
                            seed=1440, 
                            missing=None)
    
    xlf.fit(X_train, y_train, eval_metric='rmse', verbose = True, eval_set = [(X_test, y_test)],early_stopping_rounds=100)
    
    # 计算 auc 分数、预测
    preds = xlf.predict(X_test)

    一个运用到实际例子的代码,来自xgboost入门与实战(实战调参篇)

    import numpy as np
    import pandas as pd
    import xgboost as xgb
    from sklearn.cross_validation import train_test_split
    
    #from xgboost.sklearn import XGBClassifier
    #from sklearn import cross_validation, metrics   #Additional scklearn functions
    #from sklearn.grid_search import GridSearchCV   #Perforing grid search
    #
    #import matplotlib.pylab as plt
    #from matplotlib.pylab import rcParams
    
    #记录程序运行时间
    import time 
    start_time = time.time()
    
    #读入数据
    train = pd.read_csv("Digit_Recognizer/train.csv")
    tests = pd.read_csv("Digit_Recognizer/test.csv") 
    
    params={
    'booster':'gbtree',
    'objective': 'multi:softmax', #多分类的问题
    'num_class':10, # 类别数,与 multisoftmax 并用
    'gamma':0.1,  # 用于控制是否后剪枝的参数,越大越保守,一般0.1、0.2这样子。
    'max_depth':12, # 构建树的深度,越大越容易过拟合
    'lambda':2,  # 控制模型复杂度的权重值的L2正则化项参数,参数越大,模型越不容易过拟合。
    'subsample':0.7, # 随机采样训练样本
    'colsample_bytree':0.7, # 生成树时进行的列采样
    'min_child_weight':3, 
    # 这个参数默认是 1,是每个叶子里面 h 的和至少是多少,对正负样本不均衡时的 0-1 分类而言
    #,假设 h 在 0.01 附近,min_child_weight 为 1 意味着叶子节点中最少需要包含 100 个样本。
    #这个参数非常影响结果,控制叶子节点中二阶导的和的最小值,该参数值越小,越容易 overfitting。 
    'silent':0 ,#设置成1则没有运行信息输出,最好是设置为0.
    'eta': 0.007, # 如同学习率
    'seed':1000,
    'nthread':7,# cpu 线程数
    #'eval_metric': 'auc'
    }
    
    plst = list(params.items())
    num_rounds = 5000 # 迭代次数
    
    train_xy,val = train_test_split(train, test_size = 0.3,random_state=1)
    #random_state is of big influence for val-auc
    y = train_xy[:, 0]
    X = train_xy[:, 1:]
    val_y = val[:, 0]
    val_X = val[:, 1:]
    
    xgb_val = xgb.DMatrix(val_X,label=val_y)
    xgb_train = xgb.DMatrix(X, label=y)
    xgb_test = xgb.DMatrix(tests)
    
    
    watchlist = [(xgb_train, 'train'),(xgb_val, 'val')]
    
    # training model 
    # early_stopping_rounds 当设置的迭代次数较大时,early_stopping_rounds 可在一定的迭代次数内准确率没有提升就停止训练
    model = xgb.train(plst, xgb_train, num_rounds, watchlist,early_stopping_rounds=100)
    
    model.save_model('./model/xgb.model') # 用于存储训练出的模型
    print "best best_ntree_limit",model.best_ntree_limit 
    
    print "跑到这里了model.predict"
    preds = model.predict(xgb_test,ntree_limit=model.best_ntree_limit)
    
    np.savetxt('xgb_submission.csv',np.c_[range(1,len(tests)+1),preds],delimiter=',',header='ImageId,Label',comments='',fmt='%d')
    
    #输出运行时长
    cost_time = time.time()-start_time
    print "xgboost success!",'\n',"cost time:",cost_time,"(s)"

    所使用的数据集是Kaggle上的Classify handwritten digits using the famous MNIST data–手写数字识别数据集,即Mnist数据集。

    展开全文
  • 常用机器学习算法 总结

    千次阅读 2014-06-19 17:54:22
     找工作时(IT行业),除了常见的软件开发以外,机器学习岗位也可以当作是一个选择,不少计算机方向的研究生都会接触这个,如果你的研究方向是机器学习/数据挖掘之类,且又对其非常感兴趣的话,可以考虑考虑该岗位...
    前言:
    
    
     
    

      找工作时(IT行业),除了常见的软件开发以外,机器学习岗位也可以当作是一个选择,不少计算机方向的研究生都会接触这个,如果你的研究方向是机器学习/数据挖掘之类,且又对其非常感兴趣的话,可以考虑考虑该岗位,毕竟在机器智能没达到人类水平之前,机器学习可以作为一种重要手段,而随着科技的不断发展,相信这方面的人才需求也会越来越大。

      纵观IT行业的招聘岗位,机器学习之类的岗位还是挺少的,国内大点的公司里百度,阿里,腾讯,网易,搜狐,华为(华为的岗位基本都是随机分配,机器学习等岗位基本面向的是博士)等会有相关职位,另外一些国内的中小型企业和外企也会招一小部分。当然了,其中大部分还是百度北京要人最多,上百人。阿里的算法岗位很大一部分也是搞机器学习相关的。另外本人有幸签约了网易杭州研究院的深度学习算法岗位,打算从事机器学习领域至少5年。非常感谢小易收留了我!

      下面是本人在找机器学习岗位工作时,总结的常见机器学习算法(主要是一些常规分类器)大概流程和主要思想,希望对大家找机器学习岗位时有点帮助。实际上在面试过程中,懂这些算法的基本思想和大概流程是远远不够的,那些面试官往往问的都是一些公司内部业务中的课题,往往要求你不仅要懂得这些算法的理论过程,而且要非常熟悉怎样使用它,什么场合用它,算法的优缺点,以及调参经验等等。说白了,就是既要会点理论,也要会点应用,既要有点深度,也要有点广度,否则运气不好的话很容易就被刷掉,因为每个面试官爱好不同。

     

     

      朴素贝叶斯:

           贝叶斯(Bayes)分类算法是一类利用概率统计知识进行分类的算法,如朴素贝叶斯(Naive Bayes)算法。这些算法主要利用Bayes定理来预测一个未知类别的样本属于各个类别的可能性,选择其中可能性最大的一个类别作为该样本的最终类别。由于贝叶斯定理的成立本身需要一个很强的条件独立性假设前提,而此假设在实际情况中经常是不成立的,因而其分类准确性就会下降。为此就出现了许多降低独立性假设的贝叶斯分类算法,如TAN(Tree Augmented Naive Bayes)算法,它是在贝叶斯网络结构的基础上增加属性对

      有以下几个地方需要注意:

      1. 如果给出的特征向量长度可能不同,这是需要归一化为通长度的向量(这里以文本分类为例),比如说是句子单词的话,则长度为整个词汇量的长度,对应位置是该单词出现的次数。

      2. 计算公式如下:

       

      其中一项条件概率可以通过朴素贝叶斯条件独立展开。要注意一点就是 的计算方法,而由朴素贝叶斯的前提假设可知, = ,因此一般有两种,一种是在类别为ci的那些样本集中,找到wj出现次数的总和,然后除以该样本的总和;第二种方法是类别为ci的那些样本集中,找到wj出现次数的总和,然后除以该样本中所有特征出现次数的总和。

      3. 如果 中的某一项为0,则其联合概率的乘积也可能为0,即2中公式的分子为0,为了避免这种现象出现,一般情况下会将这一项初始化为1,当然为了保证概率相等,分母应对应初始化为2(这里因为是2类,所以加2,如果是k类就需要加k,术语上叫做laplace光滑)。

      朴素贝叶斯的优点:

      对小规模的数据表现很好,适合多分类任务,适合增量式训练。

      缺点

      对输入数据的表达形式很敏感。

     

     

      决策树:

      决策树中很重要的一点就是选择一个属性进行分枝,因此要注意一下信息增益的计算公式,并深入理解它。

      信息熵的计算公式如下:

       

      其中的n代表有n个分类类别(比如假设是2类问题,那么n=2)。分别计算这2类样本在总样本中出现的概率p1和p2,这样就可以计算出未选中属性分枝前的信息熵。

      现在选中一个属性xi用来进行分枝,此时分枝规则是:如果xi=vx的话,将样本分到树的一个分支;如果不相等则进入另一个分支。很显然,分支中的样本很有可能包括2个类别,分别计算这2个分支的熵H1和H2,计算出分枝后的总信息熵H’=p1*H1+p2*H2.,则此时的信息增益ΔH=H-H’。以信息增益为原则,把所有的属性都测试一边,选择一个使增益最大的属性作为本次分枝属性。

      决策树的优点:

      计算量简单,可解释性强,比较适合处理有缺失属性值的样本,能够处理不相关的特征;

      缺点:

      容易过拟合(后续出现了随机森林,减小了过拟合现象);

     

     

      Logistic回归:

      Logistic是用来分类的,是一种线性分类器,需要注意的地方有:

      1. logistic函数表达式为:

       

      其导数形式为:

       

      2. logsitc回归方法主要是用最大似然估计来学习的,所以单个样本的后验概率为:

       

      到整个样本的后验概率:

       

      其中:

       

      通过对数进一步化简为:

       

      3. 其实它的loss function为-l(θ),因此我们需使loss function最小,可采用梯度下降法得到。梯度下降法公式为:

       

      

      Logistic回归优点:

      1、实现简单;

      2、分类时计算量非常小,速度很快,存储资源低;

      缺点:

      1、容易欠拟合,一般准确度不太高

      2、只能处理两分类问题(在此基础上衍生出来的softmax可以用于多分类),且必须线性可分;

     

     

      线性回归:

      线性回归才是真正用于回归的,而不像logistic回归是用于分类,其基本思想是用梯度下降法对最小二乘法形式的误差函数进行优化,当然也可以用normal equation直接求得参数的解,结果为:

       

      而在LWLR(局部加权线性回归)中,参数的计算表达式为:

       

      因为此时优化的是:

       

      由此可见LWLR与LR不同,LWLR是一个非参数模型,因为每次进行回归计算都要遍历训练样本至少一次。

      线性回归优点:

      实现简单,计算简单;

      缺点:

      不能拟合非线性数据;

     

     

      KNN算法:

      KNN即最近邻算法,其主要过程为:

      1. 计算训练样本和测试样本中每个样本点的距离(常见的距离度量有欧式距离,马氏距离等);

      2. 对上面所有的距离值进行排序;

      3. 选前k个最小距离的样本;

      4. 根据这k个样本的标签进行投票,得到最后的分类类别;

      如何选择一个最佳的K值,这取决于数据。一般情况下,在分类时较大的K值能够减小噪声的影响。但会使类别之间的界限变得模糊。一个较好的K值可通过各种启发式技术来获取,比如,交叉验证。另外噪声和非相关性特征向量的存在会使K近邻算法的准确性减小。

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

      注:马氏距离一定要先给出样本集的统计性质,比如均值向量,协方差矩阵等。关于马氏距离的介绍如下:

       

      KNN算法的优点:

      1. 思想简单,理论成熟,既可以用来做分类也可以用来做回归;

      2. 可用于非线性分类;

      3. 训练时间复杂度为O(n);

      4. 准确度高,对数据没有假设,对outlier不敏感;

      缺点:

      1. 计算量大;

      2. 样本不平衡问题(即有些类别的样本数量很多,而其它样本的数量很少);

      3. 需要大量的内存;

     

     

      SVM

         支持向量机(SVM,Support Vector Machine)是Vapnik根据统计学习理论提出的一种新的学习方法[43] ,它的最大特点是根据结构风险最小化准则,以最大化分类间隔构造最优分类超平面来提高学习机的泛化能力,较好地解决了非线性、高维数、局部极小点等问题。对于分类问题,支持向量机算法根据区域中的样本计算该区域的决策曲面,由此确定该区域中未知样本的类别。  


      要学会如何使用libsvm以及一些参数的调节经验,另外需要理清楚svm算法的一些思路:

      1. svm中的最优分类面是对所有样本的几何裕量最大(为什么要选择最大间隔分类器,请从数学角度上说明?网易深度学习岗位面试过程中有被问到。答案就是几何间隔与样本的误分次数间存在关系: ,其中的δ是样本集合到分类面的间隔,R=max ||xi||  i=1,...,n,即R是所有样本中(xi是以向量表示的第i个样本)向量长度最长的值(也就是说代表样本的分布有多么广)。先不必追究误分次数的具体定义和推导过程,只要记得这个误分次数一定程度上代表分类器的误差。而从上式可以看出,误分次数的上界由几何间隔决定!

       

      经过一系列推导可得为优化下面原始目标:

      

      2. 下面来看看拉格朗日理论:

      

      可以将1中的优化目标转换为拉格朗日的形式(通过各种对偶优化,KKD条件),最后目标函数为:

       

      我们只需要最小化上述目标函数,其中的α为原始优化问题中的不等式约束拉格朗日系数。

      3. 对2中最后的式子分别w和b求导可得:

      

       

      由上面第1式子可以知道,如果我们优化出了α,则直接可以求出w了,即模型的参数搞定。而上面第2个式子可以作为后续优化的一个约束条件。

      4. 对2中最后一个目标函数用对偶优化理论可以转换为优化下面的目标函数:

      

      而这个函数可以用常用的优化方法求得α,进而求得w和b。

      5. 按照道理,svm简单理论应该到此结束。不过还是要补充一点,即在预测时有:

       

      那个尖括号我们可以用核函数代替,这也是svm经常和核函数扯在一起的原因。

      6. 最后是关于松弛变量的引入,因此原始的目标优化公式为:

       

      此时对应的对偶优化公式为:

       

      与前面的相比只是α多了个上界。

      SVM算法优点:

      可用于线性/非线性分类,也可以用于回归;

      低泛化误差;

      容易解释;

      计算复杂度较低;

      缺点:

      对参数和核函数的选择比较敏感;

      原始的SVM只比较擅长处理二分类问题;

     

       



      Boosting

      主要以Adaboost为例,首先来看看Adaboost的流程图,如下:

       

      从图中可以看到,在训练过程中我们需要训练出多个弱分类器(图中为3个),每个弱分类器是由不同权重的样本(图中为5个训练样本)训练得到(其中第一个弱分类器对应输入样本的权值是一样的),而每个弱分类器对最终分类结果的作用也不同,是通过加权平均输出的,权值见上图中三角形里面的数值。那么这些弱分类器和其对应的权值是怎样训练出来的呢?

      下面通过一个例子来简单说明。

      书中(machinelearning in action)假设的是5个训练样本,每个训练样本的维度为2,在训练第一个分类器时5个样本的权重各为0.2.注意这里样本的权值和最终训练的弱分类器组对应的权值α是不同的,样本的权重只在训练过程中用到,而α在训练过程和测试过程都有用到。

      现在假设弱分类器是带一个节点的简单决策树,该决策树会选择2个属性(假设只有2个属性)的一个,然后计算出这个属性中的最佳值用来分类。

      Adaboost的简单版本训练过程如下:

      1. 训练第一个分类器,样本的权值D为相同的均值。通过一个弱分类器,得到这5个样本(请对应书中的例子来看,依旧是machine learning in action)的分类预测标签。与给出的样本真实标签对比,就可能出现误差(即错误)。如果某个样本预测错误,则它对应的错误值为该样本的权重,如果分类正确,则错误值为0. 最后累加5个样本的错误率之和,记为ε。

      2. 通过ε来计算该弱分类器的权重α,公式如下:

       

      3. 通过α来计算训练下一个弱分类器样本的权重D,如果对应样本分类正确,则减小该样本的权重,公式为:

       

      如果样本分类错误,则增加该样本的权重,公式为:

       

      4. 循环步骤1,2,3来继续训练多个分类器,只是其D值不同而已。

      测试过程如下:

      输入一个样本到训练好的每个弱分类中,则每个弱分类都对应一个输出标签,然后该标签乘以对应的α,最后求和得到值的符号即为预测标签值。

      Boosting算法的优点:

      低泛化误差;

      容易实现,分类准确率较高,没有太多参数可以调;

      缺点:

      对outlier比较敏感;

     

     

      聚类:

      根据聚类思想划分:

      1. 基于划分的聚类:

      K-means, k-medoids(每一个类别中找一个样本点来代表),CLARANS.

      k-means是使下面的表达式值最小:

       

       k-means算法的优点:

      (1)k-means算法是解决聚类问题的一种经典算法,算法简单、快速。

      (2)对处理大数据集,该算法是相对可伸缩的和高效率的,因为它的复杂度大约是O(nkt),其中n是所有对象的数目,k是簇的数目,t是迭代的次数。通常k<<n。这个算法通常局部收敛。

      (3)算法尝试找出使平方误差函数值最小的k个划分。当簇是密集的、球状或团状的,且簇与簇之间区别明显时,聚类效果较好。

       缺点:

      (1)k-平均方法只有在簇的平均值被定义的情况下才能使用,且对有些分类属性的数据不适合。

      (2)要求用户必须事先给出要生成的簇的数目k。

      (3)对初值敏感,对于不同的初始值,可能会导致不同的聚类结果。

      (4)不适合于发现非凸面形状的簇,或者大小差别很大的簇。

      (5)对于"噪声"和孤立点数据敏感,少量的该类数据能够对平均值产生极大影响。

      2. 基于层次的聚类:

      自底向上的凝聚方法,比如AGNES。

      自上向下的分裂方法,比如DIANA。

      3. 基于密度的聚类:

      DBSACN,OPTICS,BIRCH(CF-Tree),CURE.

      4. 基于网格的方法:

      STING, WaveCluster.

      5. 基于模型的聚类:

      EM,SOM,COBWEB.

      以上这些算法的简介可参考聚类(百度百科)。

     

     

       推荐系统:

      推荐系统的实现主要分为两个方面:基于内容的实现和协同滤波的实现。

      基于内容的实现:

      不同人对不同电影的评分这个例子,可以看做是一个普通的回归问题,因此每部电影都需要提前提取出一个特征向量(即x值),然后针对每个用户建模,即每个用户打的分值作为y值,利用这些已有的分值y和电影特征值x就可以训练回归模型了(最常见的就是线性回归)。这样就可以预测那些用户没有评分的电影的分数。(值得注意的是需对每个用户都建立他自己的回归模型)

      从另一个角度来看,也可以是先给定每个用户对某种电影的喜好程度(即权值),然后学出每部电影的特征,最后采用回归来预测那些没有被评分的电影。

      当然还可以是同时优化每个用户对不同类型电影的热爱程度以及每部电影的特征。具体可以参考Ng在coursera上的ml教程:https://www.coursera.org/course/ml

      基于协同滤波的实现:

      协同滤波(CF)可以看做是一个分类问题,也可以看做是矩阵分解问题。协同滤波主要是基于每个人自己的喜好都类似这一特征,它不依赖于个人的基本信息。比如刚刚那个电影评分的例子中,预测那些没有被评分的电影的分数只依赖于已经打分的那些分数,并不需要去学习那些电影的特征。

      SVD将矩阵分解为三个矩阵的乘积,公式如下所示:

       

      中间的矩阵sigma为对角矩阵,对角元素的值为Data矩阵的特征值,且已经从大到小排列好了。即使去掉特征值小的那些特征,依然可以很好的重构出原始矩阵。如下图所示:

      

      其中更深的颜色代表去掉小特征值重构时的三个矩阵。

      果m代表商品的个数,n代表用户的个数,则U矩阵的每一行代表商品的属性,现在通过降维U矩阵(取深色部分)后,每一个商品的属性可以用更低的维度表示(假设为k维)。这样当新来一个用户的商品推荐向量X,则可以根据公式X*U1*inv(S1)得到一个k维的向量,然后在V’中寻找最相似的那一个用户(相似度测量可用余弦公式等),根据这个用户的评分来推荐(主要是推荐新用户未打分的那些商品)。具体例子可以参考网页:SVD在推荐系统中的应用

      另外关于SVD分解后每个矩阵的实际含义可以参考google吴军的数学之美一书(不过个人感觉吴军解释UV两个矩阵时好像弄反了,不知道大家怎样认为)。或者参考machinelearning in action其中的svd章节。

     

     

      pLSA:

      pLSA由LSA发展过来,而早期LSA的实现主要是通过SVD分解。pLSA的模型图如下:

       

      公式中的意义如下:

       

      具体可以参考2010龙星计划:机器学习中对应的主题模型那一讲

     

     

      LDA

      主题模型,概率图如下:

       

      和pLSA不同的是LDA中假设了很多先验分布,且一般参数的先验分布都假设为Dirichlet分布,其原因是共轭分布时先验概率和后验概率的形式相同。

     

     

      GDBT

      GBDT(Gradient Boosting Decision Tree) 又叫 MART(Multiple Additive Regression Tree),好像在阿里内部用得比较多(所以阿里算法岗位面试时可能会问到),它是一种迭代的决策树算法,该算法由多棵决策树组成,所有树的输出结果累加起来就是最终答案。它在被提出之初就和SVM一起被认为是泛化能力(generalization)较强的算法。近些年更因为被用于搜索排序的机器学习模型而引起大家关注。

      GBDT是回归树,不是分类树。其核心就在于,每一棵树是从之前所有树的残差中来学习的。为了防止过拟合,和Adaboosting一样,也加入了boosting这一项。

      关于GDBT的介绍可以可以参考:GBDT(MART) 迭代决策树入门教程 | 简介

     

     

      Regularization:

      作用是(网易电话面试时有问到):

      1. 数值上更容易求解;

      2. 特征数目太大时更稳定;

      3. 控制模型的复杂度,光滑性。复杂性越小且越光滑的目标函数泛化能力越强。而加入规则项能使目标函数复杂度减小,且更光滑。

      4. 减小参数空间;参数空间越小,复杂度越低。

      5. 系数越小,模型越简单,而模型越简单则泛化能力越强(Ng宏观上给出的解释)。

     

     

      异常检测:

      可以估计样本的密度函数,对于新样本直接计算其密度,如果密度值小于某一阈值,则表示该样本异常。而密度函数一般采用多维的高斯分布。如果样本有n维,则每一维的特征都可以看作是符合高斯分布的,即使这些特征可视化出来不太符合高斯分布,也可以对该特征进行数学转换让其看起来像高斯分布,比如说x=log(x+c),x=x^(1/c)等。异常检测的算法流程如下:

       

       其中的ε也是通过交叉验证得到的,也就是说在进行异常检测时,前面的p(x)的学习是用的无监督,后面的参数ε学习是用的有监督。那么为什么不全部使用普通有监督的方法来学习呢(即把它看做是一个普通的二分类问题)?主要是因为在异常检测中,异常的样本数量非常少而正常样本数量非常多,因此不足以学习到好的异常行为模型的参数,因为后面新来的异常样本可能完全是与训练样本中的模式不同。

      另外,上面是将特征的每一维看成是相互独立的高斯分布,其实这样的近似并不是最好的,但是它的计算量较小,因此也常被使用。更好的方法应该是将特征拟合成多维高斯分布,这时有特征之间的相关性,但随之计算量会变复杂,且样本的协方差矩阵还可能出现不可逆的情况(主要在样本数比特征数小,或者样本特征维数之间有线性关系时)。

      上面的内容可以参考Ng的https://www.coursera.org/course/ml

     

     

      EM算法:

      有时候因为样本的产生和隐含变量有关(隐含变量是不能观察的),而求模型的参数时一般采用最大似然估计,由于含有了隐含变量,所以对似然函数参数求导是求不出来的,这时可以采用EM算法来求模型的参数的(对应模型参数个数可能有多个),EM算法一般分为2步:

      E步:选取一组参数,求出在该参数下隐含变量的条件概率值;

      M步:结合E步求出的隐含变量条件概率,求出似然函数下界函数(本质上是某个期望函数)的最大值。

      重复上面2步直至收敛。

      公式如下所示:

       

      M步公式中下界函数的推导过程:

       

      EM算法一个常见的例子就是GMM模型,每个样本都有可能由k个高斯产生,只不过由每个高斯产生的概率不同而已,因此每个样本都有对应的高斯分布(k个中的某一个),此时的隐含变量就是每个对应的某个高斯分布。

      GMM的E步公式如下:

       

      M步公式如下:

       

      关于EM算法可以参考Ng的cs229课程资料 或者网易公开课:斯坦福大学公开课 :机器学习课程

     

     

      Apriori:

      Apriori是关联分析中比较早的一种方法,主要用来挖掘那些频繁项集合。其思想是:

      1. 如果一个项目集合不是频繁集合,那么任何包含它的项目集合也一定不是频繁集合;

      2. 如果一个项目集合是频繁集合,那么它的任何非空子集也是频繁集合;

      Aprioir需要扫描项目表多遍,从一个项目开始扫描,舍去掉那些不是频繁的项目,得到的集合称为L,然后对L中的每个元素进行自组合,生成比上次扫描多一个项目的集合,该集合称为C,接着又扫描去掉那些非频繁的项目,重复…

      看下面这个例子:

      元素项目表格:

       

      如果每个步骤不去掉非频繁项目集,则其扫描过程的树形结构如下:

       

      在其中某个过程中,可能出现非频繁的项目集,将其去掉(用阴影表示)为:

       

      上面的内容主要参考的是machinelearning in action这本书。

     

     

      FP Growth:

      FPGrowth是一种比Apriori更高效的频繁项挖掘方法,它只需要扫描项目表2次。其中第1次扫描获得当个项目的频率,去掉不符合支持度要求的项,并对剩下的项排序。第2遍扫描是建立一颗FP-Tree(frequent-pattentree)。

      接下来的工作就是在FP-Tree上进行挖掘。

      比如说有下表:

       

      它所对应的FP_Tree如下:

       

      然后从频率最小的单项P开始,找出P的条件模式基,用构造FP_Tree同样的方法来构造P的条件模式基的FP_Tree,在这棵树上找出包含P的频繁项集。

      依次从m,b,a,c,f的条件模式基上挖掘频繁项集,有些项需要递归的去挖掘,比较麻烦,比如m节点,具体的过程可以参考博客:Frequent Pattern 挖掘之二(FP Growth算法),里面讲得很详细。

     



    如何选择机器学习算法:http://www.52ml.net/15063.html

     




      参考资料:

       Harrington, P. (2012). Machine Learningin Action, Manning Publications Co.

          最近邻算法(维基百科)

          马氏距离(维基百科)

       聚类(百度百科)

          https://www.coursera.org/course/ml

          SVD在推荐系统中的应用

          吴军 and 谷歌 (2012). 数学之美, 人民邮电出版社.

          2010龙星计划:机器学习对应的视频教程:2010龙星计划机器学习视频教程

          GBDT(MART) 迭代决策树入门教程 | 简介

          Ng的cs229课程资料

          斯坦福大学公开课 :机器学习课程

          Frequent Pattern 挖掘之二(FP Growth算法)

    展开全文
  • 机器学习算法总结--提升方法

    千次阅读 2017-02-22 20:04:14
    浅谈机器学习基础(上) 简介 提升方法(boosting)是一种常用的统计学习方法,在分类问题中,它通过改变训练样本的权重,学习多个分类器,并将这些分类器进行线性组合,提供分类的性能。 boosting和baggingboosting...
  • 机器学习算法总结--决策树

    千次阅读 2017-02-13 21:49:42
    决策树学习通常包括3个步骤:特征选择、决策树的生成和决策树的修剪。决策树学习本质上是从训练数据集中归纳出一组分类规则,也可以说是由训练数据集估计条件概率模型。它使用的损失函数通常是正则化的极大似然函数...
  • 机器学习算法总结--线性回归和逻辑回归

    万次阅读 多人点赞 2017-02-12 19:02:52
    算法类型:回归算法 线性回归的模型函数如下: h θ = θ T x h_\theta = \theta ^T x h θ ​ = θ T x 它的损失函数如下: J ( θ ) = 1 2 m ∑ i = 1 m ( h θ ( x ( i ) ) − y ( i ) ) 2 J(\theta) =...
  • tfidf[doc_test_vec]

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 158,076
精华内容 63,230
关键字:

机器学习算法总结