文本自動分類算法的比較與研究

摘要：對于海量的網絡信息而言，文本自動分類算法的合理應用決定了當今網絡服務商所能提供服務的優良與否。因此，文章在對現今流行的分類算法，如簡單向量距離分類法、KNN、Bayes等比較、研究的基礎上提出了一種考慮詞序，即利用詞與詞之間的有序關聯與共現關系的擴展算法并進行了測試與分析，對于更好地利用文本分類算法提供了一定的依據。

關鍵詞：文本分類； 特征項； 支持向量機算法； K近鄰法； 貝葉斯方法

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044(2009)05-1183-02

The Comparison and Research of Text Categorization Algorithm

ZHAO Min-Ya

(Department of Computer Engineering， Suzhou Vocation University， Suzhou 215104， China)

Abstract： For the increasing network information， the using in reason of auto-text categorization algorithm is deciding the choiceness of service from the ISP. Then this paper puts forward a extending algorithm thinking over words order which is utilizing the relation of sequence and appearance between words， and tested and analyzed based on the comparison and research of text categorization algorithm popular nowadays， such as simple vector distance， KNN， Bayes， and laying the foundation of better using.

Key words: text categorization; item; support vector machine; K-Nearest Neighbor;bayes

1 引言

20世紀90年代以來，Internet 以驚人的速度發展起來，它容納了海量的各種類型的原始信息，包括文本信息、聲音信息、圖像信息等等。如何在浩如煙海而又紛繁蕪雜的文本中掌握最有效的信息始終是信息處理的一大目標。基于人工智能技術的文本分類系統能依據文本的語義將大量的文本自動分門別類，從而更好地幫助人們把握文本信息。近年來，文本分類技術已經逐漸與搜索引擎、信息推送、信息過濾等信息處理技術相結合，有效地提高了信息服務的質量。

2 分類算法

簡單地說，文本分類系統的任務是：在給定的分類體系下，根據文本的內容自動地確定

文本關聯的類別。從數學角度來看，文本分類是一個映射的過程，它將未標明類別的文本映射到已有的類別中，該映射可以是一一映射，也可以是一對多的映射，因為通常一篇文本可以同多個類別相關聯。用數學公式表示如下：

其中，A為待分類的文本集合，B為分類體系中的類別集合。

文本分類的映射規則是系統根據已經掌握的每類若干樣本的數據信息，總結出分類的規律性而建立的判別公式和判別規則。然后在遇到新文本時，根據總結出的判別規則，確定文本相關的類別。

2.1 文本的表示

計算機并不具有人類的智能，人在閱讀文章后，根據自身的理解能力可以產生對文章內容的模糊認識，而計算機并不能輕易地“讀懂”文章，從根本上說，它只認識 0 和 1，所以必須將文本轉換為計算機可以識別的格式。根據“貝葉斯假設”，假定組成文本的字或詞在確定文本類別的作用上相互獨立，這樣，可以就使用文本中出現的字或詞的集合來代替文本，不言而喻，這將丟失大量關于文章內容的信息，但是這種假設可以使文本的表示和處理形式化，并且可以在文本分類中取得較好的效果。

目前，在信息處理方向上，文本的表示主要采用向量空間模型（VSM）。向量空間模型的基本思想是以向量來表示文本：(w1，w2，…，wn)，其中wi為第i個特征項的權重，那么選取什么作為特征項呢，一般可以選擇字、詞或詞組，根據實驗結果，普遍認為選取詞作為特征項要優于字和詞組，因此，要將文本表示為向量空間中的一個向量，就首先要將文本分詞，由這些詞作為向量的維數來表示文本，最初的向量表示完全是0、1形式，即，如果文本中出現了該詞，那么文本向量的該維為1，否則為0。這種方法無法體現這個詞在文本中的作用程度，所以逐漸0、1被更精確的詞頻代替，詞頻分為絕對詞頻和相對詞頻，絕對詞頻，即使用詞在文本中出現的頻率表示文本，相對詞頻為歸一化的詞頻，其計算方法主要運用TF-IDF公式，目前存在多種TF-IDF公式，如下是一種比較普遍的TF-IDF公式：

其中，W(t，d)為詞t在文本d中的權重，而 tf(t，d)為詞t在文本d中的詞頻，N為訓練文本的總數，nt為訓練文本集中出現t的文本數，分母為歸一化因子。

2.2 訓練方法與分類算法

訓練方法和分類算法是分類系統的核心部分，目前存在多種基于向量空間模型的訓練算法和分類算法，本文以下具體介紹三種分類算法：

1）簡單向量距離分類法

該方法的分類思路十分簡單，根據算術平均為每類文本集生成一個代表該類的中心向量，然后在新文本來到時，確定新文本向量，計算該向量與每類中心向量間的距離（相似度），最后判定文本屬于與文本距離最近的類，它計算新文本特征向量和每類中心向量間的相似度的公式為：

其中，di為新文本的特征向量，dj為第j類的中心向量，M為特征向量的維數，Wk為向量的第K維。

2）貝葉斯算法（Bayes）

該算法的基本思路是計算文本屬于類別的概率，文本屬于類別的概率等于文本中每個詞屬于類別的概率的綜合表達式，具體算法步驟如下：

Step 1：計算特征詞屬于每個類別的概率向量，（w1，w2，w3……wn），其中：

計算公式與計算互信息量的公式相同

Step 2:在新文本到達時，根據特征詞分詞，然后按下面的公式計算該文本di屬于類Ci的概率：

Step 3:比較新文本屬于所有類的概率，將文本分到概率最大的那個類別中。

3）KNN（K 最近鄰居）算法

