本文共 13572 字，大约阅读时间需要 45 分钟。

绪论

基本术语

机器学习（machine learning）：致力于研究如何通过计算的手段，利用经验来改善系统自身的性能。

机器学习所研究的主要内容，是关于在计算机上从数据中产生"模型"的算法，即"学习算法"（learning algorithm）。

模型（model）：泛指从数据中学得的结果。有文献用"模型"指全局性结 果（例如一棵决策树），而用"模式"指局部性结果（例如一条规则）。

数据集（data set）：一组记录的集合称为一个数据集，其中每条记录是关于一个事件或对象的描述，称为一个示例（instance）或样本（sample）。

反映事件或对象在某方面的表现或性质的事项，成为属性（attribute）或特征（feature）；属性上的取值称为属性值（attribute value）。属性张成的空间称为属性空间（attribute space）、样本空间（sample space）或输入空间。例如一个对象有三个属性，将这三个属性作为三个坐标轴，则它们张成一个用于描述该对象的三维空间，每一个对象都可以在这个空间中找到自己的坐标位置。由于空间中的每个点对应一个坐标向量，因此我们也把一个示例称为一个特征向量（feature vector）。

训练（training）：从数据中学得模型的过程称为学习（learning）或训练（training），这个过程通过执行某个学习算法来完成。

训练过程中使用的数据称为训练数据（training data），其中每个样本称为一个训练样本（training sample），训练样本组成的集合称为训练集（training set）。

学得模型对应了关于数据的某种潜在的规律，因此亦称假设（hypothesis）；这种潜在规律自身，则称为真相或真实（ground-truth），学习过程就是为了找出或逼近真相。

如果希望学得一个能够帮助我们判断的模型，仅有前面的示例数据显然是不够的，要建立这样的关于预测的模型，我们需获得训练样本的结果信息。示例结果的信息，称为标记（label）；拥有了标记信息的示例，则称为样例（example）。一般的，用（xi，yi）表示第i个样例，其中yi∈Y是示例xi的标记，Y是所有标记的集合，亦称标记空间（label space）或输出空间。

根据训练数据是否拥有标记信息，学习任务可大致划分为两大类"监督学习" （supervised learning） 和"无监督学习" （unsupervised learning），分类和回归是前者的代表，而聚类则是后者的代表。

预测（prediction）：若我们预测的是离散值，此类学习任务称为分类（classification）；若欲预测的是连续值，此类学习任务称为回归（regression）。还可以对对象做聚类（clustering），即将训练集中的对象分成若干组，每组称为一个簇（cluster），这些自动形成的簇可能对应一些潜在的概念划分。

对只涉及两个类别的二分类（binary classification）任务，通常称其中一个类为正类（positive class），另一个类为反类（negative class）；涉及多个类别时，则称为多分类（multi-class classification）任务。一般的，预测任务是希望通过对训练集{（x1，y1），（x2，y2），…（xm，ym）}进行学习，建立一个从输入空间X到输出空间Y的映射f：X→Y。对二分类任务，通常令Y={-1，+1}或{0，1}；对多分类任务，|Y|>2；对回归任务，Y=R，R为实数集。

学得模型后，使用其进行预测的过程称为测试（testing），被预测的样本称为测试样本（testing sample）。

泛化能力（generalization）：学得模型适用于新样本的能力。

归纳（induction）与演绎（deduction）是科学推理的两大基本手段。前者是从特殊到一般的"泛化"过程，即从具体的事实归结出一般性规律；后者则是从一般到特殊的"特化"（specialization）过程，即从基础原理推演出具体状况。

假设空间

假设空间（hypothesis space）：由输入空间到输出空间的映射的集合。将学习过程看作一个在所有假设组成的空间中进行搜索的过程，搜索目标是找到与训练集"匹配"的假设。与训练集一致的"假设集合”称为版本空间（version space）。

归纳偏好

归纳偏好（inductive bias）：机器学习算法在学习过程中对某种类型假设的偏好。

任何一个有效的机器学习算法必有其归纳偏好，否则它将被假设空间中看似在训练集上"等效"的假设所迷惑，而无法产生确定的学习结果。归纳偏好可看作学习算法自身在一个可能很庞大的假设空间中对假设进行选择的启发式或"价值观"。

奥卡姆剃刀（Occam’s razor）：是一种常用的、自然科学 研究中最基本的原则，即"若有多个假设与观察一致，则选最简单的那个"。并且我们认为"更平滑"意味着"更简单"。

