机器学习总结（一）

文章目录

1、判别模型和生成模型

监督学习的任务就是学习一个模型，应用该模型对给定的输入预测相应的输出，这个模型的一般形式为决策函数：f(X)或者条件概率分布：P(Y∣X)

监督学习方法又可以分为生成方法（generative approach）和判别方法（discriminative approach），所生成的模型分别为生成模型和判别模型。

生成模型：由数据学习联合概率分布$P(X,Y) ，然后求出条件概率分布P(Y|X)$ 作为预测的模型，即为生成模型：

P(Y∣X)=P(X)P(X,Y)​

之所以称为生成方法，是因为模型表示了给定输入X 产生输出Y的生成关系。

生成模型常见模型：

• 朴素贝叶斯（Naive Bayes）
• 隐马尔科夫模型（HMM）
• 高斯混合机其他类型混合模型（GMM）
• 平均单依赖估计（AODE)
• LDA主题模型
• 限制玻尔兹曼机（RBM）
• 贝叶斯网络（Bayesian Networks）
• 隐含狄利克雷分布（Latent Dirichlet Allocation）。

判别模型：由数据直接学习决策函数f(X)，或求解条件概率分布P(Y∣X)作为预测模型。也可以称为条件模型或概率模型，利用正负例的分类标签，求得判别模型的边缘分布，目标函数直接对应于分类准确率。

判别方法关心的是：给定的输入X ，应该预测什么样的输出Y。

判别模型常见模型：

• 线性回归（Linear Regression）
• 逻辑回归（Logistic Regression）
• 支持向量机（SVM）
• 传统神经网络（Traditional Neural Networks）
• 线性判别分析（Linear Discriminative Analysis）
• 条件随机场（Conditional Random Field）
• 集成学习（boosting）
• 条件随机场（Conditional random fields）

两种方法的不同：

（1）生成方法优点：

• 生成方法可以还原出联合概率分布$P(X，Y) $，判别方法不能。
• 生成方法学习收敛速度更快，即当样本容量增加时，学到的模型可以更快的收敛于真实模型。
• 当存在隐变量时，仍可以用生成方法，但判别方法不能用。
  -生成模型的假设性更强一些，因为通常是从后验分布的角度去思考问题，通常对x的分布做了一些假设
• 生成模型最大化联合对数似然函数
• 因为生成模型对于特征的分布都做出了一定的假设（如高斯判别模型假设特征分布满足多元高斯分布），所以如果对于特征的分布估计比较正确的情况下，生成模型的速度更好准确性也更高。
  -生成模型在训练数据的时候对于每一类数据的都是独立估计的（也就是每一类的参数不同），这也就说明如果有新类别加入的情况下，是不需要对原有类别进行重新训练的
  -生成模型有一个大的缺点就是不能对特征进行某些预处理（如特征映射），因为预处理后的数据分布往往有了很大的变化。

（2）判别方法特点：

• 直接学习条件概率P(Y∣X) 或决策函数f(X) ，直接预测，往往学习准确率更高
• 由于直接学习条件概率P(Y∣X) 或决策函数$f(X) $，可以对数据进行各种程度上的抽象、定义特征并使用特征，因此可以简化学习问题。
• 最大化似然函数

由生成模型可以得到判别模型，但由判别模型得不到生成模型。

2、最大概率分词

其基本思想是：一个待切分的汉字串可能包含多种分词结果，将其中概率最大的作为该字串的分词结果。若某候选词在训练语料中未出现，其概率为0，求出概率最大的分词方式就是分词结果。

eg：P(B)=P(南京)∗P(市长)∗P(江大桥)=0.8∗0.6∗0.4=0.192

3、中文分词的基本方法

基于语法规则的方法、基于词典的方法和基于统计的方法。

第一类：基于语法和规则的分词法

其基本思想就是在分词的同时进行句法、语义分析,利用句法信息和语义信息来进行词性标注,以解决分词歧义现象。因为现有的语法知识、句法规则十分笼统、复杂,基于语法和规则的分词法所能达到的精确度远远还不能令人满意,目前这种分词系统还处在试验阶段。

第二类：基于字符串匹配的分词方法（机械式分词法，即基于词典）

