王 進，金理雄，孫開偉

(1.重慶郵電大學計算機科學與技術(shù)學院，重慶400065;2.計算智能重慶市重點實驗室，重慶400065)

隨著Internet應用的普及，互聯(lián)網(wǎng)上電子文檔的數(shù)量正在高速增長.為從海量電子文檔中快速、準確、全面地查找和獲取有效信息，近年來，文本分類技術(shù)得到了學術(shù)界的廣泛關注.國外對英文文本分類技術(shù)的研究始于1950年，經(jīng)過數(shù)十年的發(fā)展已經(jīng)比較成熟.當前比較流行的英文文本分類方法包括:樸素貝葉斯(Na?ve Bayes)［1］，K 最近鄰(k-nearest neighbor，KNN)［2］，支持向量機(support vector machine，SVM)［3］，最大熵模型［4］等方法.而國內(nèi)對中文文本分類的研究起步較晚，始于20世紀80年代初期，近年來也取得了顯著進展［5-7］.

受生物分子網(wǎng)絡的啟發(fā)，演化超網(wǎng)絡(evolutionary hypernetworks)最初是作為一種并行聯(lián)想記憶模型被提出［8］，并通過 DNA 計算實現(xiàn)［9］.超網(wǎng)絡由大量的超邊(hyperedges)組成，具有流體性、可重置的分子結(jié)構(gòu)，是學習友好的［10］.超網(wǎng)絡的結(jié)構(gòu)(超邊的組成)和參數(shù)(超邊的權(quán)值)通過分子演化學習得到.近年來，Zhang B.T.［10］從超圖的視角定義了超網(wǎng)絡這一新穎的認知學習和記憶模型，并已將其成功應用于手寫數(shù)字圖像重建［9］、癌癥基因挖掘［11］、證券價格預測［12］、心血管疾病診斷［13］等諸多領域.

為了建立一個高效、準確的中文文本分類系統(tǒng)，文中擬提出一種基于演化超網(wǎng)絡的中文文本分類算法.對所獲的中文語料進行文本預處理、特征選擇和權(quán)值計算，建立演化超網(wǎng)絡模式識別模型;給出超網(wǎng)絡的演化算法，實現(xiàn)模型的識別功能;并通過與SVM，KNN兩種傳統(tǒng)的文本分類方法的對比試驗，驗證演化超網(wǎng)絡擁有較好的分類性能.

1 中文文本分類的前期處理

中文文本分類的前期數(shù)據(jù)處理流程包括:文本預處理、特征選擇、權(quán)重計算.

1.1 文本預處理

文本預處理主要包括分詞處理、去停用詞兩個步驟.為將文本進行形式化表示，把中文文本表示成基于詞條的N維向量.中文是連續(xù)的字符串，為了抽取文本中的詞條，需對中文文本進行分詞處理.而去停用詞主要是去除那些對文本內(nèi)容沒有意義的詞.文中采用中國科學院計算技術(shù)研究所的漢語詞法分析系統(tǒng)(Institute of Computing Technology，Chinese Lexical Analysis System，ICTCLAS)進行分詞和詞性標記.通過詞性標記，文中可以去除無實際意義的詞條(助詞、數(shù)詞、語氣詞等)，從而保留了最能體現(xiàn)文本主題的詞條(名詞、動詞、形容詞).

1.2 特征選擇

文中采用χ2統(tǒng)計方法進行文本特征選擇以降低文本信息特征向量空間維度，提高分類效率.χ2統(tǒng)計方法是通過計算詞條t和文檔類別c的相關程度來實現(xiàn):

式中:N為訓練文本總數(shù);A為t，c同時出現(xiàn)的次數(shù);B為t出現(xiàn)而c未出現(xiàn)的次數(shù);C為c出現(xiàn)而t未出現(xiàn)的次數(shù);D為二者都未出現(xiàn)的次數(shù).χ2統(tǒng)計值越大，則詞條t對文檔類別c的相關度越高.對多類文本分類問題，χ2統(tǒng)計方法有最大值法和平均值法兩種方法來確定詞條t對整個語料的χ2值.文中采用最大值方法:

式中:m為文檔類別數(shù).文中根據(jù)χ2值從大到小選出前n個詞條作為特征向量.

1.3 權(quán)重計算

由于不同的特征項對于中文文本的重要程度和區(qū)分度不同，因此在對文本進行向量空間模型處理的時候，需對特征向量進行賦權(quán)值.文中采用布爾權(quán)重計算特征向量的權(quán)值:如果特征詞條在文本中出現(xiàn)則權(quán)重為1，如果特征詞條沒出現(xiàn)則權(quán)重為0.

