吉林大学机器学习复习

第一章、绪论：

相关概念：

训练集；评估函数（目标函数、代价函数）；梯度下降；机器学习算法的分类

机器学习是什么：寻找一个函数（模型）。

机器学习的基本流程：

训练阶段+测试阶段

训练阶段：从已经假定的函数（模型）集合中，通过将训练集代入到评估函数来识别一个最优函数（模型）；

测试阶段：使用得到的最优函数（模型）来进行测试，评价效率如何；

具体做法：选择具体的模型，定义目标函数，选出最优函数。

机器学习算法的类型：监督学习（回归，分类）、无监督学习（聚类，降维）、半监督学习、自监督学习、强化学习。

有监督学习：从给定的有标注的训练数据集中学习出一个函数，当新的数据到来时可以可以根据这个函数预测结果。常见如：回归，分类。

半监督学习：结合少量的有标注训练数据和大量的未标注数据来进行数据的学习。

无监督学习：没有标注的训练数据集，需要根据样本间的统计学规律对样本集进行分析，常见如：聚类和降维。

强化学习：一种计算性的学习方法，agent在与复杂和不确定的环境交互时，试图使其获得的奖励总量最大化。

强化学习和有监督学习的区别：

强化学习通过判别学习，有监督学习通过指导学习。

自监督学习：自监督学习是一种机器学习范式，它利用未标记的数据来训练模型，通过设计一些辅助任务来自动生成标签，从而学习数据的有用特征和表示。这种方法不需要外部的人工标记，而是从数据本身中挖掘监督信息。

有监督、无监督、自监督的对比：

第二章线性回归

相关概念：特征、目标、训练样本、训练集

特征 (Features): 在监督学习中，特征是输入数据的属性或变量，通常表示为 $x^{(i)}$ 。这些特征用于描述数据点并作为模型的输入。
目标 (Target): 目标是模型需要预测的值，通常表示为 $y^{(i)}$ 。目标可以是连续的数值（如房价、温度等），也可以是离散的类别（如垃圾邮件/非垃圾邮件、疾病/非疾病等）。
训练样本 (Training Sample): 训练样本是特征和目标值的组合，表示为 $(x^{(i)},y^{(i)})$ 。每个训练样本都包含了一个数据点的特征和相应的目标值。
训练集 (Training Set): 训练集是所有训练样本的集合，表示为 { ${(x^{(i)},y^{(i)}),i=1,2,...,m}$ }，其中 $m$ 是训练样本的数量。这个集合用于训练模型，使其能够学习特征和目标值之间的关系。
学习算法 (Learning Algorithm): 学习算法是监督学习过程中用于训练模型的算法。它接收训练集作为输入，并尝试找到一个函数 $h$ ，这个函数能够最好地映射特征到目标值。
回归问题 (Regression Problem): 当目标 $y$ 是一个实数时，监督学习问题被称为回归问题。在这种情况下，模型的目标是预测一个连续的数值。
分类问题 (Classification Problem): 当目标 $y$ 是一个类别标签时，监督学习问题被称为分类问题。在这种情况下，模型的目标是预测一个离散的类别，通常表示为y∈{1,2,3,…,C}，其中 C 是类别的总数。

线性回归：

线性回归试图找到一个线性函数，使得它能够很好地拟合输入特征和输出目标之间的关系，有简单线性回归和多元线性回归之分。多元线性回归就是可以包含多个特征变量。

多元线性回归：

这里的向量一般表示竖向量。

特征规范化：

特征规范化是机器学习中的一种重要数据预处理技术，它通过改变数据的分布，使得不同特征之间的数值范围一致，从而提高模型训练的效率和性能。

举例：

举例(回归1)：假设只有两个特征向量

这里把Living area和bedrooms分别作为特征变量 $x_{1},x_{2}$ ,把Price作为目标 $y$ ;

那么 $h_\theta(x)$ $=$ $h_{\theta}(x_{1},x_{2})$ $=$ $\theta_{0}+\theta_{1}x_{1}+\theta_{2}x_{2}$

空间图上可以表示为：

图中的平面就是由预测值 $h_{\theta}(x_{1},x_{2})$ 构成的，每个红点表示一个训练样本，红点的Y坐标表示某样本 $(x_{1}^{(i)},x_{2}^{(i)})$ 下对应的目标 $y^{(i)}$ ，所有的红点构成训练集。线性回归就是要调整 $\theta$ 的值，使得预测和目标尽量靠近，在图上就是要使得平面和红点尽量贴合。

如何确定模型 $h_{\theta}(x)$ 的参数 $\theta$ :