机械分词的原理是将文档中的字符串与词典中的词条进行逐一匹配,如果词典中找到某个字符串,则匹配成功,可以切分,否则不予切分。基于词典的机械分词法,实现简单,实用性强,但机械分词法的最大的缺点就是词典的完备性不能得到保证。据统计,用一个含有70000个词的词典去切分含有15000个词的语料库,仍然有30%以上的词条没有被分出来,也就是说有4500个词没有在词典中登录。

可以进一步分为最大匹配法，最大概率法，最短路径法等。

• **1. 最大匹配法指：**按照一定顺序选取字符串中的若干个字当做一个词，去词典中查找。

• **最大匹配法指根据扫描方式可细分为：**正向最大匹配，反向最大匹配，双向最大匹配，最小切分。

• 2. 最大概率法：是一个待切分的汉字串可能包含多种分词结果，将其中概率最大的那个作为该字串的分词结果。

• 3. 最短路径法：在词图上选择一条词数最少的路径。

第三类：基于词频统计的方法

基于统计的分词法的基本原理是根据字符串在语料库中出现的统计频率来决定其是否构成词。词是字的组合,相邻的字同时出现的次数越多,就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映它们成为词的可信度。

举例：HMM（隐马尔科夫模型），MAXENT（最大熵模型），MEMM（最大熵隐马尔科夫模型），CRF（条件随机场）。

4、CRF（条件随机场）的特点

CRF结合了最大熵模型和隐马尔可夫模型的特点，是一种无向图模型，近年来在分词、词性标注和命名实体识别等序列标注任务中取得了很好的效果。条件随机场是一个典型的判别式模型，其联合概率可以写成若干势函数联乘的形式，其中最常用的是线性链条件随机场。

CRF没有HMM那样严格的独立性假设条件，因而可以容纳任意的上下文信息，特征设计灵活。CRF需要训练的参数更多，与MEMM和HMM相比，它存在训练代价大、复杂度高的缺点。

• **HMM：**是对转移概率和表现概率直接建模，统计共现概率

• **MEMM：**对转移概率和表现概率建立联合概率，统计时统计的是条件概率

• 容易陷入局部最优，是因为MEMM只在局部做归一化

• **CRF：**在给定需要标记的观察序列的条件下，计算整个标记序列的联合概率分布，而不是在给定当前状态条件下，定义下一个状态的状态分布

• 统计了全局概率，在做归一化时，考虑了数据在全局的分布，而不是仅仅在局部归一化，这样就解决了MEMM中的标记偏置的问题

5、隐马尔可夫模型（HMM）时间复杂度及可以使用的数据集

设其观察值空间为

O={o1​,o2​,...,oN​}

状态空间为

S={s1​,s2​,...,sK​}
如果用维特比算法(Viterbi algorithm)进行解码，时间复杂度为$（O(NK^2)） $

可以应用的数据集：只要是和时间序列问题有关的 , 都可以试试HMM

例如：基因序列数据集，电影浏览数据集，股票市场数据集

6、在二分类问题中的评价方案

当测试集的正例和负例数量不均衡时，以下评价方案哪个是相对不合理的（A）

• A. Accuracy:(TP+TN)/all

• B. F-value:2·recall·precision/(recall+precision)

• C. G-mean:sqrt(precision*recall)

• D. AUC:ROC曲线下面积

在二分类问题中，我们主要关注的是测试集的正样本能否正确分类。

当样本不均衡时，比如样本中负样本数量远远多于正样本，此时如果负样本能够全部正确分类，而正样本只能部分正确分类，那么(TP+TN)可以得到很高的值，也就是Accuracy是个较大的值，但是正样本并没有取得良好的分类效果。因此A选项是不合理的。在样本不均衡时，可以采用BCD选项方法来评价。
（precision=TP/(TP+FP),recall=TP/(TP+FN)）

7、决策树特点

决策树（decision tree）是一种基本的分类与回归方法，是一颗依托决策而建立起来的树。

决策树就是用一棵树来表示我们的整个决策过程。这棵树可以是二叉树（比如 CART 只能是二叉树），也可以是多叉树（比如 ID3、C4.5 可以是多叉树或二叉树）。

