基于核覆蓋算法的中文文本分類研究

楊麗玲

(漳州職業(yè)技術(shù)學(xué)院 計算機工程系,福建 漳州 363000)

0 引言

互聯(lián)網(wǎng)的快速發(fā)展，帶來了信息的海量增長．如何從海量信息資源中高效準確地找到所需的信息，信息分類是必不可少的第一步．傳統(tǒng)上的文本分類工作通過人工來完成，這樣做在準確性上相對較有保障，但遠遠無法滿足人們多元化的需求．而文本自動分類技術(shù)為我們完成這項工作提供了很大的幫助，其在信息檢索技術(shù)中具有重要的地位．

1 文本分類的定義

文本分類的工作就是將文本按照其特定的涵義劃分到相應(yīng)的類別中．即利用預(yù)先定義好的文本類別訓(xùn)練文本，找出訓(xùn)練文檔與類別之間的關(guān)系，并由此指導(dǎo)測試文本的學(xué)習(xí),從而確定新文本所屬類別．文本分類是一個構(gòu)造映射函數(shù)ф的過程，設(shè)文檔集D= {d1,d2,…,dj,…,},預(yù)定義類集C= {C1,C2,…,Ci,…,},確定任意一個元組〈dj,Ci〉映射到集合{K,P}上的值，即函數(shù)ф:D×C→{K,P}．從廣義上來講,分類是數(shù)據(jù)挖掘的一種方法．但與傳統(tǒng)的數(shù)據(jù)挖掘不同的是,文本分類面對的是非結(jié)構(gòu)化的數(shù)據(jù)．而目前在文本分類過程中大部分是將非結(jié)構(gòu)化的數(shù)據(jù)結(jié)構(gòu)化后,再進行傳統(tǒng)的分類方法．即文檔建模的過程．

2 文本分類的主要過程及關(guān)鍵技術(shù)

文本分類過程首先是文本預(yù)處理；其次是選擇合適的特征，并為每個特征計算出相應(yīng)的權(quán)重；再次是根據(jù)預(yù)處理后的訓(xùn)練集建模，構(gòu)建出分類器，并對分類器分類效果進行評估；最后是使用分類器對測試文本進行分類[1]．其中關(guān)鍵技術(shù)是特征選取、賦權(quán)以及分類器構(gòu)造．如圖1 所示．

圖1 文本分類模型

經(jīng)過文本預(yù)處理后，我們用特征項(詞組) 的權(quán)重表示一個向量，但此時特征向量維數(shù)仍較大，需要我們利用有效的工具進行特征選取，從而尋找最有效的特征構(gòu)成較低維數(shù)的模式向量．

特征選取是通過某種方法挑選出跟文檔主題概念關(guān)系密切的特征,組成一個新的低維空間，以降低特征矩陣的維數(shù)，同時不改變原有特征空間的性質(zhì)．其準則是經(jīng)特征選擇后能有效提高文本準確率．

特征選取主要有特征頻度TF，文檔頻度DF,信息增益IG,X2統(tǒng)計,互信息 MI，相關(guān)系數(shù)法CC以及期望交叉熵ECE等方法[2-3]．這些方法的基本思想是對每一個特征計算它的權(quán)值，把權(quán)值小于指定閾值p的那些特征刪除，那么最后留下的即認為是有效特征．當(dāng)然這些算法有其存在的不足點，我們需要根據(jù)具體系統(tǒng)來進行選擇確定．

2.1 特征頻度TF

特征頻度指特征在訓(xùn)練集中出現(xiàn)的頻率．這是較為簡單的特征選擇方法．如果特征在訓(xùn)練集中出現(xiàn)頻率越大,則認為其對文本分類越有用．因此,通過設(shè)定一個閾值來過濾低頻特征，從而降低維度．因此，特征頻度主要用在文本分類時直接刪除某些低頻特征．

2.2 互信息MI

互信息MI主要體現(xiàn)了特征項與類別的關(guān)系程度．對于特征項w和某一類別cj∈(c1,c2,c3,…ck)，如果特征項在cj中出現(xiàn)的概率高，而在其它類別中出現(xiàn)的概率低，那么特征項w將獲得較高的互信息，也就有可能被選取為類別cj的特征．w和cj的互信息定義如式(1)：

(1)

式中P(w|cj)表示在文檔中特征項出現(xiàn)的概率，也可以表示為式(2)形式：

(2)

式中A表示特征w與類cj同時出現(xiàn)的概率；B表示特征w不在類cj中出現(xiàn)的概率；C表示類cj中沒有出現(xiàn)特征w的文本數(shù)；N表示總的文本數(shù)．

在訓(xùn)練過程中，這些概率可以用文本在訓(xùn)練集中相應(yīng)的出現(xiàn)頻率進行計算．但互信息有一個不足，互信息評估函數(shù)經(jīng)常傾向于選擇稀有單詞,而這在特征選取時會刪掉很多高頻的有用詞條．

2.3 相關(guān)系數(shù)法 CC

特征的相關(guān)系數(shù)法主要考慮的是特征與類型的正相關(guān)性．如式(3)所示

(3)

式中c表示類別；n表示總文本數(shù)；A表示w和c同時出現(xiàn)的次數(shù)；B表示w出現(xiàn)而c沒有出現(xiàn)的次數(shù)；C表示c出現(xiàn)而w沒有出現(xiàn)的次數(shù)；D表示w和c都沒有出現(xiàn)的次數(shù)．進行特征選擇時,選擇CC值大的特征，進一步強調(diào)特征和類之間的相關(guān)性．

