近似空間復(fù)合的矩陣表示*

姚愛夢，米據(jù)生

河北師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，石家莊 050024

近似空間復(fù)合的矩陣表示*

姚愛夢+，米據(jù)生

河北師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，石家莊 050024

近似空間；復(fù)合；粗糙集；模糊集；矩陣

1 引言

20世紀(jì)80年代初Pawlak提出的粗糙集理論[1]是一種處理不精確、不確定、不完全數(shù)據(jù)的新型數(shù)學(xué)理論，已在生活中的眾多領(lǐng)域被廣泛應(yīng)用。粗糙集理論的核心是利用等價關(guān)系從近似空間中導(dǎo)出一對上、下近似算子。然而在一些實際問題中等價關(guān)系往往不容易被滿足，涉及的論域也可能不止一個[2]，因而擴充原有的粗糙集模型和改進計算方法是粗糙集理論中一個重要的研究內(nèi)容。

矩陣是一種高效的并且可計量化的工具。在粗糙集理論中，早期Guan等人[3]提出了信息系統(tǒng)的矩陣算法，他將信息系統(tǒng)中的等價關(guān)系用矩陣的形式進行了重新描述，但在這個過程中矩陣更多的只是一種表示形式，而不能用來參與具體計算。之后劉貴龍[4-6]利用集合的特征函數(shù)，提出了一種基于矩陣布爾運算的求解上、下近似的方法。近幾年來，很多學(xué)者[2,7-10]致力于研究如何利用矩陣刻畫粗糙集的上、下近似，其中劉財輝在文獻[11]中提出了一種基于一般二元關(guān)系的粗糙集上、下近似的直接矩陣求法。本文主要研究兩個近似空間的復(fù)合問題，并考察如何將經(jīng)典集和模糊集的上、下近似用矩陣表示和求解的問題。總的來說，矩陣方法使人們從另一視角對粗糙集的認(rèn)識更加深刻，也使得計算大大簡化。

2 預(yù)備知識

下面主要介紹廣義近似空間和廣義模糊近似空間中的一些基礎(chǔ)知識。

定義1[12]設(shè)U和V是兩個非空有限集合，稱為論域。任何子集R?U×V都稱為從U到V的二元關(guān)系。如果U=V，則稱R是U上的二元關(guān)系。

定義2[12]稱三元組(U,V,R)為廣義近似空間，其中U和V是兩個非空的有限論域，R是從U到V的二元關(guān)系。

定義3[12]設(shè)(U,V,R)為廣義近似空間，分別定義兩個算子Rs:U→P(V)及Rp:V→P(U)：

例1在廣義近似空間(U,V,R)中，論域U={x1,x2,x3,x4,x5,x6}論域V={y1,y2,y3,y4,y5,y6,y7}。U和V的二元關(guān)系如表1。

故易知：Rs(x1)={y1,y4},Rs(x2)={y1,y2,y3,y4},Rs(x3)={y1,y4,y5,y6,y7} ,Rs(x4)={y1,y2,y3,y4},Rs(x5)={y5,y6,y7},Rs(x6)={y5,y6,y7};Rp(y1)={x1,x2,x3,x4},Rp(y2)={x2,x4},Rp(y3)={x2,x4},Rp(y4)={x1,x2,x3,x4},Rp(y5)={x3,x5,x6},Rp(y6)={x3,x5,x6},Rp(y7)={x3,x5,x6}。

若X={x1,x2,x3,x4},則(X)={y1,y2,y3,y4},(X)={y1,y2,y3,y4,y5,y6,y7};

Table1 Binary relation of U and V表1 U和V的二元關(guān)系表

若Y={y1,y2,y3,y4},則(Y)={x1,x2,x4},(Y)={x1,x2,x3,x4}。

定義4[13]設(shè)U和V是非空有限論域，U的模糊子集全體記為F(U)。映射R:U×V→[0,1]，稱為從U到V的模糊二元關(guān)系。?A,B∈F(U)有：(A?B)(x)=∨(A(x),B(x));(A?B)(x)=∧{A(x),B(x)}。模糊集A的α截集Aα為Aα={x|A(x)≥α}，α∈[0,1]。容易驗證：A(x)=sup{α:x∈Aα}，簡記為