决策树的三个步骤：特征选择、决策树的生成、决策树的修剪。

分类过程：

从根节点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点，此时，每个子结点对应着该特征的一个取值，如此递归地对实例进行测试并分配，直到达到叶结点，最后将实例分到叶结点的类中。

根节点包含整个样本集，每个叶结点都对应一个决策结果（注意，不同的叶节点可能对应同一个决策结果），每一个内部节点都对应一次决策过程或者说是一次属性测试。从根节点到每个叶节点的路径对应一个判定测试序列。

图示：

• 决策树学习的目标：根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类。

• 决策树学习的本质：从训练集中归纳出一组分类规则，或者说是由训练数据集估计条件概率模型。

• 决策树学习的损失函数：正则化的极大似然函数

• 决策树学习的策略：最小化损失函数

• 决策树学习的目标：在损失函数的意义下，选择最优决策树的问题。

• 决策树原理和问答猜测结果游戏相似，根据一系列数据，然后给出游戏的答案。

一句话描述决策树：

决策树学习的算法通常是递归的选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程，这一过程对应着特征空间的划分，也对应着决策树的构建。

决策树的构造过程：

1. 开始：构建根节点，将所有训练数据都放在根节点，选择一个最优特征，按着这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。

2. 如果这些子集已经能够被基本正确分类，那么构建叶节点，并将这些子集分到所对应的叶节点去。

3. 如果还有子集不能够被正确的分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的节点，如果递归进行，直至所有训练数据子集被基本正确的分类，或者没有合适的特征为止。

4. 每个子集都被分到叶节点上，即都有了明确的类，这样就生成了一颗决策树。

特征选择准则：

划分数据集的大原则是：将无序数据变得更加有序，但是各种方法都有各自的优缺点，信息论是量化处理信息的分支科学，在划分数据集前后信息发生的变化称为信息增益，获得信息增益最高的特征就是最好的选择，所以必须先学习如何计算信息增益，集合信息的度量方式称为香农熵，或者简称熵。

熵的介绍

**熵：**如果一个随机变量X的可能取值为X = {x1, x2,…, xk}，，其概率分布为P(X = xi) = pi（i = 1,2, …, n），则随机变量X的熵定义为：H(x)=−x∑​p(x)logp(x)

负号变换之后变为：H(x)=x∑​p(x)logp(x)1​

**联合熵：**两个随机变量X,Y的联合分布，可以形成联合熵，用H(X,Y)表示。

**条件熵：**在随机变量X发生的前提下，随机变量Y发生所新带来的熵定义为Y的条件熵，用H(Y∣X)表示，用来衡量在已知随机变量X的条件下随机变量Y的不确定性。

且有：H(Y∣X)=H(X,Y)–H(X)

**相对熵：**又称互熵，交叉熵，鉴别信息，Kullback熵，Kullback-Leible散度等。设p(x)、q(x)是X中取值的两个概率分布，则p对q的相对熵是：

在一定程度上，相对熵可以度量两个随机变量的“距离”，且有D(p∣∣q)̸​=D(q∣∣p)。另外，值得一提的是，D(p∣∣q)是必然大于等于0的。

最大熵：

主要思想：在学习概率模型时，所有可能的模型中熵最大的模型是最好的模型，若概率模型需要满足一些约束，则最大熵原理就是在满足已知约束的条件集合中选择熵最大模型。最大熵原理指出，对一个随机事件的概率分布进行预测时，预测应该满足全部已知的约束，而对未知的情况不要做任何主观假设，在这种情况下，概率分布最均匀，预测的风险最小，因此得到的概率分布的熵是最大的。

熵是随机变量不确定性的度量，不确定性越大，熵值越大；若随机变量退化成定值，熵为0。如果没有外界干扰，随机变量总是趋向于无序，在经过足够时间的稳定演化，它应该能够达到的最大程度的熵。

为了准确的估计随机变量的状态，我们一般习惯性最大化熵，认为在所有可能的概率模型（分布）的集合中，熵最大的模型是最好的模型。换言之，在已知部分知识的前提下，关于未知分布最合理的推断就是符合已知知识最不确定或最随机的推断，其原则是承认已知事物（知识），且对未知事物不做任何假设，没有任何偏见。