没有免费的午餐定理：（No Free Lunch Theorem：NFL）：总误差竟与学习算法无关。

NFL 定理有一个重要前提：所有"问题"出现的机会相 同、或所有问题同等重要。但实际情形并不是这样。

NFL 定理最重要的寓意，是让我们清楚地认识到，脱离具体问题，空泛地谈论"什么学习算法更好"毫无意义，因为若考虑所有潜在的问题，则所有学习算法都一样好。要谈论算法的相对优劣，必须要针对具体的学习问题；在某些问题上表现好的学习算法，在另一些问题上却可能不尽如人意，学习算法自身的归纳偏好与问题是否相配，往往会起到决定性的作用。

模型评估与选择

经验误差与过拟合

通常我们把分类错误的样本数占样本总数的比例称为"错误率"（error rate），即如果在m个样本中有α个样本分类错误，则错误率E=α/m；相应的，1一α/m称为"精度"（accuracy），即"精度=1一错误率"。

经验误差（empirical error）：我们把学习器的实际预测输出与样本的真实输出之间的差异称为"误差"（error），学习器在训练集上的误差称为"训练误差"（training error）或"经验误差"，在新样本上的误差称为"泛化误差"（generalization error）.

过拟合（over fitting）：应该从训练样本中尽可能学出适用于所有潜在样本的"普遍规律"，这样才能在遇到新样本时做出正确的判别。但是把训练样本自身的一些特点当作了所有潜在样本都会具有的一般性质，这样就会导致泛化性能下降，这种现象在机器学习中称为"过拟合"。与"过拟合"相对的是"欠拟合" （under fitting），这是指对训练样本的一般性质尚未学好。

评估方法

评估方法：们可通过实验测试来对学习器的泛化误差进行评估并进而做出选择。为此，需使用一个"测试集"（testing set）来测试学习器对新样本的判别能力，然后以测试集上的"测试误差" （testing error）作为泛化误差的近似。

通常我们假设测试样本也是从样本真实分布中独立同分布采样而得，但需注意的是，测试集应该尽可能与训练集互斥，即测试样本尽量不在训练集中出现、未在训练过程中使用过。

留出法（hold-out）：直接将数据集D划分为两个互斥的集合，其中一个集合作为训练集S，另一个作为测试集T，即D=S∪T，S∩T=∅。在S上训练出模型后，用T来评估其测试误差，作为对泛化误差的估计。

交叉验证法（cross validation）：先将数据集D划分为k个大小相似的互斥子集，即D=D1∪D2∪…∪Dk，Di∩Dj=∅（i≠j）。 每个子集Di都尽可能保持数据分布的一致性，即从D中通过分层采样得到。然后，每次用k-1个子集的并集作为训练集，余 F的那个子集作为测试集；这样就可获得k组训练/测试集，从而可进行k次训练和测试，最终返回的是这k个测试结果的均值。显然，交叉验证法评估结果的稳定性和保真性在很大程度上取决于 k的取值，为强调这一点，通常把交叉验证法称为"k折交叉验证"（k-fold cross validation）。k最常用的取值是 10，此时称为10折交叉验证；其他常用的k值有5、20等。

• 10折交叉验证示意图

自助法（bootstrapping）：给定包含m个样本的数据集D， 我们对它进行采样产生数据集D’：每次随机从D中挑选一个 样本，将其拷贝放入D’，然后再将该样本放回初始数据集D中，使得该样本在 次采样时仍有可能被采到；这个过程重复执行 m 次后，我们就得到了包含m个样本的数据集D’，这就是自助采样的结果。显然，D中有一部分样本会在D’中多次出现，而另一部分样本不出现。可以做一个简单的估计，样本在m次采样中始终不被采到的概率是（1一1/m）^m，取极限得到

即通过自助采样，初始数据集D中约有36.8%的样本未出现在采样数据集D’中。于是我们可将D’用作训练集，D\D’用作测试集；这样实际评估的模型与期望评估的模型都使用m个训练样本，而我们仍有数据总量约1/3的、没在训练集中出现的样本用于测试。这样的测试结果，亦称"包外估计"（out-of-bag estimate）。

自助法在数据集较小、难以有效划分训练集和测试集时很有用；此外，自助法能从初始数据集中产生多个不同的训练集，这对集成学习等方法有很大的好处。然而，自助法产生的数据集改变了初始数据集的分布，这会引入估计偏差。因此，在初始数据量足够时，留出法和交叉验证法更常用一些。

