八、回归模型

1、数据分析之回归分析

回归分析属于机器学习中的一种重要方法，主要用于从数据中自动分析获得规律，并利用这些规律对未知数据进行预测。机器学习方法可以分为监督学习、无监督学习、半监督学习以及其他学习方法等。回归分析通常属于监督学习，因为训练数据中既包含输入变量，也包含对应的输出结果。

回归分析是一种用于预测的建模技术，研究的是因变量或目标变量与自变量或预测变量之间的关系。它的基本目标是产生一个函数，将已有数据映射到一个实值预测变量上，从而对未知情况进行估计。

例如，如果已知某家上市公司每天的股价数据，就可以利用当前和过去的信息建立回归模型，进而预测公司未来股价走势。回归分析主要关注数据序列的趋势特征，以及变量之间的相关关系。

2、基本回归方法

回归分析的基本思想是：推求一个解析函数 $y=f(x)$，使它通过或近似通过有限序列的数据点，并在某种意义下“最佳”地逼近已知数据。

对于一元回归问题，已知平面上的一组数据点：

$$(x_i,y_i),i=1,2,\cdots ,n$$

其中 $x_i$ 互不相同。现在希望寻找一个函数或曲线：

$$y=f(x)$$

使得 $f(x)$ 在某种准则下与所有数据点最为接近，也就是曲线拟合得最好。

如果第 $i$ 个数据点的误差记为：

$${\delta }_i=f(x_i)-y_i$$

则常用的拟合准则是让误差平方和最小：

$$\sum _{i=1}^n{\delta }_i^2=\sum _{i=1}^n{\left[f(x_i)-y_i\right]}^2$$

因此，回归问题可以理解为：选择一个合适的函数 $f(x)$，使上式达到最小。

3、曲线函数类型的选择

在回归分析中，需要先确定用什么样的函数或曲线进行拟合。常见的选择方法有两类：一是通过画图观察数据点的大致趋势；二是根据问题背景进行理论分析，选择与实际规律相适应的函数形式。

常用的曲线函数类型包括：

直线：

$$y=a_{1}x+a_2$$

多项式：

$$y=a_1{x}^m+\cdots +a_{m}x+a_{m+1}$$

双曲线的一支：

$$y=\frac{a_1}{x}+a_2$$

指数曲线：

$$y=a_1{e}^{a_{2}x}$$

选择函数形式时，既要考虑拟合效果，也要考虑函数是否符合实际问题的背景规律。

4、线性回归 Linear Regression

线性回归中，因变量是连续变量，自变量可以是连续变量，也可以是离散变量。线性回归的特点是回归线具有线性形式。

一元线性回归模型通常写为：

$$Y=b_0+b_{1}X+u$$

其中，$Y$ 是因变量，$X$ 是自变量，$b_0$ 是截距项，$b_1$ 是回归系数，$u$ 是误差项。

线性回归的核心问题是：如何得到一条最佳回归线。所谓“最佳”，通常指这条直线到所有数据点的误差平方和最小。

5、线性回归中系数的确定

设拟合函数为：

$$f(x)=a_{1}x+a_2$$

对于数据点 $(x_i,y_i)$，预测值为 $a_1{x}_i+a_2$，误差为：

$$(a_1{x}_i+a_2)-y_i$$

因此，代价函数可以写为：

$$J(a_1,a_2)=\sum _{i=1}^n{\delta }_i^2=\sum _{i=1}^n{\left[(a_1{x}_i+a_2)-y_i\right]}^2$$

要求最佳直线，就需要确定 $a_1,a_2$，使 $J(a_1,a_2)$ 达到最小。

根据极值的必要条件，对参数分别求偏导，并令偏导数为 $0$：

