基于改進豪斯多夫距離的非參數(shù)輪廓變點識別

聶　斌　孫會東　李　佩　杜文超

天津大學(xué),天津,300072

基于改進豪斯多夫距離的非參數(shù)輪廓變點識別

聶斌孫會東李佩杜文超

天津大學(xué),天津,300072

輪廓監(jiān)控中的變點識別問題是統(tǒng)計過程控制的重要研究內(nèi)容。以非參數(shù)輪廓數(shù)據(jù)為研究對象,運用圖像特征識別的豪斯多夫距離測量了樣本輪廓之間的特征差異,設(shè)計了改進方法，提出了基于二維空間的改進豪斯多夫距離算法，以識別非參數(shù)輪廓變點。大量的仿真與論證表明,改進方法在識別變點位置和穩(wěn)定性方面具有優(yōu)異的性能。

非參數(shù)輪廓;變點識別;豪斯多夫距離;T2統(tǒng)計量

0　引言

在工業(yè)生產(chǎn)中,質(zhì)量控制是統(tǒng)計質(zhì)量管理的重要工具。統(tǒng)計過程控制(statistical process control,SPC)即應(yīng)用統(tǒng)計方法對生產(chǎn)過程進行監(jiān)控,可以通過分析工具直觀地觀察到過程中發(fā)生的異常波動。隨著科學(xué)技術(shù)的發(fā)展，產(chǎn)品的質(zhì)量特征從單一性逐漸過渡到多樣性,質(zhì)量監(jiān)控也發(fā)展為需測量一系列產(chǎn)品特征參數(shù),以便對產(chǎn)品質(zhì)量進行更出色的監(jiān)控。近年來,輪廓監(jiān)控已成為學(xué)者們研究的熱點。

所謂“輪廓”即為描述產(chǎn)品質(zhì)量特性的函數(shù)關(guān)系,其響應(yīng)參數(shù)對應(yīng)一個或多個產(chǎn)品解釋變量。輪廓監(jiān)控方法是將控制圖理論與其他數(shù)據(jù)分析技術(shù)相結(jié)合，對以質(zhì)量特性為輪廓的產(chǎn)品進行質(zhì)量監(jiān)控的方法，如鍛件鍛壓力、半導(dǎo)體制造中晶體腔體和發(fā)動機葉片等輪廓監(jiān)控問題。Hawkins等[1]提出,輪廓監(jiān)控包含兩個階段:在階段一(Phase Ⅰ),通過對歷史樣本數(shù)據(jù)的分析，判斷失控樣本點并移除，從而確立受控的輪廓參數(shù)；在階段二(Phase Ⅱ),通過Phase I確定的受控狀態(tài)的產(chǎn)品輪廓參數(shù)，時時動態(tài)檢驗未來數(shù)據(jù)受控與否。

在現(xiàn)階段的研究中,簡單線性輪廓的監(jiān)測問題已經(jīng)相對成熟[2-4]。然而,在工程應(yīng)用和理論研究方面,往往面對的是非線性輪廓的問題,如Ding等[5]提到的鍛壓力監(jiān)控問題。與線性輪廓相比,非線性輪廓很難采用回歸分析理論,非參數(shù)輪廓模型回歸時則更加困難。在非線性輪廓回歸分析中，一些學(xué)者提出了自己的分析理論，如Williams等[6]和Zou等[7]分別提出了基于參數(shù)和非參數(shù)的非線性回歸模型,Jensen等[8]提出了基于T2的非線性固定輪廓，Qiu等[9]提出了基于指數(shù)加權(quán)滑動平均(EWMA)的非參數(shù)固定效應(yīng)模型分析方法,Chicken等[10]提出了半?yún)?shù)化的小波分析方法,鄒長亮[11]提出了基于懲罰函數(shù)的多元統(tǒng)計監(jiān)控問題,更加詳細的描述請參考文獻[12]。

