【文章內(nèi)容簡(jiǎn)介】 算法可以非常容易地轉(zhuǎn)化成多類別分類算法，不過這種方法有一個(gè)假設(shè)條件，即各個(gè)類之間是獨(dú)立的，沒有相互依存關(guān)系或其它影響，當(dāng)然在實(shí)際應(yīng)用中，絕大多數(shù)情況是可以滿足此假設(shè)條件的。因此，在文本分類的研究中，大部分實(shí)驗(yàn)都是基于單類別分類問題的探討。國(guó)外自動(dòng)分類研究始于1950年代末，他首先將詞頻統(tǒng)計(jì)的思想用于文本分類中。1960年Maron在Journal of ASM上發(fā)表了有關(guān)自動(dòng)分類的第一篇論文“On relevance probabilitic indexing and informarion retriral。 1962年博科()等人提出了利用因子分析法進(jìn)行文獻(xiàn)的自動(dòng)分類。其后許多學(xué)者在這一領(lǐng)域進(jìn)行了卓有成效的研究。國(guó)外的自動(dòng)分類研究大體上可以分為三個(gè)階段:第一階段（1958年1964年)主要進(jìn)行自動(dòng)分類的可行性研究。第二階段(1965年1974年)，自動(dòng)分類的實(shí)驗(yàn)研究。第三階段(1975年至今)，自動(dòng)分類的實(shí)用化階段。[26]國(guó)外當(dāng)前流行的文本分類方法有Rocchio法及其變異方法、k近鄰法（KNN)、決策樹、樸素貝葉斯、貝葉斯網(wǎng)絡(luò)、支持向量機(jī)(SVM)等方法。這些方法在英文以及歐洲語種文本自動(dòng)分類上有廣泛的研究，而且很多研究表明KNN和SVM是英文文本分類的最好方法。國(guó)外很多研究人員對(duì)英文文本分類領(lǐng)域的各個(gè)問題都有相當(dāng)深入的研究，對(duì)幾種流行的方法進(jìn)行了大量的對(duì)比研究。Susan Dumais等學(xué)者對(duì)這5種方法進(jìn)行了專門的比較研究。國(guó)內(nèi)自動(dòng)分類研究起步較晚，始于20世紀(jì)80年代初期。1981年侯漢清對(duì)計(jì)算機(jī)在文獻(xiàn)分類工作中的應(yīng)用作了探討[27]，并介紹了國(guó)外在計(jì)算機(jī)管理分類表、計(jì)算機(jī)分類檢索、計(jì)算機(jī)自動(dòng)分類、計(jì)算機(jī)編制分類表等方面的概況。我國(guó)自動(dòng)分類的研究大體上正在經(jīng)歷從可行性探討輔助分類自動(dòng)分類系統(tǒng)的發(fā)展階段。關(guān)于中文文本分類的研究相對(duì)較少，國(guó)內(nèi)外的研究基本上是在英文文本分類研究的基礎(chǔ)上采取相應(yīng)策略，結(jié)合中文文本的特定知識(shí)，然后應(yīng)用于中文之上，繼而形成中文文本自動(dòng)分類研究體系。國(guó)內(nèi)外的很多學(xué)者在基于知識(shí)和統(tǒng)計(jì)的兩種方法上對(duì)中文文本分類進(jìn)行了大量的研究工作，主要有基于詞典的自動(dòng)分類系統(tǒng)和基于專家系統(tǒng)的分類系統(tǒng)。如上海交通大學(xué)、中國(guó)科學(xué)院、清華大學(xué)、北京大學(xué)、北京信息工程學(xué)院、復(fù)旦大學(xué)、東北大學(xué)、山西大學(xué)以及新加坡、香港和臺(tái)灣的一些大學(xué)都有相應(yīng)的研究成果，也研制出了不少的實(shí)驗(yàn)系統(tǒng)。一般的自動(dòng)文本分類有以下幾個(gè)階段[10]，具體如圖31所示。(1) 生成訓(xùn)練語料庫(kù)的文本特征全集；(2) 文本特征提取，形成特征子集；(3) 采用某種數(shù)學(xué)模型和分類方法進(jìn)行分類器構(gòu)造；(4) 利用訓(xùn)練語料庫(kù)中的文本對(duì)分類器進(jìn)行訓(xùn)練，得到分類器的相關(guān)參數(shù)。訓(xùn)練文本采集及處理特征提取/文本表示特征空間降維構(gòu)造分類器分類和輸出新文本預(yù)處理訓(xùn)練過程分類過程圖31 文本分類過程[26] 由圖31所示及上述的文本分類的幾個(gè)階段，可以看出文本分類過程所需要的幾個(gè)關(guān)鍵技術(shù)，現(xiàn)下面開始介紹文本分類的關(guān)鍵技術(shù)。在當(dāng)前的計(jì)算機(jī)技術(shù)的研究水平下，機(jī)器還不可能識(shí)別自然文本，從根本上說，它只認(rèn)識(shí)0和1，所以必須將文本轉(zhuǎn)換為計(jì)算機(jī)可以識(shí)別的形式。而要想讓計(jì)算機(jī)“讀懂”文本，必須能夠找到用于文本表示的數(shù)學(xué)模型。隨著信息檢索技術(shù)的發(fā)展，逐漸發(fā)展起來的主要有三個(gè)文本檢索模型，分別是:布爾模型[10] (Boolean Model，BM)、向量空間模型[12][13](Vector Space Model，VSM)和概率模型 (Probabilistic Model，PM)，這些模型從不同角度使用不同的方法處理特征加權(quán)、類別學(xué)習(xí)和相似度計(jì)算等問題，而最經(jīng)典、最實(shí)用的是向量空間模型，本文的研究是建立在向量空間模型之上的。向量空間模型是由Salton在20世紀(jì)60年代末提出的，它最早應(yīng)用于信息檢索領(lǐng)域，例如著名的SMART(System for the Manipulation and Retrieval of Text)系統(tǒng)就成功的應(yīng)用了向量空間模型技術(shù)，后來又在文本分類領(lǐng)域得到了廣泛的應(yīng)用。向量空間模型的基于兩個(gè)基本假設(shè)，一是文檔所屬的類別僅與某些特定的詞或詞組在該文檔中出現(xiàn)的頻數(shù)有關(guān)，而與詞或詞組在文檔中出現(xiàn)的位置或順序無關(guān)。二是假設(shè)文檔的各特征詞之間是相互獨(dú)立的。這樣，只需要提取出一份文檔中蘊(yùn)涵的各個(gè)特征詞的詞頻信息就可以對(duì)其進(jìn)行正確的分類。向量空間是由一組線性無關(guān)的基本向量組成，向量維數(shù)與向量空間維數(shù)一致，并可以通過向量空間進(jìn)行描述。下面介紹文檔向量空間的一些基本概念:文本:泛指一般的文獻(xiàn)或文獻(xiàn)中的片段(段落、句子或句子組)，一般指一篇文章(假設(shè)文檔中不包含除文字以外的其他多媒體信息)。特征項(xiàng):文本的內(nèi)容特征常常用它所含有的基本語言單位(字、詞、詞組或短語)來表示，一般中文中使用詞語作為文本的特征項(xiàng)。特征項(xiàng)的權(quán)重:對(duì)于含有個(gè)特征項(xiàng)的文本，常用一定的權(quán)重表示特征項(xiàng)在文本中的重要程度。即把文本表示為，特征詞表示為，特征詞的權(quán)重表示為。這樣自然語言形式的文本文檔就可以在向量空間中完全由特征向量來表示。對(duì)兩個(gè)文本試和之間的內(nèi)容相關(guān)程度的度量被稱為相似度，可以用如下公式計(jì)算： （31） tktitj圖 32 文本的向量空間模型及文本間的相似度 其中，為特征向量的維數(shù)，表示第個(gè)文本的第個(gè)特征項(xiàng)的權(quán)重值。向量空間模型的主要優(yōu)點(diǎn)在于:(l)標(biāo)引詞加權(quán)改進(jìn)了檢索效果。(2)其部分匹配策略允許檢出與查詢條件相接近的文獻(xiàn)。(3)利用余弦公式，根據(jù)待測(cè)文獻(xiàn)與訓(xùn)練文獻(xiàn)之間的相似度對(duì)其進(jìn)行排序。與其他的檢索模型相比，向量空間模型簡(jiǎn)單、便捷，而且分類性能也非常好，已成為當(dāng)今最流行的檢索模型。實(shí)現(xiàn)文本自動(dòng)分類的基本困難之一是特征項(xiàng)空間的維數(shù)過高。數(shù)量過大的特征項(xiàng)一方面導(dǎo)致分類算法的代價(jià)過高，另一方面導(dǎo)致無法準(zhǔn)確地提取文檔的類別信息，造成分類效果不佳。因此，需要在不犧牲分類質(zhì)量的前提下盡可能地降低特征項(xiàng)空間的維數(shù)。特征選擇的任務(wù)就是要將信息量小，“不重要”的詞匯從特征項(xiàng)空間中刪除，從而減少特征項(xiàng)的個(gè)數(shù)，它是文本自動(dòng)分類系統(tǒng)中的一個(gè)關(guān)鍵步驟。常用的文本特征選擇方法有:文檔頻率()、信息增益()、互信息()、統(tǒng)計(jì)量()，文本證據(jù)權(quán)，優(yōu)勢(shì)率，統(tǒng)計(jì)()等。這些方法都是基于閾值的統(tǒng)計(jì)方法，它們的基本思想都是對(duì)每一個(gè)特征計(jì)算某種統(tǒng)計(jì)度量值，然后設(shè)定一個(gè)閩值，把度量值小于閾值的那些特征過濾掉，剩下的即認(rèn)為是有效特征。文檔頻率文檔頻率(Document Frequency)，就是文檔集合中出現(xiàn)某個(gè)特征項(xiàng)的文檔數(shù)目。在特征項(xiàng)選擇中，計(jì)算每個(gè)特征項(xiàng)在訓(xùn)練集合中出現(xiàn)的頻率，根據(jù)預(yù)先設(shè)定的閡值排除那些文檔頻率特別低和特別高的特征項(xiàng)。文檔頻率的計(jì)算復(fù)雜度較低，隨訓(xùn)練集的增加而線性增加，能夠適用于大規(guī)模語料，因此是特征降維的常用方法。其基本原則是:很少出現(xiàn)的特征對(duì)分類價(jià)值極小，對(duì)整個(gè)分類系統(tǒng)的效果影響也很小，因此，將這些特征去掉有助于降低特征空間維數(shù)，并且當(dāng)這些不常出現(xiàn)的特征為噪音時(shí)，還會(huì)有助于提高分類正確率。但在信息檢索領(lǐng)域，文檔頻率較低的特征項(xiàng)被認(rèn)為是信息含量較高，與文本分類中的原則是相反的。信息增益信息增益(Information Gain)，是一種在機(jī)器學(xué)習(xí)領(lǐng)域應(yīng)用較為廣泛的特征選擇方法。它從信息論角度出發(fā)，用各個(gè)特征取值情況來劃分學(xué)習(xí)樣本空間，根據(jù)所獲取信息增益的多寡，來選擇相應(yīng)的特征。其計(jì)算公式如下: （32）其中，表示文本中出現(xiàn)單詞時(shí)，文本屬于的概率；同樣表示文中不出現(xiàn)單詞時(shí)文本屬于的概率。 表示類文本在語料中現(xiàn)的概率。 表示在整個(gè)文本訓(xùn)練集中出現(xiàn)的概率。 互信息互信息方法(Mutual Information)，可以度量特征項(xiàng)和類別的共現(xiàn)關(guān)系，特征項(xiàng)對(duì)于類別的互信息越大，說明特征中包含的與類別有關(guān)的鑒別信息就越多。因此，互信息衡量的是詞與類之間的相關(guān)程度。文本分類中，一個(gè)特征詞只有一個(gè)信息增益和文檔頻率，但擁有的互信息數(shù)目卻是與訓(xùn)練語料中類別的數(shù)目相同的，對(duì)應(yīng)于每個(gè)類，該特征詞都會(huì)有一個(gè)互信息值。一個(gè)詞可以對(duì)應(yīng)幾個(gè)互信息值，一般來說，因?yàn)槲覀兊哪康氖沁x出對(duì)分類比較有用的詞，所以通常根據(jù)每個(gè)詞最大的互信息值來排序，然后從高到低選擇特征詞或者設(shè)定一個(gè)閾值排除那些互信息值比較低的詞。假設(shè)文檔集合分為類，記為，…，特征項(xiàng)對(duì)于文檔類別的互信息 (，)的計(jì)算公式如下: （33）其中 (，)為特征項(xiàng)出現(xiàn)在類中的概率， (，)為特征項(xiàng)在所有文檔中的出現(xiàn)概率。統(tǒng)計(jì)使用衡量特征項(xiàng)的重要程度時(shí)，只考慮到了正相關(guān)對(duì)特征項(xiàng)重要程度的影響。如果特征項(xiàng)和類別反相關(guān)，就說明含有特征項(xiàng)的文檔不屬于的概率要大一些，這對(duì)于判斷一篇文檔是否不屬于類別也是很有指導(dǎo)意義的。為克服這個(gè)缺陷，使用以下公式計(jì)算特征項(xiàng)和類別的相關(guān)性: （34）其中: 為和同時(shí)出現(xiàn)的次數(shù)。 為出現(xiàn)而沒有出現(xiàn)的次數(shù)。為出現(xiàn)而沒有出現(xiàn)的次數(shù)。 為和同時(shí)沒有出現(xiàn)的次數(shù)。為訓(xùn)練集中的文檔數(shù)。和類似，如果和不相關(guān)，則 (，)值為0，因?yàn)樵谶@種情況下，個(gè)訓(xùn)練文本的數(shù)目應(yīng)該在這四種文本中均勻分布，即===。而另一個(gè)極端，詞與類別非常相關(guān)，體現(xiàn)在這四個(gè)數(shù)量上，就是詞出現(xiàn)的文本屬于類別，而詞不出現(xiàn)的文本不屬于類別。這樣的話，==/2，而==。在衡量詞和類別之間的相關(guān)關(guān)系上，互信息和統(tǒng)計(jì)量之間有一定的相似之處。這兩個(gè)向量間的不同之處在于互信息是一個(gè)非規(guī)格化的值，其取值范圍很大，特別是對(duì)于那些邊緣概率分布很小的情況。而統(tǒng)計(jì)量則是一個(gè)規(guī)格化的量。對(duì)于詞，我們可以采用兩種方法來求取其在訓(xùn)練集上的統(tǒng)計(jì)量值： （35）或是： （36） 同相同，如果有個(gè)類，每個(gè)就會(huì)有個(gè)值，取它們的平均，就能得到特征選取所需的一個(gè)線性序列。平均值大的特征優(yōu)先被選取。算法的計(jì)算復(fù)雜度也為。 特征權(quán)方法基于術(shù)語在鄰近相關(guān)文檔中出現(xiàn)的頻率來測(cè)試術(shù)語的強(qiáng)度。和是任意不同但相關(guān)的文檔，術(shù)語的權(quán)值可由下式計(jì)算出: （37）但是實(shí)際中發(fā)現(xiàn)某些值很低的特征反而是信息量比較高的，不能從特征空間中刪去，因此這種方法在某些情況下不可靠。以上介紹了五種常用的特征選擇方法，它們具有的共同優(yōu)勢(shì)是計(jì)算量相對(duì)較小，而且結(jié)果特征集的解釋性強(qiáng)，就是原來特征詞集的子集，但是它們一些方面還需改進(jìn)，比如分類器的特征集包含很多冗余的信息，同義詞、多義詞都能造成這種情況。一個(gè)詞單獨(dú)可能對(duì)分類器的作用不大，選擇時(shí)被刪去，但和其它一些詞結(jié)合卻是很好的辨別因素等等。 特征項(xiàng)選擇出來后，要對(duì)每個(gè)項(xiàng)賦予權(quán)重，應(yīng)使文本中越重要的項(xiàng)的權(quán)重越大。目前最普遍的賦權(quán)重的方法是運(yùn)用統(tǒng)計(jì)方法，即用文本的統(tǒng)計(jì)信息，主要是詞頻，來計(jì)算特征項(xiàng)的權(quán)重。下面對(duì)常用的加權(quán)函數(shù)進(jìn)行詳細(xì)介紹。 布爾權(quán)重布爾權(quán)重是最簡(jiǎn)單的一種加權(quán)方法，如果特征詞出現(xiàn)次數(shù)為0，則其權(quán)重為0，如果特征詞出現(xiàn)詞數(shù)大于0，則其權(quán)重為1。公式如下: （38）其中表示特征詞在文檔中的權(quán)重，表示特征詞在文檔中出現(xiàn)次數(shù)。 詞頻權(quán)重該方法將特征詞的頻次作為權(quán)重。公式如下： （39） 權(quán)重該方法基于以下兩點(diǎn)原因:一是特征詞在文檔中出現(xiàn)詞數(shù)越多越重要，權(quán)重和成正比。二是文檔集中含有特征詞的文檔數(shù)越大越不重要，權(quán)重和成反比。公式如下: （310）該式表明，若特征詞在所有文檔中均出現(xiàn)，即=，則=0，也就是說，雖然特征詞出現(xiàn)次數(shù)多，但它的分布比較均勻，說明它沒有區(qū)分類別的能力。考慮到文檔長(zhǎng)度的影響，對(duì)上面公式進(jìn)行歸一化: （311）為了降低的作用將式(311)調(diào)整為： （312）文本分類模式CjCkCjCjCk圖33 樣本的多峰分布 圖34 樣本的邊界重疊文本分類器包括兩個(gè)要素，一個(gè)是文本存在的特征空間，另一個(gè)是在該特征空間中所采取的分類方法。分類器的構(gòu)造模式有兩種，一種是單分類器模式，一種是多分類模式[15][16]，分別敘述如下:（1）單分類器模式所謂單分類模式，是指文本的全集及類別的全集共享一個(gè)特征空間，所有的文本及類別在這個(gè)特征空間中的不同區(qū)域內(nèi)分布，并在這個(gè)特征空間中執(zhí)行一種分類方法。在單分類器模式下的輸出為待分類文本所屬的具體的類別[12]。由于各個(gè)類別的樣本同時(shí)存在于一個(gè)特征空間中，因而各個(gè)類別的樣本之間存在著多峰分布和邊界重疊的問題(見圖33，34)。具體地說，就是同類樣本之間的距離可能會(huì)大于不同樣本之間的距離，各類樣本存在著混雜分布的情況。同類樣本的分布不夠緊湊，大多數(shù)的樣本處于類別的邊界，類與類之間存在著邊界重疊的情況。這樣一來，在單分類器模式下，對(duì)處于這兩種情況下的樣本，很難給予正確的分類。比如，圖34中位于和類交界處的樣本，就無法區(qū)分他們究竟屬于類還是屬于類。而對(duì)于圖33所示的情況，在采用KNN法或SVM法的時(shí)候，很難給予正確的分類，而采用Rocchio法則需要很好地選擇類向量。（2）、多分類器模式CjCj圖35 多分類器模式下類樣本的多峰分布所謂多分類器模式，是指各類的文本獨(dú)享一個(gè)特征子空間，每個(gè)類的文本只在自己的特征子空間中分布，類與類的特征子空間之間相互獨(dú)立，各個(gè)特征子空間中可以執(zhí)行不同的分類方法。多分類器模式下，每個(gè)類別的分類器的輸出為待分類文本是否屬于該類別。這種模式下，不會(huì)存在各類的樣本混雜分布的情況，同類樣本之間的多峰分布表現(xiàn)為該類樣本在自己的特征子空間中的不同區(qū)域內(nèi)分布(圖35)。對(duì)于樣本的邊界重疊問題，也就是對(duì)存在著兼類現(xiàn)象的文本，在多分類器模式下，會(huì)對(duì)此類文本賦予多個(gè)類別。多分類