Sci论文 - 至繁归于至简,Sci论文网。 设为首页|加入收藏
当前位置:首页 > 计算机论文 > 正文

基于样本类别的邻域粗糙集正域计算(附论文PDF版下载)

发布时间:2018-08-11 17:34:11 文章来源:SCI论文网 我要评论














SCI论文(www.scipaper.net):
 
特别说明:理工类、计算机类和医药类等论文在小编发布时可能会因为复杂的科学计算公式,导致文本格式出错,在阅读时较难读懂,阅读体验一般,建议大家可以直接在文章底部翻页到最后一页下载论文PDF版文档进行深度学习和阅读,感谢理解!

彭潇然 1,2,刘遵仁 2,纪   俊 2
PENG Xiaoran1, LIU Zunren2, JI Jun2
1.青岛大学 数据科学与软件工程学院,山东 青岛 266071
2.青岛大学 计算机科学技术学院,山东 青岛 266071
1.College of Data Science and Software Engineering, Qingdao University, Qingdao, Shandong 266071, China
2.College of Computer Science and Technology, Qingdao University, Qingdao, Shandong 266071, China

PENG Xiaoran, LIU Zunren, Ji Jun. A positive region computation of neighborhood rough set based on cat- egory of samples. Computer Engineering and Applications

Abstract:For an attribute reduction algorithm based on the neighborhood rough set, the positive region calculation is the necessary basis of its efficient performance and the uppermost part of its time cost. And the speed of the cal- culation is mainly determined by measure times between samples. In the condition of ensuring the correctness of the calculation, the less the measure times are, the faster the calculation is. In existing positive region calculations, there are usually a large measure times between samples that have the same category. Aimed at this case, this paper firstly proves that the measure between samples that have the same category is meaningless to the positive region calcula- tion in neighborhood rough set. Then according to the proof, a positive region calculation based on category of sam- ples is proposed. Compared with an existing positive region calculation, the experimental result shows that this pro- posed calculation is effective and faster. And this calculation is more suitable for data sets with fewer categories of samples.

Key words:rough set; neighborhood rough set; positive region computation; attribute reduction; category

摘 要:对基于邻域粗糙集的属性约简算法而言,正域计算是保证其有效性的重要依据,也是影响其时间开销的最主要部分。正域计算的速度主要由样本间度量计算的次数决定。在确保正确性的条件下,样本间度量计算的次数越少,则正域计算越快。在现有的正域计算中,通常存在着大量同类别样本间的度量计算。针对这个现象,首先证明在邻域粗糙集的正域计算中,同类别样本间的度量计算对正域计算是无贡献的,然后据此提出了基于样本类别的正域计算。和现有的正域计算相比,实验结果表明,该正域计算有效且更快速。而且,该正域计算更适用于样本类别数较少的数据集。

关键词:粗糙集;邻域粗糙集;正域计算;属性约简;样本类别

基金项目:国家自然科学基金(No.61503208)。
作者简介:彭潇然(1994-),男,研究生,研究领域为粗糙集理论,E-mail: pxr1203@qq.com;刘遵仁(1963-),男,博士,副教授,研究领域为粗糙集理论、数据挖掘、智能计算等;纪俊(1982-),男,博士,副教授,研究领域为数据挖掘、大数据技术、转化医学等。

1 引言

粗糙集理论认为知识是有粒度的,是一种对论 域中对象进行分类的能力。经典的 Pawlak 粗糙集[1] 采用等价划分和等价类的概念保证了粒度计算的 进行,但是这种处理方式只适用于离散型变量,而 现实应用中需要处理的数据类型往往是数值型的, 这种局限滞缓了粗糙集理论的应用。针对这个问题,Zadeh[2]提出了信息粒化和粒度计算的概念。Lin[3]在信息粒化、粒度的基础上提出了邻域模型的概念。Hu[4] 提出了基于邻域粒化和粗糙逼近的决策表属性约简算法。经各方研究后提出的邻域粗糙模型可以处理数值型数据,这大大拓展了粗糙集理论的应用范围[2-7]。

但是,和 Pawlak 粗糙集的正域计算不同,因为引进了邻域粒化的概念,在邻域粗糙集的正域计算中,邻域信息粒子需要通过度量计算来确定,这导致邻域实数空间下的计算量要比经典离散空间下的计算量大得多。正域计算直接影响着基于邻域粗糙集算法的时间开销[8]。