近年來,通過非線性回歸方法評估參數(shù)的做法已經(jīng)具有相當(dāng)程度的局限性,這使得避開回歸分析采用其他輪廓監(jiān)控技術(shù)進行分析得到愈加廣泛的重視。以Ding等[5]為代表的眾多學(xué)者提出通過主成分分析(principal component analysis,PCA)的方法對高維輪廓降維并提取輪廓樣本數(shù)據(jù)之間的變異。Zhang等[13]提出了基于度量誤差和在工件輪廓解釋變量位置非固定的情況下,度量在容許公差值范圍內(nèi)的輪廓偏移值的方法。Shiau等[14]推薦采用HotellingT2控制圖來監(jiān)控非線性輪廓主成分得分。Williams等[15]引用了更為一般的非參數(shù)方法,即比較各輪廓與基準輪廓之間的差異性。Vaghefi等[16]提出了一種基于測量樣本輪廓與假定受控輪廓之間的面積偏移絕對值的新方法。Zhang等[17]提出了通過構(gòu)建χ2統(tǒng)計量來確定輪廓偏移標準的方法。

豪斯多夫距離算法是通過計算兩組樣本點之間的距離來度量樣本間相似度的算法。作為一種有效而實用的算法，豪斯多夫距離算法近年來被眾多學(xué)者廣泛應(yīng)用于圖像識別與目標跟蹤等模式識別領(lǐng)域。然而，豪斯多夫距離對噪聲點、孤立點等特殊點的敏感性也增加了豪斯多夫距離在識別樣本差異之間的偶然性。鑒于此，Dubuisson等[18]提出了樣本維度間距離均值的修正豪斯多夫距離的算法。

針對非參數(shù)輪廓變點識別問題,本文提出一種基于二維空間的修正豪斯多夫算法(two dimensional modified Hausdorff distance,TD-MHD),并測定樣本輪廓與基準輪廓之間的局部偏移,通過T2變點識別方法監(jiān)控非參數(shù)輪廓的局部變異變點。

1　模型提出與假設(shè)

對于非線性輪廓,假設(shè)產(chǎn)品特征Y=(y1,y2,…,yp)為某些固定位置的獨立變量X=(x1,x2,…,xp)的函數(shù),即任意時刻的產(chǎn)品質(zhì)量特性表現(xiàn)為Y與X的函數(shù)關(guān)系(輪廓),其中X代表測量范圍內(nèi)的取值點,Y代表其對應(yīng)的質(zhì)量特征值,則當(dāng)處于統(tǒng)計受控狀態(tài)時,存在以下關(guān)系：

yi j=f(xi j,βi j)+εi ji=1,2,…,m;j=1,2,…，p

(1)

其中，β為輪廓系數(shù),誤差項ε假定為獨立同分布(i. id.)正態(tài)隨機變量,服從N(μ,σ2)正態(tài)分布,m為輪廓的個數(shù),p為每個輪廓取值點的個數(shù)。在本文中,為了便于研究，假設(shè)每次測量位置不變,即獨立變量X對于任意樣本均相同。那么對于每個觀測的樣本而言,研究對象為響應(yīng)因子Y。對于m個樣本(y11,y22,…,y1p),…,(ym1,ym2,…,ym p),每個樣本均為p維二元矢量。

在本文中,假設(shè)原始樣本數(shù)據(jù)識別為單變點識別。假設(shè)變點位置為τ,非線性輪廓模型式(1)表示為

(2)

1.1傳統(tǒng)豪斯多夫距離(HD)

對于同一個空間內(nèi)任意兩個點集之間的相似程度,豪斯多夫距離在不需要點集之間一一對應(yīng)關(guān)系情況下可以有效處理很多特征點的情況。對于歷史樣本集中任意兩個獨立樣本yi=(yi1,yi2,…,yjp)和yj=(yj1,yj2,…,yjp),其中i,j=1,2,…,m且i≠j,則其豪斯多夫距離為

H(yi,yj)=max(h(yi,yj),h(yj,yi))

(3)

(4)

