20期苟和平,等:一种基于粗糙集的改进KNN文本分类算法4927
Ck)=δ(dj,
{
1,dj∈Ck0,djCk。
定义3
RX={x∈U|[x]R∩X≠}。它们分别为X的R下近似集和R上近似集。
R),给定一个知识库K=(U,对于每个子
集XU和一个等价关系R∈ind(K),全集U可以划分为3个不相交的区域,即正域(posR)、负域(negR)和边界(bndR)。
posR=RX;negR=U-RX;bndR=RX-RX。
其中,正域(posR)表示那些根据知识R判断肯定属于X的U中元素组成的集合;负域(negR)是那些根据知识R判断肯定不属于X的U中元素组成的集合;边界(bndR)是那些根据知识R既不能判断X的U中元素肯定属于X又不能判断肯定属于U-组成的集合。
(6)比较各类的权重,将待分类文本ti归入权重最大的类别。
KNN作为一种有监督机器学习的非参数方法,分类器在文本分类方面简单高效。但该算法的主要缺点是在分类时需要计算待分类文本di与所有训练文本之间的距离,时间复杂度与训练文本数量、维数成正比,与大量的训练文本进行相似度的计算,计算开销大。因此,在大样本集或者是高维样本集下,分类效率会降低
[5]
。针对这个问题,目
前改进方法有:①采用抽样方法提取代表样本来实现样本集的缩减,主要有采用的方法有聚类和文本过滤
[6]
,这类方法对于有成百上千的训练样本来
说,其工作量是非常巨大的,并且样本集的缩减将会影响分类的准确性;②采用降低文本向量维数来主要的方法是采用向量投影和iDis-提高检索速度,
tance索引[7]及特征集约简[8]。
本文主要针对大样本集所带来的KNN算法计算开销大的问题,提出了一种基于粗糙集的KNN算法,主要是针对上述第一类改进方法中的不足,旨在不缩减样本集的情况下减少分类过程中待分类文本与训练文本之间的比较次数,以减少向量之间的相似度计算。
3基于粗糙集的改进KNN文本分类算法
本文提出一种基于粗糙集的改进KNN分类算
KNN,在传统KNN算法的基础上,为解决由法RS-于大样本集而带来计算开销大的问题,利用粗糙集定义各个样本子空间的上、下近似来的相关理论,
缩减样本搜索空间,减少分类时的计算量,进而提高系统的分类速度。定义4
给定一个训练文本集合S,第i个子集
→
Si(i=1,2,...n),其类中心Ci定义如下:
→
Ci=
→1
d∑|Si|d∈Si
(3)
2粗糙集相关概念
设U≠是一个对象组成的有限集合,称
定义1
R是U上的一个等价关系,U/R表示R的为论域,
[x]所有等价类构成的集合,R表示包含元素x∈U的R等价类。一个知识库就是一个关系系统K=(U,R),R是U上的一簇等价关系。定义2
若PR,且P≠,则∩P(P中所有等
价关系的交集)也是一个等价关系,称为P上的不可区分(indiscernibility)关系,记为ind(P)。
R),定义ind(K)为给定一个知识库K=(U,
K中所有等价关系的簇,记为ind(K)={ind(P)|≠PR}。对于每个子集XU和一个等价关系R∈ind(K),定义两个子集:
RX={x∈U|[x]RX};
式(3)中|Si|表示子集Si中的文本个数。给定一个训练文本集合S,第i个子集Si的类
→→→
dist(d,Ci)是文本向量d与Ci的距离,r中心为Ci,→
是以Ci为中心的向量空间的半径,则有
→
Ci)≤rl(Si)}:下近似:R(Si)={d∈Si|dist(d,
表示存在最大子集,使得分布于其中的所有向量d只属于一个类Si。
→
Ci)≤ru(Si)}:上近似:R(Si)={d∈S|dist(d,
表示存在最小子集,使得Si中的所有向量d都分布负域和边界可定义为于其中。其Si的正域、
posR(Si)=R(Si);negR(Si)=S-R(Si)};
一种基于粗糙集的改进KNN文本分类算法_专业资料。K最近邻算法(KNN)被认为是向量空间模型下最好的分类算法之一。在准确率和召回率方面比较出众,但随着样本数量的增加...
基于粗糙集与改进KNN算法的文本分类方法的研究_专业资料。KNN算法是文本自动分类领域中的一种常用算法,对于低维度的文本分类,其分类准确率较高。然而在处理大量高维度...
2012 年第 2 期 2475 ( 2012 ) 02008604 文章编号: 1006- 计算机与现代化 JISUANJI YU XIANDAIHUA 总第 198 期 基于 粗糙 集与改进 KNN 算法的文本分类方法...
(2010)24—0175—03 文献标识码:A 2010 年 12 月 December 2010 中图分类号:TP391 ·人工智能及识别技术· 基于粗糙集的快速 KNN 文本分类算法孙荣宗 a,b,...
基于粗糙集理论的KNN分类_专业资料。粗糙集理论为研究不精确数据的分析、推理,挖掘数据间的关系、发现潜在的知识提供了有效的工具。在数据挖掘技术中KNN算法是一个实...
KNN ( K 最近邻算法) 在文本处理环境下的不足 , 根 据 SOM ( 自组织映射神经网络) 理论 、特征选取和模式聚合理论, 提出了一种改进的 KNN 文本 分类方法...
基于KNN算法的文本分类_计算机软件及应用_IT/计算机_专业资料。基于KN N算法的文本分类刘科(江西省儿童医院,江西南昌330006)摘要:本文介绍了数据挖掘‘11的一个分枝...
基于粗糙集与KNN的Web文本分类的研究_专业资料。为了从海量的信息资源库中快速、...混合算法进行了实验,同时结合传统的KNN方法对该混合算法进行比较,验证该算法的...
结合粗糙集的属性约简和RBF神经网络的分类机理,提出一种新的文本分类混合算法。试验结果表明,与朴素贝叶斯、SVM、kNN传统分类方法相比,该方法在保持分类精度的基础上,...
基于粗糙集与改进KNN算法... 暂无评价 4页 免费 一种新的基于SVM_KNN的W.....d e u . en ) 摘 , 要 自动文本分类技术是 一 种对电 子 文档进 行...
热门文档