百面机器学习

• 百面机器学习
  • 1. 特征工程
    • 1.1. 特征归一化/正则化（Normalization）
    • 1.2. 类别型特征（Categorical Feature）
    • 1.3. 高维组合特征的处理
    • 1.4. 组合特征
    • 1.5. 文本表示模型
    • 1.6. Word2Vec
    • 1.7. 图像数据不足时的处理方法
  • 2. 模型评估
    • 2.1. 评估指标的局限性
    • 2.2. ROC 曲线
    • 2.3. 余弦距离的应用
    • 2.4. A/B 测试
    • 2.5. 模型评估的方法
    • 2.6. 超参数调整优
    • 2.7. 过拟合与欠拟合
  • 3. 经典算法
    • 3.1. 支持向量机
    • 3.2. 逻辑回归
    • 3.3. 决策树
  • 4. 降维
    • 4.1. PCA 最大方差理论
    • 4.2. 线性判别分析（LDA）
  • 5. 非监督学习
    • 5.1. K-Means 聚类
    • 5.2. 高斯混合模型（GMM）
    • 5.3. 自组织映射神经网络（SOM）
    • 5.4. 聚类算法的评估
  • 6. 采样
    • 6.1. 采样的作用
    • 6.2. 高斯分布的采样
  • 前向神经网络
    • 训练技巧

1. 特征工程

在机器学习中，数据和特征是“米”，模型和算法是“巧妇”。

特征工程，是对原始数据进行一系列工程处理，将其提炼为特征，作为输入供算法和模型使用。

实际工作中，特征工程旨在去除原始数据中的杂质和冗余，设计更高的特征以刻画求解的问题和预测模型之间的关系。

1.1. 特征归一化/正则化（Normalization）

消除数据特征之间的量纲影响，使得不同指标之间具有可比性。使各指标处于同一个数值量级，以便进行分析。

为什么要对数值类型的特征做归一化？常见的归一化有哪些方式？

对数值类型的特征做归一化可以将所有的特征统一到一个大致相同的数值区间内，常用的方法主要有以下两种：

1. 线性函数归一化（Min-Max Scaling）

对原始数据映射到 $[0,1]$

$$X_{norm}=\frac{X-X_{min}}{X_{max}-X_{min}}$$

2. 零值归一化（Z-Score Normalization）

将原始数据映射到均值为0、标准差为1的分布上。

$$z=\frac{x-\mu }{\sigma }$$

不同的特征如果取值范围不同，那么在学习速率相同的情况下，会出现更新速度不同的现象，需要迭代多次才能找到较优解。一般，需要通过梯度下降法求解的模型通常是需要归一化的，包括线性回归、逻辑回归、支持向量机、神经网络等模型。但是，对于决策树模型则并不适用。比如C4.5，决策树在进行节点分裂时，主要依据数据集关于特征信息的增益比，这和特征是否经过归一化无关。因为归一化不会改变样本在特征上的信息增益。

1.2. 类别型特征（Categorical Feature）

主要指性别（男、女），血型（A、B、AB、O）等只在有限选项内取值的特征。 原始输入通常是字符串形式，除了决策树等少数模型能直接处理字符串形式的输入，一般类别特征必须转换成数值型特征才能正确工作。

主要的方式包括：

• 序号编码（Ordinal Encoding）
• 独热变化（One-hot Encoding）
• 二进制编码（Binary Encoding）

在对数据进行预处理时，应该怎样处理类别型特征？

1. 序号编码

通常用于处理类别间具有大小关系的数据。按照大小关系对类别特征赋予一个数值ID，转换后依然保留大小关系。

2. 独热编码

通常用于处理类别间不由有大小关系的特征。需要注意的是：

• 使用稀疏向量来节省空间。
• 配合特征选择来降低维度。

高维空间下两点之间的距离很难得到有效地衡量，在逻辑回归模型中，参数的数量会随着维度的增高而增加，容易过拟合。通常只有部分维度对分类、预测有帮助。

3. 二进制编码

利用二进制对ID 进行哈希映射，且维度少于独热编码。

4. 其他编码方式

• Helmert Constrast
• Sum Constrast
• Polynomial Constrast
• Backward Difference Constrast

1.3. 高维组合特征的处理

为了提高复杂关系的拟合能力，在特征工程中，经常会把一阶离散特征两两组合，构成高阶组合特征。

$$Y=\sigma (\sum _i\sum _j{w}_{ij}<x_i,x_j>)$$

$w_{ij}$ 的维度等于 $|x_i|\cdot |x_j|$，这对于高维参数几乎无法学习，这种情况下，一种方法是，将用户和物品分别用$k$维的低维向量表示，这样 $w_{ij}=x_i^{\prime }\cdot x_j^{\prime }$，等价于矩阵分解。

1.4. 组合特征

简单地两两组合，依然容易存在参数过多、过拟合等问题，并且并不是所有的特征组合都是有意义的。因此，需要一种有效的方法来帮助我们找到应该对哪些特征进行组合。

