1.1 监督学习方法

监督学习也称有教师学习，是最重要也最流行的机器学习方法之一，它可以从有标记的训练数据集中学习出一个函数，并依此函数对新的数据进行预测。监督学习的训练数据集由输入（特征）和有标记的输出（目标）组成的样本对构成。其中，有标记的输出（目标）也称为监督信号（Supervised Signal），是监督学习方法得名的由来。本节将首先对监督学习方法进行概述，然后简单介绍几种主流和热门的监督学习方法。

1.1.1 监督学习概述

在监督学习问题中，训练样本集中每个样本都有确定的输出标记，机器使用这些有标记的样本，根据输入的属性数据和对应的输出标记进行学习，产生模型（Model），该模型可对测试样本的标记进行预测。这里样本集可以表示为{（x₁，y₁），（x₂，y₂），…，（x_m，y_m）}，其中m为样本个数，x_i=（x_i1，x_i2，…，x_id）（i=1，2，…，d）表示样本的属性，每个样本均由d个属性进行描述，x_ij对应第i个样本的第j个属性，这些属性既可以是离散的也可以是连续的；y_i∈Y（i=1，…，m）表示样本x_i的预期输出或称为监督信号，Y为输出空间，用函数y=f（x）表示，期望输出y与属性向量x之间存在的非线性映射关系，该函数的输出可以是一个分类标记（此类问题称为分类问题），也可以是一个连续的值（此类问题称为回归问题）。也就是说，监督学习既可以用于分类问题又可以用于回归问题。对于分类问题，输出空间Y是一个类别的集合C={c₁，c₂，…，c_l}，其中c_i（i=1，2，…，l）为样本可能所属的类别，l表示类别数，最后分类学习获得的模型称为分类器（Classifier）；对于回归问题来说，输出空间Y一般为实数值。分类和回归问题的求解方法基本相同，在本书后续内容中，对各种方法的讨论主要针对分类问题展开。

监督学习有两种模型。一般常用的模型是监督学习产生的全局模型，即将输入映射到期望输出。而另一种模型则是将这种映射作为一个局部模型（如案例推理及最近邻算法）。为解决一个给定的监督学习问题，可分为以下5个步骤进行：

1）确定训练样本数据。在进行其他步骤前，首先应根据学习任务确定要使用哪种样本数据。例如，为解决遥感图像分类问题，可能选择多光谱或高光谱遥感图像数据。

2）收集训练样本数据。这些样本数据通常须具有表征真实事物的特征。一般可以由专家确定或者由机器和传感器测量得到输入和相应的输出数据。

3）确定学习函数输入特征的表示方法。输入数据的表示形式在很大程度上决定着学习函数的准确度。传统上，输入数据会被转换成一个特征向量，该特征向量包含了许多描述数据的特征。因为维数灾难的关系，特征的个数不宜太多，但也要足够大，才能准确地预测输出。

4）确定要学习的函数及其对应的学习算法所使用的学习器类型，如可以选择神经网络。

5）完成设计。在步骤2）搜集到的样本数据上运行学习算法。可以通过将算法运行在样本数据的子集（称为验证集）上或采用交叉验证（Cross-Validation）来调整学习算法的参数。参数调整后，算法可以运行在不同于训练集的测试集上。

目前可用于监督学习的通用算法不胜枚举，其中使用最广泛的方法有神经网络、最近邻算法、遗传算法、贝叶斯学习方法及决策树方法等。著名的Statlog研究项目^［6］将18种算法用于8种大型实际问题上，其中有卫星图像、手写数字图像、Karhunen-Loeve（KL）数字图像、车辆图像、心脏损伤、心脏病、信誉风险和移动控制问题等应用。结果表明，各种监督学习方法都各有优缺点，算法性能在很大程度上与待处理的样本数据的特性有关，没有哪一种算法可以在所有给定的问题上都表现最好。目前，常常需要借助一些经验方法来对监督学习方法的性能进行比较，并且寻找决定监督学习方法性能的样本数据特性。

1.1.2 监督学习方法简介

近年来，随着科技的发展，互联网、计算机、机器学习等多个领域相互融合，对监督学习产生了更多的需求，目前监督学习的发展主要着眼于如何提升分类精度与计算效率，因此而提出的集成分类器和大规模数据分类器成为当前监督学习研究领域的两个热点^［7，8］。为此，本小节将对K-最近邻算法、遗传算法、贝叶斯算法、决策树算法这4种主流监督学习算法以及集成分类器和大规模数据分类器进行简单的介绍。

（1）K-最近邻算法