大多数学习算法都有些参数（parameter）需要设定，参数配置不同，学得模型的性能往往有显著差别。因此，在进行模型评估与选择时，除了要对适用学习算法进行选择，还需对算法参数进行设定，这就是通常所说的"参数调节"或简称"调参"（parameter tuning）.

我们通常把学得模型在实际使用中遇到的数据称为测试数据，为了加以区分，模型评估与选择中用于评估测试的数据集常称为"验证集" （validation set）。例如，在研究对比不同算法的泛化性能时，我们用测试集上的判别效果来估计模型在实际使用时的泛化能力，而把训练数据另外划分为训练集和验证集，基于验证集上的性能来进行模型选择和调参。

性能度量

性能度量（performance measure）：对学习器的泛化性能进行评估，不仅需要有效可行的实验估计方法，还需要有衡量模型泛化能力的评价标准，这就是性能度量。

回归任务最常用的性能度量是"均方误差"（mean squared error），逻辑回归为"交叉熵”（Cross Entropy）。

查准率（precision）与查全率（recall）是更为适用的性能度量。两者分别定义为：

• P=TP/（TP+FP）
• R=TP/（TP+FN）

对于二分类问题，可将样例根据其真实类别与学习器预测类别的组合划分为真正例（true positive）、假正例（false positive）、真反例（true negative）、假反例（false negative）四种情形，令TP、FP、TN、FN分别表示其对应的样例数，则显然有TP+FP+TN+FN=样例总数。

• 混淆矩阵

综合考虑查准率、查全率的性能度量：

• 平衡点（Break-EventPointBEP）：它是"查准率=查全率"时的取值。

• F1 度量：F1=2PR/（P+R）

• Fβ 度量：F1=（1+β^2）PR/（β2×P+R），β>1时查全率有更大影响，β<1查准率有更大影响。

• PR曲线与平衡点示意图

受试者工作特征曲线（Receiver Operating Characteristic curve，ROC）：ROC曲线的纵轴是"真正 例率"（True Positive Rate，TPR），横轴是"假正例率"（False Positive Rate，FPR），两者分别定义为：

• TPR=TP/（TP+FN）
• FPR=FP/（TN+FP）

若一个学习器的ROC曲线被另一个学习器的曲线完全"包住"，则可断言后者的性能优于前者；则较为合理的判据是比较ROC曲线下的面积，即AUC（Area Under ROC Curve），AUC表示分类器接受true样本高于接受false样本的概率。AUC取值在0~1之间，AUC值越大的分类器，正确率越高。

• ROC 曲线与 AUC 示意图

代价敏感（cost-sensitive）错误率为：

• 代价矩阵（cost matrix，其中 costij 表示将第 i 类样本预测为第 j 类样本的代价）

• 正例概率代价（取值[0，1]）

• 归一化代价（取值[0，1]）

其中 p 是样例为正例的概率，FPR 是假正例率，FNR=1 -TPR是假反例率。

ROC曲线上每一点对应了代价平面上的一条线段。

• 代价曲线和期望总体代价

设 ROC 曲 线上点的坐标为（TPR，FPR），则可相应计算出FNR，然后在代价平面上绘制一条从（O，FPR）到（1，FNR）的线段，线段下的面积即表示了该条件下的期望总体代价；如此将ROC曲线上的每个点转化为代价平面上的一条线段，然后取所有线段的下界，围成的自积即为在所有条件下学习器的期望总体代价。

比较检验

统计假设检验（hypothesis test）为我们进行学习器性能比较提供了重要依据。基于假设检验结果我们可推断出，若在测试集上观察到学习器A比B好，则A的泛化性能是否在统计意义上优于B，以及这个结论的把握有多大。

• 二项检验：泛化错误率为 c 的学习器在 m 个测试样本中将 m’ 个样本误分类的概率服从二项分布。
• 交叉验证 t 检验：对两个学习器 A 和 B ，若错误率相同，则使用 k 折交叉验证法得到的测试错误率cAi-cBi的差均值为零，服从 t 分布。

偏差与方差

偏差方差分解（bias-variance decomposition）是解释学习算法泛化性能的一种重要工具。

泛化误差可分解为偏差、方差与噪声之和。

