桂海霞　孟祥瑞

（安徽理工大學(xué)經(jīng)濟(jì)與管理學(xué)院，安徽 淮南 232001）

摘 要：為了從海量的信息資源庫(kù)中快速、準(zhǔn)確地進(jìn)行分類并提 取出有用的信息，提出了一種基于粗糙集和KNN混合的Web文本分類模型。利用粗糙集的屬性 約簡(jiǎn)理論降低了文本分類過程中的向量維數(shù)，使用一種基于分明矩陣的屬性約簡(jiǎn)算法，特征 選擇過程采用互信息量計(jì)算方法，并對(duì)該混合算法進(jìn)行了實(shí)驗(yàn)，同時(shí)結(jié)合傳統(tǒng)的KNN方法對(duì) 該混合算法進(jìn)行比較，驗(yàn)證該算法的可行性。

關(guān)鍵詞：Web文本分類；粗糙集；KNN；屬性約簡(jiǎn)

中圖分類號(hào)：TP399

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1672-1098(2008)04-0089-04

收稿日期：2008-06-30

作者簡(jiǎn)介：桂海霞(1978-),女,安徽桐城人,講師，碩士，研究方向 為系統(tǒng)工程。Research of Web Text Classification Based on Rough Set and KNN

GUI Hai-xia,MENG Xiang-rui

(School of Economics and Management, Anhui University of Scienc e and Technology, Huainan Anhui 232001,China)

Abstract: In order to quickly and precisely classify and search u seful information from huge information database, in the paper a kind of mixed m odel of web text classification based on rough set and KNN was introduced. By us ing the theory of attributes reduction of rough set, number of vector dimensions

in text classification process was reduced. A kind of simplified algorithm for

attributes reduction based on distinct matrix was used. In the process of featur e selection, method of mutual information was used. Experiments with the mixed m odel were conducted. The results compared with traditional KNN method show that

the mixed algorithm is feasible.

Key words:web text classification；rough set； K nearest ne ig hbor； attributes reduction

目前，隨著Internet 的日益發(fā)展和網(wǎng)上各類信息的迅猛增長(zhǎng)，用戶對(duì)散布在網(wǎng)絡(luò)各處的文檔的檢索工作變得愈加 困難，這就對(duì)Web文檔分類系統(tǒng)的研究與實(shí)現(xiàn)提出了更高的要求。Web文本自動(dòng)分類通常指將 一篇文章指定至一個(gè)或幾個(gè)預(yù)定義的文本類別中?，F(xiàn)有的文本分類方法主要有支持向量機(jī)(S VM )、K最近鄰(KNN)、決策樹、線性最小二乘法估計(jì)(LLSF)和貝葉斯分類算法(Bayes)等。 不難發(fā)現(xiàn)在這些分類方法中普遍存在一個(gè)共同的問題：這些分類方法在訓(xùn)練和分類過程中， 不能很好的處理高維數(shù)據(jù)，過多和煩雜的計(jì)算量大大限制了分類方法的分類效率的提高。而 目前，在信息處理和文本分類領(lǐng)域得到廣泛應(yīng)用的粗糙集理論可以很好的解決這個(gè)問題。粗 糙集的約簡(jiǎn)理論能夠大大縮減文本分類過程中的向量維數(shù)，從而降低了計(jì)算復(fù)雜度，提高了 分類效率。本文將介紹一種基于粗糙集和KNN混合的Web文本分類方法，并在實(shí)驗(yàn)的基礎(chǔ)上驗(yàn) 證了該混合方法的可行性，取得滿意的效果。

1 粗糙集與KNN的Web文本分類法1.1 粗糙集概述ゴ植詡是用來研究不完整數(shù)據(jù)、不精確知識(shí)的表達(dá)、學(xué)習(xí)、歸納等方法。粗糙集［1］ 理論的研究對(duì)象是一個(gè)由多值屬性集合描述的對(duì)象集合——信息系統(tǒng)。對(duì)于每個(gè)對(duì)象及其 屬性都有一個(gè)值作為其描述符號(hào)，對(duì)象、屬性和描述符是表達(dá)決策問題的三個(gè)基本要素：這 種表達(dá)形式可以看成是一個(gè)二維表格，表格的行與對(duì)象相對(duì)應(yīng)，列與對(duì)象的屬性相對(duì)應(yīng)。各 行包含了表示相應(yīng)對(duì)象信息的描述符，還有關(guān)于各個(gè)對(duì)象的類別成員的信息。通常，關(guān)于對(duì) 象的可得到的信息不一定足以劃分其成員類別，這種不精確性導(dǎo)致了對(duì)象間的不可分辨性。 在粗糙集理論中用等價(jià)類形成的上近似和下近似來描述集合的粗糙性。上近似和下近似的差 是一個(gè)邊界集合，它包含了所有不能確切地判定是否屬于給定類的對(duì)象。粗糙集理論的主要 特點(diǎn)在于它恰好反映了人們以不完全的信息或知識(shí)去處理一些不分明現(xiàn)象的常規(guī)性，依據(jù)觀 察、度量到的某些不精確的結(jié)果而進(jìn)行分類數(shù)據(jù)的能力。