例如，投掷一个骰子，如果问"每个面朝上的概率分别是多少"，你会说是等概率，即各点出现的概率均为1/6。因为对这个"一无所知"的色子，什么都不确定，而假定它每一个朝上概率均等则是最合理的做法。从投资的角度来看，这是风险最小的做法，而从信息论的角度讲，就是保留了最大的不确定性，也就是说让熵达到最大。

1）信息增益：

在划分数据集之前之后信息发生的变化（也就是熵的变化）称为信息增益，分别计算每个特征值划分数据集获得的信息增益，选择信息增益最高的特征作为划分特征。

熵定义为信息的期望值，如果待分类的事物可能划分在多个类之中，则符号xi​的信息定义为：

其中，$p(x_i)$是选择该分类的概率。

为了计算熵，我们需要计算所有类别所有可能值所包含的信息期望值，熵通过下式得到：
H=−Σi=1n​p(xi​)log2​p(xi​)
其中，n为分类数目，熵越大，随机变量的不确定性就越大。

当熵中的概率由数据估计(特别是最大似然估计)得到时，所对应的熵称为经验熵(empirical entropy)。什么叫由数据估计？比如有10个数据，一共有两个类别，A类和B类。其中有7个数据属于A类，则该A类的概率即为十分之七。其中有3个数据属于B类，则该B类的概率即为十分之三。浅显的解释就是，这概率是我们根据数据数出来的。我们定义贷款申请样本数据表中的数据为训练数据集D，则训练数据集D的经验熵为H(D)，|D|表示其样本容量，及样本个数。设有K个类Ck，k = 1,2,3,···,K，|Ck|为属于类Ck的样本个数，这经验熵公式可以写为：

根据此公式计算经验熵H(D)，分析贷款申请样本数据表中的数据。最终分类结果只有两类，即放贷和不放贷。根据表中的数据统计可知，在15个数据中，9个数据的结果为放贷，6个数据的结果为不放贷。所以数据集D的经验熵H(D)为：

经过计算可知，数据集D的经验熵H(D)的值为0.971。

在理解信息增益之前，要明确——条件熵

信息增益表示得知特征X的信息而使得类Y的信息不确定性减少的程度。

条件熵H(Y∣X)表示在已知随机变量X的条件下随机变量Y的不确定性，随机变量X给定的条件下随机变量Y的条件熵(conditional entropy) 为H(Y∣X)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望：

其中，$p_i=P(X=x_i)$

当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的分别为经验熵和经验条件熵，此时如果有0概率，令0log0=0

信息增益：

信息增益是相对于特征而言的。所以，特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D∣A)之差，即：

一般地，熵H(D)与条件熵H(D∣A)之差称为互信息(mutual information)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

信息增益值的大小相对于训练数据集而言的，并没有绝对意义，在分类问题困难时，也就是说在训练数据集经验熵大的时候，信息增益值会偏大，反之信息增益值会偏小，使用信息增益比可以对这个问题进行校正，这是特征选择的另一个标准。

信息增益的计算：

2）信息增益比：

特征A对训练数据集D的信息增益比gR​(D,A)定义为其信息增益g(D,A)与训练数据集D的经验熵之比：

决策树的特点：

• 优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
• 缺点：可能会产生过度匹配的问题

决策树的过拟合：

决策树生成算法递归的产生决策树，直到不能继续下去为止，这样产生的树往往对训练数据的分类很准确，但对未知测试数据的分类却没有那么精确，即会出现过拟合现象。过拟合产生的原因在于在学习时过多的考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树，解决方法是考虑决策树的复杂度，对已经生成的树进行简化。

决策树的剪枝：

从已经生成的树上裁掉一些子树或叶节点，并将其根节点或父节点作为新的叶子节点，从而简化分类树模型，防止过拟合，提高泛化性能。

**实现方式：**极小化决策树整体的损失函数或代价函数来实现

剪枝分为预剪枝与后剪枝：

