肖 蕾 郭樂(lè)江 胡亞慧 程 敏

(空軍雷達(dá)學(xué)院 武漢 430019)

基于遺傳神經(jīng)網(wǎng)絡(luò)的相似重復(fù)記錄檢測(cè)方法研究*

肖 蕾 郭樂(lè)江 胡亞慧 程 敏

(空軍雷達(dá)學(xué)院 武漢 430019)

設(shè)計(jì)實(shí)現(xiàn)了一個(gè)相似重復(fù)記錄檢測(cè)系統(tǒng),該系統(tǒng)包括預(yù)處理模塊、聚類(lèi)模塊、字段匹配模塊和記錄匹配模塊,支持聚類(lèi)算法和字段匹配算法的定制擴(kuò)充。并通過(guò)實(shí)驗(yàn)對(duì)比了幾種著名的算法,實(shí)驗(yàn)結(jié)果表明該系統(tǒng)提高了相似重復(fù)記錄檢測(cè)的精確度。

遺傳神經(jīng)網(wǎng)絡(luò);相似重復(fù)記錄檢測(cè)系統(tǒng);聚類(lèi)算法;字段匹配算法

Class NumberTN958

1 引言

相似重復(fù)記錄清洗技術(shù)的核心是重復(fù)記錄檢測(cè),即如何判定兩條記錄是不是重復(fù)記錄。在判定記錄是否是重復(fù)的過(guò)程中,絕大多數(shù)的重復(fù)記錄檢測(cè)算法都采用了“等值理論”,引入了相似度的概念,用記錄相似度對(duì)記錄之間的等值程度進(jìn)行量化,根據(jù)相似度的大小判定記錄是否等值。所以重復(fù)記錄檢測(cè)的核心是準(zhǔn)確的計(jì)算兩條記錄的相似度。在數(shù)據(jù)倉(cāng)庫(kù)或數(shù)據(jù)庫(kù)中,記錄都是由多個(gè)字段值組成,因此,計(jì)算記錄的相似度的基礎(chǔ)是記錄各個(gè)字段的相似度。我們發(fā)現(xiàn)不同的字段相似度計(jì)算方法往往對(duì)特定的類(lèi)型的字符特別有效,并不能對(duì)所有類(lèi)型的字段值都有很好的效果,例如:Jaro-Winkler算法對(duì)拼寫(xiě)錯(cuò)誤類(lèi)型的字段有很好的檢測(cè)效果。

基于以上分析,提出了一種基于遺傳神經(jīng)網(wǎng)絡(luò)的相似重復(fù)記錄檢測(cè)系統(tǒng)。首先,該系統(tǒng)由用戶(hù)選擇字段匹配算法計(jì)算記錄對(duì)應(yīng)的字段值的相似值;其次,在字段相似度基礎(chǔ)上使用遺傳神經(jīng)網(wǎng)絡(luò)模型計(jì)算記錄對(duì)的相似度;最后,根據(jù)記錄的相似度值進(jìn)行判定。

2 EADDS的整體結(jié)構(gòu)和特點(diǎn)

2.1 EADDS的整體結(jié)構(gòu)[1～2]

相似重復(fù)記錄檢測(cè)系統(tǒng)EADDS的工作流程圖如圖1所示。

圖1 EADDS的工作流程圖

圖1描述了EADDS的工作流程圖,原始數(shù)據(jù)經(jīng)過(guò)數(shù)據(jù)準(zhǔn)備、初步聚類(lèi)、重復(fù)記錄檢測(cè)、重復(fù)記錄判定處理后,最后檢測(cè)出原始數(shù)據(jù)集中所有的重復(fù)記錄。下面分別介紹4個(gè)模塊。

1)數(shù)據(jù)準(zhǔn)備模塊

為了保證清洗的效率和精度,在進(jìn)行重復(fù)記錄清洗之前要對(duì)原始的數(shù)據(jù)進(jìn)行預(yù)處理。EADDS的數(shù)據(jù)準(zhǔn)備模塊,通過(guò)對(duì)原始數(shù)據(jù)進(jìn)行解析、轉(zhuǎn)換、標(biāo)準(zhǔn)化,解決了原始數(shù)據(jù)中的各種問(wèn)題,如異構(gòu)數(shù)據(jù)源中屬性定義不同、字段空缺值處理、數(shù)據(jù)格式等。數(shù)據(jù)準(zhǔn)備模塊的功能就是使數(shù)據(jù)以統(tǒng)一的格式存入到數(shù)據(jù)庫(kù)中。

