數(shù)據(jù)倉庫中重復(fù)記錄清理算法研究

1、    數(shù)據(jù)倉庫中重復(fù)記錄清理算法研究        鐘嘉慶 ，張義芳，盧志剛 時(shí)間:2009年06月03日     字 體: 大 中 小        關(guān)鍵詞:        ? 摘 要：關(guān)鍵詞：數(shù)據(jù)清理；重復(fù)記錄清理；重復(fù)記錄識(shí)別；數(shù)據(jù)倉庫? 目前，國內(nèi)外已經(jīng)有一些對(duì)數(shù)據(jù)清理

2、的研究，由于中文數(shù)據(jù)之間沒有以空格分割，這在識(shí)別上帶來了一定的難度，因此大部分的研究都只針對(duì)英文的數(shù)據(jù)清理，涉及中文數(shù)據(jù)清理的研究較少。重復(fù)數(shù)據(jù)清理技術(shù)旨在清除冗余的備份數(shù)據(jù)、確保只有“獨(dú)有的”數(shù)據(jù)存儲(chǔ)在磁盤上，即容量優(yōu)化保護(hù)技術(shù)。重復(fù)數(shù)據(jù)清理技術(shù)的關(guān)鍵是只保留唯一的數(shù)據(jù)實(shí)例，有效地解決了“容量膨脹”的效率問題12、優(yōu)先隊(duì)列算法3等；對(duì)第二類算法的研究一般都是直接引用字符串相似匹配算法4，這種算法的缺點(diǎn)是沒有考慮到字段不等長、中文字段語義重點(diǎn)偏后等重復(fù)記錄的特點(diǎn)。1 重復(fù)記錄排序算法的改進(jìn)? 重復(fù)記錄清理的直觀方法是將每一個(gè)記錄與數(shù)據(jù)庫中其余記錄逐個(gè)進(jìn)行對(duì)比，該方法的識(shí)別精度非常高，但是在數(shù)據(jù)

3、量較大的情況時(shí)，其處理時(shí)間會(huì)讓用戶難以忍受。鄰近排序算法(SNM)5是目前常用的一種排序方法，它有效地克服了直觀方法的缺點(diǎn)，大大提高了重復(fù)記錄的匹配效率和重復(fù)記錄清理的完成效率。但是，SNM算法存在其匹配結(jié)果嚴(yán)重依賴于排序關(guān)鍵字的選擇和滑動(dòng)窗口大小W的選取很難控制等缺陷。由于在SNM算法里記錄只能與窗口內(nèi)的紀(jì)錄進(jìn)行比較，當(dāng)W太小時(shí)或排序的關(guān)鍵字選擇不當(dāng)時(shí)，會(huì)造成漏配；而當(dāng)W太大時(shí)又會(huì)產(chǎn)生很多沒有必要的比較，因此恰當(dāng)?shù)腤無論如何都無法得到。? 本節(jié)針對(duì)SNM算法存在的上述缺陷作了改進(jìn)，改進(jìn)后算法的基本思想是使用相對(duì)較小的滑動(dòng)窗口，選擇數(shù)據(jù)庫的一個(gè)關(guān)鍵字執(zhí)行SNM算法，存儲(chǔ)本次排序后相似記錄的序號(hào)

4、，然后依次選擇數(shù)據(jù)庫中的其他關(guān)鍵字獨(dú)立地執(zhí)行SNM算法，并在每次執(zhí)行完畢后把此次執(zhí)行結(jié)構(gòu)中新增的相似記錄號(hào)添加到相似記錄存儲(chǔ)表中得到所有可能重復(fù)記錄的序號(hào)，然后對(duì)對(duì)這些可能的重復(fù)記錄采用直觀方法進(jìn)行清理。? 改進(jìn)后的SNM算法的偽碼描述如下：? while(還有沒用過的關(guān)鍵字)? do? 為記錄集TS中的記錄選擇該趟排序需要的排序關(guān)? 鍵字；? 根據(jù)排序關(guān)鍵字對(duì)TS中的記錄進(jìn)行排序；? 滑動(dòng)窗口W從TS的第一個(gè)記錄開始滑動(dòng)；? while(W沒有滑動(dòng)到TS的尾部)? do? 初始化執(zhí)行對(duì)比的次數(shù)n=0；? while(執(zhí)行的對(duì)比次數(shù)n<|W|)? do? 新進(jìn)入滑動(dòng)窗口的記錄與第n+1個(gè)

