基于特征的數據規格化方法

摘 要：針對數據清洗時數據的標準化問題提出采用基于特征的馬爾可夫模型來解決這一問題。在學習模型的過程中，通過最大熵方法提高樣本學習的泛化能力。這種方法能夠充分利用數據的重疊特征來辨識數據項對應的狀態，結合了統計模型和規則模型的優點。理論分析和實驗表明，該方法可以有效地實現數據清洗時的數據規格化。

關鍵詞：數據清洗；最大熵；馬爾可夫模型；重疊特征

中圖分類號：TP311.13 文獻標志碼：A

文章編號：1001-3695(2008)09-2679-05

Featurebased data standardization approach

HAN Jingyu1，2，YANG Kehua2，DONG Yisheng2

（1.School of Computer， Nanjing University of Posts Telecommunications， Nanjing 210003， China；2.Dept. of Computer Science Engineering， Southeast University， Nanjing 210096， China）

Abstract:This paper proposed a featurebased Markov model for data standardization during data cleansing . This approach makes use of overlapping features to identify the corresponding state of data items and every state is the result of statestate transition and observationstate transition probability.Thus，this model may combine both advantages of statistical model and rulebased model. Theory and experiment shows that our approach has a good performance for data standardization during data cleansing. 

Key words:data cleansing; maximum entropy; Markov model; overlapping features



0 引言

當確認一個數據源的數據存在數據質量問題后，要對它進行具體的清洗。數據規格化是數據清洗中一個重要環節，它經常是隨后的重復消除、缺失值填充的必需步驟^[1]。數據規格化的目的是實現數據類型和格式的統一。一條文本記錄中（不妨將一條文本信息也稱為記錄），由于不同記錄中各個數據項的排序和格式不統一，或者有些數據項缺失，使得數據項的識別和排序變得困難。這類問題主要出現在如下幾種情況：a）同一文本記錄中姓名、地址、郵政編碼等數據項的識別和排序；b）日期數據的年、月、日、星期、小時、分、秒的識別和排序，如表1所示；c）文獻引用目錄(bibliographic references)的作者、文章、刊物（會議）、卷（期）、發表時間的識別和排序等，如表2所示。筆者提出在數據具有一些可以利用的位置、格式等特征時，可以采用基于特征的馬爾可夫模型來解決這一問題，它能夠充分地利用數據中的統計規律和表達特征來實現數據的規格化。另一方面，在模型的學習過程中，為了使學習的模型具有好的泛化能力，本文采用最大熵原則建模^[2]。本文雖然以日期時間數據的規格化為例討論問題，但這種方法完全可以應用到其他有類似特性的數據上，后文的實驗驗證了這一點。 

本文論述了相關工作，概述了根據數據的相互重疊的特征進行數據規格化的思路，說明了數據規格化時對數據的預處理和特征選擇，闡述了根據最大熵原理進行馬爾可夫模型學習的具體算法，給出了如何根據學習得到的模型來識別數據項對應的狀態，從而實現數據的規格化。表1 日期時間數據示例

iddatetimeiddatetime

11999/3/4213th dec 2003

3year 19934date:April 13th 2005，01:06 am

54，1938/9/3，23:43620050408 21:28

731 September 200585，4/3/03 05:34 pm

92003 910May22，2005 at 4:51 PM

111 Jun 200512Sunday April 20th 2003

134，2003080114date:Fri. 3 25，05 Time:6:00 pm

1506/01/2005 04:46:04 pm16May 20th，2004

表2 文獻引用示例

引用示例

1In VLDB-96，251-262. Selinger， P.;Astrahan， M.; Chamberlin， D.; Lorie， R.; and Price， T. 1979. Access path selection in a relational database management system. In SIGMOD’79

2McGrawHill. Selinger， P.; Astrahan， M.; Chamberlin， D.; Lorie， R.; and Price， T. 1979. Access path selection in a relational database management system. In SIGMOD’79

3SIAM Journal of Computing， 17(6):12531262. Selinger， G.， Astrahan， M.， Chamberlin， D.， Lorie， R.， and Price， T. (1979). Access Path Selection in a Relational Database Management System. In Proceedings of the ACM SIGMOD International Conference on Management of Data， pages 2334

4P.G.Selinger et-al : Access Path Selection in a Relational Database Management System， Proc. ACM SIGMOD Conf.， Boston， 1979， pp 2334

