基于改進移動最小二乘法的數(shù)據(jù)擬合*

王紅平，史 明

(長春理工大學機電工程學院機電一體化實驗室，長春 130022)

0 引言

最小二乘(LS)方法在數(shù)據(jù)擬合中的應用最為廣泛，其常用的基函數(shù)是多項式[1]、有理函數(shù)[2]、曲線擬合中的高斯樣條、指數(shù)樣條、平滑樣條、B樣條、非均勻有理B樣條、Bezier曲面和曲面構造中的徑向基函數(shù)。同時，LS的變形為遞歸最小二乘(RLS)、總最小二乘(TLS)、偏最小二乘(PLS)、加權最小二乘 (WLS)、廣義最小二乘(GLS)[3]、等式約束最小二乘(LSE)。然而，所有基于LS的方法全部是全局逼近格式，不適用于數(shù)據(jù)量大、分布不規(guī)則和分布分散的情況。因此，在測量數(shù)據(jù)處理中，提出了一種局部逼近的移動最小二乘(MLS)方法。

Shepard在最低階情形下引入移動最小二乘(MLS)作為逼近方法[4]，Lancaster和Salkauskas將其推廣到更高的程度[5]。目前，移動最小二乘(MLS)逼近應用越來越廣泛,已用于幾何模型的生成[6]、粒子電場的重構[7]和正則化回歸中的學習性能[8]。MLS近似在文獻中已有大量記載，并被許多學者用于工程實際問題的優(yōu)化，如:Fu Fangyan等采用最小二乘粒子流體力學(MLSPH)方法求解Burgers方程[9]，Hosseininia M等提出一種基于移動最小二乘(MLS)形狀函數(shù)無網(wǎng)格方法提高了求解模型的精度[10]。MLS逼近不只應用于工程問題，在圖像處理中也得到了大量應用。Hwang Y等提出一種具有空間約束的概率移動最小二乘法，用于圖像之間的非線性顏色轉移[11]。Yu Chong等基于運動積分最小二乘法進行輪廓圖像的變形[12]，在圖形處理器上利用移動最小二乘法加速多維插值等[13]。

雖然MLS得到了大量的應用但仍有很大的提升空間，Bayona Victor進行了移動最小二乘法(MLS)與RBF+poly法兩種無網(wǎng)格法對插值與導數(shù)逼近的比較，證明MLS在擬合高階多項式時的局限[14]。Zhang L等針對移動最小二乘未考慮全局變量的缺陷，將基于奇異值分解的參數(shù)λ引入局部逼近，提出了一種MLS的優(yōu)化方法用于生成測量數(shù)據(jù)的曲線和曲面[15]。但上述方法均未對加權函數(shù)進行研究，也未對其中影響參數(shù)進行分析。

本文基于MLS通過對加權函數(shù)的分析與對比,提出了改進的移動最小二乘法(IMLS)。對移動最小二乘的缺陷進行了改進，提升了移動最小二乘的擬合性能，增強了其實用性。

1 移動最小二乘法

1.1 傳統(tǒng)移動最小二乘

在MLS近似下，試驗函數(shù)可以表示為[16]：

(1)

其中，pi(x)，i=1,2,…,m,是單項基函數(shù)，m是基函數(shù)中的項數(shù)，而ai(x)是基函數(shù)的系數(shù)。一般而言基函數(shù)pT(x)=[p1(x),p2(x),…pm(x)]可以是多項式，切比雪夫多項式，勒讓德多項式，三角函數(shù)，徑向基函數(shù)等。

通常，基函數(shù)有以下形式：

線性基:

一維:pT=(1,x1)m=2

(2)

二維:pT=(1,x1,x2)m=3

(3)

二次基:

(4)

(5)

由蘭卡斯特和薩爾考斯卡斯定義的局部近似為：

(6)

對于函數(shù)u(x)的精確局部逼近，必須通過加權最小二乘法使局部逼近uh(x)和函數(shù)u(x)之間的差值達到最小化。

定義函數(shù):

(7)

其中，u(xI),I=1,2,…,N,是給定的均勻分布的函數(shù)結點。w(x-xI)是一個具有緊湊支持的加權函數(shù)，并且xI,I=1,2,…,n,是點x影響域中的離散點，下標“I”意味著加權函數(shù)的中心位于xI處。圖1顯示了MLS中加權方案的示意圖[17],權值施加在擬合值與給定值之間的平方誤差上,通過調節(jié)節(jié)點的權重值達到擬合的最優(yōu)化。