粗糙集方法可以解決重要的分類問題，去除冗余屬性，進(jìn)行屬性的約簡(jiǎn)，還可以用決策規(guī)則 集合的形式表示最重要屬性和特定分類之間的所有重要關(guān)系。本文將這一理論應(yīng)用到文本分 類的訓(xùn)練階段，用粗糙集的屬性約簡(jiǎn)算法實(shí)現(xiàn)規(guī)則的提取，然后結(jié)合KNN分類方法對(duì)文本進(jìn) 行分類。

1.2 KNN分類算法簡(jiǎn)介プ畛醯慕鄰法是由Cover和Hart于1968年提出的，直至現(xiàn)在仍是分類方法中最重要的方法之 一。直觀地理解，K近鄰，就是考察和待分類文本最相似的K篇文本，根據(jù)這K篇文本的類別 來判斷待分類文本的類別值。相似值的判斷可以使用歐拉距離，或是余弦相似度等。而最相 似的K篇文本按其和待分類文本的相似度高低對(duì)類別值予以加權(quán)平均，從而預(yù)測(cè)待分類文本 的類別值。在新文本的K個(gè)鄰居中，依次計(jì)算每類的權(quán)重，計(jì)算公式如下

p(﹛璱[TX-],C璲)=∑[DD(X]d璱∈KNN[DD)]玸im (x[TX-],d璱)y(k璱,C璲)

式中：玿[TX-]為新文本的特征向量，玸im (x[TX-],d璱)為相似度計(jì)算公式，而y(d 璱 ,C璲)為類別屬性函數(shù)，如果特征屬于類C璲，那么函數(shù)值為l，否則為0。比較類的權(quán)重 ，將文本分到權(quán)重最大的那個(gè)類別中。

在K近鄰分類器中，一個(gè)重要的參數(shù)是K值的選擇，K值選擇過小，不能充分體現(xiàn)待分類文本 的特點(diǎn)，而如果K值選擇過大，則一些和待分類文本實(shí)際上并不相似的文本亦被包含進(jìn)來， 造成噪聲增加而導(dǎo)致分類效果的降低。

1.3 基于粗糙集與KNN的Web文本分類模型KNN分類算法具備簡(jiǎn)單易懂并容易實(shí)現(xiàn)的優(yōu)點(diǎn)，但也存在一些問題，需要將所有樣本存入計(jì) 算機(jī)中，每次決策都要計(jì)算識(shí)別樣本與全部訓(xùn)練樣本之間的距離進(jìn)行比較。尤其是文本訓(xùn)練 集較大時(shí)，計(jì)算新文檔時(shí)存儲(chǔ)量和計(jì)算量都比較大，大大降低了分類算法和分類系統(tǒng)的效率 。

鑒于粗糙集的約簡(jiǎn)理論能夠可以有效的去掉信息系統(tǒng)中的冗余屬性，大大縮減文本分類過程 中的向量維數(shù)，降低了計(jì)算復(fù)雜度，同時(shí)又不影響分類區(qū)分能力，從而提高了分類效率。本 文利用粗糙集的上述優(yōu)點(diǎn)并結(jié)合KNN分類方法，提出了一種混合的Web文本分類模型［2 ］，其分類過程和結(jié)構(gòu)如圖1所示。[FL)]圖1 基于粗糙集和KNN的混合分類模型

