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