圖1 加權方案示意圖

式(7)的矩陣形式可以表示為：

(8)

(9)

(10)

(11)

a=(a(x),a(x),...,a(x))T

(12)

對于式(8)關于系數(shù)a(x)求偏導數(shù)，可以得到以下表達式：

A(x)=pTwp,B(x)=pTw

因此系數(shù)a(x)為：

a(x)=A-1(x)B(x)

(13)

uh(x)=PT(x)a(x)=PT(x)A-1(x)B(x)u=Φ(x)u

(14)

這里的Φ(x)被稱為MLS中的形狀函數(shù)。

1.2 移動最小二乘的優(yōu)化

1.2.1 總體最小二問題

求解線性系統(tǒng)AX=B中設矩陣A的誤差矩陣為E，向量b的誤差向量為e，則表達式等價于

(A+E)·X=(B+e)

與最小二乘法僅關注測量向量誤差e不同，總體最小二乘法綜合考慮了系數(shù)矩陣E和觀測向量e的誤差，具有較高的計算精度和可靠性。與遞推最小二乘法相比，該方法無需設定初值和迭代運算，計算簡單且便于實現(xiàn)，不需要大量的樣本數(shù)據(jù)?？傮w最小二乘法的基本思想是使誤差E和e小化，即令矩陣[E?e]的F范數(shù)最小化，可采用奇異值分解法來解算。

構造增廣矩陣C，并進行奇異值分解為：

C=[AB]=UΣVH

(15)

其中，Σ=diag(σ1,σ2,…,σn+d),設C的奇異值σ1≥σ2≥…≥σn+d，并進行分塊

(16)

當且僅當V22是非奇異矩陣時且σn≠σn+1，TLS問題有解，TLS解為：

(17)

其中，V12為k階矩陣，k為待求解維數(shù)。

1.2.2 移動最小二乘優(yōu)化

到所有變量的誤差，將在A和B之間設置參數(shù)λ的TLS方法引入移動最小二乘法的局部逼近中，對移動最小二乘(MLS)法進行優(yōu)化[16]。

在移動最小二乘法的優(yōu)化中，為x處的局部近似值定義Cx：

Cx:=Wx[DAxTBx]=UxΣxVxT

(18)

其中，

Wx=diag(w(x-xI),…,w(x-xn))
D=diag(λ,…,λ)n×n、
T=diag(1-λ,…,1-λ)n×n

在x的影響域中，局部系數(shù)近似值由以下關系式解出

a(x)=[a1(x),a2(x),…,am(x)]=-Vx12Vx22

(19)

其中，Vx12為P階矩陣:P=m。

根據(jù)文獻[16]所述方法確定參數(shù)λ：為了節(jié)省計算量和防止導致病態(tài)方程，經(jīng)大量數(shù)值實驗將λ定為定值λ=0.5。

2 改進的移動最小二乘

在MLS方法中，選擇擬合性能較好的高斯函數(shù)作為加權函數(shù)，但對加權函數(shù)沒有深入研究。本節(jié)對權函數(shù)進行了詳細的分析，通過對正態(tài)權函數(shù)和兩種典型權函數(shù)(高斯權函數(shù)和四次樣條函數(shù))的數(shù)值例子比較，證明了正態(tài)權函數(shù)在加權方面的優(yōu)越性，并著重研究了正態(tài)權函數(shù)及其參數(shù)，實現(xiàn)了MLS方法的改進。

2.1 加權函數(shù)分析

權函數(shù)的選取在MLS 近似中具有重要的作用，對計算結果影響很大，它的選取一般應該滿足 4 個條件：非負性、緊支性、單調遞減性，光滑性。目前常見的權函數(shù)有：高斯型、指數(shù)型、樣條型以及徑向基函數(shù)等。在第3節(jié)中，當選擇特定的基函數(shù)時，基函數(shù)矩陣A(x)和觀測值矩陣B(x)就被確定了，所以它們都與未知點無關，它們只是形成形狀函數(shù)的常數(shù)。因此，只有矩陣w定義在x上，并且形狀函數(shù)主要由加權函數(shù)決定。

