李朋 周鵬 王石磊
寧波潤華全芯微電子設備有限公司 浙江 寧波 315400
在二維平面上的點進行擬合時,常用的方法包括經典的最小二乘法、Hough變換,或者二者相結合等方法,但是不同的思路進行多點擬合的復雜度和計算時間是存在差異的[1]。本文介紹了2種基于最小二乘法的方法,并基于同樣的樣本對二者的算法的復雜性進行對比分析。本篇文章將詳解單變量線性回歸并寫出使用最小二乘法(least squares method)來求線性回歸損失函數最優解的完整過程,首先推導出最小二乘法,后用最小二乘法對一個簡單數據集進行線性回歸擬合。
第1種使用的方法是使用最小二乘法來求線性回歸的損失函數最小的最優解。線性回歸假設數據與結果存在著如下的線性關系:
y和x分別代表實際采樣的兩個特征,k表示梯度,b表示截距。這個等式是假設的,需要找到合適的梯度和截距,使得計算結果與真實的采樣數據的誤差最小。這里使用差的平方來衡量估計值與真實值之間的誤差。用于計算真實值與估計值之間的誤差函數稱之為最小損失函數:
根據平均損失的定義有:
展開整理得:
要使得平均損失函數取得最小值,需要將該函數對兩個未知參數k和b的偏導數等于0,進而求出兩者的解。對b求偏導可得:
令上式等于0,可得:
同時令:
對損失函數的另一個變量求出偏導:
將整理好的b帶入上式,可得:
令上式等于0,整理的到:
求得k的值為:
以上是第一種方法,即求得損失函數最小值的解,為所求的直線的梯度和截距。
第二種方法是基于點到直線距離的公式,計算出所有采樣點到目標擬合直線的距離的最小值,進而求得相關的參數。
同樣,我們利用第一種方法中的擬合的目標直線的公式:
首先要知道所擬合的直線必然經過所有樣本點的中心坐標這一原理,即:
將所有的點經過平移,即減去中心坐標,將直線平移到經過原點的位置。這樣做的主要目的是為了減少算量,使得直線方程簡化:
點到直線的距離簡化為:
根據上式,可以求得所有的點到預估直線的距離的最小值的和為:
上式對k進行求導并令其值為0,可得:
求解以上的一元二次方程可得k的值(取加號)令:
求得:
然后求得b,為:
以上即為2種方法的推導過程,可以看出從推到的繁易程度來看,第2種更加容易一些,下面根據實際工程中的數據樣本在Matlab軟件上繪制實際的擬合直線,并得出各自對應的斜率(梯度)和截距。
由以上分析,需要在Matlab的平臺驗證收集的數據樣本。實際收集了42組樣本數據來對比分析,數據樣本如表1所示:
表1 實際數據樣本
擬合的直線如下圖1所示:
圖1 兩種算法的擬合對比
其中,灰色直線為第1種方法擬合的結果,黑色直線為第2種方法擬合的結果。2種方法計算出來的結果如表2所示:
表2 2種算法的擬合結果
為了驗證以上算法我們基于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 ;
以上即為第二種算法的部分核心計算代碼。
由擬合的結果可知兩種算法的結果非常接近,當試驗樣本的數據量比較小時,可以選擇適合算法來擬合對應的直線。
當數據樣本增加到一定程度時,2種算法的計算耗時存在的較大的差異。擴大到試驗樣本到1000組數據,兩種算法的耗時記錄如表3所示:
表3 兩種算法計算耗時對比
經過對比分析,第2種算法的計算效率要比第1種算法高30%左右,所以在大數據樣本下,直線擬合的算法推薦使用第2種算法。