蔣 園，韓 旭，馬丹璇，羅登昌

(長江水利委員會(huì) 長江勘測(cè)規(guī)劃設(shè)計(jì)研究有限責(zé)任公司，湖北 武漢 430010)

0 引 言

數(shù)據(jù)清洗專家研究學(xué)者對(duì)于數(shù)據(jù)清洗并未給出標(biāo)準(zhǔn)化的定義[1]，對(duì)它的解釋大多基于字面意思，理解為通過某種技術(shù)方法發(fā)現(xiàn)數(shù)據(jù)集中錯(cuò)誤或者不一致的數(shù)據(jù)也即臟數(shù)據(jù)并將其進(jìn)行改正或者剔除[2]。數(shù)據(jù)清洗主要有數(shù)據(jù)的標(biāo)準(zhǔn)化、解析、增強(qiáng)以及重復(fù)數(shù)據(jù)的歸并[3]。標(biāo)準(zhǔn)化主要是將數(shù)據(jù)在格式上和表達(dá)方式上分別進(jìn)行規(guī)范化和同一化；解析針對(duì)字段的拆分以及合并；增強(qiáng)主要是將原有缺少的數(shù)據(jù)進(jìn)行補(bǔ)充以達(dá)到完整性[4]；重復(fù)數(shù)據(jù)的歸并主要是針對(duì)相似重復(fù)的數(shù)據(jù)或者進(jìn)行合并或者進(jìn)行剔除[5]。

數(shù)據(jù)清洗技術(shù)現(xiàn)在不僅在大數(shù)據(jù)互聯(lián)網(wǎng)企業(yè)的海量數(shù)據(jù)挖掘中得到了廣泛應(yīng)用，而且很多工程數(shù)據(jù)也用到了數(shù)據(jù)清洗技術(shù)[6]，比如堤防工程數(shù)據(jù)。堤防工程數(shù)據(jù)中很多地名、經(jīng)緯度數(shù)據(jù)不僅數(shù)據(jù)位數(shù)多、復(fù)雜，而且很多數(shù)據(jù)命名極易令人混淆，錄入系統(tǒng)后出現(xiàn)大量相似重復(fù)的數(shù)據(jù)，人工還不容易發(fā)現(xiàn)和剔除。這些存儲(chǔ)在數(shù)據(jù)庫中相似重復(fù)數(shù)據(jù)的存在不僅會(huì)浪費(fèi)系統(tǒng)有限的存儲(chǔ)空間，并且還會(huì)影響后續(xù)對(duì)一些地理檢測(cè)數(shù)據(jù)情況的正確判斷，因此相似重復(fù)數(shù)據(jù)的處理是一項(xiàng)重要的任務(wù)。

目前針對(duì)相似重復(fù)數(shù)據(jù)的算法有很多，比如N-Grams算法、聚類算法、排序和合并的算法等等[7]。N-Grams算法主要通過計(jì)算得到一個(gè)能代表數(shù)據(jù)記錄的屬性鍵值，并且鍵值生成一個(gè)映射數(shù)據(jù)庫的哈希表，然后按照一定的算法，分析哈希表、計(jì)算哈希值、根據(jù)哈希值來判斷記錄之間的相似度，最后判定是否為相似的數(shù)據(jù)[8]。聚類算法主要通過無監(jiān)督的學(xué)習(xí)、迭代計(jì)算將相似或者相同的數(shù)據(jù)聚合到同一類中，同類數(shù)據(jù)相似度大，但不同類間的數(shù)據(jù)差異大[9]。排序和合并算法基于聚類主要分為以個(gè)步驟：先依據(jù)某個(gè)特征將數(shù)據(jù)庫中的數(shù)據(jù)表進(jìn)行排序即分類，讓相似數(shù)據(jù)記錄聚集在小范圍中，再在小范圍內(nèi)對(duì)記錄進(jìn)行相似度比較。排序和合并算法包括SNM算法(鄰近排序算法)、MPN算法(多趟近鄰排序算法)以及優(yōu)先權(quán)隊(duì)列算法[10]。多趟近鄰排序算法可以將相似重復(fù)的數(shù)據(jù)聚集在較全的集合中，但該算法不僅要多次使用SNM算法還得多次創(chuàng)建不同的排序關(guān)鍵字[11]；優(yōu)先權(quán)隊(duì)列算法雖然可以將不同的相似重復(fù)記錄放到不同隊(duì)列中，從而減少比對(duì)的次數(shù)，但它使用的是單趟的優(yōu)先權(quán)隊(duì)列算法容易漏配，如果采用多趟優(yōu)先權(quán)隊(duì)列算法又造成計(jì)算時(shí)間過長。

