基于劃分的海量數據相似重復記錄檢測①

李 莉,張曉雯

(江蘇大學 計算機科學與通信工程學院,鎮江 212013)

1 引言

隨著互聯網、移動互聯網及智能手機的快速發展,人們每時每刻都產生大量的數據,如個人登錄某網站的賬號、密碼、郵箱、分享的照片、信用卡記錄、訂的機票記錄、通話記錄等個人行為數據.而現代社會數據成為了決策者,在社工庫的海量數據中挖掘出有價值的信息,即讓數據資源轉化為信息,將對做出合理的應對決策和精確的任務計劃,甚至業務方面的收益等都有著重要的意義.社工庫中的數據采集方式有人工錄入、網絡爬取等,囊括了來自不同數據源的數據.多數據源集成時,存在著對同一個概念有不同表示方法的問題,如同一個人可以在兩個不同的數據源有兩種不同表示[1].數據源的數據格式也較復雜,有.csv格式、.sql格式、.excel格式等.數據的完整性也存在著一定的欠缺,如數據的重復、缺失、錯誤等問題,而這將直接影響數據挖掘與分析的結果[2].因此對相似重復記錄的檢測便成了數據清洗中的一個關鍵環節.

近年來,國內外學者在相似重復記錄檢測研究中取得不錯的成績,相似重復記錄清洗通過排序、相似檢測與合并/刪除,相似檢測算法是清洗的核心.利用編輯距離[3]、N-gram字符串匹配度量[4]等方法,進行相似記錄比較.利用優先權隊列算法[5]、近鄰排序算法[6]、多趟近鄰排序算法[7]等檢測相似重復記錄.針對海量數據的特點,楊巧巧等人使用網格法對海量數據進行分組,并為各屬性設立對應的權值,提高了算法的檢測效率以及準確度,但網格劃分的大小是根據經驗設定的[8],而網格劃分效果很大程度依賴于網格步長的選取,并且只對密度分布較為均勻數據進行采樣,未充分考慮不同密度的簇、噪聲和密度閾值的關系對劃分結果的影響.針對相似重復記錄檢測中記錄屬性維度過高導致的查準率和時間效率低下的問題,文獻利用信息熵,通過過濾噪聲屬性,降低屬性維度,提高了相似重復記錄檢測算法的效率[9],但隨著待檢測記錄數量的增多,算法耗時會迅速增多.在CURE算法的改進方面也取得了成就,時念云等人使用預抽樣改進代表點選擇方法,采用基于距離影響因子的代表點選取策略,既可以根據數據集的密度進行代表點的選取,又能適當選取有一定意義的邊緣點作為代表點,提高了代表點選取的合理性[10],但在預抽樣中,未考慮到相鄰樣本集可能出現交叉重復記錄的情況.在SNM算法的研究上亦取得了較大的進步.劉雅思等人使用長度過濾法對數據進行預處理,根據兩條記錄的長度比例和屬性缺失情況,排除部分不可能構成相似重復記錄的數據;進一步使用動態容錯法,校準字段相似度評判結果,解決了因屬性缺失而誤判的問題[11],但對于屬性權重的設置存在主觀性,并且未能處理文字不同而語義相似的重復記錄.Miao Li等人使用余弦相似度算法進行屬性匹配,提高匹配精度,并且采用Top-k有效權重過濾算法,選擇權值較高的Top-k個屬性進行匹配,最后計算k個相似度值和權重的總和,減少了屬性的匹配次數[12].陳爽等人使用變步長伸縮窗口,動態檢測窗口大小,減少不必要的匹配,并采用動態調整等級法,根據記錄相似度調整字段等級,通過等級法將字段等級轉換為權重,解決了人為賦予固定權重主觀性強、不準確問題[13].但文獻[12,13]均未對海量數據進行預處理,而直接采用相關改進算法檢測,未能解決海量數據相似重復檢測時間效率低下的問題.

針對SNM算法的缺點以及海量數據的特點,本文提出了一種有效的基于劃分的近鄰排序算法.算法主要步驟為:首先根據屬性對海量大數據集進行劃分,形成小數據集;然后對劃分后的小數據集,采用改進的近鄰排序算法進行清洗.提高了在海量數據庫中查找相似重復記錄的時間效率以及檢測精度.

2 近鄰排序算法 (SNM)

相似重復記錄檢測中比較有效的方法是近鄰排序算法.近鄰排序(SNM)算法的基本思路是:

1)創建排序關鍵字.抽取記錄的一個或一組屬性字符串,計算數據集中每一條記錄的鍵值.

