1、數據清理關鍵技術及其軟件平臺的研究與應用第一章 緒 論1.1 引 言我國目前正在大力推廣信息技術，實施各行各業的信息化工程。隨著信息化建設的不斷深入，企事業單位積累了大量的電子數據，這些數據非常重要。為了使信息系統中的數據更準確、一致，能支持正確決策，就要求所管理的數據準確、可靠。因此，企業數據質量的管理正在獲得越來越多的關注。但是，由于各種原因，如數據錄入錯誤、不同來源數據引起的不同表示方法、數據間的不一致等，導致企業現有系統數據庫中存在這樣或那樣的臟數據，主要表現為：不正確的字段值、重復的記錄、拼寫問題、不合法值、空值、不一致值、縮寫詞的不同，不遵循引用完整性等。根據“進去的是垃圾，出來的

2、也是垃圾（garbage in，garbage out）”這條原理，若不進行清理，這些臟數據會扭曲從數據中獲得的信息，影響信息系統的運行效果，也為企業構建數據倉庫、建立決策支持系統、應用商務智能帶來隱患。顯見，數據清理問題的重要性是不言而喻的。另外，從市場上眾多的相關產品，也可以明白這一點。然而，由于數據清理本身的一些特點，比如：1) 數據清理是具體應用問題，經常要具體問題具體分析，難于歸納出通用方法；2) 數據清理問題的數學建模困難。因此，目前在學術界，數據清理并沒有得到足夠的關注，針對這方面的研究也少，有些人甚至認為數據清理是一個需要大量勞動力的過程，而且往往過于依賴特定應用領域。其實不然

3、，對于數據清理有很多內容值得研究，比如：3) 在數據清理的研究中，盡管檢測相似重復記錄受到最多的關注，采取了許多措施，但檢測效率與檢測精度并不令人滿意。特別是在數據量非常大時，耗時太多，有待于更好的方法。作者在文獻中做了一些這方面工作，在相似重復記錄檢測中采用長度過濾方法優化相似檢測算法，避免了不必要的編輯距離計算，從而提高了相似重復記錄的檢測效率；4) 在數據清理的相關研究中，數據清理整體框架的研究正逐漸成為研究的熱點。對此，作者在文獻7中提出一個可擴展的數據清理軟件平臺，該軟件平臺具有開放的規則庫和算法庫，通過在規則庫中定義清理規則以及從算法庫中選擇合適的清理算法，可使該軟件平臺適用于不同

4、的數據源，從而使其具有較強的通用性和適應性；5) 目前，對數據清理的研究主要集中在結構化數據上。由于半結構化數據 XML（Extensible Markup Language，可擴展標識語言）的快速增長以及廣泛應用，其在數據清理中越來越重要。為了使 XML 數據源中的數據更準確、一致，如何清理這些 XML 相似重復數據，都是值得研究的，作者在文獻8中做了一些這方面工作；6) 另外，關于數據清理在一些業務領域中的應用也是值得研究，作者在文獻9、10中做了一些這方面的工作。當然，對任何現實世界中的數據源，人工完成數據清理是沒有問題的。一些單位每年要花費上百萬元來查找數據錯誤，手工清理是勞累的、費時

5、的和易出錯的。對于少量數據的數據源來說，采用人工清理就可以了，但對于規模較大的數據源，手工清理是不可行的，必須借助信息技術，采用自動清理方法。當然，在自動清理的過程中，仍需要人來參與，我們要做的就是盡可能減少人的參與。總之，在信息化建設過程中，數據清理是一個非常重要，而且較新的課題，有很多東西值得我們去研究。作為全文的引言，本章主要介紹數據質量的相關概念、數據清理的原理、數據清理軟件平臺的意義以及本文的內容安排。1.2 數據質量1.2.1 數據質量概念及分類目前，數據質量問題已引起廣泛的關注。什么是數據質量呢？數據質量問題并不僅僅是指數據錯誤。文獻22把數據質量定義為數據的一致性（consis

6、tency）、正確性（correctness）、完整性（completeness）和最小性（minimality）這 4 個指標在信息系統中得到滿足的程度，文獻23則把“適合使用”作為衡量數據質量的初步標準。一般說來，評價數據質量最主要的幾個指標是：1) 準確性（Accuracy）準確性是指數據源中實際數據值與假定正確數據值的一致程度；2) 完整性（Completeness）完整性是指數據源中需要數值的字段中無值缺失的程度；3) 一致性（Consistency）一致性是指數據源中數據對一組約束的滿足程度；4) 唯一性（Uniqueness）唯一性是指數據源中記錄以及編碼是否唯一；5) 適時性（

7、Timeliness）適時性是指在所要求的或指定的時間提供一個或多個數據項的程度；6) 有效性（Validity）有效性是指維護的數據足夠嚴格以滿足分類準則的接受要求。當建立一個信息系統的時候，即使進行了良好的設計和規劃，也不能保證在所有情況下，信息系統中數據的質量都能滿足用戶的要求。用戶錄入錯誤、企業合并以及企業環境隨著時間的推移而改變，這些都會影響所存放數據的質量。信息系統中可能存在的數據質量問題有很多種，總結起來主要有以下幾種：1) 重復的記錄重復的記錄是指在一個數據源中有指現實世界同一個實體的重復信息，或在多個數據源中有指現實世界同一個實體的重復信息。2) 不完整的數據由于錄入錯誤等原

