[發明專利]一種基于貪心策略和啟發式算法搜索候選類別的方法

在審

• 申請號: 201310405219.5
• 申請日: 2013-09-06
• 公開（公告）號: CN103488707A
• 公開（公告）日: 2014-01-01
• 發明（設計）人: 何力;賈焰;楊樹強;周斌;韓偉紅;李愛平;韓毅;李莎莎;丁兆云
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京科億知識產權代理事務所(普通合伙) 11350
• 代理人: 湯東鳳

技術領域

本發明屬于互聯網技術領域，具體涉及一種基于貪心策略和啟發式算法搜索候選類別的方法。

背景技術

以互聯網為代表的信息革命極大改變了人們的生活、生產方式，社會對網絡信息系統的依賴也日益增強。然而，互聯網的自由性、開放性、迅捷性以及低廉的成本和高額的利潤同時也使其成為了有害信息發育繁殖的沃土。各種令人不安的信息如湍急暗流隱藏在互聯網信息大潮下，包括色情、邪教、賭博、毒品、虛假新聞、宣揚暴力在內的各種有害信息充斥于互聯網上。因此，對網絡和信息的安全管理與控制尤為關鍵。

基于互聯網分類目錄的網絡訪問控制是網絡安全管理的一種重要技術手段，通過建立全面、精確的互聯網分類目錄，可以實現快速、精細的網絡訪問控制。互聯網分類目錄按照一個概念或主題類別層次將海量網頁信息組織為網絡資源分類目錄，以更好地搜索、訪問和管理這些網絡資源，例如開放目錄專案(Open?Directory?Project，簡稱ODP目錄)、雅虎目錄(Yahoo!Directory)等。要自動構建網絡資源目錄，就需要實現對互聯網上未知類別信息的分類，這里的信息類別一般被組織為一個層次式結構，典型的是一棵樹(tree)或者有向無環圖(Directed?Acyclic?Graph)，這種類別層次一般規模巨大，其類別數目可以達到數千、甚至數萬之多。面向網頁的大規模層次分類技術(large?scale?hierarchical?classification)就是研究如何按照這樣一個規模巨大的類別層次對網頁進行準確分類，因此，大規模層次分類技術是構建互聯網分類目錄的基礎，是構建健康、和諧的互聯網環境的重要技術手段，同時也是很多網絡應用的基礎，包括綠色上網、網絡信譽管理、安全過濾等。

類別層次規模巨大是大規模層次分類技術面臨的一個主要挑戰，大規模層次分類問題求解方法的不同主要體現在對這一挑戰性問題的處理策略上，目前有三種處理策略：全局處理策略(overall-conquer)、分而治之的策略(divide-and-conquer)和化繁為簡的策略(reduce-and-conquer)。整體處理策略將所有類別作為一個整體，在整個數據集上進行分類的學習，然后對待分類文檔進行分類。分而治之策略按照類別層次將一個大規模的全局分類問題分解為一個個小規模的局部分類問題，然后分別進行分類的學習，對待分類文檔進行自上而下的分類。化繁為簡的策略通過搜索類別層次中所有與待分類文檔相關的類別，然后在所有候選類別上進行分類的學習和預測，將一個大規模的分類問題降低為一個小規模的分類問題。

采用化繁為簡策略的分類方法：首先根據待分類文檔搜索候選類別，然后根據候選類別的樣本訓練分類器并對待分類文檔進行分類，因此，這種方法又被稱為兩階段分類方法，其核心思想是通過減小分類器學習的類別數目以提高分類準確率。兩階段方法基于這樣一個假設：在一棵大規模類別層次樹中，給定一個文檔，其相關類別數量遠少于不相關類別。兩階段分類方法的優點是通過候選搜索有效減小了數據規模，因此可以靈活的選擇分類方法和分類器，分類準確率比較高，因此在大規模層次分類問題中應用的較為廣泛。但是這種優點是建立在候選類別搜索正確的前提之上的，因為其中的分類依賴于候選搜索的準確性，要確保分類正確，就應當使計算出來的候選類別集合包含待分類文檔的真實類別，因此，候選類別搜索是大規模層次分類中的一項關鍵技術，然而已有的兩階段分類方法并未對候選搜索方法進行深入研究。

發明內容

針對現有技術存在的問題，本發明旨在提供一種基于貪心策略和啟發式算法搜索候選類別的方法，用以于大規模層次分類問題中搜索出包含待分類文檔真實類別的候選類別，它采用評價指標V_k對搜索出的候選類別進行量化評價，且采用貪心策略和啟發式算法得出最大的評價指標V_k值，進而，準確地搜索出候選類別。

本發明提供的一種基于貪心策略和啟發式算法搜索候選類別的方法，用以從測試文檔中搜索出候選類別，其包括以下步驟：

步驟S01、輸入已知信息：提供樣本集合I＝{d₁,d₂,...,d_n}，特征集合F＝{f₁,f₂,...f_m}，類別集合L＝{l₁,l₂,...l_r}；