关键词：C++、机器学习

基础概念

机器学习是研究如何在计算机上 从数据产生模型 的学问。

• 模型：泛指从数据中学得的结果。

基本术语

数据：用于学习的输入内容，通常是一组或多组记录。

数据集：记录的集合。

学习、训练：从数据集中学习模型的过程，通过执行某个学习算法完成。

• 训练集：用于训练的数据集合。
• 测试集：用于通过模型预测结果的数据集合，评估模型优劣。
• 验证集：用于纠正和强化模型的数据集合

西瓜书（周志华的机器学习）中提到

一批关于西瓜的数据，如(色泽=青绿;根蒂=蜷缩;敲声=浊响)、(色泽=乌黑;根蒂=稍蜷;敲声=沉闷)……

其中每对括号内时一条记录，记录的集合为数据集。

• 每条记录是关于一个对象的描述，称为一个样品。
• 反映对象在某方面的表现或性质的事项，称为属性或特征。
  • 如色泽、根蒂、敲声
• 属性的取值为属性值
  • 如青绿、乌黑、浊响
• 属性所组成的空间称为属性空间、样本空间或输入空间。
  • 可以根据色泽、根蒂、敲声的取值确定一个对象，由这三者可组成向量，称为特征向量。

通常，令 $D=\{x_1,x_2,...,x_m\}$ 表示包含 $m$ 个样本的数据集，每个样本又由 $d$ 个属性描述，$x_i=(x_{i1},x_{i2},...,x_{id})$。$d$ 通常称为样本的维数，表示样本的属性个数。

通过学习得到模型，即可在没剖开一个西瓜之前，预测未知的西瓜。建立关系：

$((色泽=青绿;根蒂=蜷缩;敲声=浊响),好瓜)$

• 逗号前面是前面提过的特征向量。
• 逗号后面是结果，称为标签（标记）。
• 即 $(x_i,y_i)$
  • 由全部的标签组成的集合称为标记空间或输出空间。

只预测是“好瓜”或者“坏瓜”的任务称为分类任务。

• 只涉及两个类别称为二分类，通常为正类和反类。
• 涉及多个类别称为多分类。

预测连续的值，如西瓜的成熟度，称为回归任务。

当事先不知道某些概念，通过学习发现将西瓜分成若干组（如“外地瓜”“本地瓜”），称为聚类任务。

又根据训练数据是否拥有标记信息，学习任务可以分为监督学习和无监督学习。

• 分类和回归是监督学习的代表
• 聚类是无监督学习的代表

泛化：模型适用于新样本的能力。

经验误差与过拟合

分类错误的样本数占样本总数的比例称为错误率。

$错误率=\frac{a}{m},在m个样本中有a个样本分类错误\\ 精度=1-错误率=(1-\frac{a}{m})\times 100\%$

误差：模型的实际预测输出与样本的真实输出之间的差异。

• 训练集上的误差称为训练误差或经验误差
• 新样本上的误差称为泛化误差

过拟合：模型对训练集的某些特殊特点过于重视，泛化性能下降。

• 比如对西瓜数据集训练识别西瓜，西瓜大小被过于重视，认为小西瓜（或远处的西瓜）不是西瓜。

欠拟合：模型对训练样本的一般性质拟合不足。

• 比如对西瓜数据集训练识别西瓜，认为绿色的都是西瓜。

线性模型

基本形式

对于一个样本 $\bold{x}=(x_1,x_2,...,x_d)$，其中 $x_i$ 为第 $i$ 个属性上的取值。

线性模型试图通过一个属性值与权值的线性组合进行预测：

$f(x)=\omega_1x_1+\omega_2x_2+...+\omega_dx_d+b$

向量模式写成：

$f(\bold{x})=\bold{\omega}^T\bold{x}+b\\ \bold{\omega}=(\omega_1,\omega_2,...,\omega_d)$

线性回归

一元线性回归

线性回归对于样本 $(x_i,y_i)$ ，试图使：

$f(x_i)=\omega x_i+b近似于y_i$

通过均方误差评估 $f(x_i)$ 与 $y_i$ 之间的差别，试图让均方误差取最小值：

$(w^*,b^*)=\argmin_{(w,b)} \sum_{i=1}^m(f(x_i)-y_i)^2=\argmin_{(w,b)} \sum_{i=1}^m(y_i-f(x_i))^2\\ (w^*,b^*)=\argmin_{(w,b)} \sum_{i=1}^m(y_i-wx_i-b)^2$

• $(\omega^*,b^*)$ 为 $\omega$ 和 $b$ 的解，此处 $m$ 为样本数。
• $\argmin$ 表示右式取最小值时 $\omega$ 和 $b$ 的值。
• 求均方误差也对应了求欧氏距离。

基于均方误差最小值来进行模型求解，称为最小二乘法。

• 线性回归中，最小二乘法就是试图找到一条直线，使得样本到直线上的欧式距离之和最小。

令：

$E_{(w,b)}=\sum_{i=1}^m(y_i-wx_i-b)^2$

上式分别对 $\omega$ 和 $b$ 求导：

$\frac{\partial E_{(\omega,b)}}{\partial\omega}=2(\omega\sum_{i=1}^mx_i^2-\sum_{i=1}^m(y_i-b)x_i),\\ \frac{\partial E_{(\omega,b)}}{\partial b}=2(mb-\sum_{i=1}^m(y_i-wx_i))$

使导数为0，得到：