代价函数（Cost Function）或损失函数（Loss Function）是机器学习中用来衡量模型预测值与实际值之间差异的函数。它是一个非负实值函数，其目的是量化模型在训练数据上的表现。代价函数越小，意味着模型的预测值与实际值越接近，模型的性能越好。

显然，代价函数反应模型对数据的拟合程度。

继续上面回归1的例子：

这里的代价函数就可以写作:

$minJ(\theta)=\Sigma_{i=1}^m |h_{\theta}(x^{(i)})-y^{(i)}|$

在图上表示的就是，所有红点到平面的距离的和。

线性回归的两种损失函数表示：绝对误差和平方和误差。

绝对误差：

$J(\theta)=\sum _{i=1}^m|h_\theta(x^{(i)})-y^{(i)}|$

平方和误差：

$J(\theta)=\frac{1}{2}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})^2$

最小二乘法：

正规方程：最小二乘法的正规方程（Normal Equation）是求解线性回归模型参数 $\theta$ 的一种解析方法。

增广矩阵 $X$ 的每一行表示一个样本（除了第一列的1），每一列表示不同样本下的对应特征变量取值，可见，矩阵 $X$ 就是特征变量的集合。

$X\theta=\begin{bmatrix} (x^{(1)})^T\\ (x^{(2)})^T\\ ...\\ ...\\ (x^{(m)})^T\\ \end{bmatrix} \begin{bmatrix} \theta_0\\ \theta_1\\ ....\\ ....\\ \theta_n\\ \end{bmatrix}=\begin{bmatrix} 1,x_1^{(1)},x_2^{(1)},....,x_n^{(1)}\\ 1,x_1^{(2)},x_2^{(2)},....,x_n^{(2)}\\ ..........................\\ ..........................\\ 1,x_1^{(n)},x_2^{(n)},....,x_n^{(n)}\\ \end{bmatrix}\begin{bmatrix} \theta_0\\ \theta_1\\ ....\\ ....\\ \theta_n\\ \end{bmatrix}$

$=\begin{bmatrix} \theta_0+\theta_1x_1^{(1)}+\theta_2x_2^{(1)}+....\theta_nx_n^{(1)}\\ \theta_0+\theta_1x_1^{(2)}+\theta_2x_2^{2)}+....\theta_nx_n^{(2)}\\ ........................................\\ .........................................\\ \theta_0+\theta_1x_1^{(n)}+\theta_2x_2^{(n)}+....\theta_nx_n^{(n)}\\ \end{bmatrix}$

$=\begin{bmatrix} h_\theta(x^{(1)})\\ h_\theta(x^{(2)})\\ ........\\ .......\\ h_\theta(x^{(n)})\\ \end{bmatrix}$

$X\theta$ 就表示所有样本下预测值的集合。

因此：

$J(\theta)=\frac{1}{2}\sum _{i=1}^m(h_\theta(x^{(i)})-y^{(i)})^2=\frac{1}{2} \sum _{i=1}^m((x^{(i)})^T\theta-y^{(i)})^2$

因此，最终问题转化为：

求解过程：求 $\theta$ 偏导，令偏导数为0。

处理矩阵微积分的规性质：

然后令这个式子等于0，就得到了下面式子：

正规方程： $X^{T}X\theta=X^TY$

这样我们就可以直接通过正规方程来求 $\theta$ ,这个 $\theta$ 就是使得代价函数最小的一系列参数。

正规方程形式回归求解示例：

已知如下数据：

$X=\begin{bmatrix} 1 ,2104,5\\ 1,1416,3\\ 1,1534,3\\ 1,852, 2\\ \end{bmatrix} \\ X^T=\begin{bmatrix} 1,1,1,1\\ 2104,1416,1534,852\\ 5,3,3,2\\ \end{bmatrix} \\ Y=\begin{bmatrix} 460\\ 232\\ 315\\ 178\\ \end{bmatrix}$

带入公式去求解即可。

重点梯度下降法：

举例：以LMS（最小均方法）的线性回归为例，最小化优化

$J(\theta)=\frac{1}{2}\sum _{i=1}^m(h_\theta(x^{(i)})-y^{(i)})^2$

关键因子的计算：

只考虑一个训练样本时

$J_\theta(x)=\frac{1}{2}\cdot(h_\theta(x)-y)^2$

$\frac{\partial }{\partial\theta_j}J(\theta)=\frac{\partial }{\partial\theta_j}\frac{1}{2}(h_\theta(x)-y)^2=2\cdot \frac{1}{2}(h_\theta(x)-y)\cdot\frac{\partial}{\partial\theta_j}(h_\theta(x)-y)$

