融合多模式匹配的網(wǎng)絡(luò)信息實(shí)體關(guān)聯(lián)研究仿真

常偉鵬，袁 泉

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

1 引言

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

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

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

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

(1)

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

(2)

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

(3)

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

3 多模式匹配策略

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

3.1 語(yǔ)法語(yǔ)義匹配

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

(4)

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

(5)

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

(6)

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

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

(7)

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

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

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

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

(8)

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

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

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

(9)

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

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

(10)

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

(11)

(12)

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

(13)

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

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

(14)

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

3.4 融合多模式匹配

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

(15)

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

(16)

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

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

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

(17)

(18)

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

(19)

因?yàn)閅2

5 仿真分析

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

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

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

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

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

為了驗(yàn)證多模式匹配策略的性能，通過(guò)查準(zhǔn)率、查全率，以及全面性做性能評(píng)估，假定處理過(guò)程中匹配正確數(shù)量表示為T，全部的匹配數(shù)量表示為P，匹配不正確數(shù)量表示為F，實(shí)際匹配正確的數(shù)量表示為R，則各項(xiàng)指標(biāo)的計(jì)算公式依次為：

precision=T/P

(20)

recall-T/R

(21)

overall=(T-F)/R

(22)

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

圖2 匹配性能仿真曲線

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

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

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

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

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

6 結(jié)束語(yǔ)

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