[译]机器学习:有监督算法之分类

说明:机器学习横跨计算机科学、工程技术和统计学等多个科学。人们很难直接从原始数据本身获得所需信息,机器学习可以把无序的数据转换成有用的信息;移动计算和传感器产生的海量数据意味着未来将面临越来越多的数据,如何从中抽取到有价值的信息很重要,机器学习可以帮助我们从中抽取有用的信息。本文主要根据《机器学习实战》和网上搜集的一些有关机器学习的总结经验贴,具体的链接忘记了,因此这里将文件类型设置为翻译,还望见谅。

编辑: a_siasin

日期:2016年7月29日

一、机器学习的主要任务

如何解决分类问题和回归是机器学习其中两个主要任务,分类就是将实例数据划分到合适的分类中,回归主要用于预测数值型数据。分类和回归属于监督学习[x1] ,这类算法必须知道预测什么,即目标变量的分类信息。与其对应的无监督学习,这类算法的数据没有类别信息,也没有给定目标值。在无监督学习中,将数据集分成有类似的对象组成的多个类的过程被称为聚类;将寻找描述数据统计值的过程称之为密度估计;此外无监督学习还可以用于降维。

表1 用于执行分类、回归、聚类和密度估计的机器学习算法

二、如何选择合适的算法

在选择算法的时候,应考虑以下两个问题:
①使用机器学习算法的目的,想要算法完成何种任务;
②另一个就是需要分析和收集的数据是什么。

1、考虑使用机器学习算法的目的

(1)确定算法类型:如果想要预测目标变量的值,则可以选择监督学习算法,否则可以选择无监督学习算法。

(2)如果选择确定为监督学习算法,要进一步确定目标变量的类型,如,是离散型的数值还是连续性的数值,如果是离散型数值,则选择分类算法;如果是连续性数值,则选择回归算法。

(3)如果选择确定为无监督学习算法,要进步将数据划分为离散的组,使用聚类算法,如果还需要估计数据与每个分组的相似程度,则需要使用密度估计算法。

2、考虑数据的问题

需要充分了解数据,对数据了解的越充分,越容易创建符合实际需求的应用程序。

主要了解数据的以下特征:
(1)特征值是离散变量还是连续变量
(2)特征值中是否存在缺失值,何种原因造成的缺失值
(3)数据中是否存在异常值
(4)某个特征发生的频率如何

充分了解数据特征性可以缩短选择机器学习算法的时间,但是我们也只是在一定程度上缩小算法的选择范围,一般并不存在最好的算法,但是可以给出最好结果的算法,所以一般还要尝试不同算法的执行结果。对于所选择的每种算法,都可以使用其他的机器学习技术来改进其性能。在处理输入数据之后,两个算法的相对性能也可能会发生变化。

三、机器学习应用程序的步骤

学习和使用机器学习算法开发应用程序,通常遵循以下的步骤:

(1)数据的收集。常用的方法有:制作网络爬虫从网站上抽取数据、从RSS反馈或者API中得到信息、设备发送过来的实测数据(风速、血糖等)。为了节省时间和精力,可以使用公开的数据源。

(2)准备输入数据。得到数据后,还必须为机器学习算法准备特定的数据格式,如某些算法要求特征值使用特定的格式,一些算法要求目标变量和特征值是字符串类型,另一些算法则可能要求是整数类型。

(3)分析输入数据。该步骤主要是人工分析之前得到的数据,最简单的方法是用文本编辑器打开数据文件,查看得到的数据是否为空值、分析是否可以识别出模式、数据中是否存在明显的异常值,如某些数据点与数据集中的其他值存在明显的差异。

此步骤需要人工干预,如果在自动化系统中还需要人工干预,显然就降低了系统的价值。这一步的主要作用是确保数据集中没有垃圾数据。如果是在产品化系统中使用机器学习算法并且算法可以处理系统产生的数据格式,或者我们信任数据来源,这一步骤可以省略。

(4)根据算法的不同,第4步和第5步是机器学习算法的核心。我们将前两步得到的格式化数据输入到算法,从中抽取知识或信息。这里得到的知识需要存储为计算机可以处理的格式,方便后续步骤使用。如果使用的是无监督学习算法,不需要训练算法,所有的算法相关内容集中在第5步。

(5)为了评估算法,必须测试算法工作的效果。对于监督学习,必须已知用于评估算法的目标变量值;对于无监督学习,也必须用其他的评测手段来检验算法的成功率。无论哪种情形,如果不满意算法的输出结果,则可以回到第4步,改正并加以测试。问题常常会跟数据的收集和准备有关,这时你就必须跳回第1步重新开始。

