周國強,崔榮一

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

1 引言

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

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

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

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

2 特征向量

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

2.1 特征選擇

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

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

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

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

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

(1)

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

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

(2)

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

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

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

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

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

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

Step4： 最終得到一個去除掉少見詞和平凡詞的特征子集。

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

2.2 特征權(quán)重

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

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

(5)

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

(6)

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

(7)

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

3 樸素貝葉斯分類器

3.1 基本原理

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

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

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

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

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

(8)

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

(9)

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

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

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

圖1 文本分類流程

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

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

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

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

4 實驗結(jié)果及分析

本文的語料庫來自互聯(lián)網(wǎng)韓國各網(wǎng)站采集的450個大小的文檔集，其中包括9個類別，分別是財經(jīng)、IT、健康、體育、旅游、教育、招聘、文化、軍事，每個類別是由50個文檔構(gòu)成的文檔集。基于這些素材，本文在matlab中進行了實驗。

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

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

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

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

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

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

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

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

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

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

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

[5] 吳科. 基于機器學(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] 張璇, 左敏. 一種改進的樸素貝葉斯分類器在文本分類中的應(yīng)用研究[J]. 北京工商大學(xué)學(xué)報，2009,27(4):52-55.

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