2)排序.根據排序關鍵字對整個數據集進行排序.潛在的相似重復記錄將被調整到一個臨近的區域,從而可以將匹配限定到一定的范圍之內[11].

3)合并.在排序后的數據集上滑動一個大小為Q的窗口,窗口內的第一條數據僅與窗口內剩余的Q-1條記錄進行比較.比較結束后,最先進入窗口內的記錄滑出窗口,最后一條記錄的下一條記錄移入窗口,再把此Q條記錄作為下一輪比較對象.如此反復,直到所有記錄比較完畢[11,14].

SNM算法通過滑動窗口減少了比較次數,提高了匹配效率,算法的時間復雜度為O(QN)[12](Q為窗口大小,N為數據中的記錄總數).但是SNM存在兩個主要的缺陷,一是排序關鍵字難以選取,排序關鍵字選取的好壞不僅直接影響檢測效率,對測重結果的精度也有很大影響.二是滑動窗口大小難以設置,如果窗口過大會導致不必要的記錄比較,如果窗口過小,會出現漏配現象,降低檢測精度.

3 PSNM 算法思想

針對傳統近鄰排序(SNM)算法的缺點,PSNM算法的思想是,首先對海量數據集進行劃分,形成小數據集;其次對每個小數據集采用等級綜合評價法為屬性設置權重,以權重排序關鍵字;最后采用可伸縮的滑動窗口,進行相似重復記錄檢測.

1)數據劃分

把海量大數據集劃分為若干個不相交的小數據集.劃分方法如下:

步驟1.選取具有代表性的某個屬性,以該屬性把大數據集分割為若干個不相交的小數據集,稱為簇.記大數據集D,屬性P={p1,p2,…,pm},劃分為n個不相交的子集,D:{D1,D2,…,Dn}.

步驟2.若某些劃分后的數據集的數據量仍比較大,則對該數據集再次劃分.對數據集Di(i=1,2,…,n)再次劃分,選取屬性Pi={pi1,pi2,…,pik},依據屬性劃分為k個不相交的子集,Di:{Di1,Di2,…,Dik}.

步驟3.若仍存在某些數據集比較大,可重復步驟2,直到數據集劃分較為合理為止.

數據劃分依賴于問題的求解,為了求解的精確度,可將只選取單一屬性進行數據劃分,擴展到多屬性選取進行數據劃分.

2)關鍵字選取

為選取恰當的關鍵屬性,本文采用等級綜合評價.等級綜合評價法結合了客觀的數理統計方法和主觀的專家經驗,綜合考慮了各個屬性對記錄的貢獻程度不同[2].

數理統計方法:每個屬性都有值域.多次在數據集中隨機選取相同大小的樣本數據,統計屬性的長度,稱為屬性值.為減少隨機取樣時樣本質量差異對屬性值的影響,因此以均值法確定數據集中各屬性值,若屬性值越大,此屬性的記錄差異越大,該屬性所占權重也就越大.屬性值統計如表1所示.

表1 屬性值統計表

采用均值法確定屬性pj的屬性值Yj:

其中,Yij(1≤i≤n,1≤j≤m)表示第i次取樣第j個屬性pj的屬性長度.

將屬性值從小到大進行排序,并分別賦予屬性權重Wi(1≤i≤m),其中W1+W2+…+Wm=1.

經驗值設定:結合領域知識讓用戶根據個人經驗為各屬性進行等級分配,即為每個屬性指定經驗等級.為降低各專家經驗認知不同對屬性打分的影響,仍采用均值法就算各個屬性最終的經驗等級Gj(1≤j≤m).經驗等級表如表2所示.

表2 屬性經驗等級表

采用均值法確定屬性pj的屬性值Gj:

其中,Gij(1≤i≤n,1≤j≤m)表示第i個用戶為第j個屬性pj的分配的經驗等級.

將屬性值從小到大進行排序,并分別賦予屬性權重Wi(1≤i≤m),其中W1+W2+…+Wm=1.

根據上述分析,屬性的等級越高,其重要性越高,所對應的屬性的權重也就越大,將數理統計方法與經驗等級法相結合,計算得到最終的綜合屬性權值,公式如下[2]:

等級綜合評價法偽代碼如下:

3)排序

近鄰排序算法很大程度上依賴于排序關鍵字的選取.依據上述等級綜合評價法,首先操作數據集以屬性對應的權重W從大到小進行排序,選出前四個屬性作為數據集的排序關鍵屬性.如對特定的社工數據集,劃分為小數據集后,經上述方法最終選取“Firstname”、“Lastname”、“家庭住址”、“所在城市”四個屬性作為排序關鍵屬性,對各小數據集進行排序.

