一類曲線圖形數(shù)據(jù)挖掘的數(shù)值算法及其實現(xiàn)＊

宋花玉

（陜西省委黨校 科技部，西安710061）

在工程實際中，經(jīng)常遇到一類以曲線圖形形式只給出部分數(shù)據(jù)要求其余數(shù)據(jù)的問題．如航空工程中根據(jù)發(fā)動機在幾個典型壓力高度上的推力曲線圖，確定發(fā)動機在其它任意壓力高度、任意速度的推力，土建工程中，根據(jù)石灰土在幾個典型齡期的強度曲線圖，確定石灰土在其它任意齡期、任意混合比的強度．這類問題在工程實際中的傳統(tǒng)處理方法是先通過人工作圖查找相關(guān)數(shù)據(jù)再用兩點插值進行計算［1-2］．這種方法速度慢，精度低，不能用于大規(guī)模的精確計算問題．對于這類曲線圖形數(shù)據(jù)的大規(guī)模精確計算問題，文獻［3-7］進行了探索，提出了一些計算方法．文獻［3-5］提出的“就近整體拉格朗日擬合算法”，以距計算點最近的三條曲線為基礎(chǔ)，利用多次一元拉格朗日插值擬合出計算點所在的整條曲線的函數(shù)規(guī)律，利用此函數(shù)確定計算點的對應(yīng)值．這種方法的插值節(jié)點間距較大，根據(jù)插值的誤差理論［8］，這種方法的計算結(jié)果誤差較大．文獻［6-7］提出的“就近小區(qū)域二元拉格朗日擬合算法”，利用就近原則，在已給曲線上找出與計算點最接近的9個點，以這9個點為插值節(jié)點，利用二元拉格朗日插值擬合出計算點所在小區(qū)域的函數(shù)規(guī)律，然后利用此函數(shù)確定計算點的對應(yīng)值．由于插值節(jié)點取在計算點的附近，在一般情況下，這種方法比文獻［3-5］的就近整體擬合算法準確．但這種方法也存在一定的缺陷，由于二元9點插值多項式的次方較高，當曲線比較陡峭時，這種方法的計算結(jié)果不穩(wěn)定，在插值過程中容易出現(xiàn)“龍格”現(xiàn)象．而且文獻［3-7］均未對所研究的這類曲線圖形的數(shù)據(jù)特征進行分析，也未進行誤差估計，只是利用所提方法對所研究的具體問題進行了計算．文中對此問題進行了一般性的研究，分析曲線圖形所表示的數(shù)據(jù)關(guān)系是一種二元函數(shù)關(guān)系，提出一種準確穩(wěn)定的通用數(shù)據(jù)挖掘算法．

1 插值算法及誤差分析

1．1 數(shù)據(jù)特征分析和插值算法

文獻［1-7］中的問題可以統(tǒng)一表示為：設(shè)在某變化過程中有三個變量x、y和z，變量z的值由變量x和y的值確定，但具體關(guān)系式未知．圖1中的m條曲線Ci（i＝1，2，…，m）給出了當變量x在m個值x＝xi（其中xi為常數(shù)，i＝1，2，…，m）中任取一值，變量y在一定區(qū)間內(nèi)任取一值時變量z的對應(yīng)值，據(jù)此求當變量x在一定區(qū)間內(nèi)任取一值x＊，變量y在一定區(qū)間內(nèi)任取一值y＊時變量z的對應(yīng)值．圖1中，橫軸表示變量y，v1，v2，…v，k為橫軸y刻度值，且v1＜v2＜…＜vk；縱軸表示變量ω1，ω2，…，ωr為縱軸z的刻度值，且ω1＜ω2＜ …＜ωr．

研究分析可得如圖1所表示的數(shù)據(jù)有以下特征

① 變量x和y一旦取定，變量z值就唯一確定．

