張建中，方正，熊擁軍，袁小一

(1. 中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙，410083；2. 中南大學(xué) 化學(xué)化工學(xué)院，湖南 長沙，410083)

對(duì)基于SNM數(shù)據(jù)清洗算法的優(yōu)化

張建中1，方正2，熊擁軍1，袁小一1

(1. 中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙，410083；2. 中南大學(xué) 化學(xué)化工學(xué)院，湖南 長沙，410083)

對(duì)基本鄰近排序算法SNM(basic sorted-neighborhood method)進(jìn)行分析，指出其不足；提出基于SNM算法的一種優(yōu)化算法，通過采集中南大學(xué)冶金礦物工程機(jī)構(gòu)知識(shí)庫的2 000多條文獻(xiàn)記錄作為樣本數(shù)據(jù)進(jìn)行實(shí)驗(yàn)研究，對(duì)記錄的“臟數(shù)據(jù)”按照DC標(biāo)準(zhǔn)和相關(guān)規(guī)范進(jìn)行清洗與排重。研究結(jié)果表明：與SNM算法相比，在同樣的運(yùn)算環(huán)境下，優(yōu)化算法在招回率、誤識(shí)別率和執(zhí)行時(shí)間上有明顯優(yōu)勢(shì)。

數(shù)據(jù)挖掘；數(shù)據(jù)清洗；重復(fù)記錄；SNM算法

在構(gòu)建機(jī)構(gòu)知識(shí)庫時(shí)，其中一項(xiàng)重要的工作是將收割的臨時(shí)元數(shù)據(jù)倉儲(chǔ)中的DC(Dublin core)元數(shù)據(jù)進(jìn)行規(guī)范化[1]，并將規(guī)范后的元數(shù)據(jù)寫入 DC元數(shù)據(jù)中心。由于這些元數(shù)據(jù)來自不同的加工單位，存在錄入錯(cuò)誤、語義表示不一致、拼寫錯(cuò)誤和記錄重復(fù)等情況，數(shù)據(jù)質(zhì)量差異大，尤其是重復(fù)記錄信息嚴(yán)重，影響查全率和查準(zhǔn)率，所以，在元數(shù)據(jù)導(dǎo)入數(shù)據(jù)中心前，需要對(duì)元數(shù)據(jù)進(jìn)行清洗。在處理大的數(shù)據(jù)集時(shí)，匹配重復(fù)記錄是一項(xiàng)非常耗時(shí)的過程。目前，用于相似重復(fù)記錄識(shí)別的算法為基本鄰近有序法(SNM)，整個(gè)匹配過程相當(dāng)于對(duì)2個(gè)記錄集做笛卡爾積，算法時(shí)間復(fù)雜度較大[2]。在此，本文作者分析SNM算法的缺陷，提出一種基于排序關(guān)鍵字預(yù)處理、不同關(guān)鍵字多趟鄰近排序、窗口移動(dòng)速度與大小可伸縮的相似重復(fù)記錄識(shí)別的算法，并通過實(shí)例說明優(yōu)化算法的正確性。

1 元數(shù)據(jù)清洗

數(shù)據(jù)清洗就是分析“臟數(shù)據(jù)”產(chǎn)生的原因和存在形式，利用現(xiàn)有技術(shù)手段和方法去清洗，并將它們轉(zhuǎn)化為滿足要求的數(shù)據(jù)，從而提高數(shù)據(jù)集的質(zhì)量[3]。數(shù)據(jù)清洗(Data cleaning)的目的是檢測(cè)數(shù)據(jù)中存在的錯(cuò)誤和不一致，剔除或者改正，這樣就提高了數(shù)據(jù)的質(zhì)量[4]。數(shù)據(jù)清洗模型如圖 1所示，數(shù)據(jù)由臨時(shí)數(shù)據(jù)庫裝載到中心元數(shù)據(jù)倉儲(chǔ)時(shí)，數(shù)據(jù)清洗過程主要由數(shù)據(jù)標(biāo)準(zhǔn)化、數(shù)據(jù)解析、數(shù)據(jù)增強(qiáng)和重復(fù)數(shù)據(jù)歸并4步組成，數(shù)據(jù)標(biāo)準(zhǔn)化完成數(shù)據(jù)格式的規(guī)范化和數(shù)據(jù)表達(dá)方式的同一化；數(shù)據(jù)解析主要完成數(shù)據(jù)字段的拆分和合并；數(shù)據(jù)增強(qiáng)主要對(duì)原始數(shù)據(jù)進(jìn)行補(bǔ)充，保證數(shù)據(jù)的完整性；重復(fù)數(shù)據(jù)歸并主要是對(duì)相似重復(fù)記錄的清除與合并。