$=(h_\theta(x)-y)\cdot\frac{\partial }{\partial \theta_j}(\theta_0+\theta_1x_1+\theta_2x_2+...\theta_nx_n-y)$

$=(h_\theta(x)-y)x_j$

然后更新迭代参数

$\theta_j:=\theta_j-\alpha (h_\theta(x)-y)x_j ,0\leq j\leq n$

参数的更新量：

$|\Delta \theta|=|-\alpha(h_\theta(x)-y)x_j|=|\alpha\cdot x_j|\cdot|h_\theta(x)-y|$

回归误差：指模型预测值 hθ(x)hθ(x) 与实际目标值 yy 之间的差异，即： $|h_\theta(x)-y|$

可见：

当推广到整个训练集时：

$J(\theta)=\frac{1}{2}\sum _{i=1}^m(h_\theta(x^{(i)})-y^{(i)})^2$

$\frac{\partial }{\partial\theta_j}J(\theta)=\frac{\partial }{\partial \theta_j}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})^2=\sum_{i=1}^m\frac{\partial }{\partial \theta_j}(h_\theta(x^{(i)})-y^{(i)})^2$

$=\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}$

$\theta_j:=\theta_j-\alpha\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}$

$=\theta_j+\alpha\sum_{i=1}^m(y^{(i)}-h_\theta(x^{(i)}))x_j^{(i)}$

SGD的好处：

计算效率高：每次更新只涉及一个样本，适合于大规模数据集。
可以在线学习：可以处理数据流或实时更新模型。
有助于跳出局部最小值：由于每次更新的随机性，有助于模型探索参数空间，可能跳出局部最小值。

BGD:扫描整个训练集后再更新参数，对于大样本问题，收敛较慢。

SGD:遇到一个样本后立即更新参数，但是可能发生震荡，导致无法收敛到最小值。

mini-batch梯度下降（小批量梯度下降）：如果不是每拿到一个样本即更改梯度，而是若干个样本的平均梯度作为更新方向，则是mini-batch梯度下降算法。意在结合BGD的稳定性和SGD的效率。

图示：

线性回归的全局极小值保证：一定有全局最优解，这由它的损失函数本身决定。

梯度下降法面临的挑战：

与线性回归不同，非线性问题可能存在多个局部极小值；在非线性问题中，梯度下降法可能会在局部极小值处停止，而不是全局极小值。这取决于初始参数的选择。

接近极小值时，梯度下降的更新速度会变得非常小，导致算法收敛速度变慢；

由于鞍点的梯度为0，可能会在鞍点停下，但是鞍点既不是全局极小值也不是局部极小值；

如果梯度下降法在局部最优点停止，那么它可能没有找到全局最优解，除非在这个函数中，局部全局一致。

动态学习率算法可以根据训练过程中的不同阶段自动调整学习率。例如，学习率可以在开始时较大，以便快速接近最优解，然后在接近最优解时减小，以便进行更精细的调整。常见的动态学习率算法包括学习率衰减、自适应学习率（如AdaGrad、RMSProp、Adam等）。

选择不同的学习率对梯度下降的影响：

左图（剖面）：不同学习率的收敛路径

右图（损失与参数更新次数的关系）：

横轴表示参数更新次数，纵轴表示损失值。
黄色曲线代表学习率非常大的情况，可以看到损失值在初期迅速下降，但随后可能出现震荡，甚至越过最小值，使得梯度朝着预期相反的方向走，导致无法收敛。
蓝色曲线代表学习率较小的情况，损失值下降速度较慢，但能够稳定地收敛到最小值。
绿色曲线代表学习率较大的情况，损失值下降较快，但同样可能出现震荡。
红色曲线代表理想情况下的学习率，损失值能够平稳且快速地下降并收敛。

右图目的使损失趋于最小，表现在左图就是朝着谷底下降。

比较正规方程法和梯度下降法（重点）

正规方程法的局限性比较大，因为不是所有的矩阵都可逆，而且求逆矩阵很耗时。

特征值较小：这里的表述可能是指当特征数量（即矩阵的维度）较小的时候，特征方程法更为适用。这是因为在特征数量较少时，矩阵求逆的计算成本相对较低，且更有可能得到稳定的解。

线性回归的概率解释：

考虑预测值、真实值、误差之间的关系，对于给定的真实值 $y^{(i)}$ 总能找到误差值 $\varepsilon ^{(i)}$ 使得等式成立：

$y^{(i)}=h_\theta(x^{(i)})+\varepsilon ^{(i)}$