圖1給出了基于粗糙集和KNN進(jìn)行文本分類模型。整個(gè)建立模型的過程由基于粗糙集的預(yù)處理 和KNN分類兩部分組成。經(jīng)過特征選擇和權(quán)重的離散化，就可以構(gòu)造決策表，把粗糙集作為 預(yù)處理，對(duì)決策表進(jìn)行屬性約簡(jiǎn)，這種約簡(jiǎn)把冗余的屬性從決策表中刪去并且不損失任何有 效信息。然后該算法從前端轉(zhuǎn)向后端處理，即從粗糙集轉(zhuǎn)向KNN方法的訓(xùn)練與測(cè)試。分類模 型中粗糙集作為KNN方法的一個(gè)前端處理器，經(jīng)過粗糙集的屬性約簡(jiǎn)和沖突約簡(jiǎn)，進(jìn)入KNN的 輸入量會(huì)大大減小，這樣相應(yīng)減小了KNN分類過程中的計(jì)算量，節(jié)省了訓(xùn)練時(shí)間，并在不同 程度上避免了訓(xùn)練模型的過擬合現(xiàn)象，但分類性能并不會(huì)降低。

1.4 基于粗糙集與KNN的Web文本分類過程(1) 文本預(yù)處理和分詞 Internet上的大部分網(wǎng)頁是HTML文檔或XML文檔，文本的預(yù)處理首 先要做的是，利用網(wǎng)頁信息抽取模塊將網(wǎng)頁的內(nèi)容，去掉跟文本挖掘無關(guān)的標(biāo)記，例如HTML 中的Tag，去除禁用詞、詞根還原等，然后轉(zhuǎn)換成統(tǒng)一格式的TXT文本存放在文件夾中以備后 續(xù)處理。

經(jīng)過上述的除去標(biāo)記、禁用詞等預(yù)處理操作后，就要對(duì)文本進(jìn)行分詞處理。文本分詞主要有 三種方法:基于字符串匹配的方法、基于理解的方法和基于統(tǒng)計(jì)的方法。本文中采取了基于 統(tǒng)計(jì)的分詞方法，這種分詞方法利用了一種基于統(tǒng)計(jì)學(xué)的 N-Gram技術(shù)［3］，根據(jù)相 鄰字的共現(xiàn)頻率自動(dòng)提取特征，使文本數(shù)據(jù)分類實(shí)現(xiàn)了分類的領(lǐng)域無關(guān)性和時(shí)間無關(guān)性。它 無需任何詞典支持，對(duì)輸入文本所需的先驗(yàn)知識(shí)少。

(2) 特征提取和權(quán)值離散化 訓(xùn)練文本和待分類文本經(jīng)過分詞并去除停用詞和高頻詞后，表 示文本的向量空間和類別向量的維數(shù)也是相當(dāng)大的，因此需要進(jìn)行特征項(xiàng)的抽取。 特征提?。?］是文本分類系統(tǒng)中十分關(guān)鍵的問題，它可降低向量空間的維數(shù)，提高 系統(tǒng)的速度和精度，還可以防止過擬合。由于本文中采用了向量空間模型作為文本的表示方 式，因此特征提取方法就相應(yīng)的采用了統(tǒng)計(jì)的方法，首先利用不同的方法對(duì)特征項(xiàng)進(jìn)行評(píng)分 。對(duì)于待分類文本來說就是計(jì)算權(quán)重，通過一定的方法計(jì)算出權(quán)重然后選出分值較高的作為 特征構(gòu)成文本的向量空間。常用的特征提取方法有：互信息、信息增益、期望交叉熵和文本 證據(jù)權(quán)等等，本文中采用了是互信息特征提取方法?；バ畔⑹墙y(tǒng)計(jì)學(xué)和信息論中一個(gè)重要的 概念，它表現(xiàn)了兩個(gè)統(tǒng)計(jì)量間相互關(guān)聯(lián)的程度，關(guān)聯(lián)程度越高，互信息越大，反之亦然。特 征項(xiàng)與類別的互信息量可以用如下公式計(jì)算

Txt(w)=∑[DD(X]i[DD)]p(c璱)玪og玔SX(]p(w｜c(diǎn)璱)[]p(c璱)[SX)]

式中：玴(w｜c(diǎn)璱)為訓(xùn)練語料中特征項(xiàng)w出現(xiàn)在類別c璱中的頻率，p(c璱)為c璱類文 本在語料中出現(xiàn)的頻率。為了避免特征項(xiàng)過多造成系統(tǒng)的過擬合現(xiàn)象，計(jì)算出所 有特征項(xiàng)的互信息量后，我們要將互信息量從大到小排序，然后選出分值較高的前K個(gè)作為 特征構(gòu)成特征向量空間。

特征提取具體步驟如下：

Stepl:對(duì)于特征項(xiàng)集合中的每個(gè)詞，計(jì)算詞和類別的互信息量使用上述公式。

Step2:對(duì)于該類中所有的詞，依據(jù)計(jì)算出來的互信息量排序。