$\omega=\frac{\sum_{i=1}^my_i(x_i-\overline{x})}{\sum_{i=1}^mx_i^2-\frac{1}{m}(\sum_{i=1}^mx_i)^2}\\ \ \\ b=\frac{1}{m}\sum_{i=1}^m(y_i-\omega x_i)$

• $\overline{x}$ 为 $x$ 的均值。

例子-一元线性回归

对于一个一元线性回归数据集进行回归计算，效果如下：

该例子相关的数据集以及代码已置于仓库：Gitee

多元线性回归

用梯度下降求解多元线性回归。

• 梯度下降法的基本思想可以类⽐为⼀个下⼭的过程。
  • 最快的下山方式就是找到当前位置最陡峭的⽅向，然后沿着此方向向下⾛，对应到函数中，就是找到给定点的梯度 ，然后朝着梯度相反的⽅向，就能让函数值下降的最快。
  • 反复求取梯度，最后就能到达局部的最⼩值。

在单变量的函数中，梯度其实就是函数的微分，代表着函数在某个给定点的切线的斜率；

在多变量函数中，梯度是⼀个向量（向量有方向），梯度的方向就指出了函数在给定点的上升最快的方向。

梯度下降公式为：

$x^{i+1}=x^i-\alpha\frac{\partial}{\partial x_i}f(x^i)$

• $\alpha$ 称作学习率或者步长，意味着每一步走的距离。距离太大容易错过最低点，距离太小迟迟未到最低点。

如：

• 单变量函数梯度下降： $f(x)=x^2$
  • 微分为：$f'(x)=2x$
  • 初始化起点为： $x^0=1$，学习率取0.4
  • 梯度下降迭代：
    • $x^1=x^0-0.4\times 2x^0=1-0.4\times 2=0.2$
    • $x^2=x^1-0.4\times 2x^1=0.2-0.4\times 0.4=0.04$
    • $x^3=x^2-0.4\times 2x^2=0.04-0.4\times 0.08=0.008$
    • $x^4=x^3-0.4\times 2x^3=0.008-0.4\times 0.016=0.0016$
• 多变量函数的梯度下降： $f(x)=x_1^2+x_2^2$
  • 微分为：$f'(x)=2x_1+2x_2$
  • 初始化起点为： $x^0=(1,3)$，学习率取0.1
  • 梯度下降迭代：
    • $x^1=x^0-0.1\times f'(x^0)=(1,3)-0.1\times (2,6)=(0.8,2.4)$
    • $x^2=x^1-0.1\times f'(x^1)=(0.8,2.4)-0.1\times (1.6,4.8)=(0.64,1.92)$
    • $x^3=x^2-0.1\times f'(x^2)=(0.64,1.92)-0.1\times (1.28,3.84)=(0.512,1.536)$
    • ……
    • $x^{100}=(1.6296e^{-10},4.8889e^{-10})$

引入损失函数，度量拟合的程度。损失函数极小化，意味着拟合程度最好，对应的模型参数即为最优参数。线性回归中假设模型函数为： $f(x_1,...,x_n)=w_0+w_1x_1+w_2x_2+...+w_nx_n$

• $w_i$ 为模型参数，$b$ 为偏置。
• 简化：增加特征 $x_0=1$，可以简化为：$f(x_0,...,x_n)=\sum_{i=0}^nw_ix_i$

在线性回归中，损失函数通常为样本输出和假设函数的差取平方（或者带系数）。比如对于 $m$ 个样本 $(\bold{x_i},y_i)(i = 1, 2, ...m)$，采⽤线性回归，假设损失函数为：

$Loss(w_0,w_1,...,w_n)=\frac{1}{2m}\sum_{j=0}^m(f(x_0^{(j)},x_1^{(j)},...,x_n^{(j)})-y_j)^2$

• $x_i^{(j)}$：上标 $j$ 表示第 $j$ 个样本，下标 $i$ 表示第 $i$ 个特征。
• 系数 $\frac {1}{2}$ 是方便微分化简。
• $x_0^{(j)}$ 都为1。

对于上述损失函数的梯度为：

$\frac{\partial}{\partial w_i}Loss(w_0,w_1,...,w_n)=\frac{1}{m}\sum_{j=0}^m(f(x_0^{(j)},x_1^{(j)},...,x_n^{(j)})-y_j)x_i^{(j)}$

接着变化：

$w_i=w_i-α\frac{1}{m}\sum_{j=0}^m(f(x_0^{(j)},x_1^{(j)},...,x_n^{(j)})-y_j)x_i^{(j)}$

梯度算法变种

1. 全梯度下降算法（Full Gradient Descent）
   • 更新参数时使⽤所有的样本来进⾏更新。

$w_i=w_i-α\sum_{j=0}^m(f(x_0^{(j)},x_1^{(j)},...,x_n^{(j)})-y_j)x_i^{(j)}$

2. 随机梯度下降算法（Stochastic Gradient Descent）
   • 每次只代⼊计算⼀个样本⽬标函数的梯度来更新权重，再取下⼀个样本重复此过程，直到损失函数值停⽌下降或损失函数值⼩于某个可以容忍的阈值。

$w_i=w_i-α(f(x_0^{(j)},x_1^{(j)},...,x_n^{(j)})-y_j)x_i^{(j)}$

3. 小批量梯度下降算法（Mini-batch Gradient Descent）
   • 每次从训练样本集上随机抽取⼀个⼩样本集，在抽出来的⼩样本集上采⽤FG迭代更新权重。