②m條曲線均無“峰”無“谷”，由此可知當變量x固定時，變量z關(guān)于變量y是單調(diào)的，所以不會出現(xiàn)這樣的情況：x相同而y不同的兩對數(shù)對應(yīng)的z相等．

③m條曲線沒有交點，即當變量y固定時，變量z關(guān)于變量x是單調(diào)的，所以不會出現(xiàn)這樣的情況：y相同而x不同的兩對數(shù)對應(yīng)的z相等．

圖1 曲線數(shù)據(jù)示意圖Fig．1Graph of curve data

由特征①可知變量z是變量x和y的二元函數(shù)，記作z＝f（x，y），再由特征 ②、③ 可知此二元函數(shù)是一一對應(yīng)的，文獻［1-7］中的問題變?yōu)橐阎灰粚?yīng)連續(xù)函數(shù)z＝f（x，y）在如圖1所示的m條無“峰”無“谷”且互不相交的曲線x＝xi（i＝1，2，…，m）上的函數(shù)值，求z＝f（x，y）在任意點（x＊，y＊）的函數(shù)值．

根據(jù)變量z關(guān)于變量y和x分別是單調(diào)的特征，可以把這個二元函數(shù)值的確定問題轉(zhuǎn)化為一元函數(shù)的插值問題．基本思路為：①固定變量y，將二元函數(shù)z＝f（x，y）變?yōu)殛P(guān)于x的一元函數(shù)，用一元插值對其進行相關(guān)的計算，得到需要的計算結(jié)果；② 固定變量x，將二元函數(shù)z＝f（x，y）變?yōu)殛P(guān)于y的一元函數(shù)，以第一步所得結(jié)果為條件，用一元插值對此關(guān)于y的一元函數(shù)進行插值計算便可得到結(jié)果．由于變量z關(guān)于變量y和x分別是單調(diào)的，這就保證了一元插值能夠順利有效的進行．以下給出本文通過插值確定z＝f（x，y）在圖中范圍內(nèi)任意點（x＊，y＊）的函數(shù)值的具體步驟為

①采集基礎(chǔ)數(shù)據(jù)，在圖1的橫軸上從坐標原點開始以足夠小的步長τ取值y0＝0，y1＝τ，y2＝2τ，…，yn＝nτ（其中n由圖形中y軸的最大標度確定），把圖中每條曲線中包含的函數(shù)值按第二個變量y每隔τ查找并記錄下來，設(shè)查出的在第一個變量為xi，第二個變量為yj時的函數(shù)值為zij，i＝1，2，…，m，j＝0，1，2，…，n．

② 從x＝x1，x＝x2，……，x＝xm中尋找出與x＊最接近的3個，假設(shè)這3個為x1、x2、x3，它們對應(yīng)的圖1中的曲線分別為C1、C2、C3；從y0＝0、y1＝τ、y2＝2τ、…、yn＝nτ中尋找出與y＊最接近的2個，假設(shè)這三個為y1＝τ、y2＝2τ；

③ 在函數(shù)z＝f（x，y）中固定第二個變量y的值為y1＝τ，從基礎(chǔ)函數(shù)值數(shù)據(jù)中找出曲線C1、C2、C3上與y1＝τ對應(yīng)的函數(shù)值z11、z21、z31，以x1、x2、x3為插值節(jié)點，以（x1，z11）、（x2，z21）、（x3，z31）為插值條件，利用拉格朗日插值公式可得在第二個變量y固定為常值y1＝τ，第一個變量x在區(qū)間［x1，x3］上時函數(shù)z＝f（x，y）與第一個變量x的2次多項式插值擬合函數(shù)f1（x）

④ 將x＝x＊代入式（1），可得二元函數(shù)z＝f（x，y）在第一個變量x取x＊，第二個變量y取y1＝τ時的2次多項式插值擬合函數(shù)值f1（x＊）