圖1 數(shù)據(jù)清洗模型Fig.1 Data cleaning model

1.1 數(shù)據(jù)清洗工作流程

為實(shí)現(xiàn)數(shù)據(jù)清洗自動(dòng)執(zhí)行，關(guān)鍵是清洗規(guī)則定義，清洗流程如圖2所示。

圖2 數(shù)據(jù)清洗流程Fig.2 Data cleaning flow chart

在規(guī)則中定義了錯(cuò)誤類型及其相應(yīng)的處理策略。例如，在遇到空值時(shí)，是應(yīng)該丟棄這條記錄還是將某個(gè)特定的值填入，這都是由規(guī)則定義文件中的錯(cuò)誤類型(error type)及其策略(policy)、處理類(op_class)來決定。當(dāng)程序遇到與規(guī)則描述文件中預(yù)定義的錯(cuò)誤類型相匹配的錯(cuò)誤時(shí)，就按照預(yù)定義的錯(cuò)誤處理策略進(jìn)行處理，逐條記錄處理后，生成目標(biāo)結(jié)構(gòu)化數(shù)據(jù)，并將結(jié)果追加到中心元數(shù)據(jù)倉儲(chǔ)。這些過程都是由清洗引擎來調(diào)度執(zhí)行。清洗引擎是系統(tǒng)中最重要的部件，整個(gè)系統(tǒng)數(shù)據(jù)清洗質(zhì)量取決于數(shù)據(jù)清洗引擎的執(zhí)行情況。

1.2 清洗規(guī)則定義

清洗規(guī)則包含2部分：檢查數(shù)據(jù)完整性的規(guī)則和當(dāng)違反完整性時(shí)所采用的處理方法。清洗規(guī)則用一種描述方法來描述，同時(shí)將這些表述放到清洗規(guī)則文件中，以便調(diào)度執(zhí)行或者跟蹤和修改。本文作者采用對(duì)象的描述方法對(duì)清洗規(guī)則進(jìn)行描述。在清洗框架中，對(duì)于清洗規(guī)則采用批量執(zhí)行。清洗規(guī)則定義文件中規(guī)則的描述見文獻(xiàn)[5]：

1.3 數(shù)據(jù)標(biāo)準(zhǔn)化

由于不同的數(shù)據(jù)源對(duì)于同樣性質(zhì)的數(shù)據(jù)表現(xiàn)的形式不同，不利于信息的檢索，數(shù)據(jù)的標(biāo)準(zhǔn)化主要表現(xiàn)在數(shù)據(jù)格式的規(guī)范化和數(shù)據(jù)表達(dá)方式的統(tǒng)一化。

在數(shù)據(jù)倉儲(chǔ)中，有的元數(shù)據(jù)日期類型的數(shù)據(jù)字段表現(xiàn)形式復(fù)雜，例如，YYYY—MM—DD，MM/DD/YYYY以及其他的形式。本模塊的作用就在于將同一數(shù)據(jù)以同種形式表現(xiàn)出來，統(tǒng)一格式為符合ISO 8601[W3CDTF]規(guī)范，并使用YYYY-MM-DD的格式[6]。

對(duì)于“語種”字段，不同系統(tǒng)錄入規(guī)則也各不相同，如中文，CHN，CN和 Chinese等，可統(tǒng)一采用RFC 1766所定義的語種代碼規(guī)范，此標(biāo)準(zhǔn)定義了1個(gè)由2個(gè)英文字母組成的語言代碼。如中文用CN表示。

1.4 數(shù)據(jù)解析