在“信息爆炸”的时代,能有效且快速地对信息进行处理是十分有意义的。作为粗糙集理论的重要应用之一,属性约简一直以来是国内外学者研究的热点[9-18]。其中,基于邻域粗糙集,为了能快速地得到属性约简的结果,Hu[4]提出了基于前向贪心思想的属性约简算法(Fast forward heterogeneous at- tribute  reduction  based on neighborhood  rough sets,F2HARNRS)。通过改进 F2HARNRS 算法的正域计算,Liu[8]随后提出了时间开销更少的快速属性约简算  法  (Fast    hash    attribute    reduction    algorithm,FHARA)。

基于 Hu[4]、Liu[8]的研究,本文针对 F2HARNRS 算法和 FHARA 算法中正域计算的不足,提出了基于样本类别的正域计算,然后在此正域计算的基础上,进一步提出了基于样本类别的快速属性约简算法    (Fast Attribute     Reduction     Algorithm Based on Category,FARABC)。通过和 FHARA[8]算法进行比较,实验证明 FARABC 算法能有效且更快速地得到数据集的属性约简,在最好的情况下,算法的时间开销能缩减 5 倍左右。

2相关概念[4]

2.1邻域粒化
定义 1(度量计算) 给定 n 维实数空间 Rn ,对于空 间 中 的 任 意 两 个 点 xi   xi1 , xi 2  , xin  和xj   xj1, xj 2 ,, xjn  ,定义 d xi , xj  是 Rn 上的一个度
量计算,满足:

 n
d(xi , xj )   xip  xjp
 p1

1
2 2



定义 2(邻域信息粒子) 在实数空间上,定义样本的非空有限集合U

 x1 , x 2   , xn  ,且称U  为论

致邻域实数空间下的计算量要比经典离散空间下

域 。 定 义 U 上 的 样 本 x i

的  - 邻 域 为 

 ( xi )  { x j | x j  U , d ( xi , x j )   } , 其 中   0 。  (xi ) 称作由 x i 生成的 -邻域信息粒子,简称为 x i 的邻域粒子。
2.2邻域决策系统及上下近似
定 义 3( 邻 域 决 策 系 统 ) 定 义 四 元 组NDT  (U , C  D,V , f ) 为邻域决策系统。其中U 是论域; C 是条件属性集; D 是决策属性集,且
C  D  ,C ,D;V 是信息函数 f 的值域。
定义 4(上下近似) 对于一个给定的邻域决策表
NDT  (U , C  D,V , f ) ,D 将U 划分为 N 个等价类: D1 , D2 , ..., DN  ,B C ,定义决策属性集 D 关于 B 的下近似和上近似为:
N
N B D   N B Di ,
i 1
   N     
N B D   N B Di
i 1

其中,
N B Di  { xi |  B ( xi )  Di , xi  U } ,

N B D i  { xi |  B ( xi )  D i   , xi  U }
根据定义 1:
 B ( xi )  { x | d ( B ( xi ), B ( x ))   , x  U }
定 义 决 策 属 性 集 D 关 于 B 的 正 域 为

义 x0  {a  C, a( x0 )  min[a( xi )]} , xi  U 。
分析其正域计算:基于图 1 中的样本分布,如图 2 所示,在对样本 xi  的正域判定中,与 xi  进行度量计算的待选样本是 xi 己身所在扇环及相邻扇环中的样本。设样本均匀分布在样本空间中,则该正域计

   算 的 时 间 复 杂 度 为

O(q  n | U |2 )

, 其 中

P os B ( D )  N B D ,边界域为 BNDB (D)  NBD  NBD , 负域为 NE G B ( D )  U  N B D 。

3基于样本类别的正域计算

根据定义 4 可知,对于 n 维实数样本空间上的论域U 和样本 xi  U ,经典的正域计算包括对样本
xi  的 -邻域计算和对 ( xi )  Di  的判别,而基于样本
类别的正域计算仅依赖样本 xi  的 -邻域计算。其中,
 -邻域计算于依赖 xi 与其它样本间的度量计算。度量计算越少,正域计算越快。
3.1F2HARNRS 和 FHARA 算法的正域计算
在文献[4]中,Hu 给出了 F2HARNRS 算法。分析其正域计算:如图 1 所示,在对样本 xi 的正域判定中,与 xi 进行度量计算的待选样本是U 中的所有样本。算法正域计算的时间复杂度为 O (n | U |2 ) 。这种正域邻域计算是经典的正域计算。