8、因，字段值或記錄未被記入數據庫，造成信息系統數據源中應該有的字段或記錄缺失。3) 不正確的數據由于錄入錯誤，數據源中的數據未及時更新，或不正確的計算等，導致數據源中數據過時，或者一些數據與現實實體中字段的值不相符。4) 無法理解的數據值無法理解的數據值是指由于某些原因，導致數據源中的一些數據難以解釋或無法解釋，如偽值、多用途域、古怪的格式、密碼數據等。5) 不一致的數據數據不一致包括了多種問題，比如，由不同數據源來的數據很容易發生不一致；同一數據源的數據也會因位置、單位以及時間不同產生不一致。在以上這些問題中，前三種問題在數據源中出現的最多。根據數據質量問題產生的原因，數據質量問題可分成單數據

9、源問題和多數據源問題兩個方面，其分類如圖 1.1所示。1.2.2 單數據源數據質量問題單數據源數據質量問題可以分成模式級和實例級兩類問題進行分析，如圖 1.1 所示。一個數據源的數據質量很大程度上決定于控制這些數據的模式和完整性約束的等級。沒有模式的數據源，如文件，它對數據的輸入和保存沒有約束，于是出現錯誤和不一致的可能性就很大。因此，出現模式相關的數據質量問題是因為缺少合適的特定數據模型和特定的完整性約束，如差的模式設計，或者因為僅定義了很少一些約束來進行完整性控制。特定實例問題相關錯誤和不一致，如拼寫錯誤，不能在模式級預防。另外，不唯一的模式級特定約束不能防止重復的實例，如關于同一現實實體

10、的記錄可能會以不同的字段值輸入兩次。無論是模式級問題還是實例級問題，可以分成字段、記錄、記錄類型和數據源四種不同的問題范圍，分別說明如下：1) 字段：這類錯誤僅僅局限于單個字段的值。2) 記錄：這類錯誤表現在同一條記錄中不同字段值之間出現的不一致。3) 記錄類型：這類錯誤表現在同一個數據源中不同記錄之間的不一致關系。4) 數據源：這類錯誤表現在數據源中的某些字段值和其它數據源中相關值的不一致關系。四種不同情況的例子如表 1.1 和表 1.2 所示。表 1.1 單數據源中模式級的數據質量問題表 1.2 單數據源中實例級的數據質量問題1.2.3 多數據源集成時數據質量問題當多個數據源集成時，發生在

11、單數據源中的這些問題會更加嚴重。這是因為每個數據源都是為了特定應用，單獨開發、部署和維護的，這就很大程度上導致數據管理系統、數據模型、模式設計和實際數據的不同。每個數據源都可能含有臟數據，多數據源中的數據可能會出現不同表示、重復、沖突等現象。在模式級，模式設計的主要問題是命名沖突和結構沖突。命名沖突主要表現為不同的對象可能使用同一個命名，而同一對象可能使用不同的命名；結構沖突存在很多種不同的情況，一般是指在不同數據源中同一對象有不同表示，如不同的組成結構、不同的數據類型、不同的完整性約束等。除了模式級的沖突，很多沖突僅出現在實例級上，即數據沖突。由于不同數據源中數據的表示可能會不同，單數據源中

12、的所有問題都可能會出現，比如重復的記錄、沖突的記錄等。此外，在整個數據源中，盡管有時不同的數據源中有相同的字段名和類型，仍可能存在不同的數值表示，如對性別的描述，一個數據源中可能用“0/1”來描述，另一個數據源中可能會用“F/M”來描述，或者對一些數值的不同表示，如一個數據源中度量單位制可能用美元，另一個數據源中可能會用歐元。此外，不同數據源中的信息可能表示在不同的聚集級別上，如一個數據源中信息可能指的是每種產品的銷售量，而另一個數據源中信息可能指的是每組產品的銷售量。多數據源集成中的數據清理問題也是信息化建設中面臨的一個重要問題。對于這個問題，作者會在第五章進行研究。1.3 數據清理內涵及原

13、理通過以上對數據質量問題的分析，可以看出：數據質量問題是信息化建設中的一個重要問題，為了提高信息系統的數據質量，研究數據清理非常重要。數據清理（data cleaning）也稱數據清洗。數據清理的三個主要領域包括：數據倉庫（Data Warehouse，DW）、數據庫中的知識發現（Knowledge Discovery in Databases，KDD）和綜合數據質量管理（Total Data Quality Management，TDQM）。數據清理在不同的應用領域其要求不完全相同，如在數據倉庫環境下，數據清理是 ETL（Extraction抽取、Transition 轉換、Load 加載，

14、ETL）過程的一個重要部分，要考慮數據倉庫的集成性與面向主題的需要，包括數據的清理及結構轉換；在 KDD 中，數據清理主要是提高數據的可利用性，如去除噪聲、無關數據、空值，考慮時間順序和數據的變化等，但主要內容還是一樣的。目前，對于數據清理沒有統一的定義。文獻30認為數據清理是一個消除數據中的錯誤和不一致，解決對象識別問題的過程，文獻31則把數據清理定義為重復記錄的合并/清理問題。一般來說，從廣義上講，數據清理是將數據庫精簡以除去重復記錄，并使剩余部分轉換成標準可接收格式的過程；而狹義上的數據清理是特指在構建數據倉庫和實現數據挖掘前對數據源進行處理，使數據實現準確性、完整性、一致性、唯一性、適

15、時性、有效性以適應后續操作的過程。本文的研究是以信息化建設為背景，研究的重點是提高信息系統的數據質量，故作者本人認為：凡是有助于提高信息系統數據質量的處理過程，都可認為是數據清理。所以，數據清理可簡單看成就是從數據源中清除錯誤數值和重復記錄，即利用有關技術如數理統計、數據挖掘或預定義的清理規則等，從數據源中檢測和消除錯誤數據、不完整數據和重復數據，從而提高信息系統的數據質量。一般說來，數據清理包括以下幾個步驟：1) 數據分析數據分析是指從數據中發現控制數據的一般規則，比如字段域、業務規則等。通過對數據的分析，可定義出數據清理的規則，并選擇合適的清理算法。2) 數據檢測數據檢測是指根據預定義的清

