不完备模糊决策信息系统知识约简

对条件属性值域不完备且决策属性值又是模糊的不完备模糊决策信息系统的研究,至今还不多见。在不完备模糊决策信息系统的粗集模型基础上,提出了启发式约简算法和基于辨识矩阵的约简算法,并通过实例说明了算法的可行性。

不完备模糊决策信息系统知识约简1

付昂1，胡军2

1重庆邮电大学计算机科学与技术学院，重庆（400065）

2西安电子科技大学电子工程学院，西安（710071）

E-mail：，摘 要：对条件属性值域不完备且决策属性值又是模糊的不完备模糊决策信息系统的研究，至今还不多见。在不完备模糊决策信息系统的粗集模型基础上，提出了启发式约简算法和基于辨识矩阵的约简算法，并通过实例说明了算法的可行性。

关键词：粗糙集，不完备信息系，模糊决策信息系统

中图分类号：TP18

1. 引言

由Z. Pawlak 教授提出的Rough 集理论[1]近年来无论是在系统理论、计算模型的建立和应用系统的研制开发上，都已取得了很多成果，也建立了一套较为完善的Rough集理论体系。知识约简是Rough集理论处理信息系统的重要手段，它在保持信息系统分类能力不变的前提下，删除掉系统中冗余信息，为进一步高效的知识获取奠定基础。对于不完备信息系统的知识约简，近年来，众多学者作了大量的工作，并取得了一定的成果[2-6]。

模糊目标信息系统在许多实际应用中存在，它的特点是近似空间是清晰的，而决策是模糊的。这种系统上的知识简化不能采用Pawlak信息系统上的约简方法[7]。因此有必要对模糊目标信息系统的知识约简进行研究。近两年对模糊目标信息系统的研究也获得了比较多的成果[8-12]。

文献[10]在不完备信息系统和模糊决策信息系统的基础上，提出了不完备模糊决策信息系统的概念，并且基于不完备信息系统中的相容关系，给出了不完备模糊决策信息系统的Rough集模型，该模型是完备模糊决策信息系统的Rough集模型、不完备决策信息系统Rough集模型和完备决策信息系统Rough集模型的推广。本文在文献[10]基础上，提出了基于属性重要性的启发式约简算法，和基于辨识矩阵的约简算法，并通过实例说明了算法的可行性。

2. 基本概念

2.1 模糊决策信息系统

定义1 设S=(U,A,D,F)是决策信息系统，其中U是非空的对象集合，A是条件属性集合，D是非空的决策属性集合。若对于每个d∈D有fd:U→[0,1]，其中fd∈F，则称S=(U,A,D,F)是模糊决策信息系统。

定义2 设W是全域U上的模糊集合，对于任意的a∈[0,1]，令

Wa={x∈U|W(x)≥α},

Wa+={x∈U|W(x)>α}。

Wa与Wa+分别称为W的α水平集与弱α水平集。

以下总是用P(U)表示U的幂集，F(U)表示U上的模糊集合的全体。

定义3 设(U,R)为Pawlak近似空间，[x]R表示包含x的等价类，其中R表示U上的等1本课题得到重庆邮电大学自然科学基金（项目编号：A2006-56）的资助。

对条件属性值域不完备且决策属性值又是模糊的不完备模糊决策信息系统的研究,至今还不多见。在不完备模糊决策信息系统的粗集模型基础上,提出了启发式约简算法和基于辨识矩阵的约简算法,并通过实例说明了算法的可行性。

价关系。 W∈F(U)，令

W)(x)=max{W(y)|y∈[x]R}，

(W)(x)=min{W(y)|y∈[x]R}。 则R(W)和R(W)分别称为模糊集合W关于近似空间(U,R)的上近似集合和下近似集合。

R(Wα)={x|[x]R∩Wα≠ }，

(Wα)={x|[x]R Wα}，

