ѧ
JOURNAL OF SOFTWARE
1999ꡡ1011ڡVol.10No.111999



һֻRough Set۵Լ򼰹ȡ
ơط
ժҪRough SetԼֵԼҪоһֽڿɱʶdiscernibility matrixѧ߼õԼ·.ͬʱþ󻹿ԷعRough Set۵Ķ.,Ŀǰ㷺õһֵԼԽ˸ĽʹõĹһ.
ؼʡRough SetۣԼֵԼ򣬶.
ͼšTP18
An Approach for Attribute Reduction and Rule Generation Based on Rough Set Theory
CHANG Li-yun WANG Guo-yin WU Yu
(Institute of Computer Science and Technology Chongqing University of Posts and Telecommunications Chongqing 400065)
Abstract In this paper, the authors discuss two important issues in rough set research which are attribute reduction and value reduction. A new attribute reduction approach which can reach the best attribute reduction is presented based on discernibility matrix and logic computation. And a multivariate decision tree can be got with this method. Some improvements for a widely used value reduction method are also achieved in this paper. The complexity of acquired rule knowledge can be reduced effectively in this way.
Key wordsRough set theory, attribute reduction, value reduction, multivariate decision tree.
Rough SetɲѧZ.Pawlak1982һִͲȷѧߣ1.һ۴µӽǳ֪ʶ˶壬֪ʶǹĻ֣ѧеĵȼ۹ϵ֪ʶ.ʮķչ͸˹ܵĸ֧ģʽʶ𡢻ѧϰȷҲгɹӦ.
Rough SetУԼǷǳҪһо.оԱ֣ϵͳвݿԱ뱣ܽɾɴϵͳǱ֪ʶ.Ŀǰ,ϹԼвٷԼǻRough SetۣSkowronĿɱʶ(discernibility matrix)õԵԼ.
ڶݿзʱǾ̺ݵеǱ֪ʶ.ݿϵͳһϴ˺бҪϢҲƾָ߱ʵϢԹɵıʽֵԼ.Ŀǰ,֤ȡֵԼһNPȫ⣬˺ͨöٷСֵԼ.㷨ף2ֵԼԽһ̶ȵĸĽܹõһŻֵԼ.
ķڽԼ㷨ֵԼ㷨.ڽԼ㷨ʱ,ǻһּ򵥡ȷĶ췽.һݼΪۺñ㷨յõĹ.
1Լ㷨
ݿϵͳУڴ.Ϊݿ̺֪ʶĿ̶ȣԼ๤һЩȽЧ㷨.,ͨȥĳԺжϲֹϵǷıǷӦɾԣ3ݣ㷨ȡԼǲ걸.ʵϣνԼӦָһ׼Լõ,յõĹ,ȫԼҪ.Ľܵ㷨ɸݾҪõڸҪµԼ.
֪Rough SetоɹУSkowronĿɱʶΪȡԼṩ˺ܺõ˼·.÷ϢйϢŨһУѷֿͨþ󷽱صõϢԺˣ4ݣԺָϢвɾԣ.㷨ԿɱʶΪصогԺ֮ϣͬʱ,һЩ򵥵ѧ߼Э.
1.1ɱʶ
ɱʶɲɳѧѧSkowron䶨Ϊ:S=(U,A)һϢϵͳUΪU={x1,x2,...,xn}AԼϣDǾԣa(x)Ǽ¼xaϵֵɱʶɱʾΪ

1.2Լ㷨
MǾ߱TĿɱʶA={a1,a2,...,an},TԵļ.SMϵļϣSвظ.SаsϣÿϱʾΪBi乫ʽΪBiS,BjS,BiBj(i,j=1,2,...,s).Card(Bi)=mBiÿԱʾΪbi,kBi(k=1,2,...,m).
ɿɱʶĶ֪Ϊ1޷Ϣо߲ͬ¼ֳԱ뱣߱кԵĸһ.ˣΪ1ԾΪ߱ĺԣΪգ.C0MеĺԼC0A.
ǵɱʶ˾߱еϢ,ӦΪ1ľԪзȡ.ĳϢC0ʣϣֱʾΪa1a2...am,b1b2...bnΪѧ߼㣬ԲֵʾǷĳ.,a1=0ʾa1a1=1ʾa1.ݿɱʶ֪Ҫʶо߲ͬļ¼ai(i=1,2,...,m)bj(j=1,2,...n)֮бȻٸ豣һ.ʽP=(a1a2...am)(b1b2...bn)ϷõP=1.PתΪȡʽʽPȡʽֵ1úȡʽͬԼɽԭ߱еоֳ.ȡʽɶȡʽɣӦҪһ𹹳ָҪµԼ.ϢC0⻹ʣNϣ䴦.
ReduǾ߱TԼõԼϣԼ㷨㷨1.
㷨1.
1. ԼõԼϣRedu=C0
2. ڿɱʶҳвԵS

