0 引言

    文本分類(lèi)(Text Classification)是指在給定的分類(lèi)體系下，由計(jì)算機(jī)通過(guò)某種分類(lèi)算法將未知類(lèi)別的文本進(jìn)行自動(dòng)歸類(lèi)的過(guò)程。最近十幾年，文本分類(lèi)得到了迅速的發(fā)展，并且被廣泛應(yīng)用到許多領(lǐng)域，包括：數(shù)字圖書(shū)館、網(wǎng)頁(yè)分類(lèi)、垃圾電子郵件過(guò)濾等。到目前為止，已經(jīng)有許多基于統(tǒng)計(jì)學(xué)理論和機(jī)器學(xué)習(xí)的文本分類(lèi)方法，如決策樹(shù)（Decision Tree）、貝葉斯方法、KNN、神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)(SVM)等^[1]。然而，這些分類(lèi)方法的研究和應(yīng)用都是基于長(zhǎng)文本的，而目前短文本在網(wǎng)絡(luò)上使用越來(lái)越普遍。最近新興起的微博客的最大的特點(diǎn)就是“微”，一般發(fā)布的消息只能是只言片語(yǔ)。著名流量統(tǒng)計(jì)網(wǎng)站ALEXA的數(shù)據(jù)顯示，Twitter日均訪問(wèn)量已近2 000萬(wàn)人次，在美國(guó)、英國(guó)、加拿大等地的網(wǎng)站排名中均列前15位。在專(zhuān)業(yè)或者垂直搜索領(lǐng)域，由于資源限制，無(wú)法對(duì)全文進(jìn)行處理，轉(zhuǎn)而根據(jù)文章標(biāo)題或文章摘要進(jìn)行分類(lèi)。這些應(yīng)用場(chǎng)合都需要短文本分類(lèi)技術(shù)。針對(duì)實(shí)際的需求以及傳統(tǒng)方法的不足，本文提出了一種新的分類(lèi)方法，利用搜索實(shí)現(xiàn)基于類(lèi)似NaiveBayes的文本分類(lèi)方法。對(duì)比實(shí)驗(yàn)表明，在短文本的分類(lèi)上，此方法比傳統(tǒng)的分類(lèi)方法提高了準(zhǔn)確率和分類(lèi)速度。