\

在文献[8]中,Liu 提出了比 F2HARNRS 算法更快速的 FHARA 算法。在其正域计算中,提出了一种映射划分策略:首先根据各样本与标准样本间的距离大小给各样本划分等级,然后基于等级将各样本映射到不同的有限集合 B0 , B1,..., Bk 中,其中
B    { x  | x   U , k    d ( x , x  ) /  } x

q  4 /  max d ( xi , x0 ) /   。

\

相较 F2HARNRS 算法,FHARA 算法通过映射划分的策略缩减了样本间度量计算的次数,从而提高了正域计算的计算速度。
需注意到,因为同类别的样本在空间分布上往往相邻,所以在以上算法的正域计算中,存在相当多的同类别样本之间的度量计算。但是,根据本文的分析,这种度量计算对正域计算是无贡献的。
3.2本文的正域计算
针对以上正域计算中存在的现状,提出定理 1。定理 1:在邻域粗糙集的正域计算中,同类别
样本之间的度量计算对正域计算是无贡献的。
证明:由定义  4  可知:对于样本 xi  U ,若
xi  NB Di ,即 xi  PosB (D) ,则其 -邻域B (xi )  Di 。进一步做等价推导: 若 xi  PosB (D) , 则
x j   B ( xi ) ,满足 D ( xi )  D ( x j ) ,即 B ( xi ) 中所有样本均是同一类别。
进 一 步做逆 否 推导: 若 xj B (xi ) ,满足
D ( xi )  D ( x j ) ,即 B ( xi ) 中存在某两个样本不是同一类别,则 xi  PosB (D) 。
由此得出结论: xi 是否属于 PosB (D) ,关键在于


k i i

 i 0

 , 0 是标准样本,定


判断 B ( xi ) 中是否存在某个与 xi  类别不同的样本,即

其与同类别样本之间的度量计算对正域计算是无贡献的。即证。
据此定理 1,改进 1。
改进 1:基于图 1 中的样本分布,如图 3 所示, 在对样本 xi  的正域判定中,与 xi  进行度量计算的待选

所示,在对样本xi 的正域判定中,与xi 进行度量计算的待选样本是 x j  x D ( x )  D ( xi ), xi1  xx1   , x  U  ,若存在 x j 使 d ( xi , x j )   ,则立即判定 xi  PosB (D) ,否则 xi  PosB (D) 。

样 本 是 x j  x | D ( x)  D ( xi ), x  U  , 若 存 在 x j 使

d ( xi , x j )  

成立, 则立即判定 xi  PosB (D) ,否则

xi  PosB (D) 。

\

在改进 1 中,虽然通过样本类别筛除了同类样本,但在其异类样本中仍存在不少可避免计算的样本。采用以下策略作进一步筛除:对于n 维的样本 xi 和 x j ,称某 1 维上的计算为粗略计算, n 维上的计算为精细计算。显然,粗略计算比精细计算具有更少的时间开销,但其不作为正域判定的依据。在进行精细计算之前先作粗略计算,若不满足粗略计算
的条件则直接跳过精细计算,否则再进行精细计算。度量计算 d ( xi , x j ) 是精细计算。
定理 2 : 对于 n 维样本 xi    xi1 , xi 2  , xin   U 和

\

如图 4 虚线部分所示,理论上,若对样本 xi 的每一维均做粗略计算,能进一步筛除需要做精细计算的样本。但需注意到,随着粗略计算次数的增多, 粗略计算筛除样本的效果呈指数递减,其时间开销呈线性接近精细计算。粗略计算毕竟不作为正域判定的依据,若满足粗略计算的条件还需进行精细计算,过于追求筛选效果,反而会增大时间开销。第一次粗略计算的筛除效果是最好的,其时间开销却是最小的。所以我们仅做 1 维上的粗略计算,保证此策略有效性的最大化。

基于改进 2,分析 F2HARNRS 算法和 FHARA 算法:在对样本 xi 的正域判定中,若 xi 与xj 做度量计算,且满足 d ( xi , x j )   ,此时判定 xi  PosB (D) 。在这种情况下,注意到,在对样本 x j 的正域判定中,肯定也有 d ( x j , xi )   成立,即判定 xi  PosB (D) 时可同时

x j   x j1 , x j 2 , , x jn   U
则 xj  (xi ) 。

,若 x ip  x jp

  , p 1,2,...,n ,

