几何建模与处理之一数据拟合

2023-12-30 21:38:58

几何建模与处理之一数据拟合

简单的基础概念和知识

集合

集合：一堆具有同样性质的对象（元素）
基数（个数）：集合中元素的个数
- 有限集
- 无限集
  - 可数集：自然数集N、有理数集Q
  - 不可数集：实数集R、无理数集R\Q
运算：交、并、差

线性空间

元素之间有运算：加法、数乘
线性结构：对加法和数乘封闭

加法交换律、结合律，数乘分配率
基/维数：

每个元素就表达（对应n个实数），即一个向量
例子：
- 欧式空间：1Ds实数、2D平面、3D空间
- n次多项式：$f(x)=\sum_{k=0}^na_kx^k$

映射（mapping）

两个非空集合A和B的映射$f:A\to B$：对A中的任何一个原数a，有唯一的一个B中的元素b与之对应，记为$f(a)=b$

b称为a的象，a作为b的原象
A称为定义域，B称为值域

函数（Function）

非空实数集之间的映射称为（一元）函数$y=f(x)$，或变换

函数的图像（函数的可视化）：所有有序对$(x,f(x))$组成的集合

常见一元函数：

? 幂函数三角函数对数函数指数函数三角函数反三角函数

函数空间

用若干简单函数（“基函数”）线性组合成一个函数空间

$L=span\lbrace f_1,\dots,f_n\rbrace=\lbrace \sum_{i=1}^na_if_i(x)|a_i\in R\rbrace$

每个函数就表达（对应）为n个实数，即系数向量

例如：

? 多项式函数空间$f(x)=\sum_{k=0}^nw_kx^k$

? 三角函数空间$f(x)=a_0+\sum_{k=1}^n(a_kcoskx+b_ksinkx)$

空间的完备性：函数空间是否可以表示（逼近）任意函数

赋范空间

内积诱导范数、距离 $<f,g>=\int_{a}^{b}f(x)g(x)dx$
度量空间：可度量函数之间的距离 Lp范数
赋范空间+完备性=巴拿赫空间
内积空间（无限维）+完备性=希尔伯特空间

万能逼近定理：Weierstrass逼近定理

定理一：闭区间上的连续函数可用多项式级数一致逼近
定理二：闭区间上周期为2π的连续函数可用三角函数级数一致逼近

对$[a,b]$上的任意连续函数g，及任意给定的$ \xi \gt 0 $，必存在n次代数多项式$f(x)=\sum_{k=0}^nw_kx_k$。使得 $min|f(x)-g(x)|<\xi$.

傅里叶级数

\[f(t)=A_0+\sum_{n=1}^∞[a_ncos(n\omega t)+b_nsin(n\omega t)]\f(t)=A_0+\sum_{n=1}^∞A_nsin(n\omega t+\psi_n) \]

大部分的实际应用问题，可建模为：找一个映射/变换/函数

如何找函数

1.到哪找?

? 确定某个函数集合/空间

2.找哪个？

? 度量哪个函数是好的/“最好”的

3.怎么找？

? 求解或优化

曲线/曲面拟合问题

输入：一些型值（采样）点集

输出：一条拟合这些点集的曲线/曲面

拟合（Fitting）问题

输入：一些观察的数据点

输出：反映这些数据规律的函数$y=f(x)$

到哪找

选择一个函数空间

线性函数空间$A=span\lbrace B_0(x),\dots,B_n(x)\rbrace$

多项式函数
RBF函数
三角函数

函数表达为

$f(x)=\sum_{k=0}^na_kB_k(x)$，求n+1个系数$(a_0,\dots,a_n)$

插值型

目标：函数经过每个数据点（插值）

$y_i=f(x_i),i=0,1,\dots,n$

联立，求解线性方程：$\sum_{k=0}^na_kB_k(x_i)=y_i,i=0,1,\dots,n$

求解(n+1)*(n+1)线性方程组
n次Lagrange插值多项式

Lagrange插值函数

插值n+1个点、次数不超过n的多项式是存在而且是唯一的（n+1个变量，n+1个方程）

\[p_k(x)=\prod_{i\in B_k}\frac{x-x_i}{x_k-x_i} \]