1 相關(guān)工作介紹

    在過(guò)去的四十多年中，許多關(guān)于文本分類(lèi)的研究工作都是圍繞著Salton提出的向量空間模型(VSM)展開(kāi)的，向量空間模型的基本思想是以向量來(lái)表示文本：(W₁，W₂，…，W_n)，首先將文本進(jìn)行分詞，由這些詞作為向量的維數(shù)，用詞頻來(lái)表示特征項(xiàng)對(duì)應(yīng)的向量分量，詞頻計(jì)算方法主要運(yùn)用TF-IDF公式。對(duì)于向量空間法的研究工作主要集中在特征選取和特征權(quán)重的調(diào)整上來(lái)提高分類(lèi)的性能，如陸玉昌先生在特征選取中利用評(píng)估函數(shù)代替TF-IDF公式進(jìn)行權(quán)值調(diào)整^[2]。

    神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法在文本分類(lèi)中的研究和應(yīng)用也非常廣泛，其中最流行的神經(jīng)網(wǎng)絡(luò)算法是1986年由RUMELHARD D E和MCCLELLAND J L提出的后向傳播算法(簡(jiǎn)稱(chēng)BP算法)^[3]。由于BP算法存在收斂速度慢、容易陷入局部極小值等問(wèn)題，后人對(duì)BP算法進(jìn)行了多方面的改進(jìn)，如李曉峰提出了BP神經(jīng)網(wǎng)絡(luò)動(dòng)態(tài)全參數(shù)自動(dòng)調(diào)整學(xué)習(xí)算法^[4]。神經(jīng)網(wǎng)絡(luò)擁有很好的對(duì)噪音數(shù)據(jù)的承受能力和文本分類(lèi)能力，但是需要大量的參數(shù)，這些通常主要靠經(jīng)驗(yàn)確定。另外神經(jīng)網(wǎng)絡(luò)需要很長(zhǎng)的訓(xùn)練時(shí)間，因此它適用于有足夠長(zhǎng)訓(xùn)練時(shí)間的應(yīng)用。

    王建會(huì)等提出了基于互依賴(lài)和等效半徑、簡(jiǎn)單但高效的分類(lèi)算法SECTILE^[5]，該方法提出互依賴(lài)（Mutual Dependence，MD）模型，并將其與N-gram結(jié)合起來(lái)進(jìn)行特征屬性選擇，提高了屬性選擇的準(zhǔn)確性，實(shí)現(xiàn)了有效地降維。引入等效半徑(Equivalent Radius，ER)的概念,用基于等效半徑的相對(duì)距離代替?zhèn)鹘y(tǒng)的歐氏距離，提高了分類(lèi)精度。SECTILE分類(lèi)算法計(jì)算復(fù)雜度低，分類(lèi)模型容易更新，適用于大規(guī)模信息樣本分類(lèi)場(chǎng)合。

    石志偉等提出了向量空間法和k近鄰的組合分類(lèi)方法^[6]，該方法將整個(gè)實(shí)例空間劃分為正實(shí)例、負(fù)實(shí)例和混合實(shí)例三部分，根據(jù)查詢(xún)實(shí)例落入不同的區(qū)域調(diào)用不同的分類(lèi)算法。該方法充分利用了向量空間法分類(lèi)速度快和k近鄰方法分類(lèi)精度高的優(yōu)勢(shì)。

    以上提到的各種分類(lèi)方法都適用于長(zhǎng)文本的分類(lèi)，由于短文本相對(duì)于長(zhǎng)文本要短得多，文本中的特征數(shù)很少，并且文本之間很少含有相同的特征，因此傳統(tǒng)的文本分類(lèi)方法并不適合短文本分類(lèi)。目前專(zhuān)門(mén)研究短文本分類(lèi)的工作還較少，大致分為兩種研究方向：一種是通過(guò)外部資源來(lái)增加文本之間共享的特征，豐富文本的上下文，例如Wikipedia被作為外部資源引入短文本分類(lèi)中^[7]，從而可以使用傳統(tǒng)的文本分類(lèi)方法；另一種是充分利用這些稀疏的特征，對(duì)短文本進(jìn)行預(yù)處理。下面介紹一些針對(duì)短文本分類(lèi)的研究工作。

    蒲強(qiáng)等提出基于獨(dú)立分量分析（Independent Component Analysis，ICA）和潛在語(yǔ)義分析（Latent Semantic Analysis，LSA）的短文本分類(lèi)方法^[8]，該方法首先通過(guò)LSA對(duì)文本進(jìn)行預(yù)處理，然后對(duì)處理結(jié)果再進(jìn)行獨(dú)立分量分析。LSA利用奇異值分解（Singular Value Decomposition，SVD）降秩方法實(shí)現(xiàn)信息抽取和噪聲去除，將文檔的高維表示投影在低維的潛在語(yǔ)義空間中，從而呈現(xiàn)出潛在的語(yǔ)義結(jié)構(gòu)。然而對(duì)原始詞——文檔矩陣進(jìn)行SVD，選取最大的一些奇異值對(duì)應(yīng)的特征作為潛在語(yǔ)義空間，目前沒(méi)有理論證明奇異值最大的那些特征具有最好的分類(lèi)能力，所以在該潛在語(yǔ)義空間上進(jìn)行文本分類(lèi)，分類(lèi)效果并沒(méi)有得到改善。

    滕少華等提出基于條件隨機(jī)場(chǎng)（Conditional Random Fields，CRFs）的短文本分類(lèi)方法^[9]，該方法認(rèn)為短文本通常集中于一個(gè)主題，從而文本中的特征也具有很強(qiáng)的相關(guān)性。根據(jù)這種性質(zhì)，該方法利用中文分詞中的字標(biāo)注方法，將短文本分類(lèi)問(wèn)題轉(zhuǎn)化成序列標(biāo)注問(wèn)題，從而可以使用CRFs來(lái)解決短文本分類(lèi)問(wèn)題。然而CRFs依賴(lài)于高置信度特征，高置信度特征也可以引入干擾，這樣就很容易導(dǎo)致分詞錯(cuò)誤，這種困難很難依靠CRFs自身來(lái)解決。雖然可以通過(guò)對(duì)基于CRFs的分詞結(jié)果進(jìn)行后處理來(lái)解決該問(wèn)題，但是這種方法有它的局限性，只能使用基于CRFs的中文分詞。

    綜上所述，目前的短文本分類(lèi)方法不能有效地選擇那些分類(lèi)能力好的特征，分類(lèi)準(zhǔn)確度低，分類(lèi)速度慢；或者依賴(lài)于中文分詞系統(tǒng)，擴(kuò)展性差。本文提出的基于搜索的Na?觙veBayes文本分類(lèi)方法在這些方面進(jìn)行了改進(jìn)。

