一种基于粗糙集的改进KNN文本分类算法_苟和平.pdf

《一种基于粗糙集的改进KNN文本分类算法_苟和平.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第12卷第20期2012年7月科学技术与工程Vol.12No.20Jul．20121671—1815(2012)20-4926-04ScienceTechnologyandEngineering2012Sci.Tech.Engrg.一种基于粗糙集的改进KNN文本分类算法1122苟和平景永霞冯百明李勇12(琼台师范高等专科学校信息技术系，海口571100;西北师范大学数学与信息科学学院，兰州730070)摘要K最近邻算法(KNN)被认为是向量空间模型下最好的分类算法之一。在准确率和召回率方面比较出众，但随着样本数量的增加其相似度计算开销很大。提出一种改进算法RS-

2、KNN，主要是利用粗糙集的相关理论，计算训练样本集中各样本子类的上近似空间和下近似空间，根据待分类文本出现在不同的近似空间。以缩减与待分类样本计算相似度的训练样本个数。实验表明此算法能够有效地降低分类计算开销。关键词K最近邻文本分类粗糙集近似空间中图法分类号TP391．75;文献标志码A随着互联网的普及和信息技术的发展，网络信征集缩减，将文本以特征向量的形式定义到实数域息资源日益丰富，如何从大量的信息资源库中挖掘中;在分类阶段，按与训练阶段同样的方法将待分出有用信息成为研究的热点。作为数据挖掘关键类文本ti表示为特征向量，在训练集中找出与ti最技术之一的文本自动分

3、类技术，是实现文本数据组相似的k个文本，以这k个近邻文本的类别作为候织与检索的有效手段，在提高文本数据利用的有效选类别，将ti与这k个文本的相似度作为k近邻文性和准确性方面具有重要的现实意义和广泛的应本所在类的类别权重，把ti归入到相似度最大的类用前景。别中。KNN算法的具体步骤如下。目前文本分类方法主要包括决策树、K最近邻(1)根据训练文本最终特征集合，将训练文本(KNN)、关联规则、支持向量机(SVM)、贝叶斯算法表示为向量空间中的特征向量;(Bayes)、神经网络、粗糙集等。其中基于向量空(2)将待分类文本ti表示为和训练文本一致的［1］间模型(VSM)的K

4、最近邻(KNN)自动文本分类特征向量di;算法，是一种简单、有效、非参数的方法，在准确(3)计算待分类文本向量di和训练文本向量的率和召回率方面比较出众，是文本分类常用的分相似度，常用向量夹角余弦计算，公式为类器。TdidjS(di，dj)=cos(θ)=(1)1KNN算法的基本思想及存在问题‖di‖‖dj‖式(1)中θ是两个向量di和dj的夹角，‖d‖表示KNN作为一种基于实例的文本分类算法，被认向量长度。为是向量空间模型(VSM)下最好的分类算法之［2］［3，4］(4)选择与di相似度最大的k个文本作为向量一，该算法分为训练和分类两个阶段。其思di的k个最近邻

5、;想是:在文本训练阶段，主要是一般特征的提取、特(5)根据di的k个最近邻，计算文本类别相应2012年4月13日收到教育部科学技术研究重点项目(208148)、的权重，计算公式为k琼台师范高等专科学校项目(qtkz201006)资助p(di，Ck)=∑S(di，dj)δ(dj，Ck)(2)第一作者简介:苟和平(1978—)，男，甘肃庆阳人，讲师，硕士研究j=1生，研究方向:分布式计算、数据挖掘。E-mail:gou_he_ping@式(2)中S(di，dj)表示文本向量di与文本向量dj之163．com。间的相似度;类别属性函数为20期苟和平，等:一种基于粗糙集的

6、改进KNN文本分类算法49271，dj∈CkRX={x∈U

7、［x］R∩X≠}。δ(dj，Ck)={0，djCk。它们分别为X的R下近似集和R上近似集。(6)比较各类的权重，将待分类文本ti归入权定义3给定一个知识库K=(U，R)，对于每个子重最大的类别。集XU和一个等价关系R∈ind(K)，全集U可作为一种有监督机器学习的非参数方法，KNN以划分为3个不相交的区域，即正域(posR)、负域分类器在文本分类方面简单高效。但该算法的主(negR)和边界(bndR)。要缺点是在分类时需要计算待分类文本di与所有posR=RX;训练文本之间的距离，时间复杂度与训练文

8、本数negR=U－RX;量、维数成正比，与大量的训练文本进行相似度的bndR=RX－RX。计算，计算开销大。因此，在大样本集或者是高维其中，正域(posR)表示那些根据知识R判断肯定属［5］样本集下，分类效率会降低。针对这个问题，目于X的U中元素组成的集合;负域(negR)是那些前改进方法有:①采用抽样方法提取代表样本来实根据知识R判断肯定不属于X的U中元素组成的现样本集的缩减，主要有采用的方法有聚类和文本集合;边界(bndR)是那些根据知识R既不能判断［6］过滤，这类方法对于有成百上千的训练样本来肯定属于X又不能判断肯定属于U-X的U中元素说，其工作量是非常巨大

9、的，并且样