分别称为W的α水平集关于近似空间(U,R)的上近似集合与下近似集合。

易知：当α>β时，有R(Wα) R(Wβ)和(Wα) Wβ)。

2.2 不完备模糊决策信息系统

定义4 不完备近似空间上模糊决策信息系统S的一般形式定义为：S=(U,A,V,F;D,W,G)。其中，

(1) U表示非空有限对象的论域，即U={x1,x2,L,xn}；

(2)A表示非空有限的条件属性集合，即A={a1,a2,L,ap}，ai:U→Vi，i≤p，且至少存在一个Vi含有空值；

(3) F为条件属性映射集合， f∈F，f:U×A→V，V=UVi； 1≤i≤p

(4)D表示非空有限的决策属性集合，即D={d1,d2,L,dq}，dj:U→Wj，Wj∈F(U)，且Wj(xk)∈[0,1]，k≤n，j≤q；

(5) G表示模糊目标映射集合， g∈G，g:U×D→W，W=UWj。 1≤j≤q

在不引起混淆的情况下，简称为不完备模糊决策信息系统。

若q=1，并令D={d}，G={g}，W∈F(U)，则称S=(U,A,V,F,{d},W,{g})称为不完备模糊单决策信息系统。

定义5 设S=(U,A,V,F,{d},W,{g})是一不完备模糊决策信息系统，B A，T(B)是不完备空间(U,A,D,F)上关于B的相容关系。 x∈U，包含x的相容类为TB(x)={y∈U|(x,y)∈T(B)}，对任意的模糊集W∈F(U)，令

TB(W)(x)=max{W(y)|y∈TB(x)}，

TB(W)(x)=min{W(y)|y∈TB(x)}，

其中，W(y)表示对象y的隶属函数值，则TB(W)，TB(W)分别称为模糊集W在不完备空间(U,A,D,F)下基于相容关系T(B)的不完备模糊上近似集与不完备模糊下近似集，其中TB:F(U)→F(U)与TB:F(U)→F(U)分别称为不完备模糊上近似算子与不完备模糊下近似算子。显然，TB(W)，TB(W)是一对模糊集合。

定义6 设S=(U,A,V,F,{d},W,{g})是一不完备模糊决策信息系统，W∈F(U)，B A，0≤α,β≤1。记

TB(W)β={x∈U|TB(W)(x)≥β}，

对条件属性值域不完备且决策属性值又是模糊的不完备模糊决策信息系统的研究,至今还不多见。在不完备模糊决策信息系统的粗集模型基础上,提出了启发式约简算法和基于辨识矩阵的约简算法,并通过实例说明了算法的可行性。

TB(W)α={x∈U|TB(W)(x)≥α}。

则对于0≤β≤α≤1，W关于(α,β)的精确度与粗糙度分别定义为：

αB(α,β)=|TB(W)α|

|TB(W)β|，

ρB(α,β)=1 αB(α,β)=1 |TB(W)α|

|TB(W)β|。 规定，TB(W)β= 时，αB(α,β)=1，βB(α,β)=0。

定理1 设S=(U,A,V,F,{d},W,{g})是一不完备模糊决策信息系统，W∈F(U)，B A，0≤α,β≤1，则

αA(α,β)≥αB(α,β)，ρA(α,β)≤ρB(α,β)。

定义7 设S=(U,A,V,F,{d},W,{g})是一不完备模糊决策信息系统，W∈F(U)，B A。若B是使αA(α,β)=αB(α,β)成立，且对B的任意真子集此式不成立，则称B是不完备模糊决策信息系统S的(α,β)精度约简。

从精度约简的定义看，它确保了不完备模糊决策信息系统中隶属度不小于α的确定对象与隶属度不小于β的可能对象数之比不变。

3. 基于属性重要度的启发式精度约简算法

定义8设S=(U,A,V,F,{d},W,{g})是一不完备模糊决策信息系统，条件属性集A关于