一般来说，偏差与方差是有冲突的，这称为偏差一方差窘境（bias-variance dilemma）。

假定我们能控制学习算法 的训练程度，则在训练不足时，学习器的拟合能力不够强，训练数据的扰动不足以使学习器产生显著变化，此时偏差主导了泛化错误率；随着训练程度的加深，学习器的拟合能力逐渐增强，训练数据发生的扰动渐渐能被学习器学到，方差逐渐主导了泛化错误率；在训练程度充足后，学习器的拟合能力已非常强，训练数据发生的轻微扰动都会导致学习器发生显著变化，若训练数据自身的、非全局的特性被学习器学到了，则将发生过拟合。

• 泛化误差与偏差、方差的关系示意图

线性模型

线性回归

对数几率回归（逻辑回归）

线性判别分析

线性判别分析（Linear Discriminant Analysis，LDA）是一种经典的线性学习方法。

LDA的思想非常朴素：给定训练样例集，设法将样例投影到一条直线上，使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离；在对新样本进行分类时，将其投影到同样的这条直线上，再根据投影点的位置来确定新样本的类别。

• LDA 的二维示意图

多分类学习

有些二分类学习方法可直接推广到多分类，但在更多情形下，我们是基于一些基本策略，利用二分类学习器来解决多分类问题。

不失一般性，考虑 N 个类别 C1， C2， •••， CN，多分类学习的基本思路是"拆解法"，即将多分类任务拆为若干个二分类任务求解。具体来说，先对问题进行拆分，然后为拆出的每个二分类任务训练一个分类器；在测试时，对这些分类器的预测结果进行集成以获得最终的多分类结果。这里的关键是如何对多分类任务进行拆分，以及如何对多个分类器进行集成。

最经典的拆分策略有三种：

• 一对一（One vs. One，简称 OvO）
  • OvO 将这 N 个类别两两配对，从而产生 N（N-1）/2 个二分类任务。在测试阶段，新样本将同时提交给所有分类器，于是将得到 N（N-1）/2 个分类结果，最终结果可通过投票产生：即把被预测得最多的类别作为最终分类结果。
• 一对其余（One vs. Rest，简称 OvR）
  • OvR 则是每次将一个类的样例作为正例、所有其他类的样例作为反例来训练 N 个分类器。在测试时若仅有一个分类器预测为正类，则对应的类别标记作为最终分类结果；若有多个分类器预测为正类，则通常考虑各分类器的预测置信度，选择置信度最大的类别标记作为分类结果。
• 多对多（Many vs. Ma町，简称 MvM）
  • MvM 是每次将若干个类作为正类，若干个其他类作为反类。显然，OvO 和 OvR 是 MvM 的特例。MvM 的正、反类构造必须有特殊的设计，不能随意选取。

类别不平衡问题

类别不平衡（class imbalance）：是指分类任务中不同类别的训练样例数目差别很大的情况。

再缩放（rescaling）：类别不平衡学习的一个基本策略。

再缩放的思想虽简单，但实际操作却并不平凡，主要因为"训练集是真实样本总体的无偏采样"这个假设往往并不成立，也就是说我们未必能有效地基于训练集观测几率来推断出真实几率。现有技术大体上有三类做法：第一类是直接对训练集里的反类样例进行"欠采样"（under sampling），即去除一些反例使得正、反例数目接近，然后再进行学习；第二类是对训练集里的正类样例进行"过采样"（over sampling），即增加一些正例使得正、反例数目接近，然后再进行学习；第三类则是直接基于原始训练集进行学习，但在用 训练好的分类器进行预测时，将上式 （3.48）嵌入到其决策过程中，称为"阈值移动"（threshold-moving）。

，过采样法不能简单地对初始正例样本进行重复采样，否则会招致严重的过拟合；过采样法的代表性算法 SMOTE 是通过对训练集里的正例进行插值来产生额外的正例。另一方面，欠采样法若随机丢弃反例，可能丢失一些重要信息；欠采样法的代表性算法 EasyEnsemble 则是利用集成学习机制，将反例划分为若干个集合供不同学习器使用，这样对每个学习器来看都进行了欠采样，但在全局来看却不会丢失重要信息。

多分类学习中虽然有多个类别，但每个样本仅属于一个类别。如果希望为一个样本同时预测出多个类别标记，例如一幅图像可同时标注为"蓝天"、“白云”、“羊群”、“自然场景”，这样的任务就不再是多分类学习，而是"多标记学习"。