1 改進(jìn)算法SVN

1.1 相關(guān)概念

在數(shù)據(jù)清洗中衡量一個(gè)算法對(duì)于相似重復(fù)數(shù)據(jù)的檢測(cè)效率主要根據(jù)召回率以及誤識(shí)別率[12]。

準(zhǔn)確率：對(duì)于一個(gè)數(shù)據(jù)集合，運(yùn)用算法后實(shí)際檢測(cè)出來的相似重復(fù)的記錄數(shù)目占原有的相似重復(fù)的記錄的比例[13]。

全面率：一個(gè)數(shù)據(jù)集合運(yùn)用算法后正確地檢測(cè)出相似重復(fù)的記錄占已經(jīng)運(yùn)用算法檢測(cè)出相似重復(fù)的記錄的比率，這個(gè)比率越低越好[14]。

相似重復(fù)記錄：如果在數(shù)據(jù)庫系統(tǒng)中兩條記錄之間屬性值高度相似或者相同，則認(rèn)為是相似重復(fù)記錄[15]。

閾值：通常用U表示，判斷一個(gè)效果臨界值。文中當(dāng)計(jì)算出來的相似度高于U，則認(rèn)為是相似重復(fù)記錄，小于則認(rèn)為不是[16]。

1.2 SNM算法

SNM算法是在數(shù)據(jù)清洗中針對(duì)相似重復(fù)數(shù)據(jù)問題應(yīng)用比較成熟的算法，主要分為三個(gè)步驟：

(1)排序關(guān)鍵字的創(chuàng)建。首先在數(shù)據(jù)表中提取關(guān)鍵的屬性或者屬性的組合來區(qū)分記錄，依據(jù)這些提取的屬性或者屬性的組合對(duì)記錄進(jìn)行劃分時(shí)具有很強(qiáng)的區(qū)分度[17]。

(2)按照創(chuàng)建的關(guān)鍵字也即關(guān)鍵的屬性，將數(shù)據(jù)庫中不同位置的相似重復(fù)的記錄分配到相鄰的位置也即順序排序[18]。

(3)針對(duì)數(shù)據(jù)集中的數(shù)據(jù)，設(shè)定一個(gè)具有一定寬度比如X大小的滑動(dòng)窗口，窗口采用先進(jìn)先出的隊(duì)列方式來處理記錄，第X進(jìn)來的記錄會(huì)與窗口中第一到X-1的記錄進(jìn)行逐個(gè)比較，每比較完一條記錄窗口就會(huì)向后移動(dòng)，如果在比較的過程中存在兩條相似重復(fù)的記錄則會(huì)進(jìn)行相應(yīng)的合并處理。這種算法對(duì)檢測(cè)速度有很大的改善，因?yàn)樗闹饕?jì)算次數(shù)也只有N*(X-1),實(shí)際中X不大，但是算法還是存在如下缺陷：過于依賴關(guān)鍵字的選取，關(guān)鍵字選取的好壞將直接影響后面的檢測(cè)正確度；X的大小影響計(jì)算的次數(shù)；滑動(dòng)窗口中相似記錄的判別多數(shù)采用笛卡爾積的計(jì)算方式，計(jì)算時(shí)間較長且最重要的是針對(duì)已經(jīng)存入到數(shù)據(jù)庫(如關(guān)系型數(shù)據(jù)庫中的數(shù)據(jù)記錄)直接運(yùn)用SNM算法存在很大的弊端。因?yàn)閿?shù)據(jù)記錄中的數(shù)據(jù)隨著時(shí)間的變化會(huì)不停地添加新的數(shù)據(jù)記錄，如果此時(shí)還采用SNM排序算法進(jìn)行比較，則會(huì)將舊數(shù)據(jù)再比較一次，這樣會(huì)造成計(jì)算的浪費(fèi)。因此，文中針對(duì)關(guān)系型數(shù)據(jù)存儲(chǔ)的特點(diǎn)，將SNM算法進(jìn)行優(yōu)化來對(duì)相似重復(fù)數(shù)據(jù)進(jìn)行清洗。