(6) 使用算法。将机器学习算法转换为应用程序,执行实际任务,以检验上述步骤是否可以在实际环境中正常工作。此时如果碰到新的数据问题,同样需要重复执行上述的步骤。

四、机器学习的算法

1、k-近邻算法

(1)k-邻近算法的概述

k-近邻算法采用测量不同特征值之间的距离方法进行分类。该方法的思路是:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的实例中的大多数属于某一个类别,则该样本也属于这个类别。所谓k-近邻算法,即是给定一个训练数据集,对新的输入样本,在训练数据集中找到与该实例最邻近的k个实例, 这k个实例的多数属于某个类,就把该输入样本分类到这个类中。选择不同的k,得到的分类结果可能会有不同,当无法判定当前待分类点是从属于已知分类中的哪一类时,我们可以依据统计学的理论看它所处的位置特征,衡量它周围邻居的权重,把它归为到权重更大的那一类。这是k-近邻算法的核心思想。

KNN(k-NearestNeighbour)方法虽然从原理上也依赖于极限定理,但在类别决策时,只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合。

k-近邻算法使用的模型实际上对应于对特征空间的划分。k值的选择,距离度量和分类决策规则是该算法的三个基本要素:
① k值的选择会对算法的结果产生重大影响。k值较小意味着只有与输入样本较近的训练实例才会对预测结果起作用,但容易发生过拟合;如果k值较大,优点是可以减少学习的估计误差,但缺点是学习的近似误差增大,这时与输入样本较远的训练实例也会对预测起作用,是预测发生错误。在实际应用中,k值一般选择一个较小的数值,通常采用交叉验证的方法来选择最优的k值。随着训练实例数目趋向于无穷和k=1时,误差率不会超过贝叶斯误差率的2倍,如果k也趋向于无穷,则误差率趋向于贝叶斯误差率;
② 该算法中的分类决策规则往往是多数表决,即由输入样本的k个最临近的训练实例中的多数类决定输入样本的类别;
③ 距离度量一般采用LP距离[x2] ,当p=2时,即为欧氏距离,在度量之前,应该将每个属性的值规范化,这样有助于防止具有较大初始值域的属性比具有较小初始值域的属性的权重过大。

(2)k-近邻算法的用途和优缺点

KNN算法不仅可以用于分类,还可以用于回归。通过找出一个样本的k个最近邻居,将这些邻居的属性的平均值赋给该样本,就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权重(weight),如权重与距离成反比。实现k-近邻算法时,主要考虑的问题是如何对训练数据进行快速k-近邻搜索,这在特征空间维数大及训练数据容量大时非常必要。

① 优点:精度高、对异常值不敏感、无数据输入假定。
② 缺点以及部分解决方案:计算复杂度高、空间复杂度高。当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的k个邻居中大容量类的样本占多数,常用的解决方法是利用距离给每个已知的样本赋予权重;因为对每一个待分类的文本都要计算它到全体已知样本的距离,才能求得它的k个最近邻点,所以计算量较大。目前常用的解决方法是事先对已知样本点进行剪辑,事先去除对分类作用不大的样本;该算法比较适用于样本容量比较大的类域的自动分类,而那些样本容量较小的类域采用这种算法比较容易产生误分。
③ 适用数据范围:数值型和标称型。
注意:KNN算法中,所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

(3)k-近邻算法的一般流程

① 收集数据:可以使用任何方法。
② 准备数据:距离计算所需要的数值,最好是结构化的数据格式。
③ 分析数据:可以使用任何方法。
④ 测试算法:计算错误率。
⑤ 使用算法:首先需要输入样本数据和结构化的输出结果,然后运行k-近邻算法判定输入数据分别属于哪个分类,最后应用对计算出的分类执行后续的处理。

(4)k-近邻算法的实现

对未知类别属性的数据集中的每个点依次执行以下操作:
①计算已知类别数据集中的点与当前点之间的距离(k-近邻算法常用欧氏距离和马氏距离);
②按照距离递增次序排序;
③选取与当前点距离最小的k个点;
④确定前k个点所在类别的出现频率;
⑤返回前k个点出现频率最高的类别作为当前点的预测分类。

2、决策树

(1)决策树算法的概述

决策树(Decision Tree)是在已知各种情况发生概率的基础上,通过构成决策树来求取净现值的期望值大于等于零的概率,评价项目风险,判断其可行性的决策分析方法,是直观运用概率分析的一种图解法。在机器学习中,决策树是一个预测模型,他代表的是对象属性与对象值之间的一种映射关系。Entropy=系统的凌乱程度。决策树是一种树形结构,其中每个内部节点表示一个属性上的测试,每个分支代表一个测试输出,每个叶节点代表一种类别。

一个决策树包含三种类型的节点:
①决策点(□),是对几种可能方案的选择,即最后选择的最佳方案。如果决策属于多级决策,则决策树的中间可以有多个决策点,以决策树根部的决策点为最终决策方案,通常用矩形来表示。
②状态节点(○),代表备选方案的经济效果(期望值),通过各状态节点的经济效果的对比,按照一定的决策标准就可以选出最佳方案。由状态节点引出的分支称为概率枝,概率枝的数目表示可能出现的自然状态数目每个分枝上要注明该状态出现的概率,通常用圆圈来表示。
③结果节点(△),将每个方案在各种自然状态下取得的损益值标注于结果节点的右端,通常用三角形来表示。

(2)决策树优缺点

① 优点:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据。
② 缺点以及部分解决方案:对连续性的字段比较难预测;对有时间顺序的数据,需要很多预处理的工作;当类别太多时,错误可能就会增加的比较快;可能会产生过度匹配问题。
③ 适用数据类型:数值型和标称型。

(3)决策树的一般流程

①收集数据:可以使用任何方法。
②准备数据:树构造算法只适用于标称型数据,因此数值型数据必须离散化。
③分析数据:可以使用任何方法,构造树完成之后,我们应该检查图形是否符合预期。
④训练算法:构造树的数据结构。
⑤测试算法:使用经验树计算错误率。
⑥使用算法:使用决策树可以更好地理解数据的内在含义。

3、朴素贝叶斯

(1)朴素贝叶斯算法概述

贝叶斯分类是一系列分类算法的总称,这类算法均以贝叶斯定理为基础,故统称为贝叶斯分类。朴素贝叶斯分类器基于一个简单的假定:给定目标值时属性之间相互条件独立。独立性假设是指一个词的出现概率并不依赖于文档中的其他词。当然我们也知道这个假设过于简单。这就是之所以称为朴素贝叶斯的原因。尽管条件独立性假设并不正确,但是朴素贝叶斯仍然是一种有效的分类器。

(2)朴素贝叶斯优缺点

① 优点:在数据较少的情况下仍然有效,可以处理多类别问题;使用概率有时要比使用硬规则更为有效;贝叶斯概率及贝叶斯准则提供了一种利用已知值来估计未知概率的有效方法;可以通过特征之间的条件独立性假设,降低对数据量的需求。
② 缺点以及部分解决方案:对于输入数据的准备方式较为敏感。
③ 适用数据类型:标称型数据。

(3)朴素贝叶斯的一般流程

①收集数据:可以使用任何方法。
②准备数据:需要数值型或者布尔型数据。
③分析数据:有大量特征时,绘制特征作用不大,此时使用直方图效果更好。
④训练算法:计算不同的独立特征的条件概率。
⑤测试算法:计算错误率。
⑥使用算法:一个常见的朴素贝叶斯应用是文档分类。可以在任意的分类场景中使用朴素贝叶斯分类器,不一定非要是文本。

4、Logistic 回归

(1)Logistic 回归的概述

Logistic回归又称Logistic回归分析,是一种广义的线性回归分析模型,常用于数据挖掘,疾病自动诊断,经济预测等领域。发生概率除以没有发生概率再取对数。就是这个不太繁琐的变换改变了取值区间的矛盾和因变量自变量间的曲线关系。究其原因,是发生和未发生的概率成为了比值,这个比值就是一个缓冲,将取值范围扩大,再进行对数变换,整个因变量改变。不仅如此,这种变换往往使得因变量和自变量之间呈线性关系,这是根据大量实践而总结。所以,Logistic回归从根本上解决因变量要不是连续变量怎么办的问题。还有,Logistic应用广泛的原因是许多现实问题跟它的模型吻合。

(2)Logistic 回归的优缺点

① 优点:计算代价不高,易于理解和实现。
② 缺点:容易欠拟合,分类精度不高。
③ 适用数据类型:数值型和标称型数据;因变量为二分类的分类变量或某事件的发生率,并且是数值型变量;重复计数现象指标不适用;残差和因变量都要服从二项分布。

(3)Logistic 回归的一般流程

