魏毅峰

(鄖陽師范高等?？茖W(xué)校數(shù)學(xué)與財(cái)經(jīng)系，湖北 十堰 442000)

基于Hausdorff距離的實(shí)例選擇算法研究

魏毅峰

(鄖陽師范高等?？茖W(xué)校數(shù)學(xué)與財(cái)經(jīng)系，湖北 十堰 442000)

闡述了實(shí)例選擇的定義和關(guān)注點(diǎn)，分析了Hausdorff距離的相關(guān)概念和特點(diǎn)，提出了一種基于權(quán)重的Hausdorff距離，并以此為基礎(chǔ)設(shè)計(jì)基于Hausdorff距離的實(shí)例選擇算法，最后對算法復(fù)雜性進(jìn)行了分析。

Hausdorff距離；實(shí)例選擇；算法；復(fù)雜性

海量數(shù)據(jù)的表現(xiàn)之一就是數(shù)據(jù)的量大，而許多針對海量數(shù)據(jù)進(jìn)行處理的應(yīng)用中，處理算法的時間開銷和空間開銷與實(shí)例數(shù)，或者實(shí)例數(shù)的平方成正比(有的甚至更高)。同時，由于數(shù)據(jù)集的實(shí)例數(shù)太多，導(dǎo)致在對其進(jìn)行處理時不能將整個數(shù)據(jù)集同時加載到內(nèi)存中，這要求算法訪問數(shù)據(jù)是順序掃描的，否則內(nèi)外存之間頻繁的數(shù)據(jù)交換將造成性能急速下降。因此海量數(shù)據(jù)的處理需要關(guān)注如下的2類問題：①采集到的原始數(shù)據(jù)集中可能存在較多相似性較大的數(shù)據(jù)，即冗余數(shù)據(jù)，這些數(shù)據(jù)對數(shù)據(jù)集的處理結(jié)果貢獻(xiàn)相對較小，但是增加了數(shù)據(jù)集處理的時間開銷；②已有的減少數(shù)據(jù)集中實(shí)例數(shù)的算法主要是針對某一類型的數(shù)據(jù)(例如分類型數(shù)據(jù)集)，它們或依靠已有的先驗(yàn)知識，或根據(jù)分類的目的去除影響分類效果的數(shù)據(jù)，有一定的應(yīng)用局限性。面對海量的真實(shí)數(shù)據(jù)集，需要研究一種具有一定普適性的數(shù)據(jù)約簡方法，使其能夠應(yīng)用到大多數(shù)數(shù)據(jù)集的約簡工作上，以滿足更多的應(yīng)用需求。

1 實(shí)例選擇的定義及關(guān)注點(diǎn)

實(shí)例選擇就是從海量的原始數(shù)據(jù)集中選擇有代表性的實(shí)例，形成一個相對較小的數(shù)據(jù)集，以降低處理數(shù)據(jù)集對時間和空間的需求。但是對實(shí)例的選擇應(yīng)滿足一個約束條件，即通過實(shí)例選擇而得到的數(shù)據(jù)集不應(yīng)對數(shù)據(jù)分類效果產(chǎn)生影響。一個得到普遍認(rèn)可的實(shí)例選擇的定義如下：

實(shí)例選擇應(yīng)該滿足以下2個前提：①訓(xùn)練集的實(shí)例個數(shù)必須大于測試集的實(shí)例個數(shù);②經(jīng)算法處理后得到的壓縮集必須使得其實(shí)例數(shù)目小于測試集的實(shí)例數(shù)目。

數(shù)據(jù)集進(jìn)行實(shí)例選擇時需要考慮以下幾個方面的問題：①約簡率(Data Reduction Rratio),約簡率反映了數(shù)據(jù)集約簡的程度;②約簡效果,約簡方法的約簡效果表示約簡后數(shù)據(jù)集和原始數(shù)據(jù)集的相似程度，相似程度越高，約簡的效果越強(qiáng);③對噪聲點(diǎn)和異常點(diǎn)的敏感程度,噪聲和異常點(diǎn)的存在會對后期的處理產(chǎn)生誤導(dǎo)作用，如果約簡集中過多地存在噪聲點(diǎn)和異常點(diǎn)，必定會影響后期的處理，實(shí)例選擇的算法應(yīng)該能很好地去除噪聲和異常點(diǎn)。