2 基于搜索的樸素貝葉斯分類(lèi)算法

    基于搜索的樸素貝葉斯文本分類(lèi)是將搜索技術(shù)應(yīng)用到文本分類(lèi)中，并對(duì)樸素貝葉斯分類(lèi)算法進(jìn)行改進(jìn)，從而實(shí)現(xiàn)的一種適合短文本分類(lèi)的分類(lèi)方法。分類(lèi)算法如下：

    令C={c₁，c₂，…，c_m}是預(yù)定義的類(lèi)別集，D={d₁，d₂，…，d_n}是待分類(lèi)的文檔集，d={w₁，w₂，…，w_n}是一個(gè)文檔的特征向量，文檔d_i屬于類(lèi)別c_j的概率可以由條件概率P(c_j|d_i)表示。根據(jù)貝葉斯公式：

    式(2)、式(4)中，|c|為文本的類(lèi)別數(shù)，分子上的1是為了防止出現(xiàn)概率為零的情況進(jìn)行的加權(quán)處理。

    為了計(jì)算簡(jiǎn)便，不妨在選取訓(xùn)練數(shù)據(jù)時(shí)規(guī)定各類(lèi)別中的文本數(shù)一樣多。這樣，對(duì)于每一個(gè)文本類(lèi)別來(lái)說(shuō)，先驗(yàn)概率是相等的，計(jì)算P(c_j)的過(guò)程也可以忽略不計(jì)。計(jì)算貝葉斯概率也就簡(jiǎn)化成了計(jì)算文檔d_i屬于類(lèi)別c_j的后驗(yàn)概率：

    在式(5)中，對(duì)于每一類(lèi)別來(lái)說(shuō)，分母部分N(c_j)+|c|是相等的，即不影響屬于每一類(lèi)別的概率大小比較，這樣就直接計(jì)算：

    而為了防止出現(xiàn)負(fù)無(wú)窮和零的情況，只需要知道每一個(gè)屬性(詞)在指定類(lèi)別中出現(xiàn)的文檔個(gè)數(shù)，即N(w_i|c_j)。

    結(jié)合上面的公式推導(dǎo)，可以將基于搜索的NaiveBayes文本分類(lèi)算法描述如下：

    (1)假定有m個(gè)類(lèi)別C₁，C₂，…，C_m。分別對(duì)每一類(lèi)別中的數(shù)據(jù)樣本進(jìn)行中文分詞，建立索引C_Index1，C_Index2，…，C_Indexm；

    (2)給定一個(gè)沒(méi)有類(lèi)標(biāo)號(hào)的數(shù)據(jù)樣本X，對(duì)其進(jìn)行中文分詞(分詞系統(tǒng)要和步驟(1)用到的分詞系統(tǒng)保持一致)，每個(gè)詞對(duì)應(yīng)一個(gè)屬性，分別為W₁，W₂，…，W_n；

    (3)求將數(shù)據(jù)樣本X分配給類(lèi)別C_j的概率，即：

    換言之，X被分配到使P(w|c_i)最大的類(lèi)別C_i。

    注意：步驟(1)也可以看作是建立分類(lèi)模型，此步不影響分類(lèi)的速度，因?yàn)榻⒎诸?lèi)模型是在進(jìn)行文本分類(lèi)之前做的。基于搜索的NaiveBayes分類(lèi)器模型是對(duì)已知類(lèi)標(biāo)號(hào)的訓(xùn)練數(shù)據(jù)集建立的索引，并且各個(gè)類(lèi)別的訓(xùn)練數(shù)據(jù)文本數(shù)是相等的。這也是基于搜索的NaiveBayes分類(lèi)器和其他分類(lèi)器的不同之處。為了提高速度，本文使用了Lucene.Net搜索技術(shù)。Lucene.Net中自帶的StandardAnalyzer分詞器是以字為單位索引的，對(duì)于中文文本分類(lèi)來(lái)說(shuō)，按單字分詞會(huì)影響分類(lèi)的精度，所以本文使用了KTDictSeg分詞系統(tǒng)，KTDictSeg是由KaiToo搜索開(kāi)發(fā)的一款基于字典的開(kāi)源的中英文分詞系統(tǒng)。KTDictSeg可以識(shí)別中文人名，還有對(duì)Lucene.net 的支持，提供KTDictSegAnalyzer 分析器給Lucene.net。

    分類(lèi)器效率的評(píng)估結(jié)果可以有多種，比如分類(lèi)的準(zhǔn)確率、速度、可規(guī)模性等。而評(píng)估的方法也有多種，最簡(jiǎn)單的是保持(Holdout)方法，即使用類(lèi)標(biāo)號(hào)已知的數(shù)據(jù)來(lái)測(cè)試分類(lèi)器。在認(rèn)為分類(lèi)器的準(zhǔn)確率可以接受時(shí)，就可以利用此分類(lèi)器對(duì)類(lèi)標(biāo)號(hào)未知的數(shù)據(jù)進(jìn)行分類(lèi)預(yù)測(cè)。