5Sellinger， P.G.et al.，\"Access Path Selection in a Relational Database Management System， \" in Proc. SIGMOD Intl. Conf on Mgt. of Data， 1979

1 相關工作

數據集成的過程中，數據規格化實際上分成兩個步驟：a）將記錄的各個數據項準確地識別和分割；b）將分割后的各個數據項轉換成統一的格式。其中a）是最關鍵的，目前這類問題的解決主要采用人工定義規則的方法來處理，如AutoStan采用人工定義解析和轉換規則的方法來解決這一問題^[3]，但這類方法的手工工作量很大。為了盡可能自動化地來實現，Rapier^[4]、Nodose^[5]等采取確定性的方法提取數據分割規則。Febrl系統^[6]中首次提出采用基于字典的隱馬爾可夫模型對人名、地址數據進行規格化。這種方法的主要不足在于它是一種統計模型，而數據特征如拼寫格式、上下文特征、數據長度等對狀態的決定作用在該模型中得不到體現，有待于進一步改進。

另外一個與本文研究相關的內容是隱馬爾可夫概率模型。馬爾可夫模型描述的是一個隨機變量序列，對于一個觀察值序列O={O1，O2，…，OT}，隱含著一個狀態序列S={S1，S2，…，ST}，如果它具有如下兩個性質：a）P(St+1|St，St-1，…，S1)=P(St+1|St)，即一階馬爾可夫性；b)對任意t，i，P(St+1|St)=P(Si+1|Si)，即狀態與具體時間無關，稱該隨機變量序列為馬爾可夫鏈，這樣一個模型就稱為馬爾可夫模型。隱馬爾可夫模型（HMM）是一個五元組（S，O，A，B，π）。其中：狀態集合S={s1，s2，…，sw}；觀察值集合O={o1，o2，…，oM}；A＝{aij}表示從狀態si轉移到狀態sj的概率B={bjk}表示在狀態sj輸出符號ok的概率；π＝{πi}代表初始狀態分布概率。它是一個雙重馬爾可夫隨機過程，它的任何一個當前狀態按照一定的概率依賴于前一狀態，當前的輸出觀測符號按照一定的概率依賴于當前狀態。隱馬爾可夫模型由于在序列數據處理方面的優異性能，使它在自然語言處理尤其是語音識別領域（speechrecognition）得到了成功應用^[2，7~9]。近年來它在信息抽取方面也得到應用，如Datamold^[10]首次提出用隱馬爾可夫模型對文本記錄分割抽取。

2 基于特征的數據規格化

為了清楚，本文以表1中所示的日期時間數據為例進行討論。對于表1所示的數據，不同記錄中年、月、日、小時、分、秒等各個字段的排序和格式可能不相同，而且有些值是缺失的。本文把星期、年、月、日、小時、分、秒等七個字段各自看做一個狀態，規格化的目的是識別出記錄的各個數據項對應的狀態。為了解決這個問題，如果采用Febrl系統中所用的隱馬爾可夫模型來解決，會存在一些不足：a）它不能利用觀測數據的特征來判別它所對應的狀態，而只是根據狀態間的統計規律來推斷當前觀測數據的對應狀態。b）由于隱馬爾可夫模型是一階馬爾可夫過程，不能反映高階過程，為此它不能揭示前第i(i>1)個狀態對當前狀態的制約。比如第14條記錄的“date:Fri. 3 25，05”子串中，“05”對應的狀態不僅與前面的“25”有關，也與更前面的“date:”有關，但在隱馬爾可夫模型中得不到體現。c）這種模型認為當前觀測數據對應的狀態只與它前面的狀態有關，而與其后的狀態無關，實際上，這是不妥的。比如第15條記錄中，“04:46:04 pm”后面的“pm”對于它的狀態具有明顯的指示作用。

通過觀察發現，觀測數據有時有許多重疊的特征，它們對判別它所屬的狀態具有重要的作用。比如當遇到“21th”這個數據時，它的數字與“th”相組合的特征表明它很可能指的是某月21日，而不應只根據日、月、年間的狀態轉換概率來判斷它屬于何種狀態。另一方面，數據中往往具有多個相互重疊的特征，如第15條記錄中的“04:46:04 pm”部分，它具有兩個相互重疊的特征：a)它是含有冒號分割符的數字串；b)它后面尾隨一個后綴標志“pm”。這兩個重疊的特征對于判斷它是一個小時、分、秒的數據都起著重要作用。為此，本文提出采用基于特征的馬爾可夫模型來解決這一問題。這樣既可以利用狀態轉換的統計規律，又可以利用觀測數據所顯示的特征來判別它所對應的狀態，即本文認為一個觀測數據對應的狀態既按照概率依賴于前一個狀態，也依賴于它本身的格式特征和各種上下文特征。

