基于樸素貝葉斯分類器的朝鮮語(yǔ)文本分類的研究

周國(guó)強(qiáng),崔榮一

(延邊大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科 智能信息處理研究室，吉林 延吉 133002)

1 引言

文本分類是信息處理領(lǐng)域中重要的研究方向之一[1]。朝鮮語(yǔ)在中國(guó)來(lái)說(shuō)是少數(shù)民族語(yǔ)言，它是朝鮮族溝通意圖的主要語(yǔ)言，在民族文化傳承和發(fā)展中起著重要的作用。由于朝鮮語(yǔ)的詞法結(jié)構(gòu)和語(yǔ)法結(jié)構(gòu)與中文有較大的差異，具有其特殊性[2]，因此對(duì)朝鮮語(yǔ)文本的研究具有非常重要的意義。

文本分類是基于文本內(nèi)容將待定文本劃分到一個(gè)或多個(gè)預(yù)先定義的類中的方法，它廣泛應(yīng)用于信息自動(dòng)檢索、文本過(guò)濾和網(wǎng)頁(yè)層次分類領(lǐng)域。文本分類大致可分為： 文本的向量模型表示、文本的特

征選擇和分類器訓(xùn)練。數(shù)量巨大的訓(xùn)練樣本和過(guò)高的向量維數(shù)是文本分類的兩大難點(diǎn)。它們決定文本分類問(wèn)題是一個(gè)時(shí)間和空間復(fù)雜度很高的學(xué)習(xí)問(wèn)題。為兼顧運(yùn)算時(shí)間和分類精度兩個(gè)方面，不得不進(jìn)行特征選擇，力求在不損傷分類性能的同時(shí)來(lái)達(dá)到降維的目的。目前，許多基于統(tǒng)計(jì)理論和機(jī)器學(xué)習(xí)方法的技術(shù)應(yīng)用于文本分類中，包括決策樹(shù)、Bayes方法、神經(jīng)網(wǎng)絡(luò)、基于關(guān)聯(lián)的方法、k2最近鄰方法、遺傳算法、粗糙集等方法[3-5]。

本文通過(guò)分析朝鮮語(yǔ)的特征，利用改進(jìn)的基于類別分布的特征選擇方法以及權(quán)重計(jì)算方法在朝鮮語(yǔ)文本集上進(jìn)行了研究，并基于樸素貝葉斯分類器實(shí)現(xiàn)了對(duì)朝鮮語(yǔ)文本的分類。

2 特征向量

文本分類的前提是特征向量模型的建立。本文對(duì)朝鮮語(yǔ)文本進(jìn)行分詞后，通過(guò)特征選擇實(shí)現(xiàn)降維，通過(guò)特征加權(quán)提高分類的準(zhǔn)確度。

2.1 特征選擇