該算法的基本思路是：在給定新文本后，考慮在訓練文本集中與該新文本距離最近（最相似）的 K 篇文本，根據這 K 篇文本所屬的類別判定新文本所屬的類別，具體的算法步驟如下：

Step 1:根據特征項集合重新描述訓練文本向量

Step 2:在新文本到達后，根據特征詞分詞新文本，確定新文本的向量表示

Step 3:在訓練文本集中選出與新文本最相似的 K 個文本，計算公式為：

其中，K值的確定目前沒有很好的方法，一般采用先定一個初始值，然后根據實驗測試的結果調整K值，一般初始值定為幾百到幾千之間。

Step 4:在新文本的K個鄰居中，依次計算每類的權重，計算公式如下：

其中，x為新文本的特征向量，Sim(x，di)為相似度計算公式，與上一步驟的計算公式相同，而y(di，cj)為類別屬性函數，即，如果di屬于類Cj ，那么函數值為1，否則為0。

Step 5:比較類的權重，將文本分到權重最大的那個類別中。

除此以外，支持向量機和神經網絡算法在文本分類系統中應用也較為廣泛，支持向量機的基本思想是使用簡單的線形分類器劃分樣本空間。對于在當前特征空間中線形不可分的模式，則使用一個核函數把樣本映射到一個高維空間中，使得樣本能夠線形可分。

而神經網絡算法采用感知算法進行分類。在這種模型中，分類知識被隱式地存儲在連接的權值上，使用迭代算法來確定權值向量。當網絡輸出判別正確時，權值向量保持不變，否則進行增加或降低的調整，因此也稱為獎懲法。

2.3 考慮詞序的擴展算法（The Extending Algorithm Based on Word Order）

一篇文檔中常有一些詞串（又稱n-grams）不止一次出現，且大部分構成有序的名詞短語。例如“machine learning”，“imitation game”等在A.M.Turning所著的文檔“Computing Machinery and Intelligent”中多次出現。這些詞串應作為整體視為文檔的特征詞，并且當用戶僅選定詞串的部分單詞作為查詢時，剩下的單詞應該首先被提交作為用戶查詢的擴展信息。

短語是詞的搭配信息的一種，可以被視為單詞之間的一種強關聯關系。一般通過數據挖掘中的技術[韓家煒 2001]，如APPRIORI算法 [Fürnkranz 1998]或者統計學理論，如互信息、假設檢驗等方法從大量的語料庫中來抽取詞與詞之間的搭配關系。由于目前沒有大量的相關文檔測試集，同時APPRIORI算法會產生大量的侯選項集，我們采用以下相對較簡單的方法從文檔中抽取高頻的二元詞串作為文檔短語。

我們假定文檔的短語均由實詞構成，即短語中不含有停用詞表中的單詞，如短語“of course”就不能被看作文檔短語。系統首先利用停用詞表從文檔中去除頻率極高且與文檔主題無關的詞，如the，a，there等等；然后通過詞頻統計，將低頻詞（出現頻率低于 2）去除，剩下的單詞放入一個名為ConcurrenceSet的集合。文檔中的每個句子被視為詞的有序集合，對于ConcurrenceSet中的每個單

（下轉第1193頁）

（上接第1184頁）

詞t，找出緊鄰它的前一個單詞或后一個單詞k，判斷它是否屬于ConcurrenceSet。如果k屬于ConcurrenceSet，并且作為詞t的緊鄰在文檔中的不同句子中出現，則可以認為詞k與詞t構成了文檔中的一個二元短語。

因此，利用詞與詞之間的有序關聯與共現關系，可以較全面地反映一篇文檔的主要觀點，快速確定相應的類別，有助于新文檔的分類，并且能夠幫助用戶方便地了解文檔的主要內容，這一方面從一個側面反映了用戶的搜索興趣，另一方面幫助用戶確定檢索領域。在本文中，筆者充分考慮詞序關聯與共現關系，提出了考慮詞序的擴展算法，簡寫為EabWo。

3 算法實驗分析

本文實驗數據是直接利用搜索引擎從雅虎網（http://news.yahoo.com）上按新聞的11個類別分別下載了一定數量的文檔，保存到本地數據庫中，然后進行分析，加入了部分人工處理后得到的一組數據來測試的。實驗采用查全率和查準率的評定標準。實驗結果見表1。

如表1所示，通過比較、分析各類算法表明，考慮詞序可以更好的提高分類的查準率和查全率，得到更有效的分類結果。本實驗是在封閉的數據集上進行的。由于實驗條件、數據規模、個人技術能力等方面的不足，算法仍處在初步試驗階段。

參考文獻：

[1] Evgeniy Gabrilovich，Susan Dumais，Eric Horvitz. Newsjunkie: Providing Personalized Newsfeeds via Analysis of Information Novelty. WWW2004，May 17-22，2004，New York，USA.

[2]Davi de Castro Reis，Paulo B. Golgher，Altigran S. da Silva. Automatic Web News Extraction Using Tree Edit Distance. WWW2004，May 17-22，New York，USA.

[3] 王煜，白石，王正歐.用于Web文本分類的快速KNN算法[J].情報學報， 2007，26(1):60-64.

[4] 李楊，曾海泉，劉慶華，等.基于kNN的快速WEB文檔分類[J].小型微型計算機系統， 2004，25(4):725-729.

[5] 厲宇航，羅振聲，程慕勝.基于概念層次的英文文本自動分類研究[J].計算機工程與應用， 2004(11):75-77.

[6] Matsuo Y. ，Ishizuka M. “Keyword Extraction from a Single Document using Word Co-occurrence Statistical Information ”. American Association for Artificial Intelligence. 2003.