數(shù)據(jù)存在不同的細(xì)節(jié)級(jí)別稱為粒度。粒度越高，表示綜合程度越高。在中心數(shù)據(jù)倉儲(chǔ)中的查詢涉及不同的細(xì)節(jié)，不同的數(shù)據(jù)源對(duì)信息的描述可能具有不同的粒度，這使得對(duì)來自不同數(shù)據(jù)源的數(shù)據(jù)很難進(jìn)行相應(yīng)的比較。本模塊對(duì)結(jié)構(gòu)松散的來自不同數(shù)據(jù)源的原始數(shù)據(jù)進(jìn)行分析，使之具有良好的粒度以適合信息的檢索需要，有些字段需要拆分，有的則需要合并。

如期刊元數(shù)據(jù)中的作者字段，有的數(shù)據(jù)源將所有作者都著錄在1個(gè)字段中，需要將其拆分為主要責(zé)任者(creator)和其他責(zé)任者字段(contributor)。

對(duì)于主題詞，需要將多個(gè)合并在同一字段中，并以統(tǒng)一的分隔符分隔。還有如文獻(xiàn)引用字段的合并等。

1.5 數(shù)據(jù)增強(qiáng)

在向中心元數(shù)據(jù)倉儲(chǔ)裝載數(shù)據(jù)的過程中，原始數(shù)據(jù)可能不完整。因此，有必要對(duì)原始數(shù)據(jù)進(jìn)行補(bǔ)充，這是數(shù)據(jù)增強(qiáng)的任務(wù)。數(shù)據(jù)增強(qiáng)通常包含以下 3種方式：

(2) 為空值字段設(shè)置合適的值。如期刊數(shù)據(jù)記錄中有的填寫了語種值，有的沒有填寫，對(duì)未填寫的需要補(bǔ)充。

(3) 以增加字段的方式添加額外的信息。多數(shù)據(jù)源時(shí)，并非所有的數(shù)據(jù)源都能保證含有所有所需要的字段。在這種情況下，必須為某些缺少的數(shù)據(jù)源添加字段以保持?jǐn)?shù)據(jù)信息的完整性。例如：期刊資源的資源類型、來源、入庫時(shí)間等字段。

2 重復(fù)記錄歸并

重復(fù)記錄是指它們?cè)谡Z義上是相同的，也就是說，它們指的是現(xiàn)實(shí)世界中同一實(shí)體，但它們之間可以有一些不同的其他屬性，既占用了空間，也給檢索結(jié)果造成記錄集的冗余。

為了從數(shù)據(jù)集中檢測(cè)并歸并重復(fù)記錄，首要的問題就是判斷2條記錄是否是重復(fù)的。最可靠的檢測(cè)重復(fù)記錄的辦法是比較數(shù)據(jù)庫中每對(duì)記錄。目前，所采用的算法是基本鄰近有序法(Basic sortedneighborhood method，SNM)，但該算法時(shí)間復(fù)雜度大，需要進(jìn)行N(N?1)/2次比較(其中：N是數(shù)據(jù)庫中記錄的總數(shù))。排序?合并方法是檢測(cè)數(shù)據(jù)庫中完全重復(fù)記錄的標(biāo)準(zhǔn)方法[6]。它的基本思想是：先對(duì)數(shù)據(jù)集排序，然后，比較相鄰記錄是否相似。這一方法也為在整個(gè)數(shù)據(jù)庫級(jí)上檢測(cè)重復(fù)記錄提供了思路。目前，已有的檢測(cè)重復(fù)記錄的方法也大多以此思想為基礎(chǔ)來優(yōu)化[7]。現(xiàn)存的重復(fù)記錄清除方案主要是基于標(biāo)準(zhǔn)的檢測(cè)完全相同的2條記錄的方法[8]。Hernandez等[9]提出在不同的鍵上多次排序，并分別計(jì)算鄰近記錄的相似度，最后，綜合多次計(jì)算的結(jié)果完成記錄匹配過程。李堅(jiān)等[10]提出可變移動(dòng)窗口，對(duì)不同屬性的重要性設(shè)置不同權(quán)值，根據(jù)總相似度決定相似重復(fù)記錄。邱越峰等[11]提出一種基于N-Gram的聚類算法，在檢測(cè)的同時(shí)能自動(dòng)校正單詞的插入、刪除錯(cuò)誤，提高檢測(cè)精度，Monge等[12?13]先將表中所有記錄排序，然后，使用包含一定數(shù)量群集cluster的優(yōu)先隊(duì)列按順序掃描所有的排序記錄并動(dòng)態(tài)地將它們聚類。Kukich等[14?15]根據(jù)用戶定義的鍵值來重排表記錄，并采用滑動(dòng)窗口以成對(duì)的方式(pair-wise)比較窗口內(nèi)的記錄。

