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

桂海霞　孟祥瑞

（安徽理工大学经济与管理学院，安徽 淮南 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文本自动分类通常指将 一篇文章指定至一个或几个预定义的文本类别中。现有的文本分类方法主要有支持向量机(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) 特征提取和权值离散化 训练文本和待分类文本经过分词并去除停用词和高频词后，表 示文本的向量空间和类别向量的维数也是相当大的，因此需要进行特征项的抽取。 特征提取［4］是文本分类系统中十分关键的问题，它可降低向量空间的维数，提高 系统的速度和精度，还可以防止过拟合。由于本文中采用了向量空间模型作为文本的表示方 式，因此特征提取方法就相应的采用了统计的方法，首先利用不同的方法对特征项进行评分 。对于待分类文本来说就是计算权重，通过一定的方法计算出权重然后选出分值较高的作为 特征构成文本的向量空间。常用的特征提取方法有：互信息、信息增益、期望交叉熵和文本 证据权等等，本文中采用了是互信息特征提取方法。互信息是统计学和信息论中一个重要的 概念，它表现了两个统计量间相互关联的程度，关联程度越高，互信息越大，反之亦然。特 征项与类别的互信息量可以用如下公式计算

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.

(责任编辑：李 丽)