有效地找到特征组合，可以参考决策树，根据原始输入和标签构造决策树，每一条从根节点到叶节点的路径，都可以看作是一种组合。可以采用梯度提升决策树来构造。该方法的思想是，每次都在构建的决策树残差上构建下一棵决策树。

1.5. 文本表示模型

• 词袋模型（Bag of Words）TF-IDF（Term Frequency-Inverse Document Frequency）
• 主题模型（Topic Model）
• 词嵌入模型（Word Embedding）

词袋模型：将每篇文章看成一个袋子词，并忽略每个词出现的顺序。这个词袋向量的每一个维度代表一个单词，而该维度的权重反映了这个词在原文中的重要程度。常用TD-IDF 来计算权重

$$TF-IDF(t,d)=TF(t,d)\times IDF(t)$$

$TF(t,d)$ 表示单词$t$在文档$d$中出现的平率，$IDF(t)$ 是逆文档频率，用来衡量单词$t$对表达语义的重要性

$$IDF(t)=log\frac{文章总数}{包含t的文章数+1}$$

如果一个词在非常多的文章里面都出现，那么它可能是一个比较通用的词汇，对于区分某篇文章特殊语义的贡献较小，因此需要对权重进行惩罚。

N-Gram模型：可以连续出现的$n$个词组成的词组（$N-gram$），也作为一个单独的特征向量放到向量表示中去，构成这个模型。在实际应用中，一般会对单词进行词干抽取（Word Stemming）处理，即将不同词性的单词统一成为同一词干的形式。

主题模型：主题模型用于从文本库中发现有代表性的主题（得到每个主题上面词的分布特性），并且能够计算出每篇文章的主题分布。

词嵌入与深度学习模型：词嵌入是一类将词向量化的模型的统称，核心思想是将每个词都映射成低维空间（50~300）上的一个稠密向量。K 维空间的每一维也可以看作一个隐含的主题，只不过不像主题模型中的主题那样直观。

通常，如果仅仅把词嵌入矩阵作为原文本的表示特征输入到机器学习模型中，很难得到令人满意的结果。因此，还需要在此基础上加工出更高层的特征。深度学习的结构在文本处理中取得了很好的效果，主要是由于它们能够更好地对文本进行建模，抽取出更高一些的语义特征。另一方面，也减少了网络中待学习的参数，提高了训练的速度也降低了过拟合的风险。

1.6. Word2Vec

实际上是一种浅层的神经网络模型，一般有CBOW 和 Skip-gram 两种网络结构。

• CBOW：目标是根据上下文出现的词频来预测当前词的生成概率
• Skip-gram：根据当前词来预测上下文各词的生成概率

这两个模型都可由输入层（独热）、映射层（隐含层，CBOW 中还需要将各隐含单元求和。）和输出层组成。

输出的每一个维度和词汇表中的一个单词相对应。最后，对输出层向量应用Softmax激活函数，可以计算出每个单词的生成概率。

Input-Hidden ($N\times K$)

Hidden-Output （$K\times N$）

可以通过反向传播算法实现，每次迭代时，将权重沿梯度更优的方向进行一小步。但是，由于softmax 中存在归一化，推导出来的迭代公式需要对词汇表中的所有单词进行遍历，使得迭代的过程非常缓慢。由此，产生了 Hierarchical Softmax 和 Negative Sampling 两种改进方法。

• 与 LDA（隐狄利克雷模型）的区别和联系

LDA：利用文档中单词的共现关系来对单词按主题聚类，也可理解为对“文档-单词”矩阵进行分解，得到“文档-主题”和“主题-单词”的两个概率分布。

Word2Vec：对“上下文-单词”矩阵进行分解。其中上下文有周围的几个单词组成，由此得到的词向量表示等多地融入了上下文共现的特征。

也就是说，如果两个单词所对应的Word2Vec向量相似度较高，那么它们很可能经常出现在同样的上下文中。

主题模型可以通过一定的结构调整，基于“上下文-单词”矩阵进行主题推理，词嵌入方法也可以根据“文档-单词”矩阵学习出词的隐含向量表示。

主题模型和词嵌入两类方法的不同在于：模型本身

1. 主题模型是一种基于概率图模型的生成模型，其似然函数可以些成若干条件概率连乘的形式，其中包括需要推测的隐含变量（主题）；
2. 词嵌入模型一般表达为神经网络的形式，似然函数定义在网络的输出之上，需要通过学习网络的权重以得到单词的稠密向量表示。

1.7. 图像数据不足时的处理方法

（可能会过拟合）

迁移学习、生成对抗网络、上采样技术、数据扩充

一个模型所能提供的信息一般来源于：

1. 训练数据中蕴含的信息
2. 模型的形成过程中（构造、学习、推理），人提供的先验信息

训练数据不足，则说明从原始数据中获取的信息比较少。那就需要更多的先验信息。

• 用在模型上：结构、条件假设、添加约束
• 用在数据上：调整、变换、扩展等

手段：

1. 基于模型方法（降低过拟合风险）：
   • 简化模型（非线性转化为线性）
   • 添加约束项以缩小假设空间（L1/L2 正则项）
   • 集成学习
   • Dropout 超参数
