- 相關(guān)推薦
基于粗糙集的文本分類研究
摘 要：文本分類是信息檢索和數(shù)據(jù)挖掘等領(lǐng)域的研究熱點(diǎn)。在現(xiàn)有的一些文本分類方法中，文本都是基于向量空間模型表示的，所形成的特征空間維數(shù)相當(dāng)高，導(dǎo)致分類算法效率不高，分類精度不理想。粗糙集應(yīng)用到文本分類可以在不影響分類精度的條件下降低特征向量的維數(shù)，并且可以得到的顯式表達(dá)的分類規(guī)則。本文旨在介紹文本分類一般過程，分析將粗糙集理論應(yīng)用到文本分類中關(guān)鍵步驟，總結(jié)粗糙集與其他分類算法結(jié)合應(yīng)用到文本分類的情況。
關(guān)鍵詞：文本分類;粗糙集理論;屬性約簡
1. 引言
近年來隨著網(wǎng)絡(luò)和信息技術(shù)的發(fā)展，我們的工作和生活得到了極大的便利，可獲得的信息量急劇增長。但我們在得到便利的同時(shí)也被浩如煙海的數(shù)據(jù)所淹沒，想要快速有效的找到所需的內(nèi)容也越來越困難，若用傳統(tǒng)的手工分類和處理不但耗費(fèi)大量的人力和物力，而且在速度和精度方面也遠(yuǎn)遠(yuǎn)不能滿足要求，這對文本的分類技術(shù)提出了迫切的要求。
文本分類是信息檢索和信息智能處理的基礎(chǔ)，近年來受到了廣泛的關(guān)注，很多學(xué)者對此做了深入的研究。目前基于統(tǒng)計(jì)方法和機(jī)器學(xué)習(xí)的方法的已經(jīng)應(yīng)用到文本分類，并且取得了豐碩的成果。目前在文本分類中常用的分類方法有：樸素貝葉斯(Na?ve Bayes)、支持向量機(jī)(SVM)、決策樹、K-緊鄰(KNN)、人工神經(jīng)網(wǎng)絡(luò)等。在文本分類中，廣泛使用向量空間模型(VSM)來表示文本。由于自然語言的復(fù)雜特性，文本的特征空間的維數(shù)會特別高，如中文字Bigram 特征集的大小高達(dá)上百萬，如此高維的特征空間使得一些算法無法進(jìn)行或者效率非常低。為此有些系統(tǒng)在頻率統(tǒng)計(jì)的基礎(chǔ)上，使用閾值過濾掉一些特征來降低維數(shù)，但是這樣會造成信息的丟失，特別是對分類重要的低頻特征，從而影響了分類效果。
粗糙集理論(Rough Set)是由波蘭數(shù)學(xué)家Pawlak在1982 年提出的一種能夠處理不精確、不一致、不完整信息與知識的數(shù)學(xué)理論。粗糙集理論能夠有效的分析和處理不完備信息，已經(jīng)成為一種重要的信息處理技術(shù)，并在機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、決策支持與分析等方面得到了廣泛的應(yīng)用。粗糙集理論是建立在分類機(jī)制的基礎(chǔ)上的，將分類理解為在特定空間上的等價(jià)關(guān)系，而等價(jià)關(guān)系構(gòu)成了對該空間的劃分，粗糙集理論用上下近似來描述這種劃分。
上近似和下近似對應(yīng)著確定屬于給定類的最大的對象集合和可能屬于給定類的最小的對象集合。通過其知識約簡理論得到屬性的最小子集，能夠很好的近似分類，并可以顯式表示分類規(guī)則。
本文主要介紹文本分類的一般過程與框架，粗糙集理論的特性以及應(yīng)用到文本分類的可行性，然后分析基于粗糙集理論的文本分類模型。
2. 文本分類一般過程與框架
文本分類是基于文本的內(nèi)容將未知類別標(biāo)號的文本劃分到一個(gè)或者多個(gè)預(yù)先給定的類別中，從而提高信息檢索等應(yīng)用的效率。文本分類的一般過程包括：文本的向量表示、特征降維、特征加權(quán)、分類器的構(gòu)建與訓(xùn)練、分類結(jié)果的評價(jià)與反饋等。圖1 是一個(gè)簡單的文本分類系統(tǒng)的簡單的框架圖，其中實(shí)線表示分類器建立過程中的數(shù)據(jù)流，虛線表示分類器測試過程中的數(shù)據(jù)流。
2.1 文本的向量表示
將文檔表示成計(jì)算機(jī)能處理的形式是進(jìn)行文本分類的基礎(chǔ)工作，目前廣泛使用向量空間模型VSM 來表引文本，即把每個(gè)文本看作是由一系列特征詞構(gòu)成的集合。這部分工作主要包括處理亂碼以及非文本內(nèi)容、過濾停用詞、合并詞干、對中文文本進(jìn)行分詞處理等。中文分詞技術(shù)目前比較有影響力的是中科院開發(fā)的漢語詞法分析系統(tǒng)(ICTCLAS)，目前已經(jīng)在文本分類系統(tǒng)中得到廣泛應(yīng)用。
2.2 特征降維
文檔經(jīng)過預(yù)處理以后，其特征空間通常是高維空間，這會導(dǎo)致一些分類算法無法進(jìn)行或者效率非常低，所以必須對特征空間進(jìn)行降維處理。特征降維的方法主要有兩種：特征選擇和特征抽取。特征選擇就是從原特征集中選擇一個(gè)真子集作為其特征集，選擇的依據(jù)是特征對分類作用的大小，通常使用一個(gè)統(tǒng)計(jì)量來度量，如特征頻度、文本頻度、特征熵、互信息、信息增益、相關(guān)系數(shù)、Chi-square 等。特征抽取則是把高維的特征空間轉(zhuǎn)換成一個(gè)低維的特征空間，實(shí)現(xiàn)降維，常用的特征抽取方法有三類：特征聚類、主成分分析和潛在語義表引。特征降維不僅能夠大大降低處理開銷，而且在很多情況下可以改善分類器的分類效果。
2.3 特征加權(quán)
為了更準(zhǔn)確的描述特征在文本中的重要性，在文本用向量表示后，需要對文本向量中的特征賦予一定的權(quán)重。這主要通過詞對分類的貢獻(xiàn)程度的分析，把分類貢獻(xiàn)大的特征賦予高的權(quán)值，而貢獻(xiàn)度小的或不相關(guān)的數(shù)據(jù)則賦予低的權(quán)值。采用合理特征加權(quán)方式有助于增大特征詞之間的差異、凸顯文本的特性和提高分類的精度。目前有很多權(quán)重函數(shù)來計(jì)算關(guān)鍵字在文檔向量中的權(quán)重，如布爾權(quán)重函數(shù)、TF-IDF 權(quán)重函數(shù)、ITC 權(quán)重函數(shù)、Okapi 權(quán)重函數(shù)等。
2.4 分類器的構(gòu)建與訓(xùn)練
選擇不同分類算法決定著分類器的性能好壞，目前基于統(tǒng)計(jì)方法和機(jī)器學(xué)習(xí)的文本分類比較成熟，在很多文本分類系統(tǒng)中得到應(yīng)用。另外還有基于語義和概念網(wǎng)絡(luò)的文本分類方法，但是由于自然語言處理領(lǐng)域的研究進(jìn)展相對較慢，所以在這方面還沒有太大發(fā)展。常用的分類算法有：支持向量機(jī)(SVM)、樸素貝葉斯(Na?ve Bayes)、K 近鄰方法(KNN)、Rocchio、TFIDF、決策樹、神經(jīng)網(wǎng)絡(luò)等。
2.5 組合分類器
各種分類器都有自己分類優(yōu)勢，如果將多個(gè)分類器的分類結(jié)果優(yōu)化組合起來會比單個(gè)分類器的分類效果好。已有學(xué)者證明，如果單個(gè)分類器相互獨(dú)立，當(dāng)分類器的個(gè)數(shù)趨于無窮時(shí)，組合分類器的分類錯誤會趨向于零。組合的策略主要有多數(shù)選舉、加權(quán)組合、動態(tài)分類器選擇和自適應(yīng)分類器組合等。組合分類器已在文本分類系統(tǒng)中廣泛的應(yīng)用，并取得了不錯的分類效果。
2.6 評價(jià)標(biāo)準(zhǔn)
文本分類的評價(jià)是通過實(shí)驗(yàn)數(shù)據(jù)分析獲得的，在該部分把測試集中的每個(gè)文本進(jìn)行預(yù)處理后，輸入到分類器進(jìn)行分類。通過對分類結(jié)果的統(tǒng)計(jì)分析然后進(jìn)行評價(jià)。現(xiàn)在常用的評價(jià)標(biāo)準(zhǔn)有：準(zhǔn)確率/召回率、break-even 點(diǎn)、F-measure、11 點(diǎn)平均準(zhǔn)確率圖、精度/錯誤率等;另外還有微平均和宏平均分別用來描述一個(gè)類和全部類的分類情況。
2.7 數(shù)據(jù)集
在構(gòu)建和測試文本分類系統(tǒng)的時(shí)候需要用到大量的文本資料，如果能使用一個(gè)標(biāo)準(zhǔn)的數(shù)據(jù)集進(jìn)行研究，不僅可以減少建設(shè)數(shù)據(jù)集的費(fèi)用，而且可以使得不同研究者的分類結(jié)果具有可比性。現(xiàn)在國際上用于文本分類的英文標(biāo)準(zhǔn)數(shù)據(jù)集主要有以下幾個(gè)：Reuters-21578，OHSUMED，20Newsgroups 和TREC 等。目前為止還沒有標(biāo)準(zhǔn)的中文數(shù)據(jù)集，不過研究中比較常用的有搜狗語料庫、復(fù)旦大學(xué)中文語料庫和北京大學(xué)語料庫等等。
3. 基于粗糙集理論的文本分類模型
粗糙集理論是一種分析不確定知識的強(qiáng)有力的數(shù)學(xué)工具，可以對不精確、不一致、不完整等各種不完備信息進(jìn)行有效分析和處理，并從中發(fā)現(xiàn)隱含的知識，揭示信息中潛在的規(guī)律。粗糙集理論研究的是不同類中的對象組成的集合關(guān)系，利用不可分辨關(guān)系進(jìn)行分類[16~18]。無需提供除所需處理的數(shù)據(jù)集合外的任何先驗(yàn)信息，對問題的處理比較客觀。通過對原始決策表的約簡，可以在保持決策一致(即分類能力不發(fā)生改變)的前提下對屬性進(jìn)行約簡，可以大大降低特征向量的維數(shù)，從而方便處理提高效率。通過粗糙集理論進(jìn)行分類，可以得到最約簡顯式表達(dá)的分類規(guī)則。
盡管粗糙集理論在處理不確定性不完備的信息有著不可替代的優(yōu)勢，但是粗糙集理論也存在著某些片面性和不足。粗糙集理論模型要處理的分類必須是完全正確或肯定的，嚴(yán)格的按照等價(jià)類進(jìn)行分類，所以在實(shí)際應(yīng)用中多使用粗糙集理論的改進(jìn)模型，如Ziarko[19]基于多數(shù)包含關(guān)系的提出的可變精度粗糙集模型等。
將粗糙集理論應(yīng)用到文本分類模型，主要是利用了粗糙集理論對知識等價(jià)劃分的思想。
首先將文本的特征詞作為條件屬性，類別作為決策屬性，構(gòu)建決策表;通過加權(quán)規(guī)則對特征值進(jìn)行加權(quán);然后對加權(quán)后的權(quán)值進(jìn)行離散處理;再利用粗糙集理論的知識約簡在決策表中得到最分類規(guī)則;最后建立相應(yīng)的匹配規(guī)則，通過對測試集分類對該分類器性能進(jìn)行評估。
概括起來主要有四個(gè)步驟：文本預(yù)處理、屬性約簡、構(gòu)建分類器和性能評價(jià)�；诖植诩碚摰奈谋痉诸惸Ｐ�，其中實(shí)線表示分類器建立過程中的數(shù)據(jù)流，虛線代表分類器測試過程中的數(shù)據(jù)流。
3.1 關(guān)鍵步驟
3.1.1 構(gòu)建決策表
利用粗糙集理論獲得規(guī)則是通過對決策表里面的條件屬性和決策屬性進(jìn)行屬性的約簡得到的，在此訓(xùn)練集的文本要表示成本粗糙集理論能夠處理的決策表形式。使用向量空間模型VSM 來表引文本，將文本的特征詞作為條件屬性，文本的類別作為決策屬性，構(gòu)建決策表。
3.1.2 數(shù)據(jù)離散
粗糙集理論分析要求數(shù)據(jù)的值必須以離散的形式表達(dá)，然而在實(shí)際應(yīng)用中對特征進(jìn)行加權(quán)后得到的權(quán)值的值域?yàn)檫B續(xù)值，所以在應(yīng)用粗糙集理論方法處理之前，必須采用一種適宜的離散方法將連續(xù)數(shù)據(jù)轉(zhuǎn)化為離散區(qū)間，經(jīng)過數(shù)據(jù)離散后可能會減小原始數(shù)據(jù)表示的精度，但將會提高其一般性。
數(shù)據(jù)離散的結(jié)果直接影響到分類的效果。在粗糙集理論中應(yīng)用的離散算法很多，大體上可以將其分為兩類：一類是直接借用其它學(xué)科中的離散算法，如等距離劃分、等頻率劃分等;另一類是考慮到粗糙集理論對決策表的特殊要求，采用結(jié)合的方法來解決離散化問題，如Na?ve Scaler 算法，Semi Na?ve Scaler 算法，布爾邏輯和Rough 集理論相結(jié)合，以及基于斷點(diǎn)重要性、屬性重要性和聚類的離散算法等。
3.1.3 屬性約簡
屬性約簡是粗糙集理論的核心內(nèi)容之一，也是應(yīng)用粗糙集理論構(gòu)建分類器的重要部分。
屬性約簡的目標(biāo)就是要從條件屬性集合中找出部分必要條件屬性，使得這部分條件屬性和所有的條件屬性相對于決策屬性有相同的分類能力。經(jīng)過屬性約簡去除了不必要的屬性，實(shí)現(xiàn)信息屬性的約簡，從而分析所得約簡中的條件屬性對于決策屬性的決策規(guī)則。
目前常用的約簡算法可分為兩類，一類是不借助任何啟發(fā)信息的屬性約簡，另一類是啟發(fā)式算法，如基于屬性重要度的屬性約簡算法、基于Skowron 差別矩陣的屬性約簡算法、以及基于信息熵的屬性約簡算法等，基于蟻群算法的屬性約簡算法等。
3.1.4 值約簡和規(guī)則合成
通過屬性約簡得到的約簡并不是唯一的，但是還沒有充分去掉決策表中的冗余信息，還需要進(jìn)一步對決策表進(jìn)行處理，得到更加簡化的決策表，這部分工作就是決策表值約簡。然后按照一定的策略將多個(gè)約簡表中的相應(yīng)規(guī)則進(jìn)行合成，得到最終的分類決策規(guī)則。決策表值約簡算法有一般值約簡算法、歸納值約簡算法、啟發(fā)式值約簡算法和基于決策矩陣的值約簡算法等。
3.2 粗糙集理論與其他算法構(gòu)建的文本分類模型
粗糙集理論的屬性約簡理論可以降低文本分類過程中的向量維數(shù)，減少特征數(shù)，從而提高了分類速度。利用這一優(yōu)勢可以與其他分類算法結(jié)合構(gòu)成性能不錯的分類器。李鈍等在空間向量模型的基礎(chǔ)上將文本聚類和粗糙集理論的屬性約簡相結(jié)合，提出了一種新的文本分類方法，實(shí)驗(yàn)表明該方法可提高文本分類效率。張著英將粗糙集理論應(yīng)用到KNN 算法中,實(shí)現(xiàn)屬性約簡,提出了一種新的KNN 分類方法,解決了KNN 算法分類效率低的缺點(diǎn)，從而可使KNN 算法能夠得到更廣泛的應(yīng)用。王效岳等結(jié)合粗糙集理論的屬性約簡和神經(jīng)網(wǎng)絡(luò)的分類機(jī)理提出一種混合算法，分類速度得到提高，并體現(xiàn)較好的穩(wěn)定性及容錯性。
上述模型主要是應(yīng)用粗糙集理論的屬性約簡作為分類系統(tǒng)的預(yù)處理器，把冗余的屬性從決策表中刪去，然后運(yùn)用其他分類算法進(jìn)行分類。還有一些研究者將粗糙集理論以其他的方式應(yīng)用到文本分類中，比如Miao 等提出基于變精度粗糙集的混合算法，利用KNN 和粗糙集理論對樣本空間進(jìn)行劃分，然后用簡單快速的Rocchio 進(jìn)行分類，并取得了不錯的分類結(jié)果;將粗糙集理論的分類質(zhì)量應(yīng)用到特征加權(quán)[27], 改進(jìn)了文本樣本在整個(gè)空間中的分布，使得類內(nèi)距離減少，類間距離增大，提高樣本的可分性等。
4. 總結(jié)
文本分類近年來已經(jīng)得到很大的發(fā)展，有很多比較成熟的分類算法得到了應(yīng)用，但是過高的特征空間維數(shù)限制了分類的效率和精度。特征選擇雖然可以降低特征數(shù)量，但也不可避免的造成了有用信息的丟失，降低了分類效果。將粗糙集理論應(yīng)用到的文本分類模型中，可以利用粗糙集理論知識約簡理論，在保持分類能力的情況下得到最小的屬性約簡并得到顯式的規(guī)則。不過由于粗糙集理論本身限制條件較強(qiáng)，在實(shí)際應(yīng)用中多利用其擴(kuò)展模型或與其他算法相結(jié)合的方式，概括來說有三種方式：一是利用粗糙集理論作為預(yù)處理器，實(shí)現(xiàn)降維，結(jié)合其他分類算法構(gòu)建分類器;二是利用粗糙集理論的約簡理論直接得到分類規(guī)則構(gòu)建分類器;三是利用粗糙集理論的上下近似對樣本空間進(jìn)行劃分，提高樣本的可分性。
參考文獻(xiàn)
[1] 王國胤，姚一豫，于洪.粗糙集理論與應(yīng)用研究綜述[J].計(jì)算機(jī)學(xué)報(bào)，2009，32(7):1229-1246.
[2] 張文修，吳偉志.粗糙集理論介紹和研究綜述[J].模糊系統(tǒng)與數(shù)學(xué)，2000，14(4): 1-12.
[3] 唐春生，張磊，潘東，等.文本分類研究進(jìn)展
[4] 靳小波.文本分類綜述[J].自動化博覽. 2006 23(z1): 24-29.
[5] 薛德軍.中文文本自動分類中的關(guān)鍵問題研究[D].北京：清華大學(xué)，2004.
[6] 蘇金樹，張博鋒，徐昕.基于機(jī)器學(xué)習(xí)的文本分類技術(shù)研究進(jìn)展[J].軟件學(xué)報(bào)2006, 17(9):1848-1855.
[7] 蒲筱哥.Web 自動文本分類技術(shù)研究綜述[J].情報(bào)學(xué)報(bào) 2009,28(2):233-241.
[8] 錢曉東.數(shù)據(jù)挖掘中分類方法綜述[J].圖書情報(bào)工作，2007，51(3):68-71.
[9] 王國胤.Rough 集理論與知識獲取[M]. 西安：西安交通大學(xué)出版社，2001.
[10] 菅利榮.面向不確定性決策的雜合粗糙集方法及其應(yīng)用[M]. 科學(xué)出版社，2008.
[11] Ziarko W.. A variable precision rough set model [J]. Journal of Computer and System Sciences, 1993, 46:39-59.
[12] 汪慶， 張巍， 劉鵬. 連續(xù)特征離散化方法綜述[EB/OL].
[13] 王國胤，劉靜，胡峰. 基于斷點(diǎn)辨別力的粗糙集離散化算法[J].重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版)，2009，21(3)：388-392.
[14] 劉業(yè)政，焦寧，姜元春.連續(xù)屬性離散化算法比較研究[J]. 計(jì)算機(jī)應(yīng)用研究，2007，24(9)：28-33.
[15] 李鈍，梁吉業(yè).利用聚類和粗糙集進(jìn)行文本分類研究[J].計(jì)算機(jī)工程與應(yīng)用，2003，39(7)：186-188.
[16] 張著英，黃玉龍，王翰虎.一個(gè)高效的KNN 分類算法[J].計(jì)算機(jī)科學(xué)，2008 ，35(3)：170-172
[17] 王效岳，白如江.一種基于粗糙集-神經(jīng)網(wǎng)絡(luò)的文本自動分類方法[J].情報(bào)學(xué)報(bào). 2006,25(4) 475-480
[18] 胡清華，謝宗霞，于達(dá)仁. 基于粗糙集加權(quán)的文本分類方法研究[J].情報(bào)學(xué)報(bào)，2005，24(1):59-63.
[19] 苗奪謙，李道國. 粗糙集理論、算法與應(yīng)用[M]. 北京：清華大學(xué)出版社 2008.4.
【基于粗糙集的文本分類研究】相關(guān)文章：
基于分形維數(shù)的圖像分類研究03-07
基于BP網(wǎng)遙感影像分類研究與應(yīng)用02-25
基于BP神經(jīng)網(wǎng)絡(luò)的遙感影像分類方法研究03-07
基于Web服務(wù)的集成研究03-08
基于ＡＨＰ的企業(yè)外包研究03-22
基于ＳＮＭＰ的拓?fù)浒l(fā)現(xiàn)的研究03-03
基于內(nèi)容的圖像檢索研究11-20