2.1 基本鄰近排序算法

2.1.1 算法描述

步驟 1創(chuàng)建排序關(guān)鍵字。抽取記錄屬性的一個(gè)子集序列或?qū)傩灾档淖哟?，?jì)算數(shù)據(jù)集中每一條記錄的鍵值。

步驟 2排序。根據(jù)該排序關(guān)鍵字對(duì)整個(gè)數(shù)據(jù)集進(jìn)行排序。盡可能地使?jié)撛诘目赡艿闹貜?fù)記錄調(diào)整到一個(gè)鄰近的區(qū)域內(nèi)，從而對(duì)于特定的記錄可以將進(jìn)行記錄匹配的對(duì)象限制在一定的范圍之內(nèi)。

步驟 3合并。在排序后的數(shù)據(jù)集上滑動(dòng)一個(gè)固定大小的窗口，數(shù)據(jù)集中每條記錄僅與窗口內(nèi)的記錄進(jìn)行比較。窗口的大小為W條記錄，則每條新進(jìn)入窗口的記錄都要與先前進(jìn)入窗口的W?1條記錄進(jìn)行比較來檢測(cè)重復(fù)記錄，最先進(jìn)入窗口內(nèi)的記錄滑出窗口，最后一條記錄的下一條記錄移入窗口，再把此W條記錄作為下一輪比較對(duì)象。圖3所示為SNM排序數(shù)據(jù)集示意圖。

圖3 SNM排序數(shù)據(jù)集示意圖Fig.3 Schematic diagram of SNM method

SNM算法采用滑動(dòng)窗口的方法，每次可以只比較窗口中的W條記錄，提高了匹配效率；采用滑動(dòng)窗口也極大地提高了比較速度，只需要進(jìn)行W×N次比較，顯然，W比N小得多。但是，SNM方法存在以下缺陷[10]：(1) 對(duì)排序關(guān)鍵字的依賴性大；(2) 滑動(dòng)窗口的大小W的選取較難控制。

2.1.2 基本鄰近有序算法的優(yōu)化思想

針對(duì)SNM算法的缺點(diǎn)，對(duì)傳統(tǒng)SNM方法中的缺陷進(jìn)行如下改進(jìn)[16]：

(1) 排序關(guān)鍵字預(yù)處理。針對(duì)傳統(tǒng)的SNM方法對(duì)排序關(guān)鍵字中錯(cuò)誤的敏感性，在根據(jù)選取的排序關(guān)鍵字對(duì)數(shù)據(jù)集進(jìn)行排序之前，先對(duì)其進(jìn)行預(yù)處理，采用外部源文件更正排序關(guān)鍵字中的錯(cuò)誤，統(tǒng)一數(shù)據(jù)格式。

(2) 選擇不同的關(guān)鍵字執(zhí)行多趟鄰近排序。每趟鄰近排序，選擇不同的關(guān)鍵字。

(3) 窗口移動(dòng)速度和大小可伸縮。采用伸縮窗口的方法，使得在記錄的比較過程中，窗口移動(dòng)的大小和速度可以在一定的范圍內(nèi)根據(jù)相似規(guī)模進(jìn)行調(diào)整。

2.1.3 優(yōu)化算法

算法的參數(shù)有2個(gè)：窗口最小值W1，窗口最大值W2；算法中主要變量有 3個(gè)：窗口中相似記錄數(shù)Match_num，移動(dòng)速度v和當(dāng)前窗口大小Wi。

每次窗口的大小Wi為：

Wi窗口中，相似記錄條數(shù)Match_num可取值為0，1，2，…，Wi?1條。式(1)中，相似記錄越多，窗口越大。當(dāng)相似記錄為Wi?1條時(shí)，窗口最大為W2；當(dāng)沒有相似記錄時(shí)，窗口最小為W1。每次窗口移動(dòng)的速度vi為：

窗口移動(dòng)速度vi以線性的速度變化。當(dāng)窗口中相似記錄多時(shí)，移動(dòng)速度小，如全部相似時(shí)，移動(dòng)速度為 1；當(dāng)相似記錄越少時(shí)，移動(dòng)速度越大，如沒有相似記錄時(shí)，移動(dòng)速度為vi。