$$\{\begin{array}{l}\frac{\partial J}{\partial a_1}=2{\sum }_{i=1}^n\left[(a_1{x}_i+a_2)-y_i\right]x_i=0,\\ \frac{\partial J}{\partial a_2}=2{\sum }_{i=1}^n\left[(a_1{x}_i+a_2)-y_i\right]=0.\end{array}$$

化简后得到关于 $a_1,a_2$ 的线性方程组：

$$\{\begin{array}{l}{a}_1{\sum }_{i=1}^n{x}_i^2+a_2{\sum }_{i=1}^n{x}_i={\sum }_{i=1}^n{x}_i{y}_i,\\ a_1{\sum }_{i=1}^n{x}_i+n{a}_2={\sum }_{i=1}^n{y}_i.\end{array}$$

解这个方程组即可得到最小二乘意义下的最佳直线参数 $a_1,a_2$。

6、多元线性回归模型 Multiple Linear Regression

现实生活中，引起被解释变量变化的因素往往不止一个。例如，人均国民生产总值可能受到人口变动因素、固定资产数、货币供给量、物价指数、国内国际市场供求关系等多种因素影响。

因此，在一元线性回归模型的基础上，可以建立多元线性回归模型。多元线性回归模型中，一个因变量与多个自变量之间设定为线性关系，解释变量个数大于等于 $2$。

多元线性回归模型的一般形式为：

$$Y=b_0+b_1{X}_1+b_2{X}_2+\cdots +b_k{X}_k+u$$

其中，$Y$ 是因变量，$X_1,X_2,\cdots ,X_k$ 是多个自变量，$b_0,b_1,\cdots ,b_k$ 是需要估计的模型参数，$u$ 是误差项。

7、多元线性回归例题

例：27 名糖尿病人的血清总胆固醇、甘油三脂、空腹胰岛素、糖化血红蛋白、空腹血糖的测量值如下，试建立血糖与其他几项指标关系的多元线性回归方程。

其中，$X_1$ 表示总胆固醇，$X_2$ 表示甘油三脂，$X_3$ 表示胰岛素，$X_4$ 表示糖化血红蛋白，$Y$ 表示血糖。

序号 $i$	总胆固醇 $X_1$	甘油三脂 $X_2$	胰岛素 $X_3$	糖化血红蛋白 $X_4$	血糖 $Y$
1	5.68	1.90	4.53	8.2	11.2
2	3.79	1.64	7.32	6.9	8.8
3	6.02	3.56	6.95	10.8	12.3
4	4.85	1.07	5.88	8.3	11.6
5	4.60	2.32	4.05	7.5	13.4
6	6.05	0.64	1.42	13.6	18.3
7	4.90	8.50	12.60	8.5	11.1
8	7.08	3.00	6.75	11.5	12.1
9	3.85	2.11	16.28	7.9	9.6
10	4.65	0.63	6.59	7.1	8.4
11	4.59	1.97	3.61	8.7	9.3
12	4.29	1.97	6.61	7.8	10.6
13	7.97	1.93	7.57	9.9	8.4
14	6.19	1.18	1.42	6.9	9.6
15	6.13	2.06	10.35	10.5	10.9
16	5.71	1.78	8.53	8.0	10.1
17	6.40	2.40	4.53	10.3	14.8
18	6.06	3.67	12.79	7.1	9.1
19	5.09	1.03	2.53	8.9	10.8
20	6.13	1.71	5.28	9.9	10.2
21	5.78	3.36	2.96	8.0	13.6
22	5.43	1.13	4.31	11.3	14.9
23	6.50	6.21	3.47	12.3	16.0
24	7.98	7.92	3.37	9.8	13.2
25	11.54	10.89	1.20	10.5	20.0
26	5.84	0.92	8.61	6.4	13.3
27	3.84	1.20	6.45	9.6	10.4

建立如下多元线性回归方程：

$$\hat{Y}=f(X)=b_0+b_1{X}_1+b_2{X}_2+b_3{X}_3+b_4{X}_4=XB$$

其中，$\hat{Y}$ 表示预测血糖值，$B=(b_0,b_1,b_2,b_3,b_4{)}^T$ 表示待估计参数。

对应的代价函数为：

$$J(B)=\sum _{i=1}^{27}{e}_i^2=\sum _{i=1}^{27}(Y_i-{\hat{Y}}_i{)}^2$$

展开为：

$$J(B)=\sum _{i=1}^{27}{\left[Y_i-(b_0+b_1{X}_{1i}+b_2{X}_{2i}+b_3{X}_{3i}+b_4{X}_{4i})\right]}^2$$

令代价函数对参数的偏导数为 $0$：

$$\frac{\partial J(B)}{\partial B}=0$$

求得最后的多元回归方程为：

$$\hat{Y}=5.9433+0.1424X_1+0.3515X_2-0.2706X_3+0.6382X_4$$

该模型表示，在其他变量不变的情况下，各个指标通过对应回归系数影响血糖预测值。

8、多元线性回归的矩阵形式

对于 $n$ 个样本、$k$ 个自变量的多元线性回归模型，可以写成矩阵形式：

$$Y=XB+U$$

其中：

$$Y=\left[\begin{array}{c}{Y}_1\\ Y_2\\ ⋮\\ Y_n\end{array}\right],X=\left[\begin{array}{ccccc}1& X_{11}& X_{21}& \cdots & X_{k1}\\ 1& X_{12}& X_{22}& \cdots & X_{k2}\\ ⋮& ⋮& ⋮& \cdots & ⋮\\ 1& X_{1n}& X_{2n}& \cdots & X_{kn}\end{array}\right]$$

$$B=\left[\begin{array}{c}{b}_0\\ b_1\\ b_2\\ ⋮\\ b_k\end{array}\right],U=\left[\begin{array}{c}{u}_1\\ u_2\\ ⋮\\ u_n\end{array}\right]$$

模型参数的确定仍然基于最小二乘法。代价函数为：

$$J=\sum _{i=1}^n{e}_i^2=\sum _{i=1}^n(Y_i-{\hat{Y}}_i{)}^2$$

也就是：

$$J=\sum _{i=1}^n{\left(Y_i-b_0-b_1{X}_{1i}-\cdots -b_k{X}_{ki}\right)}^2$$

分别对 $b_0,b_1,\cdots ,b_k$ 求偏导，并令其等于 $0$，可以得到正规方程组。其矩阵形式为：

$$X^{T}X\hat{B}=X^{T}Y$$

如果 $X^{T}X$ 是满秩矩阵，存在逆矩阵，则参数估计为：

$$\hat{B}=(X^{T}X{)}^{-1}{X}^{T}Y$$

在许多现实任务中，$X^{T}X$ 可能不是满秩矩阵，或者存在多重共线性，导致参数估计不稳定。此时常见做法是引入正则化，得到：

$$\hat{B}(\lambda )=(X^{T}X+\lambda I{)}^{-1}{X}^{T}Y$$

其中，$\lambda$ 是正则化系数，$I$ 是单位矩阵。

9、线性回归的要点

线性回归的主要要点包括：

1. 自变量与因变量之间应具有线性关系。
2. 线性回归对异常值非常敏感，异常值可能严重影响回归线，从而影响预测值。
3. 多元线性回归中可能存在多重共线性，即自变量之间相互关联。多重共线性会增加系数估计值的方差，使模型在轻微变化下估计结果非常敏感，导致系数不稳定。
4. 在多个自变量的情况下，可以使用向前选择法、向后剔除法和逐步筛选法来选择较重要的自变量。

10、多项式回归模型 Polynomial Regression

多项式回归是在线性回归思想上的扩展。它使用多项式函数拟合数据，可以表示更复杂的非线性关系。

一般的多项式形式可以写为：

$$y=a_1{x}^m+\cdots +a_{m}x+a_{m+1}$$

也可以写成参数形式：

$$f(x,w)=\sum _{j=0}^M{w}_j{x}^j$$

其中，$M$ 表示多项式次数，$w_j$ 是模型参数。$M$ 的选择决定了模型复杂度。

多项式逼近连续函数的理论基础之一是 Weierstrass 第一逼近定理：设 $f(x)$ 是闭区间 $[a,b]$ 上的连续函数，则对于任意给定的 $\epsilon >0$，存在多项式 $P(x)$，使得：

$$|P(x)-f(x)|<\epsilon$$

对一切 $x\in [a,b]$ 成立。

这个定理说明，在闭区间上的连续函数可以用多项式进行任意精度的逼近。

11、多项式回归的训练目标

假设训练数据集为：

$$T=\{(x_1,y_1),(x_2,y_2),\cdots ,(x_N,y_N)\}$$

其中，$x_i$ 是输入 $x$ 的观测值，$y_i$ 是相应输出 $y$ 的观测值。

目标是通过多项式拟合，选择一个对已知数据以及未知数据都有较好预测能力的函数。

设 $M$ 次多项式为：

$$f(x,w)=\sum _{j=0}^M{w}_j{x}^j$$

采用最小二乘法，代价函数为：

$$L(w)=\frac{1}{2}\sum _{i=1}^N{\left[f(x_i,w)-y_i\right]}^2$$

通过最小化 $L(w)$，可以求得拟合多项式的参数 $w$。

12、多项式次数与欠拟合、过拟合

给定一组训练数据点，可以分别用 $M=0,1,3,9$ 次多项式进行拟合。

当 $M=0$ 时，多项式曲线是一个常数，模型过于简单，数据拟合效果很差。

当 $M=1$ 时，多项式曲线是一条直线，如果数据本身呈现明显非线性趋势，则拟合效果也较差。

这两种情况都可能属于欠拟合，即模型复杂度太低，不能充分描述数据规律。

当 $M=9$ 时，多项式曲线可以通过每一个训练数据点，训练误差为 $0$。从训练数据拟合角度看效果最好，但由于训练数据本身可能存在噪声，这种曲线对未知数据的预测能力往往不是最好。

这种情况属于过拟合，即模型过于复杂，对训练数据拟合过度，但泛化能力较差。

当 $M=3$ 时，多项式曲线对训练数据拟合效果较好，同时模型复杂度也较低，通常是较好的选择。

13、使用回归分析的优势

使用回归分析有两个主要优势：

1. 它可以表明自变量和因变量之间是否存在显著关系。
2. 它可以表明多个自变量对某个因变量的影响强度。

因此，回归分析不仅可以用于预测，也可以用于解释变量之间的关系。

14、回归技术的主要度量

选择和评价回归技术时，通常需要考虑以下几个方面：

1. 自变量的个数。
2. 因变量的类型。
3. 解析函数 $f$ 的选取。

这些因素会影响模型形式、参数估计方法以及最终预测效果。

15、一般回归问题的常规求解步骤

一般回归问题的常规求解步骤可以概括为三步：

第一步，寻找 $h$ 函数，即假设函数 hypothesis，用来表示输入和输出之间的关系。

第二步，构造 $J$ 函数，即代价函数，用来度量模型预测值与真实值之间的差异。

第三步，使 $J$ 函数最小，并求得回归参数 $\theta$。

也就是说，回归建模的核心过程是：

$$h(x)\to J(\theta )\to \min J(\theta )$$

16、最小二乘法 Least Square Method

代价函数中常用的均方误差，本质上对应了欧式距离。基于均方误差最小化进行模型求解的方法称为最小二乘法。

对于一组数据点，最小二乘法的目标是：

$$\sum _{i=1}^n{\delta }_i^2=\sum _{i=1}^n{\left[f(x_i)-y_i\right]}^2$$

即通过最小化误差平方和，寻找数据的最佳函数匹配。

最小二乘法可以从不同角度理解：

从微积分角度看，最小二乘法通过对代价函数求导，得到全局极值，从而估计参数。

从计算数学角度看，它是一个线性优化问题，目标是寻找一个最优解。

从线性代数角度看，它是在求解线性方程组。当方程个数不等于未知量个数时，最小二乘法试图找到最优残差。

从几何角度看，它的意义是高维空间中的一个向量在低维子空间上的投影。

从概率论角度看，如果数据的观测误差满足高斯分布，则最小二乘解就是使观测数据出现概率最大的解，即最大似然估计 MLE。

17、过拟合和模型选择

当模型具有不同复杂度时，例如参数个数不同，就需要进行模型选择。理想情况下，希望选择一个模型来逼近真实模型。

如果一味追求提高模型对已知数据的预测能力，所选模型的复杂度往往会比真实模型更高，从而产生过拟合。

过拟合是指：所选模型包含的参数过多，以至于该模型对已知数据预测得很好，但对未知数据预测很差。

模型选择的目标是避免过拟合，并提高模型对未知数据的预测能力。

过拟合问题往往源自过多的特征。常见解决方法有两类：

第一，减少特征数量。可以通过人工选择或模型选择算法保留重要特征，但减少特征可能会丢失部分信息。

第二，使用正则化。正则化保留所有特征，但通过限制参数大小来降低模型复杂度，在特征较多时比较有效。

18、正则化方法

正则化是结构风险最小化策略的一种实现方法，其基本思想是在经验风险上加入一个正则化项或惩罚项。

一般来说，正则化项是模型复杂度的单调递增函数。模型越复杂，正则化项越大，因此优化时会对复杂模型进行惩罚。

正则化后的目标函数通常可以理解为：

$$\text{目标函数}=\text{经验损失}+\text{模型复杂度惩罚}$$

这样可以在拟合训练数据和控制模型复杂度之间取得平衡。

19、岭回归 Ridge Regression

岭回归是一种用于处理多重共线性数据的技术。当自变量之间高度相关时，普通最小二乘法得到的系数估计可能不稳定，标准误差较大，观测值容易偏离真实值。

岭回归通过给回归估计增加惩罚项，降低标准误差，从而得到更稳定的参数估计。

回顾普通线性方程：

$$Y=a+bX$$

加入误差项后，完整形式为：

$$Y=a+bX+e$$

多元线性形式为：

$$Y=a+b_1{x}_1+b_2{x}_2+\cdots +b_n{x}_n+e$$

在线性模型中，预测误差可以分解为偏差和方差两个部分。预测错误可能来自偏差，也可能来自方差，或者二者共同作用。

岭回归的目标函数为：

$$\arg \underset{\beta \in R^p}{\min }\left\{\Vert y-X\beta {\Vert }_2^2+\lambda \Vert \beta {\Vert }_2^2\right\}$$

其中，$\Vert y-X\beta {\Vert }_2^2$ 是最小二乘损失项，$\lambda \Vert \beta {\Vert }_2^2$ 是惩罚项，$\lambda$ 是正则化系数。

岭回归的目的是通过惩罚较大的参数值，降低模型方差，使模型更稳定。

20、偏差与方差

偏差 Bias 描述预测值或估计值与真实值之间的差距。偏差越大，模型预测结果越偏离真实数据。

方差 Variance 描述预测值的变化范围和离散程度。方差越大，说明模型预测结果越分散，对数据变化越敏感。

可以用打靶的例子理解偏差和方差：

图 1：方差小，偏差小。子弹集中在目标位置附近，这是较理想的情况。

图 2：方差大，偏差小。子弹总体围绕目标，但分布不集中。

图 3：方差小，偏差大。子弹很集中，但集中位置远离目标。

图 4：方差大，偏差大。子弹既不集中，也远离目标。

岭回归主要希望通过正则化降低方差，从而提升模型对未知数据的预测稳定性。

21、正则化系数的影响

正则化系数 $\lambda$ 控制惩罚项的强弱。

如果 $\lambda$ 很大，说明对模型复杂度的惩罚较大，对拟合数据损失的容忍度较高。此时模型不会过分拟合训练数据，在训练数据上的偏差可能较大，在未知数据上的方差较小，但也可能出现欠拟合。

如果 $\lambda$ 很小，说明模型更注重对训练数据的拟合。此时训练数据上的偏差较小，但可能导致过拟合，使模型在未知数据上表现较差。

岭回归的特点包括：

1. 除常数项以外，其基本假设与最小二乘回归类似。
2. 它会收缩回归系数的值，但通常不会将系数压缩到 $0$。
3. 因为系数一般不会变成 $0$，所以岭回归本身没有特征选择功能。
4. 岭回归属于正则化方法，使用的是 $L2$ 正则化。

22、Lasso 回归

Lasso 回归的全称是 Least Absolute Shrinkage and Selection Operator。它与岭回归类似，也会对回归系数进行惩罚，但惩罚的是系数绝对值的大小。

Lasso 回归的目标函数为：

$$\arg \underset{\beta \in R^p}{\min }\left\{\Vert y-X\beta {\Vert }_2^2+\lambda \Vert \beta {\Vert }_1\right\}$$

其中，$\Vert y-X\beta {\Vert }_2^2$ 是损失项，$\lambda \Vert \beta {\Vert }_1$ 是 $L1$ 正则化惩罚项。

Lasso 与 Ridge 的重要区别在于惩罚函数不同。Ridge 使用平方惩罚，Lasso 使用绝对值惩罚。这会导致 Lasso 的一些参数估计结果变为 $0$。

从几何上看，Ridge 的约束域是圆形，Lasso 的约束域是菱形。系数估计值由约束区域与最小二乘损失等高线第一次相交的位置决定。岭回归的相交点一般不会出现在坐标轴上，而 Lasso 更容易在坐标轴上相交，因此会得到稀疏解。

Lasso 回归的特点包括：

1. 它可以将部分系数收缩到接近 $0$，甚至等于 $0$，因此有助于特征选择。
2. 它属于正则化方法，使用的是 $L1$ 正则化。
3. 如果一组预测变量高度相关，Lasso 往往会选出其中一个变量，并将其他变量的系数收缩为 $0$。
4. 它可以用于防止过拟合。

23、ElasticNet 回归

ElasticNet 是 Lasso 和 Ridge 回归技术的混合体。它同时使用 $L1$ 正则化和 $L2$ 正则化。

ElasticNet 的目标函数可以写为：

$$\arg \underset{\beta }{\min }\left\{\Vert y-X\beta {\Vert }_2^2+{\lambda }_1\Vert \beta {\Vert }_1+{\lambda }_2\Vert \beta {\Vert }_2^2\right\}$$

其中，${\lambda }_1\Vert \beta {\Vert }_1$ 对应 Lasso 的 $L1$ 惩罚，${\lambda }_2\Vert \beta {\Vert }_2^2$ 对应 Ridge 的 $L2$ 惩罚。

当存在多个相关特征时，ElasticNet 比单独使用 Lasso 或 Ridge 更有用，因为它既可以进行一定程度的特征选择，又能保持对相关变量的稳定处理。

除了线性回归、岭回归、Lasso 和 ElasticNet 之外，还有一些常见的回归技术，例如生存回归、泊松回归、Bayesian 回归、Ecological 回归和 Robust 回归。

24、逻辑回归 Logistic Regression

逻辑回归用于计算“事件 = Success”和“事件 = Failure”的概率。当因变量属于二元变量时，例如 $1/0$、真/假、是/否，就可以使用逻辑回归。

虽然逻辑回归名字中包含“回归”，但它主要用于二分类问题。它的输出值通常表示某个样本属于正类的概率，取值范围为 $0$ 到 $1$。

假设样本为 $(x,y)$，其中 $y$ 取值为 $0$ 或 $1$，表示负类或正类；$x$ 是 $m$ 维样本特征向量。样本 $x$ 属于正类，也就是 $y=1$ 的概率可以表示为：

$$P(y=1|x;\theta )=\sigma ({\theta }^{T}x)=\frac{1}{1+\exp (-{\theta }^{T}x)}$$

其中，$\theta$ 是模型参数，也就是回归系数，$\sigma$ 是 sigmoid 函数。

对应地：

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

线性回归可以写成 $f(x)=w^{T}x$，而逻辑回归是在 $w^{T}x$ 的基础上通过 sigmoid 函数进行非线性转换，使输出变成概率：

$$f(x)=P(y=1|x,w)=g(w^{T}x)$$

25、逻辑回归的极大似然估计

在逻辑回归中，通常通过观测样本的极大似然估计来选择参数。

假设有 $n$ 个独立训练样本：

$$\{(x_1,y_1),(x_2,y_2),\cdots ,(x_n,y_n)\}$$

其中 yi∈{0,1}y_i\in\{0,1\}yi​∈{0,1}。令：

$$p_i=P(y_i=1|x_i)$$

则每一个观察到的样本 $(x_i,y_i)$ 出现的概率可以写为：

$$P(y_i|x_i)=p_i^{y_i}(1-p_i{)}^{1-y_i}$$

因为每个样本相互独立，所以整个样本集出现的似然函数为：

$$L(\theta )=\prod _{i=1}^n{p}_i^{y_i}(1-p_i{)}^{1-y_i}$$

极大似然法就是求使似然函数 $L(\theta )$ 取值最大的参数 ${\theta }^{\ast }$。

为了便于计算，通常对似然函数取自然对数。设：

$$\varphi (x_i)=P(y_i=1|x_i)$$

则对数似然函数为：

$$L(\theta )=\sum _{i=1}^N\left[y_i\log (\varphi (x_i))+(1-y_i)\log (1-\varphi (x_i))\right]$$

对数似然函数的导数可以写成：

$$\frac{\partial L(\theta )}{\partial \theta }=\sum _{i=1}^N\left[y_i-\varphi (x_i)\right]x_i$$

令导数为 $0$ 时，一般不能直接得到解析解，因此通常需要使用迭代优化方法求解。

如果令：

$$L_{\text{new}}(\theta )=-L(\theta )$$

则最大化 $L(\theta )$ 的问题可以转化为最小化 $L_{\text{new}}(\theta )$ 的问题。

26、梯度与梯度下降法

在优化问题中，需要理解几个基本数学概念。

数学概念	几何意义
导数	函数在该点的瞬时变化率
偏导数	函数在坐标轴方向上的变化率
方向导数	函数在某点沿某个特定方向的变化率
梯度	函数在该点所有方向导数中最大的方向导数对应的方向

梯度方向是函数值增长最快的方向，负梯度方向是函数值减小最快的方向。因此，如果要寻找函数的最小值，就可以沿负梯度方向不断更新参数。

梯度下降法是一种利用一阶梯度信息寻找函数局部最优解的方法，也是机器学习中最简单、最常用的优化方法之一。

其基本思想是：要找最小值，只需要每一步都往下降的方向走，使代价函数逐步变小，最终到达最小值附近。

逻辑回归中，梯度下降的更新公式可以写为：

$${\theta }^{t+1}={\theta }^t-\alpha \frac{\partial L_{\text{new}}(\theta )}{\partial \theta }$$

对于逻辑回归，也可以写成：

$${\theta }^{t+1}={\theta }^t+\alpha \sum _{i=1}^n\left[y_i-\sigma (({\theta }^t{)}^T{x}_i)\right]x_i$$

其中，$\alpha$ 是学习率，表示每一步走多远。经验上，开始迭代时可以使用较大的学习率，随着参数逐渐接近最优值，学习率可以变小。

需要注意的是，不同初始点可能会导致计算出的极小值不同。

27、随机梯度下降法 SGD

普通梯度下降算法在每次更新回归系数时，都需要遍历整个数据集，计算整个数据集上的回归误差。对于小数据集，这种方法可以使用；但当样本数量达到数十亿、特征数量达到成千上万时，计算复杂度会过高。

随机梯度下降法 SGD 的改进思想是：一次只使用一个样本点的回归误差来更新回归系数。

也就是说，普通梯度下降使用全部样本更新一次参数，而随机梯度下降使用单个样本更新一次参数。

由于随机梯度下降可以在新样本到来时对分类器进行增量更新，所以它属于在线学习算法。

例如，假设已经在数据库 $A$ 上训练好分类器 $h$。如果新来一个样本 $x$，对于非增量学习算法，需要将 $x$ 与数据库 $A$ 混合成新的数据库 $B$，再重新训练分类器；而对于增量学习算法，只需要用新样本 $x$ 更新已有分类器 $h$ 的参数即可。

与在线学习相对应，一次处理整个数据集的方法称为批处理。

28、其他优化算法

除了梯度下降法和随机梯度下降法，还有一些常见优化算法：

1. Conjugate gradient method，共轭梯度法。
2. Quasi-Newton method，拟牛顿法。
3. BFGS method。
4. L-BFGS，Limited-memory BFGS。

与梯度下降算法相比，这些算法的优点是：

1. 不需要手动选择步长。
2. 通常比梯度下降算法更快。

缺点是算法本身更加复杂。

29、逻辑回归的要点

逻辑回归的主要要点包括：

1. 逻辑回归不要求自变量和因变量之间是线性关系。它可以处理不同类型的关系，因为它对预测的相对风险指数使用了非线性的对数转换。
2. 为了避免过拟合和欠拟合，应该包含所有重要变量。可以使用逐步筛选方法来估计逻辑回归模型。
3. 逻辑回归通常需要较大的样本量。样本数量较少时，极大似然估计的效果可能比普通最小二乘法差。
4. 如果因变量的值是定序变量，则称为序逻辑回归。
5. 如果因变量是多类变量，则称为多元逻辑回归。
6. Logistic 回归虽然名字中带有“回归”，但实际上主要用于两分类问题，即输出只有两种类别。

30、模型选择

模型选择时，需要同时考虑模型对已知数据的预测能力和对未知数据的预测能力。

如果模型复杂度太低，训练误差和测试误差都可能较高，这通常对应高偏差、低方差的情况。

随着模型复杂度增加，训练误差通常会持续下降。但是测试误差不一定持续下降。测试误差往往会先下降，达到某个较低点后又上升。

因此，模型选择的目标不是让训练误差最小，而是选择复杂度适当的模型，使测试误差最小。

可以概括为：

$$\text{选择复杂度适当的模型，使测试误差最小}$$

31、25年题：试给出一种回归模型，并给出一般回归问题损失函数的定义，基于损失函数，介绍模型求解参数的基本方法。

解答：

可以选取多元线性回归模型作为一种典型的回归模型。设因变量为 $Y$，自变量为 $X_1,X_2,\cdots ,X_k$，则多元线性回归模型可以表示为：

$$Y=b_0+b_1{X}_1+b_2{X}_2+\cdots +b_k{X}_k+u$$

其中，$b_0$ 为常数项，$b_1,b_2,\cdots ,b_k$ 为回归系数，$u$ 为误差项。对于第 $i$ 个样本，其预测值为：

$${\hat{Y}}_i=b_0+b_1{X}_{1i}+b_2{X}_{2i}+\cdots +b_k{X}_{ki}$$

回归问题的目标是选择合适的参数，使预测值 ${\hat{Y}}_i$ 尽可能接近真实值 $Y_i$。因此，需要定义损失函数来度量预测值与真实值之间的误差。

一般回归问题常用的损失函数是误差平方和，即：

$$J=\sum _{i=1}^n{e}_i^2=\sum _{i=1}^n(Y_i-{\hat{Y}}_i{)}^2$$

将多元线性回归模型代入，可得：

$$J(b_0,b_1,\cdots ,b_k)=\sum _{i=1}^n{\left[Y_i-(b_0+b_1{X}_{1i}+b_2{X}_{2i}+\cdots +b_k{X}_{ki})\right]}^2$$

这个损失函数表示所有样本预测误差平方的总和。损失函数越小，说明模型对数据的拟合效果越好。因此，回归模型参数求解的基本思想就是：寻找一组参数 $b_0,b_1,\cdots ,b_k$，使损失函数 $J$ 取得最小值。

基于损失函数，求解参数的基本方法是最小二乘法。具体做法是对损失函数分别关于各个参数求偏导，并令偏导数等于 $0$：

$$\{\begin{array}{l}\frac{\partial J}{\partial b_0}=0,\\ \frac{\partial J}{\partial b_1}=0,\\ \cdots \\ \frac{\partial J}{\partial b_k}=0.\end{array}$$

这样可以得到关于 $b_0,b_1,\cdots ,b_k$ 的方程组，解这个方程组即可得到使损失函数最小的模型参数。

若使用矩阵形式表示，设：

$$Y=XB+U$$

其中，$Y$ 为因变量向量，$X$ 为样本自变量矩阵，$B$ 为待求参数向量，$U$ 为误差向量。此时损失函数可以写为：

$$J(B)=(Y-XB{)}^T(Y-XB)$$

对 $B$ 求导并令导数为 $0$，得到正规方程：

$$X^{T}X\hat{B}=X^{T}Y$$

如果 $X^{T}X$ 存在逆矩阵，则参数解为：

$$\hat{B}=(X^{T}X{)}^{-1}{X}^{T}Y$$

这就是基于最小二乘法求解线性回归参数的基本公式。

如果 $X^{T}X$ 不可逆，或者自变量之间存在较强相关性，可以引入正则化方法，例如岭回归。其参数求解形式为：

$$\hat{B}(\lambda )=(X^{T}X+\lambda I{)}^{-1}{X}^{T}Y$$

其中，$\lambda$ 为正则化系数，$I$ 为单位矩阵。正则化可以降低模型参数的不稳定性，并在一定程度上缓解过拟合问题。

综上，一般回归问题的求解过程可以概括为：先根据问题选择合适的回归模型，再定义损失函数来度量预测误差，最后通过最小化损失函数求解模型参数。

九、习题与谱聚类

1、通信卫星的覆盖面积

题目：一颗地球同步通信卫星的轨道位于地球的赤道平面内，且可以认为是圆轨道。通信卫星运行的角速率与地球自转的角速率相同，即人们看到它在天空不动。若地球半径为 $R=6400\text{km}$，问卫星距地面的高度 $h$ 应为多少？试计算通信卫星的覆盖面积。

解析一：先求同步通信卫星离地面的高度。

设地球半径为 $R$，卫星到地心的距离为 $r$，则卫星距地面的高度为：

$$h=r-R$$

在地球表面，由万有引力等于重力可得：

$$\frac{km}{R^2}=mg$$

因此：

$$k=g{R}^2$$

当卫星绕地球做圆周运动时，引力提供向心力。卫星受到的引力为：

$$F=mg{\left(\frac{R}{r}\right)}^2$$

圆周运动的向心力为：

$$F=m{\omega }^{2}r$$

其中同步卫星的角速度等于地球自转角速度：

$$\omega =\frac{2\pi }{24\times 3600}$$

令引力等于向心力：

$$mg{\left(\frac{R}{r}\right)}^2=m{\omega }^{2}r$$

化简得：

$$r^3=\frac{g{R}^2}{{\omega }^2}$$

所以：

$$r={\left(\frac{g{R}^2}{{\omega }^2}\right)}^{1/3}$$

从而卫星距地面的高度为：

$$h={\left(\frac{g{R}^2}{{\omega }^2}\right)}^{1/3}-R$$

代入 $g=9.8{\text{m/s}}^2$，$R=6400\text{km}=6.4\times 10^6\text{m}$，可得：

$$h\approx 3.6\times 10^7\text{m}=36000\text{km}$$

结论：地球同步通信卫星距地面的高度约为 $36000\text{km}$。

解析二：再求通信卫星能够覆盖的地球表面积。

卫星能够覆盖的区域可以看成地球表面上由视线切线围成的球冠区域。设覆盖区域对应的球面为 $\Sigma$，则覆盖面积可写为：

$$S={\iint }_{\Sigma }dS$$

其中 $\Sigma$ 是上半球面：

$$x^2+y^2+z^2=R^2,z\ge 0$$

被圆锥角所限定的部分。

将球面写成：

$$z=\sqrt{R^2-x^2-y^2}$$

则球面面积微元为：

$$dS=\sqrt{z_x^2+z_y^2+1}dxdy$$

计算偏导后可得：

$$dS=\frac{R}{\sqrt{R^2-x^2-y^2}}dxdy$$

设投影区域为 $D$，利用极坐标变换：

$$x=r\cos \theta ,y=r\sin \theta$$

则面积为：

$$S={\int }_0^{2\pi }d\theta {\int }_0^{R\sin \beta }\frac{Rr}{\sqrt{R^2-r^2}}dr$$

即：

$$S=2\pi R{\int }_0^{R\sin \beta }\frac{r}{\sqrt{R^2-r^2}}dr$$

由几何关系可得：

$$\cos \beta =\frac{R}{R+h}$$

球冠面积最终化为：

$$S=4\pi R^2\cdot \frac{h}{2(R+h)}$$

其中 $4\pi R^2$ 是整个地球表面积，因此一颗同步通信卫星覆盖面积占地球表面积的比例为：

$$\frac{S}{4\pi R^2}=\frac{h}{2(R+h)}$$

代入 $R=6400\text{km}$，$h\approx 36000\text{km}$，可得：

$$\frac{S}{4\pi R^2}\approx 0.425$$

并且覆盖面积约为：

$$S\approx 2.19\times 10^8{\text{km}}^2$$

结论：一颗同步通信卫星约可覆盖地球表面积的 $42.5\%$，覆盖面积约为 $2.19\times 10^8{\text{km}}^2$。因此，使用三颗通信卫星就可以覆盖几乎全部地球表面。

2、矩阵的意义与价值

2.1、矩阵是简化表示的工具

在线性代数中，矩阵可以把复杂的线性方程组写成紧凑形式。例如线性方程组：

$$\{\begin{array}{l}{a}_{11}{x}_1+a_{12}{x}_2+\cdots +a_{1n}{x}_n=b_1,\\ a_{21}{x}_1+a_{22}{x}_2+\cdots +a_{2n}{x}_n=b_2,\\ \cdots \\ a_{m1}{x}_1+a_{m2}{x}_2+\cdots +a_{mn}{x}_n=b_m\end{array}$$

可以写成矩阵形式：

$$Ax=b$$

其中：

$$A\in {\mathbb{R}}^{m\times n},x\in {\mathbb{R}}^n,b\in {\mathbb{R}}^m$$

矩阵不仅可以表示方程组，还可以用于构造函数。例如二次型可写为：

$$f(x)=x^{T}Ax$$

这种写法将多个变量之间的关系压缩到一个矩阵中，便于统一研究。

价值：矩阵可以用类似“数”的方式来表达和研究方程组、数据关系以及线性变换等对象，是从一维到高维、从简单到复杂的重要工具。

2.2、矩阵可以记录和加工二维数组

在推荐系统中，用户对产品的喜好程度可以用一个二维表格表示。例如用户对音乐的评分可以组成评分矩阵：

$$Y=\left(\begin{array}{ccccc}5& 2& ?& 3& \cdots \\ 4& 5& ?& ?& \cdots \\ ?& 2& 3& 1& \cdots \\ ⋮& ⋮& ⋮& ⋮& \ddots \end{array}\right)$$

其中行可以表示不同音乐，列可以表示不同用户，数字表示评分，问号表示缺失评分。推荐系统的任务之一，就是根据已有评分推测缺失评分，从而为用户推荐感兴趣的产品。

2.3、“阶”和“维”是信息表示中的两个基本概念。

一阶信息通常对应向量。若有 $m$ 个数据，则可写为：

$$a=(a_1,a_2,\cdots ,a_m{)}^T\in {\mathbb{R}}^m$$

二阶信息通常对应矩阵。若有 $n$ 个向量作为列向量，则可写为：

$$A=(a_1,a_2,\cdots ,a_n)\in {\mathbb{R}}^{m\times n}$$

更高阶的信息可以用张量表示。例如三阶张量可以写成若干矩阵的组合：

$$\mathcal{A}=[A_1;A_2;\cdots ;A_k]\in {\mathbb{R}}^{m\times n\times k}$$

从信息表示的角度看，向量、矩阵和张量分别对应不同复杂程度的数据结构。向量适合表示一维数据，矩阵适合表示二维数据，张量适合表示更高阶的数据。

2.4、自然对象可以通过矩阵数字化。

黑白图像可以看成一个矩阵，矩阵中的每个元素表示图像中一个像素的灰度值。彩色图像通常可以分解为 $R$、$G$、$B$ 三个通道，每个通道对应一个灰度矩阵，因此彩色图像可以看成三个矩阵的组合。

视频可以看成按时间顺序排列的一组图像，因此可以表示为若干矩阵的序列。高光谱图像也可以看成多个通道矩阵叠加而成的数据结构。

结论：矩阵把自然对象转化为可计算、可存储、可运算的数字形式，是图像、视频和推荐系统等问题的基础表示工具。

3、线性代数中的运算及其启示

3.1、运算的本质是映射，是不同信息之间的作用规则。

向量加法可以看成如下映射：

$${\mathbb{R}}^n\times {\mathbb{R}}^n\to {\mathbb{R}}^n,(x,y)\mapsto x+y$$

若：

$$x=(x_1,x_2,\cdots ,x_n{)}^T,y=(y_1,y_2,\cdots ,y_n{)}^T$$

则：

$$x+y=(x_1+y_1,x_2+y_2,\cdots ,x_n+y_n{)}^T$$

向量内积可以看成如下映射：

$${\mathbb{R}}^n\times {\mathbb{R}}^n\to \mathbb{R},(x,y)\mapsto x^{T}y$$

具体为：

$$x^{T}y=(x_1,x_2,\cdots ,x_n)\left(\begin{array}{c}{y}_1\\ y_2\\ ⋮\\ y_n\end{array}\right)=\sum _{i=1}^n{x}_i{y}_i$$

内积可以反映两个向量之间的相互作用，例如向量夹角、向量长度等信息。

3.2、矩阵运算可以看成二阶信息之间的相互作用。

矩阵加法为：

$${\mathbb{R}}^{m\times n}\times {\mathbb{R}}^{m\times n}\to {\mathbb{R}}^{m\times n},(A,B)\mapsto A+B$$

若：

$$A=(a_{ij}{)}_{m\times n},B=(b_{ij}{)}_{m\times n}$$

则：

$$A+B=(a_{ij}+b_{ij}{)}_{m\times n}$$

矩阵乘法为：

$${\mathbb{R}}^{m\times k}\times {\mathbb{R}}^{k\times n}\to {\mathbb{R}}^{m\times n},(A,B)\mapsto AB$$

其元素形式为：

$$AB={\left(\sum _{l=1}^k{a}_{il}{b}_{lj}\right)}_{m\times n}$$

矩阵乘法体现了二阶信息之间的组合关系，因此在方程组求解、线性变换和数据建模中都非常重要。

3.3、外积是一种由低阶信息生成高阶信息的运算。

设：

$$x=(x_1,x_2,\cdots ,x_m{)}^T,y=(y_1,y_2,\cdots ,y_n{)}^T$$

定义外积为：

$$x\circ y=\left(\begin{array}{cccc}{x}_1{y}_1& x_1{y}_2& \cdots & x_1{y}_n\\ x_2{y}_1& x_2{y}_2& \cdots & x_2{y}_n\\ ⋮& ⋮& \ddots & ⋮\\ x_m{y}_1& x_m{y}_2& \cdots & x_m{y}_n\end{array}\right)=x{y}^T$$

外积可以把两个向量组合成一个矩阵，即由低阶信息之间的相互作用得到高阶信息。

矩阵的特征分解也可以用外积形式理解：

$$A={\lambda }_1{v}_1{v}_1^T+{\lambda }_2{v}_2{v}_2^T+\cdots +{\lambda }_n{v}_n{v}_n^T$$

其中 ${\lambda }_i$ 是特征值，$v_i$ 是对应的特征向量。该表达式说明矩阵可以看成若干个向量外积的加权组合。

3.4、Kronecker 型积可以推广外积思想。

若：

$$A=(a_{ij})\in {\mathbb{R}}^{m\times n},B\in {\mathbb{R}}^{k\times l}$$

则 Kronecker 型积可以写成分块矩阵：

$$A\otimes B=\left(\begin{array}{cccc}{a}_{11}B& a_{12}B& \cdots & a_{1n}B\\ a_{21}B& a_{22}B& \cdots & a_{2n}B\\ ⋮& ⋮& \ddots & ⋮\\ a_{m1}B& a_{m2}B& \cdots & a_{mn}B\end{array}\right)$$

这种运算可以看成矩阵与矩阵之间的更高阶组合，用于把低阶信息的相互作用扩展到高阶信息表示中。

4、实例：矩阵建模

4.1、视频前景背景分离。

视频前景背景分离的目标是将视频分成相对稳定的背景和运动的前景。若将视频的每一帧看作一个向量，则一个视频可以看作矩阵：

$$Y=(y_1,y_2,\cdots ,y_m)$$

其中 $y_i$ 表示第 $i$ 帧图像向量。由于背景通常较稳定，所以背景矩阵 $L$ 往往具有低秩性质；而运动前景只占图像中的少量区域，所以前景矩阵 $E$ 往往具有稀疏性质。

因此可以建立模型：

$$\underset{L,E}{\min }\mathrm{rank}(L)+\lambda \Vert E{\Vert }_0$$

约束条件为：

$$Y=L+E$$

其中 $\Vert E{\Vert }_0$ 表示矩阵 $E$ 中非零元素的个数。

由于秩函数和 ${\ell }_0$ 范数通常不便直接优化，可以用核范数和 ${\ell }_1$ 范数进行替代，得到松弛模型：

$$\underset{L,E}{\min }\Vert L{\Vert }_{\ast }+\lambda \Vert E{\Vert }_1$$

约束条件为：

$$Y=L+E$$

其中 $\Vert L{\Vert }_{\ast }$ 表示 $L$ 的奇异值之和，$\Vert E{\Vert }_1$ 表示 $E$ 中所有元素绝对值之和。

结论：视频前景背景分离可以转化为低秩矩阵与稀疏矩阵的分解问题。

4.2、推荐系统与矩阵修补。

推荐系统的基本思想是：根据用户对产品的喜好程度，结合使用记录以及社交关系，为用户推荐感兴趣的产品。评分数据通常可以写成一个矩阵，但这个矩阵往往含有大量缺失值。

设评分矩阵为 $Y$，已知评分位置的指标集合为 $\Omega$。矩阵修补问题的目标是寻找一个完整矩阵 $\hat{Y}$，使其在已知评分位置上与原矩阵一致：

$${\hat{Y}}_{\Omega }=Y_{\Omega }$$

由于用户之间的喜好存在相似性，产品之间也存在相似性，所以完整评分矩阵往往具有低秩性。因此可以建立模型：

$$\underset{\hat{Y}}{\min }\mathrm{rank}(\hat{Y})$$

约束条件为：

$${\hat{Y}}_{\Omega }=Y_{\Omega }$$

由于秩函数不便直接优化，可以进一步松弛为核范数优化问题：

$$\underset{\hat{Y}}{\min }\Vert \hat{Y}{\Vert }_{\ast }$$

约束条件为：

$${\hat{Y}}_{\Omega }=Y_{\Omega }$$

结论：推荐系统中的评分预测可以转化为矩阵修补问题，其核心思想是利用低秩性补全缺失评分。

5、谱聚类的基本思想

5.1、谱聚类问题的出发点。

聚类的目标是对给定数据集按照相似性进行分组，使得同一组内的数据点比较“密”，不同组之间的数据点比较“疏”。这类问题通常属于无监督学习中的模式识别问题。

谱聚类的基本出发点是：先用数据点构造一张无向加权图，再把聚类问题转化为图的分割问题。图中的每个顶点表示一个数据点，边的权重表示两个数据点之间的相似程度。

5.2、构造图与确定权重。

设数据点为 $x_1,x_2,\cdots ,x_n$，图中顶点之间的权重为 $w_{ij}$。权重越大，表示两个数据点越相似；权重越小，表示两个数据点越不相似。

一种常用方法是 $K$ 近邻法：

$$w_{ij}=w_{ji}=\{\begin{array}{ll}\exp \left(-\frac{\Vert x_i-x_j{\Vert }^2}{2{\sigma }^2}\right),& \text{若 }{x}_i\in KNN(x_j)\text{ 或 }{x}_j\in KNN(x_i),\\ 0,& \text{否则}\end{array}$$

另一种方法是全连接法：

$$w_{ij}=w_{ji}=\exp \left(-\frac{\Vert x_i-x_j{\Vert }^2}{2{\sigma }^2}\right)$$

所有权重组成权重矩阵，也称相似性矩阵：

$$W=\left(\begin{array}{cccc}{w}_{11}& w_{12}& \cdots & w_{1n}\\ w_{21}& w_{22}& \cdots & w_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ w_{n1}& w_{n2}& \cdots & w_{nn}\end{array}\right)$$

无向图中顶点 $i$ 的度定义为与该顶点相连的边权重之和：

$$d_i=\sum _j{w}_{ij}$$

度矩阵为对角矩阵：

$$D=\left(\begin{array}{cccc}{d}_1& 0& \cdots & 0\\ 0& d_2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & d_n\end{array}\right)$$

结论：谱聚类首先要把数据点之间的相似性转化为图上的边权重，并由此得到权重矩阵 $W$ 和度矩阵 $D$。

5.3、图割准则与拉普拉斯矩阵。

谱聚类中的图分割准则是：使得被删掉的边的权重之和尽可能小。设要把数据点分成 $k$ 类：

$$A_1,A_2,\cdots ,A_k$$

则“最小割”问题可写为：

$$\underset{A_1,\cdots ,A_k}{\min }\sum _{l=1}^k\sum _{i\in A_l,j\notin A_l}{w}_{ij}$$

其中 $A_l$ 表示第 $l$ 个子图包含的顶点指标集。

定义第 $l$ 类对应的示性向量：

ql=(q1l,q2l,⋯ ,qnl)T∈{−1,1}n q_l=(q_{1l},q_{2l},\cdots,q_{nl})^T\in\{-1,1\}^n ql​=(q1l​,q2l​,⋯,qnl​)T∈{−1,1}n

其中：

$$q_{il}=\{\begin{array}{ll}1,& \text{若 }i\in A_l,\\ -1,& \text{若 }i\notin A_l\end{array}$$

令：

$$Q=(q_1,q_2,\cdots ,q_k)$$

定义图拉普拉斯矩阵：

$$L=D-W$$

则图割问题可以写成：

$$\underset{Q}{\min }\mathrm{Tr}(Q^{T}LQ)$$

约束条件为：

qil∈{−1,1} q_{il}\in\{-1,1\} qil​∈{−1,1}

其中 $\mathrm{Tr}(\cdot )$ 表示矩阵的迹，即矩阵对角线元素之和。

5.4、图割目标与迹形式的关系。

为了说明图割目标可以写成迹形式，只需证明图割权重和 $\mathrm{Tr}(Q^{T}LQ)$ 成比例。

对第 $l$ 类，有：

$$\sum _{i\in A_l,j\notin A_l}{w}_{ij}=\frac{1}{4}\sum _{i=1}^n\sum _{j=1}^n{w}_{ij}(q_{il}-q_{jl}{)}^2$$

因此：

$$\sum _{l=1}^k\sum _{i\in A_l,j\notin A_l}{w}_{ij}=\frac{1}{4}\sum _{l=1}^k\sum _{i=1}^n\sum _{j=1}^n{w}_{ij}(q_{il}-q_{jl}{)}^2$$

展开平方项：

$$\frac{1}{4}\sum _{l=1}^k\sum _{i=1}^n\sum _{j=1}^n{w}_{ij}(q_{il}^2-2q_{il}{q}_{jl}+q_{jl}^2)$$

根据 $d_i={\sum }_j{w}_{ij}$，可化为：

$$\frac{1}{4}\sum _{l=1}^k\left(2\sum _{i=1}^n{d}_i{q}_{il}^2-2\sum _{i=1}^n\sum _{j=1}^n{w}_{ij}{q}_{il}{q}_{jl}\right)$$

即：

$$\frac{1}{2}\sum _{l=1}^k\left(q_l^{T}D{q}_l-q_l^{T}W{q}_l\right)$$

所以：

$$\sum _{l=1}^k\sum _{i\in A_l,j\notin A_l}{w}_{ij}=\frac{1}{2}\sum _{l=1}^k{q}_l^T(D-W)q_l$$

由于 $L=D-W$，因此：

$$\sum _{l=1}^k\sum _{i\in A_l,j\notin A_l}{w}_{ij}=\frac{1}{2}\mathrm{Tr}(Q^{T}LQ)$$

常数因子 $\frac{1}{2}$ 不影响最小化问题，因此最小割问题可以等价转化为最小化 $\mathrm{Tr}(Q^{T}LQ)$。

结论：谱聚类把图割问题转化为拉普拉斯矩阵上的迹最小化问题。

6、谱聚类的松弛与求解

6.1、整数约束问题直接求解不方便。

原始问题为：

$$\underset{Q}{\min }\mathrm{Tr}(Q^{T}LQ)$$

约束条件为：

qil∈{−1,1} q_{il}\in\{-1,1\} qil​∈{−1,1}

由于 $q_{il}$ 只能取 $1$ 或 $-1$，这是一个整数约束问题，直接求解通常比较困难。因此可以将其放松为实数约束问题。

先将约束写成向量长度约束：

$$\underset{Q}{\min }\mathrm{Tr}(Q^{T}LQ),s.t.q_l^T{q}_l=n,l=1,\cdots ,k$$

进一步归一化后写成：

$$\underset{Q}{\min }\mathrm{Tr}(Q^{T}LQ),s.t.q_l^T{q}_l=1,l=1,\cdots ,k$$

若还要求不同列向量之间正交，则可统一写成：

$$\underset{Q}{\min }\mathrm{Tr}(Q^{T}LQ),s.t.Q^{T}Q=I$$

这是一个标准的特征值问题。根据线性代数中的结论，上述问题的解对应于 $L$ 的最小特征值对应的特征向量。

结论：松弛后的谱聚类问题可以通过计算拉普拉斯矩阵的特征值和特征向量来求解。

6.2、特征向量的选择。

由于：

$$v=(1,1,\cdots ,1{)}^T$$

满足：

$$Lv=0$$

所以 $v$ 是 $L$ 的特征值 $0$ 对应的特征向量。这个向量本身不能有效区分数据类别，因此在将数据聚为 $k$ 类时，通常需要计算最小的前 $k+1$ 个特征值及其对应特征向量，再去掉常数特征向量，保留有分类信息的特征向量用于聚类。

6.3、谱聚类过程。

谱聚类的基本过程可以概括为以下三步：

1）构建表示对象集相似度的矩阵 $W$。

2）通过计算相似度矩阵或拉普拉斯矩阵的前 $k$ 个特征值与特征向量，构建特征向量空间。

3）利用 $K$-means 或其他经典聚类算法，对特征向量空间中的特征向量进行聚类。

结论：谱聚类不是直接在原始数据空间中聚类，而是先通过图和特征向量构造新的表示空间，再在该空间中完成聚类。

6.4、谱聚类例子。

对于螺旋形数据集，直接在原始坐标空间中使用简单距离进行聚类可能不容易得到理想结果。谱聚类先根据数据点之间的相似性构造图，再利用拉普拉斯矩阵的特征向量形成新的表示空间，最后在特征向量空间中进行聚类，因此能够把螺旋形数据分成不同类别。

结论：谱聚类的核心优势在于，它通过图结构和特征向量提取数据的整体结构信息，从而处理一些普通距离聚类不容易分开的数据形状。