定義5[14]稱三元組(U,V,R)為廣義模糊近似空間，如果U和V為非空有限論域，R是從U到V的模糊二元關(guān)系。

定義6[15]設(shè)(U,V,R)為廣義模糊近似空間，?A∈F(U),B∈F(V)，定義A和B的下近似和上近似分別為：

引理1[15]設(shè)(U,V,R)為廣義模糊近似空間，?A∈F(U)，B∈F(V)，有：

例2在廣義模糊近似空間(U,V,R)中，論域U={x1,x2,x3}，論域V={y1,y2,y3,y4},U和V的模糊二元關(guān)系如表2。

Table2 Fuzzy binary relation of U and V表2 U和V的模糊二元關(guān)系表

3 近似空間的復(fù)合

下面主要介紹廣義近似空間復(fù)合和廣義模糊近似空間復(fù)合的相關(guān)知識，并對復(fù)合近似空間中的算子和原來近似空間中的算子之間的關(guān)系作進一步研究。

定義7[16]設(shè)A=(U,V,R)和B=(V,W,S)是兩個廣義近似空間，A與B的復(fù)合定義為廣義近似空間A?B=(U,W,T)，其中T是二元關(guān)系R和S的復(fù)合，即T=R°S，其中運算°為二元關(guān)系的復(fù)合。

性質(zhì)1設(shè)A=(U,V,R)和B=(V,W,T)是兩個廣義近似空間，A?B=(U,W,T)是A與B合成的廣義近似空間，則?x∈U和?z∈W，(x,z)∈T?Rs(x)?Sp(z)≠?。

證明T=R°S，由關(guān)系復(fù)合的定義知?x∈U和?z∈W，(x,z)∈T 當(dāng)且僅當(dāng)?y∈V 使得(x,y)∈R,(y,z)∈S，即?y∈V 使得y∈Rs(x)且y∈Sp(z)，即Rs(x)?Sp(z)≠?。

性質(zhì)2[16]設(shè)A=(U,V,R)和B=(V,W,T)是兩個廣義近似空間，A?B=(U,W,T)是A與B復(fù)合的廣義近似空間，則：

其中運算°為算子的復(fù)合。

性質(zhì)3[16]設(shè)A=(U,V,R)和B=(V,W,T)是兩個廣義模糊近似空間，A?B=(U,W,T)是A與B復(fù)合的廣義模糊近似空間，則：

其中運算°為算子的復(fù)合。

性質(zhì)4設(shè)A=(U,V,R)和B=(V,W,T)是兩個廣義模糊近似空間，A?B=(U,W,T)是A與B復(fù)合的廣義模糊近似空間，則?α∈[0,1]，Tα=Rα°Sα，其中運算°為二元關(guān)系的復(fù)合。

另一方面，?(x,z)∈Rα°Sα，?y1∈V 使(x,y1)∈Rα且(y1,z)∈Sα，故R(x,y1)≥α 且 S(y1,z)≥α。下證T(x,z)={R(x,y)∧S(y,z)}≥α。顯然y1∈V 滿足{R(x,y1)∧S(y1,z)}≥α，從而對y1∈V有{R(x,y1)∧S(y1,z)}≥α，又因為T(x,z)≥{R(x,y1)∧S(y1,z)}，故 T(x,z)≥α，所以(x,z)∈Tα，即Rα°Sα?Tα。

這樣便證明了Tα=Rα°Sα。

性質(zhì)5設(shè)A=(U,V,R)和B=(V,W,T)是兩個廣義模糊近似空間，A?B=(U,W,T)是A與B復(fù)合的廣義模糊近似空間，則?X?U,Y?V有：

證明根據(jù)性質(zhì)2可證。