2. 基于数据
   • 扩充数据（Data Augmentation），基于一些先验知识，在保持特定信息的前提下，对原始数据进行适当变换。
     • 随机旋转、平移、缩放、裁剪、填充、左右翻转等
     • 在图像中的像素添加噪声扰动，比如椒盐噪声、高斯白噪声
     • 颜色变换
     • 改变图像的亮度、清晰度、对比度、锐度等
3. 先对图像进行特征抽取，然后在图像的特征空间内进行变换，利用一些数据扩充或者上采样技术，例如SMOTE(Synthetic Minority Over-sampling Technique)算法。
4. 生成模型：GAN
5. 迁移模型，比如借用一个在大规模数据集上预训练号的通用模型，并在针对目标任务的小数据集上进行微调。

2. 模型评估

只有选择和问题相匹配的评估方法，才能快速地发现模型选择或训练过程中出现的问题。

1. 离线评估
2. 在线评估

2.1. 评估指标的局限性

准确率的局限

$$Accuracy=\frac{n_{correct}}{n_{total}}$$

当负样本占99%时，把所有样本都预测为负样本，也可以获得99%的准确率，这是不合理的。

当不同类别的样本比例非常不均衡时，占比大的类别往往成为影响准确率的重要因素。

可以使用平均准确率作为模型评估的指标。

精确率与召回率的权衡

• 精确率：分类正确的正样本个数占分类其判定为正样本的个数的比例；通过将更有把握时才把样本预测为正样本来提高。往往会漏掉很多没有把握的正样本，导致recall 指下降
• 召回率：分类正确的正样本个数占真正正样本个数的比例

为了综合评估一个排序模型的好坏，不仅要看模型在不同 Top N 的 Precision@N 和 Recall@N，并且绘制 P-R 曲线。

F1 值是精准率和召回率的调和平均值：

$$F1=\frac{2\times precision\times recall}{precision+recall}$$

平方根误差的“意外”

对于回归模型来预测某部美剧的流量趋势，但无论采用哪种回归模型，得到的 RMSE 指标都非常高。但实际上，95% 的时间区间内的预测误差率都小于1%，为什么？

$$RMSE=\sqrt{\frac{{\sum }_{i=1}^n(y_i-{\hat{y}}_i{)}^2}{n}}$$

一般用于反映回归模型预测值与真实值的偏离程度。但如果实际问题中，存在个别偏离程度非常大的离群点（outlier）时，即使离群点数量非常少，也会让RMSE指标变得非常差。很可能，其他5% 时间区间内存在非常严重的离群点。比如流量特别小的美剧，刚上映的美剧或者刚获奖的。

解决方案：

1. 如果认定离群点时噪声的话，可以在数据预处理时把噪声过滤掉。
2. 如果离群点不是噪声，需要进一步提高模型的预测能力，将离群点的产生机制建模进去。
3. 找一个更合适的指标来评估该模型。比如平均绝对百分比误差（MAPE）

$$MAPE=\sum _{i=1}^n\left|\frac{y_i-{\hat{y}}_i}{y_i}\right|\times \frac{100}{n}$$

相对于 RMSE，MAPE相当于把每个点的误差进行了归一化，降低了个别离群点带来的绝对误差。

每个评估值都有其价值，如果只从单一的评估指标出发去评估模型，往往会得出片面甚至错误的结论；通过一组互补的指标去评估模型，可以更好地发现并解决模型存在的问题。

2.2. ROC 曲线

常常作为评估二值分类器最重要的指标之一。

什么是ROC曲线？

Receiver Operating Characteristic Curve 受试者工作特性曲线，起源于军事领域，在医学领域应用甚广。

• 横座标：假阳性率（False Positive Rate, FPR） FPR = FP/ N
• 纵座标：真阳性率（True Positive Ratem TPR） TPR = TP/P

如何绘制？

ROC 曲线是通过不断移动分类器的“截断点”来生成曲线上的一组关键点的。

• 截断点：区分正负预测结果的阈值。

实用步骤：

1. 根据样本标签统计出正负样本数量（P,N）把横轴刻度间隔设置为 1/N，纵轴为 1/P ，再根据模型输出的预测概率对样本进行从高到低的排序
2. 遍历样本，同时从ROC零点开始绘制。每遇到一个正样本就沿着纵轴防线绘制一个刻度区间，遇到负样本就沿着横轴绘制一个刻度区间。直到遍历完成。

如何计算 AUC ？

Area Under Curve 是ROC曲线下的面积大小，能够反映模型性能。 AUC 越大，说明分类器越可能把真正的正样本排在前面，分类性能越好。

ROC 和 P-R 相比又什么特点？

• 当负样本分布发生变化时，ROC曲线的形状能基本保持不变，而P-R 曲线的形状一般会发生剧烈变化。

在很多实际问题中，正负样本数量往往很不均衡，比如计算广告领域经常涉及转化率模型，正样本的数量往往是负样本的1/1000 甚至是 1/10000。选择不同的测试集合，P-R 曲线的变化就会非常大。