• 预剪枝：是指在决策树的生成过程中，对每个节点在划分前先进行评估，若当前的划分不能带来泛化性能的提升，则停止划分，并将当前节点标记为叶节点。

• 后剪枝：是指先从训练集生成一颗完整的决策树，然后自底向上对非叶节点进行考察，若将该节点对应的子树替换为叶节点，能带来泛化性能的提升，则将该子树替换为叶节点。

• 那么怎么来判断是否带来泛化性能的提升那？最简单的就是留出法，即预留一部分数据作为验证集来进行性能评估。

分别介绍不同类型的决策树：

1） ID3：使用信息增益作为选择特征的准则

1. 首先是针对当前的集合，计算每个特征的信息增益
2. 然后选择信息增益最大的特征作为当前节点的决策决策特征
3. 根据特征不同的类别划分到不同的子节点（比如年龄特征有青年，中年，老年，则划分到3颗子树）
4. 然后继续对子节点进行递归，直到所有特征都被划分

核心：在决策树的各个结点上应用信息增益来选择特征，递归的构建决策树。ID3相当于用极大似然法进行概率模型的选择

构建方法：从根节点（root node）开始，对结点计算所有可能的特征信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点，再对子结点递归的调用此方法，构建决策树，知道所有特征的信息增益均很小，或没有特征可以选择为止。

• 信息增益=划分前的熵 - 划分后的熵

• 信息增益越大，则利用属性A划分后的纯度提升越大

• ID3仅仅适用于二分类问题，仅仅能够处理离散属性

• 算法生成的决策树是一棵多叉树，分支的数量取决于分裂属性有多少个不同的取值

• 可以是二叉树或多叉树

算法步骤：

示例：


ID3算法（IterativeDichotomiser3迭代二叉树3代）是一个由RossQuinlan发明的用于决策树的算法。可以归纳为以下几点：

1. 使用所有没有使用的属性并计算与之相关的样本熵值
2. 选取其中熵值最小的属性
3. 生成包含该属性的节点
4. ID3算法生成的是多叉树模型，分支数量取决于分裂属性的不同取值

D3算法对数据的要求：

• 所有属性必须为离散量；
• 所有的训练例的所有属性必须有一个明确的值；
• 相同的因素必须得到相同的结论且训练例必须唯一。

损失函数：

2） C4.5：使用信息增益比作为选择特征的准则

• 信息增益比=信息增益 / 划分前的熵

• 信息增益相对于信息增益比的一个缺点：信息增益总是偏向于选择取值较多的属性。信息增益比在此基础上增加了一个罚项，解决了这个问题。

• C4.5克服了ID3仅仅能够处理离散属性的问题，以及信息增益偏向选择取值较多特征的问题，使用信息增益比来选择特征。

• 可以是二叉树或多叉树

3）CART（分类与回归树）：使用 Gini 指数作为选择特征的准则

CART与上述两者不同的地方在于，CART生成的树必须是二叉树，也就是无论回归还是分类，无论特征离散还是连续，无论属性取值有多个还是两个，内部节点只能根据属性进行二分。

• CART作为回归树：使用平方误差最小准则来选择特征并进行划分，也叫最小二乘回归树。

• CART作为分类树：使用Gini指数最小化准则来选择特征并进行划分

  • Gini 指数表示集合的不确定性，或者是不纯度。基尼指数越大，集合不确定性越高，不纯度也越大。这一点和熵类似。另一种理解基尼指数的思路是，基尼指数是为了最小化误分类的概率。
  • Gini指数和熵的区别：Gini指数计算不需要对数运算，更加高效，且更偏向于连续属性，熵更偏向于离散属性。

分类树：

回归树：

停止条件：

1. 直到每个叶子节点都只有一种类型的记录时停止，（这种方式很容易过拟合）

2. 另一种时当叶子节点的记录树小于一定的阈值或者节点的信息增益小于一定的阈值时停止

关于特征值与目标值：

1. 特征离散 目标值离散：可以使用ID3，cart

2. 特征连续 目标值离散：将连续的特征离散化 可以使用ID3，cart

3. 特征离散 目标值连续

决策树的分类与回归：

• 分类树 ：输出叶子节点中所属类别最多的那一类

