??? 摘 要：針對(duì)重復(fù)記錄清理中的“排序、識(shí)別、合并”算法存在的問(wèn)題進(jìn)行了改進(jìn)。改進(jìn)后的重復(fù)記錄清理算法在保證記錄匹配率的情況下有效地提高了記錄排序的效率；在重復(fù)記錄識(shí)別時(shí)，考慮了匹配字段的文字?jǐn)?shù)量、在2個(gè)字段中出現(xiàn)的頻率、在記錄中各字段的重要性(權(quán)重)、中文字段的語(yǔ)義和語(yǔ)義重點(diǎn)偏后等5個(gè)因素；合并重復(fù)記錄時(shí)采用了聚類(lèi)和實(shí)用算法并用的策略，有效地提高了數(shù)據(jù)倉(cāng)庫(kù)中重復(fù)記錄清理算法的準(zhǔn)確性和健壯性。
??? 關(guān)鍵詞：數(shù)據(jù)清理；重復(fù)記錄清理；重復(fù)記錄識(shí)別；數(shù)據(jù)倉(cāng)庫(kù)

?

??? 目前，國(guó)內(nèi)外已經(jīng)有一些對(duì)數(shù)據(jù)清理的研究，由于中文數(shù)據(jù)之間沒(méi)有以空格分割，這在識(shí)別上帶來(lái)了一定的難度，因此大部分的研究都只針對(duì)英文的數(shù)據(jù)清理，涉及中文數(shù)據(jù)清理的研究較少。重復(fù)數(shù)據(jù)清理技術(shù)旨在清除冗余的備份數(shù)據(jù)、確保只有“獨(dú)有的”數(shù)據(jù)存儲(chǔ)在磁盤(pán)上，即容量?jī)?yōu)化保護(hù)技術(shù)。重復(fù)數(shù)據(jù)清理技術(shù)的關(guān)鍵是只保留唯一的數(shù)據(jù)實(shí)例，有效地解決了“容量膨脹”的效率問(wèn)題^[1]。
??? 從數(shù)據(jù)清理算法研究內(nèi)容上講，重復(fù)數(shù)據(jù)清除算法可分為兩類(lèi)：一類(lèi)是數(shù)據(jù)清理的記錄間算法，一類(lèi)是數(shù)據(jù)清理的記錄內(nèi)算法。目前，研究人員對(duì)第一類(lèi)算法研究得比較多，如：滑動(dòng)窗口算法^[2]、優(yōu)先隊(duì)列算法^[3]等；對(duì)第二類(lèi)算法的研究一般都是直接引用字符串相似匹配算法^[4]，這種算法的缺點(diǎn)是沒(méi)有考慮到字段不等長(zhǎng)、中文字段語(yǔ)義重點(diǎn)偏后等重復(fù)記錄的特點(diǎn)。
1 重復(fù)記錄排序算法的改進(jìn)
??? 重復(fù)記錄清理的直觀方法是將每一個(gè)記錄與數(shù)據(jù)庫(kù)中其余記錄逐個(gè)進(jìn)行對(duì)比，該方法的識(shí)別精度非常高，但是在數(shù)據(jù)量較大的情況時(shí)，其處理時(shí)間會(huì)讓用戶(hù)難以忍受。鄰近排序算法(SNM)[5]是目前常用的一種排序方法，它有效地克服了直觀方法的缺點(diǎn)，大大提高了重復(fù)記錄的匹配效率和重復(fù)記錄清理的完成效率。但是，SNM算法存在其匹配結(jié)果嚴(yán)重依賴(lài)于排序關(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)生很多沒(méi)有必要的比較，因此恰當(dāng)?shù)腤無(wú)論如何都無(wú)法得到。
??? 本節(jié)針對(duì)SNM算法存在的上述缺陷作了改進(jìn)，改進(jìn)后算法的基本思想是使用相對(duì)較小的滑動(dòng)窗口，選擇數(shù)據(jù)庫(kù)的一個(gè)關(guān)鍵字執(zhí)行SNM算法，存儲(chǔ)本次排序后相似記錄的序號(hào)，然后依次選擇數(shù)據(jù)庫(kù)中的其他關(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(還有沒(méi)用過(guò)的關(guān)鍵字)
??? do{
??? 為記錄集TS中的記錄選擇該趟排序需要的排序關(guān)
??? 鍵字；
??? 根據(jù)排序關(guān)鍵字對(duì)TS中的記錄進(jìn)行排序；
??? 滑動(dòng)窗口W從TS的第一個(gè)記錄開(kāi)始滑動(dòng)；
??? while(W沒(méi)有滑動(dòng)到TS的尾部)
??? do{
??? 初始化執(zhí)行對(duì)比的次數(shù)n=0；
??? while(執(zhí)行的對(duì)比次數(shù)n<|W|)
??? do{
??? 新進(jìn)入滑動(dòng)窗口的記錄與第n+1個(gè)進(jìn)入窗口的記錄進(jìn)行重復(fù)記錄比較；
??? if(比較的記錄為相似重復(fù)記錄)
??? {
??? 把相似重復(fù)記錄的記錄號(hào)添加到相似記錄存儲(chǔ)表；
??? }
??? 執(zhí)行n+1；
??? }
??? 向下滑動(dòng)窗口；
??? }
??? 對(duì)相似記錄存儲(chǔ)表中的記錄采用直觀方法進(jìn)行比較，記錄相似重復(fù)記錄聚類(lèi)；
??? }
2 識(shí)別算法" title="重復(fù)記錄識(shí)別算法">重復(fù)記錄識(shí)別算法的改進(jìn)
??? 記錄排好序后，下一個(gè)要解決的問(wèn)題是如何判斷兩條記錄是否為相似重復(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)閾值的設(shè)定仍是一個(gè)沒(méi)有解決的難題。若閾值設(shè)定的過(guò)小，則容易遺漏某些相似的重復(fù)記錄，從而降低了算法的匹配率；若閾值設(shè)定的過(guò)大，則容易將某些不同的記錄誤判為相似重復(fù)記錄，從而降低了算法的正確率。此算法對(duì)記錄的識(shí)別僅使用一個(gè)單一的閾值過(guò)于絕對(duì)，且沒(méi)有考慮文中語(yǔ)句語(yǔ)義偏后的特點(diǎn)，無(wú)法滿(mǎn)足實(shí)際情況的要求。
??? 下面針對(duì)基于相似度的重復(fù)記錄識(shí)別算法存在的上述問(wèn)題對(duì)此算法進(jìn)行了適當(dāng)改進(jìn)，給出了一種基于雙閾值^[6]位置權(quán)重^[7]的語(yǔ)義重復(fù)記錄識(shí)別算法。本算法的具體描述如下：對(duì)記錄相似度設(shè)定一大一小兩個(gè)閾值δ_up和δ_low，當(dāng)通過(guò)位置權(quán)重識(shí)別法計(jì)算出當(dāng)前兩條記錄的相似度大于δ_up，則直接判定它們是重復(fù)記錄；若計(jì)算出的相似度小于δ_low，則可以判定它們是兩個(gè)不同的記錄；而對(duì)于相似度在δ_up和δ_low之間的兩條記錄，則不能直接確定它們是否重復(fù)或不重復(fù)，需要通過(guò)語(yǔ)義重復(fù)識(shí)別法^[3],[8]進(jìn)行判定；對(duì)仍無(wú)法判定的記錄則需人工進(jìn)行處理。根據(jù)參考文獻(xiàn)[9]一般閾值取0.37和0.68，為了提高準(zhǔn)確率本文第一次相似度計(jì)算取閾值為0.35和0.7。
??? 簡(jiǎn)單的字段識(shí)別法只考慮了字段之間的字符的匹配度，而忽略了匹配字符所在的位置(稱(chēng)為匹配序)。由于大部分中文尤其是特定領(lǐng)域的專(zhuān)業(yè)術(shù)語(yǔ)的語(yǔ)義重點(diǎn)往往集中在字段的后半部分字符串中，通過(guò)調(diào)整字段的匹配度和匹配序的權(quán)重(記作α和β，滿(mǎn)足α+β=1)，則可以在很大程度上提高字段識(shí)別的準(zhǔn)確率。具體定義如下：
???

??? 其中，f₁和f₂分別為兩個(gè)中文字段(如果字段中有英文字母，則將連續(xù)的英文字母視作一個(gè)漢字)，m和n分別為f₁和f₂的字?jǐn)?shù)，c為f₁和f₂的識(shí)別字符數(shù)量，L₁(i)和L₂(i)分別為識(shí)別字符i在f₁和f₂中的匹配序。匹配序按照從左到右的順序，從1開(kāi)始自然數(shù)遞增的方式計(jì)算，而α和β則一般根據(jù)黃金分割律來(lái)確定，分別取0.6和0.4^[10]。例如，f₁=“燕大電氣工程學(xué)院”、f₂=“燕山大學(xué)電氣工程學(xué)院”，下面通過(guò)位置權(quán)重識(shí)別法判定S₁和S₂是否為重復(fù)字段。和的匹配字符為“燕”、“大”、“電”、“氣”、“工”、“程”、“學(xué)”、“院”，它們?cè)趂₁中的匹配序依次為“1、2、3、4、5、6、7、8”，在f₂中的匹配序依次為“1、3、5、6、7、8、9、10”。那么f₁和f₂的語(yǔ)義相似度為：
???
??? 基于語(yǔ)義距離的相似度識(shí)別方法體現(xiàn)了字段內(nèi)部的結(jié)構(gòu)和詞語(yǔ)之間語(yǔ)義的相互作用關(guān)系,而編輯距離由于同義詞詞林的應(yīng)用可以兼顧同義詞之間的替換,并體現(xiàn)了組成句子的每個(gè)詞深層的語(yǔ)義信息。基于語(yǔ)義距離的相似度識(shí)別算法的基本思路是：首先，利用參考文獻(xiàn)[11]中介紹的骨架依存樹(shù)思想分析字段的語(yǔ)法結(jié)構(gòu)，得到字段中所有的核心詞和直接依存于它們的有效詞組成的搭配對(duì)(有效詞定義為動(dòng)詞、名詞和形容詞，它是由分詞后的詞性標(biāo)注決定的)，然后再進(jìn)行語(yǔ)義距離(為兩個(gè)字段有效搭配對(duì)的最短距離)的相似度計(jì)算，最后根據(jù)閾值進(jìn)行重復(fù)識(shí)別判斷。
??? 設(shè)f₁和f₂為需要識(shí)別的兩字段，f₁包含的詞為f₁₁、f₁₂、…、f_1m，f₂包含的詞為f₂₁、f₂₂、…、f_2n，則詞f_1i(1≤i≤m)和f_2j(1≤j≤n)之間的相似度可用sim( f₁, f₂)來(lái)表示，這樣就得到兩個(gè)字段中任意搭配對(duì)的相似度，f₁和f₂兩字段之間的語(yǔ)義相似度sim( f₁, f₂)的計(jì)算公式如下：
???
??? 使用雙閾值位置權(quán)重的語(yǔ)義識(shí)別法，雖然在一定程度上增加了用戶(hù)的工作量，降低了算法的效率，但同時(shí)提高了算法的正確性和健壯性；而把位置權(quán)重和基于語(yǔ)義距離的相似度識(shí)別兩種方法結(jié)合起來(lái)，揚(yáng)長(zhǎng)避短、互為補(bǔ)充，根據(jù)這些特征計(jì)算字段之間的相似度，可以使本重復(fù)識(shí)別算法獲得很高的準(zhǔn)確率。通過(guò)以上分析可知，本節(jié)對(duì)重復(fù)識(shí)別算法的改進(jìn)是有效的、值得的。
3 重復(fù)記錄合并算法的改進(jìn)
??? 在相似重復(fù)記錄的識(shí)別完成以后，下一步要做的工作就是選擇合適的方法合并識(shí)別出來(lái)的相似重復(fù)記錄。參考文獻(xiàn)[8]、[12]介紹了目前常用的多種重復(fù)記錄合并方法，它們?cè)诤喜⒎矫娓饔欣?，單?dú)使用都無(wú)法得到很好的效果，下面對(duì)此進(jìn)行改進(jìn)。
??? 針對(duì)上述缺點(diǎn)，本節(jié)采用實(shí)用兼人工策略，給出了一種實(shí)用和聚類(lèi)算法結(jié)合的合并算法。從一組相似重復(fù)記錄中選擇與其它記錄匹配次數(shù)最多的一條記錄進(jìn)行保留，如果多個(gè)不同的記錄具有相同的匹配率，則對(duì)這些相似記錄進(jìn)行聚類(lèi)(會(huì)通過(guò)屏幕把聚類(lèi)結(jié)果返回給用戶(hù))，由用戶(hù)人工確定要保留的記錄，并把其他重復(fù)記錄從數(shù)據(jù)庫(kù)中刪除。
??? 針對(duì)現(xiàn)有的重復(fù)記錄清理策略存在的問(wèn)題，分析了其原因，找出了現(xiàn)有重復(fù)記錄清理策略里記錄排序、重復(fù)記錄識(shí)別、重復(fù)記錄合并各步驟中所用算法存在的缺陷，給出了各自的改進(jìn)方案，并通過(guò)算法分析和舉例說(shuō)明證明了改進(jìn)的合理性。改進(jìn)后的重復(fù)記錄清理算法可以有效地提高判斷質(zhì)量，減小誤判率，縮短了重復(fù)記錄處理時(shí)間，很好地保障了數(shù)據(jù)倉(cāng)庫(kù)數(shù)據(jù)的質(zhì)量。
參考文獻(xiàn)
[1]?LIN De Kang. An Information-theoretic Definition of Similarity[C]//Proc. Of the 15th Intermational Conf. on Machine Learning. San 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-57.
[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 Database[C].In SIGMOD Conference,1995:127-138.
[6]?洪圓，孫未未，施伯樂(lè). 一種使用雙閥值的數(shù)據(jù)倉(cāng)庫(kù)環(huán)境下重復(fù)記錄消除算法[J]. 計(jì)算機(jī)工程與應(yīng)用，2005，1:168-170.
[7]?張雪英，閭國(guó)年. 基于字面相似度的地理信息分類(lèi)體系自動(dòng)轉(zhuǎn)換方法[J].遙感學(xué)報(bào)，2008，12(3):433-440.
[8] 劉寶艷，林鴻飛，趙晶.基于改進(jìn)編輯距離和依存文法的漢語(yǔ)句子相似度計(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)代圖書(shū)情報(bào)技術(shù)，1993，2:4-7.
[11]?趙妍妍，秦兵，劉挺，等. 基于多特征融合的句子相似度計(jì)算 [A]. 全國(guó)第八屆計(jì)算語(yǔ)言學(xué)聯(lián)合學(xué)術(shù)會(huì)議(JSCL-2005)論文集[C]，2006.
[12]?DAVIDSON? S? B，? KOSKY? A? S. Specifying Database Transformations in WOL[J].Data Engineering, 1999 ,22(1):25-31.