ROC的应用更广泛，于排序、推荐、广告。如果希望在特定数据集上的表现，那么实用 P-R 模型则更能够直观反映性能。

2.3. 余弦距离的应用

评估样本距离也是定义优化目标和训练方法的基础。

余弦相似度的取值范围是$[-1,1]$，1减去余弦相似度即为余弦距离。

什么场合用余弦相似度，什么场合用欧式距离？

关于向量$A$和$B$，其余弦相似度定义为

$$cos(A,B)=\frac{A\cdot B}{||A|{|}_2||B|{|}_2}$$

即两个向量夹角的余弦，关注的是向量之间的角度关系，并不关心他们的绝对大小。

当一对文本相似度的长度差距很大、但内容相近时，如果使用词频或词向量作为特征，他们的欧式距离可能很大，但夹角可能很小，因而相似度很高。

文本、图像、视频等领域，研究的对象特征维度往往很高，余弦相似度在高维情况下依然保持相同为1，正交为0，相反为-1。

一般来说

• $||A-B|{|}_2$ 表示欧式距离（强调绝对差异）
• $\cos (A,B)$ 表示余弦相似度
• $dist(A,B)=1-\cos (A,B)$ 表示余弦距离（强调相对差异）

余弦距离，并不是一个严格定义的距离。

• 正定性：满足，$1-\cos \theta =\frac{||A|{|}_2||B|{|}_2-AB}{||A|{|}_2||B|{|}_2}\ge 0$
• 对称性：满足
• 三角不等式，不一定。$dist(A,B)=\frac{1}{2}||A-B|{|}^2$

KL 距离，也叫相对熵，不满足对称性和三角不等式

2.4. A/B 测试

A/B 测试是常用的验证新功能、新模块、新产品是否有提升的方法。常常是机器学习中验证模型最终效果的主要手段。

需要在线A/B测试的原因：

1. 离线评估无法完全消除模型过拟合的影响，因此，得出的结果无法替代线上评估的结果
2. 离线评估无法完全还原线上的工作环境。离线评估往往不会考虑线上环境的延迟、数据丢失、标签数据缺失等情况。因此，离线评估的结果是理想工程环境下的结果。
3. 线上系统的某些商业指标在离线评估中无法计算。离线评估（ROC曲线，P-R曲线等）往往针对模型本身，而商业指标（用户点击率，留存时长，PV访问量等），往往无法评估。

如何进行线上A/B测试：

• 进行用户分桶，实验组和对照组，样本的独立性和采样方式的无偏性，确保同一用户每次只能分到同一个桶中，在分桶的过程中选取的 user_id 需要是一个随机数。

划分对照组和实验组：

• 无偏
• 正确

2.5. 模型评估的方法

1. Holdout 检验

   • 将原始样本集合随机划分成训练集和验证集两个部分。
   • 缺点：验证集上计算出来的最后评估指标与原始分组有很大关系。

2. 交叉检验

   • k-fold 交叉验证：将全部样本划分成 $k$ 个大小相等的样本，一次遍历这 $k$ 个子集，每次把当前子集作为验证集，其余所有子集作为训练集。最后把 $k$ 次评估指标的平均值作为最终的评估指标。常常 $k=10$
   • 留一验证：每次留下1个样本作为验证集，其余样本作为测试集。n次验证后，取平均值作为最终的评估指标。

3. 自助法

   • 基于自助采样的检验方法，对于总数为n的样本集合，进行n次有放回的随机抽样，得到大小为n的训练集。采样过程中，有的样本被重复采样，有的样本没有被抽出，没有被抽出的作为验证集。
   • 当对n个样本进行n次自助采样，当$n\to \infty$，一个样本未被抽中的概率为 ${\lim }_{n\to \infty }(1-\frac{1}{n}{)}^n={\lim }_{n\to \infty }\frac{1}{(1+\frac{1}{n-1}{)}^n}=\frac{1}{e}\approx 0.368$

2.6. 超参数调整优

目标函数，搜索范围，算法的其他参数，例如搜索步长等。

• 网格搜索：最简单，查找搜索范围内所有的点来确定最优值。耗时
• 随机搜索：与网格搜索类似，不再搜索上下界之间的所有值，而是在搜索范围内随机选取样本点。依据是，如果样本点集足够大，那么通过随机采样也能大概率地找到全局最优。
• 贝叶斯优化：前面两种搜索会在测试新点时，忽略前一点的信息，而贝叶斯优化则充分利用之间的信息。通过对目标函数形状进行学习。容易陷入局部最优。先给出一个经验分布，然后每一次使用新点测试时，利用这个信息来更新目标函数的先验分布，最后算法测试由后验分布给出的全局最值可能出现的位置点。

2.7. 过拟合与欠拟合

降低过拟合方法：

1. 获得更多数据，或者使用一定规则来扩充训练数据。
2. 降低模型复杂度，比如网络层数，神经元个数等，决策树低树深度、进行剪纸等
3. 正则化方法，正则约束，比如将权重值的大小加入到损失函数（L2: $C=C_0+\frac{\lambda }{2n}{\sum }_i{w}_i^2$）
4. 集成学习方法。