2 超網(wǎng)絡中文文本分類

演化超網(wǎng)絡模型在模式識別方面已經(jīng)有了成功的應用，文中把超網(wǎng)絡用于中文文本分類.超網(wǎng)絡文本分類包括兩個步驟:① 超網(wǎng)絡演化學習;②超網(wǎng)絡分類.超網(wǎng)絡學習過程中，采用超邊替代的策略，進行超網(wǎng)絡的更新.學習后的超網(wǎng)絡通過逐一給出輸入樣本屬于每個類別的條件概率進行分類.

2.1 超圖的定義

超圖是每條邊連接非零個頂點的無向圖.在一般意義上的圖論模型中，圖的每條邊最多連接兩個頂點.但是，超圖的邊所連接頂點個數(shù)可以大于2.

設G={X，E}是一個超圖，其中X={x1，x2，…，xn}是超圖G的頂點集合，表示該超圖有n個頂點;E={e1，e2，…，en}是超邊的集合，E中的每個元素ei={xi1，xi2，…xic}是一個連接c個頂點的超邊.圖1給出了一個包含6個頂點4條超邊的超圖.

圖1 超圖模型

2.2 超網(wǎng)絡模式識別模型

超網(wǎng)絡是一個每條超邊都被賦予了權(quán)值的超圖.超網(wǎng)絡可被定義為一個3元組H={X，E，W}，其中X，E，W分別表示超網(wǎng)絡的頂點集合、超邊集合以及超邊權(quán)值的集合.超網(wǎng)絡中一條超邊所連接的頂點數(shù)被稱作該超邊的階數(shù)(order)，其取值可以大于2，因此超邊能夠表示頂點的高階關聯(lián)［10］.如果一個超網(wǎng)絡的所有超邊階數(shù)均為k，則這個超網(wǎng)絡被稱為k階超網(wǎng)絡.圖2為超網(wǎng)絡模型圖.

圖2 超網(wǎng)絡模型

圖2所示的超網(wǎng)絡H={X，E，W}，頂點集合X={x1，x2，x3，x4，x5，x6}，超邊集合E={e1={x1，x2，x3}，e2={x2，x3，x4}，e3={x1，x5，x6}}，超邊權(quán)值集合W={w1=1，w2=2，w3=4}.說明此超網(wǎng)絡擁有6個頂點3類超邊.超網(wǎng)絡超邊線條的粗細代表了超邊的權(quán)值大小:線條越粗，其權(quán)值越大.文中超邊的權(quán)值就是邊的拷貝(copies)的數(shù)目.例如，超邊e3的權(quán)值w3為4，則超網(wǎng)絡中共有4條和e3完全相同的超邊，即超邊e3有4個拷貝.

在演化超網(wǎng)絡文本分類應用中，每個特征選擇后的詞條被看作超網(wǎng)絡中的一個頂點.文中可以把超網(wǎng)絡看作一個決策分類系統(tǒng)f，給定一個輸入模式X={x1，x2，…，xn}，它能輸出該模式所對應的類別.決策分類系統(tǒng)f通過使用輸入輸出對組成的訓練集D進行演化學習生成，訓練集D具有以下形式:

式中:N表示訓練集中樣本的數(shù)量;k為每個樣本的維數(shù);yi為樣本xi的類別標識.

超網(wǎng)絡中，每條超邊構(gòu)成一個決策分類規(guī)則，超邊所關聯(lián)的頂點稱作決策屬性.例如，超邊Z={x1=0，x2=0，x3=1，y=1}的階數(shù)為 3，類別為1.超網(wǎng)絡允許超邊的復制，超邊權(quán)值的大小決定了該超邊對分類的重要性.

實際上，超網(wǎng)絡代表了輸入模式X和它可能的類別Y的聯(lián)合概率P(X，Y)，其中Y∈{1，2，…，m}.聯(lián)合概率P(X，Y)可以解釋為模式X被檢索為類別Y的概率.給定一個樣本，超網(wǎng)絡將所有的超邊與樣本進行匹配，并把匹配成功次數(shù)最多的類別作為分類輸出.用超網(wǎng)絡進行文本分類，可以理解為:求輸入文本屬于每個類別的條件概率，并取擁有最大條件概率的類別作為分類結(jié)果:

經(jīng)驗概率P(X，Y)可以根據(jù)超網(wǎng)絡的超邊進行點估計得到:

