数据

机器学习的根本还是数据，模型只是逼近数据规律的上限。数据的质量直接对应了最终的输出指标。

数据预处理

在讲解数据预处理方法之前，我们先梳理一下都有哪些类型的数据。数据的类型大约可以归纳为以下三种：

结构化数据。比如关系型数据、知识图谱（语义网络）数据；
非结构化数据。常见的有文本、图像、视频、音频，这一类数据没有固定的格式；
半结构化数据。常见的有 HTML、XML、JSON，这一类数据可以简单的理解为结构化的文本数据。

数据预处理方法：

关于「结构化数据」的预处理方法，在关系型数据预处理 - data mining 中已经有详细介绍，不再赘述；
关于「半结构化数据」的预处理方法，现在有很多成熟的解析器可以将半结构化数据转换为对应标签下的非结构化数据，因此本质上还是在处理非结构化数据；
关于「非结构化数据」的预处理方法，就对应到不同的研究领域了。比如文本数据对应到自然语言处理领域，图像 / 视频数据对应到计算机视觉领域，音频数据对应到语音信号处理领域。在对应的笔记中都有详细的数据预处理方法，这里不再赘述。

特征工程

特征工程在机器学习任务中起着举足轻重的作用，大多数机器学习的应用场景下，大部分的时间其实都花在了特征工程上。而之所以需要花费大量的精力去做特征工程，主要是为了「减低特征维度来减少计算开销」同时「提升模型泛化性能」。

特征选择

所谓的特征选择，就是在所有的 \(D\) 个特征中直接选择出 \(D'\ (D'<D)\) 个特征作为模型的输入。常见的方法就是网格搜索，即尺取法枚举。

特征映射

特征映射（也就是所谓的降维）同样是减少数据的特征维度，相比于直接删除某些特征，特征映射会在压缩特征维度的基础上尽可能保留最佳特征。下面介绍几种降维算法。

多维缩放 (multidimensional scaling, MDS)。一种线性降维算法。该算法的原则：对于任意的两个样本，降维后两个样本之间的距离保持不变。