16、理規則及相關數據清理算法，檢測數據是否正確，比如是否滿足字段域、業務規則等，或檢測記錄是否是重復記錄。3) 數據修正數據修正是指手工或自動地修正檢測到的錯誤數據或處理重復的記錄。對于數據清理應該滿足：數據清理應該能檢測和消除所有主要的錯誤和不一致，包括單數據源和多數據源集成時；數據清理方法能被這樣的工具支持，人工檢測和編程工作要盡可能少，并具有可擴展性。根據以上分析，數據清理的原理可總結為如圖 1.2 所示1.4 數據清理研究現狀分析1.4.1 國外研究動態數據清理的相關研究最早可追溯到 1959 年。自那時起，合并來自不同數據源的數據是一直被認為是一個重要而且很困難的問題，這些問題被作為記錄

17、連接、實例識別、對象識別等問題來研究。它們曾經是醫療、商業、稅務領域中的研究重點之一，在流行病的研究、欺騙檢測等方面都起到重要作用。這些問題的研究可以看成是數據清理的源頭。近年來，隨著信息化的進展，國外開始系統地研究數據清理問題。目前，在數據清理算法、方法和商用系統上都取得了一些成果。主要成果可分類如下：1) 特殊域清理特殊域清理工具主要解決某類特定應用域的數據清理問題，大多數是姓名和地址數據。比如：根據概率統計學原理查找數值異常的記錄；對姓名、地址、郵政編碼等進行清理等，這是目前研究得較多的領域，也是應用最成功的一類。如商用系統：Trillinm Software、Pure Integrat

18、e（Oracle）、Quick Address（QAS Systems）等。它們用一個匹配工具抽取被清理的數據，并把姓名和地址信息轉換成單個標準元素、有效的街道名、城市和郵政編碼。它們具體表現為用一個大的預定義的規則庫，來處理在清理過程中發現的問題。比如，Trillinm Software 的抽取和匹配模型包含二十多萬個商業規則。這些工具也提供了針對特定應用，使用戶自定義規則來定制或擴展規則庫的工具。2) 與特定應用領域無關的數據清理與特定應用領域無關的數據清理研究主要集中在清理重復的記錄上，其主要工具包括：Data Blade Module，ChoiceMaker，Integrity，Mer

19、ge/Purge Library（Sagent/QM Software），Match IT（Help IT Systems），Master Merge（Pitney Bowes），Data Cleanser（EDD）等。3) 數據清理框架為了使數據清理具有一定的通用性，近年來，關于數據清理的框架也有了一些研究。文獻44提出了一個數據清理框架，該框架清晰地分離邏輯規范層和物理實現層。用戶可以在邏輯層設計數據處理流程，確定清理過程需要執行的數據轉化步驟；在物理層實現這些數據轉化操作，并對它們進行優化。例如，用戶為了計算記錄之間的相似度，對輸入數據集指定執行匹配操作，而在物理層，數據清理系統會根據實

20、際數據的特點，選擇一個特定的實現方法。該算法可以進行優化，它無須計算所有記錄對的相似度，而同時又不會損害所要求的結果。除了分離邏輯層和物理層以外，文獻44還提出了一種描述性語言，該描述性語言可以在邏輯層上指定數據清理過程所需采取的數據轉化操作，并指定何時可以彈出例外，要求用戶的交互。該描述性語言還可以指定一些數據轉化操作的參數，比如記錄匹配操作所使用的距離函數等。在44研究的基礎上，文獻30,45實現了一個可擴展的數據清理工具 AJAX。文獻3,46提出了一個關于數據清理的交互式系統框架，該框架把數據轉化和差異檢測（discrepancy detection）緊密地集成在一起。用戶面對表單風格

21、的界面，能夠以直觀的圖形化方式逐步建立起整個數據轉化過程。在此過程中，用戶可以執行或者撤消轉化操作，而且操作的結果馬上就可以在屏幕上看到。后臺進程以增量方式檢測轉化后數據中存在的問題，如果檢測到，則及時報告給用戶。用戶利用系統提供的基本數據轉化操作，無須書寫復雜的程序就能夠完成數據清理任務，而且用戶能夠隨時看到每一步轉化操作后的結果，沒有很長的延遲。因此，該系統框架具有較好的交互性。再來看一下其它一些與數據清理有關的工具。市場上有很多工具都支持數據轉換和數據清理工作，特別是針對數據倉庫。1) 數據分析工具數據分析工具能處理實例數據、識別數據錯誤和不一致，從而得到相應的清理轉換。數據分析工具可分

22、成數據剖析和數據挖掘工具。Evoke Software公司的MigrationArchitect是少數商用數據剖析工具的一種，它能分析出每一個字段的元數據，比如：數據類型、長度、集的勢、離散值和它們的百分比、最小和最大值、缺失值、以及獨特性。Migration Architect 對開發數據遷移的目標模式也有所幫助。數據挖掘工具，如 WizSoft 公司的 WizRule和 Information Discovery 公司的Data Mining Suite能推斷字段和它們的值之間的關系，并計算出一個置信度來指示符合條件的記錄。WizRule 能顯示三種規則：數據公式、IF-THEN 規則，以

23、及能指示姓名拼寫錯誤的基于拼寫的規則。WizRule 也能自動地把那些偏離發現規則集的數據指定為可疑錯誤。2) 數據再工程工具數據再工程工具也能處理實例數據、識別數據錯誤和不一致，從而得到相應的清理轉換。比如，Vality 的 Integrity可以利用檢測模型和規則執行清理轉換。3) ETL 工具ETL 是數據倉庫系統中數據處理的關鍵操作。ETL 操作的實質就是根據數據處理的需要，將源數據對象經過 ETL 處理后加載到目標數據對象中。很多商業工具在很多方面支持數據倉庫的 ETL 過程，如 Data Stage（Ardent）、Data TransformationService（Micros

