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

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

简单的基础概念和知识

集合

  • 集合:一堆具有同样性质的对象(元素)
  • 基数(个数):集合中元素的个数
    • 有限集
    • 无限集
      • 可数集:自然数集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 \]

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

上一篇:每日一练-leetcode


下一篇:DevExpress中ChartControl柱状图(Bar)用法