$w_i=w_i-α\sum_{j=t}^{t+x-1}(f(x_0^{(j)},x_1^{(j)},...,x_n^{(j)})-y_j)x_i^{(j)}$

4. 随机平均梯度下降算法（Stochastic Average Gradient Descent）
   • 在内存中为每⼀个样本都维护⼀个旧的梯度，随机选择第i个样本来更新此样本的梯度，其他样本的梯度保持不变，然后求得所有梯度的平均值，进⽽更新了参数。
   • m 个样本

$w_i=w_i-\frac{α}{m}(f(x_0^{(j)},x_1^{(j)},...,x_n^{(j)})-y_j)x_i^{(j)}$

例子-波士顿房价

数据集地址：https://archive.ics.uci.edu/ml/machine-learning-databases/housing/housing.data

• 直接复制到本地即可，保存为 .txt 文件。

数据集具有14列：

• CRIM：城镇人均犯罪率。
• ZN：占地面积超过25,000平方英尺的住宅用地比例。
• INDUS：每个城镇非零售业务的比例。
• CHAS：Charles River虚拟变量（如果是河道，则为1;否则为0）。
• NOX：一氧化氮浓度（每千万份）。
• RM：每间住宅的平均房间数。
• AGE：1940年以前建造的自住单位比例。
• DIS：波士顿的五个就业中心加权距离。
• RAD：径向高速公路的可达性指数。
• TAX：每10,000美元的全额物业税率。
• PTRATIO：城镇的学生与教师比例。
• B：$1000(Bk - 0.63)^2$ 其中Bk是城镇黑人的比例。
• LSTAT：人口状况下降%。
• MEDV：自有住房的中位数报价, 单位1000美元。
• 前13列为属性值（即 $x_i$），第14列为房价（即 $y$）。

使用 SAG 算法进行线性回归计算。

测试结果：

1
2
3

Data imported: 506
平均误差：4.57072
迭代时长：46.329s

该例子相关的数据集以及代码已置于仓库：Gitee

贝叶斯分类器

假设有 $N$ 个类别，$B=\{B_1,B_2,...,B_N\}$，现有样本 $A$，通过贝叶斯公式：

$P(B_i\vert A)=\frac{P(B_i)P(A\vert B_i)}{\sum_{j=1}^nP(B_j)P(A\vert B_j)}$

• $P(B_i)$：类别 $B_i$ 发生的概率。
  • 称作先验概率，表达了样本空间中各类样本所占的概率。
  • 根据大数定律，当训练集包含充足的独立同分布样本时，$P(B_i)$ 可通过各类样本出现的频率来进行估计
• $P(A\vert B_i)$：确定是 $B_i$ 类下，样本 $A$ 出现的概率。称作类条件概率。
• $P(B_i\vert A)$：在样本 $A$ 出现下，属于类别 $B_i$ 的概率。称作后验概率。

类条件概率通过数据集进行训练，估计参数 $\theta_b$。

令 $D_i$ 表示训练集 $D$ 中第 $i$ 类样本组成的集合，假设样本是独立同分布，则参数 $\theta_b$ 对于数据集的似然是：

$P(D_i\vert\theta_b)=\prod_{x\in D_i}P(x\vert\theta_b)$

对 $\theta_b$ 进行极大似然估计，寻找最大化似然 $P(D_i\vert\theta_b)$ 的参数值 $\theta_b'$。

• 从 $\theta_b$ 的所有可能取值中，找到一个能使数据出现可能性最大的值。

连乘容易出现下溢，可以使用对数计算：

$LL(\theta_b)=\log P(D_i\vert\theta_b)=\sum_{x\in D_i}\log P(x\vert\theta_b)$

$\theta_b'=\argmax_{\theta_b}LL(\theta_b)$

朴素贝叶斯分类器

一种基于贝叶斯理论的简单概率分类器。

• 朴素：输入变量的特征属性间具有独立性

由属性条件独立性：

$P(B_i\vert A)=\frac{P(B_i)P(A\vert B_i)}{\sum_{j=1}^nP(B_j)P(A\vert B_j)}=\frac{P(B_i)}{P(A)}\prod_{i=1}^dP(A^{(i)}\vert B_i)$

• $d$：样本的属性个数。
• $B_i$：第 $i$ 个类别。
• $A^{(i)}$：样本 $A$ 的第 $i$ 个属性值。
• 对于所有类别， $P(A)$ 都相等。

所以朴素贝叶斯表达式写成：

$f(A)=\argmax_{B_i\in B}P(B_i)\prod_{j=1}^dP(A^{(j)}\vert B_i)$

朴素贝叶斯的训练过程就是基于训练集 $D$ 来估计类先验概率 $P(B_i)$，并为每个属性估计条件概率 $P(A^{(j)}\vert B_i)$。

先验概率：

$P(B_i)=\frac{\vert D_i\vert}{\vert D\vert}{}$

离散属性下，设 $D_{B_i,A^{(j)}}$ 为第 $B_i$ 类，第 $j$ 个属性值为 $A^{(j)}$ 构成的集合，则条件概率可估计为：

$P(A^{(j)}\vert B_i)=\frac{\vert D_{B_i,A^{(j)}}\vert}{\vert D_{B_i}\vert}{}$

连续属性则考虑概率密度函数。