$\rightarrow \varepsilon ^{(i)}(1\leq i\leq m)$ 作为随机变量，是独立同分布的，服从均值为0、方差为 $\delta^2$ 的高斯分布。

理论依据：

极大似然估计（Maximum Likelihood Estimation, MLE）是一种在已知数据生成过程的假设下，估计模型参数的方法。其基本思想是选择参数值，使得观测到的数据在这些参数下出现的概率最大。

写出似然函数，然后求出使得似然函数最大时 $\theta$ 的取值。

简化问题：

因此，最终通过最大似然估计求解 $\theta$ 的问题转化为了：

可见，最小二乘回归对应着参数 $\theta$ 的最大似然估计。

注意：概率假设绝不是使最小二乘法成为一种完全良好和合理的程序所必需的，而且确实存在——也可能有——其他自然假设也可以用来证明它是合理的。

非线性模型的多元回归：多元回归是一种统计分析方法，用于研究两个或多个自变量（特征变量）与因变量之间的关系。非线性模型则允许这种关系不是简单的直线关系，而是更复杂的曲线关系。

损失函数：

得到正规方程形式的解：

样本离群点：数据集中显著偏离其他观测值的点。可能由于测量错误、数据录入错误、实验误差或者它们确实代表了某种异常情况而存在。

离群点的处理需要根据具体情况和分析目的来决定。在某些情况下，离群点可能包含有价值的信息，而在其他情况下，它们可能会干扰分析结果。

重点：欠拟合与过拟合

回归模型中的欠拟合（Underfitting）和过拟合（Overfitting）是两种常见的问题，它们描述了模型对训练数据的拟合程度以及对新数据的泛化能力。

泛化能力：指模型对新数据（即模型训练过程中未见过的数据）的预测能力。

欠拟合与过拟合的比较
	欠拟合	过拟合
发生情况	发生在模型过于简单，无法捕捉到数据中的复杂关系时。	模型过于复杂，以至于它不仅学习了数据中的有效模式，还学习了噪声和随机波动。
在训练数据上的表现	不好，因为它没有足够的能力来学习数据中的模式。	可能非常好，因为它能够精确地拟合每一个数据点，包括那些由随机误差引起的异常点。
性能比较	具有较高的偏差，这意味着模型的预测值与实际值之间存在较大的系统性误差。欠拟合的模型在新数据上的泛化能力也较差，因为它没有从训练数据中学到足够的信息。	1.在新数据上的泛化能力很差，因为它学习到了训练数据中的特定细节，这些细节可能并不适用于新数据。 2.过拟合的模型通常具有较低的偏差但较高的方差，意味着模型的预测值在不同数据集上可能会有较大的波动。

例子：

减少欠拟合与过拟合的方法：结构风险最小化。

函数子集表示模型的复杂度逐渐增加。每个子集包含的函数数量越多，模型的表达能力越强。

VC维是衡量模型容量的一个指标，它表示模型能够正确分类的最大数据点数量。这里随着模型复杂度的增加，VC维也在增加。

结构风险最小化：在实际应用中，我们希望选择一个模型，它在经验风险和置信范围之间达到一个良好的平衡。这意味着我们需要在模型的复杂度和泛化能力之间找到一个折中点。

如何防止模型过拟合：正则化。

正则化是一种通过在损失函数中添加额外项来限制模型复杂度的方法，从而提高模型的泛化能力。

主要目的：控制模型复杂度；防止过拟合，提高泛化能力；提高模型稳定性，减少对噪音的敏感性。

第三章分类问题

分类问题：机器学习和统计学中的一种有监督学习任务。

其目标是将数据点分配到两个或多个预定义的类别或类标签中。模型根据输入数据的特征来预测其所属的类别。

特点：

输出是离散的：与回归问题（输出是连续的数值）不同，分类问题的输出是离散的类别标签。

类别是预先定义的：在训练模型之前，类别标签是已知的，模型需要学习如何根据输入特征来区分这些类别。

分类问题：硬分类和软分类。

软分类和硬分类
	硬分类	软分类
输出	离散的类别标签	输出是连续的，表示为属于某个类别的概率值
决策边界	明确的，它直接给出一个确定的类别	提供了更多的信息，因为它给出了一个概率估计，这可以用于更细致的决策制定
适用场景	适用于需要明确分类结果的场景	提供了关于分类不确定性的信息，适用于需要概率估计的场景
举例	以垃圾邮件过滤为例，模型会将邮件直接分类为垃圾邮件或非垃圾邮件。输出变量 y 通常取值为1或0，其中 y=1y表示正类（例如，垃圾邮件），y=0表示负类（例如，非垃圾邮件）。	在垃圾邮件过滤的例子中，模型会输出邮件是垃圾邮件的概率，这个概率值在0到1之间。可以设置概率多大时记录为垃圾邮件，多大时不记录。