1.3 SVN算法思想

文中提出的改進(jìn)SVN的算法思想主要是避免重復(fù)比較過去的舊數(shù)據(jù)，從而減少計(jì)算量。處理過程如下：

(1)因?yàn)閿?shù)據(jù)庫的記錄中并非所有的記錄都有唯一的主鍵，可以對(duì)每個(gè)記錄設(shè)定唯一的id編號(hào)，只不過這個(gè)標(biāo)號(hào)值的權(quán)重設(shè)為0并不納入到后面的算法計(jì)算。

(2)創(chuàng)建關(guān)系記錄屬性表。首先依據(jù)表的屬性創(chuàng)建各種不同的屬性記錄庫，再在屬性記錄庫中針對(duì)每個(gè)屬性創(chuàng)建屬性值記錄表，這些表中記錄各個(gè)不同的屬性值以及對(duì)應(yīng)這個(gè)屬性的記錄。這里類似于倒排索引的思想，“單詞”對(duì)應(yīng)“文檔”的倒排索引鏈表結(jié)構(gòu)[19]，其中的記錄可以用id編號(hào)表示

(3)設(shè)定數(shù)據(jù)記錄為R={R1,R2,…,Rl},其中l(wèi)表示數(shù)據(jù)記錄的個(gè)數(shù)，相應(yīng)的某個(gè)記錄為Ri(1≤i≤l),并且兩個(gè)記錄在某個(gè)屬性(比如p屬性)之間的關(guān)系用式1表示：

M=A(Rip,Rjp)={0,1}(1≤i≤l,1≤j≤l,1≤

p≤n)

(1)

其中，Rip=(ID1,ID2,…,IDm)，IDm表示針對(duì)某個(gè)屬性值相似重復(fù)的相似記錄；n表示某個(gè)記錄具有n個(gè)屬性值的長度；p為記錄的第p個(gè)屬性值。

當(dāng)M=1，則判斷兩個(gè)記錄在p屬性具有很近的關(guān)系是重復(fù)關(guān)系，當(dāng)為0則判斷在當(dāng)前的屬性下沒有相似關(guān)系。依據(jù)此種關(guān)系就可以計(jì)算兩個(gè)記錄在某個(gè)屬性值記錄表下的相似度，以及記錄每個(gè)記錄在此屬性值記錄表中的值。設(shè)定相似度如下：

Qi,j,p=M*Wp

(2)

(3)

其中，Zi,j表示為i,j兩條記錄的相似度值。

(4)設(shè)定相似閾值U，如果式4成立，就可以判斷兩者之間的相似度。

Zi,j?U

(4)

