监督学习最常见的五种算法,你知道几个?

在机器学习中,无监督学习(Unsupervised learning)就是聚类,事先不知道样本的类别,通过某种办法,把相似的样本放在一起归位一类;而监督型学习(Supervised learning)就是有训练样本,带有属性标签,也可以理解成样本有输入有输出。

所有的回归算法和分类算法都属于监督学习。回归(Regression)和分类(Classification)的算法区别在于输出变量的类型,定量输出称为回归,或者说是连续变量预测;定性输出称为分类,或者说是离散变量预测。

以下是一些常用的监督型学习方法。

K - 近邻算法(k-Nearest Neighbors,KNN)

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

如上图,绿色圆要被决定赋予哪个类,是红色三角形还是蓝色四方形?如果 K=3,由于红色三角形所占比例为 2/3,绿色圆将被赋予红色三角形那个类,如果 K=5,由于蓝色四方形比例为 3/5,因此绿色圆被赋予蓝色四方形类。

算法的步骤为:

(1)计算测试数据与各个训练数据之间的距离; (2)按照距离的递增关系进行排序; (3)选取距离最小的 K 个点; (4)确定前 K 个点所在类别的出现频率; (5)返回前 K 个点中出现频率最高的类别作为测试数据的预测分类。

决策树(Decision Trees)

决策树是一种常见的分类方法,其思想和 “人类逐步分析比较然后作出结论” 的过程十分相似。决策过程和下图类似。

决策树是一个树结构(可以是二叉树或非二叉树)。其每个非叶节点表示一个特征属性上的测试,每个分支代表这个特征属性在某个值域上的输出,而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始,测试待分类项中相应的特征属性,并按照其值选择输出分支,直到到达叶子节点,将叶子节点存放的类别作为决策结果。

不同于贝叶斯算法,决策树的构造过程不依赖领域知识,它使用属性选择度量来选择将元组最好地划分成不同的类的属性。所谓决策树的构造就是进行属性选择度量确定各个特征属性之间的拓扑结构。

那么如何划分数据呢?各个特征的优先级是怎么排的?常用的划分数据集方法有 ID3 和 C4.5

(1) ID3 算法

划分数据集的最大原则就是将数据变得更加有序。熵(entropy)是描述信息不确定性(杂乱程度)的一个值。设 S 是当前数据下的划分,那么 S 的信息熵的定义如下:

这里,n 是类别的数目,p(xi) 表示选择 xi 类别的概率(可用类别数量除以总数量估计)。

现在我们假设将 S 按属性 A 进行划分,则 S 的条件信息熵(A 对 S 划分的期望信息)为:

这里,在属性 A 的条件下,数据被划分成 m 个类别(例如,属性 A 是体重,有轻、中、重三个选项,那么 m=3),p(tj) 表示类别 tj(属性 A 中所有具有第 j 个特性的所有数据)的数量与 S 总数量的比值,H(tj) 表示子类别 tj 的熵。

信息增益(Information gain)是指在划分数据集之前之后信息发生的变化,其定义如下:

在 ID3 算法里,每一次迭代过程中会计算所有剩余属性的信息增益,然后选择具有最大增益的属性对数据集进行划分,如此迭代,直至结束。这里有一个 ID3 算法的实例过程(点击阅读原文,在原文中可点击超级链接)。

(2) C4.5 算法

D3 算法存在一个问题,就是偏向于多值属性,例如,如果存在唯一标识属性 ID,则 ID3 会选择它作为分裂属性,这样虽然使得划分充分纯净,但这种划分对分类几乎毫无用处。ID3 的后继算法 C4.5 使用增益率(gain ratio)的信息增益扩充,试图克服这个偏倚。严格上说 C4.5 是 ID3 的一个改进算法。

在按照 ID3 的中的方法得到了信息增益后,再定义分裂信息(Split Information):

然后定义增益率(Gain Ratio):

C4.5 选择增益率为分裂属性(连续属性要用增益率离散化)。C4.5 算法有如下优点:产生的分类规则易于理解,准确率较高。其缺点是:在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。此外,C4.5 只适合于能够驻留于内存的数据集,当训练集大得无法在内存容纳时程序无法运行。

