許晴媛,李進金,張燕蘭
1.閩南師范大學計算機科學與工程系,福建漳州 363000
2.閩南師范大學數(shù)學與信息科學學院,福建漳州 363000
變精度覆蓋決策信息系統(tǒng)的約簡
許晴媛1,李進金2,張燕蘭1
1.閩南師范大學計算機科學與工程系,福建漳州 363000
2.閩南師范大學數(shù)學與信息科學學院,福建漳州 363000
把變精度方法引入到覆蓋決策信息系統(tǒng)中,給出變精度覆蓋下近似與變精度覆蓋上近似的定義。進而討論了變精度覆蓋下近似與變精度覆蓋上近似的若干性質(zhì)及約簡。分析了它們與覆蓋分布約簡、最大覆蓋分布約簡、覆蓋下近似約簡、覆蓋上近似約簡之間的關系。并給出實例進行說明。
變精度;覆蓋;決策信息系統(tǒng);約簡
由Pawlak創(chuàng)立的粗糙集理論[1-2]已被成功應用于決策信息系統(tǒng)的屬性約簡中[3-4]。然而Pawlak粗糙集模型中對象的分類是基于等價關系,分類過于苛刻,不利于大規(guī)模數(shù)據(jù)集合之上的知識發(fā)現(xiàn),人們相繼將Pawlak粗糙集進行了許多有意義的推廣。其中變精度粗糙集模型和覆蓋粗糙集模型是推廣的兩個主流方向。
變精度粗糙集理論是由Ziarko教授于1993年在文獻[5]中提出,它在Pawlak粗糙集的基礎上引進了一個參數(shù)α,并將其定義為錯誤分類率且α∈[0,0.5),即允許一定程度上錯誤分類的存在,所以變精度粗糙集理論能有效地處理帶噪聲的信息系統(tǒng)。后來,AN等人將α定義為正確分類率且α∈(0.5,1][6]。目前變精度粗糙集模型已經(jīng)在很多領域得到了廣泛的應用[7]。
覆蓋粗糙集模型是由Zakowski教授于1983年在文獻[8]提出。2003年,William Zhu和Feiyue Wang在覆蓋粗糙集的基礎上給出了約簡的概念和方法[9]。文獻[10-15]討論了覆蓋信息系統(tǒng)的約簡理論。
本文把變精度粗糙集理論引入到覆蓋決策信息系統(tǒng)中,采用參數(shù)α∈(0.5,1],給出X(X?U)的α覆蓋下、上近似的定義;進而討論了α覆蓋下、上近似的若干性質(zhì)及約簡;最后討論了它們與文獻[14]中覆蓋分布約簡、最大覆蓋分布約簡、覆蓋下近似約簡、覆蓋上近似約簡之間的關系。這些結(jié)果進一步推廣和深化了決策信息系統(tǒng)約簡理論。
為便于本文的討論,下面先給出一些重要的有關概念。
定義1[10]設C={X1,X2,…,Xn}是U上的一個覆蓋。?x∈U,記(x)C=∩{Xj:Xj∈C,x∈Xj},Cov(C)={(x)C:x∈U},則Cov(C)也是U的一個覆蓋,稱Cov(C)為U的C誘導覆蓋。
定義2[10]設?={Ci:i=1,2,…,m}是論域U的一族覆蓋,對于任意的x∈U,令▽?(x)=∩{(x)Ci:i=1,2,…,m},則Cov(?)={▽?(x):x∈U}也是U的一個覆蓋,稱Cov(?)為U的?誘導覆蓋。
定義3[10]設?={Ci:i=1,2,…,m}是論域U的一族覆蓋,D=cmkeoei是決策屬性集,U/D={D1,D2,…,Dr}是U上的決策劃分,稱(U,?,D)為覆蓋決策信息系統(tǒng)。如果對于任意的x∈U,存在Dj∈U/D,使得▽?(x)?Dj,則稱(U,?,D)為協(xié)調(diào)的覆蓋決策信息系統(tǒng),記作Cov(?)≤U/D,否則稱(U,?,D)為不協(xié)調(diào)的覆蓋決策信息系統(tǒng)。
定義4[16]設(U,?,D)是覆蓋決策信息系統(tǒng),對于任意的x∈U,記:
則稱μ?(x)=(D(D1/▽?(x)),D(D2/▽?(x)),…,D(Dr/▽?(x)))為U/D上的覆蓋概率分布函數(shù)。記:
稱m?(x)是不確定命題規(guī)則“若y∈▽?(x),則y∈Dj0”的可信度。記:
為覆蓋決策信息系統(tǒng)論域U上的關于覆蓋族?的最大決策分布函數(shù)。
定理1設(U,?,D)是不協(xié)調(diào)的覆蓋決策信息系統(tǒng),β??。則α∈(0.5,1]時的α覆蓋下近似與α覆蓋上近似有以下性質(zhì):
定義6設(U,?,D)是不協(xié)調(diào)的覆蓋決策信息系統(tǒng),β??。記:
定理2設(U,?,D)是不協(xié)調(diào)的覆蓋決策信息系統(tǒng),β??。記:
定理3設(U,?,D)是不協(xié)調(diào)的覆蓋決策信息系統(tǒng),則有:
(1)覆蓋分布協(xié)調(diào)集必為α覆蓋下近似協(xié)調(diào)集;
(2)覆蓋分布協(xié)調(diào)集必為α覆蓋上近似協(xié)調(diào)集。
證明若β為覆蓋分布協(xié)調(diào)集,則D(Dj/▽?(x))= D(Dj/▽β(x))(j≤r,x∈U),于是D(Dj/▽?(x))≥α等價于D(Dj/▽β(x))≥α,即(x)=(x)(x∈U),則β為α覆蓋下近似協(xié)調(diào)集。同理可證β為α覆蓋下近似協(xié)調(diào)集。
注1一般來講,覆蓋分布約簡集未必是α覆蓋下、上近似約簡集,α覆蓋下、上近似約簡集也未必是覆蓋分布約簡集。以例2來說明。
例2(續(xù)例1)則
由于Cov(?)≤U/D不成立,于是(U,?,D)是不協(xié)調(diào)的覆蓋決策信息系統(tǒng)。得到覆蓋決策分布(見表1)。
表1 例2覆蓋決策分布
由此可見?是覆蓋分布約簡集。
取α=0.6,根據(jù)表1得表2(α覆蓋下近似分布)和表3(α覆蓋上近似分布)。
表2 例2α覆蓋下近似分布
可見C2既是α覆蓋下近似約簡集,也是α覆蓋上近似約簡集。
表3 例2α覆蓋上近似分布
定理4設(U,?,D)是不協(xié)調(diào)的覆蓋決策信息系統(tǒng),β??。記:
若α0>0.5,則當α∈(0.5,α0]時,β是α覆蓋下近似協(xié)調(diào)集,則β必為最大覆蓋分布協(xié)調(diào)集。
定理5設(U,?,D)是不協(xié)調(diào)的覆蓋決策信息系統(tǒng),β??。記:
則有:
(1)當α∈(1-λ0,1]時,若β是覆蓋上近似協(xié)調(diào)集,則β必為α覆蓋上近似協(xié)調(diào)集。
(2)當α∈(1-λβ,1]時,若β為α覆蓋上近似協(xié)調(diào)集,則β必為覆蓋上近似協(xié)調(diào)集。
(3)當α∈(1-λ0,1]時,β為α覆蓋上近似約簡集當且僅當β是覆蓋上近似約簡集。
(3)由(1)與(2)即可證明。
注2定理5條件不成立時,覆蓋上近似協(xié)調(diào)集未必是α覆蓋上近似協(xié)調(diào)集,α覆蓋上近似協(xié)調(diào)集也未必是覆蓋上近似協(xié)調(diào)集。
例3(續(xù)例2)由表1得表4。
可見{C1}是覆蓋上近似協(xié)調(diào)集。而由表3(取α=0.6)知C1不是α覆蓋上近似協(xié)調(diào)集。
本文給出變精度覆蓋決策信息系統(tǒng),討論了α覆蓋下、上近似的若干性質(zhì)及約簡;進而討論了它們與文獻[14]中覆蓋分布約簡、最大覆蓋分布約簡、覆蓋下、上近似約簡之間的關系。這些結(jié)果可看成是決策信息系統(tǒng)約簡理論的進一步推廣和深化。
[1]Pawlak Z.Rough sets[J].International Journal of Computer and Information Sciences,1982,11(5):341-356.
[2]Pawlak Z.Rough sets:theoretical aspects of reasoning about data[M].Boston:Kluwer Academic Publishers,1991.
[3]張文修,梁怡,吳偉志.信息系統(tǒng)與知識發(fā)現(xiàn)[M].北京:科學出版社,2003.
[4]張文修,仇國芳.基于粗糙集的不確定決策[M].北京:清華大學出版社,2005.
[5]Ziarko W.Variable precision rough set model[J].Journal of Computer and System Science,1993,46(1):39-59.
[6]An A,Shan N,Chan C,et al.Discovering rules for waterdemand prediction:an enhanced rough-set approach[J].Engineering Applications in Artificial Intelligence,1996,9(6):645-653.
[7]陶志,許寶棟,汪定偉,等.基于變精度粗糙集理論的粗糙規(guī)則挖掘算法[J].信息與控制,2004,33(1):18-22.
[8]Zakowski W.Approximations in the space(U.II)[J].Demonstrati Mathematica,1983,16(1):761-769.
[9]Zhu W,Wang Feiyue.Reduction and axiomization of covering generalized rough sets[J].Information Science,2003,152(1):217-230.
[10]Chen Degang,Wang Changzhong,Hu Qinghua.A new approach to attribute reduction of consistent and inconsistent covering decision systems with covering rough sets[J].Information Sciences,2007,177:3500-3518.
[11]張亞軍,王艷平,付上金.基于覆蓋粗糙集理論中的約簡與求核[J].模糊系統(tǒng)與數(shù)學,2007,21(6):152-156.
[12]Li Fei,Yin Yunqiang.Approaches to knowledge reduction of covering decision systems based on information theory[J].Information Sciences,2009,179:1694-1704.
[13]張燕蘭,李進金.覆蓋決策系統(tǒng)的相對約簡[J].工程數(shù)學學報,2009,26(5):929-935.
[14]許晴媛,李進金,張燕蘭.覆蓋決策信息系統(tǒng)的約簡[J].山東大學學報:理學版,2010,45(1):89-93.
[15]夏秀云,秦克云,田浩.協(xié)調(diào)覆蓋決策信息系統(tǒng)下基于條件信息熵的屬性約簡[J].河南大學學報:自然科學版,2010,40(4):406-410.
[16]Lashin E F,Kozae A M,Abo Khadra A A,et al.Rough set theory for topological spaces[J].International Tournal of Approximate Reasoning,2005,40(1/2):35-43.
XU Qingyuan1,LI Jinjin2,ZHANG Yanlan1
1.Department of Computer Science and Engineering,Minnan Normal University,Zhangzhou,Fujian 363000,China
2.School of Mathematics,Minnan Normal University,Zhangzhou,Fujian 363000,China
The variable precision method is introduced into the covering decision information system.Definitions of the variable precision covering lower and upper approximations are given.Some properties and reductions of them are discussed. Their relationships with the covering distribution’s reduction,the largest covering distribution’s reduction and the covering lower and upper approximations’reduction are analyzed.Examples are given to illustrate the conclusions.
variable precision;covering;decision information system;reduction
A
TP18
10.3778/j.issn.1002-8331.1204-0350
XU Qingyuan,LI Jinjin,ZHANG Yanlan.Reductions of variable precision covering decision information system. Computer Engineering and Applications,2014,50(6):123-126.
國家自然科學基金(No.61379021,No.11301367,No.11061004,No.71140004);省屬高??蒲袑m椨媱濏椖浚∟o.JK2011031)。
許晴媛(1977—),女,副教授,研究領域為人工智能、粗糙集、不確定性理論;李進金(1960—),男,教授,博士生導師,研究領域為拓撲學、粗糙集、不確定性理論;張燕蘭(1983—),女,博士生,講師,研究領域為人工智能、粗糙集、不確定性理論。E-mail:xqyyuan871@163.com
2012-04-19
2012-07-19
1002-8331(2014)06-0123-04
CNKI網(wǎng)絡優(yōu)先出版:2012-08-08,http://www.cnki.net/kcms/detail/11.2127.TP.20120808.0938.008.html