李玉琦，李 龍

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

1 引言

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

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

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

2 網(wǎng)頁信息特征提取

若網(wǎng)頁信息詞頻的貢獻率較低，在實際情況中容易成為噪聲特征[6]?；谀Ｊ阶R別算法的網(wǎng)頁重復(fù)信息抽取方法通過特征詞集中存在的因子ai描述不同類中特征詞的集中程度，ai可通過下式計算得到

(1)

式中，在類別i中網(wǎng)頁信息特征詞w出現(xiàn)的次數(shù)為dfi(w)，tf(w)為在類別i中網(wǎng)頁信息特征詞w對應(yīng)的詞頻數(shù)；ci為屬于類別i的文檔數(shù)。

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

(2)

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

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

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

(3)

(4)

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

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

設(shè)置特征詞集Hw，網(wǎng)頁信息特征均存在于該詞集中，根據(jù)網(wǎng)頁信息的特征值對網(wǎng)頁信息進行過濾處理，并選取其中一部分信息構(gòu)建特征詞集Lw。

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

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

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

3 網(wǎng)頁重復(fù)信息抽取

3.1 網(wǎng)頁信息分類

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

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

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

(5)

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

網(wǎng)頁之間存在的鏈接關(guān)系可以有助于網(wǎng)頁信息的分類[8]。有向圖的邊通常情況下可以描述網(wǎng)頁之間存在的鏈接，并通過邊集合E存儲網(wǎng)頁中存在的所有鏈接結(jié)構(gòu)。在此基礎(chǔ)上可以將正則化因子γ引入目標函數(shù)中

(6)

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

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

(7)

式中，參數(shù)w、z的值可以通過正則化因子λ1、λ2實現(xiàn)控制。

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

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

(8)

為提高懲罰函數(shù)的靈活性，在上式的基礎(chǔ)上加入調(diào)整因子α

(9)

獲得軟間隔分類器

(10)

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

3.2 重復(fù)信息抽取

基于模式識別算法的網(wǎng)頁重復(fù)信息抽取方法在不同類別中對網(wǎng)絡(luò)信息的語義相似度進行計算，根據(jù)計算結(jié)果實現(xiàn)網(wǎng)頁重復(fù)信息的抽取。

1)語義相似度

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

(11)

2)結(jié)構(gòu)相似度

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

csim(A，B)=μδ×

(12)

3)相似度

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

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

(13)

式中，α代表在網(wǎng)頁中相同元素對應(yīng)的語義影響因子；β代表在網(wǎng)頁中相同元素對應(yīng)的結(jié)構(gòu)影響因子。語義影響因子α和結(jié)構(gòu)影響因子β之間滿足下式

(14)

根據(jù)上式可知語義影響因子α通常情況下大于結(jié)構(gòu)影響因子β，因此對網(wǎng)頁信息相似度進行計算時，需重點考慮語義影響因子α[12]。

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

4 實驗與分析

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

設(shè)q代表全面率，代表網(wǎng)頁重復(fù)信息Nt與網(wǎng)頁信息N之間的比值，其計算公式如下

(15)

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

圖1 不同方方法的全面率測試結(jié)果

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

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

表1 不同方法的重復(fù)信息比例

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

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

(16)

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

圖2 整體性能測試結(jié)果

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

5 結(jié)束語

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