豪斯多夫距離可以在保留樣本間差異的情況下將樣本數(shù)據(jù)直接降到一維,大大減小了樣本數(shù)據(jù)的復(fù)雜度。樣本數(shù)據(jù)Y通過豪斯多夫距離降維得到:

DH=(H(y1,y2),H(y2,y3),…,H(ym-1,ym))

(5)

1.2基于二維空間的改進豪斯多夫距離

在傳統(tǒng)的豪斯多夫距離概念中,求解任何兩數(shù)組之間的距離首先需計算其中一組數(shù)組中任一數(shù)據(jù)到另一數(shù)組中所有數(shù)據(jù)的距離。然而，在輪廓等二維數(shù)據(jù)中，在計算上述距離時首先應(yīng)考慮該輪廓數(shù)據(jù)各觀察值的位置參數(shù)。因此，有必要將輪廓中各觀察值的位置參數(shù)引入距離測定，且大量仿真實驗亦表明了其必要性。在輪廓二維空間中,任意兩個輪廓觀測值(即兩個輪廓yi,yj)之間的距離d為

d(yi,yj)=

(6)

依次設(shè)d(yi,yj)=(di1,di2,…,dip)T=(dj1,dj2,…,djp),則dik(djk)表示第i個(第j個)輪廓的第k個觀測值與第j個(第i個)輪廓中第1,2,…,p個觀測值距離的矢量。

樣本輪廓yi j中存在隨機誤差項,在應(yīng)用傳統(tǒng)豪斯多夫距離情況下,誤差項的波動直接導(dǎo)致輪廓點之間距離的隨機波動放大,使得選取的最小點距離(式(4))隨隨機誤差而振蕩。為了消除隨機誤差產(chǎn)生的影響,本文采用求取兩樣本之間點距離中位數(shù)的平均值的方法來計算兩個樣本間的TD-MHD，計算公式如下:

(7)

(8)

則DT=(H′(y1,y2),H′(y2,y3),…,H′(ym-1,ym))即為求得樣本輪廓間的豪斯多夫距離。

1.3χ2統(tǒng)計量方法

針對高維復(fù)雜輪廓的變異識別問題,Zhang等[17]提出基于χ2統(tǒng)計量的控制方法。在輪廓控制Phase I,針對一組樣本輪廓數(shù)據(jù)，由于其參數(shù)的未知性,往往在構(gòu)建統(tǒng)計量時需要采用一定的方法尋求均值和方差參數(shù)估計值。所提χ2統(tǒng)計量如下：

(9)

其中,μs、Σs分別表示樣本輪廓的均值和協(xié)方差。由于在樣本數(shù)據(jù)中可能已經(jīng)存在變異點,因此,在如何評估均值和方差方面,本文提出基于中位數(shù)的均值和方差估計的方法。

(1)樣本均值計算方法如下：

(10)

(11)

(2)樣本協(xié)方差計算方法如下:

①在輪廓各維度固定情況下,依次計算兩兩對應(yīng)樣本(m(m-1)/2)中相同維度的數(shù)值差：

δ(i,k)j=yi j-yk ji,k=1,2,…,m;i

(12)

②通過上述(m(m-1)/2)對評估值,估計對偏差值為

(13)

(14)

1.4Hawkins多元T2統(tǒng)計量

文獻[19]提出了基于多元T2統(tǒng)計量度來監(jiān)控多元觀測值變異的方法。針對式(2),在任意第k個樣本位置處定義組合協(xié)方差Wk和差異性指標Zk如下：

(15)

(16)

(17)

從而,在任意變點位置k處的T2統(tǒng)計量為

(18)

則當(dāng)變點發(fā)生位置未知時,在所有可能發(fā)生位置中,使得統(tǒng)計量值最大者即為樣本變異的廣義似然比檢驗統(tǒng)計量,即

2　性能比較

本文采用文獻[17]的非參數(shù)輪廓模型產(chǎn)生一組非參數(shù)輪廓樣本數(shù)據(jù),即

