基于模式識別算法的網頁重復信息抽取仿真

李玉琦，李 龍

(1. 北京郵電大學，北京 100876；2. 中國科學技術大學，安徽 合肥 230026)

1 引言

數據清洗是為了消除網頁或數據集中存在的臟數據或錯誤數據，采用某種技術對其進行剔除或改正[1]。數據清洗通常包括重復數據歸并處理、數據標準化處理、數據增強處理和數據解析等。在表達方式和數據格式方面對數據進行標準化處理是數據標準化處理的實質；拆分、合并處理數據是數據解析中的重要步驟；數據清洗處理的主要目的是為了提高數據的完整性，填補處理缺失的數據，消除文本中存在的相似數據。數據清洗技術被廣泛地應用在各種工程數據和網絡數據挖掘中[2]。網絡中存在的重復數據會對數據的檢索和判斷產生影響，同時也會浪費存儲空間，因此需要進一步深入研究網頁重復信息抽取方法。

時珉等人[3]提出基于滑動標準差計算的網頁重復信息抽取方法，該方法首先分析網頁信息的來源和信息在網頁中分布的特性，計算網頁信息的滑動標準差，根據計算結果構建標準差曲線，通過曲線上翹特性判斷網頁中存在的重復信息，實現網頁重復信息的抽取。但是，該方法沒有對網頁信息分類，導致方法的全面率較低。何俊等人[4]提出基于Petri網的網頁重復信息抽取方法。該方法在Petri網的基礎上建立RCCM模型，利用RCCM模型生成規(guī)則鏈，利用規(guī)則鏈對網絡中存在的重復信息進行檢測，實現網頁重復信息的抽取，該方法無法區(qū)分網頁信息的類別，導致方法存在重復信息比例高的問題。徐搏超[5]提出基于參數關聯性的網頁重復信息抽取方法。該方法利用關聯規(guī)則對網頁信息之間存在的關聯性進行分析，獲得關聯性較強的網頁信息，并通過空間數據聚類算法對網頁信息進行初步檢測，采用高斯核相關向量機對網頁重復信息進行抽取。但是該方法沒有對網頁信息的類別進行劃分，重復信息抽取結果受網頁信息類別的影響較大，方法的整體性能較差。

為解決上述方法存在的問題，提出新的基于模式識別算法的網頁重復信息抽取方法。

2 網頁信息特征提取

若網頁信息詞頻的貢獻率較低，在實際情況中容易成為噪聲特征[6]。基于模式識別算法的網頁重復信息抽取方法通過特征詞集中存在的因子ai描述不同類中特征詞的集中程度，ai可通過下式計算得到

(1)

式中，在類別i中網頁信息特征詞w出現的次數為dfi(w)，tf(w)為在類別i中網頁信息特征詞w對應的詞頻數；ci為屬于類別i的文檔數。

在互信息中引入詞頻信息MI(w，ci)，其表達式如下

(2)

式中，P(w)為樣本中存在特征詞w的概率；P(w|ci)表示類別ci中存在特征詞w的概率。

當網頁中存在特征詞時，用類間因子βi描述其集中程度，特征詞的重要程度受類間均勻度的影響。

特征詞w在類別ci網頁中出現的數量為衡量類間均衡性的標準，基于模式識別算法的網頁重復信息抽取方法通過差異因子βi描述網頁中特征詞的分布特征，通過下式計算因子βi

(3)

(4)

若網頁中存在的信息對應的特征值較低，通常會被刪掉[7]。但網頁中通常存在大量的低信息量特征，僅僅加權處理累加分布和詞頻不能獲得高精度的網頁特征。

為解決上述問題，所提方法在關聯規(guī)則的基礎上獲取網頁中不同信息的利用率，計算過濾特征與上述提取特征之間存在的關聯性。

設置特征詞集Hw，網頁信息特征均存在于該詞集中，根據網頁信息的特征值對網頁信息進行過濾處理，并選取其中一部分信息構建特征詞集Lw。

計算特征詞集Hw與Lw對應的頻繁2項集合，并對候選集C2過濾處理，消除頻繁出現的前項，獲得后項規(guī)則L2={(w11→w21，cv1)，…(w1k→w2k，cvk)}，其存在最大的特征值。

若特征詞規(guī)則w1g滿足w1g→w2g，則特征詞w1g根據規(guī)則置信度cvg對應的概率轉變?yōu)閣2g。

根據特征集Hw向量化處理重新映射后獲得的語料庫，獲得可入模數據txt={t1，t2，…，tn}，其中ti即為網頁信息特征。

3 網頁重復信息抽取

3.1 網頁信息分類

選擇模式識別中的支持向量機根據提取的網頁信息特征對網頁信息進行分類。

基于模式識別算法的網頁重復信息抽取方法為了建立軟間隔分類器，在支持向量機中引入松弛因子。

通過下式描述線性分類器f(x)=w·x的目標函數，其表達式如下

(5)

式中，l代表松弛因子；R(w·x，yi)代表損失函數，網頁信息訓練集產生的損失可以通過該函數進行描述；參數λ在上式中的主要目的是保證訓練集中的網頁信息可以實現正確的分類；w·w代表采用支持向量機對網頁信息進行分類時對應的間隔。

網頁之間存在的鏈接關系可以有助于網頁信息的分類[8]。有向圖的邊通常情況下可以描述網頁之間存在的鏈接，并通過邊集合E存儲網頁中存在的所有鏈接結構。在此基礎上可以將正則化因子γ引入目標函數中

(6)