5、進(jìn)入窗口的記錄進(jìn)行重復(fù)記錄比較；? if(比較的記錄為相似重復(fù)記錄)? ? 把相似重復(fù)記錄的記錄號(hào)添加到相似記錄存儲(chǔ)表；? ? 執(zhí)行n+1；? ? 向下滑動(dòng)窗口；? ? 對(duì)相似記錄存儲(chǔ)表中的記錄采用直觀方法進(jìn)行比較，記錄相似重復(fù)記錄聚類；? ? 記錄排好序后，下一個(gè)要解決的問題是如何判斷兩條記錄是否為相似重復(fù)記錄。識(shí)別重復(fù)記錄首先需要進(jìn)行字段相似度的計(jì)算，然后再根據(jù)字段的權(quán)重進(jìn)行加權(quán)和計(jì)算后得到記錄的相似度，最后進(jìn)行記錄相似度和所設(shè)定閥值的比較，如果兩條記錄的相似度小于閥值，則認(rèn)為這兩條記錄匹配，否則認(rèn)為是兩個(gè)不同的記錄。基于相似度的重復(fù)記錄識(shí)別算法1是最常用的一種重復(fù)記錄識(shí)別方法，但是恰當(dāng)閾

6、值的設(shè)定仍是一個(gè)沒有解決的難題。若閾值設(shè)定的過小，則容易遺漏某些相似的重復(fù)記錄，從而降低了算法的匹配率；若閾值設(shè)定的過大，則容易將某些不同的記錄誤判為相似重復(fù)記錄，從而降低了算法的正確率。此算法對(duì)記錄的識(shí)別僅使用一個(gè)單一的閾值過于絕對(duì)，且沒有考慮文中語句語義偏后的特點(diǎn)，無法滿足實(shí)際情況的要求。? 下面針對(duì)基于相似度的重復(fù)記錄識(shí)別算法存在的上述問題對(duì)此算法進(jìn)行了適當(dāng)改進(jìn)，給出了一種基于雙閾值6位置權(quán)重7的語義重復(fù)記錄識(shí)別算法。本算法的具體描述如下：對(duì)記錄相似度設(shè)定一大一小兩個(gè)閾值up和low，當(dāng)通過位置權(quán)重識(shí)別法計(jì)算出當(dāng)前兩條記錄的相似度大于up，則直接判定它們是重復(fù)記錄；若計(jì)算出的相似度小于l

7、ow，則可以判定它們是兩個(gè)不同的記錄；而對(duì)于相似度在up和low之間的兩條記錄，則不能直接確定它們是否重復(fù)或不重復(fù)，需要通過語義重復(fù)識(shí)別法3,8? 其中，f1和f2分別為兩個(gè)中文字段(如果字段中有英文字母，則將連續(xù)的英文字母視作一個(gè)漢字)，m和n分別為f1和f2的字?jǐn)?shù)，c為f1和f2的識(shí)別字符數(shù)量，L1(i)和L2(i)分別為識(shí)別字符i在f1和f210。例如，f1=“燕大電氣工程學(xué)院”、f2=“燕山大學(xué)電氣工程學(xué)院”，下面通過位置權(quán)重識(shí)別法判定S1和S2是否為重復(fù)字段。和的匹配字符為“燕”、“大”、“電”、“氣”、“工”、“程”、“學(xué)”、“院”，它們?cè)趂1中的匹配序依次為“1、2、3、4、5、

8、6、7、8”，在f2中的匹配序依次為“1、3、5、6、7、8、9、10”。那么f1和f2的語義相似度為：? ? 基于語義距離的相似度識(shí)別方法體現(xiàn)了字段內(nèi)部的結(jié)構(gòu)和詞語之間語義的相互作用關(guān)系,而編輯距離由于同義詞詞林的應(yīng)用可以兼顧同義詞之間的替換,并體現(xiàn)了組成句子的每個(gè)詞深層的語義信息?；谡Z義距離的相似度識(shí)別算法的基本思路是：首先，利用參考文獻(xiàn)11中介紹的骨架依存樹思想分析字段的語法結(jié)構(gòu)，得到字段中所有的核心詞和直接依存于它們的有效詞組成的搭配對(duì)(有效詞定義為動(dòng)詞、名詞和形容詞，它是由分詞后的詞性標(biāo)注決定的)，然后再進(jìn)行語義距離(為兩個(gè)字段有效搭配對(duì)的最短距離)的相似度計(jì)算，最后根據(jù)閾值進(jìn)行重

