ѧ
JOURNAL OF SOFTWARE
1999 2 No.2 1999



ֲڼиϢʾ*
ǫ1,2  2
ժҪֲڼ۶֪ʶʽ,Ϊ֪ʶṩһܵķ,ڴʾ,ֲڼ۵ıʲױ,,޸Ч֪ʶԼ㷨.Ƚ֪ʶϢ֮Ĺϵ;Ȼ,ڴ˻ϸ˴ֲڼиϢʾ;,֤֪ʶԼϢʹֲͬʾǵȼ۵.Щֲڼ۵ı,ͬʱ,ΪѰҸЧ֪ʶԼ㷨춨˻.
ؼʡֲڼ,֪ʶʾ,֪ʶԼ,Ϣ,ȼ.
ͼšTP18
An Information Representation of the Concepts and Operations in Rough Set Theory
MIAO Duo-qian1,2 WANG Jue2
Abstract Rough set theory proposes a formal definition of knowledge and provides a series of tools to deal with knowledge. However, in the algebraic representation of this theory, it is difficult to understand the essence of rough set theory, and efficient algorithm of knowledge reduction has not been found. In this paper, a relationship between knowledge and information is set up, and then based on the relationship an information representation of the concepts and operations about rough set theory is given. Finally, the equivalence properties between information representation and algebraic representation of knowledge reduction are proved. These conclusions are helpful for people to understand the essence of rough set theory and essential to seek new efficient algorithm of knowledge reduction.
Key wordsRough set, knowledge representation, knowledge reduction, information entropy, equivalence property.
ֲڼ(Rough Set)Z.Pawlak1982ģ1.һΪģȷȫϢķṩһµĹ.Ҫ˼,ڱϢϵͳǰ,֪ͨʶԼ,ľ߻.Ŀǰ,ֲڼѱӦڻѧϰϡ㷨ȡ̿Լϵݿе֪ʶȡȸӦ,ȡ˺ܴɹ24.
ֲڼеĸ㶼ͨѧĵȼ۹ϵͼ,ǳ֮Ϊֲڼ۵Ĵʾ.ڴʾ,ֲڼ۵ĺֱܶԽϲ,ǲ䱾.,ڴ˱ʾ,Ŀǰûй֪ʶԼĸЧ㷨.ͬһڲ֪ͬʶʾµ㷨Ѷǲͬģ5.
1 ֲڼҪĴʾ
Ϊڵ3֤ĸϢʾֲڼ۵Ĵʾ֮ĵȼ,бҪȽһ¸۵һЩҪ,ֽЩĴʾ£1:
Uһ,RUϵһȼ۹ϵ.U/RʾRUϵеȼ;[x]RʾԪxRĵȼ,xU.һ֪ʶһϵϵͳK=(U,P),UΪ,PUϵһȼ۹ϵ.QP,Q,Q(Qеȼ۹ϵĽ)Ҳһȼ۹ϵ,IND(Q).
1.1. K=(U,P)K1=(U,Q)֪ʶ.IND(P)=IND(Q),KK1(PQ)ǵȼ۵,KK1(PQ).
֪ʶKK1ȼ,ζKK1ͬĻ,Ǿͬı.
1.2. UΪһ.PΪUϵһȼ۹ϵ,RP.IND(P-{R})=IND(P),ƹϵRPǲҪ();,RPǱҪ.
ҪĹϵ֪ʶǶ.֪ʶȥ,ı֪ʶķ.෴,֪ʶȥһҪĹϵ,һı֪ʶķ.
1.3. UΪһ,PΪUϵһȼ۹ϵ,RP.ÿϵRPPжǱҪ,ƹϵPǶ;,P.
Ĺϵ˵,ажϵ,ԶԼ;ڶĹϵ,ȥκһϵƻ֪ʶķ.
1.4. UΪһ,PΪUϵһȼ۹ϵ.PбҪϵɵļ,ΪϵPĺ,CORE(P).
1.5. UΪһ,P,QΪUϵȼ۹ϵ,QP.
 (1) IND(Q)=IND(P);
(2) QǶ,
QPһԼ.
֪ʶQ֪ʶPԼ,ô,U֪ͨʶPֵĶ,֪ͬʶQ.֪ʶԼǴֲڼҪĸ.
2 ֪ʶϢصĹϵ
ֲڼ۴µӽǶ֪ʶ˶,֪ʶǹĻ,Ӷʹö֪ʶܹܵķ봦.ǽԴֲڼе֪ʶµ,֪ʶϢصĹϵ.Ǳ۵ϢʾĻ.
UΪһ,P,QΪUϵȼ۹ϵ(֪ʶ).ΪUһȼ۹ϵԿǶUӼɵĦ-ϵһ.ʷֲͨ·ȷ.
P,QUϵĻֱַΪX,Y:
X={X1,X2,...,Xn}, Y={Y1,Y2,...,im}, 
P,QUӼɵĦ-϶ĸʷֲΪ