如果某个属性值在训练集中没有与某个类同时出现过，可能会出现概率值为零，此时需要做一些平滑。

• 常用拉普拉斯修正：

$\hat{P}(B_i)=\frac{\vert D_i\vert+1}{\vert D\vert+N}$

$\hat{P}(A^{(j)}\vert B_i)=\frac{\vert D_{B_i,A^{(j)}}\vert+1}{\vert D_{B_i}\vert+N_j}$

• $N$：训练集中可能的类别数；
• $N_j$：第 $j$ 个属性可能的取值数。

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

正态贝叶斯分类器

正态贝叶斯分类器认为每一个分类的所有特征属性（即特征向量）服从多变量正态高斯分布，即：

$P(x\vert C_k)=\frac{1}{\sqrt{(2\pi)^n\vert\sum_k\vert}}\exp\left(-\frac{1}{2}(x-\mu_k)^T\sum_k^{-1}(x-\mu_k)\right)$

• $\mu_k$ 表示第 $k$ 个分类对应的 $n$ 维均值向量；
• $|\sum_k|$ 表示第 $k$ 个分类对应的 $n×n$ 的协方差矩阵 $\sum_k$ 的行列式的值。

正态贝叶斯分类器只能处理特征属性是连续数值的分类问题。但它认为特征属性直接不必独立，比朴素贝叶斯的使用条件宽。

同样，计算最大似然：

$\hat{y}=\argmax_{k\in\{1,...,k\}}P(x1,...,x_n\vert C_k)$

化为对数似然函数：

$ln(L)=-\frac{1}{2}\left[\ln(\vert\sum_k\vert)+(x-\mu_k)^T\sum_k^{-1}(x-\mu_k)+n\ln(2\pi)\right]\tag{1}$

求式上极大值问题可以转换为求式中方括号内的极小值问题。

均值向量 $\mu_k$ 的第 $i$ 个特征属性 $\mu_{ki}$ 的极大似然估计为：

$\hat{\mu}_{ki}=\frac{\sum_{j=1}^{N_k}x_{ki}^{(j)}}{N_k}$

• $x_{ki}^{(j)}$：训练样本中属于分类 $k$ 的第 $j$ 个样本的第 $i$ 个特征属性的值。
• $N_k$：训练样本中属于分类 $k$ 的样本数。

$\hat{\mu_k}=(\hat{\mu}_{k1}, ..., \hat{\mu}_{kn})^T\tag{2}$

$n×n$ 的协方差矩阵 $\sum_k$ 的无偏估计形式为：

$\hat{\sum}_k=\frac{1}{N_k-1}\left[\begin{matrix} cov_k^{(1,1)} & cov_k^{(1,2)} & ... & cov_k^{(1,n)} \\ cov_k^{(2,1)} & cov_k^{(2,2)} & ... & cov_k^{(2,n)} \\ \vdots & \vdots & \ddots & \vdots \\ cov_k^{(n,1)} & cov_k^{(n,2)} & ... & cov_k^{(n,n)} \end{matrix}\right] \tag{3}$

其中 $cov_k^{(p,q)}$ 表示训练样本中第 $k$ 个分类所组成的数据集合中，第 $p$ 个特征属性与第 $q$ 个特征属性的协方差，如果 $p=q$，那么为方差。

$\begin{matrix} cov_{k}^{(p,q)}&=&\sum_{j=1}^{N_k}[(x_{kp}^{(j)}-\hat{\mu}_{kp})(x_{kq}^{(j)}-\hat{\mu}_{kq})]\\ &=&\sum_{j=1}^{N_k}(x_{kp}^{(j)}x_{kq}^{(j)})-\hat{\mu}_{kq}\sum_{j=1}^{N_k}x_{kp}^{(j)}-\hat{\mu}_{kp}\sum_{j=1}^{N_k}x_{kq}^{(j)}+N_k\hat{\mu}_{kp}\hat{\mu}_{kq} \end{matrix}$

正态贝叶斯分类器的执行步骤：

1. 由训练样本数据估计每个分类的协方差矩阵（式3）和均值向量（式2）；
2. 把协方差矩阵和均值向量代入到对数似然函数（式1）；
3. 得到每个分类完整的对数似然函数；
4. 预测样本时，将样本的特征属性分别代入全部分类的对数似然函数中，最大对数似然函数对应的分类就是该样本的分类结果。

基于OpenCV实现正态贝叶斯分类器

OpenCV 自带实现了 正态贝叶斯分类器 的类： NormalBayesClassifier。

相关代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// 创建贝叶斯分类器
cv::Ptr<cv::ml::NormalBayesClassifier> model=cv::ml::NormalBayesClassifier::create();
    
// 设置训练数据
cv::Ptr<cv::ml::TrainData> tData =cv::ml::TrainData::create(datas, ROW_SAMPLE, labels);

//训练分类器
model->train(tData);
    
//预测
int label = model->predict(samples)

//保存模型
model->save(filename)

例子-糖尿病预测数据集

数据集地址：https://aistudio.baidu.com/datasetdetail/33810

• 该数据集包含数据集中共包含768个样本，取后100个数据组成测试集。

数据集中每个样本有8种特征。Outcome 是样本的标签（即类别），0表示没有糖尿病，1表示患有糖尿病。