(α,β)D的(α,β)核记为COREA(D)，则

(α,β)COREA(D)={a∈A|αA(α,β) αA {a}(α,β)>0}。

定理2 设S=(U,A,V,F,{d},W,{g})是一不完备模糊决策信息系统，则条件属性集A

(α,β)(α,β)关于D的(α,β)核COREA(D)为所有(α,β)精度约简REDA(D)的交集，即

(α,β)(α,β)COREA(D)=IREDA(D)。

(α,β)(α,β)证明 (1) 证明IREDA(D) COREA(D)，

(α,β)由定理1，易知： a∈IREDA(D)有

αA(α,β) αA {a}(α,β)>0，

即

(α,β)a∈COREA(D)。

(α,β)(α,β)(2) 证明COREA(D) IREDA(D)，

(α,β)(α,β)利用反证法，假设存在a∈COREA(D)，但a IREDA(D)，即至少存在一约简结

(α,β)(α,β)果REDA(D)，使得a REDA(D)。由定义8知，αA(α,β) αA {a}(α,β)>0。

(α,β)(α,β)(α,β)又因为，REDA(D) A {a}，结合定理1知，αA(D)≠AB(D)，其中，

(α,β)B=REDA(D)，这与定义7相矛盾，所以假设不成立，原命题正确，即

(α,β)(α,β)COREA(D) IREDA(D)。

综合(1)，(2)可知，

对条件属性值域不完备且决策属性值又是模糊的不完备模糊决策信息系统的研究,至今还不多见。在不完备模糊决策信息系统的粗集模型基础上,提出了启发式约简算法和基于辨识矩阵的约简算法,并通过实例说明了算法的可行性。

(α,β)(α,β)COREA(D)=IREDA(D)。

证毕。

定义9设S=(U,A,V,F,{d},W,{g})是一不完备模糊决策信息系统，A为条件属性集合，且B A，则对于任意属性a∈A\B的重要性SGFB(α,β)(a)定义为

SGFB(α,β)(a)=αB∪{a}(α,β) αB(α,β)。

算法1基于属性重要性的启发式精度约简算法

输入：不完备模糊决策信息系统S=(U,A,V,F,{d},W,{g})，阈值α，β。

输出：系统S的(α,β)精度约简B A。

(α,β)1初始化: B= ，COREA(D)= ；

(α,β)(α,β)2计算系统S的属性核COREA(D)，B=B∪COREA(D)；

3如果αA(α,β)=αB(α,β)，则转5；

4计算属性ai∈A\B的重要性；选取其中重要性最大的属性a(若两个属性重要度相等，则选取未知属性值个数最少的属性)，B=B∪{a}，转3；

5返回精度约简B，算法结束。

4. 基于辨识矩阵的精度约简算法

(α,β)定义10设S=(U,A,V,F,{d},W,{g})是一不完备模糊决策信息系统，CA(i,j)表示

(α,β)(α,β)精度辨识矩阵第i行第j列元素，则(α,β)精度辨识矩阵CA定义为：

{ak|ak∈A∧xj∈T{ak}(xi)}W(xj)<α(α,β)， (i,j)= CA0else

其中，i,j=1,2,L,|U|。

(α,β)′∈A，定理3 设S=(U,A,V,F,{d},W,{g})是一不完备模糊决策信息系统，ak,akCA

′相对属性ak是冗余的，当为系统S的(α,β)精度辨识矩阵。则属性ak

(α,β)(α,β)ak∈CA(i,j) a′(i,j)，i,j=1,2,L,|U|。 k∈CA

即 证明 只需证明α{ak,ak′}(α,β)=α{ak}(α,β)，

|T{ak,a′k}(W)α|

|T{ak,ak′}(W)β|=|T{ak}(W)α|

|T{ak}(W)β|。

′生成的对象xi∈U的相容类分别为T{ak}(xi)，T{a′k}(xi)。若属性设由属性ak和ak