2.4 期望交叉熵ECE

交叉熵，與信息增益類似，但其只考慮特征在文本中出現(xiàn)的這種情況．假定c為文本類變量，C為文本類的集合，對于特征f，其交叉熵記為CE(f)，則有：

(4)

若只考慮單個類，則有：

(5)

3 核覆蓋算法

核覆蓋算法就是在普通覆蓋算法上引入支持向量機SVM的核函數(shù)法的一種新算法，用它來處理高維海量數(shù)據(jù)的學(xué)習(xí)方法[4-7]．

核覆蓋算法利用核函數(shù)將數(shù)據(jù)映射到一個更易識別的高維空間,然后在此空間中利用普通覆蓋算法進行求解．這樣不僅克服了原覆蓋算法映射到一個充分大的球面上的不足，而且其識別的方法簡單，準確率高[8-10]．

具體算法如下：

①先計算所有樣本的中心，再找離中心最近的樣本點t，并從該樣本點t開始覆蓋；

②求出離t最近的異類點的距離x1和離t最遠的同類點的距離記為x2(x2

③求領(lǐng)域C(t)所覆蓋的點的重心t′,按②步驟計算其半徑,得球形領(lǐng)域C(t′)；

④重復(fù)②③，直到覆蓋的樣本數(shù)少于求重心前的樣本數(shù)；

⑤求t的平移點t″,并求對應(yīng)的球形領(lǐng)域C(t″).若C(t″)覆蓋的點數(shù)大于C(t),則進入③,否則,得到一個覆蓋K1類點的局部最大領(lǐng)域C(t)，覆蓋的K1中的子集記為K1i；

⑥找一個不同類的點t開始覆蓋，其類別為K2，令T<-K1/K1t，K1<-K2，K2<-T；

⑦重復(fù)②～⑥，直到處理完所有類點．

4 實驗結(jié)果

選取中文自然語言處理平臺的計算機等五類中文文本,采用多種特征提取方法對高維文本數(shù)據(jù)進行多次實驗，本文所有實驗都是在CPU為intel pentinum4 2.6 GHZ,編程環(huán)境為MATLAB6.5.1下完成的．實驗結(jié)果如表1所示．

表1 不同特征選取的實驗結(jié)果對比表

從實驗結(jié)果中，我們看到：

①對語料庫中的文本信息采用不同的特征選取方法，得到的實驗結(jié)果相差較大．其中互信息MI方法只有不到40%的識別率，這是由于互信息特征提取方法受詞條邊緣概率的影響較大，易造成互信息評估函數(shù)經(jīng)常傾向于選擇稀有單詞而刪除高頻的有用詞條，從而造成較低的識別率和文本覆蓋數(shù)較少．而其它的幾種特征選取方法得到的識別率和覆蓋數(shù)都比較高．

②構(gòu)造性學(xué)習(xí)雖然在多文本分類問題上處理效率高，但存在計算量大等不足．而核覆蓋算法將SVM 中的核函數(shù)法與覆蓋算法相融合，克服了以上缺點，具有運算速度快、精度高的優(yōu)點．但其也存在一些不足，如核函數(shù)的參數(shù)選取對實驗的結(jié)果影響較大，需經(jīng)過多次的實驗及計算才能找到合適的參數(shù)，造成文本分類工作量的增大．

[1]楊麗玲.基于概率的覆蓋算法在文本分類器中的應(yīng)用[J].漳州職業(yè)技術(shù)學(xué)院學(xué)報，2009，11(2):1～3．

[2]陳 濤,謝陽群.文本分類中的特征降維方法綜述[J].情報學(xué)報，2005，24(6):690～695．

[3]劉 里.中文文本分類而有信中特征描述及分類器構(gòu)造方法研究[D].重慶：重慶大學(xué)，2006．

[4]吳 濤,張 鈴,張燕平.機器學(xué)習(xí)中的核覆蓋算法[J].計算機學(xué)報，2005，28(8):1295～1301．

[5]趙 姝，張燕平，張 媛，等.基于交叉覆蓋算法的改進算法——核平移覆蓋算法[J].微機發(fā)展,2004,14(11):1～3．

[6]吳 濤，張燕平，張 鈴.前向神經(jīng)網(wǎng)絡(luò)交叉覆蓋算法的一種改進[J].微機發(fā)展,2003,13(3):50～52．

[7]趙 姝，張燕平，張 鈴，等.覆蓋聚類算法[J].安徽大學(xué)學(xué)報(自然科學(xué)版)，2005,29(2):28～32．

[8]蘇小英,胡彥鵬,楊竣輝,等.一種新的用于文本分類的概率分類器設(shè)計[J].計算機技術(shù)與發(fā)展,2014,24(3):46～48,53．

[9]董 賀,榮光怡.數(shù)據(jù)挖掘中數(shù)據(jù)分類算法的比較分析[J].吉林師范大學(xué)學(xué)報(自然科學(xué)版)，2008,29(4):107～108．

[10]田苗苗.基于決策樹的文本分類研究[J].吉林師范大學(xué)學(xué)報(自然科學(xué)版)，2008，29(1):54～56．