3. SʾΪȡʽʽP={bi,k:(i=1,2,...,s;k=1,2,...,m)}
4. PתΪȡʽʽ
5. Ҫѡ.٣ֱѡȡʽٵϣԼȽֵԼ.
1.3㷨
־һ״ʵΪϢϵͳ1ʾ.
1һϢϵͳ

UConditionAttribute(C)Decision Attribute(D)
Outlook (a1)Temperature (a2)Humidity (a3)Windy (a4)Class
1SunnyHotHighFalseN
2SunnyHotHighTrueN
3OvercastHotHighFalseP
4RainMildHighFalseP
5RainCoolNormalFalseP
6RainCoolNormalTrueN
7OvercastCoolNormalTrueP
8SunnyMildHighFalseN
9SunnyCoolNormalFalseP
10RainMildNormalFalseP
11SunnyMildNormalTrueP
12OvercastMildHighTrueP
13OvercastHotNormalFalseP
14RainMildHighTrueN

ݿɱʶĶ֪,ĶԽԪؾΪ0Խ߶Գ.ˣֻ϶ԽԪؼ,ͼ1ʾ.

ͼ1 ɱʶ
Ŀɱʶ֪Ϊ{a1a4}.۲죬Եֻa2a3.ʽP=a2a3Pһϣʽ任.,ԭ߱ԿԼΪ{a1a2a4}{a1a3a4}.ϣõ򣬽ϽֵԼ֪{a1a2a4}ΪԵõĹУ
 a1sunnyңa2hotClass=N
 a1overcastClass=P
 a1rainңa4falseClass=P
 a1rainңa4trueClass=N
 a1sunnyңa2mildңa4falseClass=N
 a2coolңa4falseClass=P
 a2mildңa4trueClass=P,
7.{a1a3a4}ΪԵõĹУ
 a1sunnyңa3highClass=N
 a1overcastClass=P
 a1rainңa4falseClass=P
 a1rainңa4trueClass=N
 a1sunnyңa3normalClass=P,
5.ԭ߱ԼӦΪ{a1a3a4}.
1.4㷨
Ŀǰÿֻ鵥ԣľΪID3ϵͳ.һƣܶิӸı÷ǳ.Ϊ˿˷һ,ǿʼøַ.ǫRough SetΪԷĸڹ5ݣ÷Է岻.
ɱʶԪɷΪ3.1Ǻԣ2ǳ֮⻹Եϣ3ǲԵ.е3˽ɺ޷ߵļ¼ɽЩ¼Ϊһ.ھ֤߱һԣ޳ͻ¼ǰ£ȥ޷ɺߵļ¼֮,¼ɸݾߵĲͬΪNࣨ߱Nͬߣ.߱ΪN+1ͬ.ö㷨㷨2.
㷨2. 
1. ÿɱʶԼC0C0=ת2,ת3;
2. ID3ѡһΪýļ;
3. ݾN߱еļ¼ΪN+1.ȸݿɱʶͳƳԵڵУжӦھ߱еļ¼ţЩ¼ɹϵһ.¼ݾٽ򻮷ΪN࣬ÿһеļ¼ͬľ.
Ա1Ϊ.ͼ1ʾĿɱʶ󣬿ԵõC0={a1a4}.a1a4Ϊa2a3ڵзֱΪ19,211ݣ89.ˣ¼{128911}Uϵһ.5¼,ԭϢʣ¼оΪNļ¼{614}ΪPļ¼{3457101213}ǹUϵ.ɴ˿ɵõϢϵͳĶͼ2ʾ.

ͼ2 
2ֵԼ㷨
Rough SetۻдϢгȡ֪ʶʵϣRough SetгȡĹǶϢֵԼĹ.
СֵԼǿɴֵ.νֵָ,Ϣÿ¼ѰҶԵóӰֵ.ϢֵˣĿǰһЩ϶˽ܣ2.ĽֵܵԼ㷨ף2ݵĻ֮ϣף2δɾĳԺʣɵϢвظ¼ʱԶӦֵĴ˲ָĽʹյֵԼõһ.
ĽֵԼ㷨㷨3.
㷨3. 
1. ϢԽп.ȥкͻ¼,ͻ¼ԭֵδͻظ¼ظ¼ĸֵΪ*¼,ֵΪ.
2. ɾܲظ¼,ÿбǡļ¼.δǵֵжϳߣ򽫡Ϊ*,޸Ϊԭֵĳ¼Ծǣ򽫱С޸Ϊԭֵ.
3. ɾԾΪ*ļ¼ܲظ¼.
4. ¼һֵͬһ¼ԱΪ*ô,Ըü¼δǵֵжϳߣɾһ¼,ɾ¼.
Լ֮õϢֵΪñֵˣм¼ΪϢĹ.
־һ2ʾ.abcdΪԣeΪ.ɵ1.2Ա2Լ򣬵õ3.ٶԱ3ֵԼ.
 2