4)可伸縮的滑動窗口

傳統近鄰排序算法滑動窗口大小難以設置,窗口過大或者過小都會出現一系列的問題,從而影響最終的檢測效果,因此滑動窗口大小的設置也極為重要.本文根據窗口內記錄間的相似程度動態地調整滑動窗口大小.記窗口最大值為Qmax,窗口最小值為Qmin,當前滑動窗口大小在Qmin和Qmax之間變化,滑動窗口大小根據記錄相似度的計算值與閾值的比較進行靈活調整.可伸縮滑動窗口需設置3個參數,窗口最小值Qmin,窗口最大值Qmax,窗口最小閾值LowT,以及變量當前滑動窗口大小Qi.窗口初始值Qi設定為Qmin,窗口中的第1條記錄R1首先在Qmin范圍內與其他記錄進行匹配,當匹配到記錄RQmin時,如果相似度Sim(R1,RQmin)>LowT,說明此時窗口內記錄間相似程度較高,應擴大窗口繼續進行匹配,窗口擴大為:

如果相似度Sim(R1,RQmin)

經過多次實驗,最終確定窗口最小閾值LowT以及相似度最小閾值為0.75時效果最佳,若兩條記錄已經匹配過的屬性相似度之和大于等于相似度最小閾值0.75,即可確定為相似重復記錄,對后續屬性可不進行匹配.窗口最小閾值以及相似度最小閾值是針對本數據集進行多次實驗比較后得出的,并不具有普遍性,若對其他數據集采用該算法,還需根據查準率、召回率等對閾值進行調整.

PSNM算法根據屬性對海量數據集進行劃分,大大降低了數據量等級,提高后續的測重效率;采用等級綜合評價法為各屬性設置權重,使關鍵屬性的選取以及各屬性權重的分配更為客觀合理,提高了算法檢測重復記錄的準確性;滑動窗口大小的伸縮,使窗口大小隨窗口內記錄間的相似程度動態調整,在增強算法測重能力的同時減少了不必要的匹配,提高算法運行效率.

4 實驗結果與分析

4.1 實驗環境

實驗計算機配置:CPU Core(TM)3.40 GHz,內存16 GB,顯存 8 GB;操作系統:Windows7;軟件環境:Python2.7,MySQL5.7.

4.2 評價標準

衡量相似重復記錄檢測算法的性能指標通常用查準率(precision)、召回率(recall)和平均數F值來加以描述.查準率是指正確識別的相似重復記錄與實際的相似重復記錄的比值,查準率越高,表明該算法識別相似重復記錄精度越高.召回率是指相似重復記錄被正確識別的百分率,召回率越高,表明該算法識別相似重復記錄的能力越強.查準率和召回率定義如下:

其中,tp表示正確識別的相似重復記錄數,fp表示錯誤識別的相似重復記錄數,fn表示未識別的相似重復記錄數[15].

由于precision和recall有時會出現矛盾的情況,因此采用求它們的調和平均數F值的方法,來綜合考慮算法的性能,F值越高表明該算法的綜合性能越高.F值的定義如下:

4.3 實驗結果與分析

本實驗數據為非洲地區人口社工數據,其中包含:姓名,性別,家庭住址,所在城市,所在州編號,電話號碼,郵箱,密碼,受教育等級,工作等級等 24 個屬性.分析數據源,不同地區同名同姓同地址的兩條記錄有可能是相似重復記錄,而相同地區同名同姓同地址的兩條記錄有極大的可能是相似重復記錄.因此選擇“所在州編號”屬性對大數據集進行劃分有重大意義.將大數據集D按照屬性“所在州編號”分割形成相應的簇,劃分成了{D1,D2,…,D69}69 個小數據集.再對{D1,D2,…,D69}各個小數據集進行相似重復記錄的檢測.

選取2.5萬條數據按照其“所在州編號”屬性進行劃分,結果如圖1所示.

圖1 數據劃分結果圖

觀察圖1可知,通過劃分將大數據集劃分成了各個有意義的簇,而在各個簇中,僅有一個簇中的數據量是大于五千的.這一操作將萬級數據量瞬間轉化為千級,并且對于簇中僅有一條數據的簇,不需要對其進行檢測,只需要檢測簇中數據量大于等于2的簇.這大大提高了后續算法檢測的檢測效率.