如果所有属性都作为分裂属性用光了,但有的子集还不是纯净集,即集合内的元素不属于同一类别。在这种情况下,由于没有更多信息可以使用了,一般对这些子集进行 “多数表决”,即使用此子集中出现次数最多的类别作为此节点类别,然后将此节点作为叶子节点。

在实际构造决策树时,通常要进行剪枝,这时为了处理由于数据中的噪声和离群点导致的过分拟合问题。剪枝有两种:先剪枝——在构造过程中,当某个节点满足剪枝条件,则直接停止此分支的构造;后剪枝——先构造完成完整的决策树,再通过某些条件遍历树进行剪枝。悲观错误剪枝 PEP 算法是一种常见的事后剪枝策略。

朴素贝叶斯(Naive Bayesian)

贝叶斯分类是一系列分类算法的总称,这类算法均以贝叶斯定理为基础,故统称为贝叶斯分类。朴素贝叶斯算法(Naive Bayesian) 是其中应用最为广泛的分类算法之一。朴素贝叶斯分类器基于一个简单的假定:给定目标值时属性之间相互条件独立。朴素贝叶斯的基本思想是对于给出的待分类项,求解在此项出现的条件下各个类别出现的概率,哪个最大,就认为此待分类项属于哪个类别。

首先给出条件概率的定义,P(A∥B) 表示事件 A 在 B 发生下的条件概率,其公式为:

贝叶斯定理用来描述两个条件概率之间的关系,贝叶斯定理公式为:

朴素贝叶斯分类算法的具体步骤如下:

(1)设 x={a1,a2,...,am} 为一个待分类项,a1,a2,...,am 为 x 的 m 个特征属性;

(2)设有类别集合 C={y1,y2,...,yn},即共有 n 个类别;

(3)依次计算 x 属于各项分类的条件概率,即计算 P(y1∥x),P(y2∥x),… ,P(yn∥x):

注意,算法的下一步骤是对比这些结果的大小,由于各项分母都是 P(x),所以分母不用计算。分子部分中 P(yn) 和 P(ai∥yn) 都是通过样本集统计而得,其中 P(yn) 的值为样本集中属于 yn 类的数量与样本总数量之比,P(ai∥yn) 的值为 yn 类中满足属性 ai 的数量与 yn 类下样本总数量之比。

这样的计算方式符合特征属性是离散值的情况,如果特征属性是连续值时,通常假定其值服从高斯分布(也称正态分布),即:

那么 P(ai∥yn) 的值为:

其中,ηyn 和σyn 分别为训练样本 yn 类别中 ai 特征项划分的均值和标准差。

对于 P(a∥y)=0 的情况,当某个类别下某个特征项划分没有出现时,就是产生这种现象,这会令分类器质量大大降低。因此引入 Laplace 校准,对没类别下所有划分的计数加 1,这样如果训练样本集数量充分大时,并不会对结果产生影响,也避免了乘积为 0 的情况。

(4)比较(3)中所有条件概率的大小,最大的即为预测分类结果,即:

逻辑回归(Logistic Regression)

我们知道,线性回归就是根据已知数据集求一线性函数,使其尽可能拟合数据,让损失函数最小,常用的线性回归最优法有最小二乘法和梯度下降法。而逻辑回归是一种非线性回归模型,相比于线性回归,它多了一个 sigmoid 函数(或称为 Logistic 函数)。逻辑回归是一种分类算法,主要用于二分类问题。逻辑回归的具体步骤如下:

(1)定义假设函数 h(即 hypothesis)

Sigmoid 函数的图像是一个 S 型,预测函数就是将 sigmoid 函数 g(x) 里的自变量 x 替换成了边界函数θ(x),如下:

这里 hθ(x) 表示结果取 1 的概率,因此对于输入 x 分类结果为类别 1 和类别 0 的概率分别为:

(2) 定义边界函数θ(x)

对于二维数据,如果是预设线性线性边界,那么边界函数为:

如果是预设非线性线性边界,那么边界函数为的形式就多了,例如:

假设我们现在要解决的是识别图片中的 0 或 1(样本库只有 0 和 1 的图片),图片大小是 20*20,那么这个时候有 400 个特征向量,那么边界函数为:

(3) 构造损失函数(cost function,loss function)

