![](https://csdnimg.cn/release/download_crawler_static/18652346/bg1.jpg)
维普资讯 http://www.cqvip.com
第
26
卷第
12
期
2006
年
12
月
计算机应用
Computer
Applications
Vo
l.
26
No.
12
Dec.
2006
文章编号:
1001
-90S1
(2
∞
6)
12
- 2961 - 03
基于划分的信息系统属性约简
张海云
lJ
,梁吉业
l.2
,钱宇华
1.2
(1.计算智能与中文信息处理省部共建教育部重点实验室,山西太原
030006;
2
山西大学计算机与信息技术学院,山西太原
030006)
(
seaddy@
sxu.
edu.
cn)
摘
要:从信息革统中属性问划分能力不同的角度出友,提出了属性左划分和属性右划分的观
点,研究了它们的特点与性质,给出了在属性划分意义下桂属性判定方法,设计了一种基于划分的属
性约简算法
ARABP
,并进行了理论分析和实,捡仿真,结果表明该约简算法在效率上较现有的启发式
算法有显著的提高。
关键词:粗糙集;属性约简;属性划分;区分度
中图分类号:
T
P3
11
文献标识码
:A
Attribute reduction based
on
partition in information system
ZHANG
Haì_yun
1
.
2
,
LIANG
Ji_ye
1
.
2
,
QIAN
Yu-hua
1
.
2
(
1.
Key
La
boratory
of
Computatìonal Intelligence a
TU1
Chìnese Information Processìng
of
Minìstry
of
Educ
ω
ìon~
Taì)
明
n
Sha
时
i
030
∞
6
,
China;
2.
School
of
Cor
叩
uter
and
Information Technology, Shanxì Universìty,
Taiyz
皿
n
Shanxi
030
ω
6
,
China)
Abstract:
Based on the viewpoint that attributes have differcnt
pa
口
ition
ability, left-partition and right-partition of the
attributes
were
proposed. Characteristics and
prope
此
ies
of them werc investigated. The judgmcnt method of core attribute
was
given in regard
to
the attribute partition view. A
new
attribute reduction algorithm named ARABP based on attrihute partition
was
brought forward, and the valìdity of the algorithm
was
illustrated by theoretical analysis and experimental results.
Key words: rough set; attribute reduction; attribute partition; dìscembility degree
利用区分矩阵
[IJ
可以方便地得到信息系统的核,但是基于
区分矩阵的属性约简算法的时间和空间复杂度都较高。利用
生物仿真算法(例如遗传算法和蚁群优化算法等)进行属性约
简可以得到约简结果,但是它自身的局限性,如函数参数的选
择,约简结果的收敛,都直接影响到该类算法的实际应用。
本文从区分关系出发,利用区分度和相对区分度的概念
刻画了属性对论域对象的区分能力和相对区分能力,定义了
属性间的左划分和右划分。利用属性左右划分的特点可以很
容易得到信息系统的一个约简属性,随后基于属性划分的思
想,给出一种新的属性约简算沽,并证明该算法是完备的。理
论分析和实验结果表明,该约简算法在效率上较现有的启发
式算法有显著的提高。
l
信息系统中的区分关系与区分度
l.
1
信息系统的基本概念
定义
1
[2]
→个信息系统
S
可以表示为
S
=
(U
,
A
,
V
刀,
其中
U
表示对象的非空有限集合
,
U
=
Ix
l
,
句,…
,
x
n
I
;A
表示
属性的非空有限集合,
A=141
,吨,…
,
a
m
t; v
=
出,飞是
属性
α
,的{自域
;f
表示
UxA
→
V
是一个信息函数,即对巩
E
U,
a
ιE
A
,
有
f(
凡,矶
)ε
V
(J,
o
定义
2[2]
在信息系统
5
中,每个属性子集
pç
二
A
决定了
一个二元不可区分关系
IND(
P):
IND(
P)
= I
(x
i
,
x)
I
a
ε
P
,
f(
町
,
a)
::
f(
巧
,
a)
I
显然
,I
ND(
P)
是一个等价关系。关系
IND(
P)
( P
Ç,
A)
决
定了
U
的一个划分,用
U/
IND(P)
表示,简记为
U/P
o
定义
3
[2]
在信息系统
5
中,若
P
,
。
ι
A
,
则。的
P
正
域
POS
p
(
Q)
定义为
:PiJSp(Q)zxeuMD(0)px
,其中
,
PX
为
X
的
P
的下近似。
定义
4[
盯
在信息系统
5
中
,
P
Ç,
A
,
如果:
1
)IND(P)
:;:;;
IND(A);
2)
P'
C P
,I
ND(P')
#
InD(A);
则称
P
是
A
的一个约简。
核属性集是所有约简的交集。
1.
2
区分关系与区分度
在信息系统
S
中
,
P
Ç,
A ,
U/P
=
I
矶
,
X
2
,
…
,
xtpt
,
其中几
表示论域
U
在属性集
P
下取值的个数。显然,不同等价类之间
的对象都是可区别的。属性集
P
Ç,
A
中所有可区别的对象序
偶决定了一个二元可区分关系
DIS(P)
:
Dβ
(P)
:;:;;
I
(衔,马)
I
:3
a E P ,
f(xi
,
a)
#f(xj
,
a)
I
容易知道,下面性质成立:
性质
1
IND(P)
U
Dl
S(P)
= U x U
o
性质
2
当
IND(P)
=
U
时
,
D
β
(P)
::白。
不可区分关系反映了属性集对论域
U
的划分能力,而区
分关系则决定了属性集区别对象的能力。为了更好地反映属
性集的区分能力,下面给出属性区分度的定义。
定义
5
设
S
::
(U
,
A)
是一个信息系统,
P
E
二
A
,
U/P
::
收稿日期
:2006
-
06
一
14;
修订日期
:2
∞
6
一
08
-26
基金项目
:[-N
家自然科学基金资助项目
(70471003);
高等学校博土学科点专项科研
某金资助
J
jÍ j
~j
(2
∞
50108
∞
4)
;Li
l
阿省高等学校拔尖创新人才基金
作者简介:张海云(1
980
一)
,男,
1[l
jI!j襄垣人,助教,硕十研究牛,主要研究方向:粗糙集理论:
梁市业
(1962
…)
,男
.lll
丽普城人,教授,博
士生导师,博士,主要研究方向:粗糙集理论、数据挖掘、人工智
ft~;
钱宇华
(1976
-),男,
111
西晋城人,陪-卡研究生,主要研究方向:粒度计算.