24、oft）、Warehouse Administrator（SAS）、PowerMart（Informatica）等。這些工具在關系數據庫系統上建立一個存儲器，以統一的方式管理關于數據源、目標模式、映射、腳本程序等所有元數據。通過文件、關系數據系統、以及標準接口，比如 ODBC（Open Database Connectivity，開放式數據庫連接），可以從操作型數據源中抽取模式和數據。數據轉換用一個容易使用的圖形界面來定義。為了指定單個的映射步驟，需要提供一個單獨的規則語言和一個全面的預定義轉換規則的庫。雖然這些 ETL 工具能夠提供大量數據的抽取、轉換和集成操作，但往往只能提供有限的數據清理

25、支持。也就是說，ETL 工具并不是完全針對數據清理。1.4.2 國內研究動態由于發達國家的信息化程度較高，各種信息系統的使用范圍廣、時間長，因此對數據清理的需求顯得較為迫切，所以關于數據清理的研究大多都集中在國外，而國外關于數據清理的研究主要是針對西文表示的數據，這些數據清理方法不一定完全適用于中文表示的數據。隨著國內信息化建設的快速發展，數據質量問題也越來越受到關注，對數據清理的研究也逐步展開，并取得了一定的成果，主要研究情況如下：復旦大學以周傲英教授為首的研究小組較早地認識到數據清理研究的重要價值，并已開始了數據清理的研究工作，目前他們取得的主要成果有：1) 提出了一個可擴展數據清洗框架的

26、定義該清洗框架以術語模型、處理描述文件、共享庫等概念和技術實現了模塊功能的可定制、系統的開放性和可擴展性。2) 提出了一種基于 N-Gram 的相似重復記錄檢測方法該方法先計算各記錄的N-Gram值，然后以各記錄的N-Gram值為排序鍵進行排序，再通過采用一種高效的應用無關的 Pair-wise 比較算法，通過計算兩記錄中單詞間的編輯距離來判斷記錄的相似與否，并采用一種改進的優先隊列算法來準確地聚類相似重復記錄。該方法在一定程度上有效地解決了相似重復記錄的檢測問題，但當數據量大，錯誤多，單詞間有互相影響時，該方法的初步聚類效果就會受到很大的影響。此外，該方法主要針對西文數據庫環境，不適用于中文

27、數據庫環境。3) 研究了一種檢測多語言數據重復記錄的綜合方法該方法充分考慮了中文數據庫的環境，有效地解決了多語言數據記錄的初步聚類和記錄比較問題。北京大學對數據清理也做了一些相關研究，他們主要解決了針對于客戶關系管理中客戶數據集成時重復記錄的數據清理問題。東南大學以董逸生教授為首的研究小組也對數據清理做了一些研究，他們主要是針對數據倉庫化過程中的數據清理問題進行研究。對于數據清理，作者本人在信息化實踐的基礎上，根據信息化建設的實際需要，也做了系統的研究，并取得了一些研究成果，相關內容會在后面的章節中做具體的論述。1.4.3 存在的問題目前，從國內外關于數據清理的研究現狀來看，主要體現在以下幾個

28、方面的不足：1) 數據清理屬于一個較新的研究課題，直接針對這方面的研究并不多。此外，數據清理的研究目前主要集中在西文數據庫上，中文數據清理與西文數據清理有較大的不同，如很多排序方法并不完全適用于中文數據庫，中文數據清理沒有引起重視。2) 數據清理的研究主要集中在字符型數據上，識別數值型字段之間的關系異常很不成熟與實用，數據挖掘算法在數據清理中的應用需要加強。3) 盡管檢測重復記錄受到很大的關注，采取了許多措施，但檢測效率與檢測精度問題并不令人滿意。特別是在數據量比較大時，耗時太多，有待于更好的檢測算法。4) 多數數據清理工具都是針對特定的領域，其應用受到一定的限制。在將來，特定領域的數據清理仍

29、將是應用重點，但較通用的清理方案會受到越來越多的關注。5) 國產的數據清理工具還很少，少量的國產數據清理工具主要研究了重復記錄的清理問題，目前還很少研究關于不完整數據、錯誤數據的清理問題，還沒有利用孤立點檢測的方法來檢測數據源中的錯誤數據。6) 目前，數據清理的研究主要集中在結構化數據上。半結構化的數據，如 XML數據已受到越來越多的重視，特別是由于 XML 自身所具有的特點，如通用性、自描述性，其在數據清理中應受到重視。1.5 數據清理軟件平臺的意義為了完成數據清理的任務，滿足信息化建設的需要，必須研制一個數據清理工具。由于數據清理的復雜性，數據清理涉及多種不同的清理算法以及清理規則，對數據

30、清理工具有以下要求：1) 對數據源進行數據清理時，清理相似重復記錄和清理錯誤數據的方法是不同的，針對不同的數據質量問題，應采用相應的清理方法有針對性的進行清理。因此，必須提供多種清理功能才能很好地完成數據源的清理工作。2) 數據清理工具不但要能清理重復數據，不完整數據、錯誤數據也要能清理，這樣才能全面提高信息系統的數據質量。3) 對于錯誤數據的清理，由于每種方法的適用范圍不同，故要盡可能的采用多種方法。所以，數據清理工具應能夠提供多種錯誤數據清理方法，并能夠擴充。4) 對不同的數據源，清理相似重復記錄時，相似度閾值 和字段權重w的取值會對清理效果有較大的影響，所以要能根據具體的數據源靈活地選取

