基于動(dòng)態(tài)雙重前綴的模糊相似性連接算法

于長(zhǎng)永, 王雯函, 溫秀靜, 趙宇海

(東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 遼寧 沈陽 110169)

相似性查找和相似性連接是數(shù)據(jù)庫中處理和分析數(shù)據(jù)的重要且基礎(chǔ)的操作.相似性查找旨在查詢與給定query滿足相似性條件的數(shù)據(jù)庫中的所有記錄.相似性連接旨在從兩個(gè)集合中找到所有相似的對(duì).它們有許多實(shí)際應(yīng)用,如數(shù)據(jù)清理與集成、近似重復(fù)檢測(cè)和信息提取等.例如當(dāng)兩個(gè)購物網(wǎng)站要合并時(shí),兩個(gè)網(wǎng)站對(duì)同一商品的描述不完全一致,此時(shí)就需要找出兩個(gè)網(wǎng)站中的同一商品并最終合并.因?yàn)樵摂?shù)據(jù)集很大,高效處理數(shù)據(jù)是一種重要需求,所以相似性連接在該情況下是一種必不可少的操作.

對(duì)于傳統(tǒng)的Jaccard算法,根據(jù)過濾算法原理,大致可分為以下三種類型:①基于前綴過濾的算法;②基于鴿籠和劃分思想的過濾算法;③基于樹型數(shù)據(jù)結(jié)構(gòu)的過濾算法.前綴過濾算法是基于兩個(gè)數(shù)據(jù)的前綴至少共享一個(gè)元素來實(shí)現(xiàn)的[1-3].文獻(xiàn)[1]首次提出了前綴過濾的思想,并利用倒排索引實(shí)現(xiàn)了快速的相似性連接算法；文獻(xiàn)[2]通過將各記錄中的元素按照頻率由小到大的順序排序優(yōu)化了前綴過濾；文獻(xiàn)[3]進(jìn)一步縮小了前綴的長(zhǎng)度，利用共享元素的位置信息對(duì)候選進(jìn)行位置過濾，而且該文還對(duì)位置過濾的思想進(jìn)行推廣,提出了后綴過濾.基于鴿籠和劃分的過濾算法[4-6]主要思想是先根據(jù)鴿籠原理將每條記錄劃分為特定個(gè)數(shù)的不相交的段,再將這些段作為簽名構(gòu)建索引,最后計(jì)算出至少有一個(gè)共有段的記錄對(duì)的集合作為候選集.文獻(xiàn)[4]首次利用鴿籠原理提出了PartEnum；文獻(xiàn)[5]首次提出了基于全局元素劃分的鴿籠過濾算法；文獻(xiàn)[6]則在鴿籠原理的基礎(chǔ)上進(jìn)行了優(yōu)化,提出了一個(gè)新的過濾框架來覆蓋基于鴿籠原理的過濾框架,并且大多數(shù)基于鴿籠原理進(jìn)行分區(qū)的算法都有可能通過采用這個(gè)新原理來提高過濾功能.基于樹型數(shù)據(jù)結(jié)構(gòu)的過濾算法[7-8]與上述算法不同,它們不生成簽名來構(gòu)建倒排索引,而是將記錄組織到樹中,在樹中進(jìn)行過濾.

