基于遺傳算法及概率論的文本分類(lèi)算法

宋倩王東明

（1.華東師范大學(xué)，上海 200241；2.成都理工大學(xué)，四川 成都 610059）

基于遺傳算法及概率論的文本分類(lèi)算法

宋倩1王東明2

（1.華東師范大學(xué)，上海 200241；2.成都理工大學(xué)，四川 成都 610059）

本文意在提高文本分類(lèi)的準(zhǔn)確度和速度。利用tf算法對(duì)特征項(xiàng)進(jìn)行初步賦予權(quán)值，再使用屏蔽詞對(duì)特殊非實(shí)意詞進(jìn)行屏蔽。本文獨(dú)創(chuàng)概率論分布法，使用L-E算子進(jìn)行加權(quán)，使得特殊位置與分布廣泛的特征項(xiàng)，呈指數(shù)形式加權(quán)，較優(yōu)結(jié)果能更快收斂。本文利用遺傳算法，采用交叉算子和變異算子，采用適宜的目標(biāo)函數(shù)，加快了檢索速度，并有更大概率得到最優(yōu)結(jié)果。采用混合算法，可以排除同義詞和非特征項(xiàng)的干擾。

遺傳算法；文本分類(lèi)；特征項(xiàng)

1 引言

文本分類(lèi)就是在指定的分類(lèi)模型下，由計(jì)算機(jī)根據(jù)文本內(nèi)容，自動(dòng)判別文本類(lèi)別的過(guò)程。當(dāng)今社會(huì)是一個(gè)信息高速膨脹的社會(huì)，我們希望能在紛繁的信息中迅速找到對(duì)自己有用的信息，而不是對(duì)所查找的對(duì)象逐個(gè)瀏覽篩選。

對(duì)于文本分類(lèi)的研究大約經(jīng)歷了50多年，從1958年至今，經(jīng)歷了文本分類(lèi)的可行性研究階段、實(shí)驗(yàn)階段和實(shí)用化階段。國(guó)外的主要研究單位有斯坦福大學(xué)、麻省理工大學(xué)和CMU等，這些單位在理論研究上有很高的水平。國(guó)內(nèi)的研究機(jī)構(gòu)主要有復(fù)旦大學(xué)、東北工業(yè)大學(xué)、哈爾濱工業(yè)大學(xué)、中國(guó)科學(xué)院等。中文文本分類(lèi)還處于試驗(yàn)階段，正確率大約在60%至90%之間。采用聚類(lèi)粒度原理的VSM分類(lèi)方法的分類(lèi)器，正確率可達(dá)99.8%[1]。

通過(guò)對(duì)文本分類(lèi)的研究，可以加速檢索結(jié)果，使得用戶(hù)可以以最快的速度獲得對(duì)自己最有用的信息，從而滿(mǎn)足需求。文本分類(lèi)的研究，將為信息查詢(xún)、加工、過(guò)濾提供堅(jiān)實(shí)基礎(chǔ)。

2 文本預(yù)處理

對(duì)文本分類(lèi)首先要對(duì)文本進(jìn)行預(yù)處理。它對(duì)文本挖掘的效果影響至關(guān)重要。預(yù)處理的主要目的是抽取代表文本特征的中間表示形式。文本預(yù)處理通常包括如下幾個(gè)環(huán)節(jié)：去除標(biāo)記；進(jìn)行數(shù)字合并、詞根還原；進(jìn)行數(shù)據(jù)清洗以去除不合適的噪聲文檔或文檔中的垃圾數(shù)據(jù)。

首先，根據(jù)代碼所用測(cè)試文章，進(jìn)行粗掃描，去除網(wǎng)頁(yè)標(biāo)記、特殊符號(hào)、參考文獻(xiàn)及公式等信息。這些只是文章在完成自己所需要的必要陳述時(shí)，所做的帶有引用性質(zhì)步驟。我們完全有理由認(rèn)為，這些不能表示這篇文章，可以被剔除。