31、 和w的值。5) 對不同的數據源，要求有不同的數據清理規則，能靈活地定義和修改數據清理規則很重要；6) 在相似重復記錄檢測中，如果數據源數據量較小，就沒有必要對記錄進行排序，可以對所有記錄進行比較，這就要求數據清理工具對數據源中數據量的大小要有較好的適應性。由前文分析可知，目前國內外已根據某種算法開發出一些各具特點的應用系統，或者開發出一些針對特定應用領域的清理軟件。但是，由于數據清理的復雜性，對不同的數據源，要求數據清理適應不同的數據類型、數據量以及具體業務，一種數據清理算法無論它采用多有效的措施，不可能在所有問題上表現出好的清理效果，不可能依靠一種或少數幾種算法普遍良好地解決各種數據清理問

32、題。有必要提供一種包含一系列數據清理算法以及輔助算法（用于數據預處理和可視化）并能利用具體業務知識、可不斷擴展的軟件，為不同背景下的數據清理提供算法方面的支持。為了有別于其它數據清理工具，作者稱之為數據清理軟件平臺。實現一個包含豐富算法的數據清理軟件平臺有助于利用問題的先驗知識在不同算法間取長補短，從而提高數據清理算法在不同應用中的清理效果。此外，雖然國外已經提出一些具有通用性的數據清理框架，并研制了相應的清理工具，但這些工具主要是針對西文數據庫，而我們的數據庫中數據往往以中文為主，這些工具對中文數據庫并不能完全適用。故此，本文提出一種可擴展的數據清理軟件平臺，該軟件平臺具有開放的規則庫和算法

33、庫，并提供大量的數據清理以及其它輔助算法。當對數據源進行清理時，根據具體的業務分析，通過預定義清理規則和選擇合適的算法，來清理數據源中的種種錯誤，具有較強的通用性和適應性，并大大提高了數據清理的綜合效果。1.6 論文研究目的與內容安排第二章 單數據源中相似重復記錄的清理2.1 引 言由于數據輸入錯誤、不標準的縮寫詞，或其它原因，數據庫中可能包含關于現實世界同一實體的重復記錄。雖然關系數據庫系統不允許含有重復主鍵值的記錄輸入，但是，由于數據輸入錯誤，不管主鍵的值是否被這些錯誤影響，關系數據庫不能再保證不存在重復的記錄。因此，在數據清理中，相似重復記錄的檢測與清除是一個重要問題。什么是相似重復記錄

34、呢？首先列舉兩個典型的重復記錄實例，如表 2.1 和表2.2 所示。表 2.1 為某 ERP 系統中關于供應商信息的四條記錄。表中編號為 G02001 和G02003 的兩條記錄看起來不一樣，但實際上兩條記錄除了“地址”略有不同之外，指的是同一個供應商。因此，這兩條記錄可稱為相似重復記錄。而表中編號為 G02002和 G02004 的兩條記錄除了“供應商編號”不同外，其它字段完全相同。因此，這兩條記錄可稱為完全重復記錄。表 2.2 為某高校學生管理信息系統中關于學生信息的三條記錄，該系統中的數據用的是英文表示。在表 2.2 中，學號為 B01051 和 B01053 的這兩條記錄看起來不一樣，

35、但這兩條記錄除了姓名的格式不同、所在學院數據中包含了最常見的拼寫錯誤：插入（Corllege）、刪除（Mecanical）、交換（Electircal）、替換（Engeneering）之外，但實際上指的是同一個學生。根據以上分析，數據源中的重復記錄可分成完全重復記錄和相似重復記錄，分別定義如下：定義 2.1 完全重復記錄完全重復記錄是指在數據表中除了主鍵外，其它各字段完全相同的記錄，或者是在那些設計差的數據庫中，沒有主鍵，所有字段完全相同的記錄。定義 2.1 相似重復記錄相似重復記錄是指那些客觀上表示現實世界同一實體的，但是由于在格式、拼寫上有些差異而導致數據庫系統不能正確識別的記錄。一般情況

36、下，對幾個記錄可能指同一現實世界實體的這種情況較感興趣，而不是在語句構成上相同的記錄。為了減少數據源中的冗余信息，重復記錄的清理是一項重要的任務。因此，本章主要研究如何清除數據源中的相似重復記錄，具體內容組織如下：第 2 節分析了相似重復記錄清理的相關研究；第 3 節給出了一種有效的相似重復記錄清理方法；在此方法的基礎上，第 4 節研究了一種提高相似重復記錄檢測精度的方法；為了提高該方法中相似重復記錄的檢測效率，第 5 節提出了一種提高相似重復記錄檢測效率的方法；第 6 節介紹了作者研制的記錄生成器，該生成器為第 7 節的實驗提供了條件；第 7 節通過實驗驗證了改進算法的效果；第 8 節總結了

37、本章的工作。需要指出的是，本章的研究主要針對中文數據庫。2.2 相似重復記錄清理的相關研究要想清理數據源中的相似重復記錄，必須要先通過某種方法檢測出相似重復記錄，然后采取一定的策略清除這些重復記錄，從而達到清理的目的。在相似重復記錄的檢測方面已經有了一些成果。在一個數據表中，完全重復記錄的標準檢測方法是先將數據庫中的記錄排序，然后，通過比較鄰近記錄是否相等來檢測完全重復記錄。完全重復記錄不管以記錄的哪一個部分進行分類，在分類排序后，都能保證互相相鄰。這種方法可被擴展后用來檢測相似重復記錄，研究人員在此基礎上提出了很多方法，比如，文獻62將整條記錄作為一個字符串進行排序，通過計算整個字符串的編輯

