机器学习算法

机器学习算法

算法基本上从功能或者形式上来分类。比如,基于树的算法,神经网络算法。这是一个很有用的分类方式,但并不完美。因为有许多算法可以轻易地被分到两类中去,比如说 Learning Vector Quantization 就同时是神经网络类的算法和基于实例的方法。正如机器学习算法本身没有完美的模型一样,算法的分类方法也没有完美的。

变量关系

学习风格

算法相似度

常用算法

本小节我们对机器学习中常见的算法及其特征与使用场景进行简单梳理。

贝叶斯算法

贝叶斯算法是给予贝叶斯定理与特征条件独立假设的监督型分类方法,典型的算法有朴素贝叶斯、高斯朴素贝叶斯、多种名义朴素贝叶斯、平均单依赖估计、BBN、BN 等。该算法要求各特征间相互独立,对于给出的待分类项,求解在此项出现的条件下各个类别出现的概率,哪个最大,就认为此待分类项属于哪个类别。其典型的运用场景包括了:

  • 文本分类

  • 疾病预测

  • 检测 SNS 社区中不真实账号

  • 垃圾邮件过滤

线性回归与逻辑回归

线性回归的目的在于找出某一变量与其他多个变量之间的定量关系,并且是线性关系;逻辑回归则是将数据拟合到一个 logit 函数(或者叫做 logistic 函数)中,从而能够完成对事件发生的概率进行预测。线性回归模型太简单,如果数据呈线性关系可采用;逻辑回归相对来说模型更简单,好理解,实现起来,特别是大规模线性分类时比较方便。同样的线性分类情况下,如果异常点较多的话,无法剔除,首先 LR,LR 中每个样本都是有贡献的,最大似然后会自动压制异常的贡献。

决策树

决策树是利用训练数据集来构造决策树,用构造好的决策树对将来的新数据进行分类的监督型算法,典型的算法有 ID3、ID4、ID5、C4.0、C4.5、C5.0、CART 等,其常用于二元或者多元分类。该算法要求变量只能数值型、名称型,其核心概念中涉及信息熵、信息增益,在构造决策树时,实际上是选择信息增益 Max 的属性作为决策节点;算法 C4.5 引入来信息增益率的概念。决策树常用于以下场景:

  • 金融行业用决策树做贷款风险评估

  • 保险行业用决策树做推广预测

  • 医疗行业用决策树生成辅助诊断处置模型

  • 用户分级评估

  • 分析对某种响应可能性影响最大的因素,比如判断具有什么特征的客户流失概率更高

  • 为其他模型筛选变量。决策数找到的变量是对目标变量影响很大的变量。所以可以作为筛选变量的手段。

SVM 支持向量机

SVM 同样是监督型分类算法,基本想法就是求解能正确划分训练样本并且其几何间隔最大化的超平面。线性支持向量机既可以解决线性可分问题,又可以解决线性不可分问题。其构建过程如下:获取训练输入,将其映射至多维空间,使用回归算法找到可最佳分离两类输入数据的超平面(超平面是一个在 n 维空间中将空间划分为两个半空间的一个平面)。一旦支持向量机完成了受训,它就可以评估有关划分超平面的新输入数据,并将划分为其中一类,在 SVM 分类决策中起决定作用的是支持向量。

SVM 常用于模式识别领域中的文本识别,中文分类,人脸识别等;工程技术和信息过滤。

KNN(K 近邻算法)

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

KNN 要求事先要有正确样本,算法比较简单,完全依赖于数据,没有数学模型,所以应用在很简单的模型。其易于理解,易于实现,无需估计参数,无需训练;适合对稀有事件进行分类,特别适合于多分类问题(multi-modal,对象具有多个类别标签), KNN 比 SVM 的表现要好。不过当样本不平衡时,抗造能力差,并且计算量大。

KNN 的典型应用场景譬如约会网站的数据分类,或者手写数字识别。

聚类算法

聚类将数据集中的样本划分为若干个不相交的子集,每个子集可能对应一个潜在的类别,这些类别对聚类算法是未知的。其典型算法有 K-means,LVQ,高斯混合聚类,密度聚类,层次聚类等。聚类算法不需要训练集。

随机森林

随机森林是监督型分类算法,顾名思义,是用随机的方式建立一个森林,森林里面有很多的决策树组成,随机森林的每一棵决策树之间是没有关联的。在得到森林之后,当有一个新的输入样本进入的时候,就让森林中的每一棵决策树分别进行一下判断,看看这个样本应该属于哪一类(对于分类算法),然后看看哪一类被选择最多,就预测这个样本为那一类。

随机森林主要包含了采样(有放回的采样)与完全分裂(叶子节点要么无法再分裂,要么要么里面的所有样本的都是指向的同一个分类)等步骤。随机森林对多元公线性不敏感,结果对缺失数据和非平衡的数据比较稳健,可以很好地预测多达几千个解释变量的作用;在数据集上表现良好,两个随机性的引入,使得随机森林不容易陷入过拟合。

在当前的很多数据集上,相对其他算法有着很大的优势,两个随机性的引入,使得随机森林具有很好的抗噪声能力。它能够处理很高维度(feature 很多)的数据,并且不用做特征选择,对数据集的适应能力强:既能处理离散型数据,也能处理连续型数据,数据集无需规范化。可生成一个 Proximities=(pij)矩阵,用于度量样本之间的相似性: pij=aij/N, aij 表示样本 i 和 j 出现在随机森林中同一个叶子结点的次数,N 随机森林中树的颗数。

在创建随机森林的时候,对 generlization error 使用的是无偏估计,训练速度快,可以得到变量重要性排序(两种:基于 OOB 误分率的增加量和基于分裂时的 GINI 下降量,在训练过程中,能够检测到 feature 间的互相影响,容易做成并行化方法,实现比较简单。

Adaboost

Adaboost 是监督型聚合式分类算法,和随机森林有点像,区别在于随机森林是并行,Adaboost 是串行,上一个分类器的结果放入下一个分类器。Adaboost 最后的分类器 YM 是由数个弱分类器(weak classifier)组合而成的,相当于最后 m 个弱分类器来投票决定分类,而且每个弱分类器的话语权 α 不一样。

Adaboost 常用于二分类或多分类的应用场景,用于做分类任务的 baseline 无脑化,简单,不会 overfitting,不用调分类器。还可以用于特征选择(feature selection)。并且 Boosting 框架用于对 badcase 的修正,只需要增加新的分类器,不需要变动原有分类器。

神经网络

人工神经网络算法模拟生物神经网络,是一类模式匹配算法。一般分为输入层、隐藏层、输出层,隐藏层的层数根据算法需要来定,层数越多,模型越复杂,计算能力要求越高。对于输入层和隐藏层,每一个神经元代表输入,经过一系列计算得到输出,将输出作为下一层神经元的输入,以此类推,直到传递到输出层。

神经网络可以充分逼近任意复杂的非线性关系;所有定量或定性的信息都等势分布贮存于网络内的各神经元,故有很强的鲁棒性和容错性;采用并行分布处理方法,使得快速进行大量运算成为可能;可学习和自适应不知道或不确定的系统。