粗糙集規則匹配算法及其在文本分類中的應用①

朱敏玲, 吳海艋, 石 磊

1(北京信息科技大學 計算機學院,北京 100101)

2(中國科學院 軟件研究所,北京 100190)

隨著信息技術的飛速發展,萬維網的文本信息量急劇增長[1]. 2008年7月26日,谷歌在官方微博中稱,其索引的網頁數量已經突破1萬億幅,截止至2014年12月底,這一數值更是突破了30萬億幅大關,并以每日50億的增長速度持續遞增[2]. 可見,如何從龐大的網頁數據中獲得有用信息成為人們的迫切需求,而自動文本分類是獲取相關信息的一種方法[3].

目前,文本分類領域常用的方法有支持向量機(SVM),樸素貝葉斯 (Na?ve Bayes),K 近鄰 (KNN),決策樹方法(Decision Tree)等[4],與這些傳統的分類方法相比,粗糙集理論用于分類的優點在于其能夠通過屬性約簡在不影響分類精度條件下降低特征向量的維數,從而獲得分類所需的最小特征子集,并配合值約簡得到最簡的顯式分類規則[5],最后根據粗糙集的規則匹配方法對待分類文本進行有效的分類.

本文首先對粗糙集理論和中文文本分類的相關知識進行介紹與分析,及如何將中文文本轉化為粗糙集所能處理的知識庫系統,和如何通過粗糙集的屬性約簡和值約簡來實現規則的提取; 然后,分析本研究中提出的粗糙集規則匹配的改進算法; 再次,對原始方法和改進算法進行對比實驗,并對實驗數據進行對比和分析; 最后,對本研究工作進行了總結.

1 相關知識

1.1 粗糙集理論

粗糙集 (Rough Set,RS) 理論是由波蘭華沙理工大學的Pawlak教授在1982年提出的一種新的數學工具,它能有效地處理和分析不精確、不協調和不完備的信息,并從中發現隱含的知識和潛在的規律[6]. 本文通過粗糙集理論中的知識約簡對文本進行分類規則提取,并通過改進的粗糙集匹配方法對新的待分類文本進行規則匹配和文本分類[7].

定義2. 設有信息系統S,是記載x在屬性a上的值,表示矩陣中的第i行,第j列元素,被定義為：

定義3. (區分函數)區分函數是從分辨矩陣中創造的. 約簡算法是先求的每個屬性的析取,再求其合取[9].

1.2 中文文本分類

相比于英文文本分類,中文文本分類的一個主要差別在于預處理階段,因為中文文本的詞與詞之間沒有明顯的切分標志,不像英文文本的單詞那樣有空格來區分. 首先,通過現有的分詞技術來對中文文本進行分詞處理,并在此基礎上提取一些重要的文本特征來將文本表示在向量空間. 本文的重點在于如何通過向量空間模型(VSM)和特定的特征選擇函數,將文本分出的字、詞、詞組或概念轉化為粗糙集理論所能處理的知識庫或信息系統,關鍵詞集即為信息系統中的條件屬性集,文本類別集即為決策屬性集. 通過Skowron提出的區分矩陣進行屬性約簡和規則提取[10],生成決策規則表,最后采用改進的規則匹配方法確定每條規則的規則支持度,最終作用于新文本的分類匹配中.

2 規則提取

2.1 文本預處理

文本預處理的過程主要包括：分詞處理、停用詞過濾、文本特征提取等[11]. 本文采用IKAnalyzer分詞工具,它是一款以開源項目Lucene為應用主體,結合詞典分詞和文法分析算法的中文分詞組件,其采用了特有的“正向迭代最細粒度切分算法”,有詞性標注、命名實體識別、分詞排歧義處理和數量詞合并輸出等功能,并支持個人詞條的優化的詞典存儲,如“北京奧運會”,“1949 年”,“反裝甲狙擊車”被納入用戶詞典后,可被正確分為一個詞條,而不會拆分為“北京”、“奧運會”,“1949”,“年”,“反”,“裝甲”,“狙擊”,“車”,同時停用詞過濾可以將文本使用頻率較大但對文本分類沒有實際作用的字、詞和詞組,例如：“的”,“和”,“同時”等,以及網絡文本中的格式標簽進行去除,例如：“@123456”,“本文來源”,“相關新聞”,“組圖”等,該分詞工具可在不影響文本原信息表達的情況下進行中文分詞,在文本分詞預處理中具有比較好的效果[12].