2)聚類(lèi)模塊

通常,在重復(fù)記錄檢測(cè)時(shí)要對(duì)數(shù)據(jù)集進(jìn)行初步聚類(lèi),目的是降低檢測(cè)的時(shí)間復(fù)雜度。在EADDS中,我們集成了當(dāng)前的各種聚類(lèi)算法,包括鄰近排序法(SNM)[3～4],多趟排序法(MPN)[3～4],優(yōu)先權(quán)隊(duì)列算法[5]等。在進(jìn)行重復(fù)記錄的檢測(cè)時(shí),EADDS允許用戶(hù)對(duì)所有的聚類(lèi)算法進(jìn)行選擇,利用所選擇的聚類(lèi)算法對(duì)數(shù)據(jù)集進(jìn)行初步聚類(lèi)。EADDS也允許用戶(hù)對(duì)聚類(lèi)模塊進(jìn)行擴(kuò)展,即將新的聚類(lèi)算法引入系統(tǒng)中,以供用戶(hù)進(jìn)行選用。

3)字段相似度計(jì)算模塊

該模塊主要是計(jì)算兩條記錄對(duì)應(yīng)的字段的相似度值。針對(duì)不同的字段一般只對(duì)特定類(lèi)型的字段有效的特性,EADDS集成了多種有效的字段相似度計(jì)算方法,對(duì)于不同的字段允許用戶(hù)選擇相應(yīng)的字段相似度計(jì)算方法,計(jì)算相應(yīng)的相似度值。EADDS也允許用戶(hù)對(duì)該模塊進(jìn)行擴(kuò)展,即將新的字段相似度計(jì)算方法引入系統(tǒng)中,以供用戶(hù)進(jìn)行選用。

4)基于遺傳神經(jīng)網(wǎng)絡(luò)的相似重復(fù)記錄檢測(cè)模塊

該模塊主要是在字段相似度值的基礎(chǔ)上計(jì)算兩個(gè)記錄對(duì)的相似度的值。該模塊以字段相似度矢量作為輸入,輸出為兩個(gè)記錄對(duì)的相似度值?；谶z傳神經(jīng)網(wǎng)絡(luò)的相似重復(fù)記錄檢測(cè)的模型如下:系統(tǒng)分為訓(xùn)練階段和檢測(cè)階段,如圖2所示。

圖2 基于遺傳神經(jīng)網(wǎng)絡(luò)的檢測(cè)模型

在訓(xùn)練階段,首先,從數(shù)據(jù)集中抽取若干個(gè)記錄對(duì)作為訓(xùn)練樣例,在抽取的記錄對(duì)中盡可能的包含各種字符串類(lèi)型的記錄對(duì);其次,計(jì)算出兩個(gè)記錄對(duì)應(yīng)字段的相似度,并手工標(biāo)注記錄對(duì)的相似值;最后,將包含記錄相似度的特征矢量作為輸入,訓(xùn)練神經(jīng)網(wǎng)絡(luò)。

在檢測(cè)階段,計(jì)算出記錄對(duì)對(duì)應(yīng)字段的相似度,得到記錄對(duì)的相似度矢量,再利用訓(xùn)練好的遺傳神經(jīng)網(wǎng)絡(luò)計(jì)算記錄的相似度;最后,選擇合適的閾值δ,確定是否是重復(fù)記錄。

2.2 EADDS的特點(diǎn)

1)可擴(kuò)展性

EADDS允許對(duì)數(shù)據(jù)數(shù)據(jù)準(zhǔn)備模塊、聚類(lèi)模塊、字段相似度計(jì)算模塊進(jìn)行擴(kuò)展,使各種新技術(shù)可以應(yīng)用到系統(tǒng)框架中,從而可以提高各個(gè)模塊的性能,最終提高重復(fù)記錄檢測(cè)的整體性能。

2)可交互性

EADDS通過(guò)各個(gè)模塊與用戶(hù)進(jìn)行交互。在運(yùn)行過(guò)程中,要求用戶(hù)對(duì)聚類(lèi)算法、字段相似度計(jì)算方法、閾值的選取進(jìn)行選擇,并通過(guò)日志存儲(chǔ)處理過(guò)的歷史記錄,用戶(hù)可根據(jù)日志對(duì)各個(gè)模塊中運(yùn)行的算法以及閾值進(jìn)行調(diào)整。

