文檔分類器生成方法和系統的製作方法
2023-06-10 17:19:56 3
專利名稱：文檔分類器生成方法和系統的製作方法
技術領域：
本發明一般地涉及信息檢索(information retrieval, IR)和文本數據挖 掘，更具體而言，涉及能夠進行自動文檔分類的文檔分類器的生成方法和 系統，其通過組合未標註文檔集的潛在數據分布和類別名字典所暗示出的 語義信息來進行高度精確的文檔分類。
背景技術：
當前，可獲得的電子文檔的快速增長使得人們無法透徹了解並有效利 用這大量的信息。如何幫助用戶以有效且高效的方式組織這些信息並找到 感興趣的信息片斷是一項富有挑戰性的任務。
信息檢索(IR)是一種在文檔集合中搜索信息的科學，其可被進-步 劃分為搜索包含在文檔中的一段信息；搜索文檔本身；搜索描述文檔的 元數據；或者在資料庫中搜索文本、聲音、圖像或數據，所述資料庫可以 是關係獨立資料庫或者通過諸如網際網路或內聯網之類的超文本聯網數據 庫。文本數據挖掘一般指的是根據明文文本構造高質量信息的過程，其可 被進一步劃分為文本分類、文本聚類(clustering)、概念/實體提取、文檔 概括等等。由於當前大多數可獲得的信息都被存儲為文本或文檔，因此相 信信息檢索和文本數據挖掘具有很高的商業價值。文檔分類是一種利用來 自預定集合的主題類別來標註(label)自然語言文本的行為，其可被應用 在多種使用IR和文本數據挖掘的情形，例如詞義消歧、文檔組織、文本 過濾和網頁檢索。
由於可用電子信息量的不斷增長，信息檢索和文本數據挖掘的重要性 是顯而易見的。自動文檔分類是用於信息檢索和文本數據挖掘的基礎技術 之一，其在大量電子信息的有效且高效利用方面扮演重要角色。
當前，對於自動文檔分類，基於機器學習(Machine Learning, ML)的方法佔主導地位。基於ML方法的良好性能極大地取決於大量手工標註的 訓練數據。但是，手工標註數據的任務是繁瑣而且昂貴的，對於複雜的文 檔分類尤其如此，其中可能存在成百上千個類別。
為了利用未經標註的數據來提高所訓練的模型的精確性，已經進行了 多種研究。但是，現有方法無法處理沒有訓練集合可用的情況。而且，由 於學習過程過多地依賴於有限數量的訓練樣本，因此分類結果很容易受訓 練集合影響而存在偏見。從而，無法對於真實世界中的系統呈現足夠好的 性能。
本發明的研究尤其與信息檢索和文本數據挖掘中的文檔分類有關，在 這方面現有技術中存在很多研究。基本上，當前流行的自動文檔分類方法 可被分成以下三類監督型文檔分類、半監督型文檔分類和無監督型文檔 分類。它們的實現方法通常包括兩個步驟，即分類器學習步驟和文檔分類 步驟。
監督型文檔分類方法將類別名僅視為符號標註，並且假設無法獲得關 於類別名含義的額外知識以及外部知識來幫助建立分類器。在分類器學習 階段，通過觀察先前已經手工分類(例如由領域專家)出的一組文檔的特 性來利用一般歸納過程自動建立針對類別的分類器。然後，在文檔分類階 段，分類器收集新文檔應該具備的特性，以便將其分類到相應的類別之 下。在先前的研究中已經研製出多種用於歸納構造文檔分類器的不同方 法，其中比較流行的方法包括概率分類器、判決樹、神經網絡、支持向量
機(support vector machine, SVM)和回歸方法。由於關於文檔正確分類的 知識被用於監督分類器學習，因此每個類別需要大量手工標註的訓練樣本 才能進行精確的學習。
為了減少用於訓練數據標註的人為麻煩，提出了半監督型文檔分類方 法，其用於具有較少標註數據的文檔分類。該方法既利用標註的訓練數據 樣本也利用未經標註的訓練數據樣本，其中未經標註的數據被用來改善監 督型學習由於訓練數據不充足而引起的低性能。到目前為止，針對半監督 型文檔分類方法的研究可以粗略分成三類，即生成方法(generative method)、 區麼、方 去(discriminative method)禾卩自學方 去(self-learningmethod)。
生成方法假設從可識別的混合分布(例如高斯混合模型)中生成文檔 實例。混合模型的未知參數可以通過大量未經標註的數據來確定。 一種代 表性的方法是期望最大化(Expertation-Maximization, EM)算法。同時， 利用對未經標註的文檔進行文檔聚類來改善文本分類，其中每個聚類實際 上充當一種"偽混合模型"。聚類過程可被應用到標註的和未經標註的數 據，從而將從這些聚類中提取出的新特徵引入標註的和未經標註的數據的 模式中。
區分方法來源於來自不同類的未經標註的數據之間具有較大差異 (margin)這一思想。基於該假設，直推式SVM利用未經標註的數據擴 展標準的SVM以嘗試通過最小化特定文檔的錯誤分類來最大化"未經標 注的數據差異"。作為SVM —般形式的邏輯回歸模型也被用於半監督型 文本分類。最近，出現了基於圖表示的一系列新型半監督型學習方法，他 們將標註的和未經標註的實例表示為頂點，將實例之間的相似性表示為 邊。
自學方法假設分類器自己的高度信任的預測是正確的。基於該假設得 到兩種代表性方法，即自訓練和協同訓練。自訓練按如下方法實現
(1)少量標註文檔被用於分類器訓練；(2)所產生的分類器被用於分類 未經標註的文檔；(3)在每次迭代中以高度信任選擇新標註的文檔的可 靠集合來重複地重新訓練分類器。在迭代期間，分類器利用其自己高度信 任的預測來自我學習。類似地，日本專利No.2002-133389提供了一種推進
(boosting)機制，該機制利用測試數據的分布來提高具有少量訓練數據 的迭代學習的精確性。對於協同訓練，其實現方式如下:(1)首先，特 徵集被分成兩個充分且有條件地獨立的集合，它們被分別用於訓練兩個分 類器；(2)然後，每個分類器對未經標註的數據進行分類，並選擇若干 可信樣本，用來擴展另一分類器的訓練集合；(3)兩個分類器利用附加 的訓練樣本被重新訓練，並且該過程被重複。
與採用文檔集合中暗示的針對文檔分類的知識的監督型和半監督型學 習方法不同，所謂的無監督型文檔分類方法主要利用類別概念中暗示的知
8識來進行自動文檔分類。該方法無需手工創建訓練文檔，而是主要利用預
定的初始關鍵字列表作為種子，並採用某些自擴展(bootstrapping)機 制。通過將文檔分成若干句子， 一種利用每個類別的關鍵字列表創建訓練 句子集合的方法被提出，隨後，被分類的句子被用於文檔分類。
但是，現有技術存在尚未解決的缺陷。 .首先，對於監督型方法，其需要針對每個文檔集或問題域獲得大量訓 練數據，而為了建立充足的訓練數據，需要花費很高成本。獲得標註數據 通常是很困難的，其非常昂貴並且耗時，因為其需要有經驗的人類標註者 的參與。對於具有成百上千個類別的複雜任務或領域尤其如此。
其次，對於半監督型方法，其文檔分類結果易於受少量訓練數據的影 響而存在偏見。半監督型學習方法的思想在於不僅從標註的訓練數據中學 習，還要採用額外獲得的未經標註的數據中的結構性信息。雖然，訓練數 據的可獲得性問題得到部分解決，但是其過分關註標注的數據集，並且極 大地依賴標註的數據集中所呈現的分布。由於標註數據是稀疏性的，因此 該方法不僅精確度不夠好，而且魯棒性也是個大問題。
另外，對於無監督型方法，其文檔分類結果易受預定的關鍵字列表影 響而存在偏見。在所謂的無監督型方法中，每個類別的類別名或關鍵字列 表充當自擴展機制的種子以用於自動文檔分類。由於該方法極大地依賴於 人為定義的初始關鍵字列表並且不存在偏見控制機制，因此分類結果的精 確性和魯棒性一般都不夠好。而且，初始種子單詞需要手工收集，這對於 複雜任務也是一項繁重而昂貴的任務。
再次，無論監督型方法、半監督型方法還是無監督型方法，它們的自 適應性和可擴展性均較差。通過這三種方法訓練出的分類器是依賴於領域 或文檔集的，即，如果文檔集或領域變化，分類器則需要重新訓練。對於 監督型方法和半監督型方法，這意味著需要額外的人為努力將一定量的文 檔標註為訓練數據。對於無監督型方法，如果領域改變，則需要重新定義 與相應類別相關的初始關鍵字列表。而且，對於改變的領域或文檔集，需 要費力進行額外的學習。
因此，需要新的文檔分類方法和系統，用來提高文檔分類的精確性和可擴展性，尤其針對沒有標註數據可用的情形。
發明內容
鑑於上述現有技術文檔分類方法中所存在的問題，作出了本發明。 本發明提出一種文檔分類器生成方法，其利用目標文檔集的數據分布
知識以及類別名所暗示的語義信息兩者來生成文檔分類器以用於自動文檔
分類，從而提高文檔分類的精確性和可擴展性。該方法尤其適用於沒有訓
練集合可用的情形。
大體上來看，本發明所提出的混合文檔分類器建立方法主要包括三個
步驟(1)初始訓練集合生成；(2)迭代分類器學習；和(3)最終分
類器建立。
首先，在初始訓練集合生成期間，初始訓練集合是在外部知識源的支 持下基於類別名的語義分析而生成的。例如，在一個實施例中，設計出一
種基於描述(profile)的方法，用於建立分類器，其中每個類別具有語義 相關的特徵集，以充當該類別的代表性描述。基於初始分類器，包括肯定 和否定樣本的初始訓練集合(標註文檔)被創建，以用於隨後的迭代分類 器學習。
然後，在迭代分類器學習階段，每次迭代中，來自上次迭代的分類器 分類結果被用於建立這次迭代的訓練集合(選擇高度可信的分類結果作為 標註數據)。然後，從更新的訓練集合(標註數據)中構造新的分類器。 最後，使用新的分類器代替上次迭代的分類器來分類剩餘的文檔。當所有 文檔都被標註、形成的一組分類器收斂或者滿足其他終止條件時，迭代過 程終止。
最後，在最終分類器建立階段，從迭代學習終止後所得到的所有分類 器中選擇最符合預先獲得的文檔聚類結果的分類器，作為最終分類器。由 於本發明假設不存在訓練數據，對於分類器選擇的方案主要利用最大似然 性估計。
需要注意的是，在機器學習過程期間，訓練集合的選擇(包括初始訓 練集合的生成和迭代學習中的中間訓練集合的生成)基於文檔分類結果與聚類結果的對準(alignment)，在此過程中，例如可採用貝葉斯(Bayesian)模型。其目標是要減小由於類別名、外部知識源或迭代分類器學習過程中的噪聲數據所帶來的可能偏見。
具體而言，根據本發明一個方面，提出了一種分類器生成方法，其包
括獲取對象(例如文檔)集合的聚類結果；生成所述對象集合的粗略分類結果以得到粗略分類器；以及用所述聚類結果調整所述粗略分類結果以生成最終分類器。在某些實施例中，粗略分類器的生成可以採取利用訓練集學習出分類器的方式，所述訓練集可以是從外部輸入的人工標註訓練集，或者可以根據領域相關的類別名通過參考外部知識源自動生成。另外，在某些實施例中，通過使得粗略分類結果與預先獲得的聚類結果對準來調整粗略分類結果，該調整過程可以採取迭代方式，通過不斷更新訓練集，從而學習出一組中間分類器，並且可以從這組中間分類器中選擇與聚類結果最匹配的最優分類器作為最終分類器。
另外，根據本發明另一方面，還提出了一種分類器生成系統，其包括獲取裝置，用於獲取對象集合的聚類結果；粗略分類裝置，用於生成所述對象集合的粗略分類結果以得到粗略分類器；以及調整生成裝置，用於用所述聚類結果調整所述粗略分類結果以生成最終分類器。
在本發明中，文檔的聚類結果和分類結果之間的對準分析被執行，並被集成到訓練集合建立以及迭代分類器學習的過程中。這樣一來，來源於類別名和相應語義分析的可能偏見得到控制。其確保了所產生的訓練數據以及最終的分類結果的精確性得以提高
另外，本發明所採用的方法不需要訓練數據或初始預定的關鍵字列表來進行文檔分類。相反，本發明採用在現有外部知識源的支持下對類別名的語義分析(包括用於同現關鍵字(co-occurrence keyword)提取的潛在語義分析)來建立初始訓練集合。由於已有的外部知識源可以覆蓋多個領域，因此當領域或文檔集改變時，本發明的方法可被容易地應用到多個不同的領域/文檔集，從而大大減少額外的標註工作。
另外，本發明所提供的最終分類器建立的機制可以降低分類器由於迭代分類器學習過程中的噪聲數據的存在而引起過大偏見的危險，尤其對於區分分類器(例如SVM、邏輯回歸等)。本發明的另一重要貢獻在於提高了最終文檔分類結果的精確性。
從下面結合附圖的詳細描述中，可以看出本發明的其他特徵和優點。注意，本發明並不限於圖中所示的示例或者任何具體的實施例。
結合附圖，從下面對本發明實施例的詳細描述，將更好地理解本發明，附圖中類似的參考標註指示類似的部分，其中
圖1示出文檔分類系統100的整體框圖，其中具體示出根據本發明實施例的分類器生成子系統10的內部結構；
圖2示出圖1所示文檔分類系統100的工作過程的流程圖3示出圖l所示分類器生成子系統IO中的調整生成裝置103的一個示例的內部結構的框圖4A和圖4B分別是示出圖1所示分類器生成子系統10中的粗略分類裝置102的兩種實現方式400A和400B的內部結構的框圖，其中在圖4A所示實現方式400A中，從外部獲取的人工標註的訓練集被直接用於分類器學習，而在圖4B所示實現方式400B中，訓練集被自動生成以用於分類器學習；
圖5是示出在自動生成訓練集的情況下，圖4B所示訓練集發生單元401B的內部結構的框圖6是示出圖5所示訓練集發生單元中的分類部件504的一個示例的內部結構的框圖7是示出圖5所示在自動生成訓練集的情況下，訓練集發生單元的工作過程的一個示例700的流程圖8是示出圖5所示根據中間分類結果生成訓練集的訓練集產生部件505的一個示例的內部結構的框圖，其中關於文檔集合的聚類結果被用於調整中間分類結果；
圖9示出根據本發明實施例，圖1所示分類器生成子系統10中的調整生成裝置103採取迭代分類器學習的工作過程900的流程圖；以及
圖io是被用於實現本發明的計算機系統的示意性框圖。
具體實施例方式
本發明所提出的分類器生成方法和系統可應用於文本過濾、文檔推薦、搜索結果聚類、網頁搜索和網絡文本挖掘等等。
圖1示出文檔分類系統100的整體框圖，其中具體示出根據本發明實施例的分類器生成子系統10的內部結構。如圖所示，來自文檔庫105的
文檔集合通過文檔聚類裝置107被預先聚類成多個組，並將聚類結果存儲在聚類結果庫104中。聚類結果庫104中所存儲的關於文檔集合的聚類結果將被根據本發明的分類器生成子系統10或者其他信息檢索相關應用所消耗。關於文檔聚類的方法屬於本領域技術人員公知技術，不作為本發明研究的重點，並因此不作贅述。本領域技術人員所知的任意文檔聚類方法都可被用於獲得所需文檔聚類結果。圖l所示根據本發明實施例的分類器生成子系統IO包括獲取裝置101、粗略分類裝置102以及調整生成裝置103。
圖2示出圖1所示文檔分類系統100的工作過程的流程圖。首先，在步驟201處，分類器生成子系統10從文檔庫105獲得將要分類的文檔集合。獲取的文檔集合首先被提供到粗略分類裝置102以進行粗略分類，從而得到粗略分類結果(即粗略分類器)，如步驟202所示。例如，在背景技術中描述的本領域公知的監督型文檔分類、半監督型文檔分類或無監督型文檔分類方法均可被用於實現粗略分類目的。在某些實施例中，例如如下文所述，可以採用訓練集學習分類器的方法生成粗略分類器。根據實際應用需求的不同，可以採用外部輸入的人工標註的訓練集，也可以通過參考來自外部知識源的關於類別名的語義信息自動生成訓練集。關於訓練集的自動生成隨後將詳細描述。
如此同時，在步驟203中，獲取裝置101從聚類結果庫104獲取預先存儲的關於該文檔集合的聚類結果。如本領域技術人員所知，聚類結果能夠反映出關於文檔集合的潛在數據分布，並因此可被用於控制粗略分類結果中可能存在的偏見。關於文檔集合的來自粗略分類裝置102的粗略分類
13結果和來自獲取裝置101的聚類結果都被提供到調整生成裝置103。接下
來，在步驟204中，調整生成裝置103利用來自獲取裝置101的聚類結果對來自粗略分類裝置102的粗略分類結果(即粗略分類器)進行調整，從而生成最終分類器106。關於利用聚類結果調整粗略分類結果的原理及過程，隨後將參考圖3來進一步描述。另外，如下文將描述的，這種利用聚類結果調整粗略分類結果的做法可被擴展為以迭代方式運行，即通過迭代不斷更新中間分類結果，從而產生一組中間分類器，並從中選擇一個最優分類器作為最終分類器。這樣做，可以進一步提高文檔分類的精確性。關於迭代分類器學習的具體描述隨後給出。隨後在步驟205中，已經在步驟201中獲取的文檔集合被提供到所生成的最終分類器106，最終分類器106將集合中的每個文檔分類到至少一個類別，並將分類結果存儲到文檔分類結果庫108中。然後，過程200結束。
圖3示出圖1所示分類器生成子系統10中的調整生成裝置103的一個示例的內部結構的框圖。在該示例中，假設粗略分類裝置102採用基於查詢的方法執行粗略分類，從而粗略分類結果被表示為一系列等級得分。調整生成裝置103利用貝葉斯(Bayesian)推論模型作為對準模型執行粗略分類結果與聚類結果的對準，從而獲得更加精確的分類結果，即得到最終分類器106。這裡應該指出，利用聚類結果調整粗略分類結果的方法並不局限於圖3所示利用貝葉斯推論模型對準的示例，本領域技術人員容易想到其他調整方法也可被類似地應用於此以實現提高分類精確度的目的。
在圖3所示示例中，調整生成裝置103包含先驗概率計算單元301和對準單元302。
首先，在先驗概率計算單元301中，計算對應於粗略分類結果的先驗概率。如前所述，這裡假設粗略分類結果被表示為一系列排序得分。令C表示類別集合，"表示文檔集合。對於文檔《e"和類別。eC，存在排序
得分4《,c」，其指示《屬於c,的概率。從而，該得分被歸一化為
從而，我們可以假設=4《,c,)。
然後，在對準單元302中，基於貝葉斯推論來建立對準模型。令C'表示聚類集合。如果聚類結果顯示文檔被聚類到聚類c^ec'中，則對準
結果被表示為如下後驗概率
formula see original document page 15(等式2)
其中，先驗概率屍(c,械)來源於粗略分類結果。顯而易見，根據統計學原理
可以計算
(等式3)(等式4)
因此，最終的對準模型被表示為
(等式5)
根據等式5所示概率模型，即已實現經過聚類結果調整的最終分類器，該最終分類器相對於等式1所表示的粗略分類器，其文檔分類的精確度更高，並且由於聚類結果調整的引入，可能由於類別名以及語義分析所導致的偏見得到有效的控制。
下面，將參考圖4A和圖4B來進一步描述構成分類器生成子系統10一部分的粗略分類裝置102的內部結構。如前所述，在某些實施例中，可以採用訓練集學習分類器的方法生成粗略分類器。這裡所採用的訓練集可以採用外部輸入的人工標註的訓練集，也可以由系統自動生成。圖4A和圖4B分別給出採用人工標註的訓練集以及自動生成訓練集情況下通過訓練集學習生成粗略分類器的兩個示例。當然，粗略分類器的生成並不局限於訓練集學習，本領域技術人員公知的任何其他分類器生成方法都可被應用於此。
首先，參考圖4A，在該示例中，粗略分類裝置102包括訓練集發生單元401A和學習單元402。訓練集發生單元401A從外部獲取人工標註的訓練集並將其直接提供到學習單元402以用於分類器學習。接著，由學習單元402學習出分類器。關於利用訓練集學習出分類器的過程，屬於本領域公知技術，這裡不作贅述。
參考圖4B，在該示例中，粗略分類裝置102包括訓練集發生單元401B和學習單元402。訓練集發生單元401B與訓練集發生單元401A的不同之處在於訓練集發生單元401B通過參考來自外部知識源404的關於類別名的語義信息來自動生成訓練集。然後，與圖4A相同，自動生成的訓練集被提供到學習單元402以學習出分類器。
下面將參考圖5-8來詳細描述圖4B所示訓練集發生單元401B中自動生成訓練集的過程及原理。
首先，如圖5所示，訓練集發生單元401B包括類別名獲取部件501、詞義消歧部件502、關鍵字生成部件503、分類部件504和訓練集產生部件505。另外，如圖5所示，除了文檔庫105之外，訓練集發生單元401B還需要參考類別名庫403和與類別名相關的外部知識源404來實現訓練集的自動生成。
下面結合圖7來描述圖5所示訓練集發生單元401B的訓練集自動生成過程700。
首先，在步驟701中，類別名獲取部件501從類別名庫403獲取預定的類別名。由於類別名中的單詞可能在不同情形下可能具有不同含義，因此可選地，在步驟702處，詞義消歧部件502可以在外部知識源404的支持下首先對類別名進行詞義消歧。然後，在步驟703中，經過詞義消歧後的類別名被提供到關鍵字生成部件503，以基於所識別出的詞義生成相關關鍵字。這裡，相關關鍵字可能包括與通過語義分析識別出的類別名具有高同現性(co-occurrence)的單詞，還可能包括類別名中出現的關鍵字的同義詞、下位詞或上位詞。這些同義詞、下位詞或上位詞可以從外部知識源404找到。
這裡為了便於理解，給出詞義消歧以及同義詞選擇的一個示例在WordNet中單詞"spam"具有兩個含義，即(1) 一種由碎豬肉製成的的罐頭肉製品，和(2)不想要的電子郵件。我們需要在兩種含義之間進行區分以選擇"spam"對於產品描述分類的同義詞。從而，"spam + —種由碎豬肉製成的的罐頭肉製品"和"spam +不想要的電子郵件"作為兩
16個査詢項被發送到文檔集合(即，所設置的產品描述)。對於前一查詢，得到20個命中；而對於後一査詢，得到100個命中。由於100 > 20，因
此在該分類任務的上下文中，"spam"因該具有第2種含義。因此，來自含義(2)的同義詞，即"垃圾郵件"被選擇。
返回圖7，在步驟704處，所產生的相關關鍵字被提供到分類部件504以用於對文檔集合進行分類，從而獲得中間分類結果(即中間分類器)。然後，在步驟705中，中間分類結果被提供到訓練集產生部件505，從而生成所需訓練集。然後，過程700結束。
圖6示出圖5所示訓練集發生單元中的分類部件504的一個示例的內部結構。在該示例中，基於描述的過濾方法被用於產生中間分類結果，即利用類別名相關關鍵字作為査詢項對文檔集合進行搜索，並選擇命中列表中的文檔標記為相應類別。如圖6所示，在該示例中，分類部件504包括搜索器601和類別標註器602。再次參考圖7中的步驟704，首先，在子步驟7041中，搜索器601接收來自關鍵字生成部件503的類別名相關關鍵字，並將相關關鍵字作為相應類別的代表性描述對文檔集合進行搜索。然後，在子步驟7042中，作為搜索結果的命中列表被發送到類別標註器602。類別標註器602將命中列表中的全部或一些(例如前200個)標註到相應類別，從而完成文檔分類。所產生的中間分類結果隨後被用於訓練集的生成。
一般而言，為了確保所標註的文檔是正確的，通常只有位於命中列表頂部的文檔被選擇。例如，對於產品類別"anti—spam" ， "spam +垃圾郵件"作為相關關鍵字被發送到文檔集合以進行搜索。這裡，"spam"是從類別名(即"anti—spam")識別出的關鍵字，而"垃圾郵件"是從WordNet選擇的同義詞。假設命中列表包括1000個搜索結果，我們可能僅僅選擇前200項作為"anti一spam"產品的代表性產品描述。這裡，假設前200項產品描述擁有人們用來判斷一個產品是否具有anti—spam功能或者是否屬於"anti一spam"類別的所有需要的特徵。
如上所述，在得到中間分類結果(即中間分類器)之後，中間分類結果被提供到訓練集產生部件505以產生訓練集。本領域技術人員公知的任意根據分類器產生訓練集的方法都可被應用於此以實現本發明的目的。但是，這裡為了進一步提高文檔分類的精確性，本發明提出在訓練集的生成過程中，同樣可以採用已知的聚類結果對中間分類結果進行調整(例如，採用貝葉斯對準模型)。圖8示出訓練集產生部件505的一個示例的內部結構，其中關於文檔集合的聚類結果被用於調整中間分類結果。
可以看出，圖8所示結構框圖與前述圖3所示調整生成裝置103的內部結構類似。就是說，在該示例中，訓練集產生部件505採用類似於圖3所示方式對中間分類結果進行調整。關於其具體細節，這裡不再贅述。經調整(對準)後的中間分類結果隨後被提供到訓練集選擇器802，以使得訓練集選擇器802能夠從中選擇所需訓練集。
以上參考圖1-8描述了根據本發明實施例的分類器生成系統10的結構和工作原理。如前所述，為了進一步提高文檔分類精度，利用聚類結果調整粗略分類結果的過程可以採取迭代方式執行。下面將通過參考圖9的流程圖來詳細描述迭代分類器學習。
首先，在步驟901處，在粗略分類結果生成過程中產生的訓練集被獲取，作為初始訓練集。在每次迭代期間，可以使用某種已知的分類器學習方法(例如基於多項式模型的NB (Naive Bayesian))利用訓練集學習出新的中間分類器(步驟902)。然後，在步驟903，新的分類器被用於對文檔庫105中的文檔進行分類，以得到新的中間分類結果。然後在步驟904處，判斷是否滿足迭代終止條件。該迭代終止條件可以由用戶確定。例如，如果在迭代過程中逐步產生的所有中間分類器逐漸收斂，則可以選擇所產生的訓練集變得穩定作為迭代終止條件。或者，例如可以選擇文檔庫105中的所有文檔均已被分類作為迭代終止條件。如果在步驟904處確定滿足迭代終止條件尚未滿足(即步驟904中的"否")，過程則前進到步驟905。在步驟905中，利用本輪迭代的中間分類結果生成用於下次迭代的新訓練集。這裡根據中間分類結果產生新訓練集的方法可以類似於圖8所示的方法。如上所述，中間分類結果基於對準模型(例如貝葉斯對準模型)被與聚類結果對準。與圖8所示方法的主要不同之處部分地在於先驗概率的計算，這裡，對於來自不同分類器的文檔分類結果，可以採用某些特定方法。例如，如果採用NB分類器，先驗概率則是從分類器直接返回的針對每對類別C,和文檔《的P(c,M)。
以NB分類器為例，該迭代算法被描述如下
(a) 首先輸入初始訓練集r: C—Powerset(Z))，即經標註的文檔子集；
(b) 利用T學習NB分類器，並利用學習結果獲得針對每個類別-文
檔對(C,^) ECXD的屍(cl力；
(c) 對於每個(c，力eCXD，如果在聚類結果中t/Ec'，則利用對準
模型計算屍(C^，C〕，令屍'(cl力-屍(cl《C〕；
(d) 生成針對新訓練集r':C-〉Powerset(D)的某些新的標註文檔，其中對於每個cEC， r(c)包括文檔集合D-domain(T) (D和r之
間的差集)中屍'(CI力從高到低排列的頂部S個文檔；
(e) 如果r=$，則迭代終止，否則，令r:=r+r，開始下一輪迭代。
以上以NB分類器為例，詳細描述了圖9所示迭代分類器學習過程中步驟901-905期間的迭代過程。在迭代學習過程中，每次迭代創建一個分類器，該分類器可以由類別-文檔對的後驗概率函數,(cl力表示。當然，本發明所涉及的分類器並不局限於NB分類器。其他種類的分類器顯而易見也可被應用於本發明。
返回圖9，如果在步驟904中確定滿足迭代終止條件(即步驟904中的"是")，過程則前進到步驟906。在步驟906中，在迭代過程中所產生的一組中間分類器被保存。然後，在步驟907中，從在迭代過程中產生的一組中間分類器中選擇一個最佳分類器作為最終分類器。這裡，典型的最終分類器選擇方式是從一組中間分類器中選擇最符合給定文檔集合的那一個。在迭代學習過程中，已知聚類結果可以消除弱訓練集的偏見。因此，我們可以利用聚類結果來評價和選擇最合適的分類器。在一個示例中，貝葉斯模型被用於從中間分類器組中選擇與聚類結果最佳匹配的中間分類器作為最終分類器。
例如，將中間分類器記作&， ^=7,麼...見W表示迭代次數。根據貝葉斯模型得到
響》=簡卿 (等式6)基於最大似然方法，我們需要找到一個特定&，該&使得戶(C'I&)最大。
顯而易見，如果假設文檔是彼此獨立的，則具有
P(C'|^) = n>(c'(")lc("》，cW) = maXjP'(c|cO (等式7)
丄丄 ceC
其中c'(^)是文檔"所屬聚類，c(^)是文檔d根據分類器^所屬類別。類似
於上述對準模型的概率計算，可以得到^的概率函數如下
並且最終分類器為F = m,xP(C'|FJ 。
然後，在選擇出最終;、類器之後，過程900結束。
圖IO是被用於實現本發明的計算機系統1000的示意性框圖。如圖所
示，該計算機系統1000包括CPU 1001、用戶接口 1002、外圍設備
1003、 存儲器1005、永久存儲設備1006以及將它們彼此相連的總線
1004。 存儲器1005中包含領域與詞性分析模塊、自動文檔分類模塊、文檔聚類模塊、IR相關系統、作業系統(OS)等等。本發明主要與所述自動文檔分類模塊相關，其例如是圖1所示的文檔分類系統100。文檔聚類模塊可以對文檔集合執行聚類處理，並將聚類結果預先存儲在適當的聚類結果庫(例如，聚類結果庫104)中。永久存儲設備1006存儲了本發明所涉及的各種資料庫，例如聚類結果庫104、文檔庫105、文檔分類結果庫雨、類別名庫403、外部知識源404等等。
以上描述了根據本發明實施例的文檔分類方法和系統，並重點描述了分類器自動生成，根據上述描述可以看出，本發明具有以下效果
首先，在本發明中，文檔的聚類結果和分類結果之間的對準分析被執行，並被集成到訓練集合建立以及迭代分類器學習的過程中。這樣一來，來源於類別名和相應語義分析的可能偏見得到控制。其確保了所產生的訓練數據以及最終的分類結果的精確性得以提高
另外，本發明所採用的方法不需要訓練數據或初始預定的關鍵字列表來進行文檔分類。相反，本發明採用在現有外部知識源的支持下對類別名的語義分析來建立初始訓練集合。由於已有的外部知識源可以覆蓋多個領域，因此當領域或文檔集改變時，本發明的方法可被容易地應用到多個不同的領域/文檔集，從而大大減少額外的標註工作。
另外，本發明所提供的最終分類器建立的機制可以降低分類器由於迭代分類器學習過程中的噪聲數據的存在而引起過大偏見的危險，尤其對於區分分類器(例如SVM、邏輯回歸等)。本發明的另一重要貢獻在於提高了最終文檔分類結果的精確性。
上面已經參考附圖描述了根據本發明的具體實施例。但是，本發明並不限於圖中示出的特定配置和處理。並且，為了簡明起見，這裡省略對這些已知方法技術的詳細描述。
在上述實施例中，描述和示出了若干具體的歩驟作為示例。但是，本發明的方法過程並不限於所描述和示出的具體步驟，本領域的技術人員可以在領會本發明的精神之後，作出各種改變、修改和添加，或者改變歩驟之間的順序。
本發明的元素可以實現為硬體、軟體、固件或者它們的組合，並且可以用在它們的系統、子系統、部件或者子部件中。當以軟體方式實現時，本發明的元素是被用於執行所需任務的程序或者代碼段。程序或者代碼段可以存儲在機器可讀介質中，或者通過載波中攜帶的數據信號在傳輸介質或者通信鏈路上傳送。"機器可讀介質"可以包括能夠存儲或傳輸信息的任何介質。機器可讀介質的例子包括電子電路、半導體存儲器設備、
ROM、快閃記憶體、可擦除ROM (EROM)、軟盤、CD-ROM、光碟、硬碟、光纖介質、射頻(RF)鏈路，等等。代碼段可以經由諸如網際網路、內聯網等的計算機網絡被下載。
本發明可以以其他的具體形式實現，而不脫離其精神和本質特徵。例如，特定實施例中所描述的算法可以被修改，而系統體系結構並不脫離本發明的基本精神。因此，當前的實施例在所有方面都被看作是示例性的而非限定性的，本發明的範圍由所附權利要求而非上述描述定義，並且，落入權利要求的含義和等同物的範圍內的全部改變從而都被包括在本發明的範圍之中。
權利要求
1.一種分類器生成方法，包括獲取對象集合的聚類結果；生成所述對象集合的粗略分類結果以得到粗略分類器；以及用所述聚類結果調整所述粗略分類結果以生成最終分類器。
2. 如權利要求1所述的方法，其中所述調整步驟包括 計算對應於所述粗略分類結果的先驗概率；利用概率上的方法使得所述粗略分類結果與所述聚類結果對準，以生 成對應於所述對準結果的後驗概率；以及 根據所述後驗概率生成所述最終分類器。
3. 如權利要求2所述的方法，其中所述概率上的方法是貝葉斯推論方法。
4. 如權利要求1所述的方法，其中生成所述粗略分類結果以得到粗略 分類器的步驟包括獲得訓練集；以及由所述訓練集學習出所述粗略分類器。
5. 如權利要求4所述的方法，其中所述訓練集是通過人工標註生成的 訓練集。
6. 如權利要求4所述的方法，其中所述訓練集是通過如下過程自動生 成的獲取與所述對象集合相關的類別名； 基於所述類別名生成相關的關鍵字；利用所述關鍵字分類所述對象集合以得到中間分類結果；以及 從所述中間分類結果獲得所述訓練集。
7. 如權利要求6所述的方法，其中，生成所述關鍵字的步驟還包括 參考外部知識源對獲取的所述類別名進行詞義消歧；以及 基於經過所述詞義消歧的類別名生成所述關鍵字。
8. 如權利要求6所述的方法，其中所述關鍵字作為代表性描述，並且所述得到中間分類結果的步驟包括利用所述代表性描述作為查詢項搜索所述對象集合；以及 將作為搜索結果的命中列表中的對象標註到相應類別。
9. 如權利要求8所述的方法，其中將所述命中列表中的前預定數目個 對象標註到相應類別。
10. 如權利要求6所述的方法，其中從所述中間分類結果獲得所述訓練集的步驟包括用所述聚類結果調整所述中間分類結果以生成中間分類器；並且從所述中間分類器對應的調整後的分類結果中選擇生成所述訓練集。
11. 如權利要求4所述的方法，其中在用所述聚類結果調整所述粗略分類結果以生成最終分類器的步驟中，以所述訓練集作為初始訓練集進行迭 代分類器學習，從而學習出一組中間分類器，並從所述一組中間分類器中 選擇一個最優分類器，作為所述最終分類器。
12. 如權利要求11所述的方法，其中所述最優分類器是與所述聚類結 果最佳匹配的分類器。
13. 如權利要求11所述的方法，其中所述迭代分類器學習中的一次迭 代包括利用從前次迭代生成的訓練集學習出本次迭代的中間分類器； 利用所述本次迭代的中間分類器對所述對象集合進行分類，以得到本次迭代的中間分類結果；用所述聚類結果調整所述本次迭代的中間分類結果，以生成用於下次迭代的訓練集。
14. 一種分類器生成系統，包括 獲取裝置，用於獲取對象集合的聚類結果；粗略分類裝置，用於生成所述對象集合的粗略分類結果以得到粗略分 類器；以及調整生成裝置，用於用所述聚類結果調整所述粗略分類結果以生成最 終分類器。
15. 如權利要求14所述的系統，其中所述調整生成裝置包括先驗概率計算單元，用於計算對應於所述粗略分類結果的先驗概率；以及對準單元，利用概率上的方法使得所述粗略分類結果與所述聚類結果 對準以生成對應於所述對準結果的後驗概率，並且根據所述後驗概率生成 所述最終分類器。
16. 如權利要求15所述的系統，其中所述概率上的方法是貝葉斯推論 方法。
17. 如權利要求14所述的系統，其中所述粗略分類裝置包括訓練集發生單元，用於獲得訓練集；以及學習單元，用於由所述訓練集學習出所述粗略分類器。
18. 如權利要求17所述的系統，其中所述訓練集發生單元從外部獲取 人工標註生成的訓練集。
19. 如權利要求17所述的系統，還包括類別名庫，用於存儲領域相關的類別名，其中所述訓練集發生單元自動生成所述訓練集，並且包括類別名獲取部件，用於從所述類別名庫獲取與所述對象集合相關的類別名；關鍵字生成部件，用於基於所述類別名生成相關的關鍵字； 分類部件，用於利用所述關鍵字分類所述對象集合以得到中間分類結 果；以及訓練集產生部件，用於從所述中間分類結果獲得所述訓練集。
20. 如權利要求19所述的系統，還包括外部知識源，用於存儲與所述 類別名相關的知識，並且所述訓練集發生單元還包括詞義消歧部件，用於 參考所述外部知識源對獲取的所述類別名進行詞義消歧，並且所述關鍵字生成部件基於經過所述詞義消歧的類別名生成所述關鍵字。
21. 如權利要求19所述的系統，其中所述關鍵字作為代表性描述，並 且所述分類部件包括搜索器，用於利用所述代表性描述作為查詢項搜索所述對象集合；以及類別標註器，用於將作為搜索結果的命中列表中的對象標註到相應類
22. 如權利要求21所述的系統，其中所述類別標註器將所述命中列表中的前預定數目個對象標註到相應類別。
23. 如權利要求19所述的系統，其中所述訓練集產生部件包括調整生成器，用於用所述聚類結果調整所述中間分類結果以生成中間分類器；以及訓練集選擇器，用於從所述中間分類器對應的調整後的分類結果中選 擇生成所述訓練集。
24. 如權利要求17所述的系統，其中所述調整生成裝置以所述訓練集 作為初始訓練集並以所述粗略分類器作為初始分類器進行迭代分類器學 習，從而學習出一組中間分類器，並從所述一組中間分類器中選擇一個最 優分類器，作為所述最終分類器。
25. 如權利要求24所述的系統，其中所述最優分類器是與所述聚類結 果最佳匹配的分類器。
全文摘要
本發明提供了一種分類器生成方法和系統。所述方法包括獲取對象集合的聚類結果；生成對象集合的粗略分類結果以得到粗略分類器；以及用聚類結果調整粗略分類結果以生成最終分類器。在一個實施例中，粗略分類結果根據對準模型與聚類結果對準相，以此控制來源於類別名和相應語義分析的可能偏見。利用根據本發明的分類器生成方法和系統，可大大提高文檔分類的精確性和可擴展性。
文檔編號G06F17/30GK101561805SQ200810094208
公開日2009年10月21日 申請日期2008年4月18日 優先權日2008年4月18日
發明者李建強, 彧 趙 申請人:日電(中國)有限公司