性質(zhì)6設(shè)A=(U,V,R)和B=(V,W,T)是兩個廣義模糊近似空間，A?B=(U,W,T)是A與B復(fù)合的廣義模糊近似空間，則?A∈F(U)，B∈F(V)有：

證明由引理1和性質(zhì)5可證。

4 近似空間復(fù)合的矩陣表示

下面主要定義幾種矩陣運算，進而根據(jù)矩陣運算將復(fù)合后的近似空間中的一些運算用矩陣進行表示和求解。

定義9設(shè)A=(aik)n×m，B=(bkj)m×l是兩個矩陣，定義矩陣 C=A°B=(cij)n×l，D=A?B=(dij)n×l，F(xiàn)=A·B，如下：

A·B表示普通意義下的矩陣乘法。

性質(zhì)7設(shè)(U,V,R)為廣義近似空間，U={x1,x2,…,xn},V={y1,y2,…,ym},關(guān)系矩陣為A=(R(xi,yk))n×m,?X?U,Y?V，令 M1=A·OY=(m11,m12,…,m1n)T，M2=AT·OX=(m21,m22,…,m2m)T,則X和Y的上、下近似分別為：

證明首先證明(Y)={xi∈U|sum1(i)=m1i},(Y)={xi∈U|m1i≠0}。

例3續(xù)例1，由上述定義可知(U,V,R)的關(guān)系矩

若X={x1,x2,x3,x4}，則X對應(yīng)的矩陣為：

若Y={y1,y2,y3,y4}，則Y對應(yīng)的矩陣為：

則A·OY=(2 4 2 4 0 0)T與 sum1中元素對應(yīng)相比可知：

AT·OX=(4 2 2 4 1 1 1)T與 sum2 中元素對應(yīng)相比可知：

性質(zhì)8設(shè)(U,V,R)和(V,W,S)是兩個廣義近似空間，它們的復(fù)合為(U,W,T)，其中U、V、W分別為n、m、l維非空有限論域，它們的關(guān)系矩陣分別為A=(R(xi,yk))n×m，B=(S(yk,zj))m×l，C=(T(xi,zj))n×l，則 C=A°B。

定義11在廣義模糊近似空間(U,V,R)中，設(shè)U={x1,x2,…,xn}，V={y1,y2,…,ym}，稱 M=(R(xi,yk))n×m為模糊關(guān)系矩陣，其中R(xi,yk)∈[0,1]。?A∈F(U)，A對應(yīng)的矩陣為OA=(A(x1)A(x2)…A(xn))。

性質(zhì)9設(shè)(U,V,R)為廣義模糊近似空間，U={x1,x2,…,xn}，V={y1,y2,…,ym}，模糊關(guān)系矩陣為 M=(R(xi,yk))n×m，則?A∈F(U)，B∈F(U)，A和B的下近似和上近似對應(yīng)的矩陣分別為：

其中E表示任一元素都是1的矩陣。

證明首先證明