由于傳統(tǒng)的相似性連接問題在尋找相似對(duì)時(shí)有一些情況并不適用.例如{sweet,hot}和{hit,sweot},雖然它們很相似,但是不論是基于token的相似性函數(shù)或者基于字符的相似性函數(shù),它們的相似度都很低,并且基于token的相似性函數(shù)的相似度甚至為0,所以文獻(xiàn)[9]首次提出了模糊相似性連接問題,利用該算法提出的token敏感簽名在前綴過濾的基礎(chǔ)上進(jìn)行過濾可減少候選的數(shù)量；并且該算法在記錄級(jí)使用基于token的相似性函數(shù),而在元素級(jí)僅僅支持基于字符的相似性函數(shù).文獻(xiàn)[10]則在記錄級(jí)以及元素級(jí)都支持基于token的相似性函數(shù).其在前綴過濾生成簽名的部分進(jìn)行了改進(jìn),利用該算法生成的簽名以及其提出的檢測(cè)過濾器和最近鄰過濾器進(jìn)行過濾可大量減少候選的數(shù)量,但它在過濾的過程中并沒有考慮到token的長(zhǎng)度、元素的長(zhǎng)度以及token在元素中的位置對(duì)過濾性能的影響,所以其過濾效率并不是很高.由于文獻(xiàn)[11]是基于鴿籠原理劃分記錄中的元素來生成簽名,共享同一簽名的元素對(duì)應(yīng)的記錄視為候選對(duì),但由于該算法并沒有考慮到記錄中匹配的元素的個(gè)數(shù)對(duì)整體相似性的影響,在記錄之間一旦有匹配的元素就將其視為候選對(duì),造成候選集中假陽性較高,并且由于該算法通過將全局元素劃分來對(duì)應(yīng)各個(gè)元素的劃分,所以部分元素的劃分中可能生成空集,但沒有考慮到出現(xiàn)空集時(shí)的處理辦法.為了解決這些問題,本文提出了一個(gè)基于動(dòng)態(tài)雙重前綴的相似性連接算法.與之前的基于前綴過濾算法不同的是,之前的算法采用固定前綴,而本文采用了雙重前綴方法,即在查找候選以及構(gòu)建索引時(shí)使用不同的前綴來提高過濾效力.在此基礎(chǔ)上又對(duì)雙重前綴過濾方法進(jìn)行了優(yōu)化,在保證不漏解的情況下取各種前綴生成的候選集合的交集來縮小候選集合.還設(shè)計(jì)了一種預(yù)驗(yàn)證方法來減少驗(yàn)證階段所花費(fèi)的不必要的時(shí)間.

1 問題定義

與之前的研究[9-11]一樣,本文也采用fuzzy overlap來實(shí)現(xiàn)模糊相似性連接.給定兩條記錄R與S和元素級(jí)相似性閾值δ,構(gòu)建一個(gè)二部圖G=((X,Y),E),X與Y中的頂點(diǎn)分別是記錄R與S中的元素.對(duì)于任意的兩個(gè)元素ri和sj,如果sim(ri,sj)≥δ,在二部圖ri和sj之間會(huì)存在一條邊,該邊的權(quán)重為ri和sj的相似值.下面是fuzzy overlap的定義.

下面利用fuzzy overlap來定義帶有元素級(jí)相似性閾值δ限制的記錄級(jí)相似性函數(shù).

Fuzzy-Jaccard Similarity:

Fuzzy-Dice Similarity:

Fuzzy-Cosine Similarity:

2 基于任選前綴的相似性連接算法

2.1 任選前綴

對(duì)于Jaccard相似性,若元素ri和sj,滿足sim(ri,sj)≥δ,則|ri∩sj|≥max{「δ|ri|?,「δ|sj|?},即ri和sj至少共享max{「δ|ri|?,「δ|sj|?}個(gè)token.將ttoken=max{「δ|ri|?,「δ|sj|?}稱為元素級(jí)overlap閾值.

下面利用記錄級(jí)fuzzy overlap閾值trecord和元素級(jí)overlap閾值ttoken定義模糊Jaccard相似性連接問題中記錄的雙重任選前綴.

根據(jù)定理1和上面的共享元素與共享token的數(shù)量,很容易得到以下的結(jié)論:

2)ri和sj滿足長(zhǎng)度過濾;

3)ri和sj對(duì)于共享token滿足位置過濾.

基于定理2,提出了基于雙重任選前綴的模糊Jaccard相似性連接算法,如表1所示.

表1 算法1

2.2 查詢最優(yōu)任選前綴

AS-prefixttoken(ri,j)=

基于上述分析,提出OptimalPrefixQuery(Ri)算法,如表2所示.

表2 算法2

2.3 索引最優(yōu)任選前綴

在傳統(tǒng)前綴方法中,所有的記錄按照同一個(gè)順序?qū)⒃剡M(jìn)行排序,然后選取前面固定個(gè)元素作為該記錄的前綴.其中的順序一般選擇元素的頻數(shù)升序的順序.被選擇的前綴中的元素是該記錄中頻數(shù)較低的元素.這樣做有利于減少頻數(shù)高的元素引起的大量候選.本文采用這種方法來選擇索引前綴,稱之為低頻前綴.同時(shí),選擇索引前綴時(shí)在低頻前綴的基礎(chǔ)上作了一些改進(jìn).

