不完全測(cè)量數(shù)據(jù)的 E M處理算法＊

林東方 宋迎春 金 昊

不完全測(cè)量數(shù)據(jù)的 E M處理算法＊

林東方 宋迎春 金 昊

推導(dǎo)了 EM算法用于不完全測(cè)量數(shù)據(jù)的實(shí)現(xiàn)方法。結(jié)果表明,應(yīng)用 EM算法處理不完全測(cè)量數(shù)據(jù),改善了測(cè)量精度,與完全數(shù)據(jù)下的平差結(jié)果極其接近,明顯優(yōu)于不進(jìn)行平差處理的結(jié)果。

不完全測(cè)量數(shù)據(jù);平差;G-M模型;最小二乘原理;EM算法

1 引言

在測(cè)量中,由于儀器設(shè)備精度、人為因素和外界環(huán)境的限制,測(cè)量中往往伴隨著誤差。為了保證測(cè)量的精度,將測(cè)量誤差控制在一定的范圍內(nèi),在必要觀測(cè)的基礎(chǔ)上常常進(jìn)行多余觀測(cè),應(yīng)用最小二乘原理平差計(jì)算,得到最優(yōu)的估計(jì)參數(shù)。但是由于工程施工、農(nóng)業(yè)生產(chǎn)或意外事故常常使一些控制點(diǎn)被破壞或找不到,無(wú)法進(jìn)行觀測(cè)?；蛘哂^測(cè)后,由于儀器故障、人為因素造成某些測(cè)站的觀測(cè)數(shù)據(jù)被破壞或丟失。這些情況的發(fā)生,都會(huì)造成觀測(cè)數(shù)據(jù)的不完整,使完全觀測(cè)數(shù)據(jù)變?yōu)椴煌耆^測(cè)數(shù)據(jù)。由于數(shù)據(jù)的不完全,在進(jìn)行平差計(jì)算時(shí)就必須將破壞或丟失的數(shù)據(jù)刪除之后再進(jìn)行平差,這嚴(yán)重影響了觀測(cè)質(zhì)量和測(cè)量精度。當(dāng)數(shù)據(jù)缺失過(guò)于嚴(yán)重時(shí),就無(wú)法進(jìn)行平差計(jì)算,測(cè)量數(shù)據(jù)便無(wú)法使用,觀測(cè)資料也就廢置不用,這就浪費(fèi)了大量人力、物力和財(cái)力。

鑒于此,一些學(xué)者提出,對(duì)不完全數(shù)據(jù)進(jìn)行插值處理,將缺失數(shù)據(jù)通過(guò)插值方法補(bǔ)充進(jìn)去,而后進(jìn)行平差計(jì)算,如時(shí)間序列處理的插值方法[1],這種方法雖然有一定的效果,但插值數(shù)據(jù)是對(duì)剩余數(shù)據(jù)的進(jìn)一步處理所得,并沒(méi)有利用更多的潛在信息。而在這方面,EM(Expectation-Maximization)算法就有著很大的優(yōu)勢(shì)。EM算法是用于非完全數(shù)據(jù)參數(shù)估計(jì)的一種有效方法,它是一種數(shù)據(jù)添加算法,即在觀測(cè)數(shù)據(jù)的基礎(chǔ)上添加一些“潛在數(shù)據(jù)”,利用對(duì)數(shù)據(jù)處理有益的潛在信息,得到數(shù)據(jù)缺失下參數(shù)的最優(yōu)估計(jì)。當(dāng)測(cè)量數(shù)據(jù)不完全時(shí),可以利用觀測(cè)數(shù)據(jù)所服從的一些規(guī)律,對(duì)缺失數(shù)據(jù)的取值范圍加以限制,即采用 EM算法,利用缺失數(shù)據(jù)在現(xiàn)有條件下的期望值,對(duì)不完全數(shù)據(jù)進(jìn)行處理計(jì)算,最終得到一個(gè)較好的參數(shù)估計(jì)結(jié)果。

2 EM算法及其在不完全測(cè)量觀測(cè)數(shù)據(jù)中的處理方法

2.1 EM算法