Step3:抽取一定數(shù)量(K個(gè))的詞作為特征項(xiàng)，K值的具體值一般先采用初始值，然后可以根據(jù) 實(shí)驗(yàn)和統(tǒng)計(jì)結(jié)果確定最佳值。

Step4:將每類中的所有的訓(xùn)練文本，根據(jù)抽取的特征項(xiàng)，表示成向量形式。

計(jì)算了各個(gè)特征項(xiàng)的權(quán)重并提取了相應(yīng)的特征向量以后，由于本文中要應(yīng)用粗糙集理論，對(duì) 于連續(xù)的數(shù)據(jù)必須先進(jìn)行離散化，也就是將各屬性的取值區(qū)間劃分為若干段，各段以不同的 離散值代表。在保持分類能力的情況下，劃分區(qū)間越少越好。目前相關(guān)文獻(xiàn)提出了很多種離 散化方法，有等距離劃分法、等頻率劃分法和自適應(yīng)離散化法等等，本文中采用了等距離劃 分方法。(3) 構(gòu)造決策表 粗糙集理論中用決策表來描述論域中的對(duì)象。它是一類特殊而重要的信息知識(shí)表達(dá)系統(tǒng)。在 此用決策表來表示分類知識(shí)：每類中的所有文本的集合作為論域，文本作為論域中的對(duì)象， 特征詞的集合作為屬性集，即把特征詞作為屬性，離散化之后的詞語的權(quán)值作為屬性的取值 ，若文檔中沒有某詞，則該詞在文檔中屬性值為0(見表1)。

表1 決策表

文本特

征玊1[]T2[]T3[]…[]T璱[]所屬類別D1[]5[]4[]1[]…[]5[]C1[BHDWG2]D2[]0[]3[]7[]…[]2[]C2[BH]ⅰ璠]ⅰ璠]ⅰ璠]ⅰ璠]ⅰ璠]ⅰ璠]ⅰ璠BH]D璱[]ⅰ璠]ⅰ璠]ⅰ璠]ⅰ璠]ⅰ璠]C璱テ渲歇玊璱表示特征項(xiàng)，C璱是文本D璱的類別表示，表中數(shù)字是離散 化后的特征權(quán)值。

(4) 屬性約簡(jiǎn)算法 屬性約簡(jiǎn)是粗糙集理論研究的一個(gè)核心內(nèi)容，它通過從屬性集合中發(fā)現(xiàn) 部分必要的屬性，使得這部分屬性相對(duì)于所有屬性有相同的分類能力。由Skowron A提出的 分明矩陣［5］可將求屬性約簡(jiǎn)的問題轉(zhuǎn)變?yōu)橛珊先》妒降轿鋈》妒睫D(zhuǎn)化的問題，其 主要思想是利用邏輯運(yùn)算使得約簡(jiǎn)后的屬性集與每個(gè)非空的分明矩陣元素相交都不為空，從 而所有對(duì)象兩兩之間都有可以相互區(qū)分的屬性。如果一個(gè)矩陣元素只包含單個(gè)屬性，則稱該 屬性為核屬性，它唯一能區(qū)分這個(gè)矩陣元素所對(duì)應(yīng)的兩個(gè)對(duì)象。核屬性是不可約去的，可作 為最佳屬性約簡(jiǎn)的起點(diǎn)，其它有用屬性需從不含核屬性的矩陣元素中得出。本文中的屬性約 簡(jiǎn)算法就是基于分明矩陣進(jìn)行屬性約簡(jiǎn)的，同時(shí)結(jié)合具體研究問題，具體算法步驟描述如下 ：

Step1:對(duì)于訓(xùn)練文本集和測(cè)試文本集合中的每一個(gè)文本，計(jì)算其相應(yīng)的分明矩陣M ；

Step2:對(duì)于所有獵ij=1的矩陣元素，將其所包含的屬性組成核屬性集合獵0 ；

Step3:將所有不含核屬性的非空矩陣元素獵ij (矩陣元素Cij是屬性的析取 式)建立合取表達(dá)式，即L=∧[DD(X]Cij≠ⅵ,c0∩cij=ⅵ誟DD)]cijВ

Step4:將此合取式L轉(zhuǎn)化為析取式:L′=∨[DD(X]i[DD)]L璱其中每個(gè)L璱所包含的屬 性與C0б黃鹱槌梢桓鍪糶栽技蚪峁。

可以看出，這種約簡(jiǎn)方法是根據(jù)論域中對(duì)象的屬性取值來得到的，不依賴于人們的任何先驗(yàn) 知識(shí)，因此它更具有客觀性。