3)組件模塊的可重用性

EADDS的各個(gè)模塊各自完成特定任務(wù),相互獨(dú)立,因此相互之間耦合度較低,可以實(shí)現(xiàn)重用?；谠撓到y(tǒng)框架可以開(kāi)發(fā)出不同領(lǐng)域的重復(fù)記錄檢測(cè)系統(tǒng)。

3 評(píng)價(jià)標(biāo)準(zhǔn)

在重復(fù)記錄清洗領(lǐng)域,研究人員一般采用召回率(Recall)和精確率(Precision)作為相似重復(fù)記錄檢測(cè)的評(píng)價(jià)標(biāo)準(zhǔn)。

召回率,也稱(chēng)為命中率,定義為正確檢測(cè)出的重復(fù)記錄數(shù)(True Positives)與所有的重復(fù)記錄(Real Duplicates)的比值,如式(1)所示:

準(zhǔn)確率是指正確檢測(cè)出的重復(fù)記錄數(shù)(True Positives)占所有檢測(cè)出的重復(fù)記錄(Detected Duplicates)中所占百分比,如式(2)所示:

性能好的檢測(cè)方法應(yīng)具有較高的召回率和準(zhǔn)確率。由定義分析可知,召回率和準(zhǔn)確率與閾值δ有關(guān),當(dāng)δ值增加時(shí),在檢測(cè)出的重復(fù)記錄中應(yīng)該含有更多的檢測(cè)正確的重復(fù)記錄,即準(zhǔn)確率提高了,但是由于檢測(cè)正確的重復(fù)記錄數(shù)少了,所以召回率降低了;反之,當(dāng)δ值減小時(shí),準(zhǔn)確率降低,召回率提高。

為了更加直觀(guān)的對(duì)清洗算法進(jìn)行評(píng)價(jià),在召回率和準(zhǔn)確率的基礎(chǔ)上又定義了一個(gè)新的評(píng)價(jià)標(biāo)準(zhǔn)—最大F1值。F1的定義如式(3)所示:

其中,R表示召回率,P表示準(zhǔn)確率。

F1值是召回率和準(zhǔn)確率的函數(shù),平均值反應(yīng)了檢測(cè)方法的性能。F1值越大,檢測(cè)算法性能越好。

4 仿真對(duì)比實(shí)驗(yàn)

為了驗(yàn)證本文提出方法的性能,將實(shí)驗(yàn)結(jié)果與TF-IDF與Marlin兩種著名的相似重復(fù)記錄檢測(cè)方法進(jìn)行了比較。TF-IDF方法首先將記錄所有的字段值連接為一個(gè)字符串,然后利用TF-IDF方法計(jì)算字符串的相似度,進(jìn)而進(jìn)行重復(fù)記錄的判定;Marlin是一種基于編輯距離的方法,提出了一種可學(xué)習(xí)的帶放射間隔的字符串編輯距離,具有良好的整體性能。

采用的實(shí)驗(yàn)數(shù)據(jù)是由Febrl[5]系統(tǒng)中的數(shù)據(jù)生成程序生成的數(shù)據(jù)。測(cè)試數(shù)據(jù)生成器生成的數(shù)據(jù)包括姓名(surname,given name),地址(address,suburb,street number),出生日期(date or birth),電話(huà)號(hào)碼(phone number),郵政編碼(postcode),社會(huì)保險(xiǎn)號(hào)(social security number)和年齡(age)等字段,其中原始數(shù)據(jù)信息來(lái)源于美國(guó)的電話(huà)手冊(cè)中。實(shí)驗(yàn)數(shù)據(jù)集中共有7200條記錄,其中包含650條相互重復(fù)的記錄。

EADDS中,選擇優(yōu)先隊(duì)列作為初步聚類(lèi)算法,字段匹配算法的選則為,字段 given_name、surname采用 Jaro,字段 street_number采用Levenshtein,字段 address_1、suburb采用 TF-IDF,字段date_of_birth、soc_sec_id采用Smith-Waterman。EADDS的實(shí)際測(cè)試輸出如圖3所示。

圖3 EADDS測(cè)試輸出

