郭 文 龍

(福建江夏學(xué)院 電子信息科學(xué)學(xué)院，福建 福州 350108)

商業(yè)銀行利用銀行卡為客戶辦理存貸款手續(xù)，航空公司、大型超市、連鎖酒店等企業(yè)為了營(yíng)銷需要，經(jīng)常發(fā)放各類會(huì)員卡，這些卡片信息隨同客戶資料均保存在企業(yè)的客戶關(guān)系數(shù)據(jù)庫(kù)中統(tǒng)一管理．現(xiàn)實(shí)生活中，一個(gè)人在同一個(gè)商業(yè)銀行辦理多張銀行卡、在同一個(gè)企業(yè)辦理多張會(huì)員卡的情況比比皆是，每張銀行卡或會(huì)員卡都對(duì)應(yīng)客戶關(guān)系表中的一條記錄，這就造成同一客戶的記錄在同一個(gè)數(shù)據(jù)庫(kù)或數(shù)據(jù)表中出現(xiàn)多條．在所有的客戶卡片中，有些卡片可能從辦理之后就從未使用過，這些卡片成了名符其實(shí)的“廢卡”，這就使得各類客戶管理系統(tǒng)中存在大量的無用數(shù)據(jù)，這些無用數(shù)據(jù)造成系統(tǒng)服務(wù)器存儲(chǔ)空間極大浪費(fèi)，此外隨著數(shù)據(jù)記錄數(shù)的增多還導(dǎo)致查詢速度變慢等問題出現(xiàn)．如何定期刪除無用的客戶記錄，如何合并同一客戶在數(shù)據(jù)庫(kù)中的多條記錄，進(jìn)而提高空間利用率并提高查詢速度就成了一個(gè)好的系統(tǒng)應(yīng)解決的問題．

1 概述

一個(gè)客戶關(guān)系數(shù)據(jù)庫(kù)中擁有多條這樣的記錄，它們的多數(shù)屬性相等、少部分屬性相似或足夠相似、個(gè)別屬性不同，則稱這樣的多條記錄為相似重復(fù)記錄．在銀行客戶管理系統(tǒng)和各類企業(yè)的會(huì)員管理系統(tǒng)中，存在許多相似重復(fù)記錄．這些記錄的共性是姓名、性別、身份證號(hào)等屬性一樣，卡號(hào)屬性不一樣，地址屬性相似或相等．如果能把這些相似重復(fù)記錄合并，即在關(guān)系表中通過增加列，如增加卡號(hào)列，將原來卡號(hào)只有一列依實(shí)際情況修改為“卡號(hào)1、卡號(hào)2…卡號(hào)N”的N列結(jié)構(gòu)，就可以大大降低記錄數(shù)，從而提高存儲(chǔ)空間利用率，還可以加快查詢速度，取得多贏的效果．相似重復(fù)記錄示例如表1所示，經(jīng)合并后如表2所示．

表1 相似重復(fù)記錄示例

表2 記錄合并后情況表

由表2可知，張三在原數(shù)據(jù)表中存在三條記錄，合并后只含一條記錄，顯然提高了空間利用率，且隨著數(shù)據(jù)記錄數(shù)的減少，數(shù)據(jù)的查詢、插入和刪除等操作速度也將大大提高．?dāng)?shù)據(jù)合并前必須將疑似相似重復(fù)記錄聚集到相鄰位置，聚集采用排序的方法實(shí)現(xiàn)；聚集之后還得判定相鄰記錄是否為相似重復(fù)記錄，如果是再進(jìn)行合并．

綜上，客戶關(guān)系數(shù)據(jù)庫(kù)相似重復(fù)記錄清洗流程如圖1所示．

2 常用相似重復(fù)記錄檢測(cè)算法

相似重復(fù)記錄檢測(cè)的最簡(jiǎn)單方法是用一條記錄和數(shù)據(jù)庫(kù)中其它記錄逐一對(duì)比，這種方法實(shí)現(xiàn)簡(jiǎn)單，精確度最高，然而時(shí)間耗費(fèi)是極其可怕的，其時(shí)間復(fù)雜度達(dá)到O(n2)，所以在實(shí)際應(yīng)用中是不可取的．

