机器学习算法总结_机器学习算法面试总结 - CSDN
精华内容
参与话题
  • 机器学习十大算法原理总结

    千次阅读 2017-11-11 23:06:41
    1、K-近邻算法:通过建立和样本之间的距离求和,然后通过选择最近的K个样本数据,样本数据类型多的就是需要分的类型。 2、决策树算法:通过求最大信息增益来得到需要判断和拆分的标签类目,然后建立递归数,进行...

    监督学习算法:
    1、K-近邻算法:通过建立和样本之间的距离求和,然后通过选择最近的K个样本数据,样本数据类型多的就是需要分的类型。
    2、决策树算法:通过求最大信息增益来得到需要判断和拆分的标签类目,然后建立递归数,进行继续拆分到叶子节点结束。
    3、朴素贝叶斯算法:通过和全量样本对比,有不同的样本概率求和,选择概率最大的作为分类。
    4、逻辑回归算法:通过样本数据来计算逻辑回归系数,确定样本的分类概率,系数越大,准确性越高,结果数据大于0.5为一类,小于0.5为另一类。
    5、支持向量机算法:和逻辑回归类型,不同之处就是支持的向量的特征维度相对较少,最后通过建立一个绝对平面来进行绝对正反分类。

    无监督学习算法:
    1、聚类算法:通过设定任意的质心,然后计算周边所有点的聚类,取最近的K个数的平均值作为新的质心,不断迭代,进行分类到结束。
    2、协同过滤算法:主要是划分数据集,然后计算支持度进行过滤无效数据,然后通过计算置信度得出数据出现的概率。

    展开全文
  • 文章目录1·knn算法 1·knn算法 为了判断未知实例的类别,以所有已知类别的实例作为作为参照数据集 计算未知实例与所有已知实例的距离(这里计算的是欧式距离) 选择最近K个已知实例 根据少数服从多数的投票法则...

    1·knn算法

    为了判断未知实例的类别,以所有已知类别的实例作为参照数据集
    计算未知实例与所有已知实例的距离(这里计算的是欧式距离)
    选择最近K个已知实例
    根据少数服从多数的投票法则(majority-voting),让未知实例归类为K个最邻近样本中最多数的类别

    k值
    这里所谓的交叉验证就是将样本划分一部分出来为预测样本,比如95%训练,5%预测,然后k分别取1,2,3,4,5之类的,进行预测,计算最后的分类误差,选择误差最小的k

    2·朴素贝叶斯算法

    朴素贝叶斯法是基于贝叶斯定理特征条件独立假设的分类方法
    1·首先由贝叶斯定理可知,
    在这里插入图片描述
    2·其次
    在这里插入图片描述
    3·如果
    在这里插入图片描述
    4.那么由朴素贝叶斯定理可知,
    在这里插入图片描述
    优缺点
    朴素贝叶斯的优点
    对小规模的数据表现很好,适合多分类任务,适合增量式训练。
    缺点
    对输入数据的表达形式很敏感(离散、连续,值极大极小之类的)。
    属性独立性的条件同时也是朴素贝叶斯分类器的不足之处。数据集属性的独立性在很多情况下是很难满足的,因为数据集的属性之间往往都存在着相互关联,如果在分类过程中出现这种问题,会导致分类的效果大大降低。

    3·线性回归算法

    首先要明白,回归分析(regression analysis)用来建立方程模拟两个或者多个变量之间如何关联
    被预测的变量叫做:因变量 被用来进行预测的变量叫做: 自变量
    以上两个变量的关系用一条直线来模拟 就称为一元线性回归
    如果包含两个以上的自变量,则称作多元线性回归分析

    利用最小二乘法可以得到 线性回归的代价函数
    在这里插入图片描述
    而求解回归方程的过程也就是求解 最优系数使得代价函数值最小的过程。可利用梯度下降法或者标准方程法。

    梯度下降法:以一元线性回归为例
    先初始化
    每次根据学习率向代价函数的值变化大的方向不停迭代

    标准方程法
    在这里插入图片描述
    在这里插入图片描述
    由于线性回归很容易出现过拟合的情况,所以为了解决这个问题 ,可以有三个措施
    在这里插入图片描述
    其中将代价函数正则化:
    在这里插入图片描述
    而L1正则化的代价函数就是Lasso的代价函数
    L2正则化的代价函数是岭回归的代价函数

    还有将代价函数加上更高层次的范数叫做弹性网
    在这里插入图片描述

    4·逻辑回归

    逻辑回归虽然有回归两个字,但是主要是用来做分类的,特别是用来做二分类。
    逻辑回归的预测函数可以看成是在线性回归的预测函数外面套了一层sigmoid函数
    在这里插入图片描述
    根据sigmoid函数的性质,当g>=0.5时,z>0恒成立,就可以假设如果h>=0.5时归为一类,<0.5归为另一类。则可得到一个关于x与系数矩阵的限制性条件。接着利用梯度下降法求得系数矩阵,将系数带入到预测函数中,根据h>0.5分类为条件就可得到一条决策边界,如果时多变量,则会得到一条几何边界。
    接下来就时如何求解系数矩阵的问题了,这里还是利用代价函数与梯度下降法来求解系数矩阵。

    由于代价函数的目的是为了求所有样本 真实值—预测值 的平方和最小,但在逻辑回归中的由于sigmoid函数的存在,使得正常的代价函数无法用梯度下降法求解最优解,所以根据sigmoid函数,对代价函数进行调整,得到如下方程

    在这里插入图片描述
    最终化简就得到了如下方程,利用梯度下降法就可求解出系数矩阵,带入原来的不等式就可求解出决策边界
    在这里插入图片描述

    5·决策树算法

    首先要明白决策树是一颗依托决策而建立起来的树。
    主要有三种算法,分别时ID3算法,C4.5算法,CART算法

    1·ID3算法

    首先是针对当前的集合,计算每个特征的信息增益
    然后选择信息增益最大的特征作为当前节点的决策决策特征
    根据特征不同的类别划分到不同的子节点(比如年龄特征有青年,中年,老年,则划分到3颗子树)
    然后继续对子节点进行递归,直到所有特征都被划分

    2·C4.5算法

    它是ID3的一个改进算法,使用信息增益率来进行属性的选择

    3·CART算法

    首先是根据当前特征计算他们的基尼增益
    选择基尼增益最小的特征作为划分特征
    从该特征中查找基尼指数最小的分类类别作为最优划分点
    将当前样本划分成两类,一类是划分特征的类别等于最优划分点,另一类就是不等于
    针对这两类递归进行上述的划分工作,直达所有叶子指向同一样本目标或者叶子个数小于一定的阈值

    4·决策树的分类与回归

    分类树
    输出叶子节点中所属类别最多的那一类
    回归树
    输出叶子节点中各个样本值的平均值

    5·解决决策树的过拟合

    剪枝
    前置剪枝:在分裂节点的时候设计比较苛刻的条件,如不满足则直接停止分裂(这样干决策树无法到最优,也无法得到比较好的效果)
    后置剪枝:在树建立完之后,用单个节点代替子树,节点的分类采用子树中主要的分类(这种方法比较浪费前面的建立过程)
    交叉验证
    随机森林

    6·决策树参数

    1.criterion gini or entropy

    2.splitter best or random 前者是在所有特征中找最好的切分点 后者是在部分特征中(数据量大的时候)

    3.max_features None(所有),log2,sqrt,N 特征小于50的时候一般使用所有的

    4.max_depth 数据少或者特征少的时候可以不管这个值,如果模型样本量多,特征也多的情况下,可以尝试限制下

    5.min_samples_split 如果某节点的样本数少于min_samples_split,则不会继续再尝试选择最优特征来进行划分如果样本量不大,不需要管这个值。如果样本量数量级非常大,则推荐增大这个值。

    6.min_samples_leaf 这个值限制了叶子节点最少的样本数,如果某叶子节点数目小于样本数,则会和兄弟节点一起被剪枝,如果样本量不大,不需要管这个值,大些如10W可是尝试下5

    7.min_weight_fraction_leaf 这个值限制了叶子节点所有样本权重和的最小值,如果小于这个值,则会和兄弟节点一起被剪枝默认是0,就是不考虑权重问题。一般来说,如果我们有较多样本有缺失值,或者分类树样本的分布类别偏差很大,就会引入样本权重,这时我们就要注意这个值了。

    8.max_leaf_nodes 通过限制最大叶子节点数,可以防止过拟合,默认是"None”,即不限制最大的叶子节点数。 如果加了限制,算法会建立在最大叶子节点数内最优的决策树。如果特征不多,可以不考虑这个值,但是如果特征分成多的话,可以加以限制具体的值可以通过交叉验证得到。

    9.class_weight 指定样本各类别的的权重,主要是为了防止训练集某些类别的样本过多导致训练的决策树过于偏向这些类别。这里可以自己指定各个样本的权重如果使用“balanced”,则算法会自己计算权重,样本量少的类别所对应的样本权重会高。

    10.min_impurity_split 这个值限制了决策树的增长,如果某节点的不纯度(基尼系数,信息增益,均方差,绝对差)小于这个阈值则该节点不再生成子节点。即为叶子节点 。

    6·svm算法

    svm的基本想法就是找到一个能正确划分训练样本并且其几何间隔最大化的超平面。
    SVM 计算的过程就是帮我们找到超平面的过程,它有个核心的概念叫:分类间隔。SVM 的目标就是找出所有分类间隔中最大的那个值对应的超平面。在数学上,这是一个凸优化问题。同样我们根据数据是否线性可分,把 SVM 分成硬间隔 SVM、软间隔 SVM 和非线性 SVM。
    在这里插入图片描述
    我们要求的也就是当d最大时的w和b的值,而通过计算推导可得以下结论
    在这里插入图片描述

    由于实际问题中,模型数据并不一定是完全线性可分的,所以根据训练数据是否线性可分,可将svm分为3个模型
    1·线性可分支持向量机(硬间隔支持向量机)
    2·线性支持向量机(软间隔支持向量机)
    3·非线性支持向量机(主要利用核技巧和软间隔最大化)
    前两种一般的解决办法就是在原来的损失函数上加入一个正则化项,从而消除异常值对模型的影响

    详细可参考:支持向量机svm

    7·聚类算法

    首先聚类算法是一个无监督模型,数据集是不带标签的。一般可以应用到一些 寻找优质客户,监控异常点(如信用卡欺诈等)
    一般的聚类算法有k-means算法,密度聚类(DBSCAN),层次聚类(AGNES),混合聚类

    k-means算法

    算法思想:以空间中k个点为中心进行聚类,对最靠近他们的对象归类。通过迭代的方法,逐次更新各聚类中心的值,直至得到最好的聚类结果

    步骤:
    1.先从没有标签的元素集合A中随机取k个元素,作为k个子集各自的重心。
    2.分别计算剩下的元素到k个子集重心的距离(这里的距离也可以使用欧氏距离),根据距离将这些元素分别划归到最近的子集。
    3.根据聚类结果,重新计算重心(重心的计算方法是计算子集中所有元素各个维度的算数平均数)。
    4.重复第2-3步,直到聚类结果不再发生变化。

    k-menas存在的问题:
    1,对k个初始质心的选择比较敏感,容易使代价函数的值陷入局部最小值
    2,k值的选择是用户指定的,不同的k会得到挺大的不用。
    3,存在局限性,对于双螺旋形状的分布没办法准确处理
    4,数据较大时,收敛会比较慢

    k-means优化:
    1,使用多次随机初始化,计算每一次建模得到的代价函数的值,选取代价函数最小时候的结果作为聚类结果
    2,使用肘部法则来选择k值

    k-means代价函数:
    就是计算 每个样本点质心距离平方和 再除以 总样本数
    在这里插入图片描述

    8·集成学习

    bagging

    对初始数据集 有放回抽样获取m个训练集,分别进行建模训练,然后对测试集进行预测,以少数服从多数的原则来通过投票确定最后的结果。(对于回归问题,则使用简单平均法确定系数)

    随机森林

    RF = 决策树 + Bagging + 随机属性选择
    1,.样本的随机:从样本集中用有放回抽样的方式,随机选
    择n个样本
    2,特征的随机:从所有属性d中随机选择k个属性(k<d),
    然后从k个属性中选择最佳分割属性作为节点建立
    CART决策树。
    最佳分割属性:分别计算k个属性的Gini系数增益,取Gini系数增益值最大的属性作为决策树的根节点属性。
    3,重复以上两个步骤m次,建立m棵CART决策树
    4,这m棵CART决策树形成随机森林,通过投票表决结果,决定数据属于哪一类

    GBDT

    GBDT 也叫做梯度提升树,它的base model 是决策树
    GBDT同AdaBoost类似,都是不断迭代前一个model的预测的结果,而AdaBoost每次都通过误差率来重新计算样本权值,而GBDT是以残差来作为下一次model的样本集。
    优点:
    预测的精度高
    适合低维数据
    能处理非线性数据
    缺点:
    并行麻烦(因为上下两棵树有联系)
    如果数据维度较高时会加大算法的计算复杂度

    Adaboost

    AdaBoost是一种根据样本误差率来不断迭代的算法.
    具体的操作过程就是:
    1,对训练集N初始化训练数据设置相同的权值为1/N,
    2,使用基分类器g1来进行分类,然后计算样本的误差率,来得到g1的权重系数a1,进而计算出训练样本的权值分布。
    3,利用新权值的样本集进行二次拟合,得到g2分类器,再次计算误差率,从来计算出每个样本的权值分布。
    4,这样一直迭代n次,然后对这n个弱分类器与权重系数的乘积 求和得到的f(x)即为最终分类器。

    Xgboost

    Xgboost是对GBDT的一个优化提升,它的base model也是决策树,也是以残差来做下一次model的样本。
    xgboost在效率和精度上有很大提升
    1,损失函数是用泰勒展开式展开的,同时用到了一阶导和二阶导,可以加快优化速度。
    2,对数结构进行了正则化约束,防止model过拟合
    3,在寻找最佳分割点时,考虑到传统的贪心算法效率较低,实现了一种近似贪心算法,用来加速和减小内存消耗,除此之外还考虑了稀疏数据集和缺失值的处理,对于特征的值有缺失的样本,XGBoost依然能自动找到其要分裂的方向。
    4,引进了特征子采样,像RandomForest那样,这种方法既能降低过拟合,还能减少计算
    5,XGBoost支持并行处理,XGBoost的并行不是在模型上的并行,而是在特征上的并行,将特征列排序后以block的形式存储在内存中,在后面的迭代中重复使用这个结构。这个block也使得并行化成为了可能,其次在进行节点分裂时,计算每个特征的增益,最终选择增益最大的那个特征去做分割,那么各个特征的增益计算就可以开多线程进行。

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

    千次阅读 2018-10-09 20:31:13
    对最常见的机器学习算法做一点点简单的总结,嫌麻烦公式就不贴了,这里有我字很丑的听课笔记,无关人员请撤离… LR与SVM的异同 相同点:逻辑回归和SVM都是有监督学习,本质都是线性分类判别模型。 不同点: (1)...

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_14916279/article/details/72822401

    对最常见的机器学习算法做一点点简单的总结,嫌麻烦公式就不贴了,这里有我字很丑的听课笔记,无关人员请撤离…

    LR与SVM的异同
    相同点:逻辑回归和SVM都是有监督学习,本质都是线性分类判别模型。
    不同点:
    (1)原理不同:逻辑回归LR基于损失函数最小化(经验风险最小化),而支持向量机SVM基于最大化间隔(结构风险最小化);
    (2)LR的分类决策面由所有样本决定,而SVM的决策面即分割超平面只由少数样本即支撑向量决定;
    (3)SVM使用核函数,而LR一般不使用;
    (4)LR使用正则化来抑制过拟合,而SVM自带正则化,但SVM使用松弛因子来实现软间隔;
    (5)SVM只给出属于哪一类,而LR在给出类别的同时,还给出了后验概率(这使得LR可以用于医疗诊断、点击率预估、推荐系统等)。

    SVM核函数,总结起来就是:若数据样本在低维空间线性不可分,它在某个高维空间是线性可分的,这就需要将样本数据从低维空间映射到高维空间,但这个映射关系难以确定。更重要的一点是,SVM中的运算是点积运算,而使用核函数,更确切的说是核技巧(Kernel trick),能将低维向量映射到高维空间并进行点积运算,转化为低维空间的简单运算,使得运算复杂度大大降低。常见的核函数主要有:线性核函数、多项式核函数、RBF径向基核函数、Sigmoid核函数。
    1)线性核函数:这里写图片描述
    2) 多项式核函数:这里写图片描述
    3) RBF径向基核函数:这里写图片描述
    4) Sigmoid核函数:这里写图片描述

    SVM软间隔与硬间隔:在SVM的最小优化目标函数中加入松弛因子,可以实现软间隔,松弛系数C越小,间隔越宽,分割超平面越硬;松弛系数C越大,间隔越窄,分割超平面越软,会更多的拟合训练样本;当C太大时,容易过拟合。

    SVM多分类问题,本质上还是两类分类问题,若共有N类(假设N=4),SVM的多分类问题主要有以下几种策略:
    (1)一对多One against Rest:训练两类分类器1 vs 2,3,4 、 2 vs 1,3,4 、3 vs 1,2,4 、 4 vs 1,2,3 共N个两类分类器,测试时将N个分类器结果投票。
    (2)一对一One against One:训练两类分类器:训练1 vs 2 、 1 vs 3 、1 vs 4 、2 vs 3 、2 vs 4 、3 vs 4共N*(N-1)/ 2个分类器,测试时通过这些分类器进行投票。
    (3)按类别层次划分

    SVM基于间隔最大化来寻找分割超平面,需要做数据归一化,采用的loss function是hinge loss,深度学习常用的Softmax Regression是对逻辑回归LR的一种扩展的多类分类器。

    LR本质上是一种线性分类算法,基于损失函数最小化,其分类决策面与所有样本点都有关,为了防止过拟合可以加入正则项,多分类问题可以分解成one vs rest问题。其主要优点有:
    (1)LR除了给出类别之外,还能给出后验概率(它采用的映射函数来自于sigmoid函数,输出可看作0~1的概率值),因此可以用于医疗诊断、CTR点击率预估、推荐系统等。
    (2)可解释性强,特征可控性高,训练快,添加特征简单。

    LR与NB(朴素贝叶斯)的区别:它们本质上都是线性分类模型,LR基于损失函数最小化,而NB基于贝叶斯定理和条件独立性假设,LR是判别模型而NB是生成模型,NB可应用于垃圾邮件过滤、文本分类等。

    KNN就不说了,比较简单。决策树DT主要有ID3、C4.5、CART等方法,分别基于信息增益、信息增益率、基尼系数来做特征选取样本数据集划分,生成一颗决策树,除了叶节点外所有节点都对应着某个特征。缓解过拟合的方法包括剪枝和随机森林,随机森林是将多颗决策树即多个弱分类器组合成强分类器的方法。

    bagging、随机森林、boosting和adaboost:
    (1)bagging是在所有样本中有放回的随机选取n个样本,使用所有样本特征,训练得到一个分类器,重复m次得到m个分类器,最后采用投票的方式得到决策结果,各分类器权重一样。
    (2)随机森林在所有样本中有放回的随机选取n个样本,在所有样本特征中随机选取k个特征,训练得到一个分类器,重复m次得到m个分类器,最后采用投票的方式得到决策结果,各分类器权重一样。
    (3)boosting相对于bagging,各分类器的权重由其分类的准确率决定,adaboost在boosting的基础上,每一个样本给定相同的初始权重,分类出错的样本的权重上升,分类正确的样本权重下降,即它是在前一个分类器训练的基础上训练得到新的分类器,分类器的权重根据其分类的准确率决定,组合弱分类器形成强分类器,不容易过拟合。

    PCA主成分分析,目的是特征降维,降低特征间相关性,实际上是将原始特征空间变换到一个复杂度更低并尽可能保留了原始信息的特征空间。对原始特征数据样本的协方差矩阵进行特征分解,利用特征向量构造出新的协方差矩阵,满足主对角元最大,非主对角元为0,选取主对角元特征值较大的k个特征向量,得到降维后的特征空间。具体步骤如下:
    (1)去均值;(2)计算协方差矩阵;(3)特征分解,选取前top k特征;(4)特征降维。
    LDA线性判别分析,即fisher准则,也是一种特征选取/降维的方法,它的原理是使得对特征空间进行投影变换后,使得类间距离最大、类内距离最小,它在降维的同时考虑了类别信息。

    关于样本处理问题,当样本数据太大时,考虑离散化、降采样等措施。关于样本不均衡问题:
    (1)若正样本远多于负样本,且负样本数量足够大,可以对正样本进行下/降采样,例如随机采样,实际场景下可能用到分层采样。
    (2)若正样本远多于负样本,且负样本数量不够多,可以收集更多的负样本,或对负样本进行上采样数据增广(例如对于图像数据,进行随机旋转、平移、缩放、镜像、图像增强等),还有修改损失函数的loss weights。

    展开全文
  • 机器学习实战-基本算法总结1

    万次阅读 2018-01-26 11:30:08
    机器学习基本算法总结 ☞监督学习——分类 代码在这,基于python3(原书代码是python2) 这里只是一个总结,原书已经讲解很清楚了,不清楚的直接看代码,或者李航的统计学习方法也有公式推导。 目录1 1....

    机器学习基本算法总结

    ☞监督学习——分类

    代码在这,基于python3(原书代码是python2)

    这里只是一个总结,原书已经讲解很清楚了,不清楚的直接看代码,或者李航的统计学习方法也有公式推导。

    目录1

    ==========================

    一、k-近邻算法(kNN)

    1.概述

    k-NN算法是最简单的分类算法,主要的思想是计算待分类样本与训练样本之间的差异性,并将差异按照由小到大排序,选出前面K个差异最小的类别,并统计在K个中类别出现次数最多的类别为最相似的类,最终将待分类样本分到最相似的训练样本的类中。与投票(Vote)的机制类似。
    k-近邻算法是基于实例的学习,使用算法时我们必须有接近实际数据的训练样本数
    据。

    • 优点:精度高,对异常值不敏感,无数据输入假定
    • 缺点:时间和空间复杂度高,无法获取样本特征
    • 数据:数值型和标称型

    2.算法介绍

    • 训练算法:此步骤不适用于k-临近算法
    • 测试算法:计算错误率
    • 使用算法:首先需要输入样本数据和结构化的输出结果,然后运行k-临近算法判定输入数据分别属于哪个分类,最后应用对计算出的分类执行后续处理。
    ##2.1 错误率

    error_rate=分错的样本数量 / 总样本数量

    ##2.2 归一化

    newvalue=(oldvalue-min) / (mx-min)

    3.伪代码

    对未知类别属性的数据集中的每个点依次执行以下操作:
    (1)计算已知类别数据集中的点与当前点之间的距离;
    (2)按照距离递增次序排序;
    (3)选取与当前点欧氏距离最小的k个点
    (4)确定前k个点所在类别的出现频率;
    (5)返回前k个点出现频率最高的类别作为当前点的预测分类。

    4.实例

    1、约会网站配对案例

    某人将对象分为三类人,不喜欢的人,魅力一般的人,极具魅力的人。
    这里实现的过程是,给定一个人的数据,进行打分预测属于哪类人,从而帮助用户是否选择相亲进行决策。

    2、手写数字识别实战案例

    5.存在的问题及解决方法、总结

    算法小结:
    (1)如果我们改变训练样本的数目,调整相应的k值,都会对最后的预测错误率产生影响,我们可以根据错误率的情况,对这些变量进行调整,从而降低预测错误率

    (2)k近邻算法是基于实例的学习,使用算法时我们必须有接近实际数据的训练样本数据。k近邻算法必须保存全部数据集,如果训练数据集很大,必须使用大量的存储空间。此外,由于必须对数据集中的每个数据计算距离,实际使用时也可能会非常耗时
    (3)此外,k近邻算法无法给出数据的基础结构信息,因此我们无法知道平均实例样本和典型实例样本具有怎样的特征。

    1、计算复杂度的问题
      在K-NN算法中,每一个预测样本需要与所有的训练样本计算相似度,计算量比较大。比较常用的方法有K-D树,局部敏感哈希等等

    2、K-NN的均匀投票
      在上述的K-NN算法中,最终对标签的选择是通过投票的方式决定的,在投票的过程中,每一个训练样本的投票的权重是相等的,
      (1)可以对每个训练样本的投票加权,以期望最相似的样本有更高的决策权。
      (2)归一化。

    ===============================================================

    二、决策树ID3

    1.概述

      k-近邻算法可以完成很多分类任务,但是它最大的缺点就是无法给出数据的内在含义,决策树的主要优势就在于数据形式非常容易理解。

      决策树算法是从数据的属性(或者特征)出发,以属性作为基础,划分不同的类。
      实现决策树的算法有很多种,有ID3、C4.5和CART等算法。

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

    2.算法介绍

    • 训练算法:构造树的数据结构。
    • 测试算法:使用经验树计算错误率。
    • 使用算法:此步骤可以适用于任何监督学习算法,而使用决策树可以更好地理解数据
      的内在含义。
    2.1 ID3算法

      ID3算法是由Quinlan首先提出的,该算法是以信息论为基础,以信息熵和信息增益为衡量标准,从而实现对数据的归纳分类。
    (1) 在ID3算法中,选择信息增益最大的属性作为当前的特征对数据集分类。
    (2) 判断划分结束,第一种为划分出来的类属于同一个类,第二种为遍历完所有划分数据集的属性。

    2.2 信息增益

       ID3算法是以信息熵和信息增益作为衡量标准的分类算法。
      熵的概念主要是指信息的混乱程度,变量的不确定性越大,熵的值也就越大,熵定义为信息的期望值。
    符号xi的信息定义为:

    (1)l(xi)=log2p(xi)

      其中p(xi)是选择该分类的概率。
      为了计算熵,我们需要计算所有类别所有可能值包含的信息期望值,通过下面的公式得到:
    (2)H=i=1np(xi)log2p(xi)

      划分数据集的大原则是:将无序的数据变得更加有序。在划分数据集之前之后信息发生的变化称为信息增益,,获得信息增益最高的特征就是最好的选择。

    3.伪代码

    对未知类别属性的数据集中的每个点依次执行以下操作:
    (1)选择特征
    (2)划分数据集——寻找划分数据集的最好特征,创建分支节点
    (3)满足终止条件
    (4)满足就结束,不满足则回到(1)

    4.实例

    4.1 预测眼镜蛇类型

    存在过度匹配问题

    5.存在的问题及解决方法

    1、过度匹配数据集

       裁剪决策树,合并相邻无法产生大量信息增益的叶节点,消除过度匹配问题。
    

      当决策树的复杂度较大时,很可能会造成过拟合问题。此时,我们可以通过裁剪决策树的办法,降低决策树的复杂度,提高决策树的泛化能力。比如,如果决策树的某一叶子结点只能增加很少的信息,那么我们就可将该节点删掉,将其并入到相邻的结点中去,这样,降低了决策树的复杂度,消除过拟合问题。

    ===============================================================

    三、基于概率论的分类方法:朴素贝叶斯

    1.概述

      前两章的KNN分类算法和决策树分类算法最终都是预测出实例的确定的分类结果,但是,有时候分类器会产生错误结果;本章要学的朴素贝叶斯分类算法则是给出一个最优的猜测结果,同时给出猜测的概率估计值。利用已知值估计未知概率

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

    2.算法介绍

    • 训练算法:计算不同的独立特征的条件概率。
    • 测试算法:计算错误率。
    • 使用算法:一个常见的朴素贝叶斯应用是文档分类。可以在任意的分类场景中使_用朴素贝叶斯命类器,不一定非要是文本。输入数据分别属于哪个分类,最后应用对计算出的分类执行后续处理。
    2.1 条件概率

    (1)P(c|x)=P(c,x)P(x)=P(x|c)P(c)P(x)

    2.2 如何使用条件概率进行分类

      假设这里要被分类的类别有两类,类c1和类c2,那么我们需要计算概率p(c1|x,y)和p(c2|x,y)的大小并进行比较:

    如果:p(c1|x,y)>p(c2|x,y),则(x,y)属于类c1

         p(c1|x,y)<p(c2|x,y),则(x,y)属于类c2
    

      我们知道p(x,y|c)的条件概率所表示的含义为:已知类别c条件下,取到点(x,y)的概率;那么p(c|x,y)所要表达的含义呢?显然,我们同样可以按照条件概率的方法来对概率含义进行描述,即在给定点(x,y)的条件下,求该点属于类c的概率值。那么这样的概率该如何计算呢?显然,我们可以利用贝叶斯准则来进行变换计算:

    (2)p(ci|x,y)=p(x,y|ci)p(ci)p(x,y)

    上述公式写为:
    (3)p(ci|w)=p(w|ci)p(ci)p(w)

    3.伪代码

    朴素贝叶斯完成文档分类依次执行以下操作:
    计算每个类别文档的数目
    计算每个类别占总文档数目的比例

    • 对每一篇文档:
        - 对每一个类别:
          - 如果词条出现在文档中->增加该词条的计数值#统计每个类别中出现的词条的次数
          - 增加所有词条的计数值#统计每个类别的文档中出现的词条总数
        - 对每个类别:
          - 将各个词条出现的次数除以类别中出现的总词条数目得到条件概率
    • 返回每个类别各个词条的条件概率和每个类别所占的比例

    4.实例

    1、文档分类
    • 针对算法的部分改进

    1)计算概率时,需要计算多个概率的乘积以获得文档属于某个类别的概率,即计算p(w0|ci)p(w1|ci)…p(wN|ci),然后当其中任意一项的值为0,那么最后的乘积也为0.为降低这种影响,采用拉普拉斯平滑,在分子上添加a(一般为1),分母上添加ka(k表示类别总数),即在这里将所有词的出现数初始化为1,并将分母初始化为2*1=2

    2)解决下溢出问题
      正如上面所述,由于有太多很小的数相乘。计算概率时,由于大部分因子都非常小,最后相乘的结果四舍五入为0,造成下溢出或者得不到准确的结果,所以,我们可以对成绩取自然对数,即求解对数似然概率。这样,可以避免下溢出或者浮点数舍入导致的错误。同时采用自然对数处理不会有任何损失。

    3)上面也提到了关于如何选取文档特征的方法,上面用到的是词集模型,即对于一篇文档,将文档中是否出现某一词条作为特征,即特征只能为0不出现或者1出现;然后,一篇文档中词条的出现次数也可能具有重要的信息,于是我们可以采用词袋模型,在词袋向量中每个词可以出现多次,这样,在将文档转为向量时,每当遇到一个单词时,它会增加词向量中的对应值

    2、过滤垃圾邮件
    • 切分数据
        这样就得到了一系列词组成的词表,但是里面的空字符串还是需要去掉,此时我们可以通过字符的长度,去掉长度等于0的字符。并且,由于我们是统计某一词是否出现,不考虑其大小写,所有还可以将所有词转为小写字符,即lower(),相应的,转为大写字符为upper()
        此外,需要注意的是,由于是URL,因而可能会出现en和py这样的单词。当对URL进行切分时,会得到很多的词,因此在实现时也会过滤掉长度小于3的词。当然,也可以根据自己的实际需要来增加相应的文本解析函数。

    • 交叉验证
        代码中,采用随机选择的方法从数据集中选择训练集,剩余的作为测试集。这种方法的好处是,可以进行多次随机选择,得到不同的训练集和测试集,从而得到多次不同的错误率,我们可以通过多次的迭代,求取平均错误率,这样就能得到更准确的错误率。这种方法称为留存交叉验证

    3、朴素贝叶斯从个人广告中获取区域倾向

      在本例中,我们通过从不同的城市的RSS源中获得的同类型广告信息,比较两个城市人们在广告用词上是否不同。如果不同,那么各自的常用词是哪些?而从人们的用词当中,我们能否对不同城市的人所关心的内容有所了解?如果能得到这些信息,分析过后,相信对于广告商而言具有不小的帮助。
      需要说明的是,这里用到了将出现次数最多的30个单词删除的方法,结果发现去掉了这些最常出现的高频词后,错误率大幅度上升,这表明了文本中的小部分高频单词占据了文本中绝大部分的用词。产生这种情况的原因是因为语言中大部分是冗余和结果辅助性内容。所以,我们不仅可以尝试移除高频词的方法,还可以进一步从某个预定词表(停用词表)中移除结构上的辅助词,通过移除辅助性词,分类错误率会所有下降

     此外,为了得到错误率的精确估计,应进行多次上述实验,从而得到错误率平均值。
    

    5.存在的问题及解决方法

      朴素贝叶斯在数据较少的情况下仍然适用,虽然例子中为两类类别的分析,但是朴素贝叶斯可以处理多分类的情况;朴素贝叶斯的一个不足的地方是,对输入的数据有一定的要求,需要花费一定的时间进行数据的处理和解析。朴素贝叶斯中用来计算的数据为标称型数据,我们需要将字符串特征转化为相应的离散值,用于后续的统计和计算。

    ===============================================================

    四、Logistic回归

    1.概述

    ogistic回归是一种简单的分类算法,利用logistic回归进行分类的主要思想是:根据现有数据对分类边界线建立回归公式,以此进行分类。
    而“回归”也就意味着最佳拟合。要进行最佳拟合,则需要寻找到最佳的拟合参数,一些最优化方法就可以用于最佳回归系数的确定。

    我们知道,logistic回归主要是进行二分类预测,也即是对于0~1之间的概率值,当概率大于0.5预测为1,小于0.5预测为0.显然,我们不能不提到一个函数,即sigmoid=11+ez,该函数的曲线类似于一个s型,在x=0处,函数值为0.5.

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

    2.算法介绍

    • 训练算法:大部分时间将用于训练,训练的目的是为了找到最佳的分类回归系数。
    • 测试算法:一旦训练步驟完成,分类将会很快。
    • 使用算法:首先,我们需要输入一些数据,并将其转换成对应的结构化数值;
      接着,基于训练好的回归系数就可以对这些数值进行简单的回归计算,判定它们属于哪个类别,在这之后,我们就可以夺输出的类别上做一些其他分析工作。
    2.1 确定最佳回归系数

    sigmoid函数的输入记为z,即

    (1)z=w0x0+w1x1+w2x2+...+wnxn

    记为:
    (1)z=wTx

    最优化方法有基于梯度的梯度下降法梯度上升法改进的随机梯度上升法等等。基于梯度的优化方法在求解问题时,本身对要求解的问题有要求:即问题本身必须是可导的。其次,基于梯度的方法会使得待优化问题陷入局部最优。此时,一些启发式优化方法可以很好的解决这样的问题,但是启发式算法的求解速度较慢,占用内存较大。
    (1)梯度上升它的基本思想是:要找到某函数的最大值,最好的方法就是沿着该函数的梯度方向搜寻。如果函数为f,梯度记为D,a为步长,那么梯度上升法的迭代公式为:
    (3)ww+αΔwf(w)

    (2)随机梯度上升法我们知道梯度上升法每次更新回归系数都需要遍历整个数据集,当样本数量较小时,该方法尚可,但是当样本数据集非常大且特征非常多时,那么随机梯度下降法的计算复杂度就会特别高。一种改进的方法是一次仅用一个样本点来更新回归系数。由于可以在新样本到来时对分类器进行增量式更新,因此随机梯度上升法是一个在线学习算法。

    2.2 处理数据中的缺失值

    我们可能会遇到数据缺失的情况,但有时候数据相当昂贵,扔掉和重新获取均不可取,这显然是会带来更多的成本负担,所以我们可以选取一些有效的方法来解决该类问题。比如:

      1 使用可用特征的均值填补缺失值

      2 使用特殊值来填补缺失的特征,如-1

      3 忽略有缺失值的样本

      4 使用相似样本的平均值填补缺失值

      5 使用另外的机器学习算法预测缺失值

    3.伪代码

    使用梯度上升法寻找最佳参数
    假设有100个样本点,每个样本有两个特征:x1和x2.此外为方便考虑,我们额外添加一个x0=1,将线性函数z=wTx+b转为z=wTx(此时向量w和x的维度均价

    1).那么梯度上升法的伪代码如下:

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

    2)随机梯度上升法可以写成如下伪代码:

    • 所有回归系数初始化为1
    • 对数据集每个样本
        - 计算该样本的梯度
        - 使用alpha*gradient更新回顾系数值
    • 返回回归系数值

    4.实例

    1、从疝气病症预测病马死亡率
    • 处理数据缺失:
      这里我们根据logstic回归的函数特征,选择实数0来替换所有缺失值,而这恰好能适用logistic回归。因此,它在参数更新时不会影响参数的值。即如果某特征对应值为0 ,那么由公式w:w+alpha*gradient,可知w不会发生改变。

        此外,由于sigmoid(0)=0.5,表面该特征对结果的预测不具有任何倾向性,因此不会对误差造成影响。

        当然,如果是发生有样本的类标签缺失的情况,此时我们最好的办法是将该样本舍弃,这是因为标签与特征不同,我们很难确定采用某个合适的值替换掉。

    5.存在的问题及解决方法

       logistic回归的目的是寻找一个非线性函数sigmoid的最佳拟合参数,从而来相对准确的预测分类结果。为了找出最佳的函数拟合参数,最常用的优化算法为梯度上升法,当然我们为了节省计算损耗,通常选择随机梯度上升法来迭代更新拟合参数。并且,随机梯度上升法是一种在线学习算法,它可以在新数据到来时完成参数的更新,而不需要重新读取整个数据集来进行批处理运算。

      总的来说,logistic回归算法,其具有计算代价不高,易于理解和实现等优点;此外,logistic回归算法容易出现欠拟合,以及分类精度不太高的缺点。
       我们知道,评判一个优化算法的优劣的可靠方法是看其是否收敛,也就是说参数的值是否达到稳定值。此外,当参数值接近稳定时,仍然可能会出现一些小的周期性的波动。这种情况发生的原因是样本集中存在一些不能正确分类的样本点(数据集并非线性可分),所以这些点在每次迭代时会引发系数的剧烈改变,造成周期性的波动。显然我们希望算法能够避免来回波动,从而收敛到某个值,并且收敛速度也要足够快。
    改进:
    1 alpha在每次迭代更新是都会调整,这会缓解数据波动或者高频运动。此外,alpha还有一个常数项,目的是为了保证在多次迭代后仍然对新数据具有一定的影响,如果要处理的问题是动态变化的,可以适当加大该常数项,从而确保新的值获得更大的回归系数。

    2 第二个改进的地方是选择随机的样本对参数进行更新,由于增加了随机性,这就防止参数值发生周期性的波动。

    ===============================================================

    五、支持向量机(SVM)

    1.概述

      SVM有很多实现,但是本章只关注其中最流行的一种实现,即序列最小优化,在此之后,将介绍如何使用一种称为核函数(kernel)的方式将SVM扩展到更多数据集上。
      支持向量机是一种二类分类算法,假设一个平面可以将所有的样本分为两类,位于正侧的样本为一类,值为+1,而位于负一侧的样本为另外一类,值为-1。虽然SVM本身是一个二类分类器,若要解决多类问题,需要修改SVM。

      我们说分类,不仅仅是将不同的类别样本分隔开,还要以比较大的置信度来分隔这些样本,这样才能使绝大部分样本被分开。比如,我们想通过一个平面将两个类别的样本分开,如果这些样本是线性可分(或者近视线性可分),那么这样的平面有很多,但是如果我们加上要以最大的置信度来将这些样本分开,那么这样的平面只有一条。

    • 1.几何间隔
        几何间隔的概念,简单理解就是样本点到分隔平面的距离
    • 2 间隔最大化
        想要间隔最大化,我们必须找到距离分隔平面最近的点,并且使得距离平面最近的点尽可能的距离平面最远,这样,每一个样本就都能够以比较大的置信度被分隔开算法的分类预测能力也就越好
        显然,SVM算法的关键所在,就是找到使得间隔最大化的分隔超平面(如果特征是高维度的情况,我们称这样的平面为超平面)。简言之:最大化支持向量到超平面距离

    • 优点:泛化错误率低,计算开销不大,结果易解释。

    • 缺点:对参数调节和核函数的选择敏感,原始分类器不加修改仅适用于处理二类问题。
    • 适用数据类型:数值型和标称型数据。

    2.算法介绍

    支持向量机推导

    • 训练算法:SVM的大部分时间都源自训练,该过程主要实现两个参数的调优。
    • 测试算法:十分简单的计算过程就可以实现。
    • 使用算法:几乎所有分类问题都可以使用SVM,值得一提的是,S V M 本身是一个二类分类器,对多类问题应用SVM需要对代码做一些修改。

    下面介绍线性支持向量机,近似线性支持向量机以及非线性支持向量机(核函数)

    2.1 线性支持向量机

      求解线性支持向量机的过程是凸二次规划问题,所谓凸二次规划问题,就是目标函数是凸的二次可微函数,约束函数为仿射函数满足
    而我们说求解凸二次规划问题可以利用对偶算法–即引入拉格朗日算子,利用拉格朗日对偶性将原始问题的最优解问题转化为拉格朗日对偶问题,这样就将求wb的原始问题的极小问题转化为求
    α

    (1)α>=0,i=1mαilable(i)=0

    的对偶问题的极大问题,即求出α,在通过KKT条件求出对应的参数w,b,从而找到这样的间隔最大化超平面,进而利用该平面完成样本分类。目标函数如下:
    (2)maxα[i=1mα12i,j=1mlabel(i)label(j)αiαj<x(i),x(j)>]

    2.2 近似线性支持向量机

      当数据集并不是严格线性可分时,即满足绝不部分样本点是线性可分,存在极少部分异常点;这里也就是说存在部分样本不能满足约束条件,此时我们可以引入松弛因子,这样这些样本点到超平面的函数距离加上松弛因子,就能保证被超平面分隔开来;当然,添加了松弛因子σ,我们也会添加对应的代价项,使得

    (3)α$$0=<α<=C$$i=1mαilable(i)=0

    2.3 非线性支持向量机

      显然,当数据集不是线性可分的,即我们不能通过前面的线性模型来对数据集进行分类。此时,我们必须想办法将这些样本特征符合线性模型,才能通过线性模型对这些样本进行分类。这就要用到核函数,核函数的功能就是将低维的特征空间映射到高维的特征空间,而在高维的特征空间中,这些样本进过转化后,变成了线性可分的情况,这样,在高维空间中,我们就能够利用线性模型来解决数据集分类问题
      如果想要透彻理解SVM建议还是要看看书和博客文章,篇幅有限,我这里的中心在于凸二次规划的优化算法——SMO(序列最小最优化算法)

    2.4 SMO优化算法

      SMO算法的工作原理是:每次循环中选择两个α进行优化处理。一旦找到一对合适的α,那么就增大其中一个而减少另外一个。这里的”合适”,意味着在选择α对时必须满足一定的条件,条件之一是这两个α不满足最优化问题的kkt条件,另外一个条件是这两个α还没有进行区间化处理,对于SMO算法编写,我们采用由简单到复杂的方法,层层递进,完成最终的SMO算法实现,最后通过实际的用例对SVM模型进行训练,并验证准确性。

    3.伪代码

    3.1 简化版SMO算法

      简化版SMO算法,省略了确定要优化的最佳α对的步骤,而是首先在数据集上进行遍历每一个α,再在剩余的数据集中找到另外一个α,构成要优化的α对,同时对其进行优化,这里同时是要确保式:i=1mαi·lable(i)=0。所以改变一个α显然会导致等式失效,所以这里需要同时改变两个α

    伪代码:

    • 创建一个alpha向量并将其初始化为0向量
    • 当迭代次数小于最大迭代次数时(w外循环)
        - 对数据集中每个数据向量(内循环):
          - 如果该数据向量可以被优化:
            - 随机选择另外一个数据向量
            - 同时优化这两个向量
            - 如果两个向量都不能被优化,退出内循环
        - 如果所有向量都没有被优化,增加迭代次数,继续下一次循环

        当然,上面的代码通过对整个数据集进行两次遍历的方法来寻找α对的方法,显然存在一定的不足,如果数据集规模较小的情况下,或许还可以满足要求。但是对于大规模的数据集而言,上面的代码显然收敛速度非常慢,所以,接下来我们在此基础上对选取合适的α对方法进行改进,采用启发式的方法来选取合适的α对,从而提升运算效率。

    3.2 启发式选取alpha变量的SMO算法

    启发式的SMO算法一个外循环来选择第一个α值,并且其选择过程会在下面两种方法之间进行交替:
    (1)在所有数据集上进行单遍扫描
    (2)另一种方法是在间隔边界上样本点进行单遍扫描,所谓间隔边界上的点即为支持向量点。
       显然,对于整个数据集遍历比较容易,而对于那些处于间隔边界上的点,我们还需要事先将这些点对应的α值找出来,存放在一个列表中,然后对列表进行遍历;此外,在选择第一个α值后,算法会通过一个内循环来选择第二个值。建立一个全局的缓存用于保存误差值,从中选择是的步长(或者 EiEj )最大的α值。
      上面的SMO完整代码是分为内外两个循环函数来编写的,采取这样的结构可以更方便我们去理解选取两个α的过程;既然,我们已经计算出了α值和b值,那么显然我们可以利用公式w=Σαi·label[i]·dataMat[i,:]计算出相应的权值参数,然后就可以得到间隔超平面的公式wx+b来完成样本的分类了,由于SVM算法是一种二类分类算法,正值为1,负值为-1,即分类的决策函数为跳跃函数signwx+b

    3.33 核函数

      核函数的目的主要是为了解决非线性分类问题,通过核技巧将低维的非线性特征转化为高维的线性特征,从而可以通过线性模型来解决非线性的分类问题。
    例如,当数据集不是线性可分时,即数据集分布是下面的圆形该怎么办呢?

    1

      显然,此时数据集线性不可分,我们无法用一个超平面来将两种样本分隔开;那么我们就希望将这些数据进行转化,转化之后的数据就能够通过一个线性超平面将不同类别的样本分开,这就需要核函数,核函数的目的主要是为了解决非线性分类问题,通过核技巧将低维的非线性特征转化为高维的线性特征,从而可以通过线性模型来解决非线性的分类问题
      而径向基核函数,是SVM中常用的一个核函数。径向基核函数是一个采用向量作为自变量的函数,能够基于向量距离运算输出一个标量。径向基核函数的高斯版本公式为:

    (4)k(xy)=exp(||xy||2)2σ2

    其中,σ为到达率,是超参数,决定了函数值跌落至0的速度。
     有了高斯核函数之后,我们只要将上面的SMO算法中所有的内积项替换为核函数即可。
      另外:有了核函数,我们就能对非线性的数据集进行分类预测了,接下来就是编写代码利用核函数进行测试,需要说明的是,在优化的过程中,我们仅仅需要找到支持向量和其对应的α值,而对于其他的样本值可以不用管,甚至可以舍弃,因为这些样本将不会对分类预测函数造成任何影响。这也就是SVM相比KNN算法的优秀的地方所在。

      通过输入不同的σ值(当然,迭代次数也会有一定的影响,我们只讨论σ值),我们发现测试错误率,训练误差率,支持向量个数都会发生变化,在一定的范围内,支持向量数目的下降,会使得训练错误率和测试错误率都下降,但是当抵达某处的最优值时,再次通过增大σ值的方法减少支持向量,此时训练错误率下降,而测试误差上升
      简言之,对于固定的数据集,支持向量的数目存在一个最优值,如果支持向量太少,会得到一个很差的决策边界;而支持向量太多,也相当于利用整个数据集进行分类,就类似于KNN算法,显然运算速度不高。

    4.实例  

      可以发现:相较于kNN算法,尽管kNN也能取得不错的效果;但是从节省内存的角度出发,显然SVM算法更胜一筹,因为其不需要保存真个数据集,而只需要其作用的支持向量点,而取得不错的分类效果。
      对于固定的数据集,存在最优的支持向量个数,使得分类错误率最低。支持向量的个数会随着σ值的增大而逐渐减少,但是分类错误率确实一个先降低后升高的过程。即最小的分类错误率并不意味着最少的支持向量个数。
      

    5.存在的问题及解决方法、总结

       支持向量机是一种通过求解凸二次规划问题来解决分类问题的算法,具有较低的泛化错误率。而SMO算法可以通过每次只优化两个alpha值来加快SVM的训练速度。
      核技巧是将数据由低维空间映射到高维空间,可以将一个低维空间中的非线性问题转换为高维空间下的线性问题来求解。而径向基核函数是一个常用的度量两个向量距离的核函数。

    ===============================================================

    六、Logistic回归

    1.概述

      AdaBoost分类器就是一种元算法分类器,adaBoost分类器利用同一种基分类器(弱分类器),基于分类器的错误率分配不同的权重参数,最后累加加权的预测结果作为输出。

    • 1.元算法:对其他算法进行组合的一种方式,这种组合结果也可以叫做集成方法。
    • 2.bagging方法:其是从原始数据集选择s次后得到s个新数据集的一种技术。需要说明的是,新数据集和原数据集的大小相等。每个数据集都是通过在原始数据集上先后随机选择一个样本来进行替换得到的新的数据集(即先随机选择一个样本,然后随机选择另外一个样本替换之前的样本),并且这里的替换可以多次选择同一样本,也就是说某些样本可能多次出现,而另外有一些样本在新集合中不再出现。s个数据集准备好之后,将某个学习算法分别作用于每个数据集就得到s个分类器。当要对新的数据进行分类时,就应用这s个分类器进行分类,最后根据多数表决的原则确定出最后的分类结果。
    • 3.boosting方法:首先,boosting集成了多个分类器,不同的分类器类型都是一致的,不过这些分类器是通过串行训练得到的(即每个新的分类器是通过原来已训练出的分类器训练得到的),集中关注被前面分类器错分的数据来获得新的分类器。然后,boosting的分类结果是基于所有分类器加权求和得到的(这也是和bagging 不同的地方,bagging中的分类器权值都相等),分类器的错误率越低,那么其对应的权重也就越大,越容易对预测结果产生影响。boosting拥有多个版本,这里介绍其中最流行的Adaboost方法。很多人认为boosting和SVM是监督机器学习中最强大的两种方法,但是这它们之间也有很多相似之处。

    • 优点:泛化错误率低,易编码,可以应用在大部分分类器上,无参数调整。

    • 缺点:对离群点敏感。
    • 适用数据类型:数值型和标称型数据。

    2.算法介绍

    • 训练算法:Adaboost的大部分时间都用在训练上,分类器将多次在同一数据集上训练弱分类器。
    • 测试算法:计算分类的错误率,训练代码会帮我们保存每个弱分类器的重要信息,比如分类器系数,分类器的最优特征,特征阈值等。有了这些重要的信息,我们拿到之后,就可以对测试数据进行预测分类了
    • 使用算法:同SVM— 样,Adaboost预测两个类别中的一个。如果想把它应用到多个类别的场合,那么就要像多类SVM中的做法一样对Adaboost进行修改。
    2.1 AdaBoost的运行过程

     训练数据的每一个样本,并赋予其一个权重,这些权值构成权重向量D,维度等于数据集样本个数。开始时,这些权重都是相等的,首先在训练数据集上训练出一个弱分类器并计算该分类器的错误率,然后在同一数据集上再次训练弱分类器,但是在第二次训练时,将会根据分类器的错误率,对数据集中样本的各个权重进行调整,分类正确的样本的权重降低,而分类错的样本权重则上升,但这些权重的总和保持不变为1.
      并且,最终的分类器会基于这些训练的弱分类器的分类错误率,分配不同的决定系数α,错误率低的分类器获得更高的决定系数,从而在对数据进行预测时起关键作用。α的计算根据错误率得来:

    (1)α=0.5ln(1ε/max(ε,1e16))

    其中:ε=
    计算出α之后,就可以对权重向量进行更新了,使得分类错误的样本获得更高的权重,而分类正确的样本获得更低的权重。D的权重更新如下:
    (1)如果某个样本被正确分类,那么权重更新为:
      
    (2)D(t+1,i)=D(t,i)·exp(α)sum(D)

    (2)如果某个样本被错误分类,那么权重更新为:
      

    (3)D(t+1,i)=D(t,i)·exp(α)sum(D)

    其中,m为迭代的次数,即训练的第m个分类器,i为权重向量的第i个分量,i<=。直到错误率为0,或者弱分类器的数目达到用户指定值。

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

      单层决策树是一种简单的决策树,也称为决策树桩。单层决策树可以看做是由一个根节点直接连接两个叶结点的简单决策树。

    3.伪代码

    3.1寻找最佳的单层决策树(弱分类器)

    最佳单层决策树是具有最低分类错误率的单层决策树,伪代码如下:
    - 将最小错误率minError设为+∞
    - 对数据集中的每个特征(第一层特征):
    - 对每个步长(第二层特征):
    - 对每个不等号(第三层特征):
    - 建立一颗单层决策树并利用加权数据集对它进行测试
    - 如果错误率低于minError,则将当前单层决策树设为最佳单层决策树
    - 返回最佳单层决策树
    包含两个函数:
    第一个函数是分类器的阈值过滤函数,即设定某一阈值,凡是超过该阈值的结果被归为一类,小于阈值的结果都被分为另外一类,这里的两类依然同SVM一样,采用+1和-1作为类别。
    第二个函数,就是建立单层决策树的具体代码,基于样本值的各个特征及特征值的大小,设定合适的步长,获得不同的阈值,然后以此阈值作为根结点,对数据集样本进行分类,并计算错误率,需要指出的是,这里的错误率计算是基于样本权重的,所有分错的样本乘以其对应的权重,然后进行累加得到分类器的错误率。错误率得到之后,根据错误率的大小,跟当前存储的最小错误率的分类器进行比较,选择出错误率最小的特征训练出来的分类器,作为最佳单层决策树输出,并通过字典类型保存其相关重要的信息。

    3.2完整AdaBoost算法实现

    伪代码如下:

    • 对每次迭代:
        找到最佳的单层决策树
        将最佳单层决策树加入到单层决策树数组
        计算alpha
        计算新的权重向量D
        更新累计类别估计值
        如果错误率为等于0.0,退出循环
        
      需要说明的几点:
      (1)上面的输入除了数据集和标签之外,还有用户自己指定的迭代次数,用户可以根据自己的成本需要和实际情况,设定合适的迭代次数,构建出需要的弱分类器数量。
      (2)权重向量D包含了当前单层决策树分类器下,各个数据集样本的权重,一开始它们的值都相等。但是,经过分类器分类之后,会根据分类的权重加权错误率对这些权重进行修改,修改的方向为,提高分类错误样本的权重,减少分类正确的样本的权重
      (3)分类器系数α,是非常重要的参数,它在最终的分类器组合决策分类结果的过程中,起到了非常重要的作用,如果某个弱分类器的分类错误率更低,那么根据错误率计算出来的分类器系数将更高,这样,这些分类错误率更低的分类器在最终的分类决策中,会起到更加重要的作用。
      (4)上述代码的训练过程是以达到迭代的用户指定的迭代次数或者训练错误率达到要求而跳出循环。而最终的分类器决策结果,会通过sign函数,将结果指定为+1或者-1

    4.实例

    4.1 难数据集上应用adaBoost

    (1)随着分类器数目的增加,adaBoost分类器的训练错误率不断的减少,而测试错误率则是经历先减少到最小值,再逐渐增大的过程。显然,这就是所说的过拟合。因此,对于这种情况,我们应该采取相应的措施,比如采取交叉验证的方法,在训练分类器时,设定一个验证集合,不断测试验证集的分类错误率,当发现训练集错误率减少的同时,验证集的错误率较之上一次结果上升了,就停止训练。或者其他比较实用的模拟退火方法,基因遗传算法等。

    (2)前面的第四章的logistic回归分类器对该数据集的分类错误率是35%,显然adaBoost分类器取得了更好的分类效果。

    (3)有文献表明,对于表现好的数据集,AdaBoost的测试误差率会随着迭代次数的增加而逐渐稳定在某一个值附近,而不会出现上表中的先减小后上升的情况。显然,这里用到的数据集不能称为”表现好”的数据集,比较该数据集存在30%的数据缺失。
    在第四章的logistic回归中,我们讲这些确实的数据设置为0,显然这在logistic回归算法中是合适,这样不会对分类结果造成影响。但是,在adaBoost算法中依然这样设置,其合理性还有待证明,所以,有必要可以将这些缺失的数据值由0变成该特征相类似的数据或者该特征数据的平均值,再来进行adaBoost算法训练,看看得到的结果会不会有所提升?

    5.存在的问题及解决方法、总结

     多个分类器组合可能会进一步凸显出单分类器的不足,比如过拟合问题。如果分类器之间差别显著,那么多个分类器组合就可能会缓解这一问题。分类器之间的差别可以是算法本身或者是应用于算法上的数据的不同。
     在bagging中,是通过随机抽样的替换方式,得到了与原始数据集规模一样的数据集。而AdaBoost在bagging的思路上更进了一步,它在数据集上顺序应用了多个不同的分类器
     AdaBoost是以弱分类器作为基础分类器,输入数据之后,通过加权向量进行加权,在每一轮的迭代过程中都会基于弱分类器的加权错误率,更新权重向量,从而进行下一次迭代。并且会在每一轮迭代中计算出该弱分类器的系数,该系数的大小将决定该弱分类器在最终预测分类中的重要程度。显然,这两点的结合是AdaBoost算法的优势所在。

    ===============================================================

    七、非均衡分类问题

      在上述机器学习的分类问题中,我们都假设所有类别的分类代价是一样的。但是事实上,不同分类的代价是不一样的,比如我们通过一个用于检测患病的系统来检测马匹是否能继续存活,如果我们把能存活的马匹检测成患病,那么这匹马可能就会被执行安乐死;如果我们把不能存活的马匹检测成健康,那么就会继续喂养这匹马。一个代价是错杀一只昂贵的动物,一个代价是继续喂养,很明显这两个代价是不一样的。

    性能度量

      衡量模型泛化能力的评价标准,就是性能度量。除了基于错误率来衡量分类器任务的成功程度的。错误率指的是在所有测试样例中错分的样例比例。但是,这样却掩盖了样例如何被错分的事实。在机器学习中,有一个普遍试用的称为混淆矩阵(confusion matrix)的工具,可以帮助人们更好地了解分类的错误。

    正确率(Precision)、召回率(Recall)、ROC曲线

    • 正确率P = TP/(TP+FP),给出的是预测为正例的样本中的真正正例的比例。
    • 召回率R = TP/(TP+FN),给出的是预测为正例的真实正例占所有真实正例的比例。
    • ROC代表接收者操作特征”Receiver Operating Characteristic”
      ROC曲线的纵轴是“真正例率”,TPR=TP/(TP+FN)
      横轴是“假正例率”,FPR=FP/(TN+FP)
      (1)在理想的情况下,最佳的分类器应该尽可能地处于左上角,这就意味着分类器在假正例率很低的同时,获得了很高的真正例率
      (2)对不同的ROC曲线进行比较的一个指标就是曲线下的面积(AUC),AUC给出的是分类器的平均性能值。一个完美的分类器的AUC是1,而随机猜测的AUC则为0.5。
      (2)若一个学习器的ROC曲线能把另一个学习器的ROC曲线完全包住,则这个学习器的性能比较好。

    基于代价函数的分类器决策控制(方法更好)

      例如代价敏感学习:为权衡不同类型错误所造成的不同损失,可为错误赋予“非均等代价”。在“代价矩阵”中,将-1错判成+1的代价(50),比把+1错判成-1的代价(1)要高。
      在分类算法中,我们有很多方法可以用来引人代价信息。(1)在AdaBoost中,可以基于代价函数来调整错误权重向量D 。(2)在朴素贝叶斯中,可以选择具有最小期望代价而不是最大概率的类别作为最后的结果。(3)在S V M 中,可以在代价函数中对于不同的类别选择不同的参数c。上述做法就会给较小类更多的权重,即在训练时,小类当中只允许更少的错误。

    处理非均衡问题的数据抽样方法(方法可以)

      另外一种针对非均衡问题调节分类器的方法,就是对分类器的训练数据进行改造。这可以通过欠抽样或者过抽样来实现。过抽样意味着复制样例,而欠抽样意味着删除样例
      如前所述,正例类别属于罕见类别。我们希望对于这种罕见类别能尽可能保留更多的信息,因此,我们应该保留正例类别中的所有样例,而对反例类别进行欠抽样或者样例删除处理。这种方法的一个缺点就在于要确定哪些样例需要进行副除。但是,在选择副除的样例中可能携带了剩余样例中并不包含的有价值信息。
    上述问题的一种解决办法,就是选择那些离决策边界较远的样例进行删除。假定我们有一个数据集,其中有50例信用卡欺诈交易和5000例合法交易。如果我们想要对合法交易样例进行欠抽样处理,使得这两类数据比较均衡的话,那么我们就需要去掉4950个样例,这看上去有些极端,因此有一种替代的策略就是使用反例类别的欠抽样和正例类别的过抽样相混合的方法。要对正例类别进行过抽样,我们可以复制已有样例或者加入与已有样例相似的点,例如,加人已有数据点的插值点,但是这种做法可能会导致过拟合的问题。

    总结

      非均衡分类问题是指在分类器训练时正例数目和反例数目不相等(相差很大)。该问题在错分正例和反例的代价不同时也存在。
      通过过抽样和欠抽样方法来调节数据集中的正例和反例数目。另外一种可能更好的非均衡问题的处理方法,就是在训练分类器时将错误的代价考虑在内。

    回归很像分类,但是和分类输出标称型类别值不同的是,回归方法会预测出一个连续值。

    展开全文
  • 机器学习算法总览——思维导图

    千次阅读 2015-10-01 15:24:42
    如下图,是对机器学习常见算法的一个总结,在后期我会再对常用算法做一个细致的介绍!
  • 机器学习算法——回归算法总结(一) 回归算法与分类算法都属于监督学习算法,不同的是,分类算法中标签是一些离散值,代表不同的分类,而回归算法中,标签是一些连续值,回归算法需要训练得到样本特征到这些连续...
  • 机器学习算法总结

    千次阅读 2018-08-19 11:23:02
    ~~~~~·个人整理,如需转载,请说明并备注,不甚感激~~...BAT机器学习面试系列 1.请简要介绍下SVM。 SVM,全称是support vector machine,中文名叫支持向量机。SVM是一个面向数据的分类算法,它的目标是为确定一个...
  • 机器学习算法汇总大全,对常见的算法用比较容易理解的语言进行描述,相比直接看算法公式更容易理解
  • 机器学习算法总结(一)

    千次阅读 2018-08-30 17:51:52
    1、TF-IDF文本相似度分析 ...那么对于我们写程序实现这个算法,就是把两个个体转换为向量,然后通过这个公式求出最终解。 比如向量a(x1, x2, x3, x4, x5),向量b(y1, y2, y3, y4, y5)。分子为(x1*y1)+(...
  • 一、机器学习算法工程师笔试题 机器学习笔试题目—-网易2016春招 BAT机器学习面试1000题系列 机器学习-算法工程师 -面试/笔试准备-重要知识点梳理 总结一点面试问题--算法工程师(机器学习) 2018 年大疆机器...
  • 机器学习——几种分类算法的汇总

    千次阅读 2019-06-25 01:03:45
    https://www.cnblogs.com/Zhi-Z/p/8912396.html
  • 机器学习岗位的面试准备——总结1

    万次阅读 2017-10-25 21:24:17
    数据结构算法水题+常用机器学习算法推导+模型调优细节+业务认识 每一个都很重要,尤其是最后一个,最后给出算法工程师的特质,可以写在简历上:善于对事物深入思考 2、写给准备参加秋招的学弟学妹们~一定要来看哦~
  • 想写这个总结很久了,但是都... 机器学习总结分为两个系列,另外一个系列重点是深度学习(DL)。我会不定期改动我的每一篇文章,将我认为最好、最精粹的部分保留下来,原理讲解完了都会附上Python的代码实现,基本在这个
  • 人工智能之机器学习常见算法

    万次阅读 多人点赞 2019-04-11 11:18:17
    摘要之前一直对机器学习很感兴趣,一直没时间去研究,今天刚好是...这里IT经理网为您总结一下常见的机器学习算法,以供您在工作和学习中参考。 机器学习的算法很多。很多时候困惑人们都是,很多算法是一类算法,而有
  • 程序员初学机器学习的四种方式

    万次阅读 2015-10-01 16:31:53
    网址 http://machinelearningmastery.com/self-study-machine-learning-projects/学习机器学习有很多方法,大多数人选择从理论开始。...这些对任何一个职业程序员来说都是重要的能力,现在它们也能用在初学机器学习上。
  • 数据挖掘,机器学习,深度学习,推荐算法的联系与区别
  • 机器学习十大算法都是何方神圣?看完你就懂了

    万次阅读 多人点赞 2017-08-26 18:06:46
    雷锋网按:机器学习与人工智能变得越来越热。大数据原本在工业界中就已经炙手可热,而基于大数据的机器学习则更加流行,...跟我们生活息息相关的最常见机器学习算法包括电影推荐算法、图书推荐算法。这些算法都是基
  • MLlib算法简介

    万次阅读 2015-04-10 12:01:33
    主要的机器学习算法目前在MLlib中都已经提供了,分类回归、聚类、关联规则、推荐、降维、优化、特征抽取筛选、用于特征预处理的数理统计方法、以及算法的评测
  • 来源:机器学习算法盘点 - ranjiewen - 博客园http://www.cnblogs.com/ranjiewen/p/6235388.html为啥感觉完全是被圈粉了----好厉害啊------主页都那么...这里我们将为您总结一下常见的机器学习算法,以供您在工作和...
  • 机器学习的常用方法

    万次阅读 多人点赞 2018-05-10 22:38:27
    转自 史上最强----机器学习经典总结---入门必读----心血总结-----回味无穷在这个部分我会简要介绍一下机器学习中的经典代表方法。这部分介绍的重点是这些方法内涵的思想,数学与实践细节不会在这讨论。 1、回归...
1 2 3 4 5 ... 20
收藏数 129,015
精华内容 51,606
关键字:

机器学习算法总结