神经网络

神经网络

神经网络的定义：神经网络是由具有适应性的简单单元组成的广泛并行互连的网络，它的组织能够模拟生物神经系统对真实 世界物体所作出的交互反应。

误差逆传播算法

全局最小与局部最小

• 局部极小解（local minimum）是参数空间中的某个点，其邻域点的误差函数值均不小于该点的函数值。
• 全局最小解（global minimum）则是指参数空间中所有点的误差函数值均不小于该点的误差函数值。

在现实任务中，人们常采用以下策略来试图"跳出"局部极小，从而进一 步接近全局最小：

• 以多组不同参数值初始化多个神经网络。按标准方法训练后，取其中误差最小的解作为最终参数。这相当于从多个不同的初始点开始搜索，这样就可能陷入不同的局部极小从中进行选择有可能获得更接近全局最小的结果。
• 使用"模拟退火"（simulated annealing）技术。模拟退火在每一步都以一定的概率接受比当前解更差的结果，从而有助于"跳出"局部极小。在每步迭代过程中，接受"次优解"的概率要随着时间的推移而逐渐降低，从而保证算法稳定。
• 使用随机梯度下降。与标准梯度下降法精确计算梯度不同，随机梯度下降法在计算梯度时加入了随机因素，于是即便陷入局部极小点，它计算出的梯度仍可能不为零，这样就有机会跳出局部极小继续搜索。

此外，遗传算法（genetic algorithms）也常用来训练神经网 络以更好地逼近全局最小，需注意的是，上述用于跳出局部极小的技术大多是启发式，理论上尚缺乏保障。

深度学习

典型的深度学习（deep learning）模型就是很深层的神经网络。

支持向量机

间隔与支持向量

如上图所示，距离超平面最近的这几个训练样本点使式（6.3）的等号成立，它们被称为"支持向量"（support vector），两个异类支持向量到超平面的距离之和为：

它被称为"间隔"（margin）。

核函数

对线性不可分问题，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。如果原始空间是有限维，即属性数有限，那么一定存在一个高维特征空间使样本可分。

令φ（x）表示将x映射后的特征向量，可以设想这样一个函数：

有了这样的函数，我们就不必直接去计算高维甚至无穷维特征空间中 的内积。这个函数就是核函数（kernel function）。

• 常用核函数

软间隔与正则化

在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分；即使恰好找到了某个核函数使训练集在特征空间中线性可分，也很难断定这个貌似线性可分的结果不是由于过拟合所造成的。

所有样本都必须划分正确，这称为"硬间隔"（hard margin），而"软间隔”（soft margin）则是允许某些样本不满足约束。当然，在最大化间隔的同时，不满足约束的样本应尽可能少。

当 C 为无穷大时，迫使所有样本均满足约束; 当 C 取有限值时，允许一些样本不满足约束。

支持向量回归

对样本（x，y）的传统回归模型通常直接基于模型输出 f（x） 与真实输出 y 之间的差别来计算损失，当且仅当 f（x） 与 y 完全相同时，损失才为零。与此不同，支持向量回归（Support Vector Regression，SVR）假设我们能容忍 f（x） 与 y 之间最多有 e 的偏差，即仅当 f（x） 与 y 之间的差别绝对值大于 e 时才计算损失。

贝叶斯分类器

贝叶斯决策论

极大似然估计

概率模型的训练过程就是参数估计（parameter estimation）过程。对于参数估计，统计学界的两个学派分别提供了不同的解决方案：频率主义学派（Frequentist）认为参数虽然未知，但却是客观存在的固定值，因此，可通过优化似然函数等准则来确定参数值；贝叶斯学派（Bayesian）则认为参数是未观察到的随机变量，其本身也可有分布，因此，可假定参数服从一个先验分布，然后基于观测到的数据来计算参数的后验分布。

朴素贝叶斯分类器

朴素贝叶斯分类器（naive Bayes classifier）采用了

“属性条件独立性假设”（attribute conditional independence assumption）：对已知类别，假设所有属性相互独立。换言之，假设每个属性独立地对分类结果发生影响。

显然，拉普拉斯修正（Laplacian correction）避免了因训练集样本不充分而导致概率估值为零的问题，并且在训练集变大时，修正过程所引入的先验（prior）的影响也会逐渐变得可忽略，使得估值渐趋向于实际概率值。

贝叶斯网