相似重復(fù)記錄清洗方法最常用的是基于排序-合并的方法，即先利用數(shù)據(jù)表的某個(gè)屬性或若干個(gè)屬性進(jìn)行排序，再對(duì)排好序后的記錄在鄰近的寬度內(nèi)比對(duì)，然后對(duì)檢測(cè)到的相似重復(fù)記錄進(jìn)行清洗與合并．常見的基于排序-合并方法的相似重復(fù)記錄檢測(cè)算法有 SNM 算法(Sorted-Neighborhood Method)[1-2]、MPN算法(Multi-Pass Sorted Neighborhood，MPN)[1-2]．SNM 算法的基本思想是設(shè)定若干條記錄寬度的窗口，在窗口內(nèi)進(jìn)行記錄的相似重復(fù)判定．該算法實(shí)現(xiàn)簡(jiǎn)單，算法的時(shí)間復(fù)雜度為O(nlogn)，排序是時(shí)間開銷最大的一環(huán)．MPN算法對(duì)SNM算法進(jìn)行了改進(jìn)，該算法使用不同的關(guān)鍵字進(jìn)行排序，每次排序后單獨(dú)在一個(gè)較小的窗口內(nèi)使用SNM算法判重．

圖1 相似重復(fù)記錄清洗流程

3 客戶關(guān)系數(shù)據(jù)庫(kù)相似重復(fù)記錄清洗算法

經(jīng)研究大量的企業(yè)客戶關(guān)系數(shù)據(jù)庫(kù)，發(fā)現(xiàn)客戶關(guān)系數(shù)據(jù)表的屬性個(gè)數(shù)均不多，一般為10個(gè)左右，且客戶信息基本包含了姓名、性別、身份證號(hào)、住址等屬性．對(duì)于住址等屬性由于描述方式不一或采用簡(jiǎn)寫等方面的原因，造成同一個(gè)人在同一張表中出現(xiàn)了多條住址不一樣的記錄．然而如果兩條或多條記錄相似重復(fù)，其姓名、性別和身份證號(hào)等屬性必定相同，所以對(duì)于客戶關(guān)系數(shù)據(jù)表判重前的排序使用“姓名+性別+身份證號(hào)”的多關(guān)鍵字排序方式．經(jīng)排序，相似和重復(fù)記錄已位于鄰近的區(qū)間內(nèi)．在排序的基礎(chǔ)上，對(duì)相鄰數(shù)據(jù)記錄進(jìn)行比對(duì)，如構(gòu)成相似重復(fù)記錄，則進(jìn)行合并，合并后刪除原來的兩條記錄，將新合并的記錄插入數(shù)據(jù)表，然后用新合并的記錄和之后的記錄再進(jìn)行比對(duì)，以此類推．

記錄的排序、合并和刪除實(shí)現(xiàn)起來均非常簡(jiǎn)單，所以清洗中最麻煩的一環(huán)便是數(shù)據(jù)記錄的比對(duì)即相鄰記錄相似重復(fù)的判定．

此外，客戶關(guān)系數(shù)據(jù)庫(kù)中常出現(xiàn)許多無用的數(shù)據(jù)，即“廢卡”信息，為了減少這些“臟數(shù)據(jù)”占用系統(tǒng)資源，也為了提高相似重復(fù)記錄的清洗速度，在相似重復(fù)記錄清洗前有必要對(duì)這些數(shù)據(jù)先行清洗．由于客戶關(guān)系數(shù)據(jù)庫(kù)都會(huì)記錄卡片使用情況，如用卡時(shí)間等信息，可以根據(jù)這些信息對(duì)所有的記錄進(jìn)行掃描，導(dǎo)出無用的數(shù)據(jù)，由人工方式判斷是否予以刪除．

由上所述，針對(duì)客戶關(guān)系表的數(shù)據(jù)特點(diǎn)，提出記錄清洗算法思路，具體實(shí)現(xiàn)步驟如下．

步驟一： “廢卡”記錄等“臟數(shù)據(jù)”清洗；

步驟二： 根據(jù)某個(gè)屬性或若干個(gè)屬性進(jìn)行排序；

步驟三： 根據(jù)關(guān)系表的屬性重要性，為部分屬性設(shè)定不同的權(quán)重Wi，權(quán)重之和為1，假設(shè)關(guān)系表中設(shè)定權(quán)值的屬性個(gè)數(shù)為n，判斷窗口內(nèi)記錄的屬性，給定一個(gè)集合Ai{0,1}，如果屬性值取值相等，Ai等于1，

否則Ai等于0，求

步驟五：將合并后的記錄插入數(shù)據(jù)表，刪除構(gòu)成相似重復(fù)的兩條記錄；

步驟六：用新合并的記錄參與隨后的記錄判重．