①收集数据:采用任意方法收集数据。
②准备数据:由于需要进行距离计算,因此要求数据类型为数值型。
③分析数据:采用任意方法对数据进行分析。
④训练算法:大部分时间将用于训练,训练的目的是为了找到最佳的分类回归系数。
⑤测试算法:一旦训练步骤完成,分类将会很快。
⑥使用算法:首先需要输入一些数据,并将其转换成对应的结构化数值;接着,基于训练好的回归系数可以对这些数值进行简单的回归计算,判定它们属于哪个类别,最后,我们就可以在输出的类别上做一些其他分析工作。

5、支持向量机(SVM)

(1)SVM的概述

支持向量机可以分析数据,识别模式,用于分类和回归分析。给定一组训练样本,每个标记为属于两类,一个SVM训练算法建立了一个模型,分配新的实例为一类或其他类,使其成为非概率二元线性分类。

(2)SVM优缺点

① 优点:泛化错误率低,计算开销不大,结果易解释。
② 缺点:对参数调节和核函数的选择敏感,原始分类器不加修改仅适用于处理二类问题。
③ 适用数据类型:数值型和标称型数据。

(3)SVM的一般流程

① 收集数据:可以使用任意方法。
② 准备数据:需要数值型数据。
③ 分析数据:有助于可视化分隔超平面。
④ 训练算法:SVM的大部分时间都源自训练,该过程主要实现两个参数的调优。
⑤ 测试算法:十分简单的计算过程就可以实现。
⑥ 使用算法:几乎所有分类问题都可以使用SVM,SVM本身是一个二类分类器。

6、AdaBoost元算法

(1)AdaBoost算法的概述

自举汇聚法(bootstrap aggregating),也称为bagging方法,是在从原始数据集选择n次后得到n个新数据集的一种技术。新数据集和原数据集的大小相等。每个数据集都是通过在原始数据集中随机选择一个样本来进行替换而得到的。这里的替换就意味着可以多次地选择同一样本。这一性质就允许新数据集中可以有重复的值,而原始数据集的某些值在新集合中则不再出现。在n个数据集建好之后,将某个学习算法分别作用于每个数据集就得到了n个分类器。当我们要对新数据进行分类时,就可以应用这n个分类器进行分类。与此同时,选择分类器投票结果中最多的类别作为最后的分类结果。

boosting是一种与bagging很类似的技术。不论是在boosting还是bagging当中,所使用的多个分类器的类型都是一致的。但是在前者当中,不同的分类器是通过串行训练而获得的,每个新分类器都根据已训练出的分类器的性能来进行训练。boosting是通过集中关注被已有分类器错分的那些数据来获得新的分类器。

由于boosting分类的结果是基于所有分类器的加权求和结果的,因此boosting和bagging不太一样。bagging中的分类器权重是相等的,而boosting中的分类器权重并不相等,每个权重代表的是其对应分类器在上一轮迭代中的成功度。

boosting方法拥有多个版本,其中一个最流行的版本就是AdaBoost 。

(2)AdaBoost算法的优缺点

① 优点:泛化错误率低,易编码,可以应用在大部分分类器上,无参数调整。
② 缺点:对离群点敏感。
③ 适用数据类型:数值型和标称型数据。

(3)AdaBoost算法的一般流程

①收集数据:可以使用任意方法。
②准备数据:依赖于所使用的弱分类器类型,如果是单层决策树,可以处理任何数据类型。
③分析数据:可以使用任意方法。
④训练算法:AdaBoost的大部分时间都用在训絲上,分类器将多次在同一数据集上训练弱分类器。
⑤测试算法:计算分类的错误率。
⑥使用算法:同SVM一样,AdaBoost预测两个类别中的一个。如果想把它应用到多个类别的场合,那么就要像多类SVM中的做法一样对AdaBoost进行修改。

五、其它资料对机器学习的解释

1、机器学习的概念

如果我的数据越多,我的模型就越能够考虑到越多的情况,由此对于新情况的预测效果可能就越好。这是机器学习界“数据为王”思想的一个体现。一般来说(不是绝对),数据越多,最后机器学习生成的模型预测的效果越好。

图1 机器学习与人类思考的类比

人类在成长、生活过程中积累了很多的历史与经验。人类定期地对这些经验进行“归纳”,获得了生活的“规律”。当人类遇到未知的问题或者需要对未来进行“推测”的时候,人类使用这些“规律”,对未知问题与未来进行“推测”,从而指导自己的生活和工作。

机器学习中的“训练”与“预测”过程可以对应到人类的“归纳”和“推测”过程。通过这样的对应,我们可以发现,机器学习的思想并不复杂,仅仅是对人类在生活中学习成长的一个模拟。由于机器学习不是基于编程形成的结果,因此它的处理过程不是因果的逻辑,而是通过归纳思想得出的相关性结论。