2.2 特征選擇

在文本分類中,常用的特征選擇函數有信息增益IG (Information Gain),期望交叉熵ECE (Expected Cross Entropy),互信息MI (Mutual Information)等[13].但是它們并不按類別計算統計值,所以選出的特征詞往往都是全局意義上的,而實際情況中,往往很多極具類別區分度的詞,如“劇組”,“直升機”,“導彈”,“演員”,“電子書”等,根據函數計算出的值不是很大,很可能被除掉,為了避免以上情的發生,本文采用CHI統計方法進行特征詞的選擇[14],選出的特征詞往往更具備類別區分度,其定義如公式(1)所示.

其中,w代表特定詞匯,Dj代表文本類別,N為文本總篇數;A為詞匯w與類別Dj共現的文本篇數;B為詞匯w出現類別Dj不出現的文本篇數C為類別Dj出現而詞而匯w不出現的文本篇數;D為詞匯w和類別Dj均不出現的文本篇數.

一般特征項的CHI值選取為對所有類別的CHI平均值或最大值,但是CHI統計方法由于考慮了特征項與類別的負相關性. 所以,在實際情況中,選詞結果往往偏向于類別區分度更高的那一類或那幾類文本,而對于文本內容比較相似、區分度較低的文本,選出的詞函數值普遍偏低,從而只有較少的類別區分詞被選中,對后續的粗糙集知識庫的知識約簡造成影響.故本文對CHI特征選擇算法進行了改進,規定選取時特征項的CHI值為其對所有類別的CHI最大值,并加入新的選擇公式對每類文本的特征詞數量進行重新分配,使選擇出的特征詞更偏向于類別區分度較低的幾類文本. 假設從K類文本中選取出N個特征項,改進后的公式(2).

即在原方法中,每類文本平均分到的特征詞數量為N/k,由于原CHI方法在特征選擇上對類別區分度較高的文本的偏袒,因此類別區分度較低的那幾類文本實際分到的特征詞數量將小于N/k,改進后的公式在N/k的基礎上乘以類別因子AVG(N)/AVGN,Dj消除后者在特征詞數量上的劣勢,其中為全部文本的前N個特征項的CHI平均值,AVGN,Dj為類別Dj中前N個特征項的CHI值平均值. 從式(2)可以看出,類別區分度較小的類別,其AVG(N)/AVGN,Dj更大,故實際分到的特征詞數也更多. 這也更有利于接下來的粗糙集屬性約簡,因為在類別區分度較大的類別中,過多的特征詞必定造成條件屬性的冗余,加大屬性約簡的負擔,甚至影響屬性約簡的結果.

2.3 生成文本決策表

根據改進后的CHI特征選擇方法選出前N個特征詞組成了決策表的條件屬性集,文本類別集合組成了決策屬性集. 特征詞的權重根據TF-IDF公式計算,如公式(3).

其中,tfik為特征項tk在文本di中出現的頻率,idfik為特征項tk的逆向文檔頻率.

考慮到TF-IDF公式計算出的權值為連續值,因此還需要對連續值進行離散化,如公式(4).

其中,Weightik表示該特征詞i在文本k中的權值,Wmin和Wmax分別表示特征詞i在所有決策表中的最小值和最大值.a和b表示縮放范圍[a,b].本文中對為0的項,取0,其余項根據縮放范圍取[1,3]進行權值離散化.并對最終結果取整(如1.123取值為1)作為離散化后的權值. 經過離散化后的決策表1所示.

表1 文本分類決策表

2.4 決策表的規則提取

在規則提取上分兩步走,首先進行特征詞的屬性約簡,隨后再進行屬性值約簡.

2.4.1 屬性約簡

為刪除對文本分類決策沒有影響的特征詞,利用粗糙集的屬性約簡能力在保證決策表分類能力不變的前提之下,刪除其中不相關、對決策結果不會造成影響的條件屬性,即文本特征詞,從而達到屬性約簡和降低特征維數的目的[15].