K-最近邻算法^［9］（K-Nearest Neighbors，KNN）是将在特征空间中最接近的训练样本进行分类的监督学习方法。K-最近邻算法最初由Cover和Hart于1967年提出，其思路非常简单直观，易于快速实现，错误率较低。K-最近邻算法的基本思想为：根据距离函数计算待分类样本x和每个训练样本的距离，选择与待分类样本x距离最小的K个样本作为x的K个最近邻，最后根据x的K个最近邻判断x的类别。该算法没有单独的学习阶段，是一种在分类过程中实现学习的监督学习方法。

K-最近邻算法为非参数学习算法，在处理未知分布和非正态分布的数据时分类准确率较高，主要优点包括以下4点：

1）算法简单直观，易于快速实现。

2）无需额外数据对规则进行描述，训练数据本身就是算法的规则，而且对数据的一致性问题没有要求，具有一定的抗噪声能力。

3）K-最近邻算法虽然是以极限定理为理论依据，但在类别判别过程中，决策结果只取决于极少数的相邻样本数据，故K-最近邻算法可以较好地处理样本数量的不平衡问题。

4）在分类过程中，K-最近邻算法直接利用样本数据间的关系，降低了类别特征选择不正确对分类结果造成的不利影响，可以最大限度地减少分类过程中的误差项。

这就使得K-最近邻算法在处理一些类别特征不明显样本时，充分体现出其分类规则独立性的优势，进而使分类的自学习成为可能。

K-最近邻算法是基于实例的惰性学习方法，在分类时，这种学习法的运行需要非常大的存储空间。K-最近邻算法有以下几点不足：

1）分类速度慢。K-最近邻算法需要存储全部的训练样本，待进行分类时，算法须计算待分样本与训练样本库中每一个样本的相似度，才能求得与其最近的K个样本。对于样本集规模较大或者高维样本来说，该方法时间和空间复杂度较高，时间复杂度为O（mn），其中m为向量空间中特征维数，n为训练样本数。

2）属性等同权重影响了准确率。K-最近邻算法中每个属性具有相同的权重，但实际在这些特征中，有些特征与分类相关性较强，有些特征与分类相关性较弱，还有一些特征与分类不相关。因此，如果在计算相似度的时候，按所有特征等同权重来计算样本相似度会影响分类准确度。

3）样本集规模依赖性较强。K-最近邻算法在实际应用中受到很大的限制，因为某些类别可能无法提供充足的训练样本，无法满足K-最近邻算法所需要的相对均匀的特征空间条件，使类别判定误差较大。

4）K值难以确定，K值选择不当则分类精度不能保证。

为克服上述不足，很多学者从降低计算复杂度提高算法执行效率、优化相似度度量方法和决策策略、K值选取等方面对K-最近邻算法进行改进，有效提高了分类器的性能。

（2）遗传算法

遗传算法（Genetic Algorithm，GA）^［10］起源于20世纪60年代美国密歇根大学Holland教授对自然和人工自适应系统的研究，Bagley发明“遗传算法”一词并发表了第一篇有关遗传算法应用的论文。遗传算法的基本思想为：模拟达尔文生物进化论的自然选择和Mendel遗传学机理的生物进化过程，将解空间中每一个点都编码为二进制位串，称为染色体，并对应一个适应度值，适应度值按概率决定个体性质遗传到下一代中的机会，在每一代中使用选择、交叉和变异等作用机制获得新的种群，若干代后，种群中包含的个体具有更高的适应度，直到满足某种收敛指标为止。遗传算法作为一种快捷、简便的算法具有搜索面广、适应性强、容错能力强等特点。它采用随机搜索方法，几乎不需要所求问题的任何信息而仅需要目标函数的信息，并可不受搜索空间是否连续或可微的限制就可找到最优解，具有较强的适应能力，且便于并行计算。

遗传算法理论方面主要包含以下内容^［11］：分析遗传算法的编码策略、全局收敛性和搜索效率的数学基础、遗传算法的新结构探索、基因操作策略及其性能分析、遗传算法参数的选择以及与其他算法的综合比较等。

以遗传算法理论为基础的遗传学习系统是一种增强式学习系统，该学习系统的理论框架由Holland^［10］奠定，一般由产生式规则组成候选种群，和外界环境进行交互式学习以完成特定的任务。Holland^［10］发展了认知系统一号（Cognitive Systems-Ⅰ，CS-Ⅰ），该系统是第一个遗传学习系统，又称为分类器系统（Classifier System），并为后续研究提供了模板。

目前，遗传学习已被应用于诸多领域，其本身的发展也处于不断进化过程中^［12］。

（3）贝叶斯算法