(α,β)(α,β)′∈CAak∈CA(i,j)，由已知条件知，ak(i,j)，即对象xj∈U满足：

xj∈T{ak}(xi)∧xj∈T{ak′}(xi)∧W(xj)<α，

因此xj∈T{ak,ak′}(xi)∧W(xj)<α。

继而根据定义5，6可得T{ak}(W)α=T{ak,a′k}(W)α，T{ak}(W)β=T{ak,a′k}(W)β。

因此，

对条件属性值域不完备且决策属性值又是模糊的不完备模糊决策信息系统的研究,至今还不多见。在不完备模糊决策信息系统的粗集模型基础上,提出了启发式约简算法和基于辨识矩阵的约简算法,并通过实例说明了算法的可行性。

|T{ak,a′k}(W)α|

|T{ak,ak′}(W)β|

即 =|T{ak}(W)α||T{ak}(W)β|，

α{a,a′}(α,β)=α{a}(α,β)。 kkk

证毕。

算法2 基于(α,β)精度辨识矩阵的约简算法

输入：不完备模糊决策信息系统S=(U,A,V,F,{d},W,{g})，阈值α，β。

输出：系统S的(α,β)精度约简B A。

1初始化：B= ；

(α,β)2生成(α,β)精度辨识矩阵CA；

(α,β)遍历辨识矩阵CA3′,ak∈A满足条件，若有属性ak

(α,β)(α,β)′∈CA′； ak∈CA(i,j) ak(i,j)，则删除属性ak

(α,β)4 统计辨识矩阵CA中剩余未删除属性a1,a2,Lam，得到约简结果B=Ual； 1≤l≤m

5 算法结束。

5. 算法测试

为了说明算法的可行性，这里引用文献[10]的一个不完备模糊决策信息系统的例子，并在原例的基础上，添加了两条属性，如表1所示。其中论域U={x1,x2,x3,x4,x5,x6,x7,x8,x9}，条件属性A={a1,a2,a3,a4,a5}，决策属性D={d}。

表1 不完备模糊决策信息系统数据表 U x1a1 a2 a3 a4 a5 d x2x3 x4x5x6 x7x8

x9

W=0.80.60.90.70.80.50.70.60.5， ++++++++x1x2x3x4x5x6x7x8x9

各对象关于条件属性集A的相容类分别为：

TA(x1)={x1}，TA(x2)={x2,x4}，TA(x3)={x3}，TA(x4)={x2,x4}，TA(x5)={x5}，TA(x6)={x6}，TA(x7)={x7}，TA(x8)={x8}，TA(x9)={x9}。

TA(W)=0.80.70.90.70.80.80.70.60.5++++++++， x1x2x3x4x5x6x7x8x9

对条件属性值域不完备且决策属性值又是模糊的不完备模糊决策信息系统的研究,至今还不多见。在不完备模糊决策信息系统的粗集模型基础上,提出了启发式约简算法和基于辨识矩阵的约简算法,并通过实例说明了算法的可行性。

TA(W)=

0.80.60.90.60.80.80.70.60.5。 ++++++++x1x2x3x4x5x6x7x8x9|TB(W)0.6|

|TB(W)0.6|=8=1，ρA(0.6,0.6)=0。 8若取(α,β)=(0.6,0.6)，则αA(0.6,0.6)=

(0.6,0.6)(D)={a1,a2,a4}， (1)采用算法1，求得属性核为COREA

因为αA(0.6,0.6)=α{a1,a2,a4}(0.6,0.6)，所以得到(0.6,0.6)精度约简为{a1,a2,a4}。

(α,β)为： (2)采用算法2，求得(α,β)精度辨识矩阵CA

x1Lx5

x1 0

x2 x3 x4

=x5 x6

