常偉鵬，袁 泉

(中國藥科大學圖書與信息中心，江蘇 南京 211198)

1 引言

網(wǎng)絡(luò)形態(tài)的不斷變化，使得網(wǎng)絡(luò)數(shù)據(jù)呈現(xiàn)不同形式分布在各種不同類型的平臺上，要對這些分布復(fù)雜的信息數(shù)據(jù)采取綜合分析，必須將這些多源信息做集成處理，這其中最重要的工作就是信息實體的關(guān)聯(lián)匹配[1-2]。由于網(wǎng)絡(luò)信息實體的異構(gòu)沖突特性，以及當前各領(lǐng)域?qū)?shù)據(jù)安全的嚴格控制，導致當前對于網(wǎng)絡(luò)信息實體關(guān)聯(lián)匹配的處理難以滿足應(yīng)用需求，因此對于信息實體匹配的性能改進研究已經(jīng)成為網(wǎng)絡(luò)信息處理的重點。

文獻[3]采用信息實體匹配與模式匹配雙重交錯的處理方式，取得了較好的精確性，但是算法處理復(fù)雜度過高；文獻[4]為了降低相似度計算，設(shè)計了信息實體的字符跳轉(zhuǎn)距離，在匹配效率上取得了一定程度的性能改善；文獻[5]將單一模式采取改進優(yōu)化，在迭代處理的過程中，自主完成本地化特征的匹配，從而避免多模式情況下的匹配沖突，但是該方法與文獻[4]方法一樣，沒有考慮信息實體的復(fù)雜特性；文獻[6]采用分層匹配策略，通過特征分類、分類匹配，以及混合匹配三個層次，依次遞進，逐漸將匹配實體進行壓縮，最終完成信息實體的關(guān)聯(lián)匹配，該方法降低了匹配次數(shù)，但是缺乏對特征分類的精準性。針對現(xiàn)有方法存在的缺陷，本文提出了融合多模式匹配的網(wǎng)絡(luò)信息實體關(guān)聯(lián)策略，分別設(shè)計了語法語義、數(shù)據(jù)類型，以及結(jié)構(gòu)性三種模式相似度，實現(xiàn)信息實體關(guān)聯(lián)的混合匹配處理，有效應(yīng)對含有詞干與復(fù)合詞匯的實體，缺失信息的實體，以及具有上下文聯(lián)系的實體匹配問題，從而提高網(wǎng)絡(luò)信息實體的查全率與查準率，同時優(yōu)化匹配執(zhí)行效率。

2 網(wǎng)絡(luò)信息實體的關(guān)聯(lián)匹配原理

網(wǎng)絡(luò)信息實體關(guān)聯(lián)匹配有利于查找和分析同屬一類的網(wǎng)絡(luò)數(shù)據(jù)，當前對其實現(xiàn)方法通常有窮盡處理與分塊處理。采用窮盡處理時，利用對集合的遍歷搜索得出匹配結(jié)果，準確度與完整性較好，但是處理復(fù)雜度較高；采用分塊處理時，利用映射方法把集合中的實體映射至相應(yīng)規(guī)則塊，并采用排序和距離等計算得出匹配結(jié)果，分塊處理具有較好的處理效率，但是在塊分割的過程中，難以對復(fù)雜信息實體進行準確處理，導致影響匹配的準確度。無論哪種處理方式，最終思想都歸于相似度的計算和度量，據(jù)此匹配信息實體之間的關(guān)聯(lián)。在準確度公式設(shè)計時，對于信息實體，常用字符串距離作為依據(jù)，通過增刪改操作對字符串進行轉(zhuǎn)換，從而得出距離的表示，相似度與距離成正相關(guān)。假定字符串s1與s2的距離為d(s1，s2)，則有d(s1，s2)≤max(|s1|，|s2|)。于是編輯距離計算可以表示為：

(1)

式中s[i]為s的第i個字符，且c(s1[i]，s2[j])的表達式描述為

(2)

根據(jù)距離計算，結(jié)合歸一化操作，任意兩個字符串關(guān)于距離的相似度公式描述為

(3)

通過信息實體間的距離關(guān)系，可以獲得彼此關(guān)聯(lián)匹配性，由于在該距離計算時考慮了動態(tài)規(guī)劃，因此，本文在結(jié)構(gòu)相似度處理過程中，涉及距離的計算也基于該方法。另外，傳統(tǒng)單一模式很難實現(xiàn)網(wǎng)絡(luò)復(fù)雜信息實體的全部匹配工作[7]，為此，本文針對網(wǎng)絡(luò)信息實體屬性，從多個模式對其進行匹配處理。

