自動分類技術研究

摘要：自動分類技術已成為文檔信息分類的主導關鍵技術，針對技術的發展現狀，歸納自動分類技術的類型及歸類方法，以及對未來發展的展望。

關鍵詞：自動分類；現狀；類型；文檔分類；方法

中圖分類號：TP391文獻標識碼：A文章編號：1009-3044(2009)04-1020-02

自動分類技術是利用計算機系統對文本集按照一定的分類體系或標準進行自動類別標記，分類工具根據文檔的信息將其分配到已經存在的類別中，也稱“主題”。

隨著網絡的迅猛發展，網頁、電子郵件、數據庫、聊天室和數字圖書館等電子文本成幾何級數不斷增長，處理這些海量數據的一個重要方法就是將它們分類。當我們瀏覽一個網站查找信息時，如果網頁凌亂的堆積在一起沒有類別供我們查找，會使我們很難找到自己所需的信息。現在，大型網站都將網頁分類，以方便人們瀏覽。比如，Yahoo就將網頁放在一個巨大的層次分類結構中，通過組裝維護這些類別，可以幫助人們查找知識和信息。網頁自身并沒有類型區分，這就需要人工分類，將網頁、郵件等各種格式的文檔經過文法分析都可以轉化為純文本，而自動文本分類系統可以幫助人們檢查文本、判斷文本所屬類別。

1 自動分類技術的現狀

到目前為止，國外已在自動分類領域進行了較為深入的研究。已經從最初的可行性基礎研究經歷了實驗性研究進入實用階段，并在郵件分類、電子會議、信息過濾等方面取得了較為廣泛的應用[1]。

國內對自動分類技術的研究相對較晚。1986年，上海交通大學電腦應用技術研究所開發的中文科技文獻（計算機類）實驗性分類系統。1995年，清華大學電子工程系研制的漢語語料自動分類系統。1998年，東北大學計算機系的新聞語料漢語文本自動分類模型。1999年，由鄒濤等人開發的中文技術文本分類系統CTDS。除此之外，國內眾多學者對中文文本分類算法也進行了深入研究，黃萱箐等提出的基于機器學習的、獨立于語種的文本分類模型[3]，周永庚等研究的隱含語義索引在中文文本處理中的應用[4]，李榮陸等的最大熵模型[5]，張劍等提出的一種以WordNet語言本體庫為基礎，建立文本的概念向量空間模型作為文本特征向量的特征提取方法[6]，朱靖波等將領域知識引入文本分類，利用領域知識作為文本特征，提出一種基于知識的文本分類方法等[7]。

從20世紀90年代以來，基于機器學習的文本分類逐漸成為文本分類的主流技術。近年來文本分類技術取得了很大的進展，提出了多種特征抽取方法和分類方法，如回歸模型、支持向量機、最大熵模型等，建立了OHSUMED，Reuters等開放的分類語料庫。

2 自動分類技術的類型

根據目的性，信息自動分類包括自動聚類和自動歸類兩種類型。

2.1 自動聚類

由計算機系統對待分類文本進行分析并提取有關的特征，然后對提取的特征進行比較，根據一定規則將具有相同或相近特征的對象定義為一類。自動聚類的目的是在已有信息中定義符合實際情況的類。在網站的非主要分類體系中，也可以用自動聚類的方法自動生成欄目內的類別。

2.2 自動歸類

計算機系統對分類文本提取有關特征，然后與既定分類系統中對象所具有的公共特征進行相關性比較。將對象歸入其特征最相近的類中。自動歸類的目的是把各種信息納入已建立的分類系統中，用于搜索引擎或網站導航系統的管理和數據更新。根據使用的技術，自動歸類通常分為基于詞的自動分類（詞典法）和基于專家系統的自動分類（知識法）兩大類，也有人將界于兩種技術之間的稱為基于信息的自動分類。

3 文檔分類關鍵技術分類及方法

現有的文本分類技術主要采用3 種方法:基于連接的方法、基于規則的方法和基于統計的方法。

3.1 基于連接的文本分類方法

基于連接的方法主要是利用人工神經網絡來模擬人腦神經網絡，并期望其能像大腦一樣地運作，一樣地學習，從而產生智慧。這種方法可以實現信息的分布存取，運算的全局并行，并且可在進行非線性處理的同時具有高容錯性等特點，適用于學習一個復雜的非線性映射。但是使用他學習所形成的知識結構是人所難以理解的，系統本身也不具有良好的透明性。

3.2 基于規則的文本分類方法

基于規則的方法本質上是一種確定性的演繹推理方法。其優點在于他能根據上下文對確定性事件進行定性描述，并且能充分利用現有的語言學成果。其成立的前提是有大量的知識，而這些知識必須是人類專家總結出來的。由于必須有人的參與，這種方法側重于知識的可理解性和可讀性，對于有些統計方法無法解決的問題，利用基于規則的方法可以很容易地解決。但是，這種方法在不確定性事件的描述、規則之間的相容性等方面存在一些缺陷和限制。常用的基于規則的方法有決策樹、關聯規則等。

3.3 基于統計的文本分類方法

基于統計的方法本質上是一種非確定性的定量推理方法。基于統計的方法的優勢在于他的全部知識是通過對大規模語料庫分析得到的，可以取得很好的一致性和非常高的覆蓋率，對語言處理提供了比較客觀的數據依據和可靠的質量保證。但由于其是基于概率的一種方法，因此必然會對小類別文本即小概率事件造成忽視。常用的基于統計的方法有KNN、樸素貝葉斯、類中心向量、回歸模型、支持向量機、最大熵模型等。