yi j=10-20ae-axjsinxj+10e-axjcosxj+εi j

(19)

i=1,2,…,m;j=1,2,…,p

其中,εi j假定是服從于N(0,σ2)的i.i.d.正態(tài)隨機變量。在本文中,每次仿真產(chǎn)生m=200個隨機輪廓,每個輪廓維度p=100,x=0.08,0.16,…,8。參數(shù)a分別取0.5和1(σ=0.05)時的輪廓圖形如圖1所示。

圖1　輪廓圖形(σ=0.05)

本文中,假定樣本數(shù)據(jù)為單變點局部變異,變點位置為τ1=50,τ2=100,τ3=150。假定在受控情況下a=0.5,σ=0.5,在變異發(fā)生后,變點之后樣本在x11～x15位置發(fā)生變異,發(fā)生變異時參數(shù)a分別取0.6,0.7,…,1.9。為了真實性和可靠性,本文在任意參數(shù)情況下進行10 000次仿真。

在識別出變點位置時,本文采用校正R(即用AR表示)指標聚類評價方法分析變點識別優(yōu)劣性。文獻[20]將R指標和AR指標應(yīng)用到變點識別方法中。對單變點識別問題而言,R指標和AR指標通過比較聚類結(jié)果的相似性來評估變點識別的準確性,聚類結(jié)果即為識別出的變點對原始樣本的分類。假定變點位置檢測結(jié)果為τ,則全部樣本中前τ個樣本受控,后m-τ個樣本失控。變點位置τ將樣本分為兩個聚類,此種聚類結(jié)果定義為U。為了評價此聚類結(jié)果的好壞,繼而評價變點位置識別的準確度,需要對實際上述聚類結(jié)果U進行評價,評價標準即為仿真假定的變點位置τ0。同理，各算法識別出變點位置的聚類結(jié)果定義為V。因此,檢驗變點識別準確度問題轉(zhuǎn)化為檢驗聚類結(jié)果U與V的相似度,即當(dāng)τ=τ0時U=V,此時相似度AR應(yīng)為1。

為檢驗U與V的相似度，假設(shè):聚類結(jié)果中,

在U和V中都屬于同一類的樣本個數(shù)為a;在U中屬于同一類但在V中不屬于同一類的樣本個數(shù)為b;在U中不屬于同一類但在V中屬于同一類的樣本個數(shù)為c;在U和V中均不屬于同一類的樣本個數(shù)為d。

基于此，R指標和AR指標分別為

(20)

(21)

對于這兩種指標，R或AR值越大表明變點識別準確度越高,其中AR指標最大值為1,即為變點完全正確識別時的情況。本文根據(jù)圖1中識別出的變點位置,采用AR指標評價變點識別結(jié)果,識別結(jié)果如表1～表3所示,AR指標及其波動性如圖2所示。

通過表1～表3和圖2可以清楚地看到，在變點位置τ1=50,100,150時，通過TD-MHD和

表1　τ=50時AR指標

表2　τ=100時AR指標

表3　τ=150時AR指標

(a)局部變異τ=50

(b)局部變異τ=100

(c)局部變異τ=150圖2　AR指標和波動性

χ2識別出的變點位置將樣本集Y分為兩部分。通過對這兩部分的AR指標對比,表明無論變點在任何位置，當(dāng)局部變異a值變化較小時TD-MHD總表現(xiàn)出更優(yōu)異的性能。同時,隨著a值的增加，兩者表現(xiàn)出了大致相當(dāng)?shù)臋z測能力。但當(dāng)變點位置存在樣本輪廓中部時,χ2算法則完全失去了監(jiān)控的能力?？紤]到變點識別過程中的波動性,通過大量仿真評估AR指標的波動性可以看出,當(dāng)a≤0.7時,TD-MHD的波動性相對較大;而隨著a的逐漸增加,TD-MHD的波動性逐漸小于χ2算法的波動性，并且兩者的波動性在a>1.3之后逐漸趨近于0時，表現(xiàn)出較好的穩(wěn)定性。

