相似重復(fù)數(shù)據(jù)檢測的數(shù)據(jù)清洗算法優(yōu)化

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

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

0 引 言

數(shù)據(jù)清洗專家研究學(xué)者對于數(shù)據(jù)清洗并未給出標準化的定義[1]，對它的解釋大多基于字面意思，理解為通過某種技術(shù)方法發(fā)現(xiàn)數(shù)據(jù)集中錯誤或者不一致的數(shù)據(jù)也即臟數(shù)據(jù)并將其進行改正或者剔除[2]。數(shù)據(jù)清洗主要有數(shù)據(jù)的標準化、解析、增強以及重復(fù)數(shù)據(jù)的歸并[3]。標準化主要是將數(shù)據(jù)在格式上和表達方式上分別進行規(guī)范化和同一化；解析針對字段的拆分以及合并；增強主要是將原有缺少的數(shù)據(jù)進行補充以達到完整性[4]；重復(fù)數(shù)據(jù)的歸并主要是針對相似重復(fù)的數(shù)據(jù)或者進行合并或者進行剔除[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)和剔除。這些存儲在數(shù)據(jù)庫中相似重復(fù)數(shù)據(jù)的存在不僅會浪費系統(tǒng)有限的存儲空間，并且還會影響后續(xù)對一些地理檢測數(shù)據(jù)情況的正確判斷，因此相似重復(fù)數(shù)據(jù)的處理是一項重要的任務(wù)。

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

1 改進算法SVN

1.1 相關(guān)概念

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

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

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

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

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

1.2 SNM算法

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

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

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

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

1.3 SVN算法思想

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

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

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

(3)設(shè)定數(shù)據(jù)記錄為R={R1,R2,…,Rl},其中l(wèi)表示數(shù)據(jù)記錄的個數(shù)，相應(yīng)的某個記錄為Ri(1≤i≤l),并且兩個記錄在某個屬性(比如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表示針對某個屬性值相似重復(fù)的相似記錄；n表示某個記錄具有n個屬性值的長度；p為記錄的第p個屬性值。

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

Qi,j,p=M*Wp

(2)

(3)

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

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

Zi,j?U

(4)

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

如果a[i]

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

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

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

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

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

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

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

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

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

2 實驗與結(jié)果分析

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

2.1 實驗過程

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

表1 準確率和全面率的對比

度量標準SNMSVN3萬7萬3萬7萬準確率/%82.5799585全面率/%8180100100

表2 記錄添加運行時間

2.2 結(jié)果討論

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

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

3 結(jié)束語

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