• Pregnancies: 怀孕次数
• Glucose：血浆葡萄糖浓度
• BloodPressure：舒张压
• SkinThickness：肱三头肌皮肤褶皱厚度
• Insulin：两小时胰岛素含量
• BMI：身体质量指数，即体重除以身高的平方
• DiabetesPedigreeFunction：糖尿病血统指数，即家族遗传指数
• Age：年龄

使用手搓的朴素贝叶斯分类器和 OpenCV 实现的正态贝叶斯分类器进行训练测试，结果如下：

1
2
3
4
5
6
7
8
9
10
11

Train Data imported: 668
正态贝叶斯分类器：
计算花费时长：0ms
Test Data imported: 100
正确率：0.76

Train Data imported: 668
朴素贝叶斯分类器：
计算花费时长：1ms
Test Data imported: 100
正确率：0.59

代码及数据集地址：Gitee - bayesClassifier

例子-鸢尾花数据集

数据集地址：

• 训练集：http://download.tensorflow.org/data/iris_training.csv
• 测试集：http://download.tensorflow.org/data/iris_test.csv

部分数据如下：

使用手搓的朴素贝叶斯分类器和 OpenCV 实现的正态贝叶斯分类器进行训练测试，结果如下：

1
2
3
4
5
6
7
8
9
10
11

Train Data imported: 120
正态贝叶斯分类器：
计算花费时长：0ms
Test Data imported: 30
正确率：0.966667

Train Data imported: 120
朴素贝叶斯分类器：
计算花费时长：0ms
Test Data imported: 30
正确率：0.8

代码及数据集地址：Gitee - bayesClassifier

初探 EM 算法

EM 介绍

期望极大值（Expectation Maximization，EM）算法是一种能够得到极大似然参数估计的迭代方法。

• 可适用于包含隐变量的统计模型
  • 隐变量：属性值未知的变量。

令 $X$ 表示已观测变量集，$Z$ 表示隐变量集，$\theta$ 表示模型参数，如果想对 $\theta$ 作极大似然估计，则最大化对数似然应为：

$LL(\theta|X,Z)=\ln P(X,Z|\theta)$

由于 $Z$ 是隐变量，故无法直接求解。可以通过对 $Z$ 计算期望，来最大化已观测数据的对数“边际似然”：

$LL(\theta|X)=\ln P(X|\theta)=\ln\sum_ZP(X,Z|\theta)\tag{1}$

EM 算法的基本思想：

• E-step：若参数 $\theta$ 已知，则根据训练数据推断除最优隐变量 $Z$ 的值。
• M-step：若隐变量 $Z$ 的值已知，则对参数 $\theta$ 作极大似然估。

若计算 $Z$ 的期望，以 $\theta^0$ 为起点，对式1迭代以下步骤直至收敛：

• E-step：基于 $\theta^t$ 推断隐变量 $Z$ 的期望，记作 $Z^t$；
• M-step：基于已观测变量 $X$ 和 $Z^t$ 对参数 $\theta$ 作极大似然估计，记作 $\theta^{t+1}$。

若基于 $\theta^t$ 计算隐变量 $Z$ 的概率分布 $P(Z|X,\theta^t)$，则 EM 的步骤变成：

• E-step：基于 $\theta^t$ 推断隐变量分布 $P(Z|X,\theta^t)$，并计算对数似然 $LL(\theta|X,z)$ 关于 $Z$ 的期望：

$Q(\theta|\theta^t)=E_{Z|X,\theta^t}LL(\theta|X,Z)$

• M-step：寻找参数最大化期望似然：

$\theta^{i+1}=\argmax_\theta Q(\theta|\theta^t)$

基于OpenCV实现EM

EM 是一种无监督的机器学习方法，它还可以用于聚类处理上。

OpenCV 提供了 EM 类，可用于实现 EM 算法对高斯混合模型的参数估计：

• 高斯混合模型可以看作是由 K 个单高斯模型组合而成的模型，这 K 个子模型是混合模型的隐变量。

1
2
3
4
5
6
7
8

// 创建 EM
cv::Ptr<cv::ml::EM> model=cv::ml::EM::create();

// 设置聚类数
model->setClustersNumber(classes);

// 训练函数，结果反映在 labels参数
bool trainEM(InputArray samples,OutputArray logLikelihoods=noArray(),OutputArray labels=noArray(),OutputArray probs=noArray()) ;

使用 EM 算法进行像素聚类进而实现图像分割。

• 将 RGB 属性作为样本，进行聚类。即每一个像素都是一个样本。

效果如下：

代码地址：EM 算法 - Gitee

K 近邻（KNN）算法

K 近邻算法（K-Nearest Neighbors，KNN）既可以处理分类问题，也可以处理回归问题。

KNN 是一种懒惰学习算法。

• 懒惰学习算法：指直到出现新的测试样本，该算法才开始依据训练样本进行样本的预测处理工作。
  • 也就是说，该算法事先不会对训练样本进行任何处理，只会懒散地等待测试样本的到来，然后才开始工作。

懒惰学习算法构建的目标函数能够更近似测试样本数据本身，但同时它需要更大的存储空间用于存储训练样本数据。

• 懒惰学习算法非常适用于 具有较少特征属性 的 大型数据库 的问题。

KNN 算法原理

在训练集中，每个样本假设都是一个具有 $n$ 个特征属性的向量，即 $x=(x_1, x_2, x_3, ..., x_n)$ ，可看作每个样本在 $n$ 维特征空间内分布。每个样本还有一个标签 $y$。

目的是找到一个函数，使得 $y=f(x)$，以确定新样本 $u$ 的标签。