降低欠拟合的方法：

1. 添加新特征：挖掘上下文特征，ID类特征，组合特征等新的特征，往往能取得更好地的效果。很多工具可以帮助这个步骤，例如因子分解机，梯度提升决策树，Deep-crossing等方法可以成为丰富特征的方法。
2. 增加模型复杂度。在线性模型中添加高次项，在神经网络模型中增加网络层数或神经元个数等。
3. 减小正则化系数

3. 经典算法

3.1. 支持向量机

SMO（Sequential Minimal Optimization）算法

对于任意线性可分的两组点，它们在SVM分类的超平面上的投影都是线性不可分的。

SVM 的预测公式：

$$f(x)=\sum _{i=1}^m{a}_i{y}^{(i)}K(x^{(i)},x)+b$$

3.2. 逻辑回归

1. 逻辑回归：
   • 分类问题
   • 因变量取值是一个二元分布
   • 学习得出的是 $E[y|x;\theta ]$，因变量的期望
   • 基于此期望来处理预测分类问题
   • 假设因变量 y 服从伯努利分布
2. 线性回归：
   • 回归问题
   • 求解的是对真实函数的一个近似。
   • 假设因变量 y 服从高斯分布

逻辑回归可以看作是对于 $y=1|x$ 这一事件的对数几率 $\log \frac{p}{1-p}$ 的线性回归。

都可以看作广义线性模型，都使用了极大似然估计来对训练样本进行建模。

逻辑回归用于多标签的分类问题时的处理方法：

1. 一个样本对应一个标签：可以假设每个样本属于不同标签的概率服从几何分布，使用多项逻辑回归(Softmax Regression)来进行分类。

$$h_{\theta }(x)=\left[\begin{array}{c}p(y=1|x;\theta )\\ p(y=2|x;\theta )\\ ⋮\\ p(y=k|x;\theta )\end{array}\right]=\frac{1}{{\sum }_{j=1}^k{e}^{{\theta }_j^{T}x}}\left[\begin{array}{c}{e}^{{\theta }_1^{T}x}\\ e^{{\theta }_2^{T}x}\\ ⋮\\ e^{{\theta }_k^{T}x}\end{array}\right]$$

多项逻辑回归具有参数冗余的特点，即 ${\theta }_1,{\theta }_2,\dots ,{\theta }_k$ 同时加减一个相同的向量后，预测结果不变。

多项逻辑回归实际上是二分类逻辑回归在多标签下的一种拓展。

2. 一个样本可能属于多个标签的情况时，可以训练 $k$ 个二分类的逻辑回归分类器。"Not hot dog"

3.3. 决策树

常用的算法及其启发式函数

1. ID3 —— 最大信息增益

对于样本集合 $D$ 类别数 $K$ 数据集 $D$ 的经验熵表示为：

$$H(D)=-\sum _{k=1}^K\frac{|C_k|}{|D|}{\log }_2\frac{|C_k|}{|D|}$$

$C_k$ 是样本集合 $D$ 中属于第 k 类的样本子集。

计算某个特征$A$ 的条件信息熵：

$$H(D|A)=\sum _{i=1}^k\frac{|D_i|}{|D|}H(D_i)$$

$D_i$ 表示 $D$ 中特征$A$取第$i$个值的样本子集。

于是信息增益可以表示为：

$$g(D,A)=H(D)-H(D|A)$$

• 实际中，决策树往往不能通过一个特征就完成构建，需要在经验熵非0的类别中继续生长。
• 会倾向于取值较多的特征，因为信息增益反映的是给定条件以后不确定性减少的程度，特征取值越多，意味着确定性更高，即条件熵越小，信息增益越大。但是，这种分类的泛化能力是非常弱的。
• 只能处理离散变量
• 只能用于分类
• 对特征缺失值比较敏感
• 可以在每个节点上产生出多叉分支，而且每个特征在层级之间不会复用
• 通过剪枝来权衡准确性和泛化能力

2. C4.5 —— 最大信息增益比

特征 $A$ 对于数据集 $D$ 的信息增益比定义：

$$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$$

其中，

$$H_A(D)=-\sum _{i=1}^n\frac{|D_i|}{|D|}{\log }_2\frac{|D_i|}{|D|}$$

为数据集$D$ 关于 $A$的取值熵。

• 对 ID3 进行优化，通过引入信息增益比，一定程度上对取值比较多的特征进行惩罚，避免ID3出现过拟合的特性。
• 能处理离散和连续的变量。
• 对数据排序后找到不同类别的不同分割线作为切分点，根据切分点把连续属性转化为布尔型，从而将连续变量转为多个取值区间的离散型变量。
• 只能用于分类
• 可以在每个节点上产生出多叉分支，而且每个特征在层级之间不会复用
• 通过剪枝来权衡准确性和泛化能力

3. CART（Classification and Regression Tree，分类回归树） —— 最大基尼指数

Gini 描述的是数据的纯度，与信息熵含义类似：