2.1.4 重復(fù)記錄清洗算法效率度量標(biāo)準(zhǔn)

衡量重復(fù)記錄檢測(cè)算法效率的標(biāo)準(zhǔn)是算法是否能把數(shù)據(jù)集中存在的所有重復(fù)記錄都檢測(cè)出來。常用的標(biāo)準(zhǔn)主要有：召回率(Recall)和誤識(shí)別率(False)[17]。

(1) 招回率(Recall)。定義為被重復(fù)記錄檢測(cè)算法正確識(shí)別出的重復(fù)記錄占數(shù)據(jù)集實(shí)際包含的重復(fù)記錄的百分比。

假設(shè)有7條記錄{X1,X2,X3,Y1,Y2,Y3,Z1}，其中{X1,X2,X3}和{Y1,Y2,Y3}分別是記錄X和Y的重復(fù)記錄。通過一個(gè)數(shù)據(jù)清洗的過程識(shí)別出{X1,X2,Z1}和{Y1,Y2}是重復(fù)記錄，則其Recall=(4/6)×100%=66.67%。

(2) 誤識(shí)別率(False)。定義為被重復(fù)記錄檢測(cè)算法錯(cuò)誤地識(shí)別為重復(fù)記錄的數(shù)目占被算法識(shí)別為重復(fù)記錄總數(shù)的百分比。誤識(shí)別率越低，表明算法結(jié)果的置信度就越高。

在上面的例子中，檢測(cè)算法錯(cuò)誤地把Z1識(shí)別為1條重復(fù)記錄，則有False=(1/5)×100%=20%。

3 實(shí)驗(yàn)方法與結(jié)果

實(shí)驗(yàn)中所采用的數(shù)據(jù)集是礦物工程機(jī)構(gòu)庫中的50種期刊的2 000多條文獻(xiàn)記錄，每條記錄有23個(gè)屬性，屬性如表1所示，清洗前、清洗后數(shù)據(jù)質(zhì)量的記錄例子如表2所示。

SNM法和SNM優(yōu)化算法均采用同一計(jì)算環(huán)境。各種情況下檢測(cè)重復(fù)記錄算法效率的結(jié)果如表 3所示。從表3可以看出：在排序之前對(duì)排序關(guān)鍵字進(jìn)行預(yù)處理，以及利用大小與速度變化窗口的 SNM 優(yōu)化算法在效率上要優(yōu)于傳統(tǒng)的 SNM 算法；由于采用了窗口的大小和移動(dòng)速度可變的技術(shù)，執(zhí)行時(shí)間明顯比傳統(tǒng)SNM算法少；進(jìn)行關(guān)鍵字預(yù)處理后，招回率明顯提高，誤識(shí)別率得到降低。

表1 期刊元數(shù)據(jù)信息Table 1 Metadata information of journal

表2 數(shù)據(jù)清洗中的部分“臟數(shù)據(jù)”實(shí)例Table 2 Partly dirty data examples of journal at data cleaning

表3 SNM與優(yōu)化SNM算法效率的比較Table 3 Comparison of efficiency of SNM and improved SNM algorithm

4 結(jié)果分析與討論

(1) 數(shù)據(jù)標(biāo)準(zhǔn)化問題：例如有的發(fā)表時(shí)間表現(xiàn)為2007.12.10，有的時(shí)間表現(xiàn)為2007?1?11和 20071015等，故需要統(tǒng)一日期表現(xiàn)格式，必須執(zhí)行數(shù)據(jù)的標(biāo)準(zhǔn)化動(dòng)作。在這里，使用YYYY-MM-DD作為清洗后的日期格式；對(duì)語種字段，表現(xiàn)形式有CN、中文和CHN，必須執(zhí)行標(biāo)準(zhǔn)化操作，統(tǒng)一格式為CN。還有如ISSN號(hào)分隔符的不一致、2個(gè)漢字的作者字段中有空格、期的字符串位數(shù)不同等，這些都需要進(jìn)行標(biāo)準(zhǔn)化操作。