從測(cè)試輸出圖上可以看出,大部分輸出比較接近0.2和0.8。若我們把閾值定為0.5,即相似度小于0.5的為非重復(fù)記錄,相似度大于0.5的為重復(fù)記錄。在7200條測(cè)試記錄中,EADDS檢測(cè)出有672條重復(fù)記錄,在檢測(cè)出的重復(fù)記錄中,有631條記錄為真正的重復(fù),錯(cuò)誤檢測(cè)為重復(fù)記錄的記錄為41條,所以,精確率為0.93,召回率為0.97。

在實(shí)驗(yàn)數(shù)據(jù)集上分別對(duì) TF-IDF和Marlin進(jìn)行實(shí)驗(yàn)。首先確定精確率的值,然后再確定三種方法相應(yīng)的召回率,如圖4所示。

從實(shí)驗(yàn)結(jié)果圖上可以看出,對(duì)于不同的準(zhǔn)確率值,EADDS的召回率值要比其他兩種方法高,這說(shuō)明在進(jìn)行相似重復(fù)記錄檢測(cè)時(shí),在用戶(hù)指定的精確度的情況下,EADDS比其他的方法能夠更多的檢測(cè)出數(shù)據(jù)集中的相似重復(fù)記錄。同樣,對(duì)于不同的召回率值,EADDS的準(zhǔn)確率值也比其他兩種方法高,這也說(shuō)明檢測(cè)時(shí),在用戶(hù)指定的召回率的情況下,EADDS比其他的方法能夠更加精確的檢測(cè)出重復(fù)記錄。

圖4 測(cè)試結(jié)果圖

表1 相似重復(fù)記錄檢測(cè)的最大 F1值

表1顯示了在數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)所得到最大的F1值的平均值。因?yàn)镕1的值表示了一種檢測(cè)算法的整體性能,因此從表中可以看出,EADDS比TF-IDF和Marlin具有更高的整體性能,具有良好的檢測(cè)效果。

5 結(jié)語(yǔ)

設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)基于遺傳神經(jīng)網(wǎng)絡(luò)的相似重復(fù)記錄檢測(cè)系統(tǒng)EADDS。該系統(tǒng)是一個(gè)可擴(kuò)展的檢測(cè)系統(tǒng),支持聚類(lèi)算法和字段匹配算法的定制擴(kuò)充,具有較好的通用性。實(shí)驗(yàn)對(duì)比了EADDS與現(xiàn)有相似重復(fù)記錄檢測(cè)方法的性能,證明了EADDS的有效性。

[1]Hernandez M,Stolfo S.The merge/purge problem for large databases[J].ACM SIGMOD Record,1995,24(2):127～138

[2]Monge A,Elkan C.An efficient domain-independent algorithm for detecting approximately duplicate database records[C]//Proceedings of the ACM-SIGMOD Workshop on Research Issues on Knowledge Discorvery and Data Mining,Tucson,AZ,1997

[3]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

[4]周芝芬.基于數(shù)據(jù)倉(cāng)庫(kù)的數(shù)據(jù)清洗方法研究[D].上海:東華大學(xué)碩士學(xué)位論文,2004

[5]A.Monge,C.Elkan.An effieient domain independent algorithm for detecting approximately duplicate database reeords[J]//proeeedings of the SIGMOD workshop on Data Mining and Knowledge Diseovery,Tueson,Arizona,1997:211～217

Study on Approximately Duplicate Record Detection Method Based on Genetic Neural Network

Xiao Lei Guo Lejiang Hu Yahui Cheng Min
(Air Force Radar Academy,Wuhan 430019)

An extensible duplicates detecting system is designed and implemented.This system includes data preparation module,clustering module,field matching module and record matching module.The working principle and implementation mechanism in process of the four modules are given respectively in this dissertation.In our experiments,we compare the performance of our method with some famous approximately duplicate records detecting algorithms.The experiment results show that the system improved the precision.

genetic neural network,approximately duplicates detecting system,clustering algorithm,field matching algorithm

TN958

2010年8月10日,

2010年9月17日

肖蕾,女,助理實(shí)驗(yàn)師,研究方向:計(jì)算機(jī)網(wǎng)絡(luò)。郭樂(lè)江,男,博士,講師,研究方向:計(jì)算機(jī)網(wǎng)絡(luò)。胡亞慧,女,碩士,講師,研究方向:計(jì)算機(jī)結(jié)構(gòu)。程敏,女,助教,研究方向:計(jì)算機(jī)網(wǎng)絡(luò)。