自从20世纪60年代，贝叶斯学派形成后，关于贝叶斯算法的研究经久不衰。自20世纪90年代以来，贝叶斯算法一直是机器学习研究的重要方向之一。贝叶斯算法提供了一种概率手段，可用于确定给定数据下最可能的假设。贝叶斯算法的基本思想为：假设待考察的样本遵循某种概率分布，基于这些先验和数据观测假定进行推理，获得观测数据的后验概率，以此作出最优决策。贝叶斯算法能够方便地处理不完全数据，能够学习变量间的因果关系，同时贝叶斯网络与贝叶斯统计相结合，能够充分利用领域知识和样本数据的信息。

近年来，贝叶斯方法以其独特的不确定性知识表达形式、丰富的概率表达能力、综合先验知识的增量学习特性等成为当前众多机器学习方法中最为引人注目的焦点之一。其中贝叶斯密度估计探讨如何根据样本的数据信息和专家的先验知识获得对未知变量（向量）的分布及其参数的估计。贝叶斯网络是处理不确定信息最有效的方法之一，是表示变量间概率分布及关系的有向无环图，应用于有条件地依赖多种控制因素的决策，可以从不完全、不精确或不确定的知识或信息中作出推理，在多个领域中获得广泛应用。朴素贝叶斯（Naive Bayesian）模型假定特征向量的各分量相对于决策变量是独立的，也就是说各分量独立地作用于决策变量。尽管这一假定在一定程度上限制了朴素贝叶斯模型的适用范围，然而在实际应用中，不仅指数级的降低了贝叶斯网络构建的复杂性，而且即使在违背这种假定的条件下，朴素贝叶斯也表现出相当的健壮性和高效性，它已经成功地应用到分类、聚类及模型选择等数据挖掘的任务中。目前，许多研究人员正致力于放松特征变量间条件独立性的限制，以使它适用于更大的范围。

（4）决策树算法

决策树^［13］算法起源于20世纪60年代的概念学习系统（Concept Learning System），是目前应用最广泛的监督学习算法之一。决策树算法的基本思想为：采用树结构表示数据特征与目标之间的映射关系。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直至到达叶子节点，将叶子节点存放的类别作为决策结果。

决策树算法能够逼近离散函数，对噪声数据有很好的鲁棒性，该方法对完整表示的假设空间进行搜索，从而避免了受限假设空间的不足，能够学习解析表达式。它采用自顶向下不回溯策略，能保证找到一个简单的树。决策树算法通常包括两个部分，即树的生成和树的修剪。树的生成从一棵空的决策树开始，不断加入新的节点，根节点包含所有数据，根据设定的标准选择测试属性，用不同的测试属性递归进行数据分割，直到生成的决策树能够对所有训练样本正确分类为止。树的修剪过程是去掉一些可能是噪声或异常的数据。决策树建立的关键在于如何确定内部节点的分支。而在确定内部节点的分支过程中，选择不同的字段值将划分出不同的样本子集。

对于基本决策树算法，目前已有许多扩展算法，其中主要包括以下几方面：后修剪的方法；处理实数值的属性；容纳缺少属性值的训练样本；当有了新的训练实例时递增精化决策树；使用信息增益之外的其他属性选择度量；考虑与实例属性关联的代价。1979年，由J.Ross Quinlan提出了ID3算法，此算法能够减少树的深度，但是缺少对叶子数的探讨。在ID3算法的基础上发展了C4.5决策树算法，C4.5决策树能够处理连续属性，此外对于预测变量的缺值处理、剪枝技术、派生规则等方面都作了较大改进。

（5）集成学习分类器

集成学习是使用一系列学习器进行学习，并使用某种规则把各个学习结果进行整合，从而获得比单个学习器更好的学习效果的一种监督学习方法^［14］。分类问题是集成学习研究的基本问题。集成学习分类器的基本思想是：将多个弱分类器按特定方式集成起来，得到一个更强大的分类器。这种集成是有条件的，要想实现对整体精度的提升，要求每个子分类器的错误率都小于50%，且各分类器产生的错误相互独立。实现集成学习分类器的两个关键步骤是：构造足够多有差异的子分类器；对这些子分类器进行合理的集成。

构造子分类器的方法主要包括以下几种：

1）样本子集法。对训练样本集进行处理，即采用同一学习算法对不同样本子集进行独立学习，以生成多个子分类器。常使用这种方法构建基于决策树、神经网络、规则学习等算法的子分类器，这些算法中训练集微小改动便会造成分类器参数的较大变化，样本子集法对这类稳定性较差的算法，具有较好效果。Bagging^［15］、Boosting^［16］以及交叉检验^［17］均属于样本子集法。

2）属性选择法。当样本属性较多时对训练数据的输入属性进行一定操作可以让每个子分类器分别学习不同的属性，之后再对学习结果进行整合。该方法在构造子分类器时同样存在一定的局限性，当样本输入属性的数目比较少的时候，通过属性选择法构造子分类器并综合其结果，最终的分类精度不会提高反而有所降低。