判定 x j  PosB (D) 。
根据以上分析,提出本文的基于样本类别的正

证 明 : 根 据 题 设 不 妨 设 x i1  x j 1   , 即

域计算。和经典的正域计算相比,这种正域计算不

xi1  x


j1

2   2
 n

, 且 xip  xjp
1


2 2

2  0 ,

p  2,3,..., n , 则

d ( x , x )  

必判定 ( xi )  Di  ,仅依赖 -邻域计算。
定义 5(基于样本类别的正域计算):对于一个给

d (xi , xj )    xip  x jp
 p 1
x  (x )

    ,易知若 i j


,则 定的邻域决策系统NDT  (U,C  D,V, f ) ,根据样本类别, D 将 U 划分为 N 个等价类: D1, D2 ,..., DN 。

j i 。即证。

改进 2:在改进 1 的基础上,根据定理 2 提出粗略计算 xi1  x j1   。基于图 1 中的样本分布,如图 4

B  C ,在对样本 xi  Di 进行正域判定时,若已判定 xi  PosB (D) , 则跳过计算,否则与待选样本

x j U  Di 按照改进  2  的策略进行度量计算, 若d ( xi , x j )   ,则立即判定 xi  PosB (D) ,且同时判定x j  PosB (D) 。
3.3性能分析
设对于 n 维实数样本空间上的论域U  , D 将
U   划 分 为  N   个 等 价 类 :  D1, D2 ,..., DN     , 且 

的时间开销会随着数据集中样本类别数 N 的增加而增大,当 N  很大时,上述表达式可表示为
O   n U 2  。本文的实验部分也证明了这点:本文
的 FARABC  算法对类别数较少的数据集进行属性约简的效率最高。
4 2


D1        D2     ...  DN     , U 中有一半的样本属于正

对于时间复杂度 O( n  n |U | ) 需要注意的是,

N
域,则基于样本类别的正域计算在进行计算时,其计算量如图 5 阴影所示。


\

在图 5 中,阴影方格 B(i, j) 的计算量是
 U 2
p n  ,其中 p  2 / max( xp1  xq1 ) , xp , xq  D j ,总
 N 
共需计算 N(N 1) 个方格,所以基于样本类别的正域
2
 P(N 1) 2 

FHARA 算法的效率受样本在样本空间中分布情况的影响。上述表达式是在样本均匀分布的情况下求得的,而在实际中样本的分布往往边缘稀疏,中心密集,这种情况会限制了图 2 中扇环筛除样本的能力;其次,基于扇环映射的样本划分在进行正域判定前,需要对样本进行 hash 映射,在进行正域判定时,又需要进行 hash 访问,这些操作也存在一定的时间开销。
3.4基于样本类别的正域计算算法
根据以上思路,设计基于样本类别的正域计算Pos(U , B, D, ) ,其中U  D1  D2  ...  DN 。如算法 1 所示。
算 法 1 :
输入: U , B , D , 

计算的时间复杂度近似为 O 2N  n U  ,其中

 
p  2 / max( xp1  xq1 ) , x p , xq  U 。

输出: PosB (D)
Step 1 初始化Pos=U

在完成对数据集归一化处理的条件下,对于基

Step 2 for each

xi  Di , i  1, 2,..., N

于样本类别的正域计算,其时间复杂度的表达式中

if xi  Pos

max(xp1

xq1

)  1

,所以其时间复杂度可进一步表示为

for each

x j  U  Di

O  (N 1)  n U 2  ;对于 FHARA 算法的正域计算,

if x i1  x j 1  
if d ( xi , x j )  

 N 

 
其时间复杂度的表达式中max d ( xi , x0 ) 
4


n ,所以其

Po s    P o s   xi , x j  ;
break;

时间复杂度可进一步表示为 O(

 n |U |2) 。对比两个

end if end if

表达式可知,基于样本类别的正域计算除了受到
的取值、样本维数和样本个数的影响外,还受到样本类别数的影响。
时间复杂度 O  (N 1)  n U 2  说明,若 的取值
 
和数据集的规模恒定,则基于样本类别的正域计算

end for end  if end for
Step 3 return Pos

4基于样本类别的快速属性约简算法

对一个数据集而言,如何删除冗余属性,得到属性约简是粗糙集理论研究的重点之一。

定义 6[1](属性约简):对于一个给定的邻域决策end while Step 3 return red可以看出,正域计算 Pos(U , B, D, ) 影响着算法系 统 NDT  (U,C  D,V, f ) ,