式中:|L|表示超邊總數(shù)(x1，x2，…，xk，Y)為第i條超邊;k為超邊的階數(shù).如果該超邊與輸入模式X相匹配，則(x1，x2，…，xk，Y)=1，否則(x1，

x2，…，xk，Y)=0.例如，輸入模式X=(x1=1，x2=0，

x3=1)，某一超邊(x1，x2，…，xk，Y)，當且僅當超邊中頂點x1，x2，x3的取值分別為 1，0，1 時，兩者匹配.超網(wǎng)絡文本分類過程的具體描述如下:

1)根據(jù)超網(wǎng)絡的超邊集合L進行點估計，得到經(jīng)驗概率分布P(X，Y).

2)輸入一個文本Xi.

3)分類文本Xi.

①從L中提取所有與Xi匹配的超邊，并加入到集合M中表示所有與X匹配的超i邊所占比例，也即是樣本Xi被記憶并存儲的概率.

②根據(jù)類別，將M中的超邊分類:將類別為Y的超邊歸類到)表示樣本Xi屬于Y類的概率.

③計算y*=

2.3 超網(wǎng)絡演化學習

超網(wǎng)絡的演化學習是一個不斷地對超邊進行匹配、選擇和放大的過程.由于文中將超邊的權(quán)值設為其拷貝的數(shù)量，因此，給定一個訓練集，就可以創(chuàng)建一個由帶權(quán)值的超邊組成的初始化超網(wǎng)絡.這些初始的超邊經(jīng)過不斷地匹配、替代和放大等演化學習操作，最終形成一種能夠準確地擬合訓練集數(shù)據(jù)的概率分布.超網(wǎng)絡可以通過演化學習找到一個合適的概率分布，以準確地擬合訓練集數(shù)據(jù).超網(wǎng)絡演化學習的具體步驟如下:

1)初始化.

初始化超邊集合為空集L，設置每次迭代被替代超邊的最大值為m(m=20 000).對于訓練集中的每個樣本，隨機生成10條階數(shù)為k的超邊，初始化超邊的適應值為fw=0，fc=0(fw表示超邊不能正確分類訓練樣本時的適應值，fc表示超邊正確分類訓練樣本時的適應值)，并加入到集合L中.

2)分類.

用步驟1)初始化得到的超網(wǎng)絡對訓練樣本分類，然后將分類正確的樣本加入到集合XC中，分類不正確的樣本加入到集合XW中.

3)計算超邊適應值.

對于每條超邊li，計算它對于XW中的樣本xi的適應值.如果該邊可以正確分類xi則將適應值設為fw(li)=fw(li)+|Y|-1，否則將適應值設置為fw(li)=fw(li)-1;同樣，也計算超邊li對于XC中的樣本xi的適應值，如果該邊可以正確分類樣本xi則將適應值設置為fc(li)=fc(li)+|Y|-1，否則將其適應值設置為fc(li)=fc(li)-1.在這里，正確分類時對適應值加|Y|-1，其中|Y|為類別總數(shù).因為隨著類別的增加，正確分類樣本的超邊比例會下降，從而避免很少分類正確的超邊獲得更高的適應值.

4)排序.

對于所有的超邊，先按照fw降序排序，對于有相同fw的超邊，按照fc降序排序.

5)計算被替代的超邊數(shù)目.

s=wr|L|，其中超邊替代控制參數(shù)w(通過系統(tǒng)試驗，文中取w=0.8)用于控制被替代的超邊數(shù)目，r為步驟 2)中分類不正確的樣本比例表示訓練集樣本數(shù)量 )表示超邊的總數(shù).如果s大于m，則s=m，且m=0.8s.

6)替代.

根據(jù)排序的結(jié)果，選取最后s個超邊，用與之關聯(lián)的模式重新產(chǎn)生超邊并代替原超邊.

7)返回步驟2)，直到s=0.

從上述超網(wǎng)絡的演化學習過程可以看出超網(wǎng)絡的最大超邊數(shù)是2k×C(n，k)，其中n是輸入空間維數(shù)，k為超邊階數(shù).

3 試驗

為了驗證演化超網(wǎng)絡中文文本分類方法的有效性，文中選用兩個目前國內(nèi)公開的中文語料庫.

3.1 試驗數(shù)據(jù)集

