人工智能的知识体系–分类算法

【声明】本文为AdamsLee原创,转载请注明出自围炉网并保留本文有效链接:人工智能的知识体系–分类算法, 转载请保留本声明!

识别某个对象属于哪个类别,常用的算法有:SVM(支持向量机)、nearest neighbors(最近邻)、random forest(随机森林),常见的应用有:垃圾邮件识别、图像识别。

  • 逻辑回归(Logistic Regression)

    • 主要解决二分类问题,用来表示某件事情发生的可能性。

    • 逻辑回归算法就是在样本数据中寻找一个超平面,然后可以把样本数据准确的分隔成不同的类别,并且能够对相应的新数据特征进行分类。逻辑回归的本质是:假设数据服从这个分布,然后使用极大似然估计做参数的估计。

    • 逻辑回归是在线性回归的基础上加了一个 Sigmoid 函数(非线形)映射,使得逻辑回归称为了一个优秀的分类算法。本质上来说,两者都属于广义线性模型,但他们两个要解决的问题不一样,逻辑回归解决的是分类问题,输出的是离散值,线性回归解决的是回归问题,输出的连续值。

    • 在逻辑回归中,最常用的是代价函数是交叉熵(Cross Entropy),交叉熵是一个常见的代价函数,在神经网络中也会用到。在线性回归中,最常用的是均方误差(Mean squared error)。

    • 优点:

      • 实现简单,广泛的应用于工业问题上;

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

      • 便利的观测样本概率分数;

      • 对逻辑回归而言,多重共线性并不是问题,它可以结合L2正则化来解决该问题;

      • 计算代价不高,易于理解和实现;

    • 缺点:

      • 当特征空间很大时,逻辑回归的性能不是很好;

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

      • 不能很好地处理大量多类特征或变量;

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

      • 对于非线性特征,需要进行转换;

    • 美团的应用案例

      • 预测用户对品类的购买偏好,该问题可以转换为预测用户在未来某个时间段是否会购买某个品类,如果把会购买标记为1,不会购买标记为0,就转换为一个二分类问题。用到的特征包括用户在美团的浏览,购买等历史信息,

      • 其中提取的特征的时间跨度为30天,标签为2天。生成的训练数据大约在7000万量级(美团一个月有过行为的用户),人工把相似的小品类聚合起来,最后有18个较为典型的品类集合。如果用户在给定的时间内购买某一品类集合,就作为正例。有了训练数据后,使用Spark版的LR算法对每个品类训练一个二分类模型,迭代次数设为100次的话模型训练需要40分钟左右,平均每个模型2分钟,测试集上的AUC也大多在0.8以上。训练好的模型会保存下来,用于预测在各个品类上的购买概率。预测的结果则会用于推荐等场景。

      • 由于不同品类之间正负例分布不同,有些品类正负例分布很不均衡,尝试了不同的采样方法,最终目标是提高下单率等线上指标。经过一些参数调优,品类偏好特征为推荐和排序带来了超过1%的下单率提升。

  • 决策树模型

    • 决策树是一种解决分类问题的算法。决策树算法采用树形结构,使用层层推理来实现最终的分类。

    • 决策树由下面几种元素构成:

      • 根节点:包含样本的全集

      • 内部节点:对应特征属性测试

      • 叶节点:代表决策的结果

    • 预测时,在树的内部节点处用某一属性值进行判断,根据判断结果决定进入哪个分支节点,直到到达叶节点处,得到分类结果。这是一种基于 if-then-else 规则的有监督学习算法,决策树的这些规则通过训练得到,而不是人工制定的。

    • 决策树是最简单的机器学习算法,它易于实现,可解释性强,完全符合人类的直观思维,有着广泛的应用。

    • 特征选择

      • 特征选择决定了使用哪些特征来做判断。在训练数据集中,每个样本的属性可能有很多个,不同属性的作用有大有小。因而特征选择的作用就是筛选出跟分类结果相关性较高的特征,也就是分类能力较强的特征。

    • 在特征选择中通常使用的准则是:信息增益。

    • 决策树生成

      • 选择好特征后,就从根节点触发,对节点计算所有特征的信息增益,选择信息增益最大的特征作为节点特征,根据该特征的不同取值建立子节点;对每个子节点使用相同的方式生成新的子节点,直到信息增益很小或者没有特征可以选择为止。

    • 决策树剪枝

      • 剪枝的主要目的是对抗「过拟合」,通过主动去掉部分分支来降低过拟合的风险。

    • 3 种典型的决策树算法

      • ID3 算法

        • ID3 是最早提出的决策树算法,他就是利用信息增益来选择特征的。

      • C4.5 算法

        • 是 ID3 的改进版,他不是直接使用信息增益,而是引入“信息增益比”指标作为特征的选择依据。

      • CART(Classification and Regression Tree)

        • 这种算法即可以用于分类,也可以用于回归问题。CART 算法使用了基尼系数取代了信息熵模型。

    • 决策树的优缺点

      • 优点

        • 决策树易于理解和解释,可以可视化分析,容易提取出规则;

        • 可以同时处理标称型和数值型数据;

        • 比较适合处理有缺失属性的样本;

        • 能够处理不相关的特征;

        • 测试数据集时,运行速度比较快;

        • 在相对短的时间内能够对大型数据源做出可行且效果良好的结果。

      • 缺点

        • 容易发生过拟合(随机森林可以很大程度上减少过拟合);

        • 容易忽略数据集中属性的相互关联;

        • 对于那些各类别样本数量不一致的数据,在决策树中,进行属性划分时,不同的判定准则会带来不同的属性选择倾向;信息增益准则对可取数目较多的属性有所偏好(典型代表ID3算法),而增益率准则(CART)则对可取数目较少的属性有所偏好,但CART进行属性划分时候不再简单地直接利用增益率尽心划分,而是采用一种启发式规则)(只要是使用了信息增益,都有这个缺点,如RF)。

        • ID3算法计算信息增益时结果偏向数值比较多的特征。

    • scikit-learn决策树算法类库内部实现是使用了调优过的CART树算法,既可以做分类,又可以做回归。分类决策树的类对应的是DecisionTreeClassifier,而回归决策树的类对应的是DecisionTreeRegressor。两者的参数定义几乎完全相同,但是意义不全相同。

  • 随机森林(Random forest)

    • 随机森林顾名思义,是用随机的方式建立一个森林,森林里面有很多的决策树组成,随机森林的每一棵决策树之间是没有关联的。在得到森林之后,当有一个新的输入样本进入的时候,就让森林中的每一棵决策树分别进行一下判断,看看这个样本应该属于哪一类(对于分类算法),然后看看哪一类被选择最多,就预测这个样本为那一类。随机森林可以既可以处理属性为离散值的量,比如ID3算法,也可以处理属性为连续值的量,比如C4.5算法。另外,随机森林还可以用来进行无监督学习聚类和异常点检测。

    • 优点

      • 它可以出来很高维度(特征很多)的数据,并且不用降维,无需做特征选择

      • 它可以判断特征的重要程度

      • 可以判断出不同特征之间的相互影响

      • 不容易过拟合

      • 训练速度比较快,容易做成并行方法

      • 实现起来比较简单

      • 对于不平衡的数据集来说,它可以平衡误差。

      • 如果有很大一部分的特征遗失,仍可以维持准确度。

    • 缺点

      • 随机森林已经被证明在某些噪音较大的分类或回归问题上会过拟合。

      • 对于有不同取值的属性的数据,取值划分较多的属性会对随机森林产生更大的影响,所以随机森林在这种数据上产出的属性权值是不可信的

    • 随机森林的4个应用方向

      • 对离散值的分类

      • 对连续值的回归

      • 无监督学习聚类

      • 异常点监测

    • 随机森林的分类学习器为RandomForestClassifier,回归学习器为RandomForestRegressor

  • 支持向量机(support vector machines, SVM)

    • 一种监督式学习的方法,可广泛地应用于统计分类以及回归分析(支持向量回归 Support Vector Regression或SVR)。

    • 是一种二分类模型,它的基本模型是定义在特征空间上的间隔最大的线性分类器,间隔最大使它有别于感知机;

            

    • SVM还包括核技巧,这使它成为实质上的非线性分类器。SVM的的学习策略就是间隔最大化,可形式化为一个求解凸二次规划的问题,也等价于正则化的合页损失函数的最小化问题。SVM的的学习算法就是求解凸二次规划的最优化算法。

    • 除了进行线性分类之外,SVM还可以使用所谓的核技巧有效地进行非线性分类,将其输入隐式映射到高维特征空间中。

    • 当数据未被标记时,不能进行监督式学习,需要用非监督式学习,它会尝试找出数据到簇的自然聚类,并将新数据映射到这些已形成的簇。将支持向量机改进的聚类算法被称为支持向量聚类,当数据未被标记或者仅一些数据被标记时,支持向量聚类经常在工业应用中用作分类步骤的预处理。

    • SVM的优缺点

      • 优点

        • 可以解决高维问题,即大型特征空间;

        • 解决小样本下机器学习问题;

        • 能够处理非线性特征的相互作用;

        • 无局部极小值问题;(相对于神经网络等算法)

        • 无需依赖整个数据;

        • 泛化能力比较强;

      • 缺点

        • 当观测样本很多时,效率并不是很高;

        • 对非线性问题没有通用解决方案,有时候很难找到一个合适的核函数;

        • 对于核函数的高维映射解释力不强,尤其是径向基函数;

        • 常规SVM只支持二分类

        • 对缺失数据敏感;

  • 贝叶斯分类

    • 贝叶斯分类是一类分类算法的总称,这类算法均以贝叶斯定理为基础,故统称为贝叶斯分类。而朴素朴素贝叶斯分类是贝叶斯分类中最简单,也是常见的一种分类方法。

    • 贝叶斯分类器的分类原理是通过先验概率,利用贝叶斯公式计算出后验概率,选择最大后验概率所对应的分类结果。

    • 朴素贝叶斯算法是假设各个特征之间相互独立

    • 实例:

      • 问题描述:通过一些测量的特征,包括身高、体重、脚的尺寸,判定一个人是男性还是女性。

    • 朴素贝叶斯分类的优缺点

      • 优点:

        • 算法逻辑简单,易于实现

        • 分类过程中时空开销小

        • 对小规模的数据表现很好,能个处理多分类任务,适合增量式训练(即可以实时的对新增的样本进行训练);

        • 对缺失数据不太敏感,算法也比较简单,常用于文本分类;

        • 朴素贝叶斯对结果解释容易理解。

      • 缺点:

        • 理论上,朴素贝叶斯模型与其他分类方法相比具有最小的误差率。但是实际上并非总是如此,这是因为朴素贝叶斯模型假设属性之间相互独立,这个假设在实际应用中往往是不成立的,在属性个数比较多或者属性之间相关性较大时,分类效果不好。

    • 在sklearn中对应的方法是naive_bayes.GaussianNB、MultinomialNB、BernoulliNB(分别是高斯贝叶斯分类器、多项式贝叶斯分类器、伯努利贝叶斯分类器)

  • K近邻(简称KNN)

    • KNN是通过测量不同特征值之间的距离进行分类。它的思路是:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别,其中K通常是不大于20的整数。KNN算法中,所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

    • 在KNN中,通过计算对象间距离来作为各个对象之间的非相似性指标,避免了对象之间的匹配问题,在这里距离一般使用欧氏距离或曼哈顿距离

    • K近邻算法的这种分类特点称为消极学习方法,具有同样特点的学习算法还有局部加权回归,它的优点在于不是在整个实例空间上一次性的估计目标函数,而是针对每个待分类的新实例做出局部的和相异的估计。而与之对应的分类算法,我们称之为积极学习方法,例如:支持向量机、神经网络等等,它的特点是在新的查询实例到来之前,通过训练实例总结归纳出相似判断的目标函数。

    • K近邻同样可以应用于回归任务。K近邻做分类预测时,一般是选择多数表决法,即训练集里和预测的样本特征最近的K个样本,预测为里面有最多类别数的类别。而K近邻做回归时,一般是选择平均法,即最近的K个样本的样本输出的平均值作为回归预测值。

    • K近邻三要素

      • 距离度量

        • 回到刚才那个例子,我们假设从生活习惯、节日风俗、衣着服饰、宗教信仰等多个方面来考察部落之间的相似程度。所谓的相似程度用另外一种说法来表达即差异,差异越小,相似程度越大。在机器学习中,我们使用距离来度量差异。一般情况下我们采用欧式距离来度量差异(其他的距离度量方式如曼哈顿距离等同样适用)。

        • 我们将通过生活习惯、节日风俗、衣着服饰、宗教信仰等多个方面来考察部落之间的相似程度,但是现在我们需要考虑这样一种情况,我们观察发现这些部落虽然在有些方面存在很大的差异,但是这些差异却不能成为区分不同民族的依据,比如说,A和B两个部落都属于C民族,但是A部落信仰D教,B部落信仰E教。也就是说,应用k-近邻的一个实践问题是,实例间的距离是根据实例的所有属性计算的,但是这些属性当中存在着对分类无关的属性,这些无关的属性可能在实例空间中相距很远,这样一来近邻间的距离会被大量的不相关属性所支配。这种由于存在很多不相关属性所导致的难题,有时被称为维度灾难。解决该问题的一个方法是,当计算两个实例间的距离时对每个属性加权,从不断的测试中获得启发,给对分类影响大的属性赋予更高的权值。

      • K值选择

        • K值的选择会对K近邻法的结果产生巨大的影响。如果选择较小的K值,学习的近似误差会减小,只有与输入实例较近的训练实例才会对预测结果起作用,这样做存在的问题是预测结果对近邻点过于敏感,如果近邻点恰巧是噪声,预测结果就会出错。如果选择较大的K值,其优点是可以减少学习得估计误差,缺点是与输入实例较远的训练实例也会对预测起作用。K值选择的原则往往是经过大量独立测试数据、多个模型来验证最佳选择。

      • 分类决策规则

        • K近邻中的分类决策往往是多数表决,即由输入实例的K个近邻的训练实例中的多数类决定输入实例的类。这样的决策规则存在一个问题,假设我们现在已知A、B两个部落属于同一个民族,C、D、E三个部落属于同一个民族。为了测试我们的模型,我们将A部落作为实例,输入到模型中进行测试,K值设为4。经过计算我们发现,得到的K个近邻实例分别为B、C、D、E,并且A、B部落之间的特征距离很小,而A与C、D、E三个部落之间的特征距离很大。但是由于分类决策规则是依据多数进行表决的,所以我们最终会将A判断为与C、D、E部落相同的民族。由此可以看出,多数表决的决策规则是不合理的。解决这一问题的方法是对距离进行加权,B部落与A部落的差异比较小,所以在K个实例当中B部落应该对最终的决策产生更大的影响,而距离越远影响力越小。

      • 优点

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

        • 可用于非线性分类;

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

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

        • KNN是一种在线技术,新数据可以直接加入数据集而不必进行重新训练;

        • KNN理论简单,容易实现;

      • 缺点

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

        • 需要大量内存;

        • 对于样本容量大的数据集计算量比较大(体现在距离计算上);

        • 样本不平衡时,预测偏差比较大。如:某一类的样本比较少,而其它类样本比较多;

        • KNN每一次分类都会重新进行一次全局运算;

        • k值大小的选择没有理论选择最优,往往是结合K-折交叉验证得到最优k值选择;

  • 逻辑回归与SVM

    • 相同点:

      • 都是分类算法,本质上都是在找最佳分类超平面;

      • 都是监督学习算法;

      • 都是判别式模型,判别模型不关心数据是怎么生成的,它只关心数据之间的差别,然后用差别来简单对给定的一个数据进行分类;

      • 都可以增加不同的正则项。

    • 不同点:

      • LR 是一个统计的方法,SVM 是一个几何的方法

      • SVM 的处理方法是只考虑 Support Vectors,也就是和分类最相关的少数点去学习分类器。而逻辑回归通过非线性映射减小了离分类平面较远的点的权重,相对提升了与分类最相关的数据点的权重;

      • 损失函数不同:LR 的损失函数是交叉熵,SVM 的损失函数是 HingeLoss,这两个损失函数的目的都是增加对分类影响较大的数据点的权重,减少与分类关系较小的数据点的权重。对 HingeLoss 来说,其零区域对应的正是非支持向量的普通样本,从而所有的普通样本都不参与最终超平面的决定,这是支持向量机最大的优势所在,对训练样本数目的依赖大减少,而且提高了训练效率;

      • LR 是参数模型,SVM 是非参数模型,参数模型的前提是假设数据服从某一分布,该分布由一些参数确定(比如正太分布由均值和方差确定),在此基础上构建的模型称为参数模型;非参数模型对于总体的分布不做任何假设,只是知道总体是一个随机变量,其分布是存在的(分布中也可能存在参数),但是无法知道其分布的形式,更不知道分布的相关参数,只有在给定一些样本的条件下,能够依据非参数统计的方法进行推断。所以 LR 受数据分布影响,尤其是样本不均衡时影响很大,需要先做平衡,而 SVM 不直接依赖于分布;

      • LR 可以产生概率,SVM 不能;

      • LR 不依赖样本之间的距离,SVM 是基于距离的;

      • LR 相对来说模型更简单好理解,特别是大规模线性分类时并行计算比较方便。而 SVM 的理解和优化相对来说复杂一些,SVM 转化为对偶问题后,分类只需要计算与少数几个支持向量的距离,这个在进行复杂核函数计算时优势很明显,能够大大简化模型和计算。

  • 逻辑回归与朴素贝叶斯

    • 朴素贝叶斯和逻辑回归都属于分类模型,当朴素贝叶斯的条件概率服从高斯分布时,它计算出来的 P(Y=1|X) 形式跟逻辑回归是一样的。

    • 两个模型不同的地方在于:

      • 逻辑回归是判别式模型 p(y|x),朴素贝叶斯是生成式模型 p(x,y):判别式模型估计的是条件概率分布,给定观测变量 x 和目标变量 y 的条件模型,由数据直接学习决策函数 y=f(x) 或者条件概率分布 P(y|x) 作为预测的模型。判别方法关心的是对于给定的输入 x,应该预测什么样的输出 y;而生成式模型估计的是联合概率分布,基本思想是首先建立样本的联合概率概率密度模型 P(x,y),然后再得到后验概率 P(y|x),再利用它进行分类,生成式更关心的是对于给定输入 x 和输出 y 的生成关系;

      • 朴素贝叶斯的前提是条件独立,每个特征权重独立,所以如果数据不符合这个情况,朴素贝叶斯的分类表现就没逻辑会好了。

  • 数据处理量

    • 处理中、小量数据的模型

      • 比如SVM,基于贝叶斯的一些算法

    • 处理大量数据的模型

      • 简单的模型,比如逻辑回归

      • 可以并行训练的模型,比如神经网络,随机森林

此条目发表在未分类分类目录,贴了标签。将固定链接加入收藏夹。