其次，將文本讀入。將標(biāo)題段單獨(dú)存儲(chǔ)為一段；按回車(chē)鍵區(qū)分段落，即遇到回車(chē)鍵則系統(tǒng)默認(rèn)文章進(jìn)入下一段；按空格號(hào)區(qū)分詞語(yǔ)，即遇到空格符則默認(rèn)此特征項(xiàng)已輸入完畢。

再次，將僅首字母大寫(xiě)的單詞小寫(xiě)后存儲(chǔ)；將至少有兩個(gè)字母大寫(xiě)的單詞保留大寫(xiě)格式保存，作為不同的特征詞。

最后，去除非句號(hào)標(biāo)點(diǎn)符號(hào)，例如逗號(hào)、引號(hào)、冒號(hào)等。對(duì)特殊位置進(jìn)行標(biāo)記，主要指標(biāo)題、段首、段尾等。這樣標(biāo)記有利于下一步特征項(xiàng)詞頻統(tǒng)計(jì)。

3 特征項(xiàng)抽取

我們以特征項(xiàng)作為文本表示的基本單位。特征項(xiàng)，即關(guān)鍵詞，是指一篇文本中相對(duì)重要而能表現(xiàn)文本特征的詞語(yǔ)。我們用權(quán)值來(lái)衡量不同的特征項(xiàng)在文本中的重要程度。權(quán)值越大，對(duì)應(yīng)于該特征項(xiàng)對(duì)于該文本越重要。權(quán)值體現(xiàn)了該特征項(xiàng)對(duì)于文本內(nèi)容的反映能力。由于不同的詞匯在文本中出現(xiàn)的頻率與統(tǒng)計(jì)特性會(huì)不一樣，我們可據(jù)此抽取關(guān)鍵詞并衡量其權(quán)值。

3.1 權(quán)值計(jì)算

3.1.1 tf算法

tf即特征項(xiàng)頻率，是指某個(gè)特征項(xiàng)在文本中出現(xiàn)的次數(shù)。出現(xiàn)次數(shù)越多，則賦予更大的權(quán)值；不常出現(xiàn)的詞語(yǔ)，則被賦予較低的權(quán)值。這種方法簡(jiǎn)單、效率高，在文本篇幅很長(zhǎng)的情況下普遍適用，是最初文本分類(lèi)常用的方法。但其與信息論中“出現(xiàn)頻率越低的信息，其信息量越大”的思想有所出入。事實(shí)上，在某些情況下，頻率低的詞語(yǔ)常常含有對(duì)文本非常重要的信息。因此這種方法不夠完善。

3.1.2 idf算法

idf即倒排序算法。僅僅使用tf算法會(huì)出現(xiàn)一個(gè)問(wèn)題，文檔中出現(xiàn)的大量禁用詞會(huì)干擾特征項(xiàng)抽取。例如英文文本里的“is”、“are”等。

倒排序算法著眼于文檔集合，計(jì)算含有相同特征項(xiàng)的文本數(shù)量。其數(shù)量越多，則該特征項(xiàng)對(duì)于辨別相似文本的作用越低。若某一特征項(xiàng)在所有的文本中含有，則此特征項(xiàng)的權(quán)值將置0。

倒排序的核心是，認(rèn)為在少數(shù)文本中出現(xiàn)的關(guān)鍵詞比在大量文本中出現(xiàn)的關(guān)鍵詞重要。倒排序算法能夠有效減少禁用詞的影響，以便抽取到更準(zhǔn)確的特征項(xiàng)。

3.1.3 詞頻統(tǒng)計(jì)與L-E線性指數(shù)加權(quán)因子

首先，我們對(duì)于文章按段為單位，對(duì)每一個(gè)特征項(xiàng)在每段（包括）標(biāo)題出現(xiàn)的次數(shù)做統(tǒng)計(jì)。期間，標(biāo)記標(biāo)題出現(xiàn)的詞語(yǔ)，以及段首段尾出現(xiàn)過(guò)的詞語(yǔ)，以及在標(biāo)題出現(xiàn)的次數(shù)和在段首段尾出現(xiàn)的次數(shù)。

