一種有效檢測漢語相似重復記錄的方法文學論文
摘要：從排序屬性的選擇、匹配方法、相似度計算、檢測和處理相似重復記錄以及實驗結果幾個方面，闡述了一種有效檢測漢語相似重復記錄的方法。
關鍵詞：相似重復記錄;匹配;排序屬性
Web系統、數據挖掘系統、決策支持系統都離不開高質量的數據。由于系統所需數據常常來自不同數據源中的Web文件、各種格式文檔文件和數據庫文件，而集成這些文件中的數據極易產生包括相似重復記錄在內的各種質量問題。重復記錄是指描述同一個對象的記錄，而相似記錄是指不完全相同但相似度超過了給定閾值的記錄。產生相似重復記錄出現的原因很多，包括輸入錯誤、縮寫、計量單位不同、字符串分割錯誤、模式轉換錯誤等。相似重復記錄的存在不僅浪費系統的存儲資源，而且還會造成系統得到有偏差的、甚至是錯誤的結果。因此，檢測和消除相似重復記錄是保證系統性能的一項重要工作。檢測重復記錄的方法很多：在記錄層次，有機器學習方法、領域知識方法和基于距離的方法;在屬性層次，則有基于字符相似度、基于標記相似度、基于語音相似度和基于數值相似度等方法[1]。在大型數據庫中檢測相似重復記錄，排序—比較—處理是一個有效的方法[2]。
排序的目的是將相似或重復記錄盡可能聚集在一起，以便縮小記錄之間的比較范圍，縮短檢測時間，而用于排序的屬性一般是關鍵屬性或權重值大的屬性[3-4]。比較是檢測數據庫中相似重復記錄的過程，它需要逐個比較記錄的各個屬性，最后根據各個屬性總的匹配程度判斷兩個記錄是否是重復記錄或相似記錄。處理是對檢查出的重復記錄或相似記錄進行處理，對重復記錄一般刪除，對相似記錄則可以選擇保留、合并或刪除。在排序—比較—處理方法中，核心工作是字符串之間的匹配，無論是英文還是中文字符串，基于距離的匹配是常用方法[5-6]。
本文提出了一種新的排序—比較—處理方法，實驗結果表明，該方法的查準率和運行時間均優于目前已有的方法。
1排序屬性的選擇
檢測數據庫中的相似重復記錄時，如果不限制比較范圍，每條記錄從自己的下一條記錄開始進行比較直到最后一條記錄為止。如果數據庫有N條記錄，總共需要比較(N-1)!次。如果先排序再比較，則由于具有相同或相似屬性值的記錄聚集在相近位置，每個記錄只需要比較臨近的少量記錄，這樣可以大大降低每條記錄的比較次數。設屬性Ai值的種類分別有δi種，則用Ai排序后，記錄比較的范圍是N/δi+ε(ε<
2匹配方法
在排序屬性的選擇、記錄排序和檢測記錄是否是相似重復記錄過程中，都需要進行漢字匹配。漢字字符串匹配、比較時要考慮以下3種情況：一是省略，如“東華大學”和“上海東華大學”相比，省略了“上海”2個字;二是縮寫，如“中科大”是“中國科技大學”的縮寫;三是輸入錯誤，輸入同音、近音字或字形相似的字。
對于前兩種情況，通過查找子串算法解決;對于第三種情況，則通過查找相似漢字表解決。相似漢字表選用GB 2312—80中的常用字，按讀音對它們進行編碼，每個漢字有唯一的區位碼。而當滿足下面條件之一時，兩個漢字被認為是相似的：(1)區碼相同，位碼差值的絕對值小于8;
(2)區碼不同，但屬緊鄰的區，且位碼差值的絕對值小于8。
字符串S和T的匹配方法如下，Ω存放S和T中相同字符個數：步驟1：計算字符串長度|S|和|T|。
步驟2：如果|S|≥|T|，則指針i指向T的第1個字符，指針j指向S的第1個字符;否則相反。
步驟3：保存j的值到變量head作為下次比較開始位置。如果i和j所指字符相同，Ω加1，i和j的值加1，使其指向下一個待比較字符。如果i的值大于Min(|S|，|T)|，匹配束;如果不相同，則查詢同音字表;如果在表中的相似度等于0，則j的值增1，否則λ加1，i和j的值加1，使其指向下一個待比較字符。
步驟4：如果j的值等于Max(|S|，|T|)，則將head中的值賦給j作為下次匹配起始位置，返回步驟3。
3相似度計算
對有n個屬性的記錄M和N，它們的相似度用公式(1)計算：Sim(M，N)=α1ma(tMi，N)i+α2ma(tMj，N)j+nk=1，k≠i，jΣ1-α1-α2n-2ma(tMk，Nk)(1)(α1>0，α2>0，α1+α2<1)式(1)中，ma(tMi，N)i是記錄M和N屬性Ai的匹配值，α1,α2分別是Ai，Aj匹配結果的權重，越重要的屬性權重值越大。
屬性值匹配用公式(2)計算：
ma(tMi，N)i=Min(|Mi|，|Ni)|k=1ΣΩk(|Mi|，|Ni)|/2(2)式(2)中，|Mi|和|Ni|分別表示記錄M和N的.第i個屬性的字符個數，ΣΩ表示相同字符數。
4檢測和處理相似重復記錄
檢測相似重復記錄的步驟如下：(1)數據庫中記錄數是N，則從中抽樣εN的記錄。N越大，ε就越小，反之越大，原則是抽樣記錄要能夠比較真實地反映整體數據庫記錄的情況。
(2)統計記錄中前5個屬性值的種類數，選擇種類數最多的屬性作為第1次排序的屬性。如果Ai是第1排序屬性，則統計屬性Ai+A(jAj是其他4個屬性)值的種類數，選擇種類數最多的屬性Aj作為第2排序屬性;當屬性值的匹配值大于0.8時認為相等。
(3)先用Ai然后用Aj對數據庫排序。
(4)初始化時i指向第1個記錄。
(5)指針j指向下1個記錄。
(6)計算第i個和第j個記錄中屬性的ma(t)，如果值小于0.80，則將j+1的值賦給i，轉到步驟(5);如果大于0.80，則計算屬性Aj的ma(t);如果均值大于0.90，則繼續比較后續的屬性，最后計算Sim()，其中Ai和Aj的權重分別是0.3和0.2。如果Sim小于0.90，則將j+1的值賦給i，轉到步驟(5);如果Sim大于0.90，則認定它們是相似或重復記錄;如果Sim在0.90和0.95之間，則它們之間認定為相似記錄，將其復制到文件表中由人工判斷;如果大于0.95，則它們是重復記錄，轉向(5)。
5實驗結果
實驗環境是Pentium Dual-Core CPU，3.20 GHz，2.00 GB聯想電腦。實驗數據來源于學校圖書館搜集的漢語文獻，其中包含大約8%的相似或重復記錄。同時，實驗比較了文獻[6]中的方法一和本文提出的方法二得到的查準率和運行時間，如圖1和圖2所示。從中可以看出，本文提出的方法是有所改進的。6結語在當今信息社會，信息的來源和種類越來越多，而將信息集成到一起不可避免地會產生相似重復記錄。而如何消除相似重復記錄，是人們必須面對的問題，因此也是一個值得研究的問題。
【一種有效檢測漢語相似重復記錄的方法文學論文】相關文章：