几何建模与处理之一 数据拟合
简单的基础概念和知识
集合
- 集合：一堆具有同样性质的对象（元素）
- 基数（个数）：集合中元素的个数
- 有限集
- 无限集
- 可数集：自然数集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\)
函数表达为
\(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
\]
稀疏学习：稀疏正则化
冗余基函数（过完备） ：选择的基函数过多
通过优化来选择合适的基函数
拟合算法
多项式插值
对于给定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
\]
几何建模与处理之一 数据拟合
原文：https://www.cnblogs.com/YIMG/p/15042008.html