2 實(shí)驗(yàn)測(cè)試與分析

實(shí)驗(yàn)數(shù)據(jù)來源于從新浪網(wǎng)站上選取的300篇文檔，手工分為數(shù)碼、手機(jī)、房產(chǎn)、政治、財(cái)經(jīng)5 個(gè)類別。我們將其中的240篇文檔構(gòu)成訓(xùn)練文檔集合，另外的60篇作為測(cè)試文本集合。采用 通用的召回率和準(zhǔn)確率對(duì)系統(tǒng)性能進(jìn)行測(cè)試，其中召回率是被判定為相關(guān)的相關(guān)文本占全部 相關(guān)文本的比率；準(zhǔn)確率是被判定為相關(guān)的文本中真正相關(guān)的文本所占的比率。準(zhǔn)確率和召 回率反映了分類質(zhì)量的兩個(gè)不同方面，兩者必須綜合考慮，不可偏廢，所以還使用兩者綜合 考慮的評(píng)估指標(biāo)：獸1測(cè)試值,其數(shù)學(xué)公式為

獸1指數(shù)=準(zhǔn)確率×召回率×2準(zhǔn)確率+召回率

同時(shí)為了跟其他分類方法之間進(jìn)行比較，本文還選用了KNN文本分類法一同進(jìn)行分類實(shí)驗(yàn)， 通過實(shí)驗(yàn)得到了如下數(shù)據(jù)(見表2)。

表2 實(shí)驗(yàn)數(shù)據(jù)表

分類方法分類質(zhì)量數(shù)碼手機(jī)房產(chǎn)政治財(cái)經(jīng)KNN法準(zhǔn)確率（玃）0.9150.9260.9180.7460.917召回率(玆)0.8700.8420.9630.7560.885獸1測(cè)試值0.8920.8820.9400.7510.901粗糙集與

KNN 混合法準(zhǔn)確率(玃)[]0.923[]0.936[]0.925[]0.755[]0.931[BH]召回率(玆)[]0.895[]0.851[]0.970[]0.778[]0.912獸1測(cè)試值0.9080.8910.9470.7660.921

從表2可以看出，與傳統(tǒng)的KNN分類法的結(jié)果比較可得，基于粗糙集和KNN的混合分類方法的 準(zhǔn)確率和召回率明顯得到提高。

3 結(jié)束語

本文提出了一種基于粗糙集和KNN的混合文本分類模型，對(duì)每個(gè)關(guān)鍵步驟進(jìn)行了詳細(xì)的介紹 ，其中，分詞部分使用了基于統(tǒng)計(jì)的分詞方法；特征提取部分采用了互信息量計(jì)算方法，給 出了具體的算法步驟；在決策表的屬性約簡(jiǎn)步驟中，提出了一種基于分明矩陣的屬性約簡(jiǎn)算 法；最后我們對(duì)該混合算法進(jìn)行了實(shí)驗(yàn)，并結(jié)合傳統(tǒng)的KNN方法對(duì)混合算法進(jìn)行了比較。實(shí) 驗(yàn)證明，基于粗糙集和KNN 的混合分類方法是一種性能比較優(yōu)秀的分類方法，能夠明顯提高 分類的準(zhǔn)確率和召回率，很好地滿足了大量的專業(yè)網(wǎng)站的 Web知識(shí)發(fā)現(xiàn)的需求，具有應(yīng)用可 行性。

參考文獻(xiàn)：

［1］ 李波,李新軍.一種基于粗糙集和支持向量機(jī)的混合分類算法［J］.計(jì)算機(jī)應(yīng) 用,2004,24(3):42-46.

［2］ 孫麗華,張積東,李靜梅.一種改進(jìn)的KNN方法及其在文本分類中的應(yīng) 用［J］.應(yīng)用科技，2005,32(2):25-27.

［3］ 胡運(yùn)發(fā).基于N-Gram 信息的中文文檔分類研究［J］.中文信息學(xué)報(bào)，2007,1 5(1):124-128.

［4］ SUN LI HUA,ZHANG JI DONG,LI JING MEI.An improved k-nearest neighbo r system and its application to Text classification［J］.Applied Science and Te chnology.2002,29(2):25-27.

［5］ 徐風(fēng)亞,羅振聲.文本自動(dòng)分類中特 征權(quán)重算法的改進(jìn)研究［J］.計(jì)算機(jī)工程與應(yīng)用,2005,41(1):75-77.

(責(zé)任編輯：李 麗)