基于遺傳算法及概率論的文本分類算法

宋倩王東明

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

基于遺傳算法及概率論的文本分類算法

宋倩1王東明2

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

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

遺傳算法；文本分類；特征項

1 引言

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

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

通過對文本分類的研究，可以加速檢索結(jié)果，使得用戶可以以最快的速度獲得對自己最有用的信息，從而滿足需求。文本分類的研究，將為信息查詢、加工、過濾提供堅實基礎(chǔ)。

2 文本預(yù)處理

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

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

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

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

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

3 特征項抽取

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

3.1 權(quán)值計算

3.1.1 tf算法

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

3.1.2 idf算法

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

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

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

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

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

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

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

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

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

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

圖1 文本特征項概率分布

4 基于并行遺傳算法的文本特征項提取

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

4.1 二進制編碼

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

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

4.2 遺傳算子

4.2.1 選擇算子

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

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

4.2.2 交叉算子

具體操作如下：

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

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

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

4.2.3 變異算子我們選擇簡單的變異算子來使用。具體操作過程如下：

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

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

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

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

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

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

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

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

2)用兩個染色體分別表示同一文本。此時要注意：對兩個染色體來說，如果某一個特征詞在該染色體中沒有被提取，則將該染色體表示的文本向量在對應(yīng)位上置0。舉例說明一下?，F(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個文本；wki指第i個文本的第k個特征詞的出現(xiàn)概率。通過這種計算，三代間最佳染色體基因序列一致，或者繁殖已達10代，則退出遺傳算法計算，得出結(jié)果。

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

5 對文本進行分類

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

6 結(jié)束語

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

表1 文本相似度

[1]戴文華．《基于遺傳算法的文本分類及聚類研究》[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é)士，研究方向：電磁通訊。

大夏基金項目，項目編號：2013DX-241。