基于SVM的重復網(wǎng)頁(yè)檢測算法分析論文
引言
隨著(zhù)互聯(lián)網(wǎng)的發(fā)展，網(wǎng)絡(luò )上的文本信息越來(lái)越容易復制，由此產(chǎn)生了大量的重復網(wǎng)頁(yè)和鏡像文檔，這一方面增加了網(wǎng)絡(luò )爬蟲(chóng)的負擔，另一方面降低了用戶(hù)體驗。因此，越來(lái)越多的學(xué)者關(guān)注重復網(wǎng)頁(yè)檢測這一領(lǐng)域。
對于重復網(wǎng)頁(yè)可以定義為內容完全重復和近似重復，對于完全重復的網(wǎng)頁(yè)可以計算其MD5值，通過(guò)比較網(wǎng)頁(yè)問(wèn)MD5值是否相等即可作出判斷。因此，本文只討論近似重復網(wǎng)頁(yè)的檢測。大量重復網(wǎng)頁(yè)的產(chǎn)生基本上是通過(guò)用戶(hù)轉載，如一些新聞文章、熱門(mén)事件及經(jīng)典文章等，也就是說(shuō)一般重復網(wǎng)頁(yè)改動(dòng)比較小，如加入引文信息、插入廣告導航等。
本文把相似網(wǎng)頁(yè)的比較轉換成二元分類(lèi)問(wèn)題，即兩張網(wǎng)頁(yè)相似標記為+1(相似)，否則標記為-1(小相似)。SVM(Support Vector Machine)算法在文本分類(lèi)中取得了較好的效果。因此，本文采用SVM算法對每對網(wǎng)頁(yè)分類(lèi)，通過(guò)訓練數據的學(xué)習得到分類(lèi)判別函數，由判別函數對新的數據進(jìn)行計算。
1相關(guān)研究
目前，對重復網(wǎng)頁(yè)檢測問(wèn)題已經(jīng)提出了很多解決方案:有基于字符串比較的方法，即按小同粒度提取指紋，有基于詞頻統計的方法，還有基于聚類(lèi)的方法等。
Border提出將文本中連續的n個(gè)term序列作為文本的一個(gè)特征，稱(chēng)之為二shingleo M-Theobald等人提出的SpotSig算法，以停用詞作為先行詞，提取其后的k個(gè)詞形成一個(gè)個(gè)特征，使用Jaccard計算相似度。
哈工大張剛等人把句號作為一個(gè)提取位置，分別在句號兩邊L/2長(cháng)的詞串構成網(wǎng)頁(yè)的一個(gè)特征。清華大學(xué)吳平博等人提取每個(gè)句子中首尾字符作為特征串。彭淵等人提出將兩篇文檔的最長(cháng)公共子序列(LCS)作為特征碼。
2算法實(shí)現過(guò)程
2. 1特征碼提取
網(wǎng)頁(yè)通常由以下幾部分組成:標題、正文內容、鏈接和廣告等。正文是原始網(wǎng)頁(yè)中真正描述主題的部分。本文采用通用網(wǎng)頁(yè)正文抽取算法州提取網(wǎng)頁(yè)的正文內容，網(wǎng)頁(yè)中其余部分當作噪音過(guò)濾掉。
從長(cháng)段落中提取特征碼，可以減少一些次要特征，使計算更簡(jiǎn)潔。長(cháng)段落定義:段落的長(cháng)度要大于設定的閾值或以句號、問(wèn)號、感嘆號分割得到的句子數大于設定的閾值。
提取出長(cháng)段落后，以逗號、句號、感嘆號和問(wèn)號分割得到每個(gè)句子，提取每個(gè)句子首尾各L/2個(gè)字作為特征碼;把各個(gè)特征碼按序組成特征串，該特征串代表了該篇文檔。
2. 2相似度計算
在比較特征串差異性的基礎上得到網(wǎng)頁(yè)的相似度。目前，比較文本之問(wèn)差異算法主要有兩大類(lèi):一類(lèi)是基于最短編輯距離算法;一類(lèi)是基于最長(cháng)公共子串算法。最短編輯距離算法是以字符串八變成另一個(gè)字符串B的過(guò)程中，通過(guò)插入字符、刪除字符、替換字符等操作的次數表示兩個(gè)字符串的差異，數值越小字符串的差異越小算法表示字符串八和字符串B的最長(cháng)公共子串長(cháng)度，數值越大字符串的差異越小。
通用的做法是根據以上計算出的相似度數值，作一些規范化處理后與閾值比較。但是在現實(shí)中閾值的設定往往是依靠經(jīng)驗來(lái)設置的，因此很難設定準確，這樣就有誤差。本文采用了監督學(xué)習算法，通過(guò)學(xué)習得到的判別函數來(lái)判斷文檔是否相似，避免了人為設定閾值帶來(lái)的風(fēng)險。
2. 3支持向量機(SVM )
2. 3. 1 SVM簡(jiǎn)介
支持向量機是一種二元分類(lèi)模型，它的基本模型是定義在特征空間上的問(wèn)隔最大的線(xiàn)性分類(lèi)器。在重復網(wǎng)頁(yè)檢測應用中，我們把每對網(wǎng)頁(yè)中計算出的特征定義如過(guò)程中，通過(guò)插入字符、刪除字符、替換字符等操作的次數表示兩個(gè)字符串的差異，數值越小字符串的差異越小算法表示字符串八和字符串B的最長(cháng)公共子串長(cháng)度，數值越大字符串的差異越小。
通用的做法是根據以上計算出的相似度數值，作一些規范化處理后與閾值比較。但是在現實(shí)中閾值的設定往往是依靠經(jīng)驗來(lái)設置的，因此很難設定準確，這樣就有誤差。本文采用了監督學(xué)習算法，通過(guò)學(xué)習得到的判別函數來(lái)判斷文檔是否相似，避免了人為設定閾值帶來(lái)的風(fēng)險。
2. 3. 2操作流程
SVM在重復網(wǎng)頁(yè)檢測應用中的大致流程，主要分為訓練階段和測試階段。訓練階段主要從預先給定的數據集中學(xué)習并建立分類(lèi)器，得到判別函數。因此，訓練數據的好壞對于分類(lèi)器的性能至關(guān)重要。測試階段用來(lái)分類(lèi)未知結果的數據集，可以判斷出文檔集中與輸入文檔重復的文檔，即把文檔集中每個(gè)文檔與輸入的文檔使用判別函數計算
2. 4算法描述
本文算法大致分為3大步:提取特征串、衡量指標和構造分類(lèi)器。
3結語(yǔ)
本文提出一種使用機器學(xué)習的方法檢測網(wǎng)頁(yè)是否重復，通過(guò)訓練數據構造SVM分類(lèi)器。提取網(wǎng)頁(yè)特征串，計算兩個(gè)特征串的相似度，使用SVM判別函數計算。實(shí)驗表明:加入兩個(gè)網(wǎng)頁(yè)間的長(cháng)度差異值能提高算法的準確率和查全率。
【基于SVM的重復網(wǎng)頁(yè)檢測算法分析論文】相關(guān)文章：
期中檢測質(zhì)量分析報告01-14
期末檢測質(zhì)量分析總結09-30
案例分析論文11-27
案例分析論文07-15
對于計算機網(wǎng)絡(luò )安全的入侵檢測技術(shù)分析論文11-01
小學(xué)期中檢測分析報告范文07-10
案例分析論文[優(yōu)選]07-17
【實(shí)用】案例分析論文07-17
- 相關(guān)推薦