本文的數據規格化工作分成三個階段:a)對數據進行適當的預處理并分析數據的可利用特征；b）采用最大熵馬爾可夫模型學習觀測數據狀態間的關系；c）利用學習得到的模型對數據進行分割、轉換，最終得到規格統一的數據。本文重點討論前兩個階段。

3 數據預處理和特征利用

本文以日期時間數據為例來分析數據的特征。日期時間類型的數據可以表示為如圖1所示的狀態層次結構。日期、時間是兩個高層次的狀態，日期對應星期、年、月、日四個基本狀態，時間對應小時、分、秒三個基本狀態。

3.1 預處理階段

預處理階段一方面是統一大小寫，去除多余空白等；另一方面是對含有前后綴標志的數據進行日期、時間字符串的劃分，以便于后面的特征權重的學習。在日期時間數據中經常有些重要的前綴標志符如date、time、at、year等，后綴標志符如am、pm等，它們對于識別緊鄰其前后的數據或緊鄰其前后的若干個數據的狀態具有重要指示作用。根據標志符是對緊鄰其前后的若干個數據項起作用，還是對緊鄰其前后的一個數據項起作用，可將其劃分成一級標志符（如date、time、at等）和二級標志符（如year、hh、mm、ss等）。前者對緊鄰其前后的若干個連續的數據項起指示作用，后者只對緊鄰其前后的數據項起指示作用。因此可以劃分成四類標志符：一級前綴標志符、二級前綴標志符、一級后綴標志符和二級后綴標志符。如果數據中存在上述標志符，須將指示符與其相關的數據項相關聯，以起到指示作用。如表1中的第14條記錄可以劃分成“date:Fri. 3 25，05”和“time:6:00 pm”兩個字符串，以利于后文的學習。

3.2 數據特征的利用

日期時間數據中的特征是辨識元素類型的關鍵。本文將特征劃分成三種類型：位置特征、上下文特征和格式特征（表3）。

1）位置特征 表征數據項在記錄或子字符串中的位置，如特征1、2、3、17、18等。

2）上下文特征 表征數據項前后的上下文符號，如特征4、5、6、7、8、9、15、16等。

3）格式特征 單詞本身的數字或字符格式特征，如特征10、11、12、13、14等。

表3 日期時間數據特征示例

數據特征數據特征

含有/分隔符的連續字符串的首項2含有/分隔符的連續字符串的中間項

3含有/分隔符的連續字符串的末項4后跟am的連續字符串的首項

5后跟pm的連續字符串的首項6以date:開頭的連續字符串的首項

7以time:開頭的連續字符串的末項8以at:開頭的連續字符串的首項

9有year前綴標志符10以st或rd、th結尾的數字字符串

11四位數字串121～30的數字

13五位數字串的首項141～12的數字

15其后是{Jan，Feb，…，Dec}集合中的單詞16其前是{Monday，Tuesday，…}集合中的單詞

17位于句首的數字單詞18位于句末的數字單詞

由于同一觀測數據可能有若干個相互重疊的特征，每個特征對辨識觀測數據的狀態發揮著不同的作用（通過權重來表征）。對于一個日期時間數據序列，為了辨識它的各個觀測數據項的對應狀態，本文采用基于特征的馬爾可夫模型來建模。學習過程中，由于訓練樣本常常不能涵蓋所有的特征，導致從樣本學習中得到的概率不具有好的推廣性，為此學習時采用最大熵的方法來解決^[2]，其中每個特征發揮的作用通過下章所述的GIS算法獲得。

4 基于特征的最大熵馬爾可夫模型的學習

0，否則

