融合多模式匹配的網絡信息實體關聯研究仿真

常偉鵬，袁 泉

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

1 引言

網絡形態的不斷變化，使得網絡數據呈現不同形式分布在各種不同類型的平臺上，要對這些分布復雜的信息數據采取綜合分析，必須將這些多源信息做集成處理，這其中最重要的工作就是信息實體的關聯匹配[1-2]。由于網絡信息實體的異構沖突特性，以及當前各領域對數據安全的嚴格控制，導致當前對于網絡信息實體關聯匹配的處理難以滿足應用需求，因此對于信息實體匹配的性能改進研究已經成為網絡信息處理的重點。

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

2 網絡信息實體的關聯匹配原理

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

(1)

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

(2)

根據距離計算，結合歸一化操作，任意兩個字符串關于距離的相似度公式描述為

(3)

通過信息實體間的距離關系，可以獲得彼此關聯匹配性，由于在該距離計算時考慮了動態規劃，因此，本文在結構相似度處理過程中，涉及距離的計算也基于該方法。另外，傳統單一模式很難實現網絡復雜信息實體的全部匹配工作[7]，為此，本文針對網絡信息實體屬性，從多個模式對其進行匹配處理。

3 多模式匹配策略

由于網絡信息的多源異構特性，信息實體中的復雜屬性如果僅依靠某一種模式很難準確匹配，即便一種模式實現匹配也不能表示該匹配是正確的，因此，這里針對網絡信息實體的復雜特性，從以下三種模式進行匹配設計。

3.1 語法語義匹配

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

(4)

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

(5)

式中，hypo(sn)用于計算sn包含多少下位詞，Nodemax為全部節點數目，depth(sn)為sn在詞典中的對應深度。任意兩個詞匯或屬性的相關距離描述為：

(6)

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

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

(7)

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

3.2 數據類型匹配

在網絡數據傳輸過程中，存在大量的數據類型轉換，且在類型轉換時可能出現信息缺失，一個信息實體可能對應多種數據類型，為此，類型的匹配也會影響網絡信息實體的真實關聯性。假定兩個信息實體sni與snj的數據類型分別為typel和type2，則它們的類型相似度表示為：

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

(8)

此時，結合語法語義和數據類型模式，任意兩個網絡信息實體相似度可以描述為：

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

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

(9)

3.3 結構性匹配

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

(10)

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

(11)

(12)

通過懲戒函數A與C，實現了字符數量設計規則，將編輯距離采取進一步處理，從而得出節點間距相似度為：

(13)

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

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

(14)

式中的加權系數滿足限定0≤η≤1。

3.4 融合多模式匹配

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

(15)

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

(16)

融合匹配初始時，首先在匹配屬性Xm與未匹配屬性Xu內部隨機生成一組屬性對，然后計算出它們的語法語義相似度、類型相似度和結構相似度，最后代入區分性能公式，利用迭代處理得到融合匹配程度，在程序實現過程中，將匹配成功的網絡信息實體進行連接，便得到網絡信息實體的關聯性。

4 網絡信息實體處理復雜度分析

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

(17)

(18)

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

(19)

因為Y2

5 仿真分析

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

5.1 區分性能結果分析

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

圖1 區分性能仿真曲線

5.2 匹配性能結果分析

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

precision=T/P

(20)

recall-T/R

(21)

overall=(T-F)/R

(22)

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

圖2 匹配性能仿真曲線

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

表1 匹配性能結果對比

5.3 匹配效率結果分析

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

圖3 匹配效率仿真結果曲線

6 結束語

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