李 莉,張曉雯

(江蘇大學(xué) 計算機科學(xué)與通信工程學(xué)院,鎮(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ù)資源轉(zhuǎn)化為信息,將對做出合理的應(yīng)對決策和精確的任務(wù)計劃,甚至業(yè)務(wù)方面的收益等都有著重要的意義.社工庫中的數(shù)據(jù)采集方式有人工錄入、網(wǎng)絡(luò)爬取等,囊括了來自不同數(shù)據(jù)源的數(shù)據(jù).多數(shù)據(jù)源集成時,存在著對同一個概念有不同表示方法的問題,如同一個人可以在兩個不同的數(shù)據(jù)源有兩種不同表示[1].數(shù)據(jù)源的數(shù)據(jù)格式也較復(fù)雜,有.csv格式、.sql格式、.excel格式等.數(shù)據(jù)的完整性也存在著一定的欠缺,如數(shù)據(jù)的重復(fù)、缺失、錯誤等問題,而這將直接影響數(shù)據(jù)挖掘與分析的結(jié)果[2].因此對相似重復(fù)記錄的檢測便成了數(shù)據(jù)清洗中的一個關(guān)鍵環(huán)節(jié).

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

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

2 近鄰排序算法 (SNM)

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

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

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

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

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

3 PSNM 算法思想

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

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ù)集比較大,可重復(fù)步驟2,直到數(shù)據(jù)集劃分較為合理為止.

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

2)關(guān)鍵字選取

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

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

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

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

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

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

經(jīng)驗值設(shè)定:結(jié)合領(lǐ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)驗等級.

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

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

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

3)排序

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

4)可伸縮的滑動窗口

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

如果相似度Sim(R1,RQmin)

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

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

4 實驗結(jié)果與分析

4.1 實驗環(huán)境

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

4.2 評價標準

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

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

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

4.3 實驗結(jié)果與分析

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

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

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

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

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

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

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

接著分兩組進行實驗,分別為實驗1和實驗2.實驗1中,設(shè)置滑動窗口最小值30,最大值50;實驗2中,設(shè)置滑動窗口最小值50,最大值70.使用上述方案,在相同的實驗環(huán)境下,分別利用SNM算法、Cure算法和PSNM算法進行實驗,并對同一個數(shù)據(jù)集進行測試.測試結(jié)果均與Python Pandas庫測重結(jié)果進行對標,實驗1結(jié)果如圖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算法整體提高了相似重復(fù)記錄的召回率,提高了相似重復(fù)記錄檢測能力,解決了因字段權(quán)重分配不合理以及窗口大小不合適導(dǎo)致的部分相似重復(fù)記錄無法識別的問題.

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

實驗2的結(jié)果如圖5、圖6、圖7所示.

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

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

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

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

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

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

5 結(jié)論

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

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