實(shí)例選擇的研究方法主要包括關(guān)鍵點(diǎn)選擇、邊界點(diǎn)去除和原型選擇等。

2 Hausdorff距離

2.1經(jīng)典Hausdorff距離

給定2個有限數(shù)據(jù)集A={a1,a2,…,ap}，B={b1,b2,…,bq},則數(shù)據(jù)集A和B之間的Hausdorff距離定義為：

H(A,B)=max(h(A,B),h(B,A))

(1)

式中，|a-b|表示點(diǎn)a和b之間的距離范數(shù)；h(A,B)稱為數(shù)據(jù)集A到數(shù)據(jù)集B的有向Hausdorff距離，即點(diǎn)集A中所有點(diǎn)到點(diǎn)集B的最小距離的最大值；h(B,A)為反向Hausdorff距離，它和h(A,B)中的較大者構(gòu)成了點(diǎn)集A和點(diǎn)集B的Hausdorff距離。

圖1 Hausdorff距離的幾何描述

結(jié)合上面的分析，Hausdorff距離可以用另外一種方法定義：

(2)

通過對Hausdorff距離定義(式(1)和式(2))的分析可以發(fā)現(xiàn)：①如果數(shù)據(jù)集A和數(shù)據(jù)集B是有界的，即A和B是緊子數(shù)據(jù)集，那么Hausdorff距離是有界的；反之，如果數(shù)據(jù)集A和數(shù)據(jù)集B是定義在非緊子數(shù)據(jù)集上，則Hausdorff距離有可能無窮大。②如果數(shù)據(jù)集A和數(shù)據(jù)集B是相同的閉包，數(shù)據(jù)集A和數(shù)據(jù)集B的Hausdorff距離為0；數(shù)據(jù)集A和數(shù)據(jù)集B在空間上越相似，則數(shù)據(jù)集A和數(shù)據(jù)集B之間的Hausdorff距離越小。③Hausdorff距離能夠較好的保持?jǐn)?shù)據(jù)集的輪廓特征。

2.2改進(jìn)的Hausdorff距離

經(jīng)典的Hausdorff距離受噪聲或者外部點(diǎn)的影響非常大。如2個形狀非常相似的點(diǎn)集A和B，如果點(diǎn)集A或者點(diǎn)集B中有一個噪聲點(diǎn)(或者叫外部點(diǎn))距離A或者B較遠(yuǎn)，那么根據(jù)上面的定義所計(jì)算出來的Hausdorff距離將會很大，這樣計(jì)算出來的Hausdorff距離無法真實(shí)反映點(diǎn)集A和點(diǎn)集B之間的相似性。相關(guān)研究提出了對Hausdorff距離改進(jìn)：Huttenlocher等［1］提出了部分Hausdorff距離的概念；Dubuisson和Jain［2］提出了均值Hausdorff距離(MHD)；Sim［3］提出了M-HD(M-estimation Hausdorff Distance)。

目前，Hausdorff距離的計(jì)算都是假設(shè)數(shù)據(jù)集中各個特征對于距離的貢獻(xiàn)是相同的，在實(shí)際應(yīng)用中往往并非如此，比如在評價一本書的好壞時，書的印刷次數(shù)這一特征一般來說比它的其他特征更能體現(xiàn)書的價值，因此應(yīng)該加重其在距離中的貢獻(xiàn)?；谶@個思想，筆者提出了一種基于權(quán)重的Hausdorff距離：

(3)

式中，xk為實(shí)例x的第k個特征；yk為實(shí)例y的第k個特征；wk為第k個特征的權(quán)重；D為實(shí)例的特征數(shù)。

改進(jìn)的Hausdorff距離可以去除噪音和外部點(diǎn)的影響，同時考慮了數(shù)據(jù)集中特征的權(quán)重，增強(qiáng)了Hausdorff距離的普適性。

3 基于Hausdorff距離的實(shí)例選擇

3.1算法描述