B  C

, 若 满 足 

2 的时间开销。相比 F2HARNRS 算法,FHARA 算

PosB (D)  PosC (D) ,则称 B 是一个独立属性子集;如果对aB , Pos B { a }  D   Pos B  D  ,则称 B 为 C 的一个属性约简。

贪心策略具有以较少时间求解最优解或次优解的特点。为了更快速地求得数据集的属性约简,
F2HARNRS 算法[4]和 FHARA 算法[8]均采用了贪心策略:初始化属性约简集合为空集,当前正域为空集,每次选取使当前正域中样本个数增加最多的属性加入集合,直至对于当前集合而言所有属性的重
要度全为 0 或样本全划入当前正域中时,输出集合。

法的工作在于改进了正域计算,从而减少了算法时间开销。本文沿用算法 2,结合本文的基于样本类别的正域计算(算法 1),提出基于样本类别的快速属性约简算法(Fast Attribute Reduction Algorithm Based on Category,FARABC)。
在该算法下,假设某一数据集有 m 个属性,约
简结果中包含 k 个属性,且每增加一个属性正域中
增加 U 个样本,则进行正域判定的次数为:
k
k  1 1

其中,根据新增加的属性不会使已属于正域的样本

m U  m  1 U

 ...  m  k  U
k k

变为非正域样本这一性质,在算法的计算过程中, 每次仅对还未判定为正域的样本进行正域计算。如算法 2 所示。
算法 2[4,8]:
输入:决策表(U ,C  D,V , f )
输出;属性子集 red
Step 1  初始化 red= ,待检验样本smp_chk=U 当 前 正 域 max_pos= , 最 好 属 性max_i=
Step 2 while smp_chk 
max_pos 

 m U 1  2  ...  k  k
 m U 1  k 
2

5实验分析

5.1实验环境及方案
UCI(University of California Irvine)提供了一系列用于测试的标准数据集。本文从 UCI 中选取了
12 个数据集,并按其样本数的大小进行升序排列,
如表 1 所示。

本次实验在一台Intel(R) Pentium(R) CPU G620 和 4GB 内存的 PC 机上,采用 Windows 7 环境下的MATLAB R2016b 进行实验。
通过和 FHARA 算法进行对比,实验将从三个方面对 FARABC 算法进行分析。首先,通过比较两种算法得到的属性约简,分析 FARABC 算法的有效性;其次,通过比较两种算法的运行时间和样本间的度量计算次数,分析 FARABC 算法的时间开销; 最后,通过比较 FARABC 算法相对于 FHARA 算法在度量计算次数上的比例和数据集中样本类别数的关系,分析 FARABC 算法的效率。其中,FHARA 算法和 FARABC  算法的比较实质上是两种正域计算的比较。
5.2实验结果
5.2.1FARABC 算法的有效性

为了去掉量纲对数据的影响,先对数据集数据进行归一化处理。参考 Hu[4]和 Liu[8]的实验结果, 本文在区间 0, 0.2 中随机地选取  的取值。将
FHARA 算法和 FARABC 算法各执行十次,取十次运行时间中的最小值作为算法的运行时间。实验运行结果如表 2 所示。
表 2 算法得到的属性约简

8
tion

由表 2 可知,在 取值相同的情况下,两种算法得到的约简结果一致,这说明了 FARABC 算法是正确有效的。
5.2.2FARABC 算法的时间开销
两种算法的运行时间如表 3 所示。
表 3  算法的运行时间 s

编号 数据集 FHARA FARABC
1 Zoo 0.153486 0.13305
2 Iris 0.082747 0.055788
3 Wine 0.41165 0.219212
4 Sonar 5.31434 2.226284
5 Ionosphere 12.850363 2.570889
6 Libras movement 4.237643 2.914878
7 WDBC 6.633978 1.798142
8 Credit Approval 15.05088 2.366395
9 German Credit 13.532281 1.734165
10 CMC 19.582114 3.229287
11 Segmentation 24.922299 14.291288
12 Abalone 34.01808 17.390264

文章出自SCI论文网转载请注明出处:https://www.scipaper.net/jisuanjilunwen/442.html

发表评论

Sci论文网 - Sci论文发表 - Sci论文修改润色 - Sci论文期刊 - Sci论文代发
Copyright © Sci论文网 版权所有 | SCI论文网手机版 | 豫ICP备2022008342号-1 | 网站地图xml | 百度地图xml