基于内外因分析的粗糙近似算子*

许黎明, 何小卫

(浙江师范大学 数理与信息工程学院,浙江 金华 321004)

0 引 言

粗糙集理论是由波兰数学家Pawlak在1982年提出的处理不完全与不精确问题的有效的数学工具[1]，该理论在数据分析[2-3]、知识发现[4-5]、数据挖掘[6-7]、决策支持与分析[8-9]等方面得到了广泛的应用.经典的粗糙集理论是建立在分类机制的基础上，将分类理解成特定空间上的等价关系，这种等价关系构成了对该空间的划分.粗糙集理论的主要思想是将不确定和不精确知识用已知的知识来刻画.与其他处理不确定性和不精确问题理论相比，粗糙集不需要提供问题所需处理的数据集合之外的任何先验信息，所以它对问题的不确定性的描述是比较客观的.

Pawlak粗糙集模型的推广是粗糙集理论研究的一个重要研究方向.Pawlak粗糙集模型的推广有2种方法：构造性方法和公理化方法.构造性方法主要是从给定的近似空间出发去研究粗糙集和近似算子，由于这种方法研究的问题一般源于实际，所以所建立的数学模型具有很强的应用价值，但不容易深刻揭示近似算子的代数结构，如一般关系下的粗糙集模型[10]、变精度粗糙集模型[11 ]、基于领域算子的粗糙集模型[12]、基于随机集的粗糙集模型[13-14]等等.公理化的方法又称为代数方法，它的主要思路是事先给定一对近似算子L和H：2U→2U.这种方法虽能深刻揭示近似算子的代数结构，但应用性不强.除了以上对粗糙集模型推广研究之外，还有把粗糙集理论用于概念格数据分析之中[15]，它体现了概念内涵和外延的统一, 反映了对象和特征间的联系以及概念间的泛化与例化关系.

粗糙集模型的各种推广研究把粗糙集的理论研究和应用渗透到各种领域，特别是信息系统的约简[16]、规则提取和属性重要性分析等等.但运用粗糙集对信息系统的研究,基本上只考虑静态的信息系统，虽然也有学者对粗糙集的动态特性进行了一些研究[17]，但没有考虑信息系统变化的外在因素.信息系统数据的变化是由外因驱动的.笔者尝试建立基于外因驱动的动态信息系统模型，用粗糙集的方法研究外因在信息系统数据变化过程中的作用.

1 预备知识

2 基于外因驱动的单步动态信息系统模型

内因是事物变化的根据和基础，外因是事物变化的条件，外因通过内因起作用.动态信息系统属性数据的变化也是由外因驱动的，不同属性变化的外因是不同的，本文基于以上动态信息系统,建立了基于外因驱动的动态信息系统模型，用粗糙集的方法研究外因在信息系统数据变化过程中的作用.

考虑信息系统S在外部各种因素的作用下发生了变化，假设变化后的信息系统为S′=(U′,A′,V′,f′).称S为初始信息系统，S′为目标信息系统，信息系统S在外部条件W的作用下转化为S′,其中W是外因 .

为了讨论方便，尝试在最简单的情况下对动态的信息系统建立模型，假设满足以下条件：1)W是非空有限的条件属性集；2)信息系统变化过程中论域U和属性集合A都不发生变化，即U=U′，A=A′；3)根据哲学中外因对事物发展变化是通过内因起作用的原理，假设信息系统的变化是通过A中各个属性值的变化来体现，即ρa;Va→V′a.

一个外因属性能触发的属性值迁移的集合记为

gR={(a,x,x′)∈Ω|gR(a,x,x′)}⊆Ω;

(1)

g能触发的变迁属性集合记为

(2)

所有能触发属性值迁移(a,x,x′)∈Ω的外因集合记为

R(a,x,x′)={g∈W|gR(a,x,x′)}⊆W;

(3)

所有能触发属性a上的属性值迁移的外因集合记为

(4)

以下几种表示方法是等价的

3 近似算子对外因与内因的分析

上面建立了基于外因驱动的单步动态信息系统模型，接下来将给出2对近似算子，用以刻画外部因素和属性值变迁及变迁属性集之间的关系.

定义3设T=(Ω,W,R)为外因驱动的近似空间，Ω是S到S′的属性值变迁集，G⊆W，定义一对近似算子▽,△：2W→2Ω为：

G▽={(a,x,x′)∈Ω| ∀g∈W(gR(a,x,x′)⟹g∈G)}={(a,x,x′)∈Ω|R(a,x,x′)⊆G};

(5)