Skowron教授提出的區分矩陣和區分函數可以通過區分函數中的極小析取范式進行合取,獲得知識系統中的所有屬性約簡的集合,但是對于最優約簡子集的選擇一直都是一個NP問題[16],因此不在本文的討論范圍之內. 本文直接選取所有屬性約簡集合中條件屬性最少的約簡子集生成新的約簡決策表,并通過從約簡決策表中減少條件屬性的方法,依次計算每個條件屬性的重要程度,作為后續規則匹配中的一個重要參數,如公式(5).

2.4.2 值約簡

與粗糙集理論的屬性約簡相比,值約簡再次用到了區分矩陣獲取每一項中的極小析取范式,但兩者的不同之處在于,在對結果進行合取轉化時,屬性約簡是從全局出發,對所有的極小析取范式進行統一的合取化,其結果為所有屬性約簡結果的集合[17]. 而值約簡中是對區分矩陣的每一行進行合取化,每一條完整的規則最終被約簡為了多個能區分其他不同類別的最小規則集合.

表2 決策表

根據表2構造的區分矩陣如表3所示.

表3 區分矩陣

以表3的第2行為例,根據區分矩陣獲取第i行完全規則的約簡規則的步驟如下.

步驟1. 把每一行的空項和重復項去除,獲得互不重復的最小析取范式集.處理后的第2行,第2項和第

步驟2. 把每一行的最小析取范式進行合取化,獲得約簡規則集的條件屬性下標集合. 第2行提取出的規則集合表示為：

步驟3. 根據離散定律中的吸收律和冪等律刪除冗余和包含關系,獲得每一行的最簡規則集合. 第2行的最簡規則集合表示為：

經過值約簡后導出的約簡規則如表4所示,*代表約簡掉的屬性權值.

表4 決策規則表

然后,對約簡后的決策表中的重復規則和冗余規則進行合并,可得出表5的決策規則表.

表5 決策規則表

則,化簡后的規則如下：

對表2和表5分析可知,經過值約簡后的決策規則表,每條規則的條件前件長度得到了進一步的縮減,同時每兩條規則之間互不沖突,并且與原決策表的完整規則一一對應. 約簡后的規則集更加清晰明了,也具可解釋性.

3 規則匹配

決策規則生成之后,就可以運用規則對新數據項或文本進行預測和分類. 基于粗糙集的規則匹配分為完全匹配和部分匹配兩個階段.

3.1 完全匹配

1)完全匹配的基本步驟

步驟1. 在分類器中對新數據項進行規則化處理,抽取出與完全規則條件屬性一一對應的表達式.

步驟2. 在決策規則集中進行規則查找,如果有且只有一條規則與之完全對應,則新數據項的類別歸至該決策規則所屬的類別; 如果遍歷完所有規則后,沒有任何規則與之相匹配,則把該數據項歸入待定項進入部分匹配階段.

步驟3. 如果出現多個規則的前件與該數據項相匹配,則根據規則支持度的排序,把支持度最高的規則的決策類別定義為新對象的類別,如公式(7).

其中,Strength(R)是規則強度(Strength),即訓練集中與之匹配的訓練項個數;Specificity(R)是規則專指度(Specificity),即規則中條件屬性前件的個數; ω (R)是規則支持度[19].

但是,由于規則專指度會對規則中屬性條件較長的規則有所偏袒,導致完全匹配的規則結果往往選出條件屬性數較多的規則作為分類的依據,這與粗糙集理論的本意有所矛盾. 故本文對完全匹配的算法進行了改進,在完全匹配階段之前,對約簡規則進行規則預檢驗.

2)規則預檢驗

規則預檢驗的過程分為如下幾個步驟.

步驟1. 選取一份新的驗證集,并進行規則化.

步驟2. 將約簡規則與驗證集進行比較,依次求出規則強度和規則置信度(Confidence).

此時的規則支持度可表示為公式(8).

其中,Confidence(R)是規則置信度,即約簡規則與驗證集的規則條件匹配且類別標簽相同的比率. ω (R)值越大,表示根據該規則推導出的類別標簽的可信賴程度越大,在多個規則同時滿足匹配條件的情況下選擇ω(R)值最高的規則的類別進行匹配,其結果的準確率往往更高. 同時,如果某一新數據項完全匹配出的規則的 ω (R)=0或沒有任何規則與之相匹配,則把該數據項歸入待定項進入部分匹配階段.