注意：软分类的输出是连续的，但它表示的是样本属于某个类别的概率。即使输出值是连续的，它们仍然与类别标签相关联，只是提供了更细致的概率信息。在实际应用中，软分类的连续输出可以通过设定一个阈值来转换为硬分类的离散决策。例如，在二分类问题中，如果概率大于0.5，则可以将样本分类为正类；否则，分类为负类。

因此尽管软分类输出连续，但它依然是分类问题。

虽然传统的线性回归不适用于分类问题，但Logistic回归和Softmax回归是专门为分类任务设计的回归模型。它们通过使用特定的函数（如sigmoid或softmax）将线性回归的连续的输出转换为离散的类别概率，从而使得回归方法可以应用于分类问题。

逻辑回归（Logistic回归）是一种广泛使用的分类算法，它通过使用Logistic函数（或称为sigmoid函数）将线性回归的输出映射到0和1之间，从而可以表示类别的概率。

逻辑回归常用于二分类问题。

举例：

这个边界将特征空间分为两个区域，每个区域对应一个类别。
图片中的红色圆点（C-）和蓝色方块（C+）代表两个不同的类别。
根据Logistic回归的输出，如果 y>0，则预测为正类（positive label，蓝色方块）；如果 y<0，则预测为负类（negative label，红色圆点）。

如果特征变量数目为2，在空间图上可以理解为：

决策边界是这个超平面，将样本分成两部分。

逻辑回归模型的输出是一个介于0和1之间的概率值，表示样本属于正类（通常标记为1）的概率。这与单位阶跃函数的输出范围相似，后者是0或1。通过建立映射来架起线性回归和二分类问题的桥梁。

但是单位阶跃函数不连续，这里y只取到{0,0.5,1}，难以通过最大似然估计确定模型参数 $\theta$ 。

寻找一种效果和单位阶跃函数一致但是连续的函数：Sigmoid 函数（也叫logistic函数）

$Sigmoid function: y=\frac{1}{1+e^{-z}},z\epsilon R$

求解过程：

预测函数：

$Z=\theta^Tx=\theta_0+\sum_{j=1}^n\theta_jx_j$

带入到Logistic函数，得到回归模型的假设函数：

$h_\theta(x)=g(\theta^Tx)=\frac{1}{1+e^{-\theta^Tx}}$

这里 $h_\theta(x)$ 的输出结果就是“当前输入样本下，预测结果为正类的概率”

故属于正类的概率：

$p(y=1|x;\theta)=h_\theta(x)$

属于负类的概率：

$p(y=0|x;\theta)=1-h_\theta(x)$

那么随机变量 $y$ 的概率函数为：

$p(y|x:\theta)=h_\theta(x)^y\cdot(1-h_\theta(x))^{1-y}$

注意：

我们现在要求的就是使得对于整个数据集，使得 $h_\theta(x)$ 尽可能大，即划分为正类的概率尽可能大时，参数 $\theta$ 的取值。可以采用最大似然函数求。

假设有 $m$ 个样本，则最大似然函数：

对数化：

接下来有两种求法：

一种是人工直接求导，再令导函数等于0，

即有：

$h_\theta(x^{(i)})=y^{(i)}=g(\theta^Tx^{(i)})=\frac{1}{1+e^{-\theta^Tx^{(i)}}}$

据此来求出参数.

另一种常用的：梯度下降

因为这里实际上求似然函数最大值时的 $\theta$ 取值，因此其实是“梯度上升”，爬山法。

所以这里迭代公式的符号是正号。

这里采用随机梯度上升。

接下来计算梯度项：

计算一个样本时

重点

牛顿法求解似然函数的极大值

当参数量（特征变量数目）很大时候，因为要求逆矩阵，导致效率变慢。

模型评估方法和性能评价指标：

过拟合与欠拟合；样本集的划分（流出法，交叉验证，自助法）；

分类问题的性能评价指标：准确率；召回率；平均准确率；精确率；F1-Score

第四章神经网络

神经网络：一种模仿人脑神经元之间连接和交互方式的计算模型，它属于机器学习领域中的一个分支，称为深度学习。神经网络通过学习输入数据之间的复杂模式和关系来识别数据中的模式和特征。

人脑神经元：