G△={(a,x,x′)∈Ω| ∃g∈W(gR(a,x,x′)∧g∈G)}=

(6)

根据定义3的算子定义，W中能触发G▽中的属性值变迁的外部因素全都在G中，W中能触发G▽中的属性值变迁的外部因素至少有1个在G中.

定义4设T=(Ω,W,R)为外因驱动的近似空间，Ω是S到S′的属性值变迁集，X⊆Ω，定义一对近似算子▽,△:2Ω→2W为：

X▽={g∈W| ∀(a,x,x′)∈Ω(gR(a,x,x′)⟹(a,x,x′)∈X)}={g∈W|gR⊆X};

(7)

X△={g∈W| ∃(a,x,x′)∈W(gR(a,x,x′)∧(a,x,x′)∈X)}=

(8)

根据定义4的算子定义，X▽中每一个外因属性能触发的属性值变迁全都在X中，X△中每一个外因属性能触发的属性值变迁至少有1个在X中.

定理1假设G,G1,G2⊆W;X,X1,X2⊆Ω,则算子▽和△具有以下性质：

1)GC▽C=G△,GC△C=G▽;XC▽C=X△,XC△C=X▽.其中C表示集合的补集.

2)若∀(a,x,x′)∈Ω,R(a,x,x′)≠φ，则G▽⊆G△;若∀g∈Ω,gR≠φ，则X▽⊆X△.

3)G1⊆G2⟹(G▽1⊆G▽2,G△1⊆G△2);X1⊆X2⟹(X▽1⊆X▽2,X△1⊆X△2) .

4)G▽△⊆G⊆G△▽;X▽△⊆X⊆X△▽.

5)G▽△▽=G▽,G△▽△=G△;X▽△▽=X▽,X△▽△=X△.

6)(G1∩G2)▽=G▽1∩G▽2,(G1∪G2)△=G△1∪G△2;(X1∩X2)▽=X▽1∩X▽2,(X1∪X2)△=X△1∪X△2.

证明 以GC▽C=G△和X▽△▽=X▽的证明为例 ，其余的证明方法类似，故略.

1)GC▽C=G△.

若(a,x,x′)∈GC▽C,则只需证明(a,x,x′)∈G△.假设 (a,x,x′)∉G△，则R(a,x,x′)∩G=φ,即R(a,x,x′)⊆GC,所以(a,x,x′)∈GC▽.矛盾.故(a,x,x′)∈G△.

若(a,x,x′)∈G△,则只需证明(a,x,x′)∈GC▽C.假设(a,x,x′)∉GC▽C，则(a,x,x′)∈GC▽,即R(a,x,x′)⊆GC.又由假设条件(a,x,x′)∈G△得,R(a,x,x′)∩G≠φ.矛盾.故(a,x,x′)∈GC▽C.

综上所述，GC▽C=G△.

2)X▽△▽=X▽.

若g∈X▽△▽,则gR⊆X▽△.那么，对所有的(a,x,x′)∈Ω,有gR(a,x,x′)⟹(a,x,x′)∈X▽△,即gR(a,x,x′)⟹R(a,x,x′)∩X▽≠φ.其中：gR(a,x,x′)意味着存在一个w∈W， 使得wR(a,x,x′)∧w∈X▽成立;w∈X▽意味着wR⊆X成立.由wR⊆X和wR(a,x,x′)可得到(a,x,x′)∈X成立.则对所有的(a,x,x′)∈Ω,gR(a,x,x′)⟹(a,x,x′)∈X,即g∈X▽成立.

若g∈X▽,则对于∀(a,x,x′)∈Ω,有gR(a,x,x′)⟹R(a,x,x′)∩X▽≠φ成立,故对∀(a,x,x′)∈Ω,gR(a,x,x′)⟹(a,x,x′)∈X▽△⟹g∈X▽△▽.

综上所述，X▽△▽=X▽.

定义5设T=(Ω,W,R)为式(2)所描述的近似空间，Ω是S到S′的属性值变迁集，G⊆W，定义一对近似算子★,☆:2W→2A为:

(9)

(10)

根据定义5的算子定义，W中能触发G★中的属性发生值变迁的外部因素全都在G中，W中能触发G☆中的属性发生值变迁的外部因素至少有1个包含在G中.

定义6设T=(Ω,W,R)为式(2)所描述的近似空间，Ω是S到S′的属性值变迁集，X⊆A，定义一对近似算子★,☆：2A→2W为:

(11)

(12)

根据定义6的算子定义，X★中每一个外因属性能触发值变迁的属性全都在X中，X☆中每一个外因属性能触发值变迁的属性至少有1个包含在X中.