設P是空間S×O上所有滿足特征約束的分布，對于任意的s∈S，o∈O，如何從訓練樣本中學習得到概率p(s|o)的值是本文關注的問題。為了最有效地根據訓練樣本的經驗概率來擬合全局概率p*，可以采用最大熵原則來學習概率分布。最大熵原則是通過樣本的經驗概率擬合全局概率的一種方法，滿足最大熵原則的概率分布p*應當是：在對某個事件一無所知的情況下，應對未知的情況作盡可能少的假設，如采取均勻分布。采用最大熵原則建模時，實驗者只要集中精力選擇特征，而不必花費精力考慮各個特征的權重^[2]。由于是條件分布，根據香農的熵的計算式^[11]：

模型確定下來后，對于一個觀測數據序列o1，o2，…，om，就可以根據Veterbi動態規劃算法^[2]，求出它對應的概率最大的狀態序列s1，s2，…，sm。設δm(i)表示對于觀測序列o1，o2，…，om，om屬于狀態i的最大可能概率，遞歸地可得δm+1(j)=maxi δm(i)×p(j|i，o)。這樣可求得一個觀測數據序列對應的最大可能的狀態序列。根據得到的最大可能的狀態序列將各個數據項準確地劃分到各個字段中。這樣對于表1中的任一記錄，其各個數據項即可劃分到年、月、日、星期、小時、分、秒等七個字段中去。然后，根據用戶定義的要求將各個字段內容轉換成統一的格式，從而完成數據的規格化工作。

算法2描述了如何在學習的模型上進行日期時間數據項的識別。

算法2 

5 實驗分析

實驗平臺采用一臺256 MB內存、1.8 GHz主頻的PC機，后臺數據庫采用SQL Server 2000。

1)日期時間數據

實驗數據是如下產生的，采用Google搜索引擎分別以若干數字日期項搜到了許多含有日期時間的Web頁面；并采用東南大學數據庫組研制的網頁提取工具提取出其中包含的日期時間數據，獨立地構建四個種子數據集，每個種子數據集中含有各自特點的60個日期時間數據記錄（前文表1中即是部分有代表性的數據），在種子數據集的基礎上產生實驗數據集。由于對于一個特定的應用，數據會表現出一定的統計特征，按兩個參數來控制實驗數據集的產生：元素間的轉移概率，特征引入比例。

2)文獻引用目錄數據

到Citeseer的主頁上，按照若干關鍵字搜索文獻引用記錄信息，并采用網頁提取工具提取800條記錄保存下來作為實驗數據。實驗主要關注兩個方面的問題：相比于隱馬爾可夫模型的精度比較；是基于特征的最大熵方法的樣本學習的魯棒性。學習各個不同特征的權重值時的迭代次數為100。

5.1 精度比較

進行兩組實驗：一組是在日期時間數據上進行，另外一組是在文獻引用數據上進行。

5.1.1 日期時間數據上的精度測試

在合成的日期時間數據上進行了精度比較。在四個數據集set1、set2、set3、set4上，數據規模分別取500、1 000、2 000、3 000，比較了FMM（feature based Markov model）方法和HMM（hidden Markov model）方法的識別精度(如表4所示，F代表FMM，H代表HHMM)。對于每一個數據集，取其中的1/4用作訓練數據集（training instances），另外的3/4作為測試數據集(test instances)。精度是被正確標注狀態的數據項數目與所有數據項數目的比值。 

表4 日期時間數據上精度比較

5.1.2 文獻引用數據上的精度

這組實驗用citeseer上的文獻引用為實驗數據，數據對應的狀態集合為{author，title，conference，journal，volume，pages，year}。實驗時取其中的1/4作為訓練數據集，其余的3/4作為測試數據集。表5是對文獻引用數據所采用的部分特征示例。表6給出了FMM方法和HMM方法識別各個狀態的精度比較和平均精度比較。

表5 文獻引用數據特征示例

特征描述特征描述

含有proceedings的字符串含有international的字符串

含有conference的字符串含有journal的字符串

以In開頭的字符串含有transactions的字符串

以pp開頭的數字串1 900～2 050間的數字串

以et al結尾的字符串位于句首的字符串

含有“單個大寫字母”的子串句子的第2個子串

表6 文獻引用數據上精度比較