先證 ORU(A)=OA?(E-M)。?yk∈V，有(A)(yk)=(A)(yk)={A(x)∨(1-R(x,yk))},而 OA?(E-M)中第k列元素為(A(xi)∨(1-R(xi,yk)))，故(A)(yk)={A(x)∨(1-R(x,yk))}=(A(xi)∨(1-R(xi,yk))得證。

例4續(xù)例2，由上述定義可知(U,V,R)的關(guān)系矩

性質(zhì)10設(shè)(U,V,R)和(V,W,S)是兩個廣義模糊近似空間，它們的復(fù)合為(U,W,T)，其中U、V、W分別為n、m、l維非空有限論域，它們的模糊關(guān)系矩陣分別 為A=(R(xi,yk))n×m，B=(S(yk,zj))m×l，C=(T(xi,zl))n×l，則C=A°B。

證明證明過程和性質(zhì)8的證明類似。

性質(zhì)11設(shè)(U,V,R)和(V,W,S)是兩個廣義模糊近似空間，它們的復(fù)合為(U,W,T)，其中U、V、W分別為n、m、l維非空有限論域，模糊關(guān)系R、S、T的α 關(guān)系矩陣分別為 MR=(tik)m×n，MS=(tkj)n×l，MT=(tij)m×l，則MT=MR°MS。

證明證明過程和性質(zhì)8的證明類似。

5 結(jié)束語

本文對兩個近似空間復(fù)合前后近似算子之間的關(guān)系作了進一步的探討，進而根據(jù)關(guān)系的矩陣表示和矩陣運算對近似空間中的一些運算用矩陣進行了表示。由于矩陣是一種高效并且可計量化的工具，本文所給出的矩陣方法使人們從另一視角加深對粗糙集的認(rèn)識，也使得計算大大簡化。

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

[2]Yan Ruixia,Zheng Jianguo,Liu Jinliang,et al.Research on the model of rough set over dual-universes[J].Knowledge-Based Systems,2010,23(8):817-822.

[3]Guan J W,Bell DA,Guan Z.Matrix computation for information systems[J].Information Sciences,2001,131(1/4):129-156.

[4]Liu Guilong.The axiomatization of rough set upper approximate operation[J].Fundamental Informaticae,2006,69(3):331-342.

[5]Liu Guilong.Rough set theory based on two universal sets and its applications[J].Knowledge Based Systems,2010,23(2):110-115.

[6]Liu Guilong.The algebraic structures of generalized rough set theory[J].Information Sciences,2008,178(21):4105-4113.

[7]Li Zhongran,Shu Lan.Matrix computation for upper and lower approximations of fuzzy rough sets[J].Computer Technology and Development,2015,25(4):10-12.

[8]Yao Y Y.Constructive and algebraic methods of the theory of rough sets[J].Information Sciences,1998,109(1):21-47.

[9]Zhang Junbo,Li Tianrui,Ruan Da,et al.Rough sets based matrix approaches with dynamic attribute variation in set-valued information systems[J].International Journal of Approximate Reasoning,2012,53(4):620-635.

[10]Wang Shiping,Zhu William,Zhu Qingxin,et al.Characteristic matrix of covering and its application to Boolean matrix decomposition[J].Information Sciences,2014,263(3):186-197.

[11]Liu Caihui,Miao Duoqian.Algorithm of upper and lower approximations based on matrix[J].Application Research of Computers,2011,28(5):1628-1630.

[12]Zhang Wenxiu,Wu Weizhi,Liang Jiye,et al.Rough set theory and method[M].Beijing:Science Press,2001.

[13]Yang Lunbiao,Gao Yingyi.Principle and application of fuzzy mathematics[M].Guangzhou:South China University of Technology Press,2005.

[14]Dubois D,Prade H.Rough fuzzy sets and fuzzy rough sets[J].International Journal of General Systems,1990,17(2/3):191-209.

[15]Sun Wenxin.Fuzzy rough set models over two universes and multi-granulation[D].Chongqing:Chongqing University of Technology,2013.

[16]Mi Jusheng,Zhang Wenxiu.Indirect learning based on rough set theory[J].Computer Science,2002,29(6):96-97.

附中文參考文獻：

[7]李中然,舒蘭.模糊粗糙集的上下近似的矩陣計算[J].計算機科學(xué)與發(fā)展,2015,25(4):10-12.

[11]劉財輝,苗奪謙.基于矩陣的粗糙集上、下近似求解算法[J].計算機應(yīng)用研究,2011,28(5):1628-1630.

[12]張文修,吳偉志,梁吉業(yè),等.粗糙集理論與方法[M].北京:科學(xué)出版社,2001.

[13]楊綸標(biāo),高英儀.模糊數(shù)學(xué)原理與應(yīng)用[M].廣州:華南理工大學(xué)出版社,2005.

[15]孫文鑫.雙論域與多粒度模糊粗糙集模型研究[D].重慶:重慶理工大學(xué),2013.

[16]米據(jù)生,張文修.基于粗糙集的間接學(xué)習(xí)[J].計算機科學(xué),2002,29(6):96-97.

Matrix Representation of Composition ofApproximation Spaces*

YAOAimeng+,MI Jusheng
College of Mathematics and Information Science,Hebei Normal University,Shijiazhuang 050024,China
+Corresponding author:E-mail:yaoaimeng2015@163.com

YAO Aimeng,MI Jusheng.Matrix representation of composition of approximation spaces.Journal of Frontiers of Computer Science and Technology,2017,11(8)：1347-1353.

This paper mainly discusses the problem about calculating the upper and lower approximates of rough set in approximation space.Because a relation can be represented by a matrix and matrix operations are simple and intuitive,this paper proposes the calculation of the upper and lower approximates in rough set based on relation matrix and matrix operations.Firstly,this paper studies the compositions of two generalized approximation spaces and two generalized fuzzy approximation spaces,discusses the relationships between the operators in the composite approximation space and the two original approximation spaces,and shows that the generalized fuzzy approximation space is the further promotion of the generalized approximation space.Then,according to the matrix representation and the operation of the relation,this paper describes some operations and related properties in approximation space by matrix.Finally,this paper introduces the calculation of the upper and lower approximations of rough set in approximation space in matrix method.The theoretical proof shows that the matrix method is feasible and effective.

approximation space;composition;rough set;fuzzy set;matrix

g was born in 1966.He

the Ph.D.degree in applied mathematics from Xi'an Jiaotong University in 2003.Then he was a post-doctoral fellow at the Chinese University of Hong Kong.Now he is a professor and Ph.D.supervisor at Hebei Normal University.His research interests include rough sets,concept lattices and approximate reasoning,etc. 米據(jù)生（1966—），男，河北寧晉人，2003年于西安交通大學(xué)應(yīng)用數(shù)學(xué)專業(yè)獲得博士學(xué)位，隨后在香港中文大學(xué)從事博士后研究，現(xiàn)為河北師范大學(xué)教授、博士生導(dǎo)師，主要研究領(lǐng)域為粗糙集，概念格，近似推理等。

YAO Aimeng was born in 1992.She is an M.S.candidate at Hebei Normal University.Her research interests include rough set and approximate reasoning,etc.姚愛夢（1992—），女，河北保定人，河北師范大學(xué)碩士研究生，主要研究領(lǐng)域為粗糙集，近似推理等。

A

：O236

*The National Natural Science Foundation of China under Grant Nos.61573127,61502144,61300121,61472463(國家自然科學(xué)基金);the Natural Science Foundation of Hebei Province under Grant No.A2014205157(河北省自然科學(xué)基金);the Training Program for Leading Talents of Innovation Teams in the Universities of Hebei Province under Grant No.LJRC022(河北省高校創(chuàng)新團隊領(lǐng)軍人才培育計劃項目);the Natural Science Foundation of Higher Education Institutions of Hebei Province under Grant No.QN2016133(河北省高等學(xué)校自然科學(xué)基金);the Doctor Science Foundation of Hebei Normal University under Grant No.L2015B01(河北師范大學(xué)博士基金).

Received 2016-05,Accepted 2016-08.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-08-15,http://www.cnki.net/kcms/detail/11.5602.TP.20160815.1659.016.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2017/11(08)-1347-07

10.3778/j.issn.1673-9418.1605041

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

摘 要：針對近似空間中粗糙集上、下近似的求解問題，根據(jù)關(guān)系的矩陣表示和矩陣運算具有簡便直觀的特點，提出了利用矩陣方法對近似空間中粗糙集上、下近似進行計算。通過研究廣義近似空間的復(fù)合和廣義模糊近似空間的復(fù)合問題，首先對復(fù)合近似空間的算子和原來近似空間中的算子之間的關(guān)系作進一步的探討，并說明了廣義模糊近似空間的復(fù)合是廣義近似空間復(fù)合的進一步推廣；進而根據(jù)關(guān)系的矩陣表示和矩陣運算對近似空間中的一些運算以及相應(yīng)的性質(zhì)用矩陣進行了表示；最后對近似空間中粗糙集上、下近似的求解問題，也用矩陣方法進行了計算，理論證明結(jié)果顯示了該方法是可行有效的。