其次，對(duì)于均勻分布的特征項(xiàng)進(jìn)行權(quán)值加權(quán)。但均勻分布的標(biāo)準(zhǔn)是什么呢？每段出現(xiàn)特征項(xiàng)次數(shù)差不多，是均勻分布嗎？顯然不是，因?yàn)橐话闱闆r下，文章的段落有長(zhǎng)有短，而特征項(xiàng)出現(xiàn)的次數(shù)將受限于段落的長(zhǎng)度。特征項(xiàng)在每段（不包括標(biāo)題段）出現(xiàn)頻率比較相似，波動(dòng)不大，比較符合均勻分布的概念。

使用方差去評(píng)價(jià)似乎很合理。但使用方差有一個(gè)問(wèn)題。對(duì)于某些特殊文章，第一二段可能只是作為文章的引入，這時(shí)出現(xiàn)特征項(xiàng)的概率非常小。而使用方差計(jì)算，這時(shí)一個(gè)低概率的項(xiàng)會(huì)對(duì)整體計(jì)算產(chǎn)生巨大影響。在此，我們提出了L-E線性指數(shù)加權(quán)因子。

其中，T為該特征項(xiàng)在整個(gè)文章中的加權(quán)總次數(shù)；T1為該特征項(xiàng)在整篇文章出現(xiàn)過(guò)的次數(shù)；T2為該特征項(xiàng)在標(biāo)題中出現(xiàn)的次數(shù)；T3為該特征項(xiàng)在文章段首段尾處出現(xiàn)過(guò)的總次數(shù)；T4為該特征項(xiàng)在整個(gè)文章中的T4段都出現(xiàn)過(guò)。

n1為一個(gè)由文章篇幅決定的常數(shù)，文章越短，值越大，本文取1；n2為一個(gè)由標(biāo)題相對(duì)文章長(zhǎng)度比值決定的常數(shù)，比值越小取值越大，本文取10；n3的取值由文章段落字?jǐn)?shù)大小決定，文本取5；n4的取值影響分布廣泛的特征項(xiàng)的收斂速度，本文取2。通過(guò)這種方法，可以既排除了部分特殊情況對(duì)方差影響較大的情況，又使得收斂加快。例如，僅在文章一段中出現(xiàn)的詞語(yǔ)，最末項(xiàng)加權(quán)后僅為1；而出現(xiàn)在5段中的特征項(xiàng)最末一項(xiàng)加權(quán)為25，大大加快了分布廣泛的特征項(xiàng)的收斂速度。

特征選擇一般是通過(guò)設(shè)置閾值來(lái)控制的。當(dāng)某一特征項(xiàng)的權(quán)值大于閾值時(shí)，我們將該特征項(xiàng)作為參考特征項(xiàng)；如果特征項(xiàng)的權(quán)值低于閾值，則忽略該特征項(xiàng)的作用。我們特征項(xiàng)選擇，利用屏蔽詞來(lái)進(jìn)行。我們利用屏蔽詞容器，可以屏蔽掉大部分非實(shí)意詞。當(dāng)然，我們的屏蔽詞容器以寧缺毋濫為原則，不包含絕大多數(shù)的名詞和動(dòng)詞，主要為介詞、情態(tài)動(dòng)詞等非實(shí)意詞，最后的特征項(xiàng)的概率分布如圖1。

圖1 文本特征項(xiàng)概率分布

4 基于并行遺傳算法的文本特征項(xiàng)提取

遺傳算法是對(duì)達(dá)爾文生物進(jìn)化理論的簡(jiǎn)單模擬，其遵循“適者生存”、“優(yōu)勝劣汰”的原理。遺傳算法模擬一個(gè)人工種群的進(jìn)化過(guò)程，并且通過(guò)選擇、雜交以及變異等機(jī)制，經(jīng)過(guò)若干代以后，總是達(dá)到最優(yōu)（或近最優(yōu)）的狀態(tài)。其主要步驟如下：

4.1 二進(jìn)制編碼

染色體中的每一位對(duì)應(yīng)原始特征詞集合中的一個(gè)特征詞，當(dāng)該特征詞被提取時(shí)對(duì)應(yīng)染色體位置為1，不被提取時(shí)置0。這種方法即使在特征詞集合很大時(shí)，占用的空間也很小。例如，有一個(gè)數(shù)量為8的特征項(xiàng)群。選取第2、4、5、7、8個(gè)特征項(xiàng)，則其編碼為：01011011。

