相似重復記錄檢測的特征優選策略探究

楊家娥

摘 要：信息時代的來臨，對大數據的檢測和識別提出更高的要求，如檢測精度更高和檢測代價低廉。而傳統的重復記錄檢測方法其特征屬性繁多，數據源組成更為繁瑣，導致檢測精度不足和檢測代價高昂問題的出現。為此，本文探索分析了相似重復記錄檢測的特征優選方案，從分組模糊聚類的原理出發，對相似重復幾率的組內計算方法進行剖析，探究其在大數據集中檢測精度和識別認識方面的優勢。

關鍵詞：特征優選；相似重復記錄；模糊聚類；相似度；策略

依據相關的研究文獻，可以發現傳統重復記錄檢測方法基于排序和組合的思想，對大數據進行識別和檢測，如優先隊列技術、兩字符串距離指標計算技術、數據清洗識別技術、滑動窗口技術等。所有這些重復記錄檢測技術的原理基本一致，在實際應用中存在檢測精度不足且實施檢測的成本高昂。如優先隊列技術在應用過程中篩選具有代表性的記錄能力不足；滑動窗口技術是基于相似重復記錄的傳遞性基礎上導致檢測精確度不足等等。面對傳統相似重復記錄檢測方法的不足和漏洞，一種的新的基于分組模糊聚類的記錄特征屬性優選方法表現出其具有非常強的優勢和彌補性。此種方法基于模糊聚類壓縮記錄的基礎上，對組內具有代表性的記錄進行篩選，利用組內相似度比較的算法對重復記錄進行有效的檢測和識別。這一理論具有完善的基礎理論體系，利用先進的理論分析方法和精確的設計思路，在實踐應用中表現出高檢測精確度和低檢測成本的優勢。

1 特征優選的分組聚類的實現過程

1.1 記錄分組與組內記錄屬性處理過程

就目前的相關研究而言，關鍵字屬性排序分組方法已經成為幾率分組和聚集的應用最為多的方法，這也是相似重復記錄檢測的初始步驟。關鍵字屬性排序分組方法對記錄的屬性值進行分割，形成大小適中的原字串，然后對每一個原子串進行數字化編碼，以正序和逆序編碼排序為原則，利用關鍵屬性對記錄進行排序，然后將具有相同的正序和逆序排列合并為一組。以此減少記錄分組過程中的誤差或者錯誤的出現，如在關鍵屬性輸入錯誤的情況下，正序和逆序排列可能存在不一致性，導致記錄分組不在同一組別內。

1.2 大數據集組內屬性的處理

1.2.1 組內無關屬性的處理方法

大數據集組內屬性受特征屬性的影響，特征屬性越典型，分組越精確，越不典型，分組誤差越大。因此，對組內每個記錄進行處理時，應確保每一個維度上的特征屬性值都呈現高斯分布，將記錄的特征屬性值聚集在均值附近，以此減少偏差。特征屬性值越是聚集于均值附近，說明其越典型；反之則代表誤差過大，對分組越不利，即屬于分組無關的屬性。其衡量標準可以用下式驗證：

某一維屬性值同其均值偏差的表示方式，即其屬性方差：

其中 —— 代表第j維屬性的均值，P代表記錄的屬性維數。

1.2.2 組間特征屬性處理

所謂的典型特征的選擇，也即是對存在于組內的且對分組無關的屬性進行刪除。這一選擇過程也即是組間特征屬性的處理過程。在記錄檢測過程中，對記錄集中最優的特征屬性進行選取，避免因存在大量的相關屬性而影響記錄分組的精確度，降低重復記錄檢測的可分性。為此，組間特征屬性的處理可以利用算法進行處理。首先對特征屬性的數目進行自動確定，利用組間特征屬性之間的距離和相似矢量對其相似性進行處理。其次，借助聚類分析的方法，利用FCM對自動確定的特征屬性進行壓縮，其中FCM的算法如下：

其中FCM表示模糊C均值聚類算法，c=q。

對具有相似性的特征屬性的維度進行壓縮，有利于篩選出組內最具有代表性的記錄，提高了相似重復記錄的識別精度。

2 組內相似重復記錄的檢測

在組內具有代表性記錄獲取之后，檢測重復記錄成為最關鍵性的工作。基于分組模糊聚類的相似度計算方法，可以對實際的記錄組內的每個屬性值進行分割，每一個屬性值的集合其元素則是由分割而得到的原子串。在進行原子串分割、集合、編碼過程中，可充分利用中、西方文字進行混合使用，從而最大程度的降低因記錄輸入而出現的拼寫或者所寫錯誤，避免其對重復記錄檢測的影響。利用算法對不同記錄的相似度進行檢測，刪除超過閾值的幾率，最后檢測出記錄較為集中的記錄。其應用到的算法如下：

其中 中 表示是原子串a與 原子串匹配的分值， 介于0到1之間。 的屬性長度為 ，其數量為m。

通過分析，我們了解到基于分組模糊聚類的相似重復記錄檢測的特征優選方案，相比于傳統的排列和合并檢測方法具擁有檢測精度高、實施檢測成本低的特征。新的特征優選方案對組間和組內的特征屬性進行分組壓縮，降低其屬性的維數，一方面利用FCM方法自動確定特征屬性的數量，最后將具有代表性的記錄與其他記錄進行比較，從而大大提高檢測的精度。

[參考文獻]

[1]宏圓，孫未未，施伯樂.一種使用雙閾值的數據倉庫環境下重復記錄消除算法[J].計算機工程與應用，2005.41（1）：168—171.

[2]李星毅，包從劍，施化吉.數據倉庫中的相似重復記錄檢測方法[J].電子科技大學學報，2007，36（6）：1273-1277.