x7 x8 x9 0L0M0ML0x6a3a2,a3,a4,a5a1,a3,a4,a5a3,a4,a5a1,a3,a5a1,a2,a3,a4,a5a1,a3,a5a1,a2,a3,a5

a3,a4LLx9a3,a4(0.6,0.6)CA a2,a3,a4,a5 Ma3,a4 a3,a4,a5 0a1,a3,a4,a5 a3,a4 Ma3,a4,a5 a3,a4 La1,a2,a3,a4,a5

经分析可知，属性a3,a5是冗余的，因此得到约简结果为：{a1,a2,a4}。

6. 结束语

本文在不完备模糊决策信息系统的粗集模型基础上，提出了基于属性重要性的启发式约简算法和基于辨识矩阵的约简算法，并通过实例说明了算法的可行性。为进一步研究不完备模糊决策信息系统的知识获取提供了一定基础。

参考文献

[1] Pawlak Z. Rough Sets[J]. International Journal of Computer and Information Sciences, 1982, 11:314-356.

[2] Kryszkiewicz M. Rough set approach to incomplete information system[J]. Information Sciences, 1998,

112:39-49.

[3] Wu Weizhi, Mi Jusheng, Zhang Wenxiu. Approaches to approximation reducts in incomplete decision

tables[J]. Lecture Notes in Artificial Intelligence, 2003, 2639:283-286.

[4] 黄兵. 基于粗糙集的不完备信息系统知识获取理论与方法[D]. 南京:南京理工大学, 2004.

[5] 顾沈明, 吴伟志, 高济. 不完备信息系统中知识获取算法[J]. 计算机科学, 2005, 32(9):149-152.

[6] 黄海, 王国胤，吴渝. 一种不完备信息系统的直接约简方法[J]. 小型微型计算机系统, 2005,

26(10):1761-1765.

[7] 管涛，冯博琴. 模糊目标信息系统上的知识约简[J]. 软件学报，2004，15(10):1470-1478.

[8] Liu Wenjun, Xiao Qimei. Fuzzy decision algorithm based on rough sets[J]. Fuzzy Systems and Mathematics,

2006, 20(2):127-132.

[9] 袁修久，张文修. 模糊目标信息系统的属性约简[J]. 系统工程理论与实践，2004，5：116-125.

[10] 魏大宽, 周献中, 黄兵. 不完备模糊决策信息系统的粗集模型与精度约简[J]. 计算机科学, 2006,

33(6):182-185.

[11] 魏大宽，黄兵，周献中. 不完备模糊目标信息系统粗集模型与知识约简[J]. 计算机工程, 2006,

32(8):48-51.

[12] 张文修，梁怡，吴伟志. 信息系统与知识发现[M].北京：科学出版社，2003.

对条件属性值域不完备且决策属性值又是模糊的不完备模糊决策信息系统的研究,至今还不多见。在不完备模糊决策信息系统的粗集模型基础上,提出了启发式约简算法和基于辨识矩阵的约简算法,并通过实例说明了算法的可行性。

Knowledge Reduction in Incomplete and Fuzzy Decision

Information Systems

Fu Ang1，Hu Jun2

1,2School of Computer Science and Technology，Chongqing University of Posts and

Telicommunications，Chongqing (400065)

2 School of Electronic Engineering，XiDian University，Xi'an (710071)

Abstract

The concept of incomplete and fuzzy decision information systems based on incomplete approximation space and fuzzy decision information system was proposed recently. Based on the rough set model of incomplete fuzzy decision information systems by the tolerance relation, two reduction algorithms was proposed, and showed they are feasible by example.

Keywords：Rough set，Incomplete information system，Fuzzy decision information system

作者简介：

付昂，男，1981年生，硕士研究生，主要研究方向是智能信息处理，粒计算；

胡军，男，1977年生，博士研究生，讲师，主要研究方向包括知识发现，粒计算，粗糙集等。

本文来源：https://www.bwwdw.com/article/06w4.html