神经元网络中各神经元之间联结的强弱，按外部的激励信号做自适应变化，而每个神经元又随着所接收到的多个信号的综合大小而呈现兴奋或抑制状态。

大脑的学习过程就是神经元之间连接强度随外部激励信息做自适应变化的过程，而大脑处理信息的结果则由神经元的状态表现出来。

什么是人工神经网络：

美国神经网络学者Nielsen的定义：人工神经网络是一个并行、分布处理结构，它由处理单元及其称为联接的无向讯号通道互连而成。

人工神经网络的特点：

并行结构和并行处理，知识的分布存储，容错性，自适应性。

人工神经元的形式化模型：

M-P模型，线性加权模型，阈值逻辑模型；

，

圆圈代表神经网络中的神经元，而圆圈内的参数 $\theta$ 表示该神经元的权重。

举例：

神经元的作用：

具体来说，这种神经元配置可以用于实现以下功能：

存储状态：通过兴奋性和抑制性输入的组合，神经元可以维持一个稳定的状态，直到受到新的输入信号。
记忆单元：神经元可以作为记忆单元，存储信息的“1”或“0”状态，这在构建神经网络和计算系统中非常有用。
逻辑门：神经元可以模拟逻辑门的功能，如与门（AND）、或门（OR）、非门（NOT）等，通过调整兴奋性和抑制性输入的权重和时间。

第六章支持向量机SVM

支持向量机：二类分类模型，基本模型是是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机。

支持向量机还包括核技巧（升维），这使它成为实质上的非线性分类器。

支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸二次规划(convex quadratic programming)的问题，也等价于正则化的Hinge 损失函数的最小化问题。支持向量机的学习算法是求解凸二次规划的最优化算法。

类型分类：

线性可分支持向量机（硬间隔；软间隔）

非线性支持向量机：当训练数据线性不可分时，通过使用核技巧(kernel trick)及软间隔最大化。

线性可分支持向量机：

什么是线性可分：：在二维空间上，如果两类点可以被一条直线（高维空间叫超平面）完全分开叫做线性可分。这个超平面可以将不同类别的数据点尽可能清晰地分隔开.

严格的数学定义：

例子：

在这个图中，如何选取合适的超平面？

找到最大Margins对应的平面;

设已经找到超平面： $w\cdot x+b=0$

当数据集线性可分时，存在一个超平面，使得所有属于同一类别的数据点都位于超平面的同一侧。这意味着对于所有的数据点 $(x_i,y_i)$ ，其中 $y_i$ 是数据点的类别标签（通常取 +1 或 -1,表示正负类），以下不等式成立：

$y_i\cdot (w\cdot x_i+b)>0$ .
因为当数据点 $(x_i,y_i)$ 来自正类时, $(w\cdot x_i+b)>0$ ,故 $1\cdot (w\cdot x_i+b)>0$ ;

来自负类时同理；

由此定义支持向量：到平面距离最小的样本点

让 $d^*$ 最大，即让 $w$ 最小，即等价于让 $w^2$ 最小。

得到最优超平面：

支持向量机的优化算法：

求解其对偶问题来优化。

若数据是线性可分的，则上述凸二次规划问题的解存在且唯一。二次规划问题有很多算法可以求解，也有很多求解器能直接解决二次规划问题。但是一般我们不直接求解原问题，而是求解其对偶问题。

强对偶性是指在某些条件下，原始问题的最优值等于对偶问题的最优值。在SVM中，由于问题是凸的，且满足Slater's condition（即存在一个点使得所有不等式约束严格成立），我们可以保证强对偶性成立。

分类器是一种算法或模型，它能够根据输入数据的特征来预测其类别或标签。在SVM中，分类器是基于找到的最优超平面构建的，它能够将新数据点正确地分类到相应的类别中。

优化步骤：

公式解释：

求解步骤描述：

这时候得到了一个仅仅关于 $\alpha$ 的式子；

求解最优 $\alpha$ 的分解算法：

软间隔最大化：

软间隔（Soft Margin）是支持向量机（SVM）中的一个概念，它与硬间隔（Hard Margin）相对应。在分类问题中，硬间隔SVM假设数据是线性可分的，即存在一个超平面可以完美地将不同类别的数据点分开，没有任何数据点位于超平面的错误一侧。然而，在现实世界中，大多数数据集并不是线性可分的，或者即使线性可分，也可能存在一些异常值或噪声。

软间隔SVM通过引入松弛变量（slack variables）来解决这个问题。松弛变量允许一些数据点违反分类规则，即允许它们位于超平面的错误一侧，但会为这些违反规则的数据点引入惩罚项。这样，SVM可以在最大化间隔和最小化分类错误之间找到一个平衡。