3 多模式匹配策略

由于網(wǎng)絡(luò)信息的多源異構(gòu)特性，信息實體中的復(fù)雜屬性如果僅依靠某一種模式很難準確匹配，即便一種模式實現(xiàn)匹配也不能表示該匹配是正確的，因此，這里針對網(wǎng)絡(luò)信息實體的復(fù)雜特性，從以下三種模式進行匹配設(shè)計。

3.1 語法語義匹配

利用字符串比較算法實現(xiàn)語法匹配，根據(jù)q-gram對數(shù)據(jù)集合中的字符串進行字符分解，計算出分解后的每個字符權(quán)值ω，并將其組合成向量v=(ω1，ω2…，ωn，)，用來代表語法屬性，于是對于任意兩個匹配語法sni和snj，它們的相似度計算公式如下

(4)

由于網(wǎng)絡(luò)信息實體數(shù)據(jù)屬性復(fù)雜，單純的語法不能完成對詞干與復(fù)合詞匯的描述[8]。因此，當完成語法匹配后，再將屬性sn采取詞形分解，得出語義匹配程度。采用WordNet詞典建立語義相似度模型，詞匯所含信息，以及詞匯在詞典中與其它詞匯的距離，可以作為語義相似度的計算指標。根據(jù)詞形與深度，可以將屬性sn所含信息描述為

(5)

式中，hypo(sn)用于計算sn包含多少下位詞，Nodemax為全部節(jié)點數(shù)目，depth(sn)為sn在詞典中的對應(yīng)深度。任意兩個詞匯或?qū)傩缘南嚓P(guān)距離描述為：

(6)

式中，L(IC)用于計算所含內(nèi)容的語義距離，L(path)用于計算在最小路徑條件下的屬性距離，據(jù)此，進一步計算得到關(guān)于sni與snj的語義相似度如下：

WtSim(sni，snj)=e-(a×L(IC)+β×L(path))

(7)

式中，a和λ為正系數(shù)。所含信息IC和深度之間為正關(guān)聯(lián)，IC和密度之間為負關(guān)聯(lián)。通過語義距離和密度計算，得出其相似度，可以有效應(yīng)對復(fù)合表達式詞匯匹配問題。

3.2 數(shù)據(jù)類型匹配

在網(wǎng)絡(luò)數(shù)據(jù)傳輸過程中，存在大量的數(shù)據(jù)類型轉(zhuǎn)換，且在類型轉(zhuǎn)換時可能出現(xiàn)信息缺失，一個信息實體可能對應(yīng)多種數(shù)據(jù)類型，為此，類型的匹配也會影響網(wǎng)絡(luò)信息實體的真實關(guān)聯(lián)性。假定兩個信息實體sni與snj的數(shù)據(jù)類型分別為typel和type2，則它們的類型相似度表示為：

TySim(sni，snj)=Matrix[type1][type2]

(8)

此時，結(jié)合語法語義和數(shù)據(jù)類型模式，任意兩個網(wǎng)絡(luò)信息實體相似度可以描述為：

BaSim(sni，snj)=aEdSim(sni，snj)+bWtSim(sni，snj)

+(1-a-b)TySim(sni，snj)

(9)

3.3 結(jié)構(gòu)性匹配

除了信息實體本身的信息匹配外，網(wǎng)絡(luò)信息實體之間也存在一定程度的依賴和約束，因此，這里引入實體間結(jié)構(gòu)性的相似度，利用實體的節(jié)點路徑，描述實體上下文關(guān)系。對于某節(jié)點來說，如果它與其它實體的節(jié)點相似，則表明該節(jié)點的上下文與其它實體節(jié)點上下文也相似，其相似度可以通過實體屬性節(jié)點來計算。假定信息實體sni與snj的節(jié)點集依次表示為nodes(sni)和nodes(sni)，則根據(jù)前述類型匹配計算節(jié)點間類型相似度，在結(jié)果矩陣內(nèi)進行遍歷，搜索其中所有超過限定邊界haccept的相似度，并將其權(quán)值做求和處理，作為信息實體sni與snj的最終節(jié)點相似度。另外，由于通過信息實體中的字符數(shù)量可以分為多字符與空字符兩種情況，因此在計算實體結(jié)構(gòu)性節(jié)點距離的時候，不應(yīng)該采取字符串距離的計算方式，為此，這里將編輯距離做出改進，從而使節(jié)點間距相似性不受字符數(shù)量影響。其具體的規(guī)則為：當信息實體為非空字符，相同即判定為匹配；當信息實體為空字符，判定不匹配。并采用最小實體距離進行編輯距離計算：

