一种改进的KNN Web文本分类方法.doc
《一种改进的KNN Web文本分类方法.doc》由会员分享,可在线阅读,更多相关《一种改进的KNN Web文本分类方法.doc(11页珍藏版)》请在三一文库上搜索。
1、一种改进的文本分类方法?丶?词:Web文本分类; K最近邻; 快速分类 Improved KNN Web text classification method WU Chun-ying, WANG Shi-tong (School of Information Engineering, Jiangnan University, Wuxi Jiangsu 214122, China) Abstract:KNN method not only has large computational demands, because it must compute the similarity betwee
2、n unlabeled text and all training texts; but also may decrease the precision of classification because of the commonness of classes. This paper presented an improved KNN method, which solved two problems mentioned above. It firstly got the most k0 classes fast by Rocchio method, and then used KNN ar
3、ithmetic in some representative training texts of theclasses, at last assigned class by an improved similar arithmetic in KNN. The result of research indicates that the impact of the new method is better. Key words:Web text classification; KNN(K-nearest neighbor); fast classification ? 随着网络信息技术的高速发展
4、和高速通信基础设施的建设,Internet上的Web页面数量呈指数增长。如何有效地组织和处理这些海量信息,如何更好地搜索、过滤和管理这些网络资源,Web文本分类成了关键技术。目前关于这方面的研究已经取了很大的进步,并取得了一系列的分类方法,其中比较著名的文本分类方法有Rocchio、支持向量机(SVM)、K最近邻(KNN)、神经网络和贝叶斯(Bayes)算法等1。在这些方法中,KNN是一种简单、有效、非参数的方法,目前应用比较广泛。 为了使KNN方法更实用,不少学者对KNN方法进行了进一步研究,王煜等人2提出了一种快速KNN算法,通过建立索引表来快速找到k个最近邻,但没有提高分类精度;李杨等人
5、3提出了排类和归类算法在不影响原有精度下提高分类速度;李荣陆等人4针对不均匀训练样本,提出了基于密度的裁剪方法,取得了较好的分类效果。本文提出一种改进KNN文本分类方法,目的是为了减少样本间相似度的计算量,克服KNN分类搜索空间巨大的问题,同时又能一定程度地改善分类效果。 1传统的KNN文本分类方法 11文本表示方法 向量空间模型(vector space model,VSM)5是由Salton于1968 年提出的,是近年来文本表示应用较多且效果较好的方法之一。该模型涉及到以下三个基本概念: a)文档(document)。泛指一般的文本或文本中的片断,一般指一篇文章。 b)项(term)。文本
6、中的内容特征常用切分后的词来表示,称为文本的项,即文本可用项集(term list),表示为D(t1,t2,,tn)。其中:tk是项。 c)项的权重(term weight)。对于含有N项的文本,不同的项tk,其区分文本的能力不同,故tk常被赋予不同的权重wk(d),表示它们在文本中的重要程度。常用的有布尔函数、平方根函数、对数函数、TF-IDF 函数6等。其中TF-IDF 在文本检索和机器学习中被频繁使用。目前存在多种TF-IDF公式,比较普遍的TF-IDF公式如下: W(t,d)=tf(t,d)log(N/nt+0.01)/dtf(t,d)log (N/nt+0.01)2(1) 其中:w(
7、t,d)为词t在文本d中的权重;tf(t,d)为词t在文本d中出现的词频(绝对词频即使用词在文本d中出现的频次;相对词频即为归一化的词频);N为训练文本的总数;nt为训练文本集中出现词t的文本数,分母为归一化因子。这样,Web文本d可表示为向量空间模型为 V(d)=(t1,w1(d);t2,w2(d);tn,wn(d)(2) 12KNN分类算法 KNN算法是一种简单、有效、非参数的文本分类方法;其本质是一种预测性的监督分类算法,不需要额外的数据来描述规则,它的规则本身就是数据样本;它并不要求数据的一致性,即可以存在噪声;KNN根据待分类样本的k个最近邻样本来预测未知样本的类别。因此,KNN算法
8、必须明确两个基本因素:最近邻样本的数目k和测量相似性的距离函数。距离函数是一个非负函数,用来刻画不同样本的相似程度。常用的有欧氏距离、曼哈顿距离、余弦夹角等。本文采用余弦夹角公式7,如下: sim(di,dj)=(di?dj)/(didj)=(nk=0wikwjk)/(nk=0wik2nk=0wjk2)(3) 其中:sim(di,dj)表示文本di和文本dj的相似度;wik表示文本di中第k个特征的权重。 在分类时,首先将待分类文本D转换与训练样本一致的向量空间模型;然后计算D与每个样本的相似度,计算见式(3);再取相似度最大的K个样本,根据K个样本计算属于每个类别的权重,计算见式(4)2 ;
9、最后文本D属于权重最大的那个类别。 p(D,Cj)=ki=0sim (di,D)Pd(di,Cj) (4) 其中:sim(di,D)表示文本D的K个最近文本di与文本D间的相似度。 Pd(di,Cj)=1di属于类别Cj样本0di不属于类别Cj样本 (5) 2改进的KNN分类算法 在传统的KNN分类中,要求计算待测文本与所有训练样本间的相似度,时间上难以满足实际分类需求。因此本文提出了一种改进的KNN分类算法。它的主要思想是:先通过Rocchio分类快速得到k0个最有可能的候选类别;然后在k0个类中心区域采用KNN算法;最后结合Rocchio分类结果,由一种改进的相似度计算方法决定最终的文本所
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一种 改进 KNN Web 文本 分类 方法
链接地址:https://www.31doc.com/p-1592167.html