在客戶關(guān)系表中最重要的屬性莫過于身份證號(hào)了，所以身份證號(hào)的權(quán)值設(shè)置為最大．假設(shè)有數(shù)據(jù)記錄如表1所示，依次為身份證號(hào)、姓名和性別三個(gè)屬性分配權(quán)值，權(quán)值分別為 0.5、0.3、0.2，設(shè)置記錄相似度 U =0.7．依據(jù)上述算法，表1中前兩條記錄的清洗過程如下：

1) 根據(jù)身份證號(hào)進(jìn)行排序，排序結(jié)果同表1；

2) 計(jì)算 Ai，A1=1，A2=1，A3=1；

5) 合并兩條記錄，刪除原兩條記錄，新記錄參與之后的相似重復(fù)記錄清洗．

經(jīng)兩次清洗合并，表1的三條記錄清洗為表2的一條記錄．合并時(shí)需考慮屬性取值不同的合并策略，如表1中的三條記錄是相似重復(fù)記錄，而地址和卡號(hào)各不相同，必須分別對(duì)其進(jìn)行處理．卡號(hào)的合并處理較為簡(jiǎn)單，只需在關(guān)系表中增加新列，在新列中添加相似重復(fù)記錄中相應(yīng)的屬性值即可．對(duì)于地址的處理，目前的技術(shù)也較為成熟，如果相似重復(fù)記錄的地址數(shù)據(jù)均一樣，則直接進(jìn)行合并，不做任何處理；如果不一樣，必須清洗之后再合并，目前常用的地址清洗方法是基于特征字、基于地址詞典和基于規(guī)則的方法，文獻(xiàn)[3-5]對(duì)地址的處理方法均達(dá)到較好的效果，所以可以將地址導(dǎo)出參照相關(guān)文獻(xiàn)進(jìn)行清洗后，再將規(guī)范的地址導(dǎo)入關(guān)系表．

然而，因人為輸入等原因，導(dǎo)致關(guān)系表中出現(xiàn)如表3所示的兩條記錄，兩條記錄的性別、身份證號(hào)和地址均完全相同，第二條記錄因輸入錯(cuò)誤將“張”輸入成“章”，顯然兩條記錄互為相似重復(fù)記錄，這種情況可將記錄導(dǎo)出，設(shè)置同音字表，通過查詢同音字表由機(jī)器判斷清洗，或由人工判斷修正后再進(jìn)行清洗．

表3 相似重復(fù)記錄示例表

4 小結(jié)

在客戶關(guān)系數(shù)據(jù)庫(kù)中存在大量的客戶信息，有些客戶的信息是以多條記錄的方式存在于同一關(guān)系表中，這些記錄構(gòu)成了相似重復(fù)記錄．通過制定算法對(duì)相似重復(fù)記錄進(jìn)行清洗并合并，可以提高系統(tǒng)空間的利用率，降低記錄數(shù)量還可以提高新數(shù)據(jù)插入、無用數(shù)據(jù)刪除和查詢的速度．本文提出利用關(guān)系表的若干個(gè)屬性對(duì)關(guān)系表的數(shù)據(jù)記錄進(jìn)行排序，對(duì)排序后的相鄰記錄通過設(shè)置屬性權(quán)值和記錄相似度閘值，求相鄰記錄的相似度，如相鄰記錄構(gòu)成相似重復(fù)，再對(duì)其清洗并合并，取得了較好的效果．然而算法的屬性權(quán)重和記錄相似度閘值是憑經(jīng)驗(yàn)設(shè)置，實(shí)際應(yīng)用中應(yīng)設(shè)置多大較合適，文中未有定論，這將是下一步需進(jìn)一步研究的地方．

[1] HERNANDEZ M A, STOLFO S J. The Merge/Purge Problem for Large Databases[C]//In: Proceedings of the ACM SIGMOD International Conference on Management of Data, San Jose, California,1995:127-138.

[2] 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(1): 9-37.

[3] 張雪英,閭國(guó)年,李伯秋,等.基于規(guī)則的中文地址要素解析方法[J].地球信息科學(xué)學(xué)報(bào),2010,12(1):9-16.

[4] 程昌秀,于濱.一種基于規(guī)則的模糊中文地址分詞匹配方法[J].地理與地理信息科學(xué),2011,27(3):26-29.

[5] 劉哲,夏秀峰,宋曉燕,等. 一種中文地址類相似重復(fù)信息的檢測(cè)方法[J].小型微型計(jì)算機(jī)系統(tǒng),2008,29(4):726-729.