通過兩組實驗結果看到，FMM方法的識別精度要高于HMM方法。筆者分析這主要是因為隱馬爾可夫模型是一種一階馬爾可夫過程，不能夠揭示高階過程特性，即它認為任何一個當前狀態只受前一狀態的影響，而不受更前面的狀態的影響；另一方面，它不能揭示序列中某個觀測其后的狀態對前面狀態的影響，這顯然是不足的。本文的方法認為當前狀態是緊密依賴于觀測特征的，并且各個重疊的特征對字段的辨別發揮著各自不同的作用。這樣就避免了不利用數據特征而只根據統計規律對數據的字段類型作出不恰當的判斷，從而有效地彌補隱馬爾可夫模型的不足，因此會取得更好的效果。

5.2 樣本學習效果

學習的過程中必須對訓練數據集進行手工標注，為此訓練集的實例數目是學習時須關注的問題^[10]。基于特征的方法的一個重要優點是對于學習過程中沒有遇到的觀測實例，同樣具有好的分辨性。以日期時間數據的set1數據集為例，圖2、3分別給出了在測試數據集規模分別取500和3 000時，精度隨訓練樣例數目的變化情況（這里訓練集包含在測試數據集當中）。結果顯示在500個測試數據樣例時，12個訓練樣例可取得90％的精度，而33個樣例時則可以取得99％的精度；在3 000個測試數據樣例時，40個樣例時可以取得90％的精度，160個訓練樣例可取得95％的精度。同時本文觀察發現，在各個不同的測試數據規模500、1 000、2 000、3 000上，訓練樣本數目為測試數據集規模的12％左右都會達到約95％的精度，顯示了基于重疊特征的最大熵學習方法具有好的泛化能力。這有利于減少手工標注訓練樣本的工作量，這在數據清洗中是非常重要的。

6 結束語

數據規格化經常是數據清洗中的一個必需步驟。對于一個特定的應用，本文提出采用基于特征的最大熵馬爾可夫模型來解決這一問題，利用數據中的重疊的特征來識別數據項對應的字段類型。其優點主要在于：

a）基于特征的方法可以根據數據相互重疊的特征來判斷它所對應的狀態，比基于字典的方式具有更好的推廣能力^[6]，尤其在無法窮盡所有可能出現的觀測數據的情況下。b）本文采用的模型，將數據對應的狀態看做是狀態轉換概率和特征—觀測概率的聯合效果，結合了隱馬爾可夫模型的統計優越性和特征判別的優越性。

理論分析和實驗表明，這是解決數據規格化的一種有效方法。下一步研究工作是如何優化地選擇特征。

參考文獻：

［1］DASU T，JOHNSON T.Exploratory data mining and data cleaning[M].[S.l.]:Wiley Press，2003. [2]RATNAPARKHI A.A simple introduction to maximum entropy models for natural language processing[R].US:University of Pennsylvania，1997.

[3]TECHNOLOGIES M.Autostan and automatch user’s manuals[K].Kennebunk，Maine:[s.n.]，1998.

[4]CALIFF M E，MOONEY R J.Relational learning of patternmatch rules for information extraction[C]//Proc of the 6th National Conference on Artificial Intelligence.Orlando，F L:[s.n.]，1999:328-334.

[5]ADELBERG B.NoDoSE:a tool for semiautomatically extracting structured and semistructured data from text documents[C]//Proc of ACM SIGMOD International Conference on Management of Data.New York:ACM，1998:283294.

[6]CHRISTEN P，CHURCHES T，ZHU J X.Probabilistic name and address cleaning and standardization[EB/OL].(2002-05-30).http://datamining.anu.edu.au/projects/linkage.html.

SENFELD R.Adaptive statistical language modeling:a maximum entropy approach[D].New York:CMU，1994.

[8]RABZNER L R.A tutorial on hidden Markov models and selected applications in speech recognition[C]//Proc of IEEE.Washington DC:IEEE Computer Society，1989:257-286.

[9]CHENS F，ROSENFIELD R.Efficient sampling and feature selection in whole sentence maximum entropy language model[C]//Proc of ICASSP’99.New York:IEEE Computer Society，1999:549-552.

[10]BORKAR V，DESHMUKH K，SARAWAGI S.Automatic segmentation of text into structured records[C]//Proc of ACM SIGMOD International Conference on Management of Data.New York:ACM，2001:175186.

[11]SHANNON C E.A mathematical theory of communication[J].ACM SIGMOBILE Mobile Computing and Communications Review，2001，5(1):3-55.

[12]DARROCH J N，RATCLIFF D.Generalized iterative scaling for loglinear models[J].The Annual of Mathematical Statistics，1972，43(5):14701480