(10)

這里的sni[m]與snj[n]依次為信息實體與snj的第m、n個字符，A與C代表懲戒函數(shù)，用以處理字符數(shù)量對距離計算的影響。它們的表達式分別如下

(11)

(12)

通過懲戒函數(shù)A與C，實現(xiàn)了字符數(shù)量設(shè)計規(guī)則，將編輯距離采取進一步處理，從而得出節(jié)點間距相似度為：

(13)

兩個信息實體的結(jié)構(gòu)性相似度為節(jié)點相似度與節(jié)點間距相似度的加權(quán)，將結(jié)構(gòu)性相似度表示為StSim(snisnj)，則此時信息實體相似度可以表示為：

Sim(snisnj)=ηBaSim(snisnj)+(1+η)StSim(snisnj)

(14)

式中的加權(quán)系數(shù)滿足限定0≤η≤1。

3.4 融合多模式匹配

為了得出各種模式匹配時的區(qū)分性能，這里將匹配屬性記作Xm，未匹配屬性記作Xu，并將Xm對應(yīng)的語法語義相似度、類型相似度、結(jié)構(gòu)性相似度依次記作EdSimXm、WtSimXm、TySimXm、StSimXm，構(gòu)成集合SimXm，將Xu對應(yīng)的語法語義相似度、類型相似度、結(jié)構(gòu)性相似度依次記作EdSimXu、WdSimXu、TySimXu、TySimXu，構(gòu)成集合SimXu。于是，混合模式的相似度區(qū)別性可以表示如下：

(15)

式中simi為屬性相似度，根據(jù)該公式，可以得出各模式相似度的區(qū)分性能，另外，根據(jù)該公式得出信息實體在融合模式中的相似度為：

(16)

融合匹配初始時，首先在匹配屬性Xm與未匹配屬性Xu內(nèi)部隨機生成一組屬性對，然后計算出它們的語法語義相似度、類型相似度和結(jié)構(gòu)相似度，最后代入?yún)^(qū)分性能公式，利用迭代處理得到融合匹配程度，在程序?qū)崿F(xiàn)過程中，將匹配成功的網(wǎng)絡(luò)信息實體進行連接，便得到網(wǎng)絡(luò)信息實體的關(guān)聯(lián)性。

4 網(wǎng)絡(luò)信息實體處理復(fù)雜度分析

融合多模式匹配網(wǎng)絡(luò)信息實體關(guān)聯(lián)性，提高準確性的同時，也導致了由多種模式引起的執(zhí)行復(fù)雜度增加問題。因此，這里首先分析算法執(zhí)行的復(fù)雜度，然后對其進行優(yōu)化。根據(jù)多模式匹配處理過程，主要增加的是相似度計算與迭代處理，假定需要處理的信息實體為n個，且n≥2，單個信息實體平均具有屬性數(shù)量為m，且m>1，則可以利用參與相似度處理的屬性對數(shù)量，來描述算法復(fù)雜度：

(17)

(18)

如果xi=1，說明屬性數(shù)量為1，則不再計算相似度。由于xi≈m，k≈n，因此可將復(fù)雜度整理為

(19)

因為Y2

5 仿真分析

仿真的網(wǎng)絡(luò)信息實體來自CiteSeer數(shù)據(jù)庫，其中還有引用的文獻，這些文獻具有題目信息、作者信息、日期信息等屬性。通過DBGenerator將文獻與實體信息以一定比例生成模擬信息，作為待匹配的網(wǎng)絡(luò)信息實體關(guān)聯(lián)數(shù)據(jù)。利用JAVA編程完成多模式相似度的計算與迭代處理，實現(xiàn)多模式匹配策略，并分別從區(qū)分性能、匹配性能和執(zhí)行效率三個方面進行仿真驗證。

5.1 區(qū)分性能結(jié)果分析

為了驗證多模式匹配的區(qū)分性能，從每次需要完成匹配的網(wǎng)絡(luò)信息實體里任意取出若干屬性對，并由此組成匹配與非匹配集，同時保證它們在數(shù)量上的一致。采用文獻[6]方法作為對比，仿真得出相似度區(qū)分性能結(jié)果曲線如圖1所示，其中橫坐標為兩種集合所包含的元素數(shù)量。從結(jié)果曲線可以看出，對比方法的區(qū)分性能隨著屬性對的增加先是呈現(xiàn)上漲狀態(tài)，隨后趨于平衡狀態(tài)。本文方法的區(qū)分性能在屬性對增加的過程中，始終處于平衡狀態(tài)，大約穩(wěn)定在0.75左右，顯著優(yōu)于對比方法。根據(jù)區(qū)分性能的整體平衡狀態(tài)，表明本文方法在對同義詞，同類型，以及結(jié)構(gòu)相似的信息實體匹配時都具有良好的屬性敏感度，比文獻方法具有更好的實體區(qū)分性能。