3.4 經典文本分類方法

3.4.1 KNN算法

KNN算法即k- Nearest Neighbor 分類方法，是一種穩定而有效的文本分類方法。采用KNN 方法進行文檔分類的過程如下：對于某一給定的測試文檔d，在訓練集中，通過相似度找到與之最相似的k個訓練文檔。在此基礎上，給每個文檔類打分，分值為k個訓練文檔中屬于該類的文檔與測試文檔之間的相似度之和。也就是說， 如果在這k個文檔中，有多個文檔屬于一個類，則該類的分值為這些文檔與測試文檔之間的相似度之和。對這k個文檔所屬類的分值統計完畢后，即按分值進行排序。還應當選定一個閾值，只有分值超過閾值的類才予考慮。測試文檔屬于超過閾值的所有類。形式化表示為:

■（1）

其中，dj∈ci時y(dj，ci)=1；dj?埸ci時y(dj，ci) 。

bi為閾值，Sim(d，dj)為文檔d和dj的相似度，score(d，ci)為測試文檔d屬于ci類的分值。一般的，bi是一個有待優化的值可以通過一個驗證文檔集來進行調整。驗證文檔集是訓練文檔集的一部分，根據公式(1)可確定測試文檔的類別。很顯然，對于每一個測試文檔，必須求解其和訓練文檔庫中所有文檔的相似度。因此， KNN方法的時間復雜度為o(|D|ni)。其中，|D|和ni分別為訓練文檔總數和測試文檔總數。

3.4.2 SVM

支持向量機（Support Vector Machine，SVM）是在統計學習理的基礎上發展而來的一種機器學習方法， 該模型是基于結構風險最小化原理的方法，把原始數據集合壓縮為支持向量集合，其基本思想是構造出一個超平面作為決策平面，使正負模式之間的空白為最大化。在解決小樣本、非線性及高維模式識別問題中SVM表現出了許多特有的優勢， 并在很大領域得到了成功的應用，如：人臉識別、手寫字體識別、文本分類等。其中，SVM在文本分類方面的表現尤為突出。

SVM 的基本思想可用圖1的兩維情況進行說明。圖1中，圓形實心點和菱形實心點代表2類樣本，H為分類線，H1，H2分別為過各類中離分類線最近的樣本且平行于分類線的直線，他們之間的距離叫做分類間隔。所謂最優分類線就是要求分類線不但能將兩類正確分開(訓練錯誤率為0)，而且使分類間隔最大。分類線方程為：

x·w+b=0

在此可以對他進行歸一化，使得對線性可分的樣本集：

(xi，yi)，i=1，…，n，x∈R4，y∈{+1，-1}

滿足：yi[(w.xi)+b]-1≥0 i=1，2，…n

此時分類間隔等于2/‖w‖， 使間隔最大等價于使‖w‖2最小。滿足式且使間距為‖w‖/2的分類面就叫做最優分類面， H1 ， H2上的訓練樣本點就稱作支持向量。

基本的SVM是針對兩類分類問題的，為了實現對多個類別的識別，需要對SVM進行擴展。常用的SVM多類分類方法有One-vs-Res， One-vs-One，ECOC( Error Correcting Output Coding)、DAGSVM和二叉樹等方法。實驗結果表明DAGSVM 方法要優于其他2 種方法。Weston和Watkins[2]對SVM的理論進行了擴充，使其一次就可以完成多類分類，但是實驗結果顯示其分類查準率要低于One-vs-Rest 和One-vs-One方法。

4 技術的發展趨勢與展望

本文介紹了文本分類的研究背景，國內外關于文本分類技術研究的最新動態，總結了近年來文本分類研究的關鍵技術。文本分類技術有著廣泛的應用，逐漸趨于實用。

但隨著自動分類技術相關應用的發展，及對其需求的不斷提升，文本分類技術仍有非常多的問題值得研究：可靠、有效及快速的在線分類；基于語義度量的數據模型和分類方法；緩解樣本標注瓶頸以及樣本數據分布帶來的影響等。隨著數據挖掘領域和機器學習理論、技術研究的不斷深入， 針對解決不同實際應用和數據特征的問題將成為文本分類相關研究，及其應用的主要突破方向和攻克難點。

參考文獻：

[1] 李榮陸.文本分類及相關技術研究[D].上海:復旦大學，2005.

[2] 李應紅.慰詢楷. 劉建勛.支持向量機的工程應用[M].北京:兵器工業出版社，2004.

[3] 黃萱菁，吳立德，石崎洋之，等. 獨立于語種的文本分類方法[J].中文信息學報，2000，14(6):1-7.

[4] 周水庚，關佶紅，胡運發. 隱含語義索引及其在中文文本處理中的應用研究[J].小型微型計算機系統，2001，22(2):239-244.

[5] 李榮陸，王建會，陳曉云，胡運發等. 使用最大熵模型進行中文文本分類[J].計算機研究與發展.2005，42(1):94-101.

[6] 張劍，李春平. 基于WordNet概念空間模型的文本分類[J].計算機工程與應用.2006(4):174-178.

[7] 朱靖波，陳文亮. 基于領域知識的文本分類[J].東北大學學報，2005，26(8):733-736.

畢靜，女，陜西漢中人，助理講師，工作于漢中市農業干部學校，主要從事于計算機科學應用的研究。