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