(5)屬性值記錄表的數(shù)據(jù)在進(jìn)行比較的過程中，并不是對(duì)屬性值記錄表進(jìn)行順序比較，如果從頭到尾比對(duì)會(huì)增加時(shí)間長度。文中引用快速排序算法先進(jìn)行排序再進(jìn)行比較，經(jīng)過從大到小排序或者從小到大排序后，一旦比較發(fā)現(xiàn)了有相等的屬性值后出現(xiàn)不相等的值，后面的數(shù)據(jù)就不用再進(jìn)行比較，從而縮短了計(jì)算時(shí)間。傳統(tǒng)的快速排序算法主要將從數(shù)據(jù)組中隨機(jī)選取一個(gè)數(shù)作為比對(duì)數(shù)，再將其他數(shù)據(jù)與比對(duì)數(shù)進(jìn)行比較，也即分為兩段比較方法，比它小的數(shù)放在左邊，比它大的數(shù)放到后邊，最后多次遞歸比較來達(dá)到最后的排序。但是因?yàn)槲闹嗅槍?duì)的是重復(fù)相似的數(shù)據(jù)，所以很顯然屬性值記錄表中存在很多的重復(fù)數(shù)據(jù)，對(duì)這些重復(fù)數(shù)據(jù)再一次進(jìn)行排序就會(huì)浪費(fèi)計(jì)算時(shí)間。文中采取三區(qū)間比較方法讓重復(fù)的數(shù)據(jù)不需要再參與排序，只讓大于或者小于選定的數(shù)參與排序。比如選定的數(shù)為x，只對(duì)大于x或者小于x的序列數(shù)進(jìn)行排序，如圖1所示，從左到右掃描使得指針lt維護(hù)[lo…lt]中的數(shù)字比x小，另外的指針gt維護(hù)[g(t+1)…h(huán)i]的數(shù)字大于x，以及指針i，使得所有[lt…(i-1)]的數(shù)字與x大小相等。[i…gt]之間的數(shù)字是還沒有進(jìn)行處理的數(shù)字，i從lo開始進(jìn)行掃描：

如果a[i]

如果a[i]>v，那么交換a[i]和a[gt],gt指針自減；

如果a[i]=v，i指針自增。

圖1 三區(qū)間快速排序示意

1.4 算法的實(shí)現(xiàn)步驟

(1)將數(shù)據(jù)庫中的數(shù)據(jù)記錄標(biāo)記相應(yīng)的屬性記錄標(biāo)號(hào)，并且在數(shù)據(jù)庫中增加屬性記錄庫，對(duì)應(yīng)的庫中針對(duì)每個(gè)屬性增加屬性值記錄表。

(2)將數(shù)據(jù)庫中錄入的所有的堤防工程數(shù)據(jù)記錄對(duì)應(yīng)屬性找到屬性值記錄表，將屬性值和記錄編號(hào)通過編碼程序錄入，從而完成屬性之間的關(guān)系表。

(3)拿到當(dāng)前記錄，依據(jù)當(dāng)前記錄的屬性值從屬性記錄庫中找到對(duì)應(yīng)的屬性記錄表，依據(jù)屬性記錄表的值讀取經(jīng)過三分區(qū)快速算法排序后的數(shù)據(jù)屬性值，通過對(duì)比來判斷當(dāng)前屬性是否相似重復(fù)。當(dāng)相似重復(fù)，則用1乘以相應(yīng)的權(quán)重，當(dāng)不重復(fù)，即為0，不用乘以相應(yīng)的權(quán)重，并且將當(dāng)前的記錄分別和每一個(gè)屬性值記錄表進(jìn)行比較計(jì)算，最后將每個(gè)記錄的屬性相似值求和即為最終的記錄相識(shí)值。

(4)根據(jù)相似值和規(guī)定閾值之間的大小來判斷兩個(gè)記錄之間的相似度大小。

(5)當(dāng)新增記錄時(shí)，將記錄的值增加到屬性庫中的每個(gè)屬性值記錄表，然后只需要重復(fù)步驟3～5，計(jì)算新增的記錄和屬性表中其他記錄之間的相似度。

2 實(shí)驗(yàn)與結(jié)果分析

在相同的實(shí)驗(yàn)環(huán)境下，應(yīng)用傳統(tǒng)的基于SNM算法的數(shù)據(jù)清洗方法和優(yōu)化后的SVN算法，分別對(duì)某存儲(chǔ)有7萬條數(shù)據(jù)記錄的堤防工程的數(shù)據(jù)庫進(jìn)行相似重復(fù)數(shù)據(jù)的數(shù)據(jù)清洗處理，記錄表中包含7條屬性值，實(shí)驗(yàn)中隨機(jī)測(cè)試3萬，7萬數(shù)據(jù)記錄，并且人為地在每組里面設(shè)置245，3 487條重復(fù)記錄數(shù)據(jù)，統(tǒng)計(jì)分別在兩種算法下的準(zhǔn)確率和全面率以及添加新記錄后的運(yùn)行時(shí)間。