贝叶斯网（Bayesian network）亦称"信念网"（belief network），它借助有向无环图（Directed Acyclic Graph，DAG）来刻画属性之间的依赖关系，并使用条件概率表 （Conditional Probability Table，CPT）来描述属性的联合概率分布。

以上图为例，联合概率分布定义为：

贝叶斯网中三个变量之间的典型依赖关系：

EM 算法

未观测变量的学名是"隐变量"（latent variable）。我们可通过对隐变量计算期望，来最大化己观测数据的对数"边际似然" （marginal likelihood）。

EM算法（Expectation-Maximization）是常用的估 计参数隐变量的利器，它是一种迭代式的方法。其基本想法是：

• 若参数θ己知，则可根据训练数据推断出最优隐变量Z的值（E 步）；
• 若Z的值已知，则可方便地对参数θ做极大似然估计（M 步）。

集成学习

个体与集成

集成学习（ensemble learning）：通过构建并结合多个学习器来完成学习任务，有时也被称为多分类器系统（multi-classifier system）、基于委员会的学习（committee-based learning）等。

• 同质（homogeneous）集成学习：神经网络。
• 异质（heterogenous）集成学习。

同质集成中的个体学习器亦称"基学习器"（base learner），相应的学习算法称为"基学习算法"（base learning algorithm）。异质集成中的个体学习器由不同的学习算法生成，这时就不再有基学习算法，相应的，个体学习器一般不称为基学习器，常称为"组件学习器"（component learner）或直接称为个体学习器。

集成学习通过将多个学习器进行结合，常可获得比单一学习器显著优越的泛化性能。因为集成学习的很多理论研究都是针对弱学习器（weak learner）进行的，所以基学习器有时也被直接称为弱学习器。

要获得好的集成，个体学习期应该"好而不同”，即个体学习器要有一定的"准确性”，即学习器不能太坏，并且要有"多样性" （diversity），即学习器间具有差异。

在基学习器的误差相互独立的情况下，随着集成中个体分类器数目 T 的增大，集成的错误率将指数级下降，最终趋向于零。

根据个体学习器的生成方式，目前的集成学习方法大致可分为两大类：

• 个体学习器间存在强依赖关系、必须串行生成的序列化方法：Boosting；
• 个体学习器间不存在强依赖关系、可同时生成的并行化方法：Bagging 和"随机森林"（Random Forest）。

Boosting

Boosting是一族可将弱学习器提升为强学习器的算法。这族算法的工作机制类似：先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器；如此重复进行，直至基学习器数目达到事先指定的值T，最终将这T个基学习器进行加权结合。

Boosting 族算法最著名的代表是 AdaBoost。

Bagging 与随机森林

Bagging是并行式集成学习方法最著名的代表。由自助采样法采样出 T 个含 m 个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基学习器进行结合。这就是 Bagging 的基本流程。在对预测输出进行结合时，Bagging通常对分类任务使用简单投票法，对回归任务使用简单平均法。若分类预测时出现两个类收到同样票数的情形，则最简单的做法是随机选择一个，也可进一步考察学习器投票的置信度来确定最终胜者。

随机森林（Random Forest，RF）是Bagging的一个扩展变体。RF在以决策树为基学习器构建Bagging集成的基础上，进一步在 决策树的训练过程中引入了随机属性选择。具体来说，传统决策树在选择划分属性时是在当前结点的属性集合（假定有d个属性）中选择一个最优属性；而在RF中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优属性用于划分。这里的参数k控制了随机性的引入程度；若令k=d，则基决策树的构建与传统决策树相同；若令k=1，则是随机选择一个属性用于划分；一般情况下，推荐值k=log2d。

结合策略

学习器结合可能会从三个方面带来好处：

1. 从统计的方面来看，由于学习任务的假设空间往往很大，可能有多个假设在训练集上达到同等性能，此时若使用单学习器可能因误选而导致泛化性能不佳，结合多个学习器则会减小这一风险。
2. 从计算的方面来看，学习算法往往会陷入局部极小，有的局部极小点所对应的泛化性能可能很糟糕，而通过多次运行之后进行结合，可降低陷入糟糕局部极小点的风险。
3. 从表示的方面来看，某些学习任务的真实假设可能不在当前学习算法所考虑的假设空间中，此时若使用单学习器则肯定无效，而通过结合多个学习器，由于相应的假设空间有所扩大，有可能学得更好的近似。

结合的常见策略：