圖1 區(qū)分性能仿真曲線

5.2 匹配性能結(jié)果分析

為了驗證多模式匹配策略的性能，通過查準率、查全率，以及全面性做性能評估，假定處理過程中匹配正確數(shù)量表示為T，全部的匹配數(shù)量表示為P，匹配不正確數(shù)量表示為F，實際匹配正確的數(shù)量表示為R，則各項指標的計算公式依次為：

precision=T/P

(20)

recall-T/R

(21)

overall=(T-F)/R

(22)

首先，驗證提出的融合多模式匹配方法在網(wǎng)絡(luò)信息實體數(shù)量變化時的性能，分析實體數(shù)量是否會對匹配性能產(chǎn)生影響，圖2為仿真結(jié)果。根據(jù)結(jié)果曲線可知，在信息實體增加過程中，各項評估指標均出現(xiàn)一定的上升趨勢，并且查準率始終為0.9以上，查全率始終在0.8以上，全面性始終維持在0.74以上。緩慢上升趨勢表明信息實體中存在著非均衡分布，在實體增加時，隨著查找越來越全面，準確性也隨之提高。

圖2 匹配性能仿真曲線

再驗證本文方法與文獻方法的各項指標性能優(yōu)劣，保持實驗中處理的實體數(shù)量相同，得到10次仿真結(jié)果的平均值，結(jié)果數(shù)據(jù)如表1所示。根據(jù)表中數(shù)據(jù)對比，三項評估指標均顯著優(yōu)于對比方法，其原因是多模式匹配能夠有效利用語法語義、類型、以及結(jié)構(gòu)特征，多角度準確區(qū)分復(fù)合表達式詞匯，類型轉(zhuǎn)換，上下文邊界等復(fù)雜場景。

表1 匹配性能結(jié)果對比

5.3 匹配效率結(jié)果分析

為了驗證本文方法的匹配效率，通過仿真得到處理時間與網(wǎng)絡(luò)信息實體數(shù)量變化之間的關(guān)系曲線，結(jié)果如圖3所示。根據(jù)曲線可知，隨著信息實體數(shù)量的增加，文獻方法的執(zhí)行時間快速增長，逼近指數(shù)形式；而本文方法的執(zhí)行時間增長顯然要慢很多，近似呈現(xiàn)對數(shù)形式。該現(xiàn)象主要是由于多模式匹配增加了實體關(guān)聯(lián)分析的準確性，避免了模糊實體被反復(fù)分類，導致迭代計算無法滿足結(jié)束條件，不能快速跳出。多模式匹配提高查準率的同時，也有效降低了迭代處理次數(shù)，提高了匹配效率。

圖3 匹配效率仿真結(jié)果曲線

6 結(jié)束語

網(wǎng)絡(luò)信息實體具有異構(gòu)、分布等特點，對其關(guān)聯(lián)匹配有利于數(shù)據(jù)的共享與分析，現(xiàn)有方法采取的模式匹配往往難以獲得理想的準確度與效率，為此本文提出了融合多模式匹配的網(wǎng)絡(luò)信息實體關(guān)聯(lián)策略。分別從語法語義、數(shù)據(jù)類型，以及結(jié)構(gòu)性三方面進行信息實體關(guān)聯(lián)的匹配處理，并針對各模式設(shè)計了相應(yīng)的相似度匹配算法。語法相似性可以完成簡單實體的粗略匹配，語義相似性可以完成詞干與復(fù)合詞匯的匹配，類型相似性用來完成類型轉(zhuǎn)換實體的匹配，結(jié)構(gòu)性相似性用來完成實體上下文的匹配。通過仿真，分別從相似度區(qū)分性能、匹配性能和執(zhí)行效率三個方面進行了驗證，證明了融合多模式匹配的網(wǎng)絡(luò)信息實體關(guān)聯(lián)策略具有良好的區(qū)分能力，顯著提高了實體關(guān)聯(lián)的準確度，并且執(zhí)行效率呈現(xiàn)良好的對數(shù)增長趨勢。