特征選擇是指從最初的n個(gè)特征中選取t(t

本文采用一個(gè)基于類別分布的特征選擇方法。該方法的基本思想是，對(duì)于那些對(duì)分類有很大貢獻(xiàn)的特征詞應(yīng)該是在該類文檔中出現(xiàn)頻率足夠高而在其他類文檔中出現(xiàn)頻率足夠低的特征詞。那么少見(jiàn)詞和平凡詞在訓(xùn)練集所有文檔分詞后存儲(chǔ)的情況，要么是只有一個(gè)類中的詞頻計(jì)數(shù)很少，要么是在大多數(shù)類別中出現(xiàn)的很多?；谶@種情況，將分詞后在各個(gè)類別中出現(xiàn)特征詞的文檔頻度計(jì)數(shù)和在所有類別中出現(xiàn)該特征詞的文檔頻度計(jì)數(shù)總和相比，就可以得到該特征詞在各個(gè)類別中出現(xiàn)的分布情況。通過(guò)這個(gè)分布情況，去除那些少見(jiàn)詞和平凡詞，從而保留那些次關(guān)鍵詞、關(guān)鍵詞，達(dá)到特征選擇的目的。

對(duì)于少見(jiàn)詞的去除，根據(jù)定義設(shè)置一個(gè)閾值α，如果滿足條件(1)式就將該特征詞歸為少見(jiàn)詞，并予以去除：

DFi<α,DFj=0,i=1,2,…,n,

j=1,2,…,i-1,i+1,…,n

(1)

在(1)式中將在某類中出現(xiàn)的文檔頻度計(jì)數(shù)小于閾值α且在其他類別中文檔頻度計(jì)數(shù)為0的特征詞歸為少見(jiàn)詞，其中，DFi表示在i類中出現(xiàn)某特征詞的文檔頻度計(jì)數(shù)，n表示訓(xùn)練集中出現(xiàn)的類別總數(shù)量。

如何給定平凡詞，次關(guān)鍵詞的區(qū)分標(biāo)準(zhǔn)是一個(gè)問(wèn)題。到底一個(gè)特征詞在多少個(gè)類別中大量出現(xiàn)，才算是平凡詞?這里需要設(shè)置一個(gè)閾值D來(lái)加以確定。本文給出一個(gè)判別方法，如下： 如果某特征詞滿足條件(2)式，即將該特征歸為平凡詞，并予以刪除。

(2)

(2)式表示某特征詞在每個(gè)類別中出現(xiàn)該詞的文檔頻度計(jì)數(shù)與所有出現(xiàn)的類別中出現(xiàn)該詞的文檔頻度計(jì)數(shù)總數(shù)的比例小于等于閾值γ的話，就將該特征詞作為平凡詞。在實(shí)際實(shí)驗(yàn)中，使用條件(2)逆反條件來(lái)進(jìn)行判斷，即只要該特征詞在某個(gè)類別中出現(xiàn)該詞的文檔頻度總數(shù)大于閾值γ的話，就可以將該詞作為次關(guān)鍵詞予以保留。

本文實(shí)驗(yàn)中，將訓(xùn)練集文本分詞后，將各特征詞在各個(gè)文檔中出現(xiàn)的詞頻計(jì)數(shù)存入文本中，因此容易得到每個(gè)特征詞在每個(gè)類別中出現(xiàn)該特征詞的文檔頻度。

該方法的具體步驟描述如下：

Step1： 按照特征子集S中的特征詞，得到每個(gè)特征詞在每個(gè)類別中出現(xiàn)該詞的文檔頻度計(jì)數(shù)與所有類別中出現(xiàn)該詞的文檔頻度計(jì)數(shù)總數(shù)。

Step2： 判斷該特征詞是否為少見(jiàn)詞，判斷條件為(1)式，如果是的話，將該特征詞從特征子集S中去除，并轉(zhuǎn)到步驟1，否則轉(zhuǎn)至步驟3。

Step3： 如果出現(xiàn)該特征詞的類別總數(shù)大于閾值β，那么計(jì)算在各個(gè)類別中出現(xiàn)該特征詞的文檔頻度計(jì)數(shù)和在所有類別中出現(xiàn)該特征詞的文檔頻度計(jì)數(shù)總和的比例di，如果存在一個(gè)di大于閾值，則將該特征詞作為次關(guān)鍵詞保留，如果沒(méi)有任何di大于閾值，就將該特征詞作為平凡詞去除。如果特征子集S中還有特征詞未進(jìn)行特征選擇，則轉(zhuǎn)至步驟1，否則轉(zhuǎn)至步驟4。

Step4： 最終得到一個(gè)去除掉少見(jiàn)詞和平凡詞的特征子集。

經(jīng)過(guò)這種基于類別分布的特征選擇后，過(guò)濾掉少見(jiàn)詞和平凡詞，達(dá)到了特征詞維度下降的目的。

2.2 特征權(quán)重

文本特征的權(quán)重全面權(quán)衡反映該特征詞對(duì)標(biāo)識(shí)文本內(nèi)容的貢獻(xiàn)度和區(qū)分文本的能力。不合理的特征權(quán)重估算方法會(huì)使分類的效果變差，而好的合理的特征權(quán)重估算方法卻可以使特征詞對(duì)分類的作用變得顯著。本文從樸素的貝葉斯分類的特點(diǎn)出發(fā)，提出一種類TF-IDF特征估算方法[7-8]。

利用式(5)來(lái)表示特征詞tk對(duì)Ci類的區(qū)分能力。

(5)

為保證分母不為零值，對(duì)分母加一個(gè)參數(shù)值L，L的值取0.1，得到公式(6)：

(6)

對(duì)公式(6)取對(duì)數(shù)，那么特征詞tk在第Ci類中的權(quán)重估算方法公式如下：

(7)

在公式(7)中，DFik表示在Ci中包含特征詞tk的文檔數(shù)，N為訓(xùn)練集中的文檔總數(shù)。在公式中前半部分DFik表示特征詞tk在第Ci類中的重要程度，當(dāng)DFik等于0時(shí)，說(shuō)明特征詞tk在Ci類中沒(méi)有出現(xiàn)，我們將權(quán)值設(shè)為0。當(dāng)DFik不等于0時(shí)，公式后半部分的對(duì)數(shù)表示了特征詞tk在訓(xùn)練集中出現(xiàn)的幾個(gè)類別里的分布情況。

3 樸素貝葉斯分類器

3.1 基本原理

在機(jī)器學(xué)習(xí)中，通常感興趣的是在給定數(shù)據(jù)集D時(shí)，確定假設(shè)空間H中的最佳假設(shè)。所謂最佳假設(shè)是在給定的數(shù)據(jù)集D以及H中不同假設(shè)的先驗(yàn)概率的有關(guān)知識(shí)的最可能假設(shè)。

BNC[9-10]提供了直接計(jì)算這種可能性的方法，其分類原理是通過(guò)某對(duì)象的先驗(yàn)概率，利用貝葉斯公式計(jì)算出其后驗(yàn)概率，選擇具有最大后驗(yàn)概率的類作為該對(duì)象所屬的類。形式化描述為：

設(shè)每個(gè)數(shù)據(jù)樣本用一個(gè)n維特征向量來(lái)描述n個(gè)屬性的值，即：A={a1,a2,…,an}，則給定一個(gè)未知的數(shù)據(jù)樣本，得到的最可能的目標(biāo)值為：

Vmap=arg maxP(Vj|a1,a2,…,an)，其中Vj∈V。

假定有m個(gè)類，分別用V1,V2,…,Vm來(lái)表示。給定一個(gè)未知的數(shù)據(jù)樣本X(即沒(méi)有類標(biāo)號(hào))，根據(jù)貝葉斯定理，可得：

(8)

由于P(X)對(duì)于所有類為常數(shù)，最大后驗(yàn)概率P(Vi|X)可轉(zhuǎn)化為最大化先驗(yàn)概率P(X|Vi)P(Vi)。由于假設(shè)各屬性的取值是相互獨(dú)立的，所以，先驗(yàn)概率p(x1|Vi),p(x2|Vi),…,p(xn|Vi)可以從訓(xùn)練數(shù)據(jù)集中求得。

(9)

根據(jù)此方法，對(duì)一個(gè)未知類別的樣本X，可以先分別計(jì)算出X屬于每一個(gè)類別Vi的概率P(X|Vi)P(Vi)，然后選擇其中概率最大的類別作為其類別。

3.2 文本分類實(shí)現(xiàn)

文本分類流程如圖1所示，具體步驟描述如下：

圖1 文本分類流程

Step1: 對(duì)訓(xùn)練樣本集的文檔進(jìn)行分詞，利用本文基于類別分類的方法進(jìn)行特征選擇，計(jì)算權(quán)重；

Step2: 利用step1中所得數(shù)據(jù)進(jìn)行樸素貝葉斯分類器的構(gòu)造；

Step3: 測(cè)試分類器，其中，測(cè)試樣本集是由剩余的文檔集組成；

Step4: 輸出分類結(jié)果。

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

本文的語(yǔ)料庫(kù)來(lái)自互聯(lián)網(wǎng)韓國(guó)各網(wǎng)站采集的450個(gè)大小的文檔集，其中包括9個(gè)類別，分別是財(cái)經(jīng)、IT、健康、體育、旅游、教育、招聘、文化、軍事，每個(gè)類別是由50個(gè)文檔構(gòu)成的文檔集?；谶@些素材，本文在matlab中進(jìn)行了實(shí)驗(yàn)。

本文采用查準(zhǔn)率和查全率作為評(píng)估方法，查準(zhǔn)率如公式(10),查全率如公式(11)。

TPi表示測(cè)試文檔集中本來(lái)屬于類別Ci而且分類器分類到類別Ci的文檔數(shù)，F(xiàn)Pi表示測(cè)試文檔集中本來(lái)不屬于類別Ci但被分類器錯(cuò)誤分到Ci的文檔數(shù)，F(xiàn)Ni表示本來(lái)應(yīng)該屬于類別Ci但被分類器分類到其他別的類別的文檔數(shù)。

表1 分類器分類測(cè)試結(jié)果

由表1的實(shí)驗(yàn)數(shù)據(jù)上看來(lái)，采用新的特征選擇方法的本文方法在分類效果上比貝葉斯文本分類要好，表明本文方法在朝鮮語(yǔ)文本分類上能取得較好的效果。

5 結(jié)論及下一步工作

本文結(jié)合樸素貝葉斯分類器對(duì)朝鮮語(yǔ)文本分類進(jìn)行了研究，提出了基于類別選擇的特征選擇方法對(duì)朝鮮語(yǔ)文檔進(jìn)行分類。本文方法充分考慮到朝鮮語(yǔ)特征詞對(duì)分類結(jié)果的影響以及分類的復(fù)雜度。實(shí)驗(yàn)數(shù)據(jù)分析結(jié)果表明，本方法取得了較好的分類結(jié)果，為實(shí)現(xiàn)跨語(yǔ)言的朝漢文本檢索提供了一定的依據(jù)。

由于本文構(gòu)造的語(yǔ)料庫(kù)的文檔數(shù)量不是很多，可能存在一定的誤差，增大語(yǔ)料庫(kù)規(guī)模，考慮朝漢文本的跨語(yǔ)言分類是下一步的研究工作。

[1] 蘇金樹(shù), 張博鋒. 基于機(jī)器學(xué)習(xí)的文本分類技術(shù)研究進(jìn)展[J]. 軟件學(xué)報(bào)，2006,17(9):1849-1853.

[2] 畢玉德. 面向語(yǔ)言信息處理的朝鮮語(yǔ)知識(shí)庫(kù)研究[J]. 中文信息學(xué)報(bào)，2005, 19(3):28-30.

[3] 王志玲, 王效岳. 國(guó)內(nèi)文本分類研究論文的統(tǒng)計(jì)分析[J]. 圖書情報(bào)工作，2006,50(11):136-138.

[4] 何國(guó)輝, 吳禮發(fā). 基于機(jī)器學(xué)習(xí)的文本分類技術(shù)的研究[J]. 計(jì)算機(jī)與現(xiàn)代化，2009,(8):3-6.

[5] 吳科. 基于機(jī)器學(xué)習(xí)的文本分類研究[D]. 上海交通大學(xué)博士論文. 2008:5-12.

[6] 梅君. 中文文本分類的研究與應(yīng)用[D]. 南昌大學(xué)碩士論文. 2010:31-38.

[7] P. Soucy, E. Mineau. Beyond TFIDF weighting for text categorization in the vector space model[C]//Proceedings of International Joint Conference on Artificial Intelligence. Edinburgh, Scotland, 2005: 1130-1135.

[8] H. J. Kim, J. Chang. Integrating incremental feature weighting into na’fve bayse text classifier[C]//Proceedings of the 6thInternational Conference on Machine Learning and Cybemetcs. Hong Kong, China, 2007: 1137-1143.

[9] 張璇, 左敏. 一種改進(jìn)的樸素貝葉斯分類器在文本分類中的應(yīng)用研究[J]. 北京工商大學(xué)學(xué)報(bào)，2009,27(4):52-55.

[10] 張?chǎng)? 張化祥. 屬性加權(quán)的樸素貝葉斯集成分類器[J]. 計(jì)算機(jī)工程與應(yīng)用，2010, 46(29):144-146.