文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 互联网 > 一种基于粗糙集的改进KNN文本分类算法_苟和平
侵权投诉

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

20期苟和平,等:一种基于粗糙集的改进KNN文本分类算法4927

Ck)=δ(dj,

{

1,dj∈Ck0,djCk。

定义3

RX={x∈U|[x]R∩X≠}。它们分别为X的R下近似集和R上近似集。

R),给定一个知识库K=(U,对于每个子

集XU和一个等价关系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

若PR,且P≠,则∩P(P中所有等

价关系的交集)也是一个等价关系,称为P上的不可区分(indiscernibility)关系,记为ind(P)。

R),定义ind(K)为给定一个知识库K=(U,

K中所有等价关系的簇,记为ind(K)={ind(P)|≠PR}。对于每个子集XU和一个等价关系R∈ind(K),定义两个子集:

RX={x∈U|[x]RX};

式(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)};

上一页第2页

你可能喜欢

  • 文本分类论文
  • 力和运动分类
  • 文本聚类
  • 文献的类型
  • 平面镜成像实验创新改进论文

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email