3 實(shí)驗(yàn)及結(jié)果分析

    對(duì)于中文文本分類(lèi)而言，目前還沒(méi)有標(biāo)準(zhǔn)的語(yǔ)料庫(kù)可供使用。因此，本文使用搜狗實(shí)驗(yàn)室整理的語(yǔ)料庫(kù)(SogouC.reduced.20061127)，此語(yǔ)料庫(kù)包含了九個(gè)類(lèi)別，分別是財(cái)經(jīng)、IT、健康、體育、旅游、教育、招聘、文化、軍事，每一類(lèi)包含1 990篇文章。對(duì)此語(yǔ)料庫(kù)做一下簡(jiǎn)單整理，從每一類(lèi)中隨機(jī)選出160篇文章作為測(cè)試數(shù)據(jù)，用剩余的1 830篇文章作為訓(xùn)練數(shù)據(jù)建立分類(lèi)模型。用準(zhǔn)備好的測(cè)試數(shù)據(jù)對(duì)基于搜索的NaiveBayes文本分類(lèi)器和weka的NaiveBayes文本分類(lèi)器進(jìn)行測(cè)試，測(cè)試結(jié)果如表1所示。

    從表1可以看出，基于搜索的NaiveBayes分類(lèi)器和weka的NaiveBayes分類(lèi)器不相上下。但是，為了體現(xiàn)基于搜索的NaiveBayes分類(lèi)器對(duì)于短文本分類(lèi)的優(yōu)越性，對(duì)這1 440篇測(cè)試數(shù)據(jù)做一下簡(jiǎn)單處理后再次進(jìn)行測(cè)試，即每一類(lèi)中包含50字以?xún)?nèi)的文本50篇、50～200字的文本50篇、200～1 000字的文本50篇和1 000字以上的文本50篇。這樣測(cè)試數(shù)據(jù)就按照文本字?jǐn)?shù)的多少分為了不同的等級(jí)，并且測(cè)試數(shù)據(jù)文本數(shù)也增加到了1 800篇。然后用整理后的測(cè)試數(shù)據(jù)對(duì)兩種分類(lèi)器進(jìn)行測(cè)試，測(cè)試結(jié)果如表2所示。

    根據(jù)表2的數(shù)據(jù)繪制出分類(lèi)準(zhǔn)確率的曲線圖，如圖1所示。

    通過(guò)圖1可以清楚地看到，對(duì)于100字以?xún)?nèi)的短文本的分類(lèi)，基于搜索的NaiveBayes分類(lèi)器在分類(lèi)精度方面表現(xiàn)出了優(yōu)越的性能。通過(guò)表2和表1的比較也不難發(fā)現(xiàn)，對(duì)于1 440篇長(zhǎng)文本的分類(lèi)，基于搜索的NaiveBayes分類(lèi)器耗時(shí)12.587 5 s；而對(duì)于加入了短文本的1 800篇文本的分類(lèi)，基于搜索的NaiveBayes分類(lèi)器耗時(shí)13.006 2 s。從數(shù)字上可以看出，對(duì)于短文本的分類(lèi)，基于搜索的NaiveBayes分類(lèi)器在分類(lèi)速度上也明顯提高。

    這說(shuō)明基于搜索的NaiveBayes分類(lèi)方法對(duì)短文本的處理得到了很好的分類(lèi)效果，并且并沒(méi)有因?yàn)檫x取全部的文本特征而降低分類(lèi)速度，相反，由于搜索技術(shù)的引入，從某種程度上還提高了文本分類(lèi)的速度。