EM算法的最大特點(diǎn)是通過(guò)對(duì)完全數(shù)據(jù)的處理來(lái)解決不完全數(shù)據(jù)問(wèn)題[2,3]。它主要應(yīng)用于下面兩種不完全數(shù)據(jù)參數(shù)估計(jì)：第一,觀測(cè)數(shù)據(jù)不完全,這是由于觀測(cè)過(guò)程的局限性或觀測(cè)后的意外事故所導(dǎo)致;第二,似然函數(shù)不是解析的,或者似然函數(shù)的表達(dá)式過(guò)于復(fù)雜從而導(dǎo)致極大似然函數(shù)難以解算。第一種情況在測(cè)量數(shù)據(jù)處理中經(jīng)常遇到。

EM算法是一種迭代算法,它的每一步迭代由兩步組成：E步(求期望)和M步(極大化)[4]。E步在給定己觀測(cè)到的數(shù)據(jù)和現(xiàn)有參數(shù)下,求“缺失數(shù)據(jù)”的條件期望;M步計(jì)算參數(shù)的MLE估計(jì),這與己知似然求參數(shù)的MLE估計(jì)的計(jì)算方法一致。

具體地講,以 P(θ/Y)表示θ的基于觀測(cè)數(shù)據(jù)的后驗(yàn)分布密度,稱(chēng)為觀測(cè)數(shù)據(jù)后驗(yàn)分布。以 P(θ/Y, Z)表示添加數(shù)據(jù) (缺失數(shù)據(jù))Z后得到的關(guān)于θ的后驗(yàn)分布密度函數(shù),稱(chēng)為完全數(shù)據(jù)后驗(yàn)分布。P(Z/ θ,Y)表示在給定θ和觀測(cè)數(shù)據(jù) Y下潛在數(shù)據(jù) (缺失數(shù)據(jù))Z的條件分布密度函數(shù)。我們的目的是計(jì)算觀測(cè)后驗(yàn)分布 P(θ/Y)的參數(shù)。EM的算法為,記θi為第 i+1次迭代開(kāi)始時(shí)后驗(yàn)參數(shù)的估計(jì)值,則第 i +1次迭代的兩步為：

E步：將 P(θ/Y,Z)或 logP(θ/Y,Z)關(guān)于 Z的條件分布求期望,從而把 Z積掉,即

M步：將 Q(θ/θi,Y)極大化,即找一個(gè)點(diǎn)θi+1,使

EM算法在每一次迭代后均提高觀測(cè)極大似然密度函數(shù)值,具有良好的全局收斂性[4,5]。

2.2 (G-M)模型下不完全測(cè)量觀測(cè)數(shù)據(jù)的EM處理方法

測(cè)量中常采用 Gauss-Markov(G-M)模型[6]

在測(cè)量平差中,間接平差的誤差方程為[7]

這里假設(shè)觀測(cè)數(shù)據(jù) ln由于意外事故丟失,應(yīng)用 EM算法建立似然函數(shù)方程 P(θ/Y,Z)

式中θ為未知參數(shù) X,Y為不完全觀測(cè)數(shù)據(jù) (l1,l2,…,ln-1),Z為缺失數(shù)據(jù) ln。

由于測(cè)量誤差改正數(shù) V服從期望為零的正態(tài)分布,因此可以得到缺失數(shù)據(jù) ln的條件分布概率密度函數(shù)為

由式(6)、(7)便得到 EM算法的期望步

3 算例分析

以水準(zhǔn)測(cè)量為例。在圖 1中,A、B為已知水準(zhǔn)點(diǎn),其高程 HA=12.013 m,HB=10.013 m,可視為無(wú)誤差,為了確定 C及D點(diǎn)的高程,共觀測(cè)了 4個(gè)高差,h1=-1.004 m,h2=1.516 m,h3=2.512 m,h4=1.520 m。

當(dāng)測(cè)量數(shù)據(jù)完全時(shí),即高差觀測(cè)值h1、h2、h3、h4沒(méi)有丟失,我們采用最小二乘原理,應(yīng)用間接平差法,計(jì)算得到 HC、HD的高程為：HC=11.008 3 m,HD=12.525 7 m。

圖1 水準(zhǔn)測(cè)量路線(xiàn)Fig.1 Leveling line