• 回归树 ：输出叶子节点中各个样本值的平均值

解决决策树的过拟合：

1. 剪枝

• 前置剪枝：在分裂节点的时候设计比较苛刻的条件，如不满足则直接停止分裂（这样干决策树无法到最优，也无法得到比较好的效果）

• 后置剪枝：在树建立完之后，用单个节点代替子树，节点的分类采用子树中主要的分类（这种方法比较浪费前面的建立过程）

1. 交叉验证

2. 随机森林

决策树的优缺点：

• 优点：

• 计算量简单，可解释性强，比较适合处理有缺失属性值的样本，能够处理不相关的特征；

• 缺点：

• 单颗决策树分类能力弱，并且对连续值变量难以处理；

• 容易过拟合（后续出现了随机森林，减小了过拟合现象）；

总结：

决策树算法主要包括三个部分：特征选择、树的生成、树的剪枝。常用算法有 ID3、C4.5、CART。

• 特征选择：特征选择的目的是选取能够对训练集分类的特征。特征选择的关键是准则：信息增益、信息增益比、Gini 指数；

• 决策树的生成：通常是利用信息增益最大、信息增益比最大、Gini 指数最小作为特征选择的准则。从根节点开始，递归的生成决策树。相当于是不断选取局部最优特征，或将训练集分割为基本能够正确分类的子集；

• 决策树的剪枝：决策树的剪枝是为了防止树的过拟合，增强其泛化能力。包括预剪枝和后剪枝。

示例1：

假设我们有一个数据集，在一个深度为 6 的决策树的帮助下，它可以使用 100% 的精确度被训练。则当深度为4时，将有高偏差和低方差。

解析：

如果在这样的数据中利用深度为 4 的决策树进行拟合，这意味着其更有可能与数据欠拟合。因此，在欠拟合的情况下，将获得高偏差和低方差。

示例2：

决策树的父节点和子节点的熵的大小关系是什么？——根据具体情况而定，父节点不一定大于或小于子节点

解析：

假设一个父节点有2正3负样本，进一步分裂情况1：两个叶节点（2正，3负）；情况2：两个叶节点（1正1负，1正2负）。分别看下情况1和情况2，分裂前后确实都有信息增益，但是两种情况里不是每一个叶节点都比父节点的熵小。

Boosting和Bagging

（1）随机森林
　　随机森林改变了决策树容易过拟合的问题，这主要是由两个操作所优化的：

1）Boostrap从袋内有放回的抽取样本值

2）每次随机抽取一定数量的特征（通常为sqr(n)）。
　　分类问题：采用Bagging投票的方式选择类别频次最高的
　　回归问题：直接取每颗树结果的平均值。

（2）Boosting之AdaBoost

Boosting的本质实际上是一个加法模型，通过改变训练样本权重学习多个分类器并进行一些线性组合。而Adaboost就是加法模型+指数损失函数+前项分布算法。Adaboost就是从弱分类器出发反复训练，在其中不断调整数据权重或者是概率分布，同时提高前一轮被弱分类器误分的样本的权值。最后用分类器进行投票表决（但是分类器的重要性不同）。

（3）Boosting之GBDT

将基分类器变成二叉树，回归用二叉回归树，分类用二叉分类树。和上面的Adaboost相比，回归树的损失函数为平方损失，同样可以用指数损失函数定义分类问题。但是对于一般损失函数怎么计算呢？GBDT（梯度提升决策树）是为了解决一般损失函数的优化问题，方法是用损失函数的负梯度在当前模型的值来模拟回归问题中残差的近似值。

注：由于GBDT很容易出现过拟合的问题，所以推荐的GBDT深度不要超过6，而随机森林可以在15以上。

（4）Xgboost

这个工具主要有以下几个特点：

• 支持线性分类器

• 可以自定义损失函数，并且可以用二阶偏导

• 加入了正则化项：叶节点数、每个叶节点输出score的L2-norm

• 支持特征抽样

• 在一定情况下支持并行，只有在建树的阶段才会用到，每个节点可以并行的寻找分裂特征。

GBDT/XGboost

随机森林

8、过拟合