插值函数的*度=未知量个数-已知量个数

病态问题：系数矩阵条件数高时，求解不稳定

逼近型

目标：函数尽量靠近数据点（逼近）

$min\sum_{i=0^n}(y_i-f(x_i))^2$

对各系数求导，得法方程（线性方程组）：$AX=b$

最小二乘法

问题：点多，系数少；点少，系数多

拟合问题

过拟合（overfitting）

误差为0，但是拟合的函数并无使用价值

欠拟合（underfitting）

还存在欠拟合（underfitting）问题

需要根据不同的应用与需求，不断尝试（调参）

避免过拟合的常用方法

数据去噪

剔除训练样本中的噪声
数据增广

增加样本数，或者增加样本的代表性和多样性
模型简化

预测模型过于复杂，拟合了训练样本中的噪声

选用更简单的模型，或者对模型进行裁剪
正则约束

适当的正则项，比如方差正则项、稀疏正则项

岭回归正则项

最小二乘拟合

\[\min_W||Y-XW||^2 \]

Ridge regression（岭回归）

\[\min_W||Y-XW||^2+\mu||W||_2^2 \]

稀疏学习：稀疏正则化

冗余基函数（过完备）：选择的基函数过多

通过优化来选择合适的基函数

系数向量的 L0模（非0元素个数）尽量小
挑选（“学习”）出合适的基函数

\[\min_\alpha||Y-XW||^2+\mu||W||_0\\min_\alpha||Y-XW||^2,s.t.||W||_0 \le\beta \]

拟合算法

多项式插值

对于给定n个数据点（采样点），使用多项式函数（幂基函数的线性组合）进行插值：?

\[f(x)=\sum_{i=0}^{n-1}\alpha_i B_i(x)\\B_i(x)=x^i \]

将各数据点代入，得到如下方程组：

\[\begin{pmatrix}1&x_0&x_0^2&\ldots&x_0^{n-1}\\1&x_1&x_1^2&\ldots&x_1^{n-1}\\1&x_2&x_2^2&\ldots&x_2^{n-1}\\\vdots&\vdots&\vdots&\ddots&\vdots\\1&x_{n-1}&x_{n-1}^2&\ldots&x_{n-1}^{n-1}\\\end{pmatrix}\begin{pmatrix}a_0\\a_1\\a_2\\\vdots\\a_{n-1}\\\end{pmatrix}=\begin{pmatrix}y_0\\y_1\\y_2\\\vdots\\y_{n-1}\\\end{pmatrix} \]

Lagrange插值

Lagrange基函数：

\[l_i(x)=\prod_{j=0,j\ne i}\frac{x-x_j}{x_i-x_j} \]

Lagrange插值多项式：

\[L_n(x)=\sum_{k=0}^ny_kl_k(x) \]

Newton插值

定义：

一阶差商：

\[f[x_0,x_1]=\frac{f(x_1)-f(x_0)}{x_1-x_0} \]

k阶差商：

\[f[x_0,x_1,\dots,x_k]=\frac{f[x_1,\dots,x_k]-f[x_0,x_1,\dots,x_k]}{x_k-x_0} \]

Newton 插值多项式：

\[N_n(x)=f(x_0)+f[x_0,f_1](x-x_0)+\dots+f[x_0,x_1,\dots,x_k](x-x_0)\cdots(x-x_n-1) \]

Gauss基函数插值

对于给定n个数据点（采样点），使用Gauss基函数进行插值：

\[f(x)=a + \sum_{i=0}^{n-1}b_i g_i(x)\\g_i(x)=\exp\left(-\frac{(x-x_i)^2}{2\sigma^2}\right) \]

即对称轴在插值点上，$i=1,\dots,n$，缺省设 $\sigma =1$

将各个数据点代入：

\[\begin{cases}y_0=a+b_0g_0(x_0)+b_1g_1(x_0)+\dots+b_{n-1}g_{n-1}(x_0)\\y_1=a+b_0g_0(x_1)+b_1g_1(x_1)+\dots+b_{n-1}g_{n-1}(x_1)\\\vdots\\y_{n-1}=a+b_0g_0(x_{n-1})+b_1g_1(x_{n-1})+\dots+b_{n-1}g_{n-1}(x_{n-1})\\\end{cases} \]