38、距離來檢測記錄是否相似；文獻31中提出的 Sorted-Neiberhood 方法以用戶定義的健作為排序鍵進行排序，然后，通過一組規則定義的相等理論判定記錄是否相似，其基本思想可描述如下：按照用戶定義的排序鍵對整個數據表進行排序，將可能匹配的記錄排列在一起。當然，按照某個排序鍵排一次序往往是不夠的，需要按照不同的排序鍵對數據多次排序，再將結果結合起來。具體說來，Sorted-Neiberhood 算法分為三步：一、 創建排序鍵抽取記錄中重要的字段或字段的一部分組成每條記錄的排序鍵，排序鍵的選擇對于檢測結果的準確性至關重要。二、 記錄排序用第一步生成的排序鍵對記錄排序。三、 合并定義一個固定大小

39、的窗口，在記錄列表上移動，比較窗口內的記錄是否相似，如圖 2.1 所示。如果窗口的大小為 L（ 2 LN），那么每條最新進入窗口的記錄與前面的 L-1 條記錄逐一比較以找到匹配記錄。窗口中第一條記錄滑出窗口。至于說如何叫相似，由用戶定義的規則指定，例如：假設 R1、R2 為兩條記錄IF R1 中的字段 Last name 等于 R2 中的字段 Last name ANDR1 中的字段 First name 等于 R2 中的字段 First name AND兩記錄的 Address 字段差別很小THENR1 和 R2 相似END IF其中，“字段的差別”是通過將距離函數的計算結果與閾值比較確定的

40、。距離函數一般包括：字符串編輯距離，語音距離和打字機距離，用戶也可以自己定義距離函數。Sorted-Neiberhood 算法的時間復雜度與定義的窗口大小有關，窗口大小為 2時，復雜度為 O ( NlogN)，窗口大小為 N 時，復雜度為O (N2)。在目前常用的相似重復記錄清理方法中，Sorted-Neiberhood 算法是較為流行的匹配與合并算法，并且該算法已被應用到幾個關于數據清理的軟件之中。文獻55先計算各記錄的 N-Gram 值，然后以各記錄的 N-Gram 值為排序鍵進行排序，再通過采用一種高效的應用無關的 Pair-wise 比較算法，通過計算兩記錄中單詞間的編輯距離來判斷記錄

41、的相似與否，并采用一種改進的優先隊列算法來準確地聚類相似重復記錄,該算法使用固定大小的優先隊列順序掃描已排序的記錄,通過比較當前記錄和隊列中記錄的距離來聚類相似重復記錄；文獻56在文獻55的基礎上提出了一種檢測多語言數據重復記錄的綜合方法。上述這些方法的基本思想可以總結為：先對數據表中的記錄排序，然后用某種方式檢測相鄰記錄是否為重復記錄，不同之處是所采用的排序方法和相似檢測方法不同。本章在對這些方法研究的基礎上，吸收這些方法的思想，來解決相似重復記錄的清理問題，并對算法的關鍵環節進行改進，提高了相似重復記錄的檢測效率和檢測精度。為了后文論述的方便，首先給出相似重復記錄清理中的幾個相關定義：定義

42、 2.3 記錄之間的相似度 S記錄之間的相似度S 是根據兩條記錄的內容而計算出的一個表示兩記錄相似程度的數值， 0 < S <1。S 越小，則兩記錄相似程度越高；若 S =0，則表示兩條記錄為完全重復記錄。定義 2.4 記錄相似檢測記錄相似檢測是指通過計算兩條記錄之間的相似度S ，來判定兩記錄是不是重復記錄。2.3 相似重復記錄的清理方法2.3.1 相似重復記錄清理方法總體描述根據以上分析，本文采用的相似重復記錄清理方法的原理可以總結為如圖 2.2所示。由圖 2.2 可以看出，相似重復記錄的清理過程可總結為：記錄排序記錄相似檢測相似重復記錄合并/清除。其清理過程可描述如下：首先，把

43、數據源中需要清理的數據通過 JDBC（Java DataBase Connectivity,Java 數據庫連接）接口調入到系統中來；然后，執行數據清理，記錄排序模塊從算法庫中調用排序算法，執行記錄之間的排序；在記錄已排序的基礎上，記錄相似檢測模塊從算法庫中調用相似檢測算法，作鄰近范圍內記錄間的相似檢測，從而計算出記錄間的相似度，并根據預定義的重復識別規則，來判定是否為相似重復記錄。為了能檢測到更多的重復記錄，一次排序不夠，要采用多輪排序，多輪比較，每次排序采用不同的鍵，然后把檢測到的所有重復記錄聚類到一起，從而完成重復記錄的檢測；最后，對所檢測出的每一組相似重復記錄根據預定義的合并/清除規則

44、，完成相似重復記錄的合并處理。由圖 2.2 可以看出，記錄排序和記錄相似檢測是相似重復記錄清理過程中的兩個重要步驟，下面分別討論這兩個步驟中的關鍵技術。2.3.2 記錄排序為了能查找到數據源中所有的重復記錄，必須比較每一個可能的記錄對，如此以來，檢測相似重復記錄是一個很昂貴的操作，當數據源中數據量很大時，這會導致是一個無效和不可行的方案。為了減少記錄之間的比較次數，提高檢測效率，常用的方法是僅比較相互距離在一定范圍的記錄，即先對數據表中的記錄排序，然后對鄰近記錄進行比較。比如，在文獻31中，作者在整個分類后的數據表中通過移動一個固定大小的窗口，比較附近的記錄。一個大小為 W 的窗口，在數據庫中