损失函数的大小可以体现出边界函数的各项参数是否最优。对于线性回归,损失函数是欧式距离指标,但这样的 Cost Function 对于逻辑回归是不可行的,因为在逻辑回归中平方差损失函数是非凸,我们需要其他形式的 Cost Function 来保证逻辑回归的成本函数是凸函数。

我们选择对数似然损失函数:

那么逻辑回归的 Cost Function 可以表示为:

这里 m 表示有 m 个样本,y 是二值型数据,只能 0 或 1,代表两种不同的类别。

(4) 求最优θ

要想找到最合适的边界函数参数,只要使 J(θ) 最小即可。最优化的表达式为:

与线性回归相似,可以采用梯度下降法寻优,也可以采用其他方法,具体见下面列出的第 5 个参考网址。

参考资料:

机器学习(一)K - 近邻(KNN)算法 地址:http://t.cn/RLj0XIZ

算法杂货铺——分类算法之决策树 (Decision tree) 地址:http://t.cn/zjqquUf

决策树算法总结 地址:http://t.cn/zjCCJpC

算法杂货铺——分类算法之朴素贝叶斯分类 (Naive Bayesian classification) 地址:http://t.cn/hqMdur

Coursera 公开课笔记: 斯坦福大学机器学习第六课 “逻辑回归 (Logistic Regression)” 地址:http://t.cn/zOuCqYb

原文发布于微信公众号 - AI研习社(okweiwu)

原文发表时间:2017-04-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python中文社区

机器学习算法实践:树回归

專 欄 ❈PytLab,Python 中文社区专栏作者。主要从事科学计算与高性能计算领域的应用,主要语言为Python,C,C++。熟悉数值算法(最优化方法,...

45990
来自专栏算法channel

深度学习|反向传播算法(BP)原理推导及代码实现

《实例》阐述算法,通俗易懂,助您对算法的理解达到一个新高度。包含但不限于:经典算法,机器学习,深度学习,LeetCode 题解,Kaggle 实战。期待您的到来...

727100
来自专栏计算机视觉战队

卷积神经网络就是这么简单就能学会

卷积神经网络和前几次介绍的神经网络非常相似:它们都是由神经元组成,神经元中有具有学习能力的权重和偏差。每个神经元都得到一些输入数据,进行内积运算后再进行激活函数...

14520
来自专栏智能算法

从感知机到神经网络简略

最热门的深度学习,想必很多人都想了解学习,网络上也有不少资料;小编也希望可以从头开始,更为透彻地去理解原理机制,这样在日后可以在深度学习框架实战的学习上更为轻松...

37760
来自专栏新智元

【值得收藏的深度学习思维导图】全面梳理基本概念与11大模型关系

【新智元导读】 作者dformoso在Github上放出了自己绘制的深度学习思维导图,共有三张:基本概念、架构和TensorFlow。以图示的方法介绍深度学习必...

34030
来自专栏机器学习算法与Python学习

机器学习(6) -- SVM

本篇主要是对支持向量机(support vector machine , SVM) 总结性的文章,想详细的理解SVM的请看之前所发的支持向量机系列文章。 Co...

37750
来自专栏梦里茶室

读论文系列:Object Detection ECCV2016 SSD

转载请注明作者:梦里茶 Single Shot MultiBox Detector Introduction 一句话概括:SSD就是关于类别的多尺度RPN...

33060
来自专栏老秦求学

【手把手系列之一】手写实现单层神经网络

训练集: \(X = [x^{(1)},x^{(2)},...,x^{(i)},....,x^{(m)}]\) ;对应标签:\(Y=[y^{(1)},y^{(2...

15520
来自专栏AI研习社

手把手教你如何用 TensorFlow 实现 CNN

CNN 的引入 在人工的全连接神经网络中,每相邻两层之间的每个神经元之间都是有边相连的。当输入层的特征维度变得很高时,这时全连接网络需要训练的参数就会增大很...

782120
来自专栏深度学习与计算机视觉

从AlexNet理解卷积神经网络的一般结构

2012年AlexNet在ImageNet大赛上一举夺魁,开启了深度学习的时代,虽然后来大量比AlexNet更快速更准确的卷积神经网络结构相继出现,但是Alex...

41660

扫码关注云+社区

领取腾讯云代金券