【正文】 引，非常便于使用。對于要排序的字段，根據(jù)以上方法把該字段中所有的字符轉(zhuǎn)換成相應(yīng)的序值，然后，采快速排序算法可以對記錄進行排序。在此排序的基礎(chǔ)上，再采用相似重復(fù)記錄檢測算法對相鄰記錄進行檢測，從而提高了檢測效率。按以上方法重排記錄后，相似記錄被放在較接近的位置，從而可以在相對集中的范圍內(nèi)作記錄的相似檢測。但是由于排序時對錯誤的位置非常敏感，不能保證排序后的重復(fù)記錄都在一起。因此這種方法也有一定的局限性。此外，對整個數(shù)據(jù)庫記錄進行重排的開銷也很大。因此，從實用的角度考慮，在實際應(yīng)用中，對于小批量數(shù)據(jù)，如記錄總數(shù)小于 5 萬時，沒有必要采用復(fù)雜的記錄排序算法，可以直接進行記錄的比較，從而提高相似重復(fù)記錄的查全率。記錄相似檢測記錄相似檢測是相似重復(fù)記錄清理過程中的一個重要步驟，通過記錄相似檢測，可以判斷兩條記錄是不是相似重復(fù)記錄。對于記錄相似檢測，一般采用 Pairwise 比較算法，它是一種比較成熟的方法。相似重復(fù)記錄的合并/清除當(dāng)完成相似重復(fù)記錄的檢測之后，對檢測出的重復(fù)記錄要進行處理。對于一組相似重復(fù)記錄，一般有兩種處理方法：1. 第一種處理方法第一種處理方法是把一組相似重復(fù)記錄中的一個記錄看成是正確的，其它記錄看成是含有錯誤信息的重復(fù)記錄。于是，任務(wù)就是刪除數(shù)據(jù)庫中的重復(fù)記錄。在這種情況下，一些常用的處理規(guī)則是：1) 人工規(guī)則人工規(guī)則是指由人工從一組相似重復(fù)記錄中選出一條最準確的記錄保留，并把其它重復(fù)記錄從數(shù)據(jù)庫中刪除掉，這種方法最簡單。2) 隨機規(guī)則隨機規(guī)則是指從一組相似重復(fù)記錄中隨機地選出一條記錄保留，并把其它重復(fù)記錄從數(shù)據(jù)庫中刪除掉。3) 最新規(guī)則在很多情況下，最新的記錄能更好地代表一組相似重復(fù)記錄。比如，越接近當(dāng)前日期的信息準確性可能越高，經(jīng)常使用賬戶上的地址要比退休賬戶上的地址權(quán)威一些?；谶@種分析，最新規(guī)則是指選擇每一組相似重復(fù)記錄中最新的一條記錄保留，并把其它重復(fù)記錄從數(shù)據(jù)庫中刪除掉。4) 完整規(guī)則完整規(guī)則是指從一組相似重復(fù)記錄中選擇最完整的一條記錄保留，并把其它重復(fù)記錄從數(shù)據(jù)庫中刪除掉。5) 實用規(guī)則因為重復(fù)率越高的信息可能越準確一些，比如，如果三條記錄中兩個供應(yīng)商的電話號碼是相同的，那么重復(fù)的電話號碼可能是正確的。基于這種分析，實用規(guī)則是指從一組相似重復(fù)記錄中選擇與其它記錄匹配次數(shù)最多的一條記錄保留，并把其它重復(fù)記錄從數(shù)據(jù)庫中刪除掉?？梢园岩陨戏椒ǘx成規(guī)則，存放在規(guī)則庫中，供用戶根據(jù)具體的業(yè)務(wù)要求選擇使用。2. 第二種處理方法第二種處理方法是把每一條相似重復(fù)記錄看成是信息源的一部分。于是，目的就是合并一組重復(fù)記錄，產(chǎn)生一個具有更完整信息的新記錄。該方法一般要由人工進行處理。在實際執(zhí)行相似重復(fù)記錄的清理過程中采用什么樣的處理方法，要根據(jù)具體的數(shù)據(jù)源以及用戶要求來確定。相似重復(fù)記錄檢測精度提高方法等級法的使用比較記錄的相似性，其過程為：先比較兩條記錄中每個字段的相似度；然后對每個字段賦予不同的權(quán)重，計算出兩條記錄的相似度，從而判定兩條記錄是不是相似重復(fù)記錄。由此可見各個字段所賦予的權(quán)重對檢測精度影響很大，合適的賦值能提高記錄相似檢測的精度。在進行記錄比較時，沒有考慮各記錄中各字段的權(quán)重；雖然考慮到了字段權(quán)重的重要性，但沒有給出一個合適的權(quán)重選取方法。本節(jié)在對相關(guān)方法研究的基礎(chǔ)上，采用一種計算字段權(quán)重的有效方法——等級法來計算各字段的權(quán)重。當(dāng)進行相似重復(fù)記錄檢測時，根據(jù)對具體業(yè)務(wù)的分析，采用該方法來計算相應(yīng)字段的權(quán)重，然后，對不同的字段使用不同的權(quán)重，從而提高相似重復(fù)記錄檢測的精度。等級法是一種計算記錄字段權(quán)重的方法，它是讓用戶根據(jù)數(shù)據(jù)表中各個字段的重要程度來劃分等級，即最重要字段的等級指定為 1，第二重要的字段等級指定為 2，等等。然后，根據(jù)記錄各字段的等級，計算其相應(yīng)的權(quán)重。都表明采用等級法不但效果好，而且容易使用。 利用權(quán)重提高檢測精度在運行相似重復(fù)記錄檢測的過程中，首先采用等級法來獲取記錄中不同字段的等級，并采用 RC 方法生成各字段相應(yīng)的權(quán)重。然后，在記錄相似檢測過程中對不同字段指定不同的權(quán)重，這樣可提高相似重復(fù)記錄的檢測精度，從而更好地識別重復(fù)記錄。采用等級法生成的權(quán)重存放在規(guī)則庫中，供運行數(shù)據(jù)清理時調(diào)用。相似重復(fù)記錄檢測效率提高方法提高檢測效率的方法分析快速完成數(shù)據(jù)清理是很重要的，因此，必須提高相似重復(fù)記錄的檢測效率。在相似重復(fù)記錄檢測過程中，記錄間的相似檢測是一個重要問題，其關(guān)鍵步驟是記錄中各字段的相似檢測，其效率直接影響整個算法的效率，記錄中大多字段采用編輯距離算法來檢測，由于編輯距離算法的復(fù)雜度為 O ( m n)，當(dāng)數(shù)據(jù)量很大時，如不采用一種高效的過濾方法來減少不必要的編輯距離計算，則會導(dǎo)致相似檢測時間過長。因此，為了提高相似重復(fù)記錄的檢測效率，有一種優(yōu)化相似重復(fù)記錄檢測效率的方法，該方法采用長度過濾方法減少不必要的編輯距離計算。實驗證明：長度過濾方法能有效地減少不必要的編輯距離計算，降低相似檢測時間，從而提高了相似重復(fù)記錄的檢測效率。單數(shù)據(jù)源中不完整數(shù)據(jù)的清理數(shù)據(jù)不完整是產(chǎn)生數(shù)據(jù)質(zhì)量問題的一個重要因素，簡單地說，數(shù)據(jù)不完整是指數(shù)據(jù)源中字段值的缺失問題。不完整數(shù)據(jù)的存在不但會影響信息系統(tǒng)的運行效果，還會引起決策錯誤，特別是數(shù)值數(shù)據(jù)中出現(xiàn)不完整數(shù)據(jù)。故必須要解決數(shù)據(jù)源中的數(shù)據(jù)不完整問題。在多數(shù)情況下，數(shù)據(jù)源之間的字段值并不是相互獨立的。所以，通過識別字段值之間的關(guān)系可以推斷出缺失的字段值?；谝陨戏治?，為了清理數(shù)據(jù)源中的不完整數(shù)據(jù)，應(yīng)首先檢測記錄的可用性，然后刪除不可用的記錄，最后，對可用記錄通過選用合適的方法來處理該記錄的缺失值，從而完成數(shù)據(jù)源中不完整數(shù)據(jù)的清理。不完整數(shù)據(jù)的清理方法對于數(shù)據(jù)源中不完整數(shù)據(jù)的清理，可分成以下三步來處理：1. 檢測數(shù)據(jù)源中的不完整數(shù)據(jù)要清理數(shù)據(jù)源中的不完整數(shù)據(jù)，首先要做的就是把數(shù)據(jù)源中的不完整數(shù)據(jù)檢測出來，以便于下一步的處理。2. 判斷數(shù)據(jù)的可用性如果一條記錄中字段值缺失的太多，或者剩余的字段值中根本就不包含關(guān)鍵信息，就沒有必要花費精力去處理該記錄。因此，對于檢測出的不完整數(shù)據(jù)，要根據(jù)每一條記錄的不完整程度以及其它因素，來決定這些記錄是保留還是刪除。判斷數(shù)據(jù)的可用性就是完成這一工作。3. 推斷缺失字段的值推斷缺失字段的值是指對那些要保留的記錄，要采取一定的方法來處理該記錄中缺失的字段值。清理數(shù)據(jù)源中不完整數(shù)據(jù)的過程簡要描述如下：首先，把數(shù)據(jù)源中需要清理的數(shù)據(jù)通過 JDBC 接口調(diào)入到系統(tǒng)中來，不完整數(shù)據(jù)檢測模塊調(diào)用算法庫中的檢測算法，來判定每條記錄是否完整。如果記錄完整，則無須清理，直接將該記錄通過 JDBC 接口導(dǎo)入到數(shù)據(jù)源中，如果記錄不完整，則把該記錄導(dǎo)入到記錄可用性檢測模塊中來；記錄可用性檢測模塊從算法庫中調(diào)用可用性檢測算法，執(zhí)行記錄的可用性檢測，然后根據(jù)規(guī)則庫中預(yù)定義的規(guī)則，來判定該記錄是否可用；如果記錄不可用，則直接刪除該記錄，如果記錄可用，則不完整數(shù)據(jù)處理模塊從算法庫中調(diào)用相關(guān)算法來處理該記錄中缺失的字段值；最后，處理完的數(shù)據(jù)經(jīng) JDBC 接口導(dǎo)入到數(shù)據(jù)源中。在以上這種不完整數(shù)據(jù)清理方法中，通過在規(guī)則庫中定義合適的閾值，能靈活、合理地確定記錄的取舍；對于要保留的記錄，又可以通過選用合適的不完整數(shù)據(jù)處理方法來處理該記錄，可見這種不完整數(shù)據(jù)清理方法具有較強的通用性和靈活性。所以，該方法能較好地完成不完整數(shù)據(jù)的清理工作。 不完整數(shù)據(jù)的可用性檢測記錄的可用性檢測是不完整數(shù)據(jù)清理過程中的一個重要步驟。如果一條記錄字段值缺失的太多，或者剩余的字段值中根本就不包含關(guān)鍵信息，就沒有必要花費精力去處理該記錄。因此，要解決數(shù)據(jù)的不完整問題，判斷記錄的可用性非常重要。判斷記錄的可用性也就是根據(jù)每一條記錄的不完整程度及其它因素，來決定該記錄是保留還是刪除。對于記錄的可用性檢測，方法是：先評估每一條記錄的不完整程度，也就是先計算每一條記錄中缺失字段值的百分比，再考慮其它因素，如記錄剩余的字段值中關(guān)鍵信息是否存在，然后決定記錄的取舍。由于當(dāng)一條記錄某字段取值為缺省值時，意味著該字段值已缺失，所以，把字段值為缺省值的也作為缺失值來處理。缺失字段值的處理在完成記錄可用性檢測之后，對那些要保留的不完整數(shù)據(jù)記錄 R ，要采取一定的方法來處理該記錄中缺失的字段值，一般采取以下幾種處理方法：1) 人工處理法對一些重要數(shù)據(jù)，或當(dāng)不完整數(shù)據(jù)的數(shù)據(jù)量不大時應(yīng)該采用這種方法。2) 常量值替代法常量替代法就是對所有缺失的字段值用同一個常量來填充，比如用“Unknown”或“Miss Value”，這種方法最簡單。但是，由于所有的缺失值都被當(dāng)成同一個值，容易導(dǎo)致錯誤的分析結(jié)果。3) 平均值替代法平均值替代法就是使用一個字段的平均值來填充該字段的所有缺失值。4) 常見值替代法常見值替代法就是使用一個字段中出現(xiàn)最多的那個值來填充該字段的所有缺失值。5) 估算值替代法估算值替代法是最復(fù)雜，也是最科學(xué)的一種處理方法。采用這種方法處理缺失字段值的過程為：首先采用相關(guān)算法，如回歸、判定樹歸納、K最臨近等算法預(yù)測該字段缺失值的可能值，然后用預(yù)測值填充缺失值。在執(zhí)行不完整數(shù)據(jù)的清理過程中采用什么樣的處理方法，要根據(jù)具體的數(shù)據(jù)源以及用戶要求來確定。單數(shù)據(jù)源中錯誤數(shù)據(jù)的清理在三種重要的數(shù)據(jù)質(zhì)量問題上，數(shù)據(jù)錯誤是最重要的數(shù)據(jù)質(zhì)量問題。簡單地說，數(shù)據(jù)錯誤是指數(shù)據(jù)源中記錄字段的值和實際的值不相符。如果信息系統(tǒng)中包含錯誤數(shù)據(jù)，記錄重復(fù)問題和數(shù)據(jù)不完整問題則會更難清理。故必須要清理數(shù)據(jù)源中的錯誤數(shù)據(jù)。對于錯誤數(shù)據(jù)的清理，有兩種相聯(lián)系的方法：1. 通過檢測數(shù)據(jù)表中單個字段的值來發(fā)現(xiàn)錯誤數(shù)據(jù)這種方法主要是根據(jù)數(shù)據(jù)表中單個字段值的數(shù)據(jù)類型、長度、取值范圍等，來發(fā)現(xiàn)數(shù)據(jù)表中的錯誤數(shù)據(jù)。2. 通過檢測字段之間以及記錄之間的關(guān)系來發(fā)現(xiàn)錯誤數(shù)據(jù)這種方法主要是通過在大量數(shù)據(jù)中發(fā)現(xiàn)特定的數(shù)據(jù)格式，如幾個字段之間的關(guān)系，從而得到字段之間的完整性約束，如采用函數(shù)依賴或特定應(yīng)用的業(yè)務(wù)規(guī)則來檢測并改正數(shù)據(jù)源中的錯誤數(shù)據(jù)。另外，采用一個具有高置信度的關(guān)聯(lián)規(guī)則能夠檢測違反這一規(guī)則的數(shù)據(jù)質(zhì)量問題，比如，一個置信度為 99%的關(guān)聯(lián)規(guī)則“總數(shù)＝數(shù)量 單價”表明 1%記錄不遵守這一規(guī)則，需要對記錄做進一步的檢查。對于這一方面，一些數(shù)據(jù)挖掘工具，如 WizSoft 公司的 WizRule 和 Information Discovery 公司的 Data Mining Suite，能通過推斷字段和它們的值之間的關(guān)系，計算出一個置信度來指示符合條件的記錄?；诠铝Ⅻc檢測的錯誤數(shù)據(jù)清理在數(shù)據(jù)源中經(jīng)常含有一定數(shù)量的異常值，它們與數(shù)據(jù)源的其它部分不同或不一致，這樣的數(shù)據(jù)常常被稱為孤立點（Outlier）。Hawkins 給出了孤立點本質(zhì)性的定義：孤立點是在數(shù)據(jù)源中與眾不同的數(shù)據(jù)，使人懷疑這些數(shù)據(jù)并非隨機偏差，而是產(chǎn)生于完全不同的機制。孤立點可能是度量或執(zhí)行錯誤所導(dǎo)致，也可能是固有的數(shù)據(jù)變異性的結(jié)果，例如，一個人的年齡為 999，可能是程序?qū)?shù)據(jù)表記錄中年齡字段的缺省設(shè)置所產(chǎn)生的；一個公司總經(jīng)理的工資，自然遠遠高于公司其他雇員的工資，成為一個孤立點；如果一個整型字段 99%的值在某一范圍內(nèi)，則剩下 1%的不在此范圍內(nèi)的記錄可以認為是異常。孤立點檢測是數(shù)據(jù)挖掘中的一個重要方面，用來發(fā)現(xiàn)數(shù)據(jù)源中顯著不同于其它數(shù)據(jù)的對象，它常常應(yīng)用在電信和信用卡欺騙檢測、貸款審批、氣象預(yù)報和客戶分類等領(lǐng)域中。由于數(shù)據(jù)錯誤往往表現(xiàn)為孤立點，所以，通過檢測并去除數(shù)據(jù)源中的孤立點可以達到數(shù)據(jù)清理的目的，從而提高數(shù)據(jù)源的數(shù)據(jù)質(zhì)量。但是，并非所有的孤立點都是錯誤的數(shù)據(jù)，所以，在檢測出孤立點后還應(yīng)結(jié)合領(lǐng)域知識或所存儲的元數(shù)據(jù)，從中找出相應(yīng)的錯誤數(shù)據(jù)。孤立點檢測的相關(guān)方法通過分析可以看出，如何檢測數(shù)據(jù)源中的孤立點是基于孤立點檢測的錯誤數(shù)據(jù)清理方法中的一個關(guān)鍵步驟，常用的有孤立點檢測算法。從 20 世紀 80 年代起，孤立點檢測問題就在統(tǒng)計學(xué)領(lǐng)域里得到廣泛研究。通常用戶用某個統(tǒng)計分布對數(shù)據(jù)點進行建模，再以假定的模型，根據(jù)點的分布來確定是否異常。目前，已經(jīng)研究出若干種檢測孤立點的方法，大多數(shù)方法建立在統(tǒng)計學(xué)的基礎(chǔ)上，這些方法大致可以分為 4 類：基于分布的、基于深度的、基于距離的和基于密度的，每種方法都給出了相應(yīng)的孤立點的定義。1. 基于分布的方法基于分布的方法對給定的數(shù)據(jù)集合假定一個分布或概率模型，如一個正態(tài)分布，然后根據(jù)模型對數(shù)據(jù)集中的每個點進行不一致性測試，如果與分布不符合，就認為它是一個孤立點。這種方法的缺陷是：要求知道數(shù)據(jù)集參數(shù)（如假設(shè)的數(shù)據(jù)分布）、分布參數(shù)（如平均值和方差）和預(yù)期的孤立點的數(shù)目。然而，在許多情況下，用戶并不知道數(shù)據(jù)集合參數(shù)的知識，況且現(xiàn)實數(shù)據(jù)也往往不符合任何一種理想狀態(tài)的數(shù)學(xué)分布。2. 基于距離的方法基于距離（Distancebased ，DB）的孤立點的概念是由 Knorr 和 Ng 在 1998 年提出的。他們認為如果一個點與數(shù)據(jù)集中大多數(shù)點之間的距離都大于某個閾值，那么這個點就是一個孤立點。也就是說，不依賴于統(tǒng)計檢驗，可以將基于距離的孤立點看作是那些沒有“足夠多”鄰居的對象，這里的鄰居是基于給定對象的距離來定義的?；诰嚯x的孤立點定義如下：如果數(shù)據(jù)集合 S 中對象至少有 p 部分與對象 O 的距離大于 d，則對象 O 是一個帶參數(shù) p 和 d 的基于距離（DB）的孤立點，即 DB（p，d）。與基于分布的方法相比，基于距離的孤立點檢測包含并擴展了基于分布的思想，當(dāng)數(shù)據(jù)集不滿足任何標準分布時，基于距離的方法仍能有效地發(fā)現(xiàn)孤立點。而且，這種方法能夠處理任意維的數(shù)據(jù)。但不足的是，