样本在 $n$ 维特征空间内分布，可以找到样本间的一种“距离”，用于评估样本间的相似程度。

• 欧氏距离：（适用于特征属性是连续变量）

$D_{Eu}(x, u)=\sqrt{\sum_{i=1}^n(x_i-u_i)^2}$

• 曼哈顿距离：（适用于特征属性是连续变量）

$D_{Man}(x, u)=\sum_{i=1}^n|x_i-u_i|$

• 闵可夫斯基距离：（适用于特征属性是连续变量）

$D_{Min}=\sqrt[q]{\sum_{i=1}^n|x_i-u_i|^q}$

• 汉明距离：（适用于特征属性是离散变量）

$D_{Ham}(x, u)=\sum_{i=1}^n|x_i-u_i|,\begin{cases}当x_i=u_i时，D_{Ham}(x, u)=0\\当x_i\neq u_i时，D_{Ham}(x, u)=1\end{cases}$

KNN 的任务是在训练集中，依据距离找到与新样本（测试样本） $u$ 最相似的那 $K$ 个训练样本。

• 若做分类问题，则多数表决，在 $K$ 个训练样本中，哪个分类的样本数多，哪个分类就是 $u$ 的预测分类。
• 若做回归问题，$u$ 的预测值 $v$ 为：

$v=\frac{\sum_{i=1}^Ky_i}{K}$

在考虑训练集与测试样本之间距离大小的影响下，使得距离更小的样本具有更大的权值，$K$ 个最邻近样本中第 $i$ 个样本 $x^i$ 与测试样本 $u$ 的权值定义为：

$w(x^i, u)=\frac{\exp{(-D(x^i, u))}}{\sum_{i=1}^n\exp{(-D(x^i, u))}}$

• 对于回归问题，预测结果 $v$ 变成：

$v=\sum_{i=1}^Kw(x^i, u)y_i$

• 对于分类问题，最终分类结果为权值最大的类。

KNN 的 $K$ 需要预先确定：

• 若值过大，会使特征空间内明确分类边界变得模糊；
• 若值过小，则引入误差。

常用 交叉验证法 选择 $K$ 值。

• 把训练数据 $D$ 分为 $K$ 份，用其中的 $(K-1)$ 份训练模型，把剩余的1份数据用于评估模型的质量。

基于OpenCV实现KNN

OpenCV 并没有采用交叉验证和距离权值的方法。

相关函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// 创建模型
cv::Ptr<cv::ml::KNearest> model=cv::ml::KNearest::create();

// 设置默认 K 值
model->setDefaultK(k);

// 是否分类
model->setIsClassifier(true);

// 设置算法类型
model->setAlgorithmType(cv::ml::KNearest::BRUTE_FORCE);

// 训练，实际上是初始化训练样本数据
model->train(trainDataPtr);

// 找到最近邻
model->findNearest(testMat, k, result);

例子-小麦品种籽粒数据集

数据集地址：https://archive.ics.uci.edu/dataset/236/seeds

三种不同小麦品种籽粒几何特性的测定。数据集具有7个属性：

1. 一个区域
2. 周边P
3. 紧性 $C=4\times\pi\times A / P^2$
4. 核的长度
5. 核的宽度
6. 不对称系数
7. 核槽长度

部分数据如下：

使用自实现 KNN 和 OpenCV 提供的 KNN 类进行训练计算，结果如下：

1
2
3
4
5
6
7
8
9
10
11

Train Data imported: 150
Test Data imported: 60
K近邻算法：
正确率：0.933333
计算花费时长：1ms

Train Data imported: 150
Test Data imported: 60
K近邻算法(基于OpenCV实现)：
正确率：0.95
计算花费时长：50ms

代码及数据集地址：KNN - Gitee

SVM 支持向量机算法

• SVM（Support Vector Machine）：支持向量机
• SVC（Support Vector Classifier）：支持向量分类器
• SVR（Support Vector Regression）：支持向量回归器

支持向量机基本型

给定大小为 $m$ 的训练集 $D=\{(\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2), \ldots, (\mathbf{x}_m, y_m)\},y_i\in\{-1, 1\}$。基于训练集 $D$ 在样本空间中找到一个超平面，将不同类别的样本分开，如下图：

明显红色的划分超平面更合适。划分超平面可通过线性方程描述：

$w^T\mathbf{x}+b=0$

• $w=(w_1, w_2, \ldots, w_n)$：为法向量，决定了超平面的方向；
• $b$：位移项。
• $\mathbf{x}=(\mathbf{x}_1, \mathbf{x}_2, \ldots,\mathbf{x}_n)$

样本空间中任意点到超平面 $(w,b)$ 的距离为：

$r=\frac{\vert w^T\mathbf{x}+b\vert}{\vert\vert w\vert\vert}$

在做分类时，应有 $(\mathbf{x}_i, y_i)\in D$，当 $y_i=+1$ 时，$w^T\mathbf{x}_i+b>0$；当 $y_i=-1$ 时，$w^T\mathbf{x}_i+b<0$。令：

$\begin{cases} w^T\mathbf{x}_i+b\geq+1, y_i=+1\\ w^T\mathbf{x}_i+b\leq-1, y_i=-1 \end{cases}$

距离超平面最近的几个训练样本点满足上式，如下图 $H_1$、$H_2$ 上的样本被称为支持向量（support vector）。

两个异类的支持向量到超平面的距离之和（也称为间隔）为：