試驗數(shù)據(jù)集1來自復旦大學計算機信息與技術(shù)系國際數(shù)據(jù)庫中心自然語言處理小組搜集的文本分類語料庫(http:∥www.nlp.org.cn/categories/default.php?cat-id=16).該語料庫包含20個類別，其中訓練語料和測試語料的文檔數(shù)分別為9 804篇和9 833篇.由于每個類別的文檔數(shù)分布不均勻，其中少的類別才十幾個文檔而多的可達幾千個，因此文中選取復旦語料庫中文檔數(shù)最多的9個類別進行試驗.從這9個類別的訓練集中，每類隨機選取450個文檔，構(gòu)成包含4 050個文檔的訓練集;同時也從這9個類別的測試集中，每類隨機選取450個文檔，構(gòu)成包含4 050個文檔的測試集.

試驗數(shù)據(jù)集2來自搜狐新聞網(wǎng)站保存和整理的新聞語料(http:∥www.sogou.com/labs/dl/c.html).文中使用其中的精簡版.此版本包含9個類別，每個類別的文檔數(shù)都為1 990個.文中把每類中前450個文檔作為訓練集，再從剩余文檔中選取前450個文檔作為測試集.因此文中的訓練集和測試集文檔數(shù)都為4 050個.

3.2 分類性能評價

文本分類器的性能通常采用3個指標進行評估:準確率(precision，P)、召回率(recall，R)和F1值，且有:

式中:a為正確判為該類的文本數(shù)目;b為錯誤判為該類的文本數(shù)目;c為原本屬于該類但是錯判的文本數(shù)目.以上評價指標只能針對某一類，為了表示分類器在全部類別上的綜合分類性能，通常有宏平均和微平均兩種方法.文中使用宏平均進行試驗數(shù)據(jù)評價，即在類別之間求取平均值.

3.3 試驗結(jié)果

演化超網(wǎng)絡模型中，超邊的階數(shù)設定對分類器的性能有很大影響.為在特定數(shù)據(jù)集上選取合適的超邊階數(shù)，文中分別在數(shù)據(jù)集1下設置了6組不同的超邊階數(shù)(分別為 15，20，25，30，35，40)，在數(shù)據(jù)集2下也設置6組不同的超邊階數(shù)(分別為25，30，35，40，45，50).

圖3，4分別給出了在數(shù)據(jù)集1和數(shù)據(jù)集2中，不同超邊階數(shù)設定下的試驗結(jié)果.兩圖中的宏準確率、宏召回率、宏F1值均為超網(wǎng)絡在不同設定下獨立進行20次演化學習的平均測試結(jié)果.

由圖3可見，當超邊階數(shù)值設置在30左右時，超網(wǎng)絡文本分類器的宏準確率、宏回率和宏F1值都是最高的.而當超邊階數(shù)小于20或者大于35時，分類性能急劇下滑.圖4中，當宏準確率，宏召回率和宏F1值都為最高值時，超邊階數(shù)設置是在35左右，小于30或者大于45時，超網(wǎng)絡文本分類器的宏準確率、宏回率和宏F1值都有所下滑.上述情況是因為，階數(shù)較小的超邊表示信息的一般性能力較強，而階數(shù)較大的超邊表示信息的特殊性能力較強.當超邊階數(shù)過大或者過小時，都無法兼顧到信息的局部性和全局性.依據(jù)試驗結(jié)果，在數(shù)據(jù)集1和數(shù)據(jù)集2上，階數(shù)分別設為30和35時，演化超網(wǎng)絡分類器能較好地兼顧到信息的局部性和全局性，具有較強的泛化能力.

為了說明演化超網(wǎng)絡模型在中文文本分類應用中的有效性，文中選擇了兩種傳統(tǒng)的文本分類方法:KNN和SVM進行對比.

數(shù)據(jù)集1的對比試驗:對演化超網(wǎng)絡(用χ2統(tǒng)計選取400維特征，進行布爾權(quán)值計算，階數(shù)定為30)，KNN［7］和 SVM［7］進行分類試驗.試驗結(jié)果如表1所示.在宏準確率、宏召回率和宏F1值方面，演化超網(wǎng)絡文本分類器分別為87.2%、86.9%和87.0%，都稍優(yōu)于其他兩種傳統(tǒng)中文文本分類器.

表1 數(shù)據(jù)集1的試驗結(jié)果對比 %