处理近似线性可分数据：

非线性支持向量机

核方法：

线性分类器的局限：有的情况下没法用线性函数划分

使用广义线性分类器的困难：

一般来讲，确定𝑥−>𝑧的映射函数φ(x)困难；

转换之后，存在维数灾难问题（维数过大）。

第七章聚类问题

聚类：最常见的无监督学习算法，它是按照某个特定标准（如数据间距离）把一个数据集分割成不同的类或簇，使得同一个簇内的数据对象的相似性尽可能大，同时不在同一个簇中的数据对象的差异性也尽可能地大。

聚类需要解决的问题：

定义数据间距离/相似度度量；

使用相应的算法对数据集进行分割；

度量聚类结果的性能；

如下图，假如特征变量有两个，按照某种规则将数据绘制在图上。根据点和点之间的距离来评价数据间的相似度。

曼哈顿距离：

欧氏距离：

闵可夫斯基距离：

$p$ 维空间的两点 $X=(x_1,x_2,x_3,....,x_n)$ 和 $Y=(y_1,y_2,y_3,....,y_n)$

$D(X,Y)=(|x_1-y_1|^p+|x_2-y_2|^p+....+|x_n-y_n|^p)^{\frac{1}{p}}$

余弦相似度和相关系数：

$r_{ij}$ 用来度量样本 $X$ 中特征变量 $x_i,x_j$ 之间的相关性。

聚类的主要类型：

划分聚类；层次聚类；密度聚类；网格法；模型法；谱聚法

基于划分的聚类:

给定包含N个点的数据集，划分法将构造K个分组，每个分组代表一个聚类，这里每个分组至少包含一个数据点，每个数据点属于且仅属于一个分组.

基于层次的聚类：将给定数据集进行逐层分解，直到满足某种条件为止，具体可分为“自底向上”和“自顶向下”两种方案。

举个例子：老师将全班同学进行男女兴趣小组聚类。

先分男女，再按兴趣科目分。

基于密度的聚类：不依赖于距离，而是依赖于密度，从而克服基于距离的算法只能发现“球形”聚簇的缺点（因为那些距离远的点可能不被聚在正确的簇）。只要一个区域中点的密度大于某个阈值，就把它加到与之相近的聚类中去。

基于模型的聚类：

给每一个聚类假定一个模型，然后去寻找能很好的拟合模型的数据集。

模型可能是数据点在空间中的密度分布函数或者其它。

数据集是由一系列的潜在概率分布生成的。

基于网格的聚类：

将数据空间划分成有限个单元的网格结构，所有的处理都是以单个的单元为对象。

重点算法：

K-means算法（K-means聚类，也称为K-平均或K-均值聚类）

假设某个簇 $j$ 的样本数为 $n$ ,则这个簇的损失函数为： $\sum_{i=1}^n|x_i^j-c_j|^2$ ,显然簇 $j$ 的损失函数就是其误差平方和。

那么总体的损失函数就是： $\sum_{j=1}^k\sum_{i=1}^n|x_i^j-c_j|^2$ .

关于K值的选取：

通常，随着K值的增加，SSE会减少，因为更多的聚类可以更好地拟合数据。

优点：

决聚类问题的一种经典算法，简单、快速；

对处理大数据集，该算法保持可伸缩性和高效率；

当结果簇是密集的，它的效果较好；

缺点：

只适合对数值型数据聚类；

必须事先给出k（要生成的簇的数目），而且对初值敏感，对于不同的初始值（簇中心点），可能会导致不同结果；

不适合于发现非凸面形状的簇或者大小差别很大的簇；

对噪声和孤立点数据敏感；

常常结合其他聚类算法使；

注意：可伸缩性（Scalability）是系统、网络或过程在大小、量级或范围上增加时，仍能保持其性能和效率的能力。

层次聚类方法（也叫系统聚类法）：

层次聚类法需要度量样本点之间的距离(dissimilarity) 和类与类之间的联接(linkage) 程度。

类与类之间的连接\l链接（linkage）是指用于确定不同聚类之间相似度或距离的准则。层次聚类不需要预先指定聚类的数量，而是通过逐步合并（聚合方法）或分裂（分裂方法）聚类来构建一个聚类层次结构。

层次聚类的结果通常用树状图来表示。

树状图的高度表示类与类之间的相异度（dissimilarity），高度越大，表示类之间的差异越大。

例如：

如果在高度0.6处切割，可能会得到2个主要的聚类。
如果在高度0.3处切割，可能会得到5个聚类，具体数量取决于在该高度上有多少个分支。