加權函數(shù)的基本要求是緊支撐、非負定的、連續(xù)的、具有較高導數(shù)的，以保證系數(shù)的唯一性。緊湊的支撐特性是MLS的本質，而加權函數(shù)的緊湊性是由支撐半徑dmi決定的，從圖1可以明顯看出，相對較大的支持域意味著在計算中涉及更多的節(jié)點，各節(jié)點的權函數(shù)都是緊支函數(shù)，因而在某計算點x處的MLS近似只需利用對x有影響的節(jié)點xI(I=1,2,…,N)(節(jié)點xI的權函數(shù)在x點處不等于零或者說該節(jié)點的支撐域半徑大于它到x點之間的距離)來構造。節(jié)點xI的支撐域一般為半徑dmi的圓形區(qū)域(二維問題)如圖2所示或球形區(qū)域(三維問題)。如何選擇合適的支承半徑取決于擬合誤差、平滑度和問題本身的特點。

圖2 二維平面支撐域示意圖

2.2. 加權函數(shù)的選擇

(1)正態(tài)加權函數(shù):

(20)

σ為參數(shù)。

其中，r=|x-xI|/dmi是相對距離，dmi是影響域半徑，σ是形狀參數(shù)，根據(jù)影響域與支撐域的性質及加權函數(shù)僅在影響域中定義，所以加權函數(shù)是一個緊湊的支持函數(shù)。正態(tài)加權函數(shù)如圖3所示。此外，擬合的平方誤差被加權，只是作為一個移動窗口，簡單來說就是對每個樣本點計算一次加權最小二乘法，然后對該樣本的自變量xi求函數(shù)值f(xi)，算出來的(xi,f(xi))就是平滑的結果，所以MLS與IMLS可以看做是WLS與SLS的結合。此外|x-xI|為想要求自變量x到附近樣本自變量的歐幾里德距離:

圖3 正態(tài)加權函數(shù)圖

(2)高斯加權函數(shù)為:

(21)

β為參數(shù)。

在高斯加權函數(shù)中，β是形狀參數(shù)，r=|x-xI|/dmi是相對距離，dmi是影響域半徑。

(3)四次樣條函數(shù):

(22)

可以看出在正態(tài)加權函數(shù)與高斯加權函數(shù)中有兩個調節(jié)參數(shù)，分別為dmi,σ和dmi，β，而在四次樣條加權函數(shù)中只有dmi一個調節(jié)參數(shù)，圖4顯示了高斯樣條函數(shù)和四次樣條函數(shù)，數(shù)值試驗表明，β=1.9時，高斯函數(shù)與四次樣條相似甚至近乎一致。相應地，正態(tài)加權函數(shù)和高斯加權函數(shù)對于IMLS是非常靈活的，都可對形狀參數(shù)β和σ進行調節(jié)從而調節(jié)局部逼近效果，但哪一個更適用于IMLS，我們將在下面的具體數(shù)值算列中進行分析。

圖4 四次樣條與高斯加權函數(shù)

2.3 數(shù)值算例與分析

在這部分給出了兩個例子來分析權函數(shù)的選擇。

示例1：選擇函數(shù)

y1=sin(x)·cos(3x)

(23)

利用該函數(shù)選擇均勻分布的節(jié)點(xi,yi),i=1,2,…,n。將正態(tài)分布的均值為零的隨機誤差σx和σy分別加到xi和yi中，形成一組測量點,基函數(shù)pT(x)=[1,x,x2]。IMLS方法中總體最小二乘參數(shù)λ由上述方法確定。采用正態(tài)加權函數(shù)和高斯加權函數(shù)兩種加權方法對被測點進行擬合，根據(jù)圖5所示,顯示正態(tài)加權函數(shù)在擬合性能上優(yōu)于高斯加權函數(shù)，但還需進一步驗證。

圖5 函數(shù)y1=sin(x)·cos(3x)的兩種加權的IMLS擬合

示例2:選擇函數(shù)

(24)

測量點按與示例1相同的方式生成，基函數(shù)pT=[1,x]分別用正態(tài)加權和高斯加權進行擬合，擬合效果如圖6所示。

圖6 函數(shù)的兩種加權的IMLS擬合

從數(shù)值實例中可以看出，正態(tài)加權擬合性能更好一些。所以在以下的IMLS擬合數(shù)值例子中均采用正態(tài)加權函數(shù)進行加權。

因此，我們可以在IMLS中得出以下結論：