數(shù)據(jù)集2的對比試驗:演化超網(wǎng)絡，KNN和SVM分類時都采用χ2統(tǒng)計做特征選擇，特征數(shù)均為800維.演化超網(wǎng)絡使用布爾權(quán)值計算方法，KNN和SVM采用tf-idf計算權(quán)值.演化超網(wǎng)絡階數(shù)設定為35，KNN的K值設為28，SVM采用多項式核K(xi，yi)=(xi·yi+1)d，參數(shù)d=1.試驗結(jié)果如表2所示.雖然演化超網(wǎng)絡在宏準確率方面比SVM低，但是在宏召回率和綜合指標F1值方面都高于SVM和KNN.

表2 數(shù)據(jù)集2的試驗結(jié)果對比 %

4 結(jié)論

文中提出了一種基于演化超網(wǎng)絡的中文文本分類方法，結(jié)論如下:

1)演化超網(wǎng)絡文本分類器在復旦大學語料庫和搜狐語料庫上均取得了較好的效果，并稍優(yōu)于傳統(tǒng)的KNN和SVM分類器.

2)為了進一步提高文本分類器的性能和學習速度，演化超網(wǎng)絡學習算法和文本特征提取方法的改進，是今后的工作重點.

References)

［1］ Kulesza T，Stumpf S，Wong W K，et al.Why-oriented end-user debugging of naive bayes text classification［J］.ACM Transactions on Interactive Intelligent Systems，2011，1(1)，doi:10.1145/2030365.2030367.

［2］ Hao Xiulan，Tao Xiaopeng，Zhang Chenghong，et al.An effective method to improve KNN text classifier［C］∥Proceedings of the8th ACIS International Conference on Software Engineering，Artificial Intelligence，NetworkingandParallel/DistributedComputing. Quebec:IEEE Computer Society，2007:379-384.

［3］ Wang T Y，Chiang H M.One-against-one fuzzy support vector machine classifier:an approach to text categorization［J］.Expert Systems with Applications，2009，36(6):10030-10034.

［4］ Mann G，McDonald R，Mohri M.Efficient large-scale distributed training of conditional maximum entropy models［C］∥Proceedings of Advances in Neural Information Processing Systems22.Vancouver:Curran Associates，Inc.2009:1231-1239.

［5］ 李 文，苗奪謙，衛(wèi)志華，等.基于阻塞先驗知識的文本層次分類模型［J］.模式識別與人工智能，2010，23(4):456-463.LiWen，Miao Duoqian，Wei Zhihua，et al.Hierarchical text classification model based on blocking priori knowledge［J］.Pattern Recognition and Artificial Intelligence，2010，23(4):456-463.(in Chinese)

［6］ 王素格，李德玉，魏英杰.基于賦權(quán)粗糙隸屬度的文本情感分類方法［J］.計算機研究與發(fā)展，2011，48(5):855-861.Wang Suge，Li Deyu，Wei Yingjie.A method of text sentiment classification based on weighted rough membership［J］.Journal of Computer Research and Development，2011，48(5):855-861.(in Chinese)

［7］ 張孝飛，黃河燕.一種采用聚類技術(shù)改進的KNN文本分類方法［J］.模式識別與人工智能，2009，22(6):936-940.Zhang Xiaofei，Huang Heyan.An improved KNN text categorization algorithm by adopting cluster technology［J］.Pattern Recognition and Artificial Intelligence，2009，22(6):936-940.(in Chinese)

［8］ Thurber K J，Wald L D.Associative and parallel processors［J］.Computing Survey，1975，7(4):215-255.

［9］ Lim H W，Lee SH，Yang K A，et al.In vitro molecular pattern classification via DNA-based weighted-sum operation ［J］.BioSystems，2010，100(1):1-7.

［10］ Zhang B T.Hypernetworks:a molecular evolutionary architecture for cognitive learning and memory ［J］.IEEE Computational Intelligence Magazine，2008，3(3):49-63.

［11］ Park C H，Kim S J，Kim S，et al.Use of evolutionary hypernetworks for mining prostate cancer data［C］∥Proceedings of8th Int Symposium on Advanced Intelligent Systems.Heidelberg:Springer-Verlag，2007:702-706.

［12］ Bautu E，Kim S，Bautu A，et al.Evolving hypernetwork models of binary time series for forecasting price movements on stock markets［C］∥Proceedings of2009IEEE Congress on Evolutionary Computation.Piscataway:IEEE Computer Society，2009:166-173.

［13］ Ha JW，Eom JH，Kim SC，et al.Evolutionary hypernetwork models for aptamer-based cardiovascular disease diagnosis［C］∥Proceedings of9th Annual Genetic and Evolutionary Computation Conference.New York:ACM，2007:2709-2716.