基于粗糙集與ＫＮＮ的Ｗｅｂ文本分類的研究

桂海霞　孟祥瑞

（安徽理工大學經濟與管理學院，安徽 淮南 232001）

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

關鍵詞：Web文本分類；粗糙集；KNN；屬性約簡

中圖分類號：TP399

文獻標識碼：A

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

收稿日期：2008-06-30

作者簡介：桂海霞(1978-),女,安徽桐城人,講師，碩士，研究方向 為系統工程。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 的日益發展和網上各類信息的迅猛增長，用戶對散布在網絡各處的文檔的檢索工作變得愈加 困難，這就對Web文檔分類系統的研究與實現提出了更高的要求。Web文本自動分類通常指將 一篇文章指定至一個或幾個預定義的文本類別中?，F有的文本分類方法主要有支持向量機(S VM )、K最近鄰(KNN)、決策樹、線性最小二乘法估計(LLSF)和貝葉斯分類算法(Bayes)等。 不難發現在這些分類方法中普遍存在一個共同的問題：這些分類方法在訓練和分類過程中， 不能很好的處理高維數據，過多和煩雜的計算量大大限制了分類方法的分類效率的提高。而 目前，在信息處理和文本分類領域得到廣泛應用的粗糙集理論可以很好的解決這個問題。粗 糙集的約簡理論能夠大大縮減文本分類過程中的向量維數，從而降低了計算復雜度，提高了 分類效率。本文將介紹一種基于粗糙集和KNN混合的Web文本分類方法，并在實驗的基礎上驗 證了該混合方法的可行性，取得滿意的效果。

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

粗糙集方法可以解決重要的分類問題，去除冗余屬性，進行屬性的約簡，還可以用決策規則 集合的形式表示最重要屬性和特定分類之間的所有重要關系。本文將這一理論應用到文本分 類的訓練階段，用粗糙集的屬性約簡算法實現規則的提取，然后結合KNN分類方法對文本進 行分類。

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

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

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

在K近鄰分類器中，一個重要的參數是K值的選擇，K值選擇過小，不能充分體現待分類文本 的特點，而如果K值選擇過大，則一些和待分類文本實際上并不相似的文本亦被包含進來， 造成噪聲增加而導致分類效果的降低。

1.3 基于粗糙集與KNN的Web文本分類模型KNN分類算法具備簡單易懂并容易實現的優點，但也存在一些問題，需要將所有樣本存入計 算機中，每次決策都要計算識別樣本與全部訓練樣本之間的距離進行比較。尤其是文本訓練 集較大時，計算新文檔時存儲量和計算量都比較大，大大降低了分類算法和分類系統的效率 。

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

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

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

經過上述的除去標記、禁用詞等預處理操作后，就要對文本進行分詞處理。文本分詞主要有 三種方法:基于字符串匹配的方法、基于理解的方法和基于統計的方法。本文中采取了基于 統計的分詞方法，這種分詞方法利用了一種基于統計學的 N-Gram技術［3］，根據相 鄰字的共現頻率自動提取特征，使文本數據分類實現了分類的領域無關性和時間無關性。它 無需任何詞典支持，對輸入文本所需的先驗知識少。

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

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

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

特征提取具體步驟如下：

Stepl:對于特征項集合中的每個詞，計算詞和類別的互信息量使用上述公式。

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

Step3:抽取一定數量(K個)的詞作為特征項，K值的具體值一般先采用初始值，然后可以根據 實驗和統計結果確定最佳值。

Step4:將每類中的所有的訓練文本，根據抽取的特征項，表示成向量形式。

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

表1 決策表

文本特

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

(4) 屬性約簡算法 屬性約簡是粗糙集理論研究的一個核心內容，它通過從屬性集合中發現 部分必要的屬性，使得這部分屬性相對于所有屬性有相同的分類能力。由Skowron A提出的 分明矩陣［5］可將求屬性約簡的問題轉變為由合取范式到析取范式轉化的問題，其 主要思想是利用邏輯運算使得約簡后的屬性集與每個非空的分明矩陣元素相交都不為空，從 而所有對象兩兩之間都有可以相互區分的屬性。如果一個矩陣元素只包含單個屬性，則稱該 屬性為核屬性，它唯一能區分這個矩陣元素所對應的兩個對象。核屬性是不可約去的，可作 為最佳屬性約簡的起點，其它有用屬性需從不含核屬性的矩陣元素中得出。本文中的屬性約 簡算法就是基于分明矩陣進行屬性約簡的，同時結合具體研究問題，具體算法步驟描述如下 ：

Step1:對于訓練文本集和測試文本集合中的每一個文本，計算其相應的分明矩陣M ；

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

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

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

可以看出，這種約簡方法是根據論域中對象的屬性取值來得到的，不依賴于人們的任何先驗 知識，因此它更具有客觀性。

2 實驗測試與分析

實驗數據來源于從新浪網站上選取的300篇文檔，手工分為數碼、手機、房產、政治、財經5 個類別。我們將其中的240篇文檔構成訓練文檔集合，另外的60篇作為測試文本集合。采用 通用的召回率和準確率對系統性能進行測試，其中召回率是被判定為相關的相關文本占全部 相關文本的比率；準確率是被判定為相關的文本中真正相關的文本所占的比率。準確率和召 回率反映了分類質量的兩個不同方面，兩者必須綜合考慮，不可偏廢，所以還使用兩者綜合 考慮的評估指標：獸1測試值,其數學公式為

獸1指數=準確率×召回率×2準確率+召回率

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

表2 實驗數據表

分類方法分類質量數碼手機房產政治財經KNN法準確率（玃）0.9150.9260.9180.7460.917召回率(玆)0.8700.8420.9630.7560.885獸1測試值0.8920.8820.9400.7510.901粗糙集與

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

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

3 結束語

本文提出了一種基于粗糙集和KNN的混合文本分類模型，對每個關鍵步驟進行了詳細的介紹 ，其中，分詞部分使用了基于統計的分詞方法；特征提取部分采用了互信息量計算方法，給 出了具體的算法步驟；在決策表的屬性約簡步驟中，提出了一種基于分明矩陣的屬性約簡算 法；最后我們對該混合算法進行了實驗，并結合傳統的KNN方法對混合算法進行了比較。實 驗證明，基于粗糙集和KNN 的混合分類方法是一種性能比較優秀的分類方法，能夠明顯提高 分類的準確率和召回率，很好地滿足了大量的專業網站的 Web知識發現的需求，具有應用可 行性。

參考文獻：

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

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

［3］ 胡運發.基于N-Gram 信息的中文文檔分類研究［J］.中文信息學報，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］ 徐風亞,羅振聲.文本自動分類中特 征權重算法的改進研究［J］.計算機工程與應用,2005,41(1):75-77.

(責任編輯：李 麗)