從以上步驟得知,規則預檢驗的方法是基于規則支持度 ω (R)而展開的,其也存在一些缺憾. 若選取的支持度過高,則某些有價值的規則模式不能被獲取; 反之,過低時會產生很多無實際意義的規則模式,分類系統性能下降. 本文通過實際訓練來選取合適的特征詞數來彌補其缺憾.

3.2 部分匹配

部分匹配的基本過程是逐一減少新數據項的條件屬性個數,直到出現一條或多條規則能與之匹配為止.其匹配思路與完全匹配基本相同. 因此,部分匹配的規則支持度 ω (R)可以表示為公式(9).

其中,N為表示新對象的總條件屬性個數,Nc表示部分匹配過程中去掉的條件屬性個數.

同時,關于對新數據項條件屬性的去除次序的確定方法,本文規定,條件屬性去除的先后次序與文章之前的屬性約簡過程中計算的SIG(a,R,D)的升序次序保持一致,即屬性重要程度低的屬性會在部分匹配的過程中優先被去除.

經過完全匹配和部分匹配之后,如果出現沒有與現有規則相匹配的數據項,則將驗證集中規則支持度最高的結果賦給該項. 到此為止,規則匹配完全結束.

4 實驗結果及分析

為驗證該分類器的效果,進行了如下的實驗驗證.首先,選取合理的訓練集是非常必要的. 因為訓練集的文本數、類別數及特征項數對于分類器的執行效果都有重大影響[20]. 在此,選取了UCI(University of California Irvine)數據庫中的iris和diabetes數據集和Statlog中的australian和heart數據集作為訓練樣本,在每個數據集中任意選擇了3類數據. 同時,考慮到分類器默認情況下假設的樣本數是大致均勻分布的,如果一類比其他類數據量大得過分,分類器會把其他類的數據判為大的類別上,從而換取平均誤差最小. 為了避免該情況的發生,采取不同的樣本比例進行訓練的方法.

然后,采用第2節中提到的方法對原始數據進行處理,并把數據樣本分別按 1：1：1 和 5：2：3 的比例隨機打亂,各生成10份不同的訓練集,并記錄平均的分類準確率情況,實驗結果如表6所示. 改進后的匹配方法在4組數據集上的準確率相比于原方法,分類效果均有不同程度的提升. 同時,改進后的匹配方法在訓練集數據較少的情況下仍獲得不錯的分類效果.

表6 4種訓練集的訓練結果

表7為特征詞數相同而取不同訓練樣本數量時,2種匹配方法的訓練結果,數據集采用UCI的iris數據集. 對表7進行對比分析,可以看出改進后的匹配方法在訓練數據取不同數量的情況下,均獲得不錯的分類效果; 同時,在訓練數據小于測試數據的情況下分類效果的提升更加明顯. 因此,在對訓練數據量有限的數據進行分類的時候,改進后的匹配方法更加實用.

表7 iris訓練集的訓練結果(特征詞數=125)

表8為訓練樣本數相同,而特征詞數不同的情況下,原方法與本文改進后方法的執行結果. 可以看出,并不是特征詞數量越多準確率越高. 當訓練文本數都取360時,特征詞數量較少的情況下,改進方法的分類效果更佳; 特征詞數大于125后,兩種匹配方法的分類效果相差不大.

表8 特征詞數對分類效果的影響(訓練文本數=360)

經過訓練集的訓練后,不僅驗證了粗糙集約簡的效率,也驗證了本文規則提取方法的合理性,同時得到比較好的特征詞參數范圍.

最后,運用一般數據進行測試,驗證其泛化能力等.從網上下載和收集了來自騰訊新聞、鳳凰新聞、新浪新聞及網易新聞的新聞報道組成的語料庫,從中選用了軍事、娛樂、閱讀和法制四個類別共600篇文章作為實驗語料. 從特征詞數量和訓練文本數量兩個方面對改進前后的匹配方法進行分析,實驗結果如表9所示. 由表9可知,當特征詞數都取125時,測試文本取不同數量的情況下,改進方法的分類效果均有不同程度的提高; 同時,在測試文本數較少時,改進方法對分類效果的提升更加明顯.

表9 訓練文本數對分類效果的影響(特征詞數=125)

5 結束語

