基于Hausdorff距離的實例選擇算法研究

魏毅峰

(鄖陽師范高等專科學校數學與財經系，湖北 十堰 442000)

基于Hausdorff距離的實例選擇算法研究

魏毅峰

(鄖陽師范高等專科學校數學與財經系，湖北 十堰 442000)

闡述了實例選擇的定義和關注點，分析了Hausdorff距離的相關概念和特點，提出了一種基于權重的Hausdorff距離，并以此為基礎設計基于Hausdorff距離的實例選擇算法，最后對算法復雜性進行了分析。

Hausdorff距離；實例選擇；算法；復雜性

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

1 實例選擇的定義及關注點

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

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

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

實例選擇的研究方法主要包括關鍵點選擇、邊界點去除和原型選擇等。

2 Hausdorff距離

2.1經典Hausdorff距離

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

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

(1)

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

圖1 Hausdorff距離的幾何描述

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

(2)

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

2.2改進的Hausdorff距離

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

目前，Hausdorff距離的計算都是假設數據集中各個特征對于距離的貢獻是相同的，在實際應用中往往并非如此，比如在評價一本書的好壞時，書的印刷次數這一特征一般來說比它的其他特征更能體現書的價值，因此應該加重其在距離中的貢獻。基于這個思想，筆者提出了一種基于權重的Hausdorff距離：

(3)

式中，xk為實例x的第k個特征；yk為實例y的第k個特征；wk為第k個特征的權重；D為實例的特征數。

改進的Hausdorff距離可以去除噪音和外部點的影響，同時考慮了數據集中特征的權重，增強了Hausdorff距離的普適性。

3 基于Hausdorff距離的實例選擇

3.1算法描述

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

在上述描述的基礎上，可以得到基于Hausdorff距離的實例選擇算法：

input：Original Data setA，Thresoldμ，WeightW

output：Reduction Data setB

C=A;

For eachx∈Cdo

End for

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

3.2算法復雜性分析

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

4 結 語

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

［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年大學畢業，碩士,講師，現主要從事模式識別與智能系統方面的教學與研究工作。

［編輯］ 洪云飛