⑤ 在函數(shù)z＝f（x，y）中固定第二個變量y的值為y2＝2τ，從基礎(chǔ)函數(shù)值數(shù)據(jù)中找出曲線C1、C2、C3上與y2＝2τ對應(yīng)的函數(shù)值z12、z22、z32，以x1、x2、x3為插值節(jié)點，以（x1，z12）、（x2，z22）、（x3，z32）為插值條件，利用拉格朗日插值公式可得在第二個變量y固定為常值y2＝2τ，第一個變量x在區(qū)間［x1，x3］上時函數(shù)z＝f（x，y）與第一個變量x的2次多項式插值擬合函數(shù)f2（x）

⑥ 將x＝x＊代入式（2），可得二元函數(shù)z＝f（x，y）在第一個變量x取x＊，第二個變量y取y2＝2τ時的2次多項式插值擬合函數(shù)值f2（x＊）

⑧ 將y＝y(tǒng)＊代入式（3），便可得到二元函數(shù)z＝ f（x，y） 在 點 （x＊，y＊） 處 的 擬 合 函 數(shù) 值

1．2 算法選取依據(jù)及誤差分析

由式（5）可知，插值點x在插值節(jié)點x1、x2、x3某點附近時，2次插值的誤差較小，插值點x離插值節(jié)點x1、x2、x3越近，二次插值的誤差越?。驗槲覀円嬎闶剑?）中當x＝x＊時的函數(shù)值擬合，為了減少誤差，所以在1．1插值算法的具體步驟 ②中要從x＝x1，x＝x2，……，x＝xm中尋找出與x＊最接近的3個．

2 算法實現(xiàn)及實例計算

圖2 檢驗曲線圖Fig．2 Testing curve graph

為了檢驗文中算法，取圖2中與x＝2 000m對應(yīng)的曲線C3為檢驗曲線，在其上取10個點（見表1第1列），用文中程序計算這10個點的函數(shù)值（因為做檢驗之用，所以計算時應(yīng)該把從曲線C3采集到的11個基礎(chǔ)函數(shù)值從程序的基礎(chǔ)數(shù)據(jù)文本文件中暫時去掉），并與從圖上查出的準確函數(shù)值進行對比，結(jié)果見表1．

表1 計算結(jié)果檢驗數(shù)據(jù)Tab．1 Testing data of calculation result

從表1的第2列和第6列數(shù)據(jù)可看出，程序計算得到結(jié)果與圖中查出的準確結(jié)果基本吻合．計算可知，程序計算結(jié)果與準確結(jié)果的平均絕對誤差為109N，平均相對誤差為3．3%，根據(jù)問題的實際意義，這樣的誤差在小于5%的誤差允許范圍之內(nèi)，這說明本文提出的算法在實際中是準確可行的．

從理論上說，傳統(tǒng)方法只用到計算點附近的3個插值節(jié)點的函數(shù)值，而本文算法用到計算點附近的9個插值節(jié)點的函數(shù)值，文中的算法更接近于函數(shù)的真實狀態(tài)，所以本文的計算結(jié)果精度更高．實際計算結(jié)果也證明了這一點．在本例中，用傳統(tǒng)方法計算所取10個點的函數(shù)值，并與從圖上查出的準確函數(shù)值進行對比，結(jié)果見表1．計算可知，傳統(tǒng)方法計算結(jié)果的平均相對誤差為4．1%，比本文程序計算結(jié)果的平均相對誤差大0．8%．在本例中經(jīng)多次實際計算可知，傳統(tǒng)方法進行一次計算需要10min左右，文中程序進行1次計算所需時間不超過2s，所以文中算法效率更高．

3 結(jié) 論

1）對一類曲線圖形的數(shù)據(jù)挖掘進行了研究，在分析這類曲線圖形的數(shù)據(jù)關(guān)系是二元函數(shù)的基礎(chǔ)上，提出就近小區(qū)間拉格朗日插值挖掘算法．

