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