式中的第三項代表正則化因子；αij代表網頁j與網頁i之間存在的鏈接對應的權重；φ(w·xi，w·xj)代表懲罰函數。

分類器受特征空間豐富度的影響，兩者之間呈線性關系[9]，引入變量zi將其作為松弛因子提高分類器的靈活性，針對網頁中存在的所有結點i，都構建對應的分類器，目標函數此時可以轉變?yōu)橄率?/p>

(7)

式中，參數w、z的值可以通過正則化因子λ1、λ2實現控制。

目標函數屬于凸函數，需要對其進行優(yōu)化，即在約束條件下最小化參數w、z[10]，基于模式識別算法的網頁重復信息抽取方法通過運行回歸算法對參數w進行最小化處理。

所提方法對網頁結點i和j分類之前，需要計算網頁的置信度，根據計算結果獲得正則化因子，設fi、fj分別代表網頁i、j對應的可信度，基于模式識別算法的網頁重復信息抽取方法根據可信度重新定義懲罰函數

(8)

為提高懲罰函數的靈活性，在上式的基礎上加入調整因子α

(9)

獲得軟間隔分類器

(10)

利用上式的軟間隔分類器對網頁信息完成分類處理。

3.2 重復信息抽取

基于模式識別算法的網頁重復信息抽取方法在不同類別中對網絡信息的語義相似度進行計算，根據計算結果實現網頁重復信息的抽取。

1)語義相似度

設asim(A，B)代表網頁信息A和網頁信息B之間的語義相似度，其計算公式如下

(11)

2)結構相似度

語義要素受網頁結構要素的影響可以通過結構相似度進行衡量[11]，因此計算結構相似度時需要引入權重要素，設csim(A，B)代表網頁信息A和網頁信息B之間存在的結構相似度，其計算公式如下

csim(A，B)=μδ×

(12)

3)相似度

綜合考慮語義相似度asim(A，B)和結構相似度csim(A，B)，計算網頁信息A與網頁信息B之間存在的相似度sim(A，B)

sim(A，B)=αasim(A，B)+βcsim(A，B)

(13)

式中，α代表在網頁中相同元素對應的語義影響因子；β代表在網頁中相同元素對應的結構影響因子。語義影響因子α和結構影響因子β之間滿足下式

(14)

根據上式可知語義影響因子α通常情況下大于結構影響因子β，因此對網頁信息相似度進行計算時，需重點考慮語義影響因子α[12]。

當相似度sim(A，B)大于等于閾值δ時，表明信息重復，完成網頁重復信息的抽取。

4 實驗與分析

為驗證基于模式識別算法的網頁重復信息抽取方法的整體有效性，需要對基于模式識別算法的網頁重復信息抽取方法進行測試。分別采用基于模式識別算法的網頁重復信息抽取方法(方法1)、基于滑動標準差計算的網頁重復信息抽取方法(方法2)、基于Petri網的網頁重復信息抽取方法(方法3)和基于參數關聯性的網頁重復信息抽取方法(方法4)進行對比測試。

設q代表全面率，代表網頁重復信息Nt與網頁信息N之間的比值，其計算公式如下

(15)

方法1、方法2、方法3和方法4的全面率測試結果如圖1所示。

圖1 不同方方法的全面率測試結果

分析圖1中的數據可知，采用方法1對網頁重復信息抽取時，獲得的全面率均高于80%，采用方法2對網頁重復信息抽取時，獲得的全面率均在40%-60%內波動；采用方法3對網頁重復信息抽取時，獲得的全面率均在30%-50%內波動；采用方法4對網頁重復信息抽取時，獲得的全面率均在60%附近波動，通過上述分析可知，所提方法的全面率最高，表明方法1可有效地實現網頁重復信息的抽取，這是因為該方法根據提取的網頁信息特征對網頁信息進行分類處理，對不同類別中存在的重復信息進行抽取，提高了方法1的全面率。

基于以上實驗結果，下面將重復信息所占比例作為測試指標，對方法1、方法2、方法3和方法4進行測試，結果如表1所示。

表1 不同方法的重復信息比例

根據表1數據可知，方法2、方法3和方法4的重復信息比例較高，表明采用上述方法對網頁重復信息抽取后，網頁中還存在大量的重復信息，表明方法的有效性較差。方法1在測試過程中獲得的重復信息比例較低，表明采用方法1對網頁重復信息進行抽取后，網頁中的重復信息量明顯下降，原因是方法1對網頁信息進行分類處理時，引入了松弛因子，提高了分類器的靈活性，可有效的提取出網頁中存在的重復信息，降低了重復信息比例。

采用綜合指標F-Measure對方法1、方法2、方法3和方法4的整體有效性進行測試，F-Measure的計算公式如下

(16)

其中，Recall代表查全率；Precision代表查準率。

圖2 整體性能測試結果

根據圖2中的數據可知，方法1的綜合指標值遠遠高于方法2、方法3和方法4的綜合指標值，表明方法1進行網頁重復信息抽取時的整體性能優(yōu)于方法2、方法3和方法4的整體性能，原因為方法1對網頁信息進行分類處理時，利用調節(jié)因子對懲罰函數進行調整，分類器分類性能得以提高，進而優(yōu)化了方法1的整體性能。

5 結束語

目前網頁重復信息抽取方法存在全面率低、重復信息比例高和整體性能差的問題，提出基于模式識別算法的網頁重復信息抽取方法，根據網頁信息的特征對網頁信息進行分類，計算不同類別網頁信息的相似度，以此完成網頁重復信息的抽取，解決了目前方法中存在的問題，為網頁信息資源的利用創(chuàng)造了條件。