2）實例計算表明，本文算法的平均相對誤差為3．3%，傳統(tǒng)算法的平均相對誤差為4．1%，文中算法比傳統(tǒng)算法準確，利用傳統(tǒng)方法進行1次計算需要10min左右，利用文中程序進行1次計算所需時間不超過2s．

3）文中算法雖然是對具有圖1數(shù)據(jù)特征的曲線圖形的數(shù)據(jù)挖掘設(shè)計的，但對于其他的一般曲線圖形的數(shù)據(jù)挖掘，在對曲線圖形進行一定的分割后，仍可用文中算法．當曲線圖形有“峰”有“谷”，或相互交叉時，應(yīng)從“峰”、“谷”、“交叉點”處分開，轉(zhuǎn)化為一段一段無“峰”無“谷”無“交叉點”的情形，這時在每一段內(nèi)曲線圖形具有圖1數(shù)據(jù)特征．

［1］ 鄧學(xué)均．路面路基工程［M］．北京：人民交通出版社，2008．DENG Xue-jun．Pavement and Subgrade Construction［M］．Beijing：China Communications Press，2008．（in Chinese）

［2］ 洪冬林．石灰穩(wěn)定土最大干密度與齡期的關(guān)系［J］．鐵道建筑技術(shù)，2011，28（3）：57．HONG Dong-lin．Relationship between Lime Stabilized Soil’s Maximum Dry Density and Its Age［J］．Railway construction technology，2011，40（3）：57．（in Chinese）

［3］ 宋花玉．飛機起飛滑跑發(fā)動機推力數(shù)值確定方法［J］．航空計算技術(shù)，2010，40（6）：43．SONG Hua-yu．A Numerical Value Confirmation Method of Engine Thrust in Aircraft Take-off Running［J］．Aeronautical Computing Technique，2010，40（6）：43．（in Chinese）

［4］ 金星馳，龔光軍，董玉德．圖形生成與變換算法可視化的原理與方法（英文）［J］．西安工程大學(xué)學(xué)報，2014，28（01）：94．JIN Xing-chi，GONG Guang-jun，DONG Yu-de．The Principle and Method of Graphics Generating and transform Algorithm Visualization（in English）［J］．Journal of Xi’an Polytechnic University，2014，28（01）：94．（in Chinese）

［5］ 楊旭，董玉德，余來宏，等．圖形自動編程在火焰切割機系統(tǒng)開發(fā)中的實現(xiàn)［J］．西安工程大學(xué)學(xué)報，2014，28（2）：235．YANG Xu，DONG Yu-de，YU Lai-hong，et al．Realization of Graphic Automatic programming in Flame Cutting Machine System［J］．Journal of Xi’an Polytechnic University，2014，28（2）：235．（in Chinese）

［6］ 宋花玉，蔡良才．飛機起飛航跡計算中發(fā)動機推力計算方法［J］．交通運輸工程學(xué)報，2010，10（2）：59．SONG Hua-yu，CAI Liang-cai．Computational Method of Engine Thrust in Aircraft Take-off Track Calculation［J］．Journal of Traffic and Transportation Engineering，2010，10（2）：59．（in Chinese）

［7］ 宋花玉．飛機起飛性能計算中發(fā)動機推力確定方法的改進［J］．航空計算技術(shù)，2015，45（1）：61．SONG Hua-yu．Improvement of Engine Thrust Confirmation Method in Aircraft Take-off Performance Calculation［J］．Aeronautical Computing Technique，2015，45（1）：61．（in Chinese）

［8］ 黃云清．數(shù)值計算方法［M］．北京：科學(xué)出版社，2010．HUANG Yun-qing．Numerical Computation Method［M］．Beijing：Science Press，2010．（in Chinese）

［9］ 朱金付．C＋＋實驗指導(dǎo)書［M］．北京：清華大學(xué)出版社，2009．ZHU Jin-fu．C＋＋ Experiment Instruction［M］．Beijing：Tsinghua University Press，2009．（in Chinese）