在其它条件不变的前提下，以下哪种做法容易引起机器学习中的过拟合问题（D ）

• A 增加训练集数量
• B 减少神经网络隐藏层节点数
• C 删除稀疏的特征
• D SVM算法中使用高斯核/RBF核代替

机器学习中发生过拟合的主要原因有：

（1）使用过于复杂的模型；
（2）数据噪声较大；
（3）训练数据少。

对应的降低过拟合的方法有：

（1）简化模型假设，或者使用惩罚项限制模型复杂度；
（2）进行数据清洗，减少噪声；
（3）收集更多训练数据。

数据清洗中，处理缺失值的方法有两种：

一、删除法：

1. 删除观察样本
2. 删除变量：当某个变量缺失值较多且对研究目标影响不大时，可以将整个变量整体删除
3. 使用完整原始数据分析：当数据存在较多缺失而其原始数据完整时，可以使用原始数据替代现有数据进行分析
4. 改变权重：当删除缺失数据会改变数据结构时，通过对完整数据按照不同的权重进行加权，可以降低删除缺失数据带来的偏差

二、查补法：均值插补、回归插补、抽样填补等

高斯核的使用增加了模型复杂度，容易引起过拟合。选择合适的核函数以及软边缘参数C就是训练SVM的重要因素。一般来讲，核函数越复杂，模型越偏向于过拟合；C越大模型越偏向于过拟合，反之则拟合不足。

9、异方差性

如果线性回归模型中的随机误差存在异方差性，那么参数的OLS估计量是（无偏的，非有效的）

由高斯—马尔可夫定理，在给定经典线性回归的假定下，最小二乘估计量是具有最小方差的线性无偏估计量。

根据证明过程可知，随机误差中存在异方差性不会影响其无偏性，而有效性证明中涉及同方差性，即异方差会影响参数OLS估计量的有效性。

10、Fisher线性判别函数/PCA

PCA：

PCA方法是一种简单的线性降维（特征提取）方法，这里不讨论其数学推导。基本步骤如下：

1）计算样本集合X（D维）的均值矢量mu和协方差矩阵sigma；

2）计算sigma的特征值和特征矢量，按特征值降序排列；

3）选择前d个特征矢量构成矩阵E；

4）D维的矢量x可以转换为d维的矢量x’：x’ = ET（x - mu）。

为什么协方差矩阵的特征向量就是k维理想的特征：最大方差理论、最小误差理论来解释

最大方差理论：

信号处理中，认为信号具有较大的方差，噪声具有较小的方差，信噪比就是信号和噪声的方差比，越大越好，所以选择的第一条坐标轴就是覆盖数据最大方差的位置，第二条坐标轴就是垂直于最大第一条轴的方向。所以我们认为最好的选取的k维特征是将n维样本点转化为k维之后，每一维上的样本方差都很大，并且k维新的特征是正交的。

最小平方误差理论：
最初学习线性回归，目的是求得一个线性函数，使得其能够最佳拟合样本点，也就是最小化平方误差，来获得最佳线性函数。

PCA方法等价于在原特征空间里建立了一个新坐标系，该坐标系的原点放在均值mu的位置，前d个特征矢量就是其基矢量。由于协方差矩阵sigma为实对称矩阵，并且半正定，那么其特征值都会大于等于零，特征矢量两两正交。所以新坐标系是直角坐标系。也就是说，新坐标系下不同特征之间不相关（但不一定独立）。可以证明，经过降维之后的样本集合的协方差矩阵是对角阵。

对于计算机来说，当协方差矩阵sigma非常大时，直接求其特征值和特征矢量开销很大。这时可以考虑用奇异值分解（SVD）来计算。在进行SVD之前，需要对样本集合预处理，也就是机器学习中所谓的Feature Scaling，使样本集合里的每一维特征的均值为0，方差为1。预处理之后，协方差矩阵sigma即为XTX。而X的奇异值分解，X = UDVT，V的列就是XXT的特征向量，D为对角阵，值为对应特征向量的算数平方根。