$$Gini(D)=1-\sum _{k=1}^n{\left(\frac{|C_k|}{|D|}\right)}^2$$

每一次迭代中，选择基尼指数最小的特征及其对应的切分点进行分类。与前面的算法不同的是，CART是一棵二叉树，采用二元切割法，每一步将数据按照特征A的取值切分成两份，分别进入左右子树。

• 能处理离散和连续的变量
• 构建时对每个特征进行二值划分，因此可以很好地适用于连续变量。
• 可以用于分类和回归
• 每个节点只会产生两个分支，每个层级之间不会复用。
• 直接利用全部数据发现所有可能的树结构进行对比。

如何对决策树进行剪枝？？

完全生长的决策树往往会过拟合。剪枝通常有两种方法：

1. 预剪枝：在生成决策树的过程中提前停止树的增长，而后剪枝，是在已生成的过拟合决策树上进行剪枝，得到简化版的剪枝决策树。
   • 在树中节点进行扩展之前，先计算当前洞儿划分能否带来模型泛化能力的提升，如果不能，则不再继续生长子树。此时，可能存在不同类别的样本同时存在于节点之中，按照多数投票的原则，判断该节点所属类别。
     • 当树达到一定深度的时候，停止树的生长
     • 当到达当前节点的样本数量小于某个阈值的时候，停止树的生长
     • 计算每次分裂对测试集的提升，当小于某个阈值，可以不用继续扩展
   • 思想直接，算法简单，效率高，适合解决大规模问题。但对如何准确地估计何时停止树的生长，不同问题差别大，存在欠拟合的风险。
2. 后剪枝：让算法生成一棵完全生长的决策树，然后从最底层向上计算是否剪枝。直接将子树删除，用一个叶子节点代替。该节点的类别由多数投票原则进行判断。可以得到泛化能力更好的树，但是时间开销会变大。
   • 常见的方法包括：
     1. 错误率降低剪枝（Reduced Error Pruning,REP）
     2. 悲观剪枝（Pessimistic Error Pruning,PEP）
     3. 代价复杂度剪枝（Cost Complexity Pruning,CCP）
     4. 最小误差剪枝（Minimum Error Pruning,MEP）
     5. 准则值剪枝（Critical Value Pruning,CVP）
     6. 最优剪枝（Optimal Pruning）
   • CCP：
     1. 从完整的决策树 $T_0$ 开始，生成一个子树序列 $\{T_0,T_1,\dots ,T_n\}$，其中 $T_{i+1}$ 由 $T_i$ 生成，$T_n$ 为根节点。
     2. 在子树序列中，根据真实误差，选择最佳的决策树。

4. 降维

4.1. PCA 最大方差理论

高维的向量数据包含很多冗余和噪声。我们可以通过降维的方法来寻找数据内部的特性，从而表达特征能力，降低训练复杂度。

如何定义主成分，如何设计目标函数使得降维达到主成分提取的目的，如何求解？

在信号处理的领域，我们认为信号具有较大方差，而噪声具有较小的方差，信号于噪声之比称为信噪比。信噪比越大表示数据的质量越好。

• 目标：最大化投影方差，也就是让数据在主轴上投影的方差最大。

• 求解方法：

  1. 对样本数据进行中心化处理
  2. 求样本协方差矩阵
  3. 对协方差矩阵进行特征值分解，将特征值从大到小排列。
  4. 取特征值前 $d$ 大对应的特征向量 ${\mathbf{\omega }}_1,{\mathbf{\omega }}_2,\dots ,{\mathbf{\omega }}_d$，通过以下映射将 $n$ 维样本映射到 $d$ 维
  $${\mathbf{x}}_i^{\prime }={\left[\begin{array}{cccc}{\mathbf{\omega }}_1^T{\mathbf{x}}_i& {\mathbf{\omega }}_2^T{\mathbf{x}}_i& \cdots & {\mathbf{\omega }}_d^T{\mathbf{x}}_i\end{array}\right]}^T$$

  新的 ${\mathbf{x}}_i^{\prime }$ 的第 $d$ 维就是 $x_i$ 在 $d$ 个主成分 ${\omega }_d$ 方向上的投影，通过选取最大的 $d$ 个特征值对应的特征向量，我们将方差最小的特征（噪声）抛弃。

• 扩展：KPCA (核主成分分析)

4.2. 线性判别分析（LDA）

Linear Discriminant Analysis 是一种有监督学习算法，同时经常被用来对数据进行降维。

PCA 中，算法没有考虑数据的标签，只是把原数据映射到一些方差比较大的方向上而已。

LDA 首先是为了分类服务的，因此只要找到一个投影方向 $\mathbf{\omega }$ 使得投影后的样本尽可能按照原始类别分开。每一类的内部方差要更小。

中心思想： 最大化类间距离和最小化类内距离。

但是，对数据的分布做了一些很强的假设，例如，每个类数据都是高斯分布、各个类的协方差相等。尽管这些假设在实际中并不一定完全满足，但 LDA 已被证明是非常有效的一种降维方法。主要是因为线性模型对于噪声的鲁棒性比较好，但由于模型简单，表达能力有一定局限性。可以通过引入核函数扩展 LDA 方法以处理分布较为复杂的数据。