切割的高度越高，得到的聚类数量越少；切割的高度越低，得到的聚类数量越多。

聚合聚类算法：

1、输入所有样本，每个点为一个类；

2、计算相异度（距离）矩阵( $d_{ij}$ );

3、合并最小链接的两个类（即将两个差异度最小的类合并）；

4、计算新的类和其他所有类之间的链接大小；

5、重复3-4，直到所有类合并为一个类或者满足停止条件；

6、输出树状图，切割树状图得到聚类结果；

类间联系程度度量的方法：简单连接（single linkage 看最近）、完全连接（complete linkage 看最远）、平均连接、质心连接

第八章数据降维

什么是维数灾难：

维数灾难通常是指涉及到向量计算的问题中，随着维数的增加，计算量呈现指数倍增长的一种现象。（其实就是特征变量个数很多）

在很多机器学习问题中，每条数据经常具有很高的特征维度。如果直接使用原始的数据，不仅会让训练非常缓慢，还会影响模型的泛化性能。

为什么要降维？

数据降维可以使得数据集更易使用、确保变量之间彼此独立、算降低算法计算运成本、去除噪音;

数据降维常应用于文本处理、人脸识别、图片识别、自然语言处理等领域

什么是数据降维：

降维就是将训练数据中的样本从高维空间转换到低维空间，该过程和信息论中的有损压缩概念相似，完全无损的降维时不存在的。

数据降维是一种在机器学习和数据科学中常用的技术，目的是减少数据集中的特征数量，同时尽可能保留重要的信息。

降维方法分类：线性降维（基于核函数、基于流形）；非线性降维。

主成分分析算法（PCA）

用最直观的方式告诉你：什么是主成分分析PCA_哔哩哔哩_bilibili

主成分分析（Principal Component Analysis，简称PCA）是一种统计方法，它通过正交变换将一组可能相关的变量转换为一组线性不相关的变量，这些新变量称为主成分。PCA的目的是在尽可能保留原始数据集的变异性的同时，降低数据的维度。

PCA算法对重构和降维的要求：

重构的不同维度之间线性无关（正交、协方差为0）；

降维后所得维度的值尽可能分散（最大方差）；

PCA算法的推导：

这样使得坐标轴原点落在数据中心上。

左乘变换矩阵P，但此时我们并不知道P是什么，P现在只是我们假定的可以完美的进行降维处理的变换矩阵。我们的最终目标就是求P.

在降维时所需要满足的约束（这些约束使得降维的效果好，是关键）：

有两条，一条：方差最大化；一条：重构的维度之间线性无关。

（约束1）

因为这里的 $\mu _i$ 实际上已经是0，所以公式简化了。

什么是协方差：

协方差衡量的是两个变量的联合变异性。如果 X 和 Y 同时增加或减少，协方差为正；如果一个增加而另一个减少，协方差为负。

由协方差可以反应向量方向是否一致。

如果 X 和 Y完全正相关，即当 X 增加时 Y也增加，协方差为正。
如果 X 和 Y 完全负相关，即当 X 增加时 Y 减少，协方差为负。
如果 X 和 Y 之间没有线性关系，协方差接近于零。

（约束2）

注意， $Cov(y_i,y_j)=\frac{1}{m-1}\sum_{k=1}^my_{ik}\cdot y_{jk}=Cov(y_j,y_i)=\frac{1}{m-1}\sum_{k=1}^my_{jk}\cdot y_{ik}$ ;

将计算得到的所有协方差值填入矩阵，得到协方差矩阵：

$D=\begin{bmatrix} &Cov(y_1,y_1) &Cov(y_1,y_2) ..... &Cov(y1,y_k) \\ &Cov(y_2,y_1) &Cov(y_2,y_2) ..... &Cov(y2,y_k) \\ &Cov(y_3,y_1) &Cov(y_1,y_2) ..... &Cov(y3,y_k) \\ & ........ & .......& ........\\ &Cov(y_k,y_1) &Cov(y_k,y_2) ..... &Cov(yk,y_k) \end{bmatrix}\\\\\\\\\\\ =\begin{bmatrix} &Var(y_1) &Cov(y_1,y_2) ..... &Cov(y1,y_k) \\ &Cov(y_2,y_1) &Var(y_2) ..... &Cov(y2,y_k) \\ &Cov(y_3,y_1) &Cov(y_1,y_2) ..... &Cov(y3,y_k) \\ & ........ & .......& ........\\ &Cov(y_k,y_1) &Cov(y_k,y_2) ..... &Var(y_k) \end{bmatrix}$