(2) 數(shù)據(jù)解析問題：對(duì)具有多作者的期刊論文來說，需要將第1作者與其他責(zé)任者分解，放在不同的字段中，于是，這就需要數(shù)據(jù)解析過程。

(3) 數(shù)據(jù)增強(qiáng)問題：數(shù)據(jù)中同樣存在一些空缺的字段，例如語種、資源類型、來源和入庫時(shí)間等，可以使用數(shù)據(jù)增強(qiáng)這個(gè)階段來處理這些問題。

(4) 記錄歸并問題：在這些記錄中，對(duì)于“銅藍(lán)的細(xì)菌氧化浸出”這篇論文存在2條記錄，表現(xiàn)為同一數(shù)字對(duì)象，故需要執(zhí)行重復(fù)記錄歸并的步驟來消除重復(fù)。

通過調(diào)用清洗引擎對(duì)多個(gè)清洗過程按照工作流程來清洗。與清洗前數(shù)據(jù)比較，清洗后的數(shù)據(jù)消除了大部分的錯(cuò)誤數(shù)據(jù)，從而保證了數(shù)據(jù)庫質(zhì)量。

5 結(jié)論

(1) 給出了數(shù)據(jù)清洗的 4個(gè)過程和清洗流程：數(shù)據(jù)標(biāo)準(zhǔn)化、數(shù)據(jù)解析、數(shù)據(jù)增強(qiáng)和重復(fù)數(shù)據(jù)歸并，并且提出了清洗規(guī)則的定義。對(duì)數(shù)據(jù)標(biāo)準(zhǔn)化存在的問題進(jìn)行分析，采取數(shù)據(jù)標(biāo)準(zhǔn)化、數(shù)據(jù)解析和數(shù)據(jù)增強(qiáng)技術(shù)提高了數(shù)據(jù)質(zhì)量。

(2) 闡述了SNM算法，指出存在的缺陷：一是窗口的大小選取對(duì)結(jié)果影響很大；二是對(duì)排序關(guān)鍵字的依賴性大，影響了匹配的效率與精度。

(3) 采取排序關(guān)鍵字預(yù)處理、選擇不同的關(guān)鍵字執(zhí)行多趟鄰近排序以及窗口移動(dòng)速度和大小可伸縮等方法，提出了SNM優(yōu)化算法。

(4) 證明了優(yōu)化的SNM算法優(yōu)于傳統(tǒng)的SNM算法，有效地提高了數(shù)據(jù)質(zhì)量。目前，該方法已在實(shí)際中得到應(yīng)用。

[1] 中國高等教育文獻(xiàn)保障系統(tǒng)管理中心. 中國高等教育數(shù)字圖書館技術(shù)標(biāo)準(zhǔn)與規(guī)范[M]. 北京: 中國高等教育文獻(xiàn)保障系統(tǒng),2004: 312?315.

Administrative Center for China Academic Library and Information System. China academic digital library and information system technical standards and specifications[M].Beijing: China Academic Library and Information System, 2004:312?315.

[2] 郭芝懋, 周傲英. 數(shù)據(jù)質(zhì)量和數(shù)據(jù)清洗研究綜述[J]. 軟件學(xué)報(bào), 2002, 13(11): 2076?2082.

GUO Zhi-mao, ZHOU Ao-ying. Research on data quality and data cleaning: A survey[J]. Journal of Software, 2002, 13(11):2076?2082.

[3] 劉波, 楊路明, 雷剛躍, 等. 面向 XML 數(shù)據(jù)庫的智能數(shù)據(jù)清洗策略[J]. 計(jì)算機(jī)工程, 2008, 34(16): 16?17.

LIU Bo, YANG Lu-ming, LEI Gang-yue, et al. Intelligence data cleaning strategy for XML database[J]. Computer Engineering,2008, 34(16): 16?17.

[4] Rahm E, Do H H. Data cleaning: Problems and current approaches[J]. IEEE Data Engineering Bulletin, 2000, 23(4):3?13.

[5] Raman V, Hellerstein J M. Potter’s Wheel: An interactive data cleaning system[C]//Proceedings of the 27th VLDB Conference.San Francisco: Morgan Kaufmann Publishers Inc, 2001:100?109.

[6] Bitton D, DeWitt D J. Duplicate record elimination in large data files[J]. ACM Transactions on Database Systems, 1983, 8(2):255?265.

