李 莉,張曉雯

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

1 引言

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

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

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

2 近鄰排序算法 (SNM)

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

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

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

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

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

3 PSNM 算法思想

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

1)數(shù)據(jù)劃分

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

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

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

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

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

2)關鍵字選取

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

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

表1 屬性值統(tǒng)計表

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

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

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

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

表2 屬性經(jīng)驗等級表

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

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

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

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

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

3)排序

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

4)可伸縮的滑動窗口

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

如果相似度Sim(R1,RQmin)

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

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

4 實驗結果與分析

4.1 實驗環(huán)境

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

4.2 評價標準

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

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

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

4.3 實驗結果與分析

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

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

圖1 數(shù)據(jù)劃分結果圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結論

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

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