45、一次移動一個記錄，新記錄和這個窗口中的其它 W-1 個記錄相比較。這樣，記錄比較的次數從 O（T2 ）減少到 O（TW ），其中，T 為數據庫中記錄的總數。因此，當數據源中數據量很大時，應該采用記錄排序方法。對于記錄排序方法，文獻33使用某種應用相關的鍵來將相似記錄聚類到鄰近位置。文獻63根據用戶定義的鍵值來重排表記錄，并采用滑動窗口來 Pair-wise比較窗口內的記錄。文獻55是先計算記錄的 N-Gram 值，然后按該值進行排序；文獻56針對多語言文本的情況，采用序值表的方法來進行排序。由于本文的研究主要是針對中國信息化的現狀，所以作者主要考慮采用中文表達的記錄。根據對各種排序方法的分析，

46、作者采用序值表的方法來對記錄進行排序，該方法說明如下：對于西文字符，排序就是按西文字符的字典序排列，但對于漢字來說，存在多種排序方式。在國標 GB2312-80 中共收集漢字 6763 個，分成兩級，一級漢字字庫包括漢字 3755 個，按拼音字母排序，二級漢字字庫包括漢字 3008 個，按部首排序。由此可見漢字本身的編碼不滿足任何一種統一的序值規則，不適合作序值使用。為了解決序值不統一的問題，采取建立序值文件的方式。目前，漢字通常有以下三種排序方式：拼音序、筆劃序、部首序。對于漢字各種不同的排序方式，分別建立對應于 GB2312-80 漢字基本集的序值表。序值表中序值的存放按對應的漢字在漢字基

47、本集中出現的順序進行。因此，根據漢字的內碼（0XB0A1-0XF7FE）可以直接計算出序值表中存放對應序值的入口地址，計算公式如下：其中，c1 為漢字內碼的第一個字節（區碼）；c2 為漢字內碼的第二個字節（位碼）；N 為序值編碼的長度，N=2（用兩個字節來存放序值）；headoffset 是序值表中存放第一個漢字（“啊”字的編碼 OXBOA1）的位置。序值表相當于自定義的一種編碼，不同的排序方式對應各自的序值表。序值表的大小只有幾十 K，可以存放在內存中。根據上述公式，漢字的內碼可直接映射為獲取序值的地址索引，非常便于使用。對于要排序的字段，根據以上方法把該字段中所有的字符轉換成相應的序值，然

48、后，采快速排序算法可以對記錄進行排序。在此排序的基礎上，再采用相似重復記錄檢測算法對相鄰記錄進行檢測，從而提高了檢測效率。按以上方法重排記錄后，相似記錄被放在較接近的位置，從而可以在相對集中的范圍內作記錄的相似檢測。但是由于排序時對錯誤的位置非常敏感，不能保證排序后的重復記錄都在一起。因此這種方法也有一定的局限性。此外，對整個數據庫記錄進行重排的開銷也很大。因此，從實用的角度考慮，在實際應用中，對于小批量數據，如記錄總數小于 5 萬時，沒有必要采用復雜的記錄排序算法，可以直接進行記錄的比較，從而提高相似重復記錄的查全率。2.3.3 記錄相似檢測由圖2.2可以看出，記錄相似檢測是相似重復記錄清理

49、過程中的一個重要步驟，通過記錄相似檢測，可以判斷兩條記錄是不是相似重復記錄。對于記錄相似檢測，一般采用 Pair-wise 比較算法，它是一種比較成熟的方法。本文吸收Pair-wise 比較算法的思想，所采用的記錄相似檢測算法的偽碼描述如下：算法略過2.3.4 相似重復記錄檢測算法2.3.5 相似重復記錄的合并/清除當完成相似重復記錄的檢測之后，對檢測出的重復記錄要進行處理。對于一組相似重復記錄，一般有兩種處理方法：1. 第一種處理方法第一種處理方法是把一組相似重復記錄中的一個記錄看成是正確的，其它記錄看成是含有錯誤信息的重復記錄。于是，任務就是刪除數據庫中的重復記錄。在這種情況下，一些常用的

50、處理規則是：1) 人工規則人工規則是指由人工從一組相似重復記錄中選出一條最準確的記錄保留，并把其它重復記錄從數據庫中刪除掉，這種方法最簡單。2) 隨機規則隨機規則是指從一組相似重復記錄中隨機地選出一條記錄保留，并把其它重復記錄從數據庫中刪除掉。3) 最新規則在很多情況下，最新的記錄能更好地代表一組相似重復記錄。比如，越接近當前日期的信息準確性可能越高，經常使用賬戶上的地址要比退休賬戶上的地址權威一些。基于這種分析，最新規則是指選擇每一組相似重復記錄中最新的一條記錄保留，并把其它重復記錄從數據庫中刪除掉。4) 完整規則完整規則是指從一組相似重復記錄中選擇最完整的一條記錄保留，并把其它重復記錄從數

51、據庫中刪除掉。5) 實用規則因為重復率越高的信息可能越準確一些，比如，如果三條記錄中兩個供應商的電話號碼是相同的，那么重復的電話號碼可能是正確的。基于這種分析，實用規則是指從一組相似重復記錄中選擇與其它記錄匹配次數最多的一條記錄保留，并把其它重復記錄從數據庫中刪除掉。可以把以上方法定義成規則，存放在規則庫中，供用戶根據具體的業務要求選擇使用。2. 第二種處理方法第二種處理方法是把每一條相似重復記錄看成是信息源的一部分。于是，目的就是合并一組重復記錄，產生一個具有更完整信息的新記錄。該方法一般要由人工進行處理。以上給出了常用的幾種處理相似重復記錄的方法，至于在執行相似重復記錄的清理過程中采用什么