假設(shè)由于意外事故,h2、h4數(shù)據(jù)丟失,測(cè)量數(shù)據(jù)變?yōu)椴煌耆珨?shù)據(jù),由于 h2、h4的丟失,沒(méi)有了多余觀測(cè),傳統(tǒng)的平差方法失效,直接計(jì)算得到 HC、HD的高程為：HC=11.009 m,HD=12.525 m。

在非完全數(shù)據(jù)的情況下,兩種計(jì)算方法所得結(jié)果與完全數(shù)據(jù)情況下平差計(jì)算所得結(jié)果進(jìn)行比較(表 2)。不平差所得參數(shù) HC、HD的值與完全數(shù)據(jù)下間接平差所得參數(shù) HC、HD的值均相差 0.7 mm,而 EM算法所得參數(shù) HC、HD的值與完全數(shù)據(jù)下間接平差所得參數(shù)值均相差 0.2 mm。由此可見(jiàn),在測(cè)量數(shù)據(jù)不完全時(shí),采用 EM算法進(jìn)行數(shù)據(jù)處理能夠得到更好的結(jié)果。

表1 高程點(diǎn)計(jì)算結(jié)果(單位:m)Tab.1 Elevation results(un it:m)

表2 高程點(diǎn)計(jì)算結(jié)果比較(單位:m)Tab.2 Comparison between elevation results(un it:m)

4 結(jié)語(yǔ)

推導(dǎo)了在測(cè)量數(shù)據(jù)不完全時(shí),采用 EM算法進(jìn)行數(shù)據(jù)處理的實(shí)現(xiàn)方法,通過(guò)實(shí)例,驗(yàn)證了 EM算法在處理不完全測(cè)量數(shù)據(jù)時(shí)的有效性。結(jié)果表明,在測(cè)量數(shù)據(jù)缺失,沒(méi)有多余觀測(cè)的情況下,使用 EM算法的處理結(jié)果與完全數(shù)據(jù)時(shí)平差結(jié)果極其接近,效果十分明顯。在 EM算法下,許多以往廢置的數(shù)據(jù)均可以重新啟用,例如,往年廢置變形監(jiān)測(cè)數(shù)據(jù),往年廢置水準(zhǔn)網(wǎng)觀測(cè)數(shù)據(jù),有了這些歷史數(shù)據(jù)的加入,充分利用過(guò)去的觀測(cè)數(shù)據(jù)[8],對(duì)分析高層建筑物、水壩形變,地殼形變具有不可估量的意義。

EM算法是一種迭代收斂算法,它的收斂速度較慢[9],參數(shù)初值的選取對(duì)迭代的收斂速度影響較大,因而在初值選取時(shí),我們應(yīng)利用參數(shù)的先驗(yàn)信息,選取一個(gè)較接近參數(shù)估計(jì)值的初值,以提高 EM算法的收斂速度。EM算法在處理單個(gè)缺失數(shù)據(jù)或連續(xù)缺失數(shù)據(jù)時(shí)的效果顯著,但是 EM算法在處理重度缺失數(shù)據(jù)時(shí),處理效果不明顯[10],在處理離散缺失數(shù)據(jù)時(shí),須分批處理,因此如何提高重度缺失數(shù)據(jù)時(shí) EM算法的處理效果和系統(tǒng)整體處理離散缺失數(shù)據(jù)尚需進(jìn)一步的研究。應(yīng)用 EM算法要求觀測(cè)值與參數(shù)之間具有一定的分布關(guān)系,當(dāng)觀測(cè)值與參數(shù)之間無(wú)分布關(guān)系時(shí)則不適用 EM算法。

1 武艷強(qiáng),黃立人.時(shí)間序列處理的新插值方法[J].大地測(cè)量與地球動(dòng)力學(xué),2004,(4)：43-45.(Wu Yanqiang and Huang Liren.A new interpolationmethod in time series analyzing[J].Journal of Geodesy and Geodynamics,2004, (4)：43-45)

2 DempsterA P,Laird N M and Rubin D B.Maximum likelihood from incomplete data via the EM algorithm[J].Journal of the Royal Statistifcal SocietyB,1977,39：1-38.

