浅析两种常用的直线拟合方法

李朋 周鹏 王石磊

宁波润华全芯微电子设备有限公司 浙江 宁波 315400

引言

在二维平面上的点进行拟合时，常用的方法包括经典的最小二乘法、Hough变换，或者二者相结合等方法，但是不同的思路进行多点拟合的复杂度和计算时间是存在差异的[1]。本文介绍了2种基于最小二乘法的方法，并基于同样的样本对二者的算法的复杂性进行对比分析。本篇文章将详解单变量线性回归并写出使用最小二乘法（least squares method）来求线性回归损失函数最优解的完整过程，首先推导出最小二乘法，后用最小二乘法对一个简单数据集进行线性回归拟合。

1 两种直线拟合算法[2-5]

第1种使用的方法是使用最小二乘法来求线性回归的损失函数最小的最优解。线性回归假设数据与结果存在着如下的线性关系：

y和x分别代表实际采样的两个特征，k表示梯度，b表示截距。这个等式是假设的，需要找到合适的梯度和截距，使得计算结果与真实的采样数据的误差最小。这里使用差的平方来衡量估计值与真实值之间的误差。用于计算真实值与估计值之间的误差函数称之为最小损失函数：

根据平均损失的定义有：

展开整理得：

要使得平均损失函数取得最小值，需要将该函数对两个未知参数k和b的偏导数等于0，进而求出两者的解。对b求偏导可得：

令上式等于0，可得：

同时令：

对损失函数的另一个变量求出偏导：

将整理好的b带入上式，可得：

令上式等于0，整理的到：

求得k的值为：

以上是第一种方法，即求得损失函数最小值的解，为所求的直线的梯度和截距。

第二种方法是基于点到直线距离的公式，计算出所有采样点到目标拟合直线的距离的最小值，进而求得相关的参数。

同样，我们利用第一种方法中的拟合的目标直线的公式：

首先要知道所拟合的直线必然经过所有样本点的中心坐标这一原理，即：

将所有的点经过平移，即减去中心坐标，将直线平移到经过原点的位置。这样做的主要目的是为了减少算量，使得直线方程简化：

点到直线的距离简化为：

根据上式，可以求得所有的点到预估直线的距离的最小值的和为：

上式对k进行求导并令其值为0，可得：

求解以上的一元二次方程可得k的值（取加号）令：

求得：

然后求得b，为：

以上即为2种方法的推导过程，可以看出从推到的繁易程度来看，第2种更加容易一些，下面根据实际工程中的数据样本在Matlab软件上绘制实际的拟合直线，并得出各自对应的斜率（梯度）和截距。

2 验证2种算法[6-7]

由以上分析，需要在Matlab的平台验证收集的数据样本。实际收集了42组样本数据来对比分析，数据样本如表1所示：

表1 实际数据样本

拟合的直线如下图1所示：

图1 两种算法的拟合对比

其中，灰色直线为第1种方法拟合的结果，黑色直线为第2种方法拟合的结果。2种方法计算出来的结果如表2所示：

表2 2种算法的拟合结果

3 部分拟合算法代码

为了验证以上算法我们基于C#平台编写了第2中方法的相关拟合的代码，其输出的结果做了输出。

代码如下：

首先需要部分使用得变量进行定义和初始化：

以上代码中，A，B，C即为如下表达：

下面利用求根公式计算得到相应的解：

double k1 = (-B + Math.Sqrt(B * B - 4 * A * C)) / (2 * A);

double k2 = (-B - Math.Sqrt(B * B - 4 * A * C)) / (2 * A);

取其中的正值即k1作为求解得到的斜率（梯度）；所求得得截距b即为：

b = Yavr - Xavr * k ;

以上即为第二种算法的部分核心计算代码。

4 结论

由拟合的结果可知两种算法的结果非常接近，当试验样本的数据量比较小时，可以选择适合算法来拟合对应的直线。

当数据样本增加到一定程度时，2种算法的计算耗时存在的较大的差异。扩大到试验样本到1000组数据，两种算法的耗时记录如表3所示：

表3 两种算法计算耗时对比

经过对比分析，第2种算法的计算效率要比第1种算法高30%左右，所以在大数据样本下，直线拟合的算法推荐使用第2种算法。