文本自動(dòng)分類算法的比較與研究

摘要：對(duì)于海量的網(wǎng)絡(luò)信息而言，文本自動(dòng)分類算法的合理應(yīng)用決定了當(dāng)今網(wǎng)絡(luò)服務(wù)商所能提供服務(wù)的優(yōu)良與否。因此，文章在對(duì)現(xiàn)今流行的分類算法，如簡(jiǎn)單向量距離分類法、KNN、Bayes等比較、研究的基礎(chǔ)上提出了一種考慮詞序，即利用詞與詞之間的有序關(guān)聯(lián)與共現(xiàn)關(guān)系的擴(kuò)展算法并進(jìn)行了測(cè)試與分析，對(duì)于更好地利用文本分類算法提供了一定的依據(jù)。

關(guān)鍵詞：文本分類； 特征項(xiàng)； 支持向量機(jī)算法； K近鄰法； 貝葉斯方法

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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世紀(jì)90年代以來(lái)，Internet 以驚人的速度發(fā)展起來(lái)，它容納了海量的各種類型的原始信息，包括文本信息、聲音信息、圖像信息等等。如何在浩如煙海而又紛繁蕪雜的文本中掌握最有效的信息始終是信息處理的一大目標(biāo)?；谌斯ぶ悄芗夹g(shù)的文本分類系統(tǒng)能依據(jù)文本的語(yǔ)義將大量的文本自動(dòng)分門(mén)別類，從而更好地幫助人們把握文本信息。近年來(lái)，文本分類技術(shù)已經(jīng)逐漸與搜索引擎、信息推送、信息過(guò)濾等信息處理技術(shù)相結(jié)合，有效地提高了信息服務(wù)的質(zhì)量。

2 分類算法

簡(jiǎn)單地說(shuō)，文本分類系統(tǒng)的任務(wù)是：在給定的分類體系下，根據(jù)文本的內(nèi)容自動(dòng)地確定

文本關(guān)聯(lián)的類別。從數(shù)學(xué)角度來(lái)看，文本分類是一個(gè)映射的過(guò)程，它將未標(biāo)明類別的文本映射到已有的類別中，該映射可以是一一映射，也可以是一對(duì)多的映射，因?yàn)橥ǔＲ黄谋究梢酝鄠€(gè)類別相關(guān)聯(lián)。用數(shù)學(xué)公式表示如下：

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

文本分類的映射規(guī)則是系統(tǒng)根據(jù)已經(jīng)掌握的每類若干樣本的數(shù)據(jù)信息，總結(jié)出分類的規(guī)律性而建立的判別公式和判別規(guī)則。然后在遇到新文本時(shí)，根據(jù)總結(jié)出的判別規(guī)則，確定文本相關(guān)的類別。

2.1 文本的表示

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

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

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

2.2 訓(xùn)練方法與分類算法

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

1）簡(jiǎn)單向量距離分類法

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

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

2）貝葉斯算法（Bayes）

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

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

計(jì)算公式與計(jì)算互信息量的公式相同

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

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

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

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

Step 1:根據(jù)特征項(xiàng)集合重新描述訓(xùn)練文本向量

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

Step 3:在訓(xùn)練文本集中選出與新文本最相似的 K 個(gè)文本，計(jì)算公式為：

其中，K值的確定目前沒(méi)有很好的方法，一般采用先定一個(gè)初始值，然后根據(jù)實(shí)驗(yàn)測(cè)試的結(jié)果調(diào)整K值，一般初始值定為幾百到幾千之間。

Step 4:在新文本的K個(gè)鄰居中，依次計(jì)算每類的權(quán)重，計(jì)算公式如下：

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

Step 5:比較類的權(quán)重，將文本分到權(quán)重最大的那個(gè)類別中。

除此以外，支持向量機(jī)和神經(jīng)網(wǎng)絡(luò)算法在文本分類系統(tǒng)中應(yīng)用也較為廣泛，支持向量機(jī)的基本思想是使用簡(jiǎn)單的線形分類器劃分樣本空間。對(duì)于在當(dāng)前特征空間中線形不可分的模式，則使用一個(gè)核函數(shù)把樣本映射到一個(gè)高維空間中，使得樣本能夠線形可分。