未知数个数大于方程个数，方程有多个解，可以添加约束条件。

\[a=y_{average}\\y‘_i=y_i-y_{average} \]

得到方程组：

\[\begin{pmatrix}g_0(x_0)&g_1(x_0)&\ldots&g_{n-1}(x_{0})\\g_0(x_1)&g_1(x_1)&\ldots&g_{n-1}(x_{1})\\g_0(x_2)&g_1(x_2)&\ldots&g_{n-1}(x_{2})\\\vdots&\vdots&\vdots&\ddots&\vdots\\g_{0}(x_{n-1})&g_{1}(x_{n-1})&\ldots&g_{n-1}(x_{n-1})\\\end{pmatrix}\begin{pmatrix}b_0\\b_1\\b_2\\\vdots\\b_{n-1}\\\end{pmatrix}=\begin{pmatrix}y‘_0\\y‘_1\\y‘_2\\\vdots\\y‘_{n-1}\\\end{pmatrix} \]

转化为求解：$Ax=b$

Gauss插值函数：

\[G_n(x)=a+\sum_{i=0}^{n-1}b_ig_i(x_i) \]

最小二乘法

在多项式插值中，当数据点个数较多时，插值多项式的阶数过高，求解不稳定。可以通过幂基函数的最高次数m（m<n），使用最小二乘法拟合：

\[f(x)=\sum_{i=0}^{m}a_iB_i(x)\\B_i(x)=x^i\\\min E\\E(x)=\sum_{i=0}^{n-1}(y_i-f(x_i))^2 \]

矩阵形式：

\[\begin{pmatrix}1&x_0&x_0^2&\ldots&x_0^{m}\\1&x_1&x_1^2&\ldots&x_1^{m}\\1&x_2&x_2^2&\ldots&x_2^{m}\\\vdots&\vdots&\vdots&\ddots&\vdots\\1&x_{n-1}&x_{n-1}^2&\ldots&x_{n-1}^{m}\\\end{pmatrix}\begin{pmatrix}a_0\\a_1\\a_2\\\vdots\\a_{m}\\\end{pmatrix}=\begin{pmatrix}y_0\\y_1\\y_2\\\vdots\\y_{n-1}\\\end{pmatrix} \]

即$Aa=Y$，B是一个非方阵，且列满秩，方程无精确解。采用最小二乘方式，

\[A^TAa=A^TY \]

解上述等式。

m次多项式曲线：

\[f(x)=a_0+a_1x+a_2x^2+\dots+a_mx^m \]

岭回归

在最小二乘求解中，当$B^TB$接近于奇异时，$(B^TB)^{-1}$有较大误差，拟合结果不稳定。为此在最小二乘的误差函数中添加$E_1$正则项 ,参数 $\lambda$，$\min (E+\lambda E_1)$，其中 $E_1=\sum_{i=1}^n\alpha_i^2$ ，则

\[\min_a(\sum_{i=0}^{n-1}(y_i-\sum_{i=0}^ma_ix^i)^2)+\lambda \sum_{i=0}^ma^2 \]

求偏导，并令其等于0，得

\[2A^TY-2A^TAa-2\lambda a=0\\a=(B^TB+\lambda I)^{-1}B^TY \]

m 次多项式曲线

\[f(x)=a_0+a_1x+a_2x^2+\dots+a_mx^m \]

几何建模与处理之一数据拟合

码农公寓

几何建模与处理之一 数据拟合

简单的基础概念和知识

集合

线性空间

映射（mapping）

函数（Function）

函数空间

赋范空间

万能逼近定理：Weierstrass逼近定理

傅里叶级数

拟合（Fitting）问题

到哪找

插值型

逼近型

拟合问题

过拟合（overfitting）

欠拟合（underfitting）

避免过拟合的常用方法

拟合算法

多项式插值

Lagrange插值

Newton插值

Gauss基函数插值

最小二乘法

岭回归

相关文章

几何建模与处理之一数据拟合