基于背景的Web廣泛主題發現方法

摘要：提出了一種主題背景的概意，認為Web上的所有內容都有一個背景分布，通過此背景分布可以發現Web廣泛主題：主要介紹了幾種基于背景的廣泛主題發現方法，同時也指出這些方法的不足和發展方向。

關鍵詞：背景 廣泛主題 噪聲 過濾

中圖分類號：TP393 文獻標識碼：A 文章編號：1002-2422(2010)02-0080-02

背景信息方便了從互聯網上提取知識，例如：(1)在搜索引擎中使用Web背景鏈接信息，能夠縮小查詢范圍，快速定位到用戶所需的知識；(2)門戶網站通過識別和區分這些背景，可以更有效地組織目錄層次，使得互聯網的自動分類成為可能；(3)研究和發現這些背景可以深入了解互聯網的進化過程。基于鏈接分析的背景分析的基礎是將Web看作有向圖G=。v是指頂點集，每個頂點表示Web上的一個頁面，E是指邊集，每個表示頁面間的鏈接。通過分析圖內蘊涵的背景鏈接結構特征和語義關系來發現背景。圖1是背景分布抽象圖。

1 基于頁面重要性分析的PageRank算法

PageRank算法是建立在基于重要度傳遞關系構造的機游動模型上的。基本思想是：如果存在從頁面p到的鏈接，頁面p的作者含蓄地將頁面p的部分重要度賦予q，用戶在Web上的隨機漫步(即有兩種途徑進入頁面p)，或以概率d隨意地選擇p，或是以1-d的概率從沿著其他網的鏈接中到達頁面p。該算法的收斂速度較快，收斂過程可以在不超過100次的遞歸內完成。PageRank算法是一個著名的頁面重要性分析算法，且與主題無關。有學者認為用戶瀏覽的游動模型是基于主題的：選擇任意一個與自己感興趣的主題相關的頁面進入，然后沿著鏈接到達與該主題相關的其他頁面。根據這一思想，算法可以發現與主題相關的背景，但是這種算法只能發現一個背景，即確定大于閾值的頁面是背景的成員，而小于閾值的頁面不屬于社區。PageRank算法中，假設Web上有一個隨機的瀏覽者，這個隨機的瀏覽者從一個任意給定的頁面出發，按照頁面上的鏈接前進，在每一個頁面，瀏覽者都有可能不再對其頁面的鏈接感興趣，從而隨機選擇一個新的頁面開始新的瀏覽，對于某一網頁A，設定一個名為Pagerank的值表示瀏覽者訪問到頁面A的概率。系統全局地為每個頁面計算一個Pagerank的值，作為頁面的質量評分。評價一個網頁的價值僅僅看被鏈接的網頁的數量是不夠的，因為如果一個網頁被大量低質量的網頁鏈接不能表示它就比一個被少量高質量網頁鏈接的網頁質量高，所以PageRank算法采取了迭代的思想，即在測度每個鏈接到特定網頁的鏈接時，要考察鏈接起點網頁的質量。

通過PageRank算法，可以很好的衡量網頁的重要性，從而可以決定一個頁面是否為背景的成員，從而達到發現廣泛主題的目的。

2 基于共引用與共耦合關系的背景發現方法：HITS技術

hub／authority方法的基本思想是：Web頁面可分為兩種類型，即目錄型頁面和權威頁面。權威頁面是指人們公認的在某一主題上內容權威的頁面，中心頁面是指頁面上有很多指向權威頁面鏈接的頁面。中心頁面與權威頁面因此形成一個相互加強的關系：好的目錄型頁面指向許多好的權威頁面，而好的權威頁面被許多好的目錄型頁面所指。這種關系將Web頁面描述成一個稠密的二分圖，權威型網頁對于一個特定的檢索，能提供最好的相關信息，目錄型網頁提供很多指向其它高質量權威型網頁的超鏈接。

此方法可以發現特定主題的權威頁面，從而找到廣泛主題背景。3基于完全二分圖背景核的方法

基于完全二分圖核的算法是建立在Web頁面上集中頁面與權威頁面的二分圖關系上的。從二分有向圖的角度對互聯網上的廣泛主題給出了一種明確的定義描述。根據隨機二分圖的理論，一個足夠大而稠密的隨機二分圖將以很高的概率包含一個完全二分有向圖，那么如果將某個包含廣泛主題的網頁的鏈接結構看作一個大而稠密的二分有向圖，則背景的核就可以用一個完全二分有向圖來表示。具體到互聯網環境中，可以對上述概念有如下直觀的理解：如果在互聯網上存在一個某種主題的背景，那么這種二分的核必將包含在其中。

基于該方法提取的Web背景核心是主題相關的，且通常不是已存在的Web目錄的部分，故反映了核心是Web背景的自然表現。但該方法提取的是背景核心，無法確定背景的邊界，且無法確定層次化的背景樹。

4 基于背景內容過濾的web廣泛主題發現方法

Web廣泛主題的簡潔性將主題的長度限制在詞和詞組級別，時效性則使得一些主題詞匯因為尚未收錄進詞典而被切分成碎片。無論這二者中的任意一種，都能夠通過切分結果的拼接獲得。因此，切分結果的拼接將作為廣泛主題發現的基礎。

在用語習慣上，對于時常談及的主題，人們習慣用縮略語代替過于冗長的全稱，大部分重要詞串實際上通過較少次數的拼接就能獲取。為保證效率，限制詞語拼接不多于三次。對于少數三次以上拼接才能獲取的熱點信息。

單純的切分詞拼接將引入大量無意義串，為獲得精簡的候選串，拼接過程需要強大過濾功能的支持，統計表明，無意義串大致分為如下三類：常見無意義串、規則性強的無意義串以及普遍存在的背景噪聲。為此制定了多級過濾策略：(1)停用詞過濾；(2)規則過濾；(3)噪聲過濾。在生成候選串之后，還需要一些處理以優化提取結果的質量，如結果收錄和結果排序。

其方法根據Web廣泛主題的特點，以背景內容為基礎進行多級過濾的拼接，經過優化處理后，得到最終發現的結果，在網絡真實語料上，此方法取得了良好的發現效果。

5 結束語

幾種基于背景的廣泛主題發現的方法，每一種方法都是從背景的某一個角度去考慮。PageRank和HITS是從頁面間的社會關系考慮，完全二分圖核的算法是從背景的圖結構考慮，最后一種方法是從背景內容來考慮。

盡管能夠成功地從Web中發現廣泛主題，但是仍然存在著一些問題，許多頁面包含多個主題，以頁面為基本單位作為頂點，會建立不正確的頁面間的關系，降低結果的準確度。應該考慮利用Web頁面的內部結構將頁面劃分為基于單個主題的塊。在塊的粒度上利用鏈接結構發現背景。另外，頁面內包含了許多垃圾鏈接，不考慮影響，也會降低結果的準確度。應該考慮研究垃圾鏈接的模式，對進行計算的鏈接做清洗，以提高精度。背景內的頁面由于基于同一主題，具有一定的內容相似性。而且，上述所有算法發現的背景都是“平”的，而非“層次”化的，即不能發現子背景。應該考慮背景的層次化特性，設計發現包含子背景的方法。每種方法考慮的是背景的一種性質，具有一定的片面性，應該考慮背景的多種結構特性來發現Web廣泛主題。