3 錢(qián)俊,舒寧.基于 EM算法和單幅雷達(dá)圖像陰影的控制點(diǎn)坡度校正[J].武漢大學(xué)學(xué)報(bào) (信息科學(xué)版),2004,(12)：1 089-1 092.(Qian Jun and Shu Ning.Correction of control point slope based on EM algorithm and shading of single SAR image[J].Geomatics and Information Science ofWuhan University,2004,(12)：1 089-1 092)

4 Graham C G and Juan C A.Approximate EM algorithms for parameter and state estimation in nonlinear stochastic models [A].Proceedings of the 44th IEEE Conference on Decision and Control,and the European Control Conference[C]. 2005,12-15.

5 王兆軍.EM算法收斂的必要條件[J].南開(kāi)大學(xué)學(xué)報(bào)(自然科學(xué)版),1994,(2)：85-88.(Wang Zhaojun.The necessary condition on the convergence of the EM algorithm [J].Acta Scientiarum Naturalium Universitatis Nankaiensis,1994,(2)：85-88)

6 郭金運(yùn),靳奉祥,劉國(guó)林.不完全測(cè)量數(shù)據(jù)的應(yīng)用研究[J].測(cè)繪通報(bào),2002,(2)：7-8.(Cuo Jinyun,Jin Fengxiang and Liu Guolin.Study ofApplication of incomplete data in surveying[J].Bulletin of Surveying andMapping,2002, (2)：7-8)

7 武漢大學(xué)測(cè)繪學(xué)院測(cè)量平差學(xué)科組.誤差理論與測(cè)量平差基礎(chǔ) [M].武漢：武漢大學(xué)出版社,2003.(Research Group of Surveying Adjustment,School of Surveying and Mapping,Wuhan University.The base of errors theory and surveying adjustment[M].Wuhan;WuhanUniversity Press, 2003)

8 熊俊楠,等.高層建筑物變形監(jiān)測(cè)數(shù)據(jù)處理方法研究及工程應(yīng)用[J].測(cè)繪科學(xué),2010,(7)：69-71.(Xiong Junnan, et al.Research and application for high-rise deformation observation data processing method[J].Science of Surveying andMapping,2010,(7)：69-71)

9 高旅端,陳志,王家潤(rùn).一種加速 EM算法收斂的方法[J].數(shù)理統(tǒng)計(jì)與應(yīng)用概率,1998,(4)：342-348.(Gao Luduan,Chen Zhi andWang Jiarui.A method for accelerating convergence of fhe E M algorithm[J].Mathematical Statistics and Applied Probability,1998,(4)：342-348)

10 張香云,張秀偉.不同缺失率下 EM算法的參數(shù)估計(jì)[J].數(shù)理統(tǒng)計(jì)與管理,2008,(3)：428-431.(Zhang Xiangyun and Zhang Xiuwei. Parametrical estimation for EM algorithm in the case of different losing-rate[J].Application of Statistics and Management,2008,(3)：428-431)

EM PROCESSING ALGORITHM OF INCOM PLETE SURVEY ING DATA

Lin Dongfang,Song Yingchun and Jin Hao
(School of Geosciences and Info-Physics,Central South University,Changsha 410083)

For the incomplete surveying data caused by various factors,traditional adjustment can not be achieved.It is har mful to the accuracy of the surveying,even leads to abandoned observation data.Through EM algorithm,we can take the potential infor mation which is helpful to i mprove the accuracy of data processing effectively.EM processing algorithm for incomplete surveying data is proved.The results show that the surveying accuracy is improved by using the EM algorithm to process the incomplete data.The results are extremely si milar to the adjustment resultswith complete data and significantly better than the resultswithout adjustment.

incomplete surveying data;adjustment;G-M model;principle of least squares;EM algorithm

(中南大學(xué)地球科學(xué)與信息物理學(xué)院測(cè)繪與國(guó)土信息工程系,長(zhǎng)沙 410083)

1671-5942(2011)04-0112-04

2011-01-16

國(guó)家自然科學(xué)基金 (40874005);教育部博士點(diǎn)基金(200805331086)

林東方,男,1986年生,碩士研究生,主要研究方向?yàn)楝F(xiàn)代測(cè)量數(shù)據(jù)處理.E-mail：lindongfang223@163.com

P207;P203

A