由于Ri的索引前綴僅用于與其后面處理的記錄的過濾,即是否與Ri+1,Ri+2,…,Rn形成候選.因此,構(gòu)造查詢前綴時(shí),考慮的不應(yīng)該是各個(gè)token在所有記錄中的頻數(shù).對(duì)于待處理記錄Ri,選擇所有未處理記錄Ri,Ri+1,Ri+2,…,Rn中各個(gè)token的低頻前綴作為索引前綴.

基于上述分析提出ImprLowFrePrefixIndex(Ri)算法,如表3所示.

表3 算法3

2.4 索引

圖1 樹的索引結(jié)構(gòu)

下面介紹在token生成候選集合時(shí)如何利用該索引結(jié)構(gòu)進(jìn)行過濾,如表4所示.

表4 算法 4

3 優(yōu) 化

3.1 生成候選的優(yōu)化

給定兩個(gè)集合A,B,若在A的某一個(gè)任意任選前綴與B的任意任選前綴中有公共token,即在A的候選集合中有B；而在另一任選前綴中與B并沒有公共token,即此時(shí)A的候選集合中并沒有B,那么此時(shí)可以斷定集合A與B并不相似.

基于此現(xiàn)象,為了減小驗(yàn)證過程所花費(fèi)的時(shí)間,可以在集合中多次選取不同任選前綴,利用不同任選前綴生成的候選的交集來縮小候選集合.然后將此發(fā)現(xiàn)應(yīng)用到二重前綴過濾算法中.

定理3設(shè)R1為任意一條記錄,C″為采用R1的任選前綴生成的候選集合,C為采用最優(yōu)任選前綴生成的候選集合,那么R1的最終候選集合為C′←C∩C″.

基于上述分析,提出了優(yōu)化生成候選算法,該算法分為三階段來完成.首先初始化候選集合C′為空集并確定任意選擇的前綴生成的候選集合C″.在每個(gè)元素中任意選擇N1個(gè)token將其加入到S1(Ri)中,隨后在S1(Ri)中任意選擇N2個(gè)子元素添加到S2(Ri)中,確定S2(Ri)中的每個(gè)子元素中的每個(gè)token生成的候選,并將候選對(duì)添加到C″中.然后確定采用最優(yōu)任選前綴生成的候選集合C.利用OptimalPrefixQuery()來生成記錄的查詢前綴,利用生成的查詢前綴以及GenCandi()來確定查詢前綴生成的候選集合C.最后取C″與C的交集.

3.2 預(yù)驗(yàn)證最大區(qū)分任選前綴

(1)

存在一個(gè)匹配,使得

(2)

存在一個(gè)匹配,邊的個(gè)數(shù)為

e≥d;

(3)

對(duì)于任意的i+j≤d-1,

(4)

由式(3)和式(4)可以推出,在二部圖中去掉任意少于等于d-1個(gè)頂點(diǎn),圖中至少還有一條邊存在.

定理4(最大區(qū)分前綴確認(rèn)) 記錄R和S的m最大區(qū)分前綴的二部圖中至少存在一條邊等價(jià)于記錄R和S的二部圖中存在一個(gè)匹配,其包含邊的個(gè)數(shù)e≥d.

由于在預(yù)驗(yàn)證階段,所有候選對(duì)的記錄的長(zhǎng)度都已知,所以d很容易求得.根據(jù)定理4可知,如果在R1與R2的d最大區(qū)分前綴的二部圖中仍有兩個(gè)頂點(diǎn)之間互相連接,那么該候選對(duì)經(jīng)過預(yù)驗(yàn)證進(jìn)入最終候選集合進(jìn)行最后驗(yàn)證.否則,R1與R2不能通過過濾器被過濾掉.

基于上述分析,本文提出了預(yù)驗(yàn)證階段最大區(qū)分任選前綴算法.首先根據(jù)求得的R1與R2中元素之間的相似值來構(gòu)建相應(yīng)的二部圖.隨后根據(jù)兩個(gè)記錄的長(zhǎng)度計(jì)算最大匹配中元素個(gè)數(shù)閾值d,并且根據(jù)閾值d來確定二部圖中需去除d-1個(gè)頂點(diǎn).然后在二部圖中去除度數(shù)最大的頂點(diǎn)以及與該頂點(diǎn)相連接的邊,每去除一個(gè)頂點(diǎn)以及相連接的邊后都需更新各頂點(diǎn)的度數(shù).此時(shí)若二部圖G中仍有兩個(gè)頂點(diǎn)之間有邊相連,那么該預(yù)候選對(duì)經(jīng)過預(yù)驗(yàn)證進(jìn)入驗(yàn)證階段.否則,該候選對(duì)被過濾掉.