本文把粗糙集理論應用于中文文本分類的規則提取和規則匹配中,并對基于CHI方法的類別特征詞選取方法進行了相應的改進,使其更加適用于粗糙集的知識約簡. 在訓練階段使用區分矩陣對完整決策規則進行屬性約簡和規則提取,并通過規則預驗證的方法對規則支持度進行優化; 同時,通過調整特征詞的數量來彌補規則預檢驗方法所帶來的信息損失而影響有效規則提取的問題. 實驗結果表明,改進后的規則匹配方法在實際的文本分類中分類準確率更高,同時在一定程度上克服了原匹配方法容易選出條件前件數較多的規則的缺點,也使得匹配出的規則更加簡單明了,更具可解釋性.

1 Fan W,Bifet A. Mining big data：Current status,and forecast to the future. ACM SIGKDD Explorations Newsletter,2012,14(2)：1-5.

2 朱基釵,高亢,劉碩. 互聯網絡發展狀況統計. 黨政論壇·干部文摘,2016,(9)：19. [doi：10.3969/j.issn.1006-1754.2017.01.016]

3 Shen YD,Eiter T. Evaluating epistemic negation in answerset programming. Artificial Intelligence,2016,237：115-135. [doi：10.1016/j.artint.2016.04.004]

4 吳德,劉三陽,梁錦錦. 多類文本分類算法GS-SVDD. 計算機 科 學,2016,43(8)：190-193. [doi：10.11896/j.issn.1002-137X.2016.08.038]

5 程學旗,蘭艷艷. 網絡大數據的文本內容分析. 大數據,2015,(3)：62-71.

6 朱敏玲. 屬性序下的粗糙集與KNN相結合的英文文本分類研究. 黑龍江大學自然科學學報,2015,32(3)：404-408.

7 Mitra S,Pal SK,Mitra P. Data mining in soft computing framework：A survey. IEEE Transactions on Neural Networks,2002,13(1)：3-14. [doi：10.1109/72.977258]

8 Miao DQ,Duan QG,Zhang HY,et al. Rough set based hybrid algorithm for text classification. Expert Systems with Applications,2009,36(5)：9168-9174. [doi：10.1016/j.eswa.2008.12.026]

9 Grzymala-Busse WJ. Rough set theory with applications to data mining. In：Negoita M,Reusch B,eds. Real World Applications of Computational Intelligence. Berlin,Heidelberg,Germany：Springer,2005.

10 Pawlak Z,Skowron A. Rudiments of rough sets. Information Sciences,2007,177(1)：3-27. [doi：10.1016/j.ins.2006.06.003]

11 朱敏玲. 基于粗糙集與向量機的文本分類算法研究. 北京信息科技大學學報,2015,30(4)：31-34.

12 馬曉玲,金碧漪,范并思. 中文文本情感傾向分析研究. 情報資料工作,2013,34(1)：52-56.

13 李揚,潘泉,楊濤. 基于短文本情感分析的敏感信息識別.西 安 交 通 大 學 學 報,2016,50(9)：80-84. [doi：10.7652/xjtuxb201609013]

14 黃章樹,葉志龍. 基于改進的CHI統計方法在文本分類中的應用. 計算機系統應用,2016,25(11)：136-140.

15 梁海龍. 基于鄰域粗糙集的屬性約簡和樣本約減算法研究及在文本分類中的應用[碩士學位論文]. 太原：太原理工大學,2015.

16 楊傳健,葛浩,汪志圣. 基于粗糙集的屬性約簡方法研究綜述. 計算機應用研究,2012,29(1)：16-20.

17 胡清華,于達仁,謝宗霞. 基于鄰域粒化和粗糙逼近的數值屬性約簡. 軟件學報,2008,19(3)：640-649.

18 段潔,胡清華,張靈均,等. 基于鄰域粗糙集的多標記分類特征選擇算法. 計算機研究與發展,2015,52(1)：56-65.[doi：10.7544/issn1000-1239.2015.20140544]

19 時希杰,沈睿芳,吳育華. 基于粗糙集的兩階段規則提取算法與有效性度量. 計算機工程,2006,32(3)：60-62.

20 李湘東,曹環,黃莉. 文本分類中訓練集相關數量指標的影響研究. 計算機應用研究,2014,31(11)：3324-3327. [doi：10.3969/j.issn.1001-3695.2014.11.028]