p(Xi)=,i=1,2,...,n;p(Yj)=,j=1,2,...,m;ţEʾEĻ.
֪ʶʷֲĶ֮,ϢۿԶ֪ʶصĸ.֪ʶPH(P)Ϊ
H(P)=p(Xi)logp(Xi). 
֪ʶQ֪ʶPH(QP)Ϊ
H(QP)=p(Xi)p(YjXi)logp(YjXi). 
3 ҪϢʾ
Ͻ,ǽ˴ֲڼе֪ʶϢصĹϵ,ӶʹܹϢĽǶȶԴֲڼ۵Ҫб.ĳƴ˱Ϊֲڼ۵Ϣʾ.ڸ˸۵ҪϢʾ,֤֪ʶԼϢֲͬʾǵȼ۵ģ6.
3.1. Uһ,P,QUϵȼ۹ϵ.IND(P)=IND(Q),H(P)=H(Q).
֤:ΪIND(P)=IND(Q),,P,QUӼɵĦ-ȷĸʷֲͬ.H(P)=H(Q).
ע:3.1δس.
˵,ʾµȼ۵֪ʶͬϢ.
3.2. Uһ,P,QUϵȼ۹ϵ,PQ.H(P)=H(Q),IND(P)=IND(Q).
֤:ΪPQ,IND(P)IND(Q).֤
IND(P)IND(Q).(1) 
U/IND(P)={A1,A2,...,An}, U/IND(Q)={B1,B2,...,Bm}.
÷֤ʽ1ٴһU/IND(P)κBjU/IND(Q)Bjj=12,,m,ӶK(2Km),ʹáBj,
0p(Bj)=1, j=1,2,...,K,
H(Q)=HP+(Q-P)=H(P)+H(Q-P)P.
ΪH(P)=H(Q)ԣH[(Q-P)|P]=0.
H(QP)=0,(2) 
ΪH(ѣP)=p(Ai)p(BjAi)logp(BjAi)-p(Ai0)p(Bj)logp(Bj)0,
˵,֪ʶڰϵʱ,֪ʶϢȿɵóڴʾǵȼ۵.
3.3. Uһ,PUϵһȼ۹ϵ.һϵRPPǲҪ(),ֱҪΪH(RP-{R})=0.
֤:(Ҫ) RPPǲҪ,ɶ֪ʽ
IND(P-{R})=IND(P). 
ɶ3.1֪,H(P-{R})=H(P).
ΪH(P)=H(P-{R})+{R}=H(P-{R})+H(RP-{R}),
ԣH(RP-{R})=0.
ԣH(RP-{R})=0.
ΪH(P)=H(P-{R})+{R}=H(P-{R})+H(RP-{R}),
ԣH(P-{R})=H(P).
ȻСP-{R}P.
ɶ3.2֪INDP-{R})=IND(P). RPPǲҪ.
˵,ڴʾ,Ҫ֪ʶ֪ʶûṩµϢ;֮Ȼ.
. RPPǱҪĳֱҪΪH(RP-{R})0.
3.4. Uһ,PUϵһȼ۹ϵ.PǶĳֱҪΪ:RP,H(RP-{R})0.
֤:ɶԵĶ弰3.3ۿ֤.
3.5. Uһ,PUϵһȼ۹ϵ.PPһԼĳֱҪΪ:
(1) H()=H(P);
(2) qʣ,H(q-{q})0.
֤:PPһԼĳֱҪΪ
IND()=IND(P),(3) 

Ƕ.(4) 
ɶ3.2֪,ʽ(3)ĳֱҪH()=H(P)(ΪP).
ɶ3.4֪,ʽ(4)ĳֱҪ,qʣ,H(q-{q})0.
ʽ۳.
˵,֪ʶԼ,ϢʾԭĴʾȫȼ.Ϣʾȴʾֱ;ǰ߱ʾĻ,ܹЧ֪ʶԼ㷨.
4  
Ŀǰ,ڴֲڼ۵оӦܵ˹˹ܽԽԽĹע.İѶϵĵȼ۹ϵϵһ,Ӷ֪ʶϢ֮Ĺϵ.ǴϢĽǶȸ˴ֲڼҪϢ.֤֪ʶԼϢֲͬʾǵȼ۵.Щֲڼ۵ı,ΪѰҸЧ֪ʶԼ㷨춨˻.
ֻԲǾߵ.оߵԼɴ˵õй֪ʶԼһָЧ㷨Ľ.
л ĸлı!
оõ863߿ƼĿ𡢹ɽʡ.
߽ܣǫ,1964,ʿ,,ҪоΪֲڼ,˹ģʽʶ.
,1948оԱʿʦҪоΪ˹ģʽʶ.
ͨѶϵˣǫ̫ԭ 030006ɽѧѧϵ
ߵλǫɽѧѧϵ̫ԭ030006йѧԺԶо  100080
 塡йѧԺԶо  100080
E-mail: dqmiao@deer.sxu.edu.cn
ο
1Pawlak Z. Rough Sets: Theoretical Aspects of Reasoning about Data. Amsterdam: Kluwer Academic Publishers, 1991. 642
2 Ziarko W. Introduction to the special issue on rough sets and knowledge discovery. International Journal of Computational Intelligence, 1995,11(2):223226
3ǫ,.ڴֲڼĶ췽.ѧ,1997,8(6):425431(Miao Duo-qian, Wang Jue. Rough sets based approach for multivariate decision tree construction. Journal of Software, 1997,8(6):425431)
4,ǫ,.Rough SetӦõ.ģʽʶ˹,1996,9(4):337344(Wang Jue, Miao Duo-qian, Zhou Yu-jian. Rough set theory and its application: a survey. Chinese Journal of Pattern Recognition and Artificial Intelligence, 1996,9(4):337344)
5,ԬС,ʯһ.֪ʶʾ.ѧ,1995,18(3):212224(Wang Jue, Yuan Xiao-hong, Shi Chun-yi et al. A discussion on knowledge representation. Chinese Journal of Computers, 1995,18(3):212224)
6ǫ.Rough SetۼڻѧϰеӦо۲ʿѧλģ.йѧԺԶо,1997(Miao Duo-qian. Rough sets and its application in machine learningPh.D. Thesis. Institute of Automation, The Chinese Academy of Sciences, 1997)
1996-10-09յԭ,1998-03-03յ޸ĸ 