為了更直觀地展示三種方法的識別變點位置時的優(yōu)劣性,圖3更加直觀和細化地表示出了TD-MHD、HD和χ2方法識別出的變點位置。如圖3所示,當(dāng)變點位置τ=50時可以看出,TD-MHD比χ2方法識別出來的變點位置更加快速地趨近于τ=50,而HD方法識別出來結(jié)果較差；當(dāng)變點位置τ=100時可以看出,TD-MHD能夠保持在τ=99～100位置區(qū)間,而χ2方法和HD表現(xiàn)出很強的波動性;同理,當(dāng)τ=150時表現(xiàn)出與τ=50時一樣的效果。綜合分析,TD-MHD具有明顯的優(yōu)勢。

(a)局部變異τ=50

(b)局部變異τ=100

(c)局部變異τ=150圖3　變點識別位置

3　結(jié)論

針對復(fù)雜非參數(shù)輪廓中存在局部變化的情形，本文在豪斯多夫距離算法的基礎(chǔ)上提出一種改進的二維空間豪斯多夫距離的算法,并通過T2統(tǒng)計量對Phase I樣本輪廓數(shù)據(jù)變點方法進行研究。通過與χ2算法進行仿真比較發(fā)現(xiàn):①在檢測輪廓局部偏移方面,無論變點存在于什么位置上,TD-MHD算法均能表現(xiàn)出優(yōu)異的性能，特別是在參數(shù)變異較小的情況下更佳；②當(dāng)變點位置發(fā)生在樣本數(shù)據(jù)中部時,χ2算法完全失效，此時TD-MHD仍能表現(xiàn)優(yōu)良的性能;③在識別穩(wěn)定性方面,TD-MHD算法在大多數(shù)情況下都具有較好的穩(wěn)定性,這對檢驗樣本變點的魯棒性具有重要意義。

雖然本文提出的TD-MHD算法有著很好的檢測偏移和識別變點的性能,但在識別較小偏移時,特別是輪廓偏移水平遠遠小于誤差因子時,仍存在著改進空間。同時,由于本文研究中提出的TD-MHD算法在受控情況下服從一定參數(shù)的正態(tài)分布,因此下一步將研究樣本輪廓控制線能夠較快地實時識別失控離群值。

[1]Hawkins D M,Qiu P,Kang C W.The Change-point Model for Statistical Process Control[J].Journal of Quality Technology,2003,35(4):355-366.

[2]Kang L,Albin S L.On-line Monitoring When the Process Yields a Linear Profile[J].Journal of Quality Technology,2000,32(4):418-426.

[3]Mahmoud M A, Parker P A, Woodall W H. A Change Point Method for Linear Profile Data[J].Quality and Reliability Engineering International,2007,23(2):247-268.

[4]聶斌,張軍軍.基于T2統(tǒng)計量的Phase I線性輪廓局部變化變點識別方法[J].系統(tǒng)工程,2014,32(1):108-117.

Nie Bin,Zhang Junjun.A Phase I Change-point Detection Method Based onT2Statistic to Identify the Local Changes in linear Profile[J].Systems Engineering,2014,32(1):108-117.

[5]Ding Y, Zeng L, Zhou S. Phase I Analysis for Monitoring Nonlinear Profiles in Manufacturing Processes[J].Journal of Quality Technology,2006, 38, 199-216.

[6]Williams J D, Woodall W H, Birch J B. Statistical Monitoring of Nonlinear Product and Process Quality Profiles[J].Quality and Reliability Engineering International, 2007, 23(8):925-941.

[7]Zou C,Tsung F,Wang Z.Monitoring General Linear Profiles Using Multivariate Exponential Weighted Moving Average Schemes[J].Technometrics,2007,49(4):395-408.

[8]Jensen W A,Birch J B.Profile Monitoring Via Nonlinear Mixed Models[J].Journal of Quality and Technology,2009,41(2):18-34.