定理2假设G,G1,G2⊆W;X,X1,X2⊆A,则算子★和☆具有以下性质：

1)GC★C=G☆,GC☆C=G★;XC★C=X☆,XC☆C=X★.

2)若∀(a,x,x′)∈Ω,R(a,x,x′)≠φ，则G★⊆G☆;若∀g∈Ω,gR≠φ,则X★⊆X☆.

3)G1⊆G2⟹(G★1⊆G★2,G☆1⊆G☆2);X1⊆X2⟹(X★1⊆X★2,X☆1⊆X☆2).

4)G★☆⊆G⊆G☆★;X★☆⊆X⊆X☆★.

5)G★☆★=G★,G☆★☆=G☆;X★☆★=X★,X☆★☆=X☆.

6)(G1∩G2)★=G★1∩G★2,(G1∪G2)☆=G☆1∪G☆2;(X1∩X2)★=X★1∩X★2,(X1∪X2)☆=X☆1∪X☆2.

证明 与定理1的证明类似,故略.

定理3假设G⊆W,X⊆A,则算子▽,△,★和☆具有以下性质：

1)G★⊇Π(G▽),G☆⊇Π(G△)；

2)X▽⊆(Π(X))★,X△⊆(Π(X))☆；

3)GC★⊇Π(GC▽),GC☆⊇Π(GC△)；

4)XC▽⊆(Π(XC))★,XC△⊆(Π(XC))☆.

证明 1)只证明G★⊇Π(G▽),G☆⊇Π(G△)的证明与G★⊇Π(G▽)相似,故略.

3)与4)的证明中只需用GC替换1)中的G，用XC替换2)中的X,即可获得证明.

4 结 语

本文根据事物发展变化过程中内外因的哲学原理，建立了信息系统变化的动态模型，提出了属性值变迁集和属性变迁集的概念，在经典的二元关系下构造了2对近似算子▽,△和★,☆,用以刻画外部因素对属性变化的作用以及2对算子之间的联系.以后需要做的工作还很多，比如考虑在模糊关系下来讨论外因和内部属性变化之间的联系等等.

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

[2]Pawlak Z.Rough sets and intelligent data analysis[J].Information Sciences,2002,147(1/2/3/4):1-12.

[3]Yao Yiyu.A comparative study of formal concept analysis and rough set theory in data analysis[C]//Rough Sets and Current Trends in Computing.Berlin：Springer,2004:59-68.

[4]Michal R C,Grzymala-Busse J W.Global discretization of continuous attributes as preprocessing for machine learning[J].International Journal of Approximate Reasoning,1996,15(4):319-331.

[5]Pawlak Z.Rough sets:Theoretical Aspects of Reasoning about Data[M].Boston:Kluwer Academic Publishers,1991.

[6]Chan Chienchung.A rough set approach to attribute generalization in data mining[J].Journal of Information Sciences,1998,107(1):169-176.

[7]Lingras P J,Yao Yiyu.Data mining using extensions of the rough set model[J].Journal of the American Society for Information Science,1998,49(5):415-422.

[8]David M S.Knowledge discovery by inspection[J].Decision Support Systems,1997,21(1):43-47.

[9]Pawlak Z.Rough set approach to Knowledge-based decision support[J].European Journal of Operational Research,1997,99(1):48-57.

[10]Yao Yiyu,Lin T Y.Generalization of rough sets using modal logic[J].Intelligent Automation and Soft Computing,1996(2):103-120.

[11]Ziarko W.Variable precision rough set model[J].Journal of Computer and System Sciences,1993,46(1):39-59.

[12]Yao Yiyu.Relational Interpretations of Neighborhood Operators and Rough Set Approximation Operators[J].Information Sciences,1998,111(1/2/3/4):239-259.

[13]张文修,吴伟志.基于随机集的粗糙集模型(Ⅰ)[J].西安交通大学学报,2000,34(12):75-79.

[14]张文修,吴伟志.基于随机集的粗糙集模型(Ⅱ)[J].西安交通大学学报,2001,35(4):425-429.

[15]Yao Yiyu,Chen Yaohua.Rough set approximation in formal concept analysis,Transactions on Rough Sets[M].Berlin：Springer,2006:285-305.

[16]商琳，万琼，姚望舒，等.一种连续值属性约简方法ReCA[J].计算机研究与发展，2005,42(7)：1217-1224.

[17]崔玉泉,史开泉.粗集的动态特性分析及应用[J].中国管理科学,2003,11(6):66-70.

[18]刘清.信息变换函数及动态信息系统[J].计算机科学，2004,31(10A):15-17.