淺析兩種常用的直線(xiàn)擬合方法

李朋 周鵬 王石磊

寧波潤(rùn)華全芯微電子設(shè)備有限公司 浙江 寧波 315400

引言

在二維平面上的點(diǎn)進(jìn)行擬合時(shí)，常用的方法包括經(jīng)典的最小二乘法、Hough變換，或者二者相結(jié)合等方法，但是不同的思路進(jìn)行多點(diǎn)擬合的復(fù)雜度和計(jì)算時(shí)間是存在差異的[1]。本文介紹了2種基于最小二乘法的方法，并基于同樣的樣本對(duì)二者的算法的復(fù)雜性進(jìn)行對(duì)比分析。本篇文章將詳解單變量線(xiàn)性回歸并寫(xiě)出使用最小二乘法（least squares method）來(lái)求線(xiàn)性回歸損失函數(shù)最優(yōu)解的完整過(guò)程，首先推導(dǎo)出最小二乘法，后用最小二乘法對(duì)一個(gè)簡(jiǎn)單數(shù)據(jù)集進(jìn)行線(xiàn)性回歸擬合。

1 兩種直線(xiàn)擬合算法[2-5]

第1種使用的方法是使用最小二乘法來(lái)求線(xiàn)性回歸的損失函數(shù)最小的最優(yōu)解。線(xiàn)性回歸假設(shè)數(shù)據(jù)與結(jié)果存在著如下的線(xiàn)性關(guān)系：

y和x分別代表實(shí)際采樣的兩個(gè)特征，k表示梯度，b表示截距。這個(gè)等式是假設(shè)的，需要找到合適的梯度和截距，使得計(jì)算結(jié)果與真實(shí)的采樣數(shù)據(jù)的誤差最小。這里使用差的平方來(lái)衡量估計(jì)值與真實(shí)值之間的誤差。用于計(jì)算真實(shí)值與估計(jì)值之間的誤差函數(shù)稱(chēng)之為最小損失函數(shù)：

根據(jù)平均損失的定義有：

展開(kāi)整理得：

要使得平均損失函數(shù)取得最小值，需要將該函數(shù)對(duì)兩個(gè)未知參數(shù)k和b的偏導(dǎo)數(shù)等于0，進(jìn)而求出兩者的解。對(duì)b求偏導(dǎo)可得：

令上式等于0，可得：

同時(shí)令：

對(duì)損失函數(shù)的另一個(gè)變量求出偏導(dǎo)：

將整理好的b帶入上式，可得：

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

求得k的值為：

以上是第一種方法，即求得損失函數(shù)最小值的解，為所求的直線(xiàn)的梯度和截距。

第二種方法是基于點(diǎn)到直線(xiàn)距離的公式，計(jì)算出所有采樣點(diǎn)到目標(biāo)擬合直線(xiàn)的距離的最小值，進(jìn)而求得相關(guān)的參數(shù)。

同樣，我們利用第一種方法中的擬合的目標(biāo)直線(xiàn)的公式：

首先要知道所擬合的直線(xiàn)必然經(jīng)過(guò)所有樣本點(diǎn)的中心坐標(biāo)這一原理，即：

將所有的點(diǎn)經(jīng)過(guò)平移，即減去中心坐標(biāo)，將直線(xiàn)平移到經(jīng)過(guò)原點(diǎn)的位置。這樣做的主要目的是為了減少算量，使得直線(xiàn)方程簡(jiǎn)化：

點(diǎn)到直線(xiàn)的距離簡(jiǎn)化為：

根據(jù)上式，可以求得所有的點(diǎn)到預(yù)估直線(xiàn)的距離的最小值的和為：

上式對(duì)k進(jìn)行求導(dǎo)并令其值為0，可得：

求解以上的一元二次方程可得k的值（取加號(hào)）令：

求得：

然后求得b，為：

以上即為2種方法的推導(dǎo)過(guò)程，可以看出從推到的繁易程度來(lái)看，第2種更加容易一些，下面根據(jù)實(shí)際工程中的數(shù)據(jù)樣本在Matlab軟件上繪制實(shí)際的擬合直線(xiàn)，并得出各自對(duì)應(yīng)的斜率（梯度）和截距。

2 驗(yàn)證2種算法[6-7]

由以上分析，需要在Matlab的平臺(tái)驗(yàn)證收集的數(shù)據(jù)樣本。實(shí)際收集了42組樣本數(shù)據(jù)來(lái)對(duì)比分析，數(shù)據(jù)樣本如表1所示：

表1 實(shí)際數(shù)據(jù)樣本

擬合的直線(xiàn)如下圖1所示：

圖1 兩種算法的擬合對(duì)比

其中，灰色直線(xiàn)為第1種方法擬合的結(jié)果，黑色直線(xiàn)為第2種方法擬合的結(jié)果。2種方法計(jì)算出來(lái)的結(jié)果如表2所示：

表2 2種算法的擬合結(jié)果

3 部分?jǐn)M合算法代碼

為了驗(yàn)證以上算法我們基于C#平臺(tái)編寫(xiě)了第2中方法的相關(guān)擬合的代碼，其輸出的結(jié)果做了輸出。

代碼如下：

首先需要部分使用得變量進(jìn)行定義和初始化：

以上代碼中，A，B，C即為如下表達(dá)：

下面利用求根公式計(jì)算得到相應(yīng)的解：

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 ;

以上即為第二種算法的部分核心計(jì)算代碼。

4 結(jié)論

由擬合的結(jié)果可知兩種算法的結(jié)果非常接近，當(dāng)試驗(yàn)樣本的數(shù)據(jù)量比較小時(shí)，可以選擇適合算法來(lái)擬合對(duì)應(yīng)的直線(xiàn)。

當(dāng)數(shù)據(jù)樣本增加到一定程度時(shí)，2種算法的計(jì)算耗時(shí)存在的較大的差異。擴(kuò)大到試驗(yàn)樣本到1000組數(shù)據(jù)，兩種算法的耗時(shí)記錄如表3所示：

表3 兩種算法計(jì)算耗時(shí)對(duì)比

經(jīng)過(guò)對(duì)比分析，第2種算法的計(jì)算效率要比第1種算法高30%左右，所以在大數(shù)據(jù)樣本下，直線(xiàn)擬合的算法推薦使用第2種算法。