2.1 實(shí)驗(yàn)過程

分別對(duì)傳統(tǒng)SNM算法和改進(jìn)后的SVN算法在準(zhǔn)確率以及全面率上進(jìn)行對(duì)比，并且對(duì)比添加記錄后運(yùn)行時(shí)間，結(jié)果如表1和表2所示。

表1 準(zhǔn)確率和全面率的對(duì)比

度量標(biāo)準(zhǔn)SNMSVN3萬7萬3萬7萬準(zhǔn)確率/%82.5799585全面率/%8180100100

表2 記錄添加運(yùn)行時(shí)間

2.2 結(jié)果討論

通過表1可以發(fā)現(xiàn)，在針對(duì)準(zhǔn)確率和全面率時(shí)，改進(jìn)后的SVN算法相較傳統(tǒng)的SVN算法有明顯的改善，雖然隨著數(shù)據(jù)量的增加SVN在準(zhǔn)確率上是下降的，但是改善后的還是較改善前的高。

表2表明，當(dāng)添加記錄時(shí)改進(jìn)后的SVN算法的運(yùn)行時(shí)間還是比之前的要小。因?yàn)閭鹘y(tǒng)的SVN算法需要將所有的數(shù)據(jù)進(jìn)行新舊比對(duì)，這會(huì)消耗大量的計(jì)算時(shí)間，雖然優(yōu)化后的SVN算法需要將屬性表中的數(shù)據(jù)進(jìn)行排序，還要添加新的屬性到屬性表中增加了時(shí)間復(fù)雜度，但文中的三區(qū)間快速算法已經(jīng)較之前的快速算法有了很大的改善。而且本來增加的記錄的數(shù)據(jù)量相比已經(jīng)存在于數(shù)據(jù)庫中的記錄已經(jīng)很少了。因此，改進(jìn)的SVN算法是有效的。

3 結(jié)束語

無論是人工錄入還是程序讀入數(shù)據(jù)到數(shù)據(jù)庫中，總會(huì)存在很多相似重復(fù)的記錄數(shù)據(jù)，如果單靠數(shù)據(jù)庫管理員來檢測(cè)，則效率非常低下，尤其是堤防工程數(shù)據(jù)大多是編碼編號(hào)，數(shù)據(jù)位數(shù)也較多、復(fù)雜，因此好的檢測(cè)算法非常必要。文中針對(duì)傳統(tǒng)SNM算法在關(guān)系型數(shù)據(jù)庫添加新記錄后進(jìn)行相似重復(fù)數(shù)據(jù)檢測(cè)時(shí)需要重復(fù)比對(duì)舊的數(shù)據(jù)增加時(shí)間復(fù)雜度的缺點(diǎn)進(jìn)行改進(jìn)，提出一種SVN算法。該算法主要通過在數(shù)據(jù)庫中增加屬性記錄庫和屬性值記錄表，然后將數(shù)據(jù)表中的記錄值以及對(duì)應(yīng)的權(quán)重添加到對(duì)應(yīng)的屬性值記錄表中，在這中間還需要通過三區(qū)間排序算法將屬性值進(jìn)行從大到小的排序，最后新添加記錄時(shí)可以將其屬性添加到對(duì)應(yīng)的屬性記錄表中和三區(qū)間排序算法排序后的屬性值進(jìn)行屬性比對(duì)，并且按照相應(yīng)的權(quán)重計(jì)算相似度，最后將相似度按照大小進(jìn)行排序。實(shí)驗(yàn)結(jié)果表明，該算法提高了相似重復(fù)數(shù)據(jù)檢測(cè)的準(zhǔn)確率和全面率。同時(shí)該算法也存在不足之處，因?yàn)殡S著數(shù)據(jù)量的增加，準(zhǔn)確率跟傳統(tǒng)算法相比也沒多大改善，而且系統(tǒng)需要額外建立屬性庫和屬性表，當(dāng)數(shù)據(jù)量是海量數(shù)據(jù)時(shí)，這將會(huì)占用一部分存儲(chǔ)空間，這方面尚需進(jìn)一步完善。