9、復(fù)識(shí)別判斷。? 設(shè)f1和f2為需要識(shí)別的兩字段，f1包含的詞為f11、f12、f1m，f2包含的詞為f21、f22、f2n，則詞f1i(1im)和f2j(1jn)之間的相似度可用sim( f1, f2)來表示，這樣就得到兩個(gè)字段中任意搭配對(duì)的相似度，f1和f2兩字段之間的語義相似度sim( f1, f2)的計(jì)算公式如下：? ? 使用雙閾值位置權(quán)重的語義識(shí)別法，雖然在一定程度上增加了用戶的工作量，降低了算法的效率，但同時(shí)提高了算法的正確性和健壯性；而把位置權(quán)重和基于語義距離的相似度識(shí)別兩種方法結(jié)合起來，揚(yáng)長避短、互為補(bǔ)充，根據(jù)這些特征計(jì)算字段之間的相似度，可以使本重復(fù)識(shí)別算法獲得很高的準(zhǔn)確率。通

10、過以上分析可知，本節(jié)對(duì)重復(fù)識(shí)別算法的改進(jìn)是有效的、值得的。3 重復(fù)記錄合并算法的改進(jìn)? 在相似重復(fù)記錄的識(shí)別完成以后，下一步要做的工作就是選擇合適的方法合并識(shí)別出來的相似重復(fù)記錄。參考文獻(xiàn)8、12介紹了目前常用的多種重復(fù)記錄合并方法，它們?cè)诤喜⒎矫娓饔欣?，單?dú)使用都無法得到很好的效果，下面對(duì)此進(jìn)行改進(jìn)。? 針對(duì)上述缺點(diǎn)，本節(jié)采用實(shí)用兼人工策略，給出了一種實(shí)用和聚類算法結(jié)合的合并算法。從一組相似重復(fù)記錄中選擇與其它記錄匹配次數(shù)最多的一條記錄進(jìn)行保留，如果多個(gè)不同的記錄具有相同的匹配率，則對(duì)這些相似記錄進(jìn)行聚類(會(huì)通過屏幕把聚類結(jié)果返回給用戶)，由用戶人工確定要保留的記錄，并把其他重復(fù)記錄從數(shù)據(jù)

11、庫中刪除。? 針對(duì)現(xiàn)有的重復(fù)記錄清理策略存在的問題，分析了其原因，找出了現(xiàn)有重復(fù)記錄清理策略里記錄排序、重復(fù)記錄識(shí)別、重復(fù)記錄合并各步驟中所用算法存在的缺陷，給出了各自的改進(jìn)方案，并通過算法分析和舉例說明證明了改進(jìn)的合理性。改進(jìn)后的重復(fù)記錄清理算法可以有效地提高判斷質(zhì)量，減小誤判率，縮短了重復(fù)記錄處理時(shí)間，很好地保障了數(shù)據(jù)倉庫數(shù)據(jù)的質(zhì)量。參考文獻(xiàn)1?LIN De Kang. An Information-theoretic Definition of SimilarityC/Proc. Of the 15th Intermational Conf. on Machine Learning. S

12、an Francisco,CA,USA:Morgan Kaufmann,1998.2?MONGE A. E, ELKAN? C. An Efficient Domain-Independent Algorithm for Detecting Approximately Duplicate Database Records.DMKD,1997.3?GUTTMAN A. R-trees? a dynamic index structure for spatial searching Proc. ACM SIGMOD Int Conf on Management of Data, 1984，47-5

13、7.4?馮玉才，桂浩，李華，等. 數(shù)據(jù)分析和清理中相關(guān)算法研究J. 小型微型計(jì)算機(jī)系統(tǒng), 2005,26(6):1018-1022.5 HEMANDEZ， M? A， STOLFO? S? J. The Merge/Purge Problem for Large DatabaseC.In SIGMOD Conference,1995:127-138.6?洪圓，孫未未，施伯樂. 一種使用雙閥值的數(shù)據(jù)倉庫環(huán)境下重復(fù)記錄消除算法J. 計(jì)算機(jī)工程與應(yīng)用，2005，1:168-170.7?張雪英，閭國年. 基于字面相似度的地理信息分類體系自動(dòng)轉(zhuǎn)換方法J.遙感學(xué)報(bào)，2008，12(3):433-440.8 劉寶艷，林鴻飛，趙晶.基于改進(jìn)編輯距離和依存文法的漢語句子相似度計(jì)算J.計(jì)算機(jī)應(yīng)用與軟件，2008，25(7):33-34.9?陳偉. 數(shù)據(jù)清理關(guān)鍵技術(shù)及其軟件平臺(tái)的研究與應(yīng)用D. 南京航空航天大學(xué)，2004.10?王源，吳小濱，涂從文，等.后控制規(guī)范的計(jì)算機(jī)處理J.現(xiàn)代圖書情報(bào)技術(shù)，1993，2: