袁 滿穆永豪王貴友于再富

(1.東北石油大學(xué) 計算機與信息技術(shù)學(xué)院,黑龍江 大慶 163318;2.黑龍江省大慶市第十采油廠肇東分公司 信息中心,黑龍江大慶 163000)

0 引 言

隨著大數(shù)據(jù)時代的到來,企業(yè)由IT時代進入DT時代,數(shù)據(jù)在企業(yè)發(fā)展中將扮演越來越重要的角色[1]。然而隨著大數(shù)據(jù)的爆炸式增長,劣質(zhì)數(shù)據(jù)也隨之而來,導(dǎo)致數(shù)據(jù)質(zhì)量低劣,極大降低了數(shù)據(jù)的可用性[2]。這些低劣“臟數(shù)據(jù)”的產(chǎn)生使這些數(shù)據(jù)質(zhì)量問題會直接導(dǎo)致計算偏差,造成難以想象的后果[3]。其中,數(shù)據(jù)庫中重復(fù)記錄占用了大量的空間,直接影響數(shù)據(jù)庫的使用效率[4],企業(yè)需要利用大量的數(shù)據(jù)進行某些結(jié)果的預(yù)測,但由于相似重復(fù)記錄的存在,導(dǎo)致預(yù)測結(jié)果產(chǎn)生偏差,給企業(yè)決策造成很大困難。因此,如何消除數(shù)據(jù)冗余,保證數(shù)據(jù)庫中高質(zhì)量數(shù)據(jù)的使用成為人們面臨的巨大挑戰(zhàn)。

關(guān)于重復(fù)記錄的定義,Monge[5]提出將同一實體對象對應(yīng)的多條記錄稱之為相似重復(fù)記錄。Lillibridge等[6]提出數(shù)據(jù)庫中存在這樣的兩條記錄R1、R2,其內(nèi)容相同或相似,且都對應(yīng)著同一個現(xiàn)實實體,則記錄對〈R1,R2〉互為相似重復(fù)記錄。李軍[7]提出在同一個數(shù)據(jù)庫系統(tǒng)中,如果出現(xiàn)兩條或兩條以上的記錄,它們之間出現(xiàn)足夠多的相同或相似的屬性值,即可認定其為相似重復(fù)記錄。潘瑋等[8]認為重復(fù)記錄是指原始數(shù)據(jù)中同一文獻產(chǎn)生的多條相同記錄,其特點是各記錄的所有字段均相同。陳亮等[9]認為相似重復(fù)記錄檢測就是識別一對是否表示為真實世界中的同一個實體。目前對于數(shù)據(jù)庫中存在的英文重復(fù)數(shù)據(jù)記錄清洗已經(jīng)形成一套完整的體系,可以利用多種算法對其進行檢測和清洗,但對中文重復(fù)記錄清洗的研究在國內(nèi)還處于初步階段,并且對中文的重復(fù)記錄數(shù)據(jù)清洗的算法積累還比較欠缺。造成這種現(xiàn)象主要原因是由于中英文本身表達、語法和語義等存在的差異和國情差距,所以對中文數(shù)據(jù)清洗的研究成果報道很少[10]。因此筆者在SNM(Sorted-Neighborhood Method)算法的基礎(chǔ)上對中文的重復(fù)記錄檢測進行了更深一步的研究。SNM算法在英文重復(fù)記錄清洗中的高效性主要是因為英文的語義和時態(tài)是基于單詞[11]。但在中文中重復(fù)記錄數(shù)據(jù)主要是以中文詞語為單位,與此同時中文單詞多會出現(xiàn)同一個實體以不同形式進行表達,這也就成為了中英文數(shù)據(jù)清洗的本質(zhì)原因。為此筆者在傳統(tǒng)的SNM算法基礎(chǔ)上對其加以改進,引入《同義詞詞林擴展版》標準詞匯集對中文字段的詞語進行相似度計算。同時引入Jieba分詞對語句進行分詞處理,以保證句子的語義有效性,進而利用余弦相似度計算語句相似度,提高中文重復(fù)記錄檢測的準確性。

1 相似重復(fù)記錄檢測相關(guān)技術(shù)研究

1.1 相似重復(fù)記錄檢測相關(guān)算法研究

目前對英文相似重復(fù)記錄檢測的算法已經(jīng)有了很多成果,例如多趟鄰近排序算法,PSNM(Partitionbased Sorted-Neighborhood Method)算法,聚類算法,優(yōu)先隊列算法等。Monge等[12]在鄰近排序算法(SNM)的基礎(chǔ)上提出了多趟鄰近排序算法,該算法的基本思想是對SNM算法獨立的執(zhí)行多次,然后再選取不同關(guān)鍵字對每次的檢測進行排序,通過本次排序使沒能排在同一個窗口的相似重復(fù)記錄能重新選取關(guān)鍵字再次匹配檢測,最后進行合并刪除重復(fù)記錄數(shù)據(jù)。進而達到全部記錄相似重復(fù)檢測的目的。PSNM算法通過將整體的數(shù)據(jù)集劃分成小數(shù)據(jù)集,并對每個小數(shù)據(jù)集內(nèi)部采用等級綜合評價法為屬性設(shè)置權(quán)重,以權(quán)重為關(guān)鍵字,最后采用滑動窗口的方式進行檢測[13]。劉齊銳[14]通過利用聚類算法進行相似重復(fù)記錄檢測,因為聚類算法能通過無監(jiān)督學(xué)習(xí)和迭代計算將相似重復(fù)記錄數(shù)據(jù)放在同一個集合中。這使同類的數(shù)據(jù)相似度比較高,不同類間的數(shù)據(jù)差異就比較大。優(yōu)先隊列算法將隊列中的數(shù)據(jù)元素作為比對記錄,然后按照順序?qū)?shù)據(jù)庫中的記錄進行匹配,如果記錄為隊列中的元素,則對兩條記錄進行比較,檢測出重復(fù)的記錄,否則將該記錄加入一個新的簇,并進入優(yōu)先隊列,且具有最高優(yōu)先級[15],但單趟優(yōu)先隊列算法容易漏掉一些數(shù)據(jù)。綜上所述,這幾種常見的相似重復(fù)記錄檢測算法都各有其適用的范圍,具體優(yōu)勢和不足如表1所示。

表1 重復(fù)記錄清洗算法優(yōu)缺點比較Tab.1 Comparison of advantages and disadvantages of duplicate record cleaning algorithms

1.2 詞語及句子相似度度量研究

《同義詞詞林》是由梅家駒等[16]編篆而成,這本詞典最初版本中包含了不止一個詞語的同義詞,同時也包含了一定數(shù)量的相關(guān)詞。之后由哈工大信息檢索研究室利用眾多詞語相關(guān)資源,更新修改后并發(fā)布《哈工大信息檢索研究室同義詞詞林擴展版》。同義詞詞林擴展版共收錄詞語7萬多條,這些詞語被分為12個大類,94個中類,1 428個小類,小類下方進一步劃分為詞群和原子詞群兩級[17]。這使同義詞詞林擴展版具有5層結(jié)構(gòu),如圖1所示。隨著級別的遞增,同一行的詞語語義更加相近,相關(guān)性也越來越強。

圖1 同義詞詞林5層結(jié)構(gòu)Fig.1 The five-tier structure of synonyms cilin

《同義詞詞林擴展版》編碼方式是由5層編碼實現(xiàn)的,編碼規(guī)則如表2所示,第1層主要用大寫字母表示;第2層用小寫的英文字母表示;第3層則是用二位的十進制整數(shù)表示;第4層使用大寫英文字母表示;第5層用二位十進制整數(shù)表示。例如:“Aa05B01=別人 旁人 他人 人家”,“Aa05B01=”是編碼,“別人 旁人 他人 人家”是這個類的詞語。其中第8個的編碼有3種,“=”代表的是“相等”,屬于同義詞;“#”代表的是“不等”,屬于相關(guān)詞語;“@”代表的是“獨立”,既沒有相關(guān)詞也沒有同義詞。

表2 詞語編碼表Tab.2 The table of code of word

Jieba分詞是目前應(yīng)用比較廣泛的一種分詞工具,是基于Python的一個第三方分詞庫。Jieba分詞采用動態(tài)規(guī)劃查找最大概率路徑,找出基于詞頻的最大切分組合;對于未登錄詞,采用了基于漢字成詞能力的HMM(Hidden Markov Model)模型,使用了Viterbi算法。Jieba分詞主要包含3種分詞模式:全模式、精確模式和搜索引擎模式。全模式是盡可能將語句屬性中的詞語全部切分;精確模式主要是對語句進行準確切分詞;搜索引擎模式,是在精確模式基礎(chǔ)上對長詞進行深度切分,從而得到比精確模式更多的詞。

余弦相似度是目前比較主流的一種文本語義相似度計算方法,通過將詞組進行分詞,然后將分出的詞組全部列出,將所出現(xiàn)的詞組進行詞頻統(tǒng)計,通過統(tǒng)計出的詞頻對詞組進行向量化處理,最后利用余弦相似度計算公式將兩個詞組進行相似度計算,最后得出兩個詞組之間的文本相似度。

2 SNM算法

SNM算法是目前數(shù)據(jù)清洗各類算法中針對英文字段相似重復(fù)記錄應(yīng)用比較成熟的算法之一,其中主要包括如下3個步驟。

1)排序關(guān)鍵字的選取。首先從數(shù)據(jù)表中提取關(guān)鍵的屬性或?qū)傩缘慕M合對記錄進行劃分,并且其劃分時具有很強的區(qū)分度[18]。

2)關(guān)鍵字排序。按照選取的關(guān)鍵字對數(shù)據(jù)庫中所有的數(shù)據(jù)進行排序,將數(shù)據(jù)庫中不同位置但關(guān)鍵字相同的相似重復(fù)的記錄分配到相鄰的位置[19]。

3)重復(fù)記錄檢測及合并,為數(shù)據(jù)集設(shè)定一個大小可滑動的窗口[7]。將最后一個滑入窗口的記錄數(shù)據(jù)與窗口內(nèi)的其他記錄數(shù)據(jù)進行比較,判定兩條記錄是否完全相同。如果相同則將兩條記錄判定為相似重復(fù)記錄,并將這兩條記錄進行合并;如果不同,就將窗口向后滑動?；瑒哟翱趦?nèi)的記錄是采用先進先出的方式進行組織,比較后的數(shù)據(jù)則滑向下一條記錄的位置,再進行新的檢測,直至滑動最后一個數(shù)據(jù)記錄。算法圖如圖2所示。

圖2 SNM算法示意圖Fig.2 Schematic diagram of SNM algorithm

SNM算法極大地提高了英文字段的匹配效率,另外,采用滑動窗口極大地減少了記錄比較的次數(shù),提高了比較速度,縮短了匹配時間[19]。但也有如下缺陷。1)關(guān)鍵字的選取。因為關(guān)鍵字是直接影響整個數(shù)據(jù)集的排序結(jié)果,關(guān)鍵字選取的好壞不僅影響檢測效率,而且對相似性檢測的精度也有很大影響,如果選取不當(dāng),還有可能漏掉一些重復(fù)記錄[7]。2)對滑動窗口大小的選擇。當(dāng)滑動窗口過大時,會導(dǎo)致檢測效率過低,但如果滑動窗口選擇較小,則容易導(dǎo)致在匹配過程中漏掉一些重復(fù)記錄,因此對確定的數(shù)據(jù)集,很難選擇合適的窗口進行檢測。3)因為滑動窗口內(nèi)部記錄比較采用笛卡爾乘積的方式進行字段比較,極大地增加了記錄的比對時間,導(dǎo)致檢測時間過長。

3 系統(tǒng)架構(gòu)和改進的SNM算法

3.1 改進的中文重復(fù)記錄檢測模型

針對上述SNM算法的不足,筆者提出基于改進的SNM算法中文重復(fù)記錄檢測模型,該模型主要包含讀取數(shù)據(jù),數(shù)據(jù)預(yù)處理,數(shù)據(jù)檢測以及結(jié)果統(tǒng)計4部分。具體模型整體架構(gòu)如圖3所示。

圖3 改進的中文重復(fù)記錄檢測模型Fig.3 Improved Chinese duplicate record detection model

數(shù)據(jù)讀取。將獲取的數(shù)據(jù)存放入相應(yīng)運行的數(shù)據(jù)庫中。

數(shù)據(jù)預(yù)處理。首先是對關(guān)鍵字的處理,由于在SNM算法中關(guān)鍵字的選定對SNM算法排序的影響很大,因此在同一關(guān)鍵字記錄滑入窗口前,對同一屬性的關(guān)鍵字進行排序處理,以增強數(shù)據(jù)庫中數(shù)據(jù)排序結(jié)果的單一性[20]。然后將同一關(guān)鍵字記錄滑入檢測的窗口。

根據(jù)輸入的數(shù)據(jù)記錄進行屬性值判斷。如果是詞語屬性,判斷該詞是否在《同義詞詞林擴展版》中,如果在,則使用同義詞詞林算法對兩組詞語進行相似度檢測;如果不在,則使用Jaccard算法進行檢測。如果為語句屬性值則利用余弦相似度對其進行檢測。

對測試的語句相似度和詞語相似度取平均值,根據(jù)設(shè)定閾值判斷兩條記錄是否屬于重復(fù)記錄。如果匹配度超過設(shè)定閾值則將這兩條記錄進行合并;如果兩條記錄相似度小于閾值則判定為非重復(fù)記錄,同時將檢測后的單一數(shù)據(jù)集也放入結(jié)果集。

3.2 相關(guān)定義

改進后的算法具體處理過程是先將記錄按照屬性創(chuàng)建關(guān)鍵字,然后對關(guān)鍵字排序,把關(guān)鍵字相同的記錄聚集在一起,然后對比窗口內(nèi)部記錄,通過判斷比較后的兩條記錄之間的相似度值,從而找出相似重復(fù)記錄。為了方便描述改進的算法,給出如下定義:

定義1 設(shè)數(shù)據(jù)集R={r1,r2,…,r L},L為記錄的總數(shù),Ri為數(shù)據(jù)記錄集R的第i個記錄,1≤i≤L。

定義2 Sim(Ri,Rj)為記錄Ri和Rj的相似程度即就是兩個記錄之間的相似度,1≤i≤L,1≤j≤L,如果兩條記錄完全相同,則相似度為1。

定義3 設(shè)Ssim1為余弦相似度計算結(jié)果,其中X i與Y i為兩條語句分詞后向量化的結(jié)果向量。

定義4 設(shè)Ssim2為Jaccard算法計算結(jié)果,其中A和B分別為兩組詞語向量化后的結(jié)果向量。

定義5 設(shè)置閾值U,如果相似度大于U,則說明Ri和Rj相似重復(fù)。

定義6 設(shè)Q為查全率。設(shè)T為測試數(shù)據(jù)集中人為插入的相似重復(fù)記錄的實際條數(shù),C為實際檢測出正確的相似重復(fù)記錄條數(shù),則有Q=C/T。Q的值域為[0,1],求得的Q值越大,則表明檢測算法的查全性能越高[7]。

定義7 設(shè)P為查準率。設(shè)F為檢測算法檢測出正確的相似重復(fù)記錄條數(shù),則P=F/C,P越高,算法判別的準確性越高。

3.3 SNM改進算法

根據(jù)上述對SNM算法的描述得知要判斷兩條記錄是否為相似重復(fù)記錄,就是通過判定兩條記錄之間的相似度是否超過設(shè)定的閾值U。在改進的過程中,將主鍵作為關(guān)鍵字對整個加載的記錄進行排序。下面對整個改進后的SNM算法步驟進行詳述。

1)將所有將要進行檢測的數(shù)據(jù)記錄進行導(dǎo)入。

2)排序關(guān)鍵字選取,對數(shù)據(jù)庫中全部數(shù)據(jù)記錄進行排序,排序后所有關(guān)鍵字相同的屬性記錄基本上能聚類到一起,以便后期在窗口內(nèi)對排序后的鄰近記錄進行檢測。

3)將數(shù)據(jù)記錄放入伸縮滑動窗口中進行檢測,每次滑動記錄都是將關(guān)鍵字相同的記錄滑動進入同一窗口進行遍歷檢測。

4)在記錄比對過程中,利用《同義詞詞林》對相應(yīng)的詞語屬性進行相似度比對,計算出屬性中存在于同義詞詞林中的詞組相似度值,若不存在于同義詞詞林中則將新的詞組利用Jaccard算法進行計算相似度值。對屬性為語句的記錄,首先,利用Jieba分詞對語句屬性值進行分詞處理,將得到的分詞進行詞頻統(tǒng)計,通過統(tǒng)計結(jié)果對兩條語句記錄進行向量化,最后利用余弦相似度對語句屬性進行相似度計算得出兩條記錄相似度。

5)設(shè)定具體的閾值U,如果兩條記錄的相似度等于1,則判定兩條記錄為重復(fù)記錄;如果不等于1,則將兩條記錄進行細化比對。若匹配度超過設(shè)定閾值則將這兩條記錄判定為重復(fù);若兩條記錄相似度小于閾值U則判定為非重復(fù)記錄,將兩條記錄放入設(shè)定的總數(shù)據(jù)集,同時將檢測后的單一數(shù)據(jù)集也放入總數(shù)據(jù)集。

算法1 讀取數(shù)據(jù)集Data,并對數(shù)據(jù)集進行排序。利用余弦相似度算法,詞林相似度算法,Jaccard算法分別對語句和詞語進行相似度計算,通過合并的兩條記錄相似度計算值判斷兩條記錄是否屬于重復(fù)記錄,最終輸出統(tǒng)計后的重復(fù)記錄數(shù)據(jù)條數(shù)Count。改進的SNM算法偽代碼如下:

Input(Data);

Sort(Data,Key);

SimCount[]=Findsim(Data)∥相同關(guān)鍵字數(shù)據(jù)條目數(shù)量數(shù)組

Count←0;∥記錄重復(fù)記錄對數(shù)

i←0;∥數(shù)據(jù)條數(shù)循環(huán)變量

num←0;∥相同關(guān)鍵字條目變量

Whilei

forj←0 toj

fork←j+1 tok

YX=YuXianSim(Data[2].get(j),Data[2].get(k));

if(CiLin.Include(Data[1].get(j)and CiLin.Include(Data[1].get(k))//判斷兩個詞組是否在詞林中

else do

JC=JCSim(Data[1].get(j),Data[1].get(k));//采用JC相似度計算

if((YX+JC)/2>U)

Count++;

end if

end if

end for

Output(count);

end

算法2 余弦相似度算法。輸入兩條語句值,通過利用Jieba分詞將語句進行劃分,統(tǒng)計兩條語句中所有詞,計算詞頻,利用余弦相似度公式計算兩條語句相似度,最終輸出兩條語句相似度值。算法偽代碼如下:

Input(S1,S2);∥讀取兩條語句

S1_cut←Jieba.cut(S1);

S2_cut←Jieba.cut(S2);∥對兩條語句分詞

All_word←set(S1_cut+S2_cut);∥統(tǒng)計所有詞

計算詞頻;

公式1;∥兩條語句計算相似度;

Output(sim1);

算法3 詞林相似度算法。輸入兩個詞語屬性值,利用《同義詞詞林》詞匯集查找兩個詞的編碼,根據(jù)編碼計算兩個詞語的相似度。算法偽代碼如下:

Input(X1,X2);∥讀取兩個詞語

code1←cilin.word[X1];

code2←cilin.word[X1];∥獲取兩個詞的編碼

獲取兩個詞的層級信息;

if(code1.end()==‘@’or code2.end()==‘@’):∥如果連個詞編碼以@結(jié)尾詞語為獨立的;

fori←1 toi<9 do

獲取兩個編碼公共部分;

判斷兩個編碼層級是否相同;

計算兩個編碼之間相似度;

Output(sim1);

end for

end if

算法4 Jaccard算法。輸入兩個詞語屬性值似度值,輸出相似度。算法偽代碼如下:

Input(A,B);∥讀取兩個詞語

corpus←[A,B];∥獲取兩個詞語編碼

公式2;∥計算兩個詞語相似度;

Output(sim);∥輸出兩條詞語相似度

4 實驗結(jié)果驗證及分析

實驗基于相同實驗環(huán)境下利用SNM算法以及改進后的SNM算法對同一測試數(shù)據(jù)集進行相似重復(fù)記錄檢測。實驗數(shù)據(jù)取自某輔導(dǎo)機構(gòu)部分學(xué)生學(xué)習(xí)信息數(shù)據(jù)集。該數(shù)據(jù)集共有1 083條數(shù)據(jù)記錄,其中插入210條相似重復(fù)記錄數(shù)據(jù)。數(shù)據(jù)表中主要包含姓名,聽寫詞語以及詞語釋義屬性。通過人工方式統(tǒng)計檢測并利用不同閾值對兩種算法的影響,以比較兩種算法的查全率和查準率。

實驗配置:CPU 2.62 GHz,4 GByte內(nèi)存,500 GByte硬盤;操作系統(tǒng):Windows10;軟件:MySQL+Python3.6。

一般對相似重復(fù)記錄算法的衡量主要依靠查全率和查準率兩個性能指標。通過利用不同算法在實驗條件相同的情況下對同一數(shù)據(jù)集進行對比實驗,得到結(jié)果如圖4和圖5所示。圖4給出了在不同閾值的設(shè)定下得到的SNM算法及改進后算法的查全率,圖5給出了在不同閾值設(shè)定下得到的SNM算法及改進后算法的查準率。

圖4 查全率結(jié)果分析圖Fig.4 Analysis chart of recall results

圖5 查準率結(jié)果分析圖Fig.5 Analysis chart of precision results

通過圖4可以看出,在閾值相同的情況下改進后算法的查全率Q高于傳統(tǒng)SNM算法。同時隨著閾值設(shè)定越高,兩種算法的查全率隨之降低。

通過圖5可以看出,改進后算法的查準率P雖然在某些情況下可能對于相似重復(fù)記錄的檢測比較低,但整體查準率高于傳統(tǒng)SNM算法的查準率,這也證明了改進后的算法更適合普遍的中文文本數(shù)據(jù)重復(fù)清洗。

5 結(jié) 語

在傳統(tǒng)數(shù)據(jù)庫中,一般存放著大量的數(shù)據(jù)記錄,很多數(shù)據(jù)由于某些人為原因,使這些記錄構(gòu)成了相似重復(fù)記錄。目前現(xiàn)有的一些算法雖然可以對部分的英文相似重復(fù)記錄進行檢測,但對中文數(shù)據(jù)的檢測還是有些欠缺。筆者在已有的SNM算法基礎(chǔ)上融合了《同義詞詞林擴展版》以及Python中的Jieba分詞對其進行改進,并通過對最后閾值的調(diào)節(jié)對同一數(shù)據(jù)集進行實驗判定,并得到如下結(jié)論,不同閾值的設(shè)定對相似重復(fù)記錄有很大影響,如果要得到合適的結(jié)果需要對閾值的調(diào)節(jié)有一個合適的調(diào)控度。綜上所述,筆者提出的算法在對中文數(shù)據(jù)清洗時獲得了較好的效果。但還存在如下不足,由于數(shù)據(jù)集的數(shù)量較少,可能掩蓋了改進算法的某些缺點,在遇到較大的數(shù)據(jù)集時可能執(zhí)行效果較差,這也是未來工作中要解決的問題。