• 平均法
  • 简单平均法
  • 加权平均法
• 投票法
  • 绝对多数投票法（票低于半数拒绝预测）
  • 相对多数投票法
  • 加权投票法
• 学习法

当训练数据很多时，一种更为强大的结合策略是使用"学习法"，即通过另一个学习器来进行结合。Stacking学习法的典型代表，这里我们把个体学习器称为初级学习器，用于结合的学习器称为 次级学习器或元学习器（meta-learner）。

Stacking先从初始数据集训练出初级学习器，然后"生成"一个新数据集用于训练次级学习器。在这个新数据集中，初级学习器的输出被当作样例输入特征，而初始样本的标记仍被当作样例标记。

聚类

性能度量

聚类性能度量亦称聚类"有效性指标"（validity index），与监督学习中的性能度量作用相似。

我们希望"物以类聚"，即同一簇的样本尽可能彼此相似，不同簇的样本尽可能不同。换言之，聚类结果的"簇内相似度"（intra-cluster similarity）高且"簇间相似度"（inter-cluster similarity）低。

聚类性能度量大致有两类。一类是将聚类结果与某个"参考模型"（reference model）进行比较，称为"外部指标"（external index）；另一类是直接考察聚类结果而不利用任何参考模型，称为"内部指标"（internal index）。

• 外部指标
  • Jaccard 指数
  • FM 指数
  • Rand 指数
• 内部指标
  • DB 指数
  • Dunn 指数

距离计算

对函数dist（.，.），若它是一个"距离度量"（distance measure），则需满足一些基本性质：

• 闵可夫斯基距离（Minkowski distance）

• 欧氏距离（Euclidean distance）

• 曼哈顿距离 （Manhattan distance）

聚类算法

• 原型聚类（基于原型的聚类）
  • k 均值（k-means）
  • 学习向量化（Learning Vector Quantization，LVQ）
  • 高斯混合聚类（Mixture-oι Gaussian）
• 密度聚类（基于密度的聚类）
  • DBSCAN
• 层次聚类（基于层次的聚类）
  • AGNES

降维

k 近邻学习

k近邻（k-Nearest Neighbor，kNN）学习是一种常用的监督学习方法。它没有显式的训练过程。事实上，它是"懒惰学习"（lazy learning）的著名代表，此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理；相应的，那些在训练阶段就对样本进行学习处理的方法，称为"急切学习"（eager learning）。

k近邻基于一个重要假设：任意测试样本a附近任意小的距 离范围内总能找到一个训练样本，即训练样本的来样密度足够大，或称为"密采样"（dense sample）。

低维嵌入

维数灾难（curse of dimensionality）：在高维情形下出 现的数据样本稀疏、距离计算困难等问题，是所有机器学习方法共同面临的严重障碍。

缓解维数灾难的一个重要途径是降维（dimension reduction），亦称"维数约简”，即通过某种数学变换将原始高维属性空间转变为 一个低维"子空间"（subspace），在这个子空间中样本密度大幅提高，距离计算也变得更为容易。

为什么能进行降维？这是因为在很多时候，人们观测或收集到的数据样本虽是高维的，但与学习任务密切相关的也许仅是某个低维分布，即高维空间中的一个低维"嵌入"（embedding）。

主成分分析（PCA）

主成分分析（Principal Component Analysis，PCA）是最常用的一种降维方法。

计算学习理论

PAC 学习

计算学习理论中最基本的是概率近似正确（Probably Approximately Correct，PAC）学习理论。

有限假设空间

• 可分情形：
  • 目标概念 c 属于假设空间 H，只保留与训练集 D 一致的假设，若训练集足够大，则直到 H 中只剩一个假设。
• 不可分情形：
  • H 中必存在一个泛化误差最小的假设。

VC 维

现实学习任务所面临的通常是无限假设空间，最常见的办法是考虑假设空间的"VC维"（Vapnik-Chervonenkis dimension）。

假设空间H的VC维是能被H打散的最大示例集的大小，VC（H）=d 表明存在大小为d的示例集能被假设空间H打散。

注意：并不意味着所有大小为d的示例集都能被假设空间H打散，VC 维的定义与数据分布D无关，因此，在数据分布未知时仍能计算出假设 空间H的VC维。

• 二维实平面上所有线性划分构成的假设空间的 VC 维为 3。

References

转载地址：https://mortal.blog.csdn.net/article/details/92201647 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！