而神經(jīng)網(wǎng)絡(luò)算法采用感知算法進(jìn)行分類。在這種模型中，分類知識(shí)被隱式地存儲(chǔ)在連接的權(quán)值上，使用迭代算法來(lái)確定權(quán)值向量。當(dāng)網(wǎng)絡(luò)輸出判別正確時(shí)，權(quán)值向量保持不變，否則進(jìn)行增加或降低的調(diào)整，因此也稱為獎(jiǎng)懲法。

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

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

短語(yǔ)是詞的搭配信息的一種，可以被視為單詞之間的一種強(qiáng)關(guān)聯(lián)關(guān)系。一般通過(guò)數(shù)據(jù)挖掘中的技術(shù)[韓家煒 2001]，如APPRIORI算法 [Fürnkranz 1998]或者統(tǒng)計(jì)學(xué)理論，如互信息、假設(shè)檢驗(yàn)等方法從大量的語(yǔ)料庫(kù)中來(lái)抽取詞與詞之間的搭配關(guān)系。由于目前沒(méi)有大量的相關(guān)文檔測(cè)試集，同時(shí)APPRIORI算法會(huì)產(chǎn)生大量的侯選項(xiàng)集，我們采用以下相對(duì)較簡(jiǎn)單的方法從文檔中抽取高頻的二元詞串作為文檔短語(yǔ)。

我們假定文檔的短語(yǔ)均由實(shí)詞構(gòu)成，即短語(yǔ)中不含有停用詞表中的單詞，如短語(yǔ)“of course”就不能被看作文檔短語(yǔ)。系統(tǒng)首先利用停用詞表從文檔中去除頻率極高且與文檔主題無(wú)關(guān)的詞，如the，a，there等等；然后通過(guò)詞頻統(tǒng)計(jì)，將低頻詞（出現(xiàn)頻率低于 2）去除，剩下的單詞放入一個(gè)名為ConcurrenceSet的集合。文檔中的每個(gè)句子被視為詞的有序集合，對(duì)于ConcurrenceSet中的每個(gè)單

（下轉(zhuǎn)第1193頁(yè)）

（上接第1184頁(yè)）

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

因此，利用詞與詞之間的有序關(guān)聯(lián)與共現(xiàn)關(guān)系，可以較全面地反映一篇文檔的主要觀點(diǎn)，快速確定相應(yīng)的類別，有助于新文檔的分類，并且能夠幫助用戶方便地了解文檔的主要內(nèi)容，這一方面從一個(gè)側(cè)面反映了用戶的搜索興趣，另一方面幫助用戶確定檢索領(lǐng)域。在本文中，筆者充分考慮詞序關(guān)聯(lián)與共現(xiàn)關(guān)系，提出了考慮詞序的擴(kuò)展算法，簡(jiǎn)寫(xiě)為EabWo。

3 算法實(shí)驗(yàn)分析

本文實(shí)驗(yàn)數(shù)據(jù)是直接利用搜索引擎從雅虎網(wǎng)（http://news.yahoo.com）上按新聞的11個(gè)類別分別下載了一定數(shù)量的文檔，保存到本地?cái)?shù)據(jù)庫(kù)中，然后進(jìn)行分析，加入了部分人工處理后得到的一組數(shù)據(jù)來(lái)測(cè)試的。實(shí)驗(yàn)采用查全率和查準(zhǔn)率的評(píng)定標(biāo)準(zhǔn)。實(shí)驗(yàn)結(jié)果見(jiàn)表1。

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

參考文獻(xiàn)：

[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].情報(bào)學(xué)報(bào)， 2007，26(1):60-64.

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

[5] 厲宇航，羅振聲，程慕勝.基于概念層次的英文文本自動(dòng)分類研究[J].計(jì)算機(jī)工程與應(yīng)用， 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.