我們?cè)O(shè)置最初始的染色體個(gè)數(shù)為2，其基因序列值是隨機(jī)產(chǎn)生的，通過(guò)之后的一代代繁殖產(chǎn)生新個(gè)體，滿(mǎn)足遺傳規(guī)律。

4.2 遺傳算子

4.2.1 選擇算子

選擇算子用于對(duì)目前這一代的種群，進(jìn)行配對(duì)，以繁殖產(chǎn)生下一代的操作。遵循客觀生物遺傳規(guī)律，選擇算子應(yīng)符合隨機(jī)原則。具體操作如下：

確定某一代種群，隨機(jī)產(chǎn)生兩個(gè)隨機(jī)數(shù)（數(shù)字應(yīng)小于該代種群數(shù)量），則編號(hào)為相應(yīng)數(shù)字的兩個(gè)染色體被配對(duì)。準(zhǔn)備進(jìn)入交叉操作。對(duì)各代分別進(jìn)行以上操作，即不允許出現(xiàn)不同代個(gè)體之間進(jìn)行配對(duì)的情況。

4.2.2 交叉算子

具體操作如下：

1）隨機(jī)產(chǎn)生一個(gè)[0，1]之間的數(shù)r，如果r＜=Pc(Pc為交叉概率，本項(xiàng)目取0.6)，則轉(zhuǎn)（2），否則直接退出交叉。

2）隨機(jī)產(chǎn)生一個(gè)[1,8]之間的自然數(shù)，作為交叉位。將兩父?jìng)€(gè)體從交叉點(diǎn)處進(jìn)行基因交叉互換，形成子代個(gè)體。

例如，兩個(gè)序列分別為1011101和1100001的染色體，隨機(jī)產(chǎn)生交叉概率大于0.6時(shí)，則對(duì)這兩個(gè)個(gè)體進(jìn)行交叉。當(dāng)符合交叉條件時(shí)，產(chǎn)生一個(gè)隨機(jī)數(shù)確定交叉位置。例如這個(gè)數(shù)是2，則交叉后的產(chǎn)生的新的染色體為1000001以及1111101。

4.2.3 變異算子我們選擇簡(jiǎn)單的變異算子來(lái)使用。具體操作過(guò)程如下：

1)隨機(jī)產(chǎn)生一個(gè)[1，8]之間的自然數(shù)C，作為變異點(diǎn)個(gè)數(shù)。

2)隨機(jī)產(chǎn)生一個(gè)與上一輪不重復(fù)的[1,8]之間的自然數(shù)，作為變異點(diǎn)。

3)隨機(jī)產(chǎn)生一個(gè)[0，1]之間的數(shù)r，如果r＜=Pm（Pm為變異概率，本項(xiàng)目取0.6），則轉(zhuǎn)（4），否則直接轉(zhuǎn)（5）。

4)將父體在變異點(diǎn)出進(jìn)行基因變異（即0變?yōu)?，1則變?yōu)?）。c=c+1。

5)如果c＞C，退出變異，否則轉(zhuǎn)（3）。

4.3 適應(yīng)度函數(shù)

我們用歐氏距離來(lái)衡量文本的相似度。關(guān)鍵問(wèn)題是如何計(jì)算不同特征項(xiàng)所組成的染色體表示的一個(gè)文本的相似度。為解決歐氏距離計(jì)算問(wèn)題，我們采取下面的辦法：

1)將兩個(gè)染色體提取的特征詞進(jìn)行擴(kuò)充，取兩者的交集，使得兩者表示的文本向量維數(shù)變?yōu)橐恢隆?/p>

2)用兩個(gè)染色體分別表示同一文本。此時(shí)要注意：對(duì)兩個(gè)染色體來(lái)說(shuō)，如果某一個(gè)特征詞在該染色體中沒(méi)有被提取，則將該染色體表示的文本向量在對(duì)應(yīng)位上置0。舉例說(shuō)明一下。現(xiàn)在有兩條染色體，分別為GA1=101111000，GA2=001111001，原始文本向量為{0.09,0.08,0.04,0.22,0.08, 0.24,0.14,0.03,0.08}，則GA1的文本向量為{0.09,0.04,0.22, 0.08,0.24,0}，GA2的文本向量為{0,0.04,0.22,0.08,0.24,0.08}，最后，利用公式即可得到歐氏距離。

