基於網絡拓撲的主題信息採集方法
2023-10-06 07:18:59 1
專利名稱：基於網絡拓撲的主題信息採集方法
技術領域：
本發明涉及基於網絡拓撲的主題信息採集方法，屬於網絡安全領域。
背景技術：
隨著信息網絡化的日益普及，網際網路上的信息與日倶增，巨大的潛在價值
蘊含在這些海量異構的Web信息資源中。網際網路方便快捷的信息發布方式以及 受眾互動的交流平臺，使得網絡已經超越傳統媒體，成為實時信息獲取的主要 方式。新聞事件通常最早出現在網際網路上，並在網絡中引起討論。
如何有效地提取並利用網絡信息成為一個巨大的挑戰。搜尋引擎通過査詢 的方式為用戶提供快捷有效的信息獲取途徑。網絡信息採集系統為搜尋引擎從 全球資訊網上下載網頁，是搜尋引擎的重要組成部分(J. Cho， Crawling the web: Discovery and Maintenance of Large-Saled Web Data, Computer Science, 2001.)。通用寬度優先(BFS)採集系統在完成當前層次的搜索後，才進行下一 層次的搜索，覆蓋面廣，往往包含用戶不關心的信息。基於特定話題主題信息 採集系統很好的解決了這個問題。主題信息採集系統根據既定的抓取目標，採 用網頁分析算法，有選擇的訪問相關連結，獲取所需要的信息，它的目的是為 面向主題的用戶查詢準備數據資源(周立柱，林玲，聚焦爬蟲技術研究綜述， 計算機應用，2005， 25(9) : 1965-1969.)。
Jyh-Jong Tsay等(Jyh-Jong Tsay, Chen-Yang Shih, Bo-Liang Wu. Auto Crawler: an Integrated System For Automatic Topical Crawler. Computer and Information Science, 2005. Fourth Annual ACIS International Conference on 2005: 462-467.)在寬度優先搜索的基礎上，使用了相關反饋併合理設置隧道長度，使採集系統
儘早脫離不相關區域，挖掘隱藏不相關連結後的相關內容。JamaliM.(JamaliM.， Sayyadi H., Hariri B.B.， et al. A Method for Focused Crawling Using Combination of Link Structure and Content Similarity. Web Intelligence, 2006. IEEE/WIC/ACM International Conference on, 2006: 753-756.)結合連結結構及文本相似性處理URL， 將URL權值定義為網頁相似性與URL鏈入鏈出度之和的乘積，是後效性的URL 處理方式。汪濤、樊孝忠(汪濤，樊孝忠.連結分析對主題爬蟲的改進.計算機 應用，2004， 24(B12): 174-176.)在使用向量空間模型的基礎上，通過對連結 進行物理結構及邏輯結構分析過濾URL，以略微降低查全率為代價，追求更高的 査準率。
通用的主題信息採集系統，將同一網頁中提取的URL不加區分地對待，保 留了較多不相關的連結，且無法降低相似性判決錯誤帶來的影響。
發明內容
本發明目的在於避免上述現有技術中的不足之處而提供一種基於網絡拓撲 的主題信息採集方法，本發明根據網際網路拓撲處理URL，對URL進行連結分析， 根據無標度網絡特徵修正權值，並進行了隧道調整。同時根據主題熱度訪問已 採集主題，獲取其回覆信息。
本發明的目的可以通過以下技術方案來達到
基於網絡拓撲的主題信息採集方法，包括如下步驟
a、 從搜尋引擎獲取種子網頁集合；
b、 對種子網頁集合中的每篇網頁根據主題詞進行分詞，表示為向量集合， 提取出URL，初始化未訪問URL隊列；
c、 選擇未訪問URL隊列，採集相應網頁，計算採集網頁與種子網頁集合的相似性；
d、把採集網頁與種子網頁集合的相似性與設定的閾值進行比較。
所述的步驟d具體包括
如果相似性大於設定的閾值，
1) 從網頁中解析出URL，去重後插入未訪問URL隊列，比較父URL與子URL 的路徑關係，給子URL分配不同的權值；
2) 計算子URL的連結權，子網頁i對父網頁j'的連結加權係數為 /滅,， +々叫，其中，w 為不同的URL路徑權值， >叫為歸一化的錨文本
關鍵詞頻率；
3) 對子URL的加權值修正，修正後的權值如下
其中，"為網頁!'的入度，^^,D)是父網頁與種子集合的相關性，"《是網 頁/對父網頁的連結加權係數，"00= 為主題網頁的偏向概率，A為父網
/
頁引用的有效連結數；
如果相似性不大於設定的閾值，根據URL與種子集合的距離設置隧道長度
內。隧道長度為s啤(!')-如orf4^1， y oor是向下取整，cr為初始深度參數常量，"(0
為種子集合至網頁!'的連結深度。若URL的隧道長度大於0，子URL處理方法與 相似性大於閾值的情況相同，反之，減少所有子URL權值。 所述的給子URL分配不同的連結權重具體包括為
1)子URL包含父URL，則子網頁處於父網頁的下級目錄中，子網頁的主題是 父網頁主題的擴展和延伸，子URL分配的權值為^2) 子URL與父URL具有相似的路徑，子網頁與父網頁目錄深度和文件夾長 度相同，新主題是前期或跟蹤報導，子URL分配的權值為r;
3) 子URL為背景插圖、廣告等冗餘連結，子URL分配的權值為A; 其中0.4<t<0.6。
本發明基於網絡拓撲的主題信息採集方法還可以為如下步驟實現
a、 從搜尋引擎獲取種子網頁集合；
b、 對種子網頁集合中的每篇網頁根據主題詞進行分詞，表示為向量集合， 提取出URL;
c、 將已訪問隊列的URL進行模板匹配，當網頁包含回覆信息時，根據主題 熱度，優先選取熱度高的主題URL獲取新回復；
主題熱度為&formula see original document page 8
其中〖為主題的平均回復時刻，即活躍時間點；n為初始時刻到當前時刻該 主題的總回複數目，"、"為常數；0<"<1，"是偏向概率的加權指數；"決定 了主題熱度函數的平滑程度。
下面詳細介紹本發明的具體方法與步驟
首先獲取種子網頁。根據聚焦關鍵詞，訪問各搜尋引擎，獲取前w條記錄， 作為聚焦的初始連結。抓取初始連結的源文件，得到種子網頁集合 z^〈a,a,zv.a〉。對集合中的每篇網頁a，提取主題信息進行分詞，去調無意 義的助詞、副詞和停用詞，表示成文檔向量形式。若文檔a包含的詞條為 〈,a，^J"〉，則對應的"維文檔向量為〈W,^,^...1^〉，其中^詞條J'的權重。、
採用經典的7Fx/I)F定義。/Z^根據文檔總數增量更新。種子網頁集合被映射成 了文檔向量集『=化,2,3.., 〉。從種子網頁集中解析出的11化，賦予初始權值l，加入採集系統的搜索隊列，採集時優先搜索較高權值的連結。
新抓取到的網頁，經預處理及分詞後，轉化成詞條向量，計算新網頁與種 子網頁集合的相似性。文檔間的相似性使用文檔向量夾角的餘弦來度量，兩網
頁A.,";，它們之間的相似性為咖formula see original document page 9。種子網formula see original document page 9
頁集合"，新網頁r，新網頁與種子網頁集的相似性為該網頁與網頁集合所有網 頁相似性的平均值咖^1)〉=丄|>—7,^〉。相似性較高的網頁，在向量空間中
的夾角越小，傾向於描述同一話題，反之，相似度越低的網頁，屬於不同話題 的概率越大。若網頁與種子網頁集合的相似度高於門限值，則把該網頁加入種 子集合。
對網頁中解析出的URL進行連結分析過濾URL。 一篇網頁中引用的連結所指 向的網頁，稱為該父網頁的子網頁。父網頁中解析出的URL，其結構反映了子網 頁與父網頁的關係，視以下幾種情況分配不同權值(權參量為^).4"<0.6):
(1 )子URL包含父URL，如父URL為"http :〃mil\. news\. sina\. com\. cn/"， 子URL為"http:〃milVnewsV sina\. comV cn/\wAd{4}-\d{2}-\d{2}Ad+\. html"，或"hUp:〃mil\.news\. sina\. com\. cn八d(4)—\d{2}—\d{2}Ad+\. html"，則子網頁處於父網頁的下級目錄中。子網頁的主題是父網頁主題的擴展 和延伸，子URL分配權值"
(2) 子URL與父URL具有相似的路徑。子網頁與父網頁目錄深度和文件夾
長度相同，新主題是前期或跟蹤報導，分配權值"
(3) 背景插圖、廣告等冗餘連結，分配權值A。同時，較多與主題相關的URL，連結附近一段文本中都包含聚焦關鍵字。因 此網頁/對父網頁乂的連結加權係數為/滅力=， +>叫，其中，戸 為上述3
種不同的URL路徑權值，/r叫為歸一化的錨文本關鍵詞頻率。
在連結分析的基礎上，對URL加權、排序，根據URL權值選擇連結加入未 訪問URL隊列。全球資訊網具有無標度網絡的特徵，網頁或站點作為網絡的節點， 連結作為網絡的邊，網絡具有冪率的度分布(SEN QIN， GUAN-ZHONG DA工， YAN—LING LI， Design and Implementation of Web Hot—topic Talk Mining Based
on Scale—free Network, Proceedings of the Fifth International Conference
on Machine Learning and Cybernetics, 2006， pp. 13-16.)。無標度網絡的 成長和優先吸附原則，使得那些包含連結數較多的網頁越可能獲得新連結。新 加入網絡的主題連結到已存在主題的偏向概率與主題包含的連結數成正比。相 似性判斷失誤，會將不相關的網頁歸入聚焦話題，僅靠連結分析不能有效地過 濾掉這些網頁中抽取出的連結。但這些錯誤聚焦的網頁，通常包含的有效連結 數較少。因此使用無標度網絡的偏向概率對URL加權，降低了這些判決失誤網 頁中抽取出的連結的權值，提高了查準率。在pagerank算法基礎上，兼顧相關 性計算，連結分析及無標度網絡特性的影響，修正後的加權值如下-
其中，"為網頁/的入度，w^(K，D)是父網頁與種子集合的相關性，//^,,是 網頁f對父網頁的連結加權係數，為主題網頁的偏向概率，A為父
網頁引用的有效連結數。w'—^")是URL權值的重要部分，相似性的閾值決定著 子URL的取向。一篇網頁的內容與聚焦話題相關，其解析出的子URL與話題相關的可能性
較大，反之，子URL傾向於描述新的話題。相關性較高的網頁，可能引用了大 量的推薦連結，使得抽取出的子URL並非屬於聚焦話題，但由於其繼承了父網 頁的相關性而權值較高。抓取這些子URL，將會得到過多不相關的內容，影響系 統性能。因此，抓取由同一父網頁解析出的子URL時，若連續數次均得到話題 無關的信息，則減小所有子URL權值。
主題網絡中，從一相關網頁到另一相關網頁的路徑中可能包含不相關的區 域，使得相關的主題網頁隱藏在無關的連結中，這稱為隧道現象。與種子集合 相似性較低的網頁，在經過多級連結後，可能連結到相似性高的網頁。忽略相 似性低於閾值的網頁中抽取的URL，將會失去隱藏在這些網頁後的相關連結，獲 得的主題減少。對不相關網頁設定適當的緩衝，提高主題信息採集系統的查全 率。因此採用原子模型來分配緩衝的連結跳數。種子集合是話題聚焦的依據， 作為原子核，原子核不斷更新。從種子集合中提取的URL，作為核外電子。同一 URL可能有多個入鏈，與種子集合的最小距離作為其的連結深度。處於同一深度 的URL視為相同能級。URL的深度越小，越靠近原子核，受到原子核的束縛力越 大，通過其獲得相關主題網頁的概率較大，設置較大的緩衝級數。相反，URL深 度越大，掙脫原子核束縛逃逸的概率也較大，不易獲得聚焦主題。緩衝跳數(即
隧道長度)的設定為s譁(一W離f4^，其中w印(/)為網頁/的緩衝網頁跳數，
是向下取整，C7為初始深度參數常量，"(O為種子集合至網頁Z'的連結深度。若不
相關網頁中的URL的緩衝跳數等於0，且減小該網頁中所有子URL權值。
已訪問的主題URL並不釋放，加入已訪問URL隊列。對URL進行連結模板 匹配，若網頁為所關注新聞評論、電子公告牌、博客等帶回復的信息，則根據主題熱度選取URL獲取熱門度大的主題的新回復。考慮到那些具有較多回復的
主題帖子，吸引了大眾興趣，它們獲得回復的概率也越大；同時隨著時間的推 移，過時的主題帖子獲得的回覆減少，吸附力逐漸趨於O。定義主題熱度如下
Ae鄰)=("+1)" e-如,"t" " °
其中f為主題的平均回復時刻，即活躍時間點，"為初始時刻到當前時刻該 主題的總回複數目，a、 / 為常數。0<"<1，"是偏向概率的加權指數。-決定 了主題熱度函數的平滑程度，-越小，越能反應一些細節，/ 越大，函數越平緩。 由於平緩的函數更能估計出主題未來的回覆趨勢，-一般大於2。
主題的熱度通常介於0到30之間，大於15的主題可認為是熱門主題，選 擇已訪問隊列時，優先選擇熱門度高的新聞評論、電子公告牌或博客主題URL。
本發明相比現有技術具有如下優點
(1) 對URL進行連結分析，過濾冗餘及無關連結，節省系統資源。
(2) 使用無標度網絡的偏向概率修正URL權值，以充分網際網路信息聚集的 特徵，減少相似性判決錯誤但來的影響。
(3) 對URL進行相關反饋，使系統儘快脫離不相關區域，提高準確率。
(4) 使用主題熱度評價帶回復的主題，使系統時間主要分配在熱點主題上。
圖1為整個方法的工作流程圖2為主題信息採集系統與BFS採集系統的查準率比較圖3為主題信息採集系統與BFS釆集系統的相關主題採集率比較圖4為連結分析與未連結分析的査準率比較圖；圖5為不同權值下的査準率比較圖6為相似性反饋前後的查準率比較圖。
具體實施例方式
主題信息採集系統的性能通過查準率來衡量。查準率是獲得相關主題網頁
精度的度量，若M為捕獲主題總數，r為所獲取網頁中的相關主題數，則查準
率為;^&/^ = ^。通過對關鍵字"北京奧運"聚焦，抓取了上百個網站的多
份主題網頁，比較主題信息採集系統與通用採集系統的相關主題採集效率及不
同系統參數對主題信息採集性能的影響(權參量z取0.5)。如圖1所示，為基於 網絡拓撲的主題信息採集方法工作流程圖，如圖2至圖6所示，的結果均為多 次仿真數據的平均值，由於網絡更新快，信息採集的準確率與網站結構有關， 為了保證可比較性，主題採集系統的種子集合與BFS採集系統的初始隊列一致。
圖2為主題信息採集系統與BFS採集系統的查準率隨抓取網頁總數的變化。 從搜尋引擎獲取主題採集系統的種子網頁集及BFS的初始URL隊列，連續抓取 10000多份網頁。圖3為對應的相關網頁採集率。可以看出，本文所提的主題採 集系統査準率明顯高於BFS採集系統，且隨著收集網頁數的增多，BFS相關主題 採集緩慢，査準率降低至40%以下，而主題採集系統仍維持在70%以上。
圖4反映了連結分析對主題採集系統査準率的影響。初始種子網頁集為10， 抓取3500份網頁。可見，未進行連結分析，採集了大量主題網頁中的無效及冗 餘連結而影響了系統的性能，在抓取2500網頁後査準率已降至0. 6以下。
圖5為査準率在不同加權方式下隨採集網頁數的變化。基於網際網路拓撲的 權值分配方式查準率較pagerank權值高，降幅更平緩。而等增益權值分配，在 採集初期査準率較高，但隨著系統的運行，片面追求最高的相似性，極易陷入 局部最優，査準率迅速降低。圖6是相似性反饋前後査準率的比較。相似性反饋使系統在陷入不相關區 域後，能較快地退出抓取誤區，防止性能進一步惡化。
下表l是聚焦不同話題，選取10個初始連結，抓取5000網頁時，主題採 集系統與BFS採集系統的查準率。
表1不同話題的査準率
主題採集系統BFS採集系統
中國大飛機項目0.380.071
神舟六號0.650.12
汶川地震0.760.28
筆記本計算機0.730.1權利要求
1. 基於網絡拓撲的主題信息採集方法，其特徵在於包括如下步驟a、從搜尋引擎獲取種子網頁集合；b、對種子網頁集合中的每篇網頁根據主題詞進行分詞，表示為向量集合，提取出URL，初始化未訪問URL隊列；c、選擇未訪問URL隊列，採集相應網頁，計算採集網頁與種子網頁集合的相似性；d、把採集網頁與種子網頁集合的相似性與設定的閾值進行比較。
2、根據權利要求l所述的基於網絡拓撲的主題信息採集方法，其特徵在於 所述的步驟d具體包括如果相似性大於設定的閾值，1) 從網頁中解析出URL，去重後插入未訪問URL隊列，比較父URL與子URL 的路徑關係，給子URL分配不同的權值；2) 計算子URL的連結權，子網頁/對父網頁y的連結加權係數為 ， + >叫，其中，， 為不同的URL路徑權值，加仏為歸一化的錨文本關鍵詞頻率；3) 對子URL的加權值修正，修正後的權值如下其中，/7為網頁f的入度，如^,D)是父網頁與種子集合的相關性，//《是網頁/對父網頁的連結加權係數，7(0= 為主題網頁的偏向概率，A為父網頁引用的有效連結數；如果相似性不大於設定的閾值，根據URL與種子集合的距離設置隧道長度 內。隧道長度為^^) = /。^(4^， ^。r是向下取整，a為初始深度參數常量，"(/)為種子集合至網頁/的連結深度；若URL的隧道長度大於O，子URL處理方法與 相似性大於閾值的情況相同，反之，減少所有子URL權值。
3、 根據權利要求2所述的基於網絡拓撲的主題信息採集方法，其特徵在於 所述的給子URL分配不同的連結權重具體包括為1) 子URL包含父URL，則子網頁處於父網頁的下級目錄中，子網頁的主題是 父網頁主題的擴展和延伸，子URL分配的權值為n2) 子URL與父URL具有相似的路徑，子網頁與父網頁目錄深度和文件夾長度相同，新主題是前期或跟蹤報導，子URL分配的權值為"3) 子URL為背景插圖、廣告等冗餘連結，子URL分配的權值為^其中0.4<t<0.6。
4、 根據權利要求l所述的基於網絡拓撲的主題信息採集方法，其特徵在於包括如下步驟a、 從搜尋引擎獲取種子網頁集合；b、 對種子網頁集合中的每篇網頁根據主題詞進行分詞，表示為向量集合， 提取出URL;c、 將已訪問隊列的URL進行模板匹配，當網頁包含回覆信息時，根據主題 熱度，優先選取熱度高的主題URL獲取新回復；主題熱度為= (" + 1)、如-如,〖=t,, / ";/=1其中？為主題的平均回復時刻，即活躍時間點；"為初始時刻到當前時刻該主題的總回複數目，"、/ 為常數；0< <1，"是偏向概率的加權指數；/ 決定 了主題熱度函數的平滑程度。
全文摘要
本發明涉及一種基於網絡拓撲的主題信息採集方法。它是從搜尋引擎獲取初始網頁集，經淨化、分詞和去停止詞後，表示成向量集合，使用向量空間模型計算文本相似性。利用網絡結構，對抽取出的URL先進行連結分析，通過URL的目錄層次過濾連結，再根據網絡的無標度性，修正URL的權值，進行優先吸附選擇。同時反饋不相關的主題區域，並通過URL與種子集合的距離設置不相關URL的緩衝區長度。對採集到的主題計算其熱度，以此選擇主題獲取其新的回覆。
文檔編號G06F17/30GK101441662SQ20081022758
公開日2009年5月27日 申請日期2008年11月28日 優先權日2008年11月28日
發明者雲 劉, 司夏萌, 立 張, 張彥超, 張振江, 勇 李, 波 沈, 菲 熊, 輝 程, 凡 賈 申請人:北京交通大學