[7] Hernandez M A, Stolfo S J. Real-world data is dirty: data cleansing and the merge/purge problem[J]. Journal of Data Mining and Knowledge Discovery, 1998, 2(1): 9?37.

[8] QIU Yue-feng, TIAN Zong-ping, JI Wen-yun, et al. An efficient approach for detecting approximately duplicate database records[J]. Chinese Journal of Computers, 2001, 24(1): 69?77.

[9] Hernandez M A, Stolfo S J. Real-World data is dirty: Data cleansing and the merge/purge problem[J]. Data Mining and Knowledge Discovery, 1998, 2(1): 9?37.

[10] 李堅(jiān), 鄭寧. 對(duì)基于MPN數(shù)據(jù)清洗算法的改進(jìn)[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2008, 25(2): 245?246.

LI Jian, ZHENG Ning. Improvement on the algorithm of data cleaning based on MPN[J]. Computer Applications and Software,2008, 25(2): 245?246.

[11] 邱越峰, 田增平, 季文赟, 等. 一種高效的檢測(cè)相似重復(fù)記錄的方法[J]. 計(jì)算機(jī)學(xué)報(bào), 2001, 24(1): 69?77.

QIU Yue-feng, TIAN Zeng-ping, JI Wen-yun, et al. An efficient approach for detecting approximately duplicate database records[J]. Chinese Journal of Computers, 2001, 24(1): 69?77.

[12] Monge A E. Matching algorithm within a duplicate detection system[J]. IEEE Data Engineering Bulletin, 2000, 23(4): 14?20.

[13] Monge A E, Elkan C P. An efficient domain-independent algorithm for detecting approximately duplicate database records[C]//Proceeding of the ACM-SIGMOD Workshop on Data Mining and Knowledge Discovery. Tucson: ACM, 1997:23?29.

[14] Kukich K. Techniques for automatically correcting words in text[J]. ACM Computing Surveys, 1992, 24(4): 377?439

[15] Hernandez M, Stolfo S. The Merge/Purge problem for large databases[C]//Proceeding of ACM SIGMOD International Conference on Management of Data. Boston: ACM, 1995:127?138.

[16] 張建中. 數(shù)字資源整合與個(gè)性化服務(wù)中關(guān)鍵技術(shù)研究[D]. 長沙: 中南大學(xué)信息科學(xué)與工程學(xué)院, 2008: 43?45.

ZHANG Jian-zhong. A study of the key technology for digital library resource integration and personalized services[D].Changsha: Central South University. School of Information Science and Engineering, 2008: 43?45.

[17] Lee M L, Ling T W, Low W L. IntelliClean: A knowledge-based intelligent data cleaner[C]//Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Ming. Boston: ACM Press, 2000: 290?294.

(編輯 劉華森)

Optimization algorithm for cleaning data based on SNM

ZHANG Jian-zhong1, FANG Zheng2, XIONG Yong-jun1, YUAN Xiao-yi1

(1. School of Information Science and Engineering, Central South University, Changsha 410083, China;2. School of Chemistry and Chemical Engineering, Central South University, Changsha 410083, China)

The basic sorted-neighborhood method (SNM) was introduced and the analysis was made on its deficiency. An improved algorithm of data cleaning based on SNM was put forward. And the experiments were made on more than 2 000 sample records data from the mineral metallurgy institutional database of Central South University. Key task was cleaning dirty data and removing approximately duplicate records according to dublin core (DC) standard and other criterion. The results show that the improved algorithm is better than SNM in the aspects of recall, precision and run time in the same computer condition.

data mining; data cleaning; approximately duplicate records; SNM algorithm

TP393

A

1672?7207(2010)06?2240?06

2009?11?15；

2010?03?02

國家自然科學(xué)基金資助項(xiàng)目(50874119)

張建中(1955?)，男，河北張家口人，博士，教授，從事數(shù)據(jù)挖掘、信息管理研究；電話：0731-88836750；E-mail: jzzhang@mail.csu.edu.cn

(1) 對(duì)數(shù)據(jù)中不完整的字段補(bǔ)充必要的信息，使之完整。例如：期刊資源中

符URL，有的只定義了參數(shù)值，并未給出完整的URL地址，需要補(bǔ)充完整，才可定位到資源對(duì)象。