[9]Qiu Peihua,Zou Changliang,Wang Zhaojun.Nonparametric Profile Monitoring by Mixed Effects Modeling[J].Technometrics,2010,52(3):265-293.

[10]Chicken E,Pignatiello J J,Simpson J R.Statistical Process Monitoring of Nonlinear Profile Using Wavelets[J].Journal of Quality Technology,2009,41(2):198-212.

[11]鄒長亮.復(fù)雜數(shù)據(jù)統(tǒng)計過程的若干研究[J].中國科學(xué):數(shù)學(xué),2013,43(8),741-750.

Zou Changliang.Some Study on Statistical Process Control of Complex Data[J].Sci. Sin. Math., 2013,43(8):741-750.

[12]Woodall W H.Current Research on Profile Monitoring[J].Revista Producao,2007,17(3):420-425.

[13]Zhang Yang, He Zhen, Fang Juntao. Nonparametric Control Scheme for Monitoring Phase Ⅱ Nonlinear Profiles with Varied Argument Values[J].Chinese Journal of Mechanical Engineering,2012,25(3):587-597.

[14]Shiau J H,Huang S L,Tsai M Y.Monitoring Nonlinear Profiles with Random Effects by Nonparametric Regression[J].Communications in Statistics-Theory and Methods,2009,38(10):1664-1679.

[15]Williams J D,Woodall W H,Birch J B.Statistical Monitoring of Nonlinear Product and Process Quality Profiles[J].Quality and Reliability Engineering International,2007,23(8):925-941.

[16]VaghefiA,Tajbakhsh S D,NoorossanaR. Phase Ⅱ Monitoring of Nonlinear Profiles[J].Communications in Statistics:Theory and Methods,2009,38(11):1834-1851.

[17]Zhang Hang,Albin Susan.Detecting Outliers in Complex Profiles Using a Control Chart Method[J].IIE Transactions,2009,41:335-345.

[18]Dubuisson M P,Jain A K.A Modified Hausdorff Distance for Object Matching[C]// Proc. International Conference on Pattern Recognition.Jerusalem,Israel,1994:566-567.

[19]Zamba K D,Hawkins D M. A Multivariate Change-point Model for Statistical Process Control[J].Technometrics,2006,48(4):539-549.

[20]Matteson D S,James N A.A Nonparametric Approach for Multiple Change Point Analysis of Multivariate Data[J].Journal of the American Statistical Association,2014,109,334-345.

(編輯袁興玲)

A Change Point Detection Method Based on Modified Hausdorff Distance in Nonparametric Profiles

Nie BinSun HuidongLi PeiDu Wenchao

Tianjin University,Tianjin,300072

Change point identification in profile monitoring is an important research topic in statistical process control.Herein,the profile had nonparametric characteristics.The proposed method was based on Hausdorff distance,and could be used to measure difference between profiles.A modified Hausdorff distance algorithm was proposed to identify nonparametric profile change point.The comparison results of simulation study show that when there exists local changes in nonparametric profile,the modified algorithem has advantages in locating change points and performance stability.

nonparametric profile;change point identification;Hausdorff distance;T2statistics

2014-04-21

國家杰出青年科學(xué)基金資助項目(71225006;7141123);國家自然科學(xué)基金資助項目(71102140)

TH165DOI：10.3969/j.issn.1004-132X.2015.08.008

聶斌,男,1971年生。天津大學(xué)管理與經(jīng)濟學(xué)部副教授。主要研究方向為統(tǒng)計過程控制、實驗設(shè)計和可靠性工程等。發(fā)表論文20余篇。孫會東,男,1990年生。天津大學(xué)管理與經(jīng)濟學(xué)部碩士研究生。李佩,女,1990年生。天津大學(xué)管理與經(jīng)濟學(xué)部碩士研究生。杜文超,男,1988年生。天津大學(xué)管理與經(jīng)濟學(xué)部碩士研究生。