52、樣的處理方法，要根據具體的數據源以及用戶要求來確定。2.4 相似重復記錄檢測精度提高方法2.4.1 等級法的使用在 2.3.3 節中研究了如何比較記錄的相似性，其過程為：先比較兩條記錄中每個字段的相似度；然后對每個字段賦予不同的權重，計算出兩條記錄的相似度，從而判定兩條記錄是不是相似重復記錄。由此可見各個字段所賦予的權重對檢測精度影響很大，合適的賦值能提高記錄相似檢測的精度。文獻55在進行記錄比較時，沒有考慮各記錄中各字段的權重；文獻56雖然考慮到了字段權重的重要性，但沒有給出一個合適的權重選取方法。本節在對相關方法研究的基礎上，采用一種計算字段權重的有效方法等級法來計算各字段的權重。當進行相

53、似重復記錄檢測時，根據對具體業務的分析，采用該方法來計算相應字段的權重，然后，對不同的字段使用不同的權重，從而提高相似重復記錄檢測的精度。等級法是一種計算記錄字段權重的方法，它是讓用戶根據數據表中各個字段的重要程度來劃分等級，即最重要字段的等級指定為 1，第二重要的字段等級指定為2，等等。然后，根據記錄各字段的等級，計算其相應的權重。文獻72，73都表明采用等級法不但效果好，而且容易使用。表 2.4 和表 2.5 為使用等級法時所用的兩種表，其中，表 2.4 是交給每個操作用戶的表，操作用戶根據自己的認識，在這張表上給各字段劃分等級；表 2.5 是分析員用來綜合所有操作用戶意見的等級表。在表

54、2.4 和 2.5 中， Yk 表示數據表中記錄的K 個字段，Suk 是操作用戶 u 為字段Yk 所指定的等級，Sk表示各個字段最終統一的等級， k1 ,2.K ， u1 ,2.N 。表 2.4 中的“字段說明”用來補充說明字段的作用及意義，便于操作用戶準確地為各字段指定等級。表 2.5 中匯集了不同操作用戶給各個字段指定的等級值，根據每個操作用戶所給的等級值，可以計算出各個字段最終統一的等級。2.4.2 等級轉變成權重的方法2.4.3 利用權重提高檢測精度在運行相似重復記錄檢測的過程中，首先采用等級法來獲取記錄中不同字段的等級，并采用 RC 方法生成各字段相應的權重。然后，在記錄相似檢測過程

55、中對不同字段指定不同的權重，這樣可提高相似重復記錄的檢測精度，從而更好地識別重復記錄。采用等級法生成的權重存放在規則庫中，供運行數據清理時調用。在第七章的實例中，作者會采用這種方法來檢測相似重復記錄，通過實例來驗證這種方法的有效性。2.5 相似重復記錄檢測效率提高方法2.5.1 提高檢測效率的方法分析快速完成數據清理是很重要的，因此，必須提高相似重復記錄的檢測效率。從前面的分析可以看出：在相似重復記錄檢測過程中，記錄間的相似檢測是一個重要問題，其關鍵步驟是記錄中各字段的相似檢測，其效率直接影響整個算法的效率，記錄中大多字段采用編輯距離算法來檢測，由于編輯距離算法的復雜度為 O ( m×

56、; n)，當數據量很大時，如不采用一種高效的過濾方法來減少不必要的編輯距離計算，則會導致相似檢測時間過長。因此，為了提高相似重復記錄的檢測效率，本文提出了一種優化相似重復記錄檢測效率的方法，該方法采用長度過濾方法減少不必要的編輯距離計算。實驗證明：長度過濾方法能有效地減少不必要的編輯距離計算，降低相似檢測時間，從而提高了相似重復記錄的檢測效率。由于作者提出的這種優化方法用于記錄相似檢測模塊中，所以，不管記錄相似檢測過程中是否進行記錄排序，這種優化方法都適用。2.5.2 長度過濾方法2.6 實驗準備記錄生成器的研制2.6.1 記錄生成器的作用2.6.2 記錄生成器的原理及實現2.7 改進算法檢測

57、效果的實驗驗證2.7.1 度量相似重復記錄檢測效果的標準2.7.2 長度過濾方法有效性的實驗檢測2.7.3 實驗結果分析2.8 本章小結如何消除數據源中的重復信息是數據清理研究中的一個熱門課題。本章在研究了相似重復記錄清理相關技術的基礎上，給出了一種相似重復記錄清理的綜合方法，并對該方法進行了改進，從而提高了該方法的檢測精度和檢測效率。本文中的方法和文獻39，55，56中所描述的相似重復記錄檢測方法相比，從兩種重要的途徑上進行了改進：第一個改進是為了提高相似重復記錄的檢測精度，采用等級法為記錄字段指定合適的權重，從而提高了相似重復記錄的檢測精度；第二個改進是提出了一種提高相似重復記錄檢測效率的

58、方法，該方法采用長度過濾方法優化相似重復記錄檢測中的相似檢測算法，避免了不必要的編輯距離計算，從而提高了相似重復記錄的檢測效率。這兩種改進可以用于任何相似重復記錄檢測算法之中。此外，作者還構造了合適的實驗環境，作了大量的檢測實驗，翔實的實驗結果驗證了改進方法的科學性及效果。第三章 單數據源中不完整數據的清理3.1 引 言數據不完整是產生數據質量問題的一個重要因素，簡單地說，數據不完整是指數據源中字段值的缺失問題。表 3.1 是 ERP 系統中“檢驗單”數據表中的一些數據，表中給出了一些不完整數據的例子。在這個表中，由于種種原因，記錄中的一些字段值缺失，如第一條記錄中字段“送檢日期”的值為空，第二條記錄中字段“狀態”的值為空，第三條記錄中字段“送檢部門編號”的值為空。這種現象在數據源中會常常出現，然而并未引