5. 非监督学习

5.1. K-Means 聚类

• 基本思想：通过迭代方式寻找 $K$ 个簇的一种划分方案，使得各聚类结果对应的代价函数最小。
• 步骤：
  1. 数据预处理，归一化、离群点处理
  2. 随机选取 $K$ 个簇中心， ${\mu }_1^{(0)},{\mu }_2^{(0)},\dots ,{\mu }_k^{(0)}$
  3. 定义代价函数： $J(c,\mu )={\min }_{\mu }{\min }_c{\sum }_{i=1}^M||x_i-{\mu }_{c_i}|{|}^2$
  4. 令 $t=0,1,2,\dots$ 为迭代步数，重复下面过程直到 $J$收敛：
     • 对每个样本 $x_i$ 将其分配到距离最近的簇
     • 对每一类簇 $k$，重新计算该类簇的中心

$$\begin{gathered} c_i^{(t)}\leftarrow \arg \underset{k}{\min }||x_i-{\mu }_k^{(t)}|| \\ {\mu }_k^{(t+1)}\leftarrow \arg \underset{\mu }{\min }\sum _{i:c_i^{(t)}=k}||x_i-\mu |{|}^2 \end{gathered}$$

两个循环交替。

缺点： 受初值和离群点的影响，每次的结果不稳定，结果通常不是全局最优，而是局部最优，无法很好地解决数据簇分布差别比较大的情况。不太适用于离散分类。

• 需要人工预先确定初值 K，且该值和真实的数据分布未必吻合。
• K 均值只能收敛到局部最优，受初值影响大
• 易受到噪点的影响
• 样本点只能被划分到单一的类中

优点： 对于大数据集，非常高效，复杂度是 $O(NKt)$

调优：

1. 数据归一化和离群点处理。
2. 合理选择 $K$ 值：基于经验和多次实验结果。例如手肘法，可以尝试不同的 $K$ 值，并将不同的 $K$ 值所对应的损失函数画成折线。认为，拐点是最佳的 $K$ 值。还可以用 Gap Statistic 方法。表示为随机样本的损失和实际样本的损失之差。
3. 采用核函数：通过非线性映射，将输入空间中的数据点映射到高维的特征空间中，并在新的特征空间中进行聚类。

ISODATA 算法：当属于某个类别的样本数过少时，把该类去除；当属于某个类别的样本数量过多、分散程度较大时，把该类别分为两个子类别。

5.2. 高斯混合模型（GMM）

Gaussian Mixed Model 使用了 EM 算法进行迭代计算。假设每个簇的数据都是符合高斯分布的，当前数据呈现的分布就是各个簇分布值的叠加。

需要计算最佳均值 $\mu$，方差 $\Sigma$，权重 $\pi$。

1. E 步骤，根据当前的参数，计算每个点由某个分布模型生成的概率
2. M 步骤，使用E步骤估计的概率，改进每个分模型的均值、方差和权重

样本可以属于多个类。

5.3. 自组织映射神经网络（SOM）

Self-Organizing Map 是无监督学习方法中的一类重要方法，可以用作聚类、高维可视化、数据压缩、特征提取等多种用途。

5.4. 聚类算法的评估

常见数据簇特点：

• 以中心定义的数据簇
• 以密度定义的数据簇
• 以连通定义的数据簇
• 以概念定义的数据簇

测定聚类质量：

• 轮廓系数
• 均方根标准偏差

构造不同类型的数据集

• 观察聚类误差是否随着类别数量增加而单调变化
• 观察类误差对实际聚类结果的影响
• 观察临近数据簇的聚类准确性
• 观察数据密度具有较大差异的数据簇聚类效果

6. 采样

6.1. 采样的作用

采样是从特定的概率分布中抽取对应的样本点。

• 本质是对随机现象的模拟，根据给定的概率分布，来模拟产生一个对应的随机事件。可以让人们对随机事件及其产生过程有更直观的认识。
• 另一方面，采样得到的样本集也可以看作是一种非参数模型，即用较少量的样本（经验分布）来近似总体分布，并刻画总体分布中的不确定性。
• 采样其实也是一种信息降维，可以起到简化问题的作用。
• 对当前数据集进行重采样，可以充分利用已有数据集，挖掘更多信息。

很多模型由于结构复杂，含有隐变量等原因，导致对应的求解公式比较复杂，没有显式解析解，难以进行精确求解或推理。在这种状况下，可以利用采样方法进行随机模拟，从而对这些复杂模型进行近似求解或推理。

主要方法：

1. 自助法和刀切法
2. 对样本多次重复采样来估计统计量的偏差、方差等。
3. 利用重采样技术，可以在保持特定的信息下，有意识地改变样本的分布，以适应后续的模型训练和学习，例如用重采样来处理分类模型的训练和不均衡问题。

几乎所有的采样方法都是以均匀分布随机数作为基本操作。