$\gamma=\frac{\vert(b+1)-(b-1)\vert}{\vert\vert w\vert\vert}=\frac{2}{\vert\vert w\vert\vert}$

为了找到具有最大间隔的划分超平面，需要满足下式中约束参数 $w$ 和b，使得 $\gamma$ 最大：

$\max_{w,b}\frac{2}{\vert\vert w\vert\vert}\\ 同时保证\ y_i(w^T\mathbf{x}_i+b)\geq 1,i=1,2,\ldots,m.$

为了最大化间隔，需要最大化 $\vert\vert w\vert\vert^{-1}$，等价于最小化 $\vert\vert w\vert\vert^2$

$\min_{w,b}\frac{1}{2}\vert\vert w\vert\vert^2\\ 同时保证\ y_i(w^T\mathbf{x}_i+b)\geq 1,i=1,2,\ldots,m.$

对上式使用拉格朗日乘子法可得到它的对偶问题。

• 拉格朗日乘⼦法是⼀种寻找多元函数在⼀组约束下的极值的方法。

  • 通过引⼊拉格朗日乘子，可将有 $d$ 个变量与 $k$ 个约束条件的最优化问题转化为具有 $d+k$ 个变量的⽆约束优化问题求解。

• 对上式每条约束添加拉格朗日乘子 $\alpha_i\geq 0$

• 对偶问题是原始问题的一种变换形式，它在数学上与原始问题密切相关，但可能具有不同的结构和性质。

$L(w,b,\mathcal{\alpha})=\frac{1}{2}\vert\vert w\vert\vert^2+\sum_{i=1}^m\alpha_i(1-y_i(w^T\mathbf{x}_i+b))$

• 其中 $\mathcal{\alpha}=(\alpha_1, \alpha_2, \ldots, \alpha_m)$

令 $L(w,b,\mathcal{\alpha})$ 对 $w$ 和 $b$ 的偏导为零，可得

$\frac{\partial L(w,b,\mathcal{\alpha})}{\partial w}=w-\sum_{i=1}^m\alpha_iy_i\mathbf{x}_i=0\Rightarrow w=\sum_{i=1}^m\alpha_iy_i\mathbf{x}_i$

$\frac{\partial L(w,b,\mathcal{\alpha})}{\partial b}=-\sum_{i=1}^m\alpha_iy_i=0\Rightarrow 0=\sum_{i=1}^m\alpha_iy_i$

将 $w=\sum_{i=1}^m\alpha_iy_i\mathbf{x}_i$ 代入 $L(w,b,\mathcal{\alpha})$，将 $w$ 和 $b$ 消去，再结合 $0=\sum_{i=1}^m\alpha_iy_i$，得到 $\min_{w,b}\frac{1}{2}\vert\vert w\vert\vert^2$ 的对偶问题：

$\max_{\mathcal{\alpha}}\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j\mathbf{x}_i^T\mathbf{x}_j\tag{1}$

$同时保证\ \sum_{i=1}^m\alpha_iy_i=0,\\ \alpha_i\geq0,i=1,2,\ldots,m.$

求解出 $\mathcal{\alpha}$ 后：

$f(\mathbf{x})=w^T\mathbf{x}+b=\sum_{i=1}^m\alpha_iy_i\mathbf{x}_i^T\mathbf{x}+b\tag{2}$

上述过程需满足 KKT 条件，即：

$\begin{cases} \alpha_i\geq 0\\ y_if(\mathbf{x})-1\geq 0\\ \alpha_i(y_if(\mathbf{x})-1)=0 \end{cases}$

对任意训练样本 $(\mathbf{x}_i,y_i)$，总有 $\alpha_i=0$ 或 $y_if(\mathbf{x}_i)=1$。

• 若 $\alpha_i=0$，该样本不会出现在式 1 的求和中，也不会对 $f(\mathbf{x}_i)$ 产生影响。
• 若 $\alpha_i>0$，则必有 $y_if(\mathbf{x}_i)=1$，对应的样本点位于最大间隔边界上，即支持向量。

训练完后，大部分训练样本也不需要保留，最终模型仅与支持向量有关。

SMO

对于式 1 的求解，可以使用二次规划算法求解，也可以通过 SMO（Sequential Minimal Optimization） 算法求解。

SMO 的基本思路：

• 固定 $\alpha_i$ 之外的所有参数，求 $\alpha_i$ 上的极值。

• 每次选择两个变量 $\alpha_i$ 和 $\alpha_j$，同时固定其他参数，在参数初始化后，不断执行以下步骤直至收敛：

  • 选取一对需更新的变量 $\alpha_i$ 和 $\alpha_j$；
  • 固定 $\alpha_i$ 和 $\alpha_j$ 以外的参数，求解式 1 获得更新后的 $\alpha_i$ 和 $\alpha_j$ 。

  SMO 使选取的两变量所对应样本之间的间隔最大。

  • 使得两个变量有很大区别，给目标函数值更大的变化。

核函数

上述讨论训练样本是线性可分的（即存在划分超平面能正确分类），如果原始样本空间内不能存在这样的划分超平面，那么需要 将样本从原始空间映射到更高维的空间，使其在这个特征空间内线性可分。

• 令 $\phi(\mathbf{x})$ 表示将 $\mathbf{x}$ 映射后的特征向量，则在特征空间中划分超平面所对应的模型表示为：