我们定义 \(b_{ij}\) 为降维后任意两个样本之间的内积，\(dist_{ij}\) 表示任意两个样本的原始距离，\(Z \in R^{d'\times m},d' \le d\) 为降维后数据集的特征矩阵。可以得到以下降维流程：

内积计算：

\[ b_{ij}=-\frac{1}{2}(dist_{ij}^{2}-dist_{i\cdot}^{2}-dist_{\cdot j}^{2}+dist_{\cdot\cdot}^{2}) \]

新属性值计算：特征值分解法。其中 \(B = V \Lambda V^T\)

\[ \mathbf{Z}=\mathbf{\Lambda}_*^{1/2}\mathbf{V}_*^\mathrm{T}\in\mathbb{R}^{d^*\times m} \]

主成分分析 (Principal Component Analysis, PCA)。另外一种线性降维算法。该算法有两个原则：样本到超平面的距离都尽可能近、样本在超平面的投影都尽可能分开。基于此思想可以得到 PCA 算法流程：

度量学习

降维的本质是寻找一种合适的样本之间距离度量方式，为什么不直接学习距离度量方式呢？我们引入「度量学习」的概念。

为了有参可学，我们需要定义样本之间距离计算表达式中的参数。定义如下马氏距离：

\[ \mathrm{dist}_{\mathrm{mah}}^2(\boldsymbol{x}_i,\boldsymbol{x}_j)=(\boldsymbol{x}_i-\boldsymbol{x}_j)^\mathrm{T}\mathbf{M}(\boldsymbol{x}_i-\boldsymbol{x}_j)=\|\boldsymbol{x}_i-\boldsymbol{x}_j\|_\mathbf{M}^2 \]

为什么用所谓的马氏距离呢？欧氏距离不行吗？有以下结论：

欧式距离具有旋转不变性和平移不变性，在低维和属性直接相互独立时是最佳实践。但是当属性之间有相关性并且尺度相差较大时，直接用欧式距离计算会丢失重要的特征之间的信息；
马氏距离具有尺度不变性，在高维和属性之间有关系且尺度不同时是最佳实践。缺点在于需要计算协方差矩阵导致计算量远大于欧氏距离的计算量。

下面介绍两种度量学习算法来学习上述 M 矩阵，也就是数据集的「协方差矩阵的逆」中的参数。准确的说是学习一个矩阵来近似代替协方差矩阵的逆矩阵。

近邻成分分析 (Neighborhood Component Analysis, NCA)。目标函数：最小化所有数据点的对数似然函数的负值。

大间隔最近邻 (Large Margin Nearest Neighbor, LMNN)¹ ²。目标函数：最小化同一个类别中最近邻点的距离，同时最大化不同类别中最近邻点的距离。

数据划分

数据集的划分策略大约有三种。

留出法

即 hold-out。将数据集分为「训练集、验证集和测试集」三个部分。测试集对于训练是完全未知的，我们划分出测试集是为了模拟未来未知的数据。当下的任务就是利用训练集训练出最佳模型来尽可能好的拟合验证集，进而在测试集上得出模型的最终指标。

交叉验证法

即 cross validation。一般为 \(k\) 折交叉验证。即将「数据集与测试集的差集」随机划分为 \(k\) 个大小相似的互斥子集，将其中 \(k-1\) 份作为训练集，\(1\) 份作为验证集。算法执行 \(k\) 次获得平均误差。该方法避免了因为数据划分的随机性带来的系统误差。

自助法

即 bootstrapping。在数据集中进行有放回采样得到训练集。从数据集 \(D\ (|D|=m)\) 中有放回采样 \(m\) 次，这 \(m\) 个抽出来的样本集合 \(D'\) 大约占数据集的 \(\frac{2}{3}\)，于是就可以将抽出的样本集合 \(D'\) 作为训练集，\(D-D'\) 作为测试集。

证明很简单，我们计算测试集比例。一次采样中某个样本没有被选中的概率为 \(1-\dfrac{1}{m}\)，那么 m 次采样中某个样本从没被选中的概率就是 \((1-\dfrac{1}{m})^m\)，由于 \(\displaystyle \lim_{m\to+\infty}(1-\dfrac{1}{m})^m = \frac{1}{e}\approx 0.368\)，那么就可以得出测试集 \(D'\) 大约就占总数据集的 \(\dfrac{1}{3}\)。

数据平衡

在分类任务的数据集中，往往会出现类别不平衡的问题。即使在类别平衡时，使用一对其余等算法进行多分类也会出现类比不平衡的问题，因此解决类比不平衡问题十分关键。

Tip

数据平衡操作只能用于训练集，验证集和测试集不能进行任何分布上的改变。

阈值移动

对于二分类任务。我们定义 \(y\) 为样本预测为正例的概率，当训练集中正负样例比例相近时，一般以 \(0.5\) 为划分依据，即 \(y>0.5\) 的判定为正例，反之为负例。简单修改一下 \(y>0.5\) 就得到了下式：

\[ \frac{y}{1-y}> 1 \]

但当数据不平衡时，上式就不合理了。我们令 \(m^+\) 为训练集中样本正例的数量，\(m^-\) 为训练集中样本负例的数量，此时应当以 \(\dfrac{m^+}{m^+ + m^-}\) 为划分依据，即 \(y>\dfrac{m^+}{m^+ + m^-}\) 的判定为正例，反之为负例。简单修改一下 \(y>\dfrac{m^+}{m^+ + m^-}\) 就得到了下式：

\[ \frac{y}{1-y} > \frac{m^+}{m^-} \]

值得注意的是，由于训练集往往不能遵循独立同分布原则，也就导致我们观测的 \(\dfrac{m^+}{m^-}\) 其实不能准确代表真实的正负比例。

欠采样

去除过多的样本从而平衡正负例数量。

优点：训练的时间开销小；
缺点：可能会丢失重要信息。

典型算法：EasyEnsemble。

过采样

添加额外的样本从而平衡正负例数量。

缺点：简单的重复采样会导致模型过拟合数据，缺少泛化能力。

典型算法：SMOTE。