分別選取其中5000條、1萬條、1.5萬條、2萬條、2.5萬條數據作為測試集,首先根據“所在州編號”屬性對其進行劃分,選取“Firstname”、“Lastname”、“家庭住址”、“所在城市”四個屬性作為排序關鍵字,對小數據集進行排序,這四個屬性的權重經過計算分別為:0.0552,0.0448,0.0366,0.0301,其他屬性權重這里就不加以贅述了.為本文提出的基于劃分的近鄰排序算法(PSNM算法)設置滑動窗口最小值為50,最大值為70,窗口最小閾值為0.75,相似度最小閾值為0.75.而傳統SNM算法也選取“Firstname”、“Lastname”、“家庭住址”、“所在城市”四個屬性作為排序關鍵字,對記錄進行排序,設置固定窗口大小為50,相似度最小閾值為0.75.各算法在選取不同數據量時的運行時間對比如表3所示.

表3 各算法運行時間對比 (單位:s)

由表3可以看出,在排序關鍵字選取相同的情況下,PSNM算法的運行效率是高于其他算法的,這是由于PSNM算法首先對數據進行了劃分,大大降低了數據量等級,并且滑動窗口的使用和屬性權值的設置,也能減少記錄間不必要的匹配,節省了相似重復記錄的檢測時間,提高了算法效率.

接著分兩組進行實驗,分別為實驗1和實驗2.實驗1中,設置滑動窗口最小值30,最大值50;實驗2中,設置滑動窗口最小值50,最大值70.使用上述方案,在相同的實驗環境下,分別利用SNM算法、Cure算法和PSNM算法進行實驗,并對同一個數據集進行測試.測試結果均與Python Pandas庫測重結果進行對標,實驗1結果如圖2至圖4所示.

圖2 實驗1中SNM與PSNM算法的查準率對比

圖3 實驗1中SNM與PSNM算法的召回率對比

圖4 實驗1中SNM與PSNM算法的F值比對

從圖2可以看出,PSNM算法的查準率始終高于SNM算法和Cure算法.但是隨著數據量的增大,兩個算法的查準率之間的差距逐漸縮小,這主要是因為隨著數據量的增加,滑動窗口最大值50已與記錄不適配,因此PSNM算法的查準率與SNM算法趨近.

從圖3可以看出,PSNM算法整體提高了相似重復記錄的召回率,提高了相似重復記錄檢測能力,解決了因字段權重分配不合理以及窗口大小不合適導致的部分相似重復記錄無法識別的問題.

從圖4可以看出,PSNM算法的綜合性能指標F也優于SNM算法和Cure算法,說明PSNM算法整體性能得到了提升.

實驗2的結果如圖5、圖6、圖7所示.

圖5 實驗2中SNM與PSNM算法的查準率比對

圖6 實驗2中SNM與PSNM算法的召回率對比

圖7 實驗2中SNM與PSNM算法的F值對比

從圖5可以看出,窗口初始大小設置為50后,PSNM算法的查準率仍優于SNM算法.由實際數據可知,窗口大小為50時,很多記錄之間的比較是沒有必要的,這時PSNM算法能動態調整窗口大小,減少將非相似重復記錄誤認為相似重復記錄的情況,提高了算法的檢測精度.

從圖6可以看出,此時窗口初始值50比較大,基本能囊括所有的相似重復記錄,在所有數據集上,PSNM算法召回率均高于SNM算法.隨著數據量的逐漸增大,PSNM算法召回率波動并不大且基本維持在0.75～0.85之間,而SNM算法的召回率卻存在極大的波動且召回效果并不佳.

從圖7可以看出,當數據量增加時,PSNM算法的F值始終是高于SNM算法和Cure算法的,這說明了PSNM算法提高了整體性能.

5 結論

為提高被挖掘數據源的數據質量,消除數據源中的相似重復記錄是數據清洗研究中的一個熱門課題.本文在分析了傳統SNM算法的基礎上,提出了三點改進:(1)對大數據集進行劃分;(2)綜合等級法選取排序關鍵字;(3)滑動窗口大小可伸縮.由于社工庫數據量龐大,因此先運用劃分的思想,將大數據集分割為小數據集,在各個小數據集中進行相似重復記錄檢測.最后通過實驗驗證,PSNM算法不僅在時間效率方面有所提升,并且在查準率、召回率、綜合性能都優于原算法以及其他算法.

雖然數據劃分提高了海量數據重復記錄檢測的時間效率,但在劃分過程中還會出現把相似記錄劃分到不同小數據集的情況,從而造成相似重復記錄的漏判,因此數據劃分技術還有待提高.并且受到實驗環境的制約,本文僅處理了以二維表形式存儲結構化的社工源數據,并且在形成的海量數據集中僅選取部分數據進行檢測.下一步工作,要繼續處理非結構化數據以及將數據量繼續擴大.