在一個數(shù)據(jù)集中，某些點(diǎn)的去除對數(shù)據(jù)集的數(shù)據(jù)分布影響較小，而有些點(diǎn)的去除則對數(shù)據(jù)集的數(shù)據(jù)分布影響較大。在原始數(shù)據(jù)集中去除某一數(shù)據(jù)點(diǎn)后得到的數(shù)據(jù)集與原數(shù)據(jù)集之間的Hausdorff距離越小，則該數(shù)據(jù)點(diǎn)對原始數(shù)據(jù)集分布影響越小。由此得到基于Hausdorff距離的實(shí)例選擇的核心思想，即去除數(shù)據(jù)集中對數(shù)據(jù)集分布影響小的實(shí)例。對于給定數(shù)據(jù)集A，基于Hausdorff距離的實(shí)例選擇算法的思想為：①取數(shù)據(jù)集中任意一個實(shí)例x；②去除實(shí)例x，得到數(shù)據(jù)集B；③計(jì)算數(shù)據(jù)集A和數(shù)據(jù)集B的Hausdorff距離Hd；④如果Hd小于給定的閾值μ，則該實(shí)例可以除去，否則保留該實(shí)例，重復(fù)①到④的工作直到所有實(shí)例都遍歷到。

在上述描述的基礎(chǔ)上，可以得到基于Hausdorff距離的實(shí)例選擇算法：

input：Original Data setA，Thresoldμ，WeightW

output：Reduction Data setB

C=A;

For eachx∈Cdo

End for

可以看出，參數(shù)μ將影響數(shù)據(jù)集的約簡率，即μ越大，約簡率越高，反之則越小。

3.2算法復(fù)雜性分析

基于Hausdorff距離的實(shí)例選擇算法能夠很好的利用2個數(shù)據(jù)集的全局特點(diǎn)，全局考慮數(shù)據(jù)集的分布情況，約簡效果較好。但是，由于每次計(jì)算都要考慮數(shù)據(jù)集中的全部數(shù)據(jù)，從而導(dǎo)致了算法的時間復(fù)雜度較大。從算法的描述可以看出，算法需要對數(shù)據(jù)集中的所有實(shí)例進(jìn)行遍歷，因此時間復(fù)雜度與數(shù)據(jù)集的大小有關(guān)。同時，在分析每個實(shí)例的情況時，都需要計(jì)算去除該實(shí)例后的數(shù)據(jù)集和原始數(shù)據(jù)集之間的Hausdorff距離，而計(jì)算Hausdorff距離的時間復(fù)雜度為O(m×n)，其中m，n分別為2個數(shù)據(jù)集的大小。由此可以得出對于一個大小為n的數(shù)據(jù)集，算法的時間復(fù)雜度為O(n3)。相比于時間復(fù)雜度，算法的空間復(fù)雜度只與數(shù)據(jù)集的大小有關(guān)，即算法的空間復(fù)雜度為O(n)。

4 結(jié) 語

目前，數(shù)據(jù)約簡主要從特征選擇和實(shí)例選擇2方面來處理，前者的目標(biāo)是降低數(shù)據(jù)的維數(shù)，后者從原始數(shù)據(jù)集中選擇有代表性的數(shù)據(jù)，形成一個新的子數(shù)據(jù)集，使得對子數(shù)據(jù)集的處理等價或者近似等價于對原始數(shù)據(jù)集的處理，從而降低對計(jì)算和存儲的消耗，提高海量數(shù)據(jù)集處理的效率，筆者只討論后者。對于海量數(shù)據(jù)而言，時間復(fù)雜度還是偏高，可以采用數(shù)據(jù)分塊來解決不能將整個數(shù)據(jù)集同時加載到內(nèi)存中的問題，這些都是有待完善的地方。

［1］Huttenlocker D P,Kalnderman G A,Rucklidge W A.Comparing Images Using the Hausdorff Distance［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence,1993,15(3):850-863.

［2］Dubuisson M P,Jain A K. Modified Hausdorff distance for object matching［A］. Proceeding of IAPR Int Conf on Pattern Recognition (ICPR’94)［C］. 1994:566-568.

［3］Sim D G,Kwon O K,Park R H. Object Matching Algorithms using Robust Hausdorff Distance Measures［J］. IEEE Transactions on Image Processing,1999,8(3): 425-429.

10.3969/j.issn.1673-1409(N).2012.07.040

TP391

A

1673-1409(2012)07-N117-03

2012-04-25

魏毅峰(1978-)，男，1999年大學(xué)畢業(yè)，碩士,講師，現(xiàn)主要從事模式識別與智能系統(tǒng)方面的教學(xué)與研究工作。

［編輯］ 洪云飛