$f(\mathbf{x})=w^T\phi(\mathbf{x})+b$

其中 $w$ 和 $b$ 为模型参数，有：

$\min_{w,b}\frac{1}{2}\vert\vert w\vert\vert^2\\ 同时保证\ y_i(w^T\phi(\mathbf{x}_i)+b)\geq 1,\ i=1,2,\ldots,m$

其对偶问题是：

$\max_\alpha\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j\phi(\mathbf{x}_i)^T\phi(\mathbf{x}_j)\\ 同时保证\ \sum_{i=1}^m\alpha_iy_i=0,\alpha_i\geq 0,i=1,2,\ldots,m$

设计核函数：

$\kappa(\mathbf{x}_i, \mathbf{x}_j)=<\phi(\mathbf{x}_i),\phi(\mathbf{x}_j)>=\phi(\mathbf{x}_i)^T\phi(\mathbf{x}_j)$

• 即 $\mathbf{x}_i$ 与 $\mathbf{x}_j$ 在特征空间的内积等于它们在原始样本空间通过函数 $\kappa(\cdot,\cdot)$ 计算的结果。

所以之前的式子改写为：

$\max_\alpha\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j\kappa(\mathbf{x}_i,\mathbf{x}_j)\\ 同时保证\ \sum_{i=1}^m\alpha_iy_i=0,\alpha_i\geq 0,i=1,2,\ldots,m$

求解后可得到：

$f(\mathbf{x})=w^T\phi(\mathbf{x})+b\\ =\sum_{i=1}^m\alpha_iy_i\phi(\mathbf{x}_i)^T\phi(\mathbf{x})+b\\ =\sum_{i=1}^m\alpha_iy_i\kappa(\mathbf{x}_i,\mathbf{x})+b$

• 上式说明模型最优解可通过训练样本的核函数展开，展式称为支持向量展式。

定理：令 $\chi$ 为输入空间，$\kappa(\cdot,\cdot)$ 式定义在 $\chi\times\chi$ 上的对称函数，则 $\kappa$ 式核函数 当且仅当 对于任意数据 $D=\{\mathbf{x}_1,\mathbf{x}_2,\ldots,\mathbf{x}_m\}$，核矩阵 $K$ 总是半正定的：

$K=\left[\begin{matrix} \kappa(\mathbf{x}_1,\mathbf{x}_1) & \cdots & \kappa(\mathbf{x}_1,\mathbf{x}_j) & \cdots & \kappa(\mathbf{x}_1,\mathbf{x}_m)\\ \vdots & \ddots & \vdots & \ddots & \vdots\\ \kappa(\mathbf{x}_i,\mathbf{x}_1) & \cdots & \kappa(\mathbf{x}_i,\mathbf{x}_j) & \cdots & \kappa(\mathbf{x}_i,\mathbf{x}_m)\\ \vdots & \ddots & \vdots & \ddots & \vdots\\ \kappa(\mathbf{x}_m,\mathbf{x}_1) & \cdots & \kappa(\mathbf{x}_m,\mathbf{x}_j) & \cdots & \kappa(\mathbf{x}_m,\mathbf{x}_m) \end{matrix}\right]$

• 对于一个半正定和矩阵，总能找到一个与之对应的映射 $\phi$。任何一个核函数都隐式定义了一个称为“再生核希尔伯特空间”（简称RKHS）的特征空间。

常用核函数如下：

• 线性核：$\kappa(\mathbf{x}_i,\mathbf{x}_j)=\mathbf{x}_i^T\mathbf{x}_j$；
• 多项式核：$\kappa(\mathbf{x}_i,\mathbf{x}_j)=(\mathbf{x}_i^T\mathbf{x}_j)^d$，$d\geq 1$ 为多项式的次数；
• 高斯核：$\kappa(\mathbf{x}_i,\mathbf{x}_j)=\exp(-\frac{\vert\vert\mathbf{x}_i-\mathbf{x}_j\vert\vert^2}{2\sigma^2})$，$\sigma>0$ 为高斯核的带宽；
• 拉普拉斯核：$\kappa(\mathbf{x}_i,\mathbf{x}_j)=\exp(-\frac{\vert\vert\mathbf{x}_i-\mathbf{x}_j\vert\vert^2}{\sigma^2})$，$\sigma>0$；
• Sigmoid核：$\kappa(\mathbf{x}_i,\mathbf{x}_j)=\tanh(\beta\mathbf{x}_i^T\mathbf{x}_j+\theta)$，$\tanh$ 为双曲正切函数，$\beta>0,\theta<0$。

此外，核函数还可通过组合得到：

• 若 $\kappa_1$ 和 $\kappa_2$ 为核函数，则对于任意正数 $\gamma_1、\gamma_2$，其线性组合 $\gamma_1\kappa_1+\gamma_2\kappa_2$ 也是核函数。
• 若 $\kappa_1$ 和 $\kappa_2$ 为核函数，则核函数的直积 $\kappa_1\otimes\kappa_2(\mathbf{x}_i,\mathbf{z})=\kappa_1(\mathbf{x}_i,\mathbf{z})\kappa_2(\mathbf{x}_i,\mathbf{z})$ 也是核函数。
• 若 $\kappa_1$ 为核函数，则对于任意函数 $g(x)$，$\kappa(\mathbf{x},\mathbf{z})=g(\mathbf{x})\kappa_1(\mathbf{x},\mathbf{z})g(\mathbf{z})$ 也是核函数。