这也可以联想到人类为什么要学习历史,历史实际上是人类过往经验的总结。有句话说得很好,“历史往往不一样,但历史总是惊人的相似”。通过学习历史,我们从历史中归纳出人生与国家的规律,从而指导我们的下一步工作,这是具有莫大价值的。

2、机器学习的范围

机器学习跟模式识别,统计学习,数据挖掘,计算机视觉,语音识别,自然语言处理等领域有着很深的联系。从范围上来说,机器学习跟模式识别,统计学习,数据挖掘是类似的,同时,机器学习与其他领域的处理技术的结合,形成了计算机视觉、语音识别、自然语言处理等交叉学科。

图2 机器学习与相关学科

(1)模式识别

模式识别=机器学习(分类)。两者的主要区别在于前者是从工业界发展起来的概念,后者则主要源自计算机学科。在著名的《Pattern Recognition And Machine Learning》这本书(已下载)中,Christopher M. Bishop在开头是这样说的“Pattern recognition has itsorigins in engineering, whereas machine learning grew out of computer science.However, these activities can be viewed as two facets of the same field, andtogether they have undergone substantial development over the past ten years.”。

(2)数据挖掘

数据挖掘=机器学习+数据库。数据挖掘仅仅是一种思考方式,告诉我们应该尝试从数据中挖掘出知识,但不是每个数据都能挖掘出金子的。一个系统绝对不会因为上了一个数据挖掘模块就变得无所不能(这是IBM最喜欢吹嘘的),恰恰相反,一个拥有数据挖掘思维的人员才是关键,而且他还必须对数据有深刻的认识,这样才可能从数据中导出模式指引业务的改善。大部分数据挖掘中的算法是机器学习的算法在数据库中的优化。

(3)统计学习

统计学习≈机器学习。统计学习是个与机器学习高度重叠的学科。在某种程度上两者是有分别的,主要在于:统计学习者重点关注的是统计模型的发展与优化,偏数学,而机器学习者更关注的是能够解决问题,偏实践,因此机器学习研究者会重点研究学习算法在计算机上执行的效率与准确性的提升。

(4)计算机视觉

计算机视觉=图像处理+机器学习。图像处理技术用于将图像处理为适合进入机器学习模型中的输入,机器学习则负责从图像中识别出相关的模式。计算机视觉相关的应用非常的多,例如百度识图、手写字符识别、车牌识别等等应用。随着机器学习的新领域深度学习的发展,大大促进了计算机图像识别的效果,因此未来计算机视觉界的发展前景不可估量。

(5)语音识别

语音识别=语音处理+机器学习。语音识别就是音频处理技术与机器学习的结合。语音识别技术一般不会单独使用,一般会结合自然语言处理的相关技术。目前的相关应用有苹果的语音助手Siri等。

(6)自然语言处理[x3]

自然语言处理=文本处理+机器学习。自然语言处理技术主要是让机器理解人类的语言的一门领域。在自然语言处理技术中,大量使用了编译原理相关的技术,例如词法分析,语法分析等等,除此之外,在理解这个层面,则使用了语义理解,机器学习等技术。作为唯一由人类自身创造的符号,自然语言处理一直是机器学习界不断研究的方向。

六、待解决问题

1、以上算法的延伸优化算法,还有很多,有待进一步探讨研究。
2、以上算法的总结,仅仅局限于有监督学习中的分类,对于回归预测的相关方法还需要进一步探讨学习。

___________________________________

[x1]所谓监管学习就是给定一堆样本,每个样本都有一组属性和一个类别,这些类别是事先确定的,那么通过学习得到一个分类器,这个分类器能够对新出现的对象给出正确的分类。这样的机器学习就被称之为监督学

[x2]定义距离应满足的条件:
(1)非负性,即对所有的i和j,恒有dij>=0同时,当且仅当两个样品的p个变量对应相等时,其等式才成立;
(2)对称性,即对所有的i,j恒有dij=dji
(3)满足三角不等式,即对所有的i,j,k,恒有dij<djk+dki

[x3]自然语言处理是一门融语言学、计算机科学、数学于一体的科学。自然语言处理(NLP)是计算机科学,人工智能,语言学关注计算机和人类(自然)语言之间的相互作用的领域。(---来自百度百科)

本文转自:CSDN - xx19901314 的博客,转载此文目的在于传递更多信息,版权归原作者所有。

推荐阅读