如需转载请联系听云College团队成员小尹 邮箱:yinhy#tingyun.com
摘要
本文讨论多项式拟合的实时计算,这里实时计算表示为,每一次的传入一个数据以及上一次计算的结果,并返回更改拟合曲线的各个参数,并给出两种算法尝试,在计算量的基础上优化算法,主要以启发为主,欢迎讨论,分享优秀的计算方法。希望对前端图形计算工程师和数据分析师能有一定的帮助。
假设读者已经熟知期望,协方差的定义,以及矩阵的简单计算,并了解以下性质。
从实时线性拟合说起
设点希望能拟合出一条直线使点到线的距离和最小,假设直线方程为,那么就可以根据公式
分别计算出就可以计算出k,计算出联立方程
可分别计算出k和b,所以问题被转化为了实时计算,期中
其中
因为
所以
令可得
对于只需要改变上面函数中的项即可
对于也只需要修改对应的参数即可
扩展到实时多项式拟合
幂次为2时开始,此时假设直线方程为,原理同上有
联立方程
此时2个方程3个未知数无法求解参数,引入并联立
转化为增广矩阵求解问题
推广到幂次为q时可以获得矩阵
另外矩阵中,在计算矩阵中每个元素时,只需要计算相同部分即可。
计算量分析
算法一
每个协方差都用如下公式进行计算
我们一共所需要计算的期望有
共项,可利用公式进行计算。
若用键值对来表示每一步加法和乘法的数量,则
同时内存中需要存储各个期望的值而不用存储协方差的值
算法二
每个协方差采用增量方程进行计算
我们所需要计算的中间变量有共项,其中,所需要计算的期望有
共项
阵计算中,协方差行,所有项均有项,可以舍弃不影响结果
计算量
n=0时,实际上是在求.
延伸出的其他应用
1)不同数据集合并
更一般的,我们在计算量个集合合并后的方差时,记两个样本集合,集合大小分别是n和m,现已知两个集合的协方差。
其中
又因为
所以
综上
对于多个集合的合并,参考上面推导过程,简写为
对于不同集合协方差,可以在不同主机上进行计算并按此公式进行合并,其中k表示k个集合,表示每个集合的大小。
2)改变输入数据的符号和n的大小,可以将算法改为递减的模式
观察公式
可以反向推导出
也就是更新了的定义,,在此基础上我们可以结合前面的公式进行滑动窗口式的计算。
想阅读更多技术文章,请访问听云技术博客,访问听云官方网站感受更多应用性能优化魔力。