PCA方法是无监督的，没有考虑样本的标签。小的特征值只是说明相应维度上样本分布的方差小，并不代表它对分类的作用小。某些极端情况下，PCA舍去的特征可能恰恰包含了对分类极其重要的信息。基于Fisher准则的可分性分析就是使用训练样本的标签来降维，最大程度地保留可分性信息。

PCA理论意义：

将n个特征降维到k个，可以用来做数据压缩，或图像压缩，经过PCA处理后，二维数据投影到一维上可以由以下几种情况：

左图的效果好，一方面是投影后方差最大，另一方面是点到直线的距离平方和最小，而且直线过样本点的中心点。

PCA得到的k个坐标轴实际上是k个特征向量，由于协方差矩阵对称，因此k个特征向量正交。PCA所做的变换就是将原始的n维样本点，投影到k个正交的坐标系当中去，丢弃其他维度的信息。

PCA实例：

假设得到2维数据如下，其中每行表示一个样本，x和y表示每个样本的2个特征：

1、去掉每列的均值，也就是对所有样本的每个特征分别求均值，去掉

2、求特征的协方差矩阵

此处只有x和y，求得协方差矩阵：

对角线上分别为x和y的方差，非对角线上是协方差，协方差大于0表示其是正相关的。

3、求协方差的特征值和特征向量

上面是两个特征值，下面是对应的特征向量，这里的特征向量都归一化为单位向量。

4、将特征值按照从大到小的顺序排序，选择其中最大的k个，然后将其对应的k个特征向量分别作为列向量组成特征向量矩阵。

这里特征值只有两个，选择其中最大的那个，对应的特征向量是（−0.677,−0.735）T

5、将样本点投影到选取的特征向量上

假设样例数量为m，特征数量为n，减去均值的样本矩阵为DataAdjust(mn)，协方差矩阵为nn，选取的k个特征向量组成的矩阵为EigenVector(n*k)，那么投影后的矩阵数据FinalData为：

FinalData(m∗n)=DataAdjust(m∗n)×EigenVector(n∗k)

此处得到的结果：

PCA特点：无参数限制，不需要人为的设定参数，或根据经验模型对计算进行干预，最后的结果和数据有关，与用户无关，但是这个特点使得PCA无法使用已有的先验知识，是无监督的降维方法。

Fisher线性判别分析FLD（也叫LDA）：

我们已知在很多情况下，准确的估计概率密度模型并非易事，在特征空间维数较高和样本数量较少的情况下尤为明显。实际上模式识别的目的是在特征空间中设法找到两类或多类的分类面，估计概率密度函数并不是我们的目的。

前文已经提到，正态分布情况下，贝叶斯决策的最优分类面是线性的或者是二次函数形式的，本文则着重讨论线性情况下的一类判别准则——Fisher判别准则。

Fisher线性判别（Fisher Linear Discrimination，FLD），也称线性判别式分析(Linear Discriminant Analysis, LDA)。FLD是基于样本类别进行整体特征提取的有效方法。它在使用PCA方法进行降维的基础上考虑到训练样本的类间信息。FLD的基本原理就是找到一个最合适的投影轴,使各类样本在该轴上投影之间的距离尽可能远,而每一类内的样本的投影尽可能紧凑,从而使分类效果达到最佳,即在最大化类间距离的同时最小化类内距离。FLD方法在进行图像整体特征提取方面有着广泛的应用。

线性判别简介：

• 表达式：g(x)=wT+w0​其中x是d维特征向量，w称为权向量，决定分类面的方向（对应二维空间的斜率），w0​是个常数，称为阈权值（对应二维空间的截距）：x=[x1​,x2​,...,xd​]T,w=[w1​,w2​,...,wd​]T

Fisher线性判别函数求解过程：将M维特征矢量投影在一维空间中进行求解

• Fisher线性判别函数是将多维空间中的特征矢量投影到一条直线上，也就是把维数压缩到一维，使得在投影线上最易于分类。

什么是最易于分类的投影面：

• 投影后两类相隔尽可能远，而对同一类的样本又尽可能聚集。

Fisher准则函数：

• 寻找这条最优直线的准则是Fisher准则：两类样本在一维空间的投影满足类内尽可能密集，类间尽可能分开，也就是投影后两类间样本均值之差尽可能大，类内部方差尽可能小