基于模糊軟集合理論的文本分類方法

基于模糊軟集合理論的文本分類方法摘要：為提高文本分類精度，提出一種基于模糊軟集合理論的文本分類方法。該方法把文本訓練集表示成模糊軟集合表格形式，通過約簡、構造軟集合對照表方法找出待分類文本所屬類別，并針對文本特征提取過程中由于相近特征而導致分類精度下降問題給出一種基于正則化互信息特征選擇算法，有效地解決了上述問題。與傳統(tǒng)的KNN和SVM分類算法相比，模糊軟集合方法在文本分類的精度和準度上都有所提高。關鍵詞：文本分類；軟集合；模糊軟集合；特征選擇；互信息1概述軟集合理論是學者于1999年提出的一種新的處理不確定、模糊及未被清楚定義的對象的數(shù)學工具。目前被廣泛應用處理不確定性問題的數(shù)學理論和工具有：概率論，模糊集理論，區(qū)間數(shù)學，粗糙集等，但是所有這些理論和結果都有其不完善的方面，產(chǎn)生這些問題的主要原因在于參數(shù)化工具的不足。而軟集合理論就是處理不確定性且不存在上述問題的強有力數(shù)學工具。當前，有越來越多的學者投入到軟集理論及應用的研究，有文獻對軟集的基本理論進行了研究，并給出軟集在決策中的一些應用；Cheng和Tsang給出了基于軟集理論的屬性約簡方法并和粗糙集中的屬性約簡作了相應的比較；有文獻在考慮增加屬性及次優(yōu)選擇問題上給出了正則化屬性約簡原理并給出相應的約簡算法；Zhou和Xiao給出使用軟集來分析不完備信息系統(tǒng)的方法。文本自動分類是信息檢索與數(shù)據(jù)挖掘領域的研究熱點與核心技術，數(shù)量巨大的訓練樣本和過高的向量維數(shù)是文本分類的2大特點。這2個特點決定了文本分類問題是一個運算時間和空間復雜度很高的問題。目前產(chǎn)生一些可用的分類系統(tǒng)，并取得了一定的成果，但仍然存在很多尚未解決的問題，文本分類算法的研究不完整、文本的特征選擇和特征抽取方法有待進一步改進，基于此，本文首先在文本特征選擇階段提出一種新的基于正則化互信息的特征選擇算法，然后結合軟集合理論與文本分類的特點提出一種基于軟集合理論的文本分類新方法。為了敘述方便，給出軟集合相關理論：定義1設U是給定的論域，E是一個參數(shù)集，一個集合對(F,E)被稱為域U上的一個軟集合(softset)當且僅當F是E到所有的U子集中某集合的映射，如F:E→P(U)，其中，P(U)是U的冪集。軟集合是U的子集的一個參數(shù)族。該參數(shù)族中每個集合F(ε)(ε∈E)可以看成軟集合(F,E)的ε個元素的集合，或者是軟集合的ε個相似元素的集合。定義2若有一個二元運算符，記為*，(F,A)與(G,B)為論域U上的2個軟集，那么在軟集上的運算*可以定義為：(F,A)*(G,B)=(H,A×B)，其中，H(α,β)=F(α)*G(β),a∈A,b∈B,A×B是集合A與集合B的笛卡爾集。2軟集合相關理論定義3P(U)為U上所有模糊集，E為一參數(shù)集，Ai?E，集合(Fi,Ai)被稱為U上的一個模糊軟集當且僅當Fi是Ai到P(U)的一個映射，如:Fi:Ai→P(U)。定義4一個信息系統(tǒng)可以形式化為S=(U,A)，其中,U為對象的非空有限集合；A為屬性的非空有限集合，并且使得滿足對于任意的a∈A有:a:U→Va,V為屬性a的值域。定義5對模糊軟集(F,E),E={e1,e2,…,em}，若存在E的子集A={e`1,e`2,…,e`p}滿足，則A不是必要的,否則A是必要的。若B是必要的且,則B為E的一個正則化約簡，即E-B是滿足fE-B(.)為一常數(shù)的E的最大子集。文本分類中的訓練集的向量維數(shù)往往非常龐大，可以達到幾萬維，所以，要對維數(shù)進行壓縮是文本分類的主要任務之一，它一方面提高了程序的效率和運行速度，另一方面也是關鍵的方面，由于各個類別都普遍存在對分類沒有多大影響的詞，因此去掉那些詞不僅能壓縮維數(shù)，而且還能把對分類起代表性的詞體現(xiàn)出來，提高了分類精度。本文采用正則化互信息特征選擇方法(NMIFS)，并且提出一種貪心選擇算法對文本集進行特征選擇，該方法既考慮了特征與類別的互信息，也計算了特征與特征之間的互信息，解決了文本中相近的特征同時被選擇而導致的性能下降問題，并且能夠得到較優(yōu)的特征子集，具體算法如下：設給定輸入數(shù)據(jù)χ含N個樣本，每個樣本有M個屬性F={fi,i=1,2,…,M},目標類別變量為c,特征選擇問題就是要找出最能刻化c的一個含有m個特征{fi}的特征子集S,NMIFS第m個特征選擇公式如下：3基于NMIFS的特征選擇算法

算法1基于NMIFS特征選擇算法輸入N個樣本χ,目標類別c(每個樣本含M個屬性F={fi,i=1,2,…,M})

輸出特征子集SStep1初始化：給出特征集F={fi,i=1,2,…,M}，S={φ}為空集。Step2對每個特征fi∈F，計算I(fi,c)。Step3選出第1個特征,使得，。Step4進行貪心選擇：重復以下(1)、(2)直到|S|=k，其中，|S|為候選集合S的維度。(1)對所有的(fi,fs)計算I(fi,fs)，其中,fi∈F,fs∈S且(fi,fs)這一對互信息沒有被計算過；

(2)從F中選擇滿足式(1)的并設置，。

4.1文本的軟集合表示按照第3節(jié)方法對訓練集中文本進行特征選擇得到文本的特征屬性集，對所有訓練集中的文本提取得到文本的特征向量。在進行文本分類時，以文本的特征屬性作為參數(shù)集為訓練集中的樣本文本，按文獻[2]中類似的圖表方式，文本知識系統(tǒng)表示見表1(因為文本特征屬性有幾千維，樣本量很大，所以表中只給出部分樣本及部分屬性)。4基于軟集合的文本分類方法

4.2軟集合(F,E)對照表的構造一個含有n個對象的軟集合(F,E)其對照表由n行n列構成，其中，n為軟集合中對象個數(shù)，表中單元格記為Cij，其取值為:在軟集合(F,E)中對象Xi的取值大于等于Xj值所對應的參數(shù)個數(shù)。顯然有0≤Cij≤d且Cij=d,?i,j,d為參數(shù)集E中參數(shù)個數(shù)，因此,Cij為對象oi在Cij

個屬性上取值上大于等于oj

，表1所對應的對比表如表2所示:

,i=1,2,…,n(2)第j列總和記為tj

，其計算如式(3)所示：,j=1,2,…,n(3)給每個對象oi賦于一個重要性值Si

，其計算公式如下：Si=ri?ti

i=1,2,…,n(4)

4.3基于軟集理論的分類算法基于軟集合理論的文本分類算法首先要把文本特征向量表示為軟集合圖表，再根據(jù)最優(yōu)值不變原則進行約簡，最后選擇最佳分類，具體算法如下：算法2基于軟集合理論的分類算法輸入訓練樣本的特征向量與待選擇的文本特征向量輸出所屬類別(1)由訓練樣本的特征向量，構造軟集合圖表。(2)采用正則化參數(shù)約簡法[3]進行約簡。(3)計算每個文本類別的聚類中心特征向量。(4)重復步驟(3)直到求出所有類別的中心特征向量。(5)由步驟(4)中c個類別中心向量構造一個C×M軟集合圖表，其中，M為約簡后的文本的特征屬性個數(shù)；C為預先劃分好的文本類別數(shù)，每個單元格為Vij(i=1,2,…,n,j=1,2,…,m)，矩陣每一行Ci為一個文本類別的中心特征向量。(6)給定一個待分類的文本，計算出其特征向量Vf

。(7)由Vf與步驟(5)中所得的表格構成新的表格，新表單元格Vij計算公式如下:(8)根據(jù)步驟(7)得到的軟集合圖表求出其對照表。(9)由式(2)~式(4)求出步驟(8)中對照表的Si,i=1,2,…,C。(10)求出最優(yōu)Ci=maxiSi

，即待分類文本的所屬類別。5實驗結果分析為了驗證基于軟集合理論的文本分類方法的性能采用復旦大學國際數(shù)據(jù)庫中心李榮陸提供的中文文本分類語料庫作為訓練集和測試集，從中提取知識并對分類算法進行評價，1882篇文本作為訓練集，934篇文本作為測試集，其中的文本涉及10個主題：即交通、體育、軍事、醫(yī)藥、政治、教育、環(huán)境、經(jīng)濟、藝術、計算機。評價分類性能[7]的2種常用指標是準確率p和召回率r。為了評估算法在整個數(shù)據(jù)集上的性能，有2種平均的方法可供使用，分別稱為宏平均(macro_average)和微平均(micro_average)。宏平均是每一個類的性能指標的算術平均值，而微平均是每一個實例(文檔)的性能指標的算術平均。分別從以下2個方面來對基于軟集合理論的分類方法進行測試：(1)選不同數(shù)量的特征時分類器的性能；(2)與KNN和SVM分類器的性能比較。在實驗中選擇特征數(shù)從400~2800之間對KNN,SVM及基于軟集合方法進行