4 結(jié)果與討論

所有實(shí)驗(yàn)均在具有Intel Xeon(R)CPU處理器,16 GB RAM,運(yùn)行Ubuntu 14.04.1的服務(wù)器上進(jìn)行. 所有算法均使用C ++實(shí)現(xiàn),并使用GCC 4.8.4進(jìn)行編譯.

4.1 數(shù)據(jù)集

在三個(gè)廣泛使用的數(shù)據(jù)集上來評(píng)估ASOP算法.DBLP:計(jì)算機(jī)科學(xué)出版物的數(shù)據(jù)集,其中包含題目、作者、出版商等屬性.將每個(gè)屬性看成一個(gè)元素,元素中的每個(gè)單詞看作一個(gè)token,從中隨機(jī)選擇了100萬個(gè).QUERY LOG:搜索引擎中的查詢?nèi)罩?將每行中的單詞看成一個(gè)元素,從中隨機(jī)選擇了80萬個(gè).WEBTABLE:大型WEB數(shù)據(jù)庫,其中包含來自WEB的數(shù)百萬個(gè)html表.本文從中隨機(jī)選擇了50萬個(gè).具體細(xì)節(jié)如表5所示.

表5 數(shù)據(jù)集

4.2 本文算法的表現(xiàn)

用AS代表在第2節(jié)提出的基于任選前綴的相似性連接算法;ASO代表在第2節(jié)AS的基礎(chǔ)上加上生成候選的優(yōu)化算法;ASOP代表在ASO的基礎(chǔ)上對(duì)候選進(jìn)行預(yù)驗(yàn)證的過程.整個(gè)過程所需要的連接時(shí)間如圖2所示.從圖2中可以看到隨著相似性閾值τ的增長(zhǎng),三種算法的連接時(shí)間都呈下降趨勢(shì),且ASOP算法的連接時(shí)間明顯比ASO以及AS低很多.

圖2 不同數(shù)據(jù)集上所提算法的連接時(shí)間

4.3 與最先進(jìn)的算法作比較

將本文的方法與最先進(jìn)的兩種算法Silkmoth以及MF-Join作比較.在該實(shí)驗(yàn)中,固定元素級(jí)相似性閾值δ=0.8,如圖3所示.從圖中可以看出:1)不論在哪個(gè)數(shù)據(jù)集中,本文提出的ASOP算法的整體性能要遠(yuǎn)好于Silkmoth以及MF-Join; 2)在三種數(shù)據(jù)集中,MF-Join的連接時(shí)間都要比Silkmoth少; 3)在三個(gè)數(shù)據(jù)集中,ASOP的連接時(shí)間要遠(yuǎn)低于MF-Join.

接下來通過改變?cè)丶?jí)相似性閾值δ來對(duì)三種算法的連接時(shí)間進(jìn)行討論.在該實(shí)驗(yàn)中,固定相似性閾值τ=0.85,實(shí)驗(yàn)結(jié)果如圖4所示.從圖中可以看出,不論在哪個(gè)數(shù)據(jù)集中,隨著閾值δ的改變,本文算法的整體表現(xiàn)仍要好于Silkmoth和MF-Join.

圖3 改變?chǔ)拥闹蹬c當(dāng)前最先進(jìn)的方法作比較

圖4 改變?chǔ)牡闹蹬c當(dāng)前最先進(jìn)的方法作比較

5 結(jié) 語

本文針對(duì)相似性連接問題,提出了ASOP算法,并在三個(gè)數(shù)據(jù)集上來評(píng)估該算法.從實(shí)驗(yàn)結(jié)果中可以看出,不論是連接過程所需要的時(shí)間、或是生成的候選對(duì)的數(shù)量,本文提出的ASOP算法的效率都優(yōu)于Silkmoth以及MF-Join算法.但是由于在構(gòu)建索引部分加入了token的長(zhǎng)度以及位置信息,這就會(huì)導(dǎo)致索引所占的空間復(fù)雜度很大,今后可以在縮小索引空間上進(jìn)一步優(yōu)化.