3）类别编码法。此类方法以错误校正输出编码法^［18］为代表，首先对类别编码，将每个类别都对应到L位的二进制位串，从而得到一个K×L的二维编码阵（K表示类别数）；接着对编码矩阵按列进行学习，得到对应各列的二分类器。对于编码的第i（1≤i≤L）位为0的类别，二分类器对应该类别的输出为0；反之则输出为1。预测过程中，每个二分类器均对新样本进行分类，从而得到码长L的位串。利用最小汉明距离（Minimum Hamming Distance）法确定与该位串最接近的类别编码，从而实现对新样本类别的判断。类别编码法能将多类问题简化成为二类判别问题，因而引起广泛的关注。

4）随机因素法。引入随机因素实现多分类器。以BP神经网络分类器组为例，对相同样本集、相同结构的网络随机采用不同的权值初值，从而生成不同的子分类器。在决策树方法中，叶节点的扩展属性也可以作为一种随机因素，即对相同的内部节点随机选取不同扩展属性，从而得到有差别的决策树。

当得到子分类器后，可采用简单投票、贝叶斯投票、Winner-Take-All以及证据推理等方法进行集成。

集成学习的主要目标是提高分类精度，但也会造成存储量和计算负担增加的问题。集成学习需要更大的空间来保存各个子分类器，相应也需要更多计算时间来完成各个子分类器的学习过程。集成学习存在的问题是目前机器学习中的一个热门的研究方向，如如何提高集成学习的学习效果、如何提高集成学习可以解决的问题的规模、集成学习和数据复杂性之间的关系等问题仍有待于进一步研究。

（6）大规模数据分类器

大规模数据通常是指具有大样本集和高维属性的数据。随着分类过程中信息量的增大，常常需要对大量样本进行学习，这就要求提升原有监督学习算法的效率来处理大规模数据的分类问题。以数据挖掘问题为例，数据库往往包含数以万计的事务，而人们则希望能在短短数小时内实现对这些数据的分析。在信息检索过程中，往往一个文档就代表一个样本，而文档中每个字都是一个属性，则任一样本都有成千上万个属性。在语音辨识、目标监测和汉字识别等领域，则会发生分类类别数过多的情况。对这些大规模分类问题，监督机器学习算法主要集中于对大样本集和高维属性两方面的研究。

对大数据量样本集学习效率问题的研究，主要是对决策树算法的改进与扩展。其中一种途径是预先对样本集进行处理，如采用动态选取方法^［19］，根据决策的困难程度进行样本集的选择。对于靠近根节点的内部节点，选择较小的样本集。伴随着决策树的增长，逐步扩大样本集。在不影响分类精度的基础上，预处理能有效缩短样本集处理时间。另一种提升效率的途径是组合多个决策树。将样本集划分成N个独立子集，通过学习各子集分别生成多棵决策树，最后按照投票方式对各个决策树的预测结果进行综合。这种做法可能使单棵决策树的分类精度降低，但总体精度则会提升，而并行生成决策树则能有效缩短处理时间。

对于高维属性样本的分类问题，难以利用反向传播（BP）神经网络和C4.5等算法来直接处理。如果从统计学的角度分析，则可以把许多属性看作噪声，因此对它们的处理只是浪费时间，甚至会导致分类器精度降低。所以处理高维分类问题时常需要对属性进行合理选择。属性选择的方法通常有3类。第一类是初始化分析数据进行属性选择。其中最简单的做法是计算属性和类别间的互信息，来描述属性的重要程度。RELIEF-F算法^［20］通过随机抽取邻近样本调整各属性的权值，使得属于不同类的近邻样本能起到关键作用的属性获得更大权重值，而对于相关属性的问题，也可以证明即便属性间的相关性非常大，该算法仍然能有效地给属性赋予权重。第二类属性选择方法是通过测试性的学习选择最优的属性子集。以Wrapper算法^［21］为例，在学习过程中每次选择部分属性，通过10折交叉检验计算分类精度，选出最优分类结果对应的属性集。Leave-one-out^［22］是更有效的选择方式，学习过程中每次从训练样本集中选取一个样本，并用最近邻法判断该样本的类别。在依次处理完所有样本后，统计错误分类样本数即为该算法的分类错误率。根据不同属性集的错分率，选取最优的属性集。第三类属性选择方法将属性选择过程融合到学习过程中，如Variable-kernel similarity metric方法^［23］就是在学习的过程中，同时对高斯分布的参数和各属性的权重进行调整。

除本小节介绍的监督学习算法外，增强学习、过拟合（Over-fitting）控制、改善算法可理解性等也是监督学习领域的重要研究方向，近年来，学术界在这些方面的研究也有着长足的进步。