4 結(jié)論

    本文針對(duì)傳統(tǒng)的文本分類(lèi)方法對(duì)短文本分類(lèi)的不足，提出了基于搜索的NaiveBayes文本分類(lèi)方法。該方法與傳統(tǒng)的文本分類(lèi)方法的不同之處在于，它將搜索引擎技術(shù)應(yīng)用到了文本分類(lèi)中，并對(duì)樸素貝葉斯分類(lèi)算法進(jìn)行了改進(jìn)。實(shí)驗(yàn)結(jié)果表明，對(duì)于短本文的分類(lèi)，基于搜索的NaiveBayes分類(lèi)方法不僅大大提高了分類(lèi)的準(zhǔn)確度，同時(shí)降低了時(shí)間復(fù)雜度。另外，在文本特征提取和中文文本停詞的處理方面，針對(duì)不同的應(yīng)用背景還需要做進(jìn)一步的研究。實(shí)驗(yàn)用的語(yǔ)料庫(kù)不是標(biāo)準(zhǔn)的語(yǔ)料庫(kù)，僅僅有17 910篇文章，因此，實(shí)驗(yàn)的規(guī)模有待進(jìn)一步擴(kuò)大。在應(yīng)用前景方面，隨著通信技術(shù)和互聯(lián)網(wǎng)的發(fā)展，電子郵件、短信、微博信息等各種短文本信息迅速增加，基于搜索的NaiveBayes文本分類(lèi)器必將會(huì)得到廣泛的應(yīng)用。

參考文獻(xiàn)

[1] Wu Xindong，KUMAR V，QUINLAN J R，et al.Top 10 algorithms in data mining[J].Knowl.Inf.Syst.，2008(14)：24-27.

[2] 陸玉昌，魯明羽，李凡，等.向量空間法中單詞權(quán)重函數(shù)的分析和構(gòu)造[J].計(jì)算機(jī)研究與發(fā)展，2002，39(10)：1205-1210.

[3] RUMELHART D E，MCCLELLAND J L.Parallel distributed processing：explorations in microstructure of cognition，Vol.1：Foundations[M].Cambridge：MIT Press，1986：318-364.

[4] 李曉峰.動(dòng)態(tài)全參數(shù)自調(diào)整BP神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)模型的建立[J].預(yù)測(cè)，2001，20(3)：69-71.

[5] 王建會(huì)，王洪偉，申展，等.一種實(shí)用高效的文本分類(lèi)算法[J].計(jì)算機(jī)研究與發(fā)展，2005，42(1)：85-93.

[6] 石志偉，劉濤，吳功宜.一種快速高效的文本分類(lèi)方法[J].計(jì)算機(jī)工程與應(yīng)用，2005，41(29)：180-183.

[7] SCHONHOFEN P.Identifying document topics using the Wikipedia category network[C].Proc.the IEEE/WIC/ACM International Conference on Web Intelligence，2006：456-462.

[8] Pu Qiang，Yang Guowei.Short-text classification based on ICA and LSA[C].Berlin：Springer-Verlag Berlin/Heidelberg，2006：265-270.

[9] 滕少華.基于CRFs的中文分詞和短文本分類(lèi)技術(shù)[D].北京：清華大學(xué)，2009.

作者信息:

康  衛(wèi)1，邱紅哲2，焦冬冬1，房志奇1，于寅虎1

(1.華北計(jì)算機(jī)系統(tǒng)工程研究所，北京100083；2.北京航天飛行控制中心，北京100094）