其中di是指第i個(gè)文本；wki指第i個(gè)文本的第k個(gè)特征詞的出現(xiàn)概率。通過(guò)這種計(jì)算，三代間最佳染色體基因序列一致，或者繁殖已達(dá)10代，則退出遺傳算法計(jì)算，得出結(jié)果。

需要說(shuō)明的是，我們?yōu)榉乐谷旧w畸變，設(shè)置了染色體性狀顯隱形閾值。也即，染色體里顯性性狀與隱性性狀都不得低于35%。顯性性狀，是指染色體基因序列上取1的性狀；隱性性狀，是指染色體基因序列上取0的性狀。這樣可防止染色體收斂于全0或全1。

5 對(duì)文本進(jìn)行分類(lèi)

排除文本同義詞的影響，將最終選擇的特征項(xiàng)賦給文本對(duì)象。輸出數(shù)據(jù)包括文章各段落的讀入內(nèi)容，以及該段的主要詞匯；每個(gè)關(guān)鍵詞，它是否在標(biāo)題出現(xiàn)，是否在段首段尾出現(xiàn)，以及出現(xiàn)的次數(shù)；分布的段落以及在文章中出現(xiàn)的次數(shù)；該特征詞加權(quán)后的出現(xiàn)概率；參考文檔的特征向量；得到的染色體通過(guò)遺傳交叉變異處理，進(jìn)行分類(lèi)判斷。

6 結(jié)束語(yǔ)

本文利用遺傳算法及概率分布，提取文本特征項(xiàng)并對(duì)其進(jìn)行抽取以得到對(duì)文本進(jìn)行分類(lèi)的目的。在信息檢索這個(gè)領(lǐng)域已有理論成果的基礎(chǔ)上，我們加入了概率論的知識(shí)提取關(guān)鍵詞。若關(guān)鍵詞在文本中分布較為均勻，則加大其權(quán)值。通過(guò)測(cè)試，我們發(fā)現(xiàn)這種算法可以提高文本分類(lèi)的速度與準(zhǔn)確度，最后的利用染色體序列計(jì)算歐式距離來(lái)判斷文本相似度，結(jié)果如表1。

表1 文本相似度

[1]戴文華．《基于遺傳算法的文本分類(lèi)及聚類(lèi)研究》[M]．北京：科學(xué)出版社，2008，14-67．

[2]Salton G，Buckley B．Term-Weighting approaches in automatic text retrieval[J]．Information Processing and Management，1988，24(5)：513-523．

[3]Fodor I K．A survey of dimension reduction techniques[R]．Technical report UCRL-ID-148494，LLNL，2002．

[4]Lewis D D．Features selection and feature extraction for text categorization[J]．Pattern Anal Applic，2003，6：301-308．

Text ClassificationAlgorithm Based on GeneticAlgorithm and Probability Theory

Song Qian1Wang Dongming2
(1.East China Normal University,Shanghai 200241; 2.Chengdu University of Technology,Chengdu 610059,Sichuan)

act】This article aims to improve the accuracy and speed of text classification.T*f algorithm is used to initially weigh the feature item,then stop words is used to shield specially meaningless words.Original probability distribution method and weighted L-E operator enable the features in the special positions or widely distributed to weight in exponential form,so that the better results converge faster.In this paper,by using the genetic algorithm,crossover operator and mutation operator,and adopting appropriate objective function,the retrieval process speeds up,and has a greater probability to get the optimal result.Hybrid algorithm is proposed,which can eliminate the synonyms and the characteristics of interference.

genetic algorithm;text classification;term

TP301.6

A

：1008-6609(2015)03-0049-04

宋倩，女，四川南充人，學(xué)士，研究方向：電磁通訊。

大夏基金項(xiàng)目，項(xiàng)目編號(hào)：2013DX-241。