若 $x,u$ 存在变换关系 $u=\phi (x)$，则它们的概率密度函数有如下关系：

$$p(u)|{\phi }^{\prime }(x)|=p(x)$$

因此，如果从目标分布 $p(x)$ 中不好采样 $x$，可以构造一个变换 $u=\phi (x)$ 使得变换后的分布 $p(u)$ 中采样 $u$ 比较容易，这样可以通过先对 $u$ 进行采样，然后通过反函数 $x={\phi }^{-1}(x)$ 来间接得到。如果是高维的随机向量，则 ${\phi }^{\prime }(x)$ 对应的 Jacobian 行列式。

特别的，在函数变换法中，如果变换关系 $\phi (\cdot )$ 是 $x$ 的累积分布函数的话，则得到所谓的逆变换采样。

如果，待采样的目标分布的累积分布函数的你函数无法求解或者不容易计算，则不适用于逆变换采样法。此时，可以构造一个容易采样的参考分布，先对参考分布进行采样，然后对得到的样本进行一定的后处理操作，使得最终的样本服从目标分布。

• 拒绝采样，对于目标分布 $p(x)$，选取一个容易采样的参考分布 $q(x)$，使得对于任意 $x$ 都有 $p(x)\le M\cdot q(x)$
  1. 从参考分布 $q(x)$ 中随机抽取一个样本 $x_i$
  2. 从均匀分布 $U(0,1)$ 产生
  3. 如果 $u_i<\frac{p(x_i)}{Mq(x_i)}$，则接受样本；否则拒绝
• 重要性采样，如果不需要计算函数积分，只想从目标分布 $p(x)$ 中采样出若干样本。先在参考分布 $q(x)$ 中抽取出 $N$ 个样本 $\{x_i\}$，然后按照它们对应的重要性权重 $\{w(x_i)\}$ 对这些样本进行重新采样，最终得到的样本服从目标分布 $p(x)$。

在实际应用中，如果是高维空间的随机向量，拒绝采样和重要性采样经常难以寻找合适的参考分布，采样效率低下，此时可以考虑马尔可夫蒙特卡洛采样法，常见的有 Metropolis-Hastings 采样法和吉布斯采样法。

6.2. 高斯分布的采样

如何对高斯分布进行采样？

首先，通过拉伸和平移得到标准正太分布。常见的采样方法有

1. 逆变换法
2. 拒绝采样
3. 重要性采样
4. 马尔科夫蒙特卡洛采样等

MCMC 采样法

在高维空间中，拒绝采样和重要性采样经常难以找到合适的参考分布，采样效率低下（样本的接受概率小或重要性权重低），此时可以考虑 MCMC 。起源于物理学。

基本思想：针对待采样的目标分布，构造一个马尔科夫链，使得马尔科夫链的平稳分布就是目标分布；然后，从任何一个初始状态出发，沿着马尔科夫链进行状态转移，最终得到的状态转移序列会收敛到目标分布，由此可以得到目标分布的一系列样本。

• Metropois-Hastings 采样法
• 吉布斯采样法：每次只对样本的一个维度进行采样和更新。对于目标分布 $p(x)$，其中 $x=(x_1,x_2,\dots ,x_d)$ 是多维向量，按如下过程进行采样：
  1. 随机选择初始状态 $x^{(0)}$
  2. 对于前一步产生的样本 $x^{(t-1)}$ 依次采样和更新每个维度的值，即依次抽取分量 $x_1^{(t)}\sim p(x_1|x_2^{(t-1)},x_3^{(t-1)},\dots ,x_d^{(t-1)})$，$x_2^{(t)}\sim p(x_2|x_1^{(t-1)},x_3^{(t-1)},\dots ,x_d^{(t-1)})$

MCMC 采样每一步都会产生一个样本，只是有时候这个样本与之前的样本一样而已。另外，MCMC采样法是在不断迭代过程中铸件收敛到平稳分布的，因此在实际应用中一般会对得到的样本序列进行 “burn-in” 处理，即截除掉序列中最开始的一部分样本，只保留后面的样本。

如果需要样本之间相互独立，可以同时运行多条马尔科夫链，这样选取出来的样本也是近似独立的。

前向神经网络

是一类网络模型的统称，包括

• 多层感知机
• 自编码机
• 限制玻尔兹曼机
• 卷积神经网络

MLP（多层感知机）

训练技巧

神经网络训练时，是否可以将全部参数初始化为0？

不可以，否则学习过程将永远无法打破对称性。初值的选择范围可以是 $\left(-\frac{1}{\sqrt{d}},\frac{1}{\sqrt{d}}\right)$ 的均匀分布，$d$ 是一个神经元接受的输入维度。

归一化的基本动机和原理是什么，在卷积神经网络中如何使用？

如果训练数据与测试数据的分布不同，将大大降低网络的泛化能力，因此我们需要在训练开始前对所有输入数据进行归一化处理。

可以通过批量归一化，可以看作在每一个输入和上一层输出之间加一个归一化层。增强了模型的泛化能力，同时也降低了模型的拟合能力。