(1)對于基函數(shù)的選擇，線性基、二次基或高階多項式都可以作為候選。雖然隨著多項式階數(shù)的增加，得到了較好的光滑擬合，但是計算成本會大幅度增加，甚至會導致病態(tài)方程。因此，在二維或三維情況下，只選擇低階多項式。

(2)形狀函數(shù)主要由加權函數(shù)決定，對于正態(tài)加權函數(shù)中的參數(shù)設置，影響半徑dmi是關鍵問題。影響半徑越大，支撐域越大，擬合光滑性越好，但是計算量越大。減小支撐域，局部性增強，但平滑度下降。從圖3可以看出，正態(tài)加權函數(shù)中的形狀參數(shù)σ越小，跟蹤快速變化能力越強，使局部性擬合效果增強，但平滑度下降，如何選擇合適的dmi與σ，取決于擬合誤差、平滑度和問題本身特點。

3 IMLS數(shù)值擬合實例

通過三個數(shù)值算例對IMLS的擬合性能進行了研究，前兩個是周期函數(shù)，另一個是三維圖形函數(shù)，測量點按上一節(jié)的方式生成，在實例中還應用了MLS方法進行了比較。他們的公式是:

(25)

(26)

z=x*e-x2-y2

(27)

參數(shù)設置：

(1)y1,y2中基函數(shù)pT(x)=[1,x,x2],m=3。z中基函數(shù)pT(x)=[1,x,y,x2,xy,y2],m=6。

(2)函數(shù)y1,y2中步長h=0.01,z中步長h=0.08。

(3)λ=0.5。

從數(shù)值圖像中可以看出IMLS的擬合效果要優(yōu)于MLS。為了更好的表達擬合優(yōu)化的效果，列出了誤差表1、2和3，誤差用均方根誤差(RMSE)表示。

(28)

實例1的擬合曲線如圖7所示，實例2的擬合曲線如圖8所示，實例3的擬合曲面如圖9所示。

圖7 函數(shù)y1=sin(2x)+e-x/3(1+cos(3x))的MLS與IMLS擬合

表1 函數(shù)y1=sin(2x)+e-x/3(1+cos(3x))兩種擬合方法的RMSE

圖8 函數(shù)的MLS與IMLS擬合

表2 函數(shù)兩種擬合方法的RMSE

圖9 函數(shù)z=x*e-x2-y2的IMLS擬合

表3 函數(shù)z=x*e-x2-y2兩種擬合方法的RMSE

從上述例子可以看出，IMLS的擬合結果要優(yōu)于MLS方法。圖10顯示了上述三個例子IMLS方法的RMSE隨影響參數(shù)線性比的變化情況。從圖中可以看出在一定范圍內當dmi/σ=0.9～1.1時，誤差值最小。所以在合理的范圍內在選取d與σ時，應盡量使dmi/σ接近于0.9～1.1，使擬合效果達到最優(yōu)化，同時節(jié)省試算時間。

圖10 均方根誤差RMSE隨dmi/σ的變化走勢圖

4 結論

MLS優(yōu)化考慮了所有變量的誤差,將基于奇異值分解的參數(shù)λ引入到局部逼近中，但MLS優(yōu)化沒有對加權函數(shù)進行深入研究，因此，本文提出了一種MLS近似的改進方法。數(shù)值算例和實測數(shù)據(jù)擬合表明了IMLS優(yōu)越的擬合性能，可以得出以下結論：

(1)數(shù)值算例表明在相同條件下，正態(tài)加權的擬合靈活性不輸于高斯加權，且正態(tài)加權的擬合性能優(yōu)于高斯加權，所以選擇正態(tài)加權作為IMLS的加權函數(shù)是一種合理的優(yōu)化方式。

(2)正態(tài)加權函數(shù)中的影響域半徑dmi越大，支撐域越大，擬合光滑性越好，但是計算量越大，減小支撐域，局部性增強，但平滑度下降。形狀參數(shù)σ越小跟蹤快速變化能力越強，使局部性擬合效果增強，但平滑度下降。所以與IMLS方法相比MLS方法具有更大的靈活性。

(3)相同條件下IMLS法與MLS法對離散數(shù)據(jù)的曲線和曲面擬合結果表明，IMLS方法比MLS方法具有更好的擬合性能，驗證了本文提出的IMLS方法的有效性。因此，IMLS是一種有效的數(shù)據(jù)處理方法。