Uabcde
110011
210001
300000
411010
511022
621022
722222

3

Uabde
11011
21001
30000
41110
51122
62122
72222

ڱ3Լ¼1ΪɾaԹɵϢвظ¼˸ü¼aֵΪ?ɾba=1,d=1¼4ľ߳ͻbԭֵɾda=1,b=0¼2ľͬdֵΪ*.¼дõ4.
2м¼1¼3bֵ߲ͬͬӦ4м¼1aΪԭֵ¼5dֵжϳߣӦü¼bΪ*.¼дõ5.
5м¼6¼7aֵӦȣɱ2֪,dжϳߣɾ¼7.6ΪֵԼ֮õϢñеļ¼ӳԭϢеǱڹ򣬿ܽΪ
 (a,1)(b,0)(e,1)
 (a,0)(e,0)
 (b,1)(d,1)(e,0)
 (d,2)(e,2).
4

Uabde
1?0*1
21?*1
30??0
4?110
5*?22
6**?2
7?*?2

5

Uabde
110*1
210*1
30**0
4*110
5**22
6**22
72*22

6

Uabde
110*1
20**0
3*110
4**22

3ʵ֤
Ϊ֤Լ㷨ǲFisherĻʶݼIris data setв.ݼ150Ϊ3ߵļ¼ÿ¼4(petal-lengthpetal-widthseptal-lengthseptal-width)1.ʵݼѡ120¼ΪѧϰݾΪֵòɳѧŲƼѧϿRosettaеOrthogoal Scalerݽɢ.ɢ󣬲ñĽܵķԼ򣬽Լ3petal-lengthpetal-widthseptal-widthֵԼ10ƽÿԣܵԼԼΪ96.7%۷μף6ݣ.Ϊ֤ЧRosetta˶ԱȲԣ,ԱЧѵDynamic ReductsԼҲõ3ԣ뱾ʵһ£ֵԼRosettaõ13ÿ3ɣԼΪ93.5%.
Ϊ֤㷨ùЧԣʵʣ30˲.ʶʶȷΪ93.3%RosettaõĹͬ30вʱ3ʶʶȷΪ90%. 
4 
SkowronĿɱʶһּϢԼ·.÷ѧ߼ڿɱʶкϣܹõҪµԼ.ڻڿɱʶаϢϢĻһֱֹ۷.󣬱һָĽֵԼ򷽷÷ЧؼյõĹ֪ʶ.
ĿоõȻѧӦûо.
߼飺ƣ1974˶ʿҪоΪRough SetۼӦ.
ط1970ʿڣҪоΪ磬Rough Setۣ֪ʶȡϵͳ.
壬Ů1970ʿʦҪоΪСRough Set.
ߵλʵѧԺѧ뼼о  400065
E-mail: netpopeye@263.net
ͨѶϵ:ƣ 510620,еžֿƼ
ο
1Pawlak Z. Rough set. International Journal of Computer and Information Sciences, 1982,11(5):341356
2壬ǫ.Rough SetӦõ.ģʽʶ˹,1996,9(4):337344
(Wang Jue, Miao Duo-qian, Zhou Yu-jian. Rough set theory and its application: a survey. Pattern Recognition and Aritificial Intelligence, 1996,9(4):337344)
3Pawlak Z, Grzymala-Busse J, Slowinski R et al. Rough sets. Communications of the ACM, 1995,38(11):8995
4Hu X,Cercone N. Learning in relational databases: a rough set approach. International Journal of Computational Intelligence, 1995,11(2):323338
5ǫ.ڴֲڼĶ췽.ѧ,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)
6壬Σǫ.Rough Set۵ġŨ.ѧ,1998,21(5):393400
(Wang Jue, Wang Ren, Miao Duoqian et al. Data enriching based on rough set theory. Chinese Journal of Computers, 1998,21(5):393400)
1998-10-20յԭ,1999-01-22յ޸ĸ
