о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999Vol.36No.6P.681-684



֪ʶԼһʽ㷨
ǫ
ժҪ֪ʶԼRough Setоеĺ֮һ֤ѰҾ߱СԼNP-hard.ȴϢĽǶȣԾ߱ԵҪԸڴ˻ϣһֻڻϢ֪ʶԼʽ㷨ָ㷨ĸǶʽģͨʵڶ¸㷨ܹõ߱СԼ.
ؼʣRough Setۣ֪ʶԼʽ㷨㷨
ţTP18
A HEURISTIC ALGORITHM FOR REDUCTION OF KNOWLEDGE
MIAO Duo-Qian
(Department of Mathematics, Shanxi University, Taiyuan 030006)
HU Gui-Rong
(Department of Mathematics, Shanxi University, Taiyuan 030006)
MIAO Duo-Qian
(National Laboratory of Pattern Recognition,Insitute of Automation,Chinese Academy of Sciences, Beijing 100080)
AbstractReduction of knowledge is one of the important topics in the research on rough set theory. It has been proven that computing the optimal (minimal) reduction of decision table is a NP-hard problem. In the paper here, first, the significance of attributes in decision table is defined from the viewpoint of information; then, a heuristic algorithm based on mutual information for reduction of knowledge is proposed, and the complexity of this algorithm is analyzed; Finally, the experimental results show that this algorithm can find the minimal reduction for most decision tables.
Key wordsRough set theory, reduction of knowledge, heuristic algorithm, complexity of algorithm
1
Rough SetһִȷݺͲȫݵµѧߣ1.Ŀǰڱ㷺Ӧ˹ܡģʽʶϢ򣬲ȡ˿ϲĳɹ23.
֪ʶԼRough Set۵ĺ֮һ1,4,5.֪֪ʶе֪ʶ()ͬҪģĳЩ֪ʶ.ر𣬵֪ʶɼʱԸΪձ.֪ʶĴڣһǶԴ˷(Ҫ洢ռ)һ棬ȷľ.ν֪ʶԼ򣬾ڱ֪ʶķ£ɾвػҪ֪ʶ.
Rough SetУǷǾԶ֪ʶֱʾΪϢϵͳ߱ʽ.Ϣϵͳ֪ʶԼף6о.Ҫ۶Ծ֪߱ʶԼֳΪ֪ʶԼ.
һһ֪߱ʶԼΨһģͬһܴ߱ڶԼ.Ϊ֪ʶԼĿǵھ߱ľ߹ԼԵĶֱӰž߹ķ.ˣҵԵԼ򣬼СԼ.ȻźWong.S.K.MZiarko.WѾ֤ҳһ߱СԼNP-hard7.
NP-hardҪԭԵϱը.˹Уһ㷽ǲʽ8.ȴϢǶȶԾ߱еԵҪԽ˶壬ԴΪʽϢС֪ʶԼеռ.ڴ˻ϣ˻ڻϢ֪ʶԼ㷨.ͨʵ˵ڶ±㷨ܹþ߱СԼ.
2ڻϢ֪ʶԼ㷨
һ߱TԶΪԪT=U,CD,V,fUΪCDֱΪU;Լʾaֵf:U(CD)VһϢx
U,aCDf(x,a)Va.
ף6УǽRough Setе֪ʶǶUӼɵĦ-ϵ.Ӷ֪ʶ뻥Ϣĸ.Щ彫Ǳչ۵Ļ.
2.1߱ҪԵĶ
ھ߱УǹĵЩԶھ߸Ҫ.ʾǿ֮ĻϢ.Ϊھ߱ĳĻϢı仯СΪҪԵĶ.
T=U,CD,V,fΪһ߱RC.ôRһaC֮ϢΪ
I(R{a};D)-I(R;D)=H(D|R)-H(D|R{a})
I(x;y)ʾxyĻϢH(y|x)ʾ֪xʱy.Խ˵֪R£aԾDԽҪ.
1. T=U,CD,V,fһ߱RC.aC-RҪSGF(a,R,D)Ϊ
SGF(a,R,D)=H(D|R)-H(D|R{a}).
R=գSGF(a,R,D)Ϊ
SGF(a,D)=H(D)-H(D|a)=I(a;D)
ΪaDĻϢ.
SGF(a,R,D)ֵԽ˵֪R£aھDԽҪ.ĽSGF(a,R,D)ΪѰС֪ʶԼʱʽϢռ.
2.2ڻϢ֪ʶԼ㷨MIBARK㷨
Rough Set֪κξ߱ԺΨһģеԼ֮УԣԺ˿ΪС֪ʶԼ.ף9УǸ֪ʶԼϢʾ֤Pawlak.ZĴʾĵȼ.Щۿ֪ϢȿΪѰ֪ʶԼֹ.
ڻϢ֪ʶԼ(MIBARK)㷨.㷨bottom-upķʽԼ.Ծ߱ԺΪ㣬ݵ2.1ڶҪԣѡҪӵԺУֱֹ.
㷨1. MIBARK(mutual information-based algorithm for reduction of knowledge)
룺һ߱T=U,CD,V,fУUΪCDֱΪ;Լ.
þ߱һԼ.
1. ߱TCDĻϢI(CD)
2. CDĺC0=CORED(C)
һ˵I(C0;D)<I(C;D)ʱԺC0=գʱI(C0;D)=0
3. B=C0ԼC-Bظ
 ÿpC-BϢI(p;D|B)
 ѡʹϢI(p;D|B)ԣp(ͬʱжԴﵽֵѡȡһBֵٵΪp)BB{p}
 I(B;D)=I(C;D)ֹת٣
4. õBCDһԼ.
2.3㷨
ѰС֪ʶԼNP-hard⣬临Ҫɾ߱е.MIBARK㷨ԣ£ÿǵΪMM-11(MΪ߱).ܴΪ
M+(M-1)++1=M(M+1)/2.
ˣԶԼʱӰ죬ô£㷨ܹO(M2)ʱ临ҵԼ.
3ʵ
Ϊ˿MIBARK㷨Чԣѡһ֪СԼľ߱жԱȷ.þ߱ף7.УU={1,2,,21}ԼC={size, cyl, turbo, fuelsys, displace, comp, power, trans, weight}D={mileage}.
Ziarko.Wף7˸þ߱Լ.˸þ߱Լ(7)ЩԼԵĸֱΪ4567Ըþ߱СԼΪR={size, fuelsys, displace, weight}.ζţԸþ߱ṩϢΪԤmileageؿǸþ߱е11أֻ迼sizefuelͣdisplacementweight ĸؾ㹻.ʵӦǼмֵ.
ñĵMIBARK㷨Ըþ߱Լ.
Ϊ㷨Ծ߱ԺΪ㣬ԣþ߱ԺCo=CORED(C)={fuelsys, weight}.
 Ըþ߱I(C;D)=0.5143.
 Ըþ߱ԺCoI(Co;D)=0.3952.
 B=CopC-BϢI(p;D|B)
1

psizecomppowercyldisplaceturbotrans
I(p;D|B)0.08740.08210.07250.05330.05330.02960.0210

ԿʹϢΪsizeԣºB={fuelsys, weight, size}ңµ
I(B;D)=I(Co;D)+I(p;D|B)
=0.3952+0.0874
=0.4826
һͬķãʹI(p;D|B)ΪdisplaceԣºB={fuelsys,weight,size,displace}ңµI(B;D)=0.5143.
ʱI(B;D)=I(C;D)ʳֹ.ˣԼ{fuelsys, weight, size, displace}Ǹþ߱һԼԼľ߱Ϊ2.
2ԼĹcarľ߱

Ծ
sizefueldisplaceweightmileage
compactEFImediummediummedium
compactEFImediumlighthigh
compact2BBLmediumheavylow
compactEFImediumheavylow
subcompact2BBLsmalllighthigh
compact2BBLsmallmediummedium
subcompactEFIsmalllighthigh
subcompactEFImediummediumhigh
compact2BBLmediummediummedium
subcompactEFIsmallmediumhigh
subcompact2BBLsmallmediumhigh
compactEFIsmallmediumhigh

ͨķԿMIBARK㷨Ըþܹ߱ҳСԼ.㷨СԼ걸Իһ̽.
4
Rough SetΪԶϵͳṩһֹ.ͨԾ֪߱ʶԼ򣬴Ӷ߹.֪ʶԼĲΨһԣʹ֪ʶԼֱӰž߹ķ.õھ߱ĹҪ߱СԼ.ȻźѾ֤ҳһ߱СԼNP-hard.
ȴϢĽǶȣԾ߱ԵҪԸڴ˻ϣһֻڻϢ֪ʶԼʽ㷨ָ㷨ĸǶʽģͨʵڶ¸㷨ܹõ߱СԼ.ǣڸ㷨СԼ걸⻹һ̽.
ĿõȻѧ(Ŀ 69805004)ɽʡ(Ŀ 981017).
߼飺ǫУ19644.ʿڣҪоΪRough SetӦáKDDData Mining˹ܺģʽʶ.
ߵλǫ(ɽѧѧϵ̫ԭ030006)
(ɽѧѧϵ̫ԭ030006)
ǫйѧԺԶоģʽʶصʵҡ100080
οף
1awlak Z. Rough SetsTheoretical Aspects of Reasoning About Data. Kluwer Academic Pub, 1991
2,ǫ,. Rough SetӦõ. ģʽʶ˹, 1996,9(4):337344
(Wang Jue, Miao Duoqian, Zhou Yujian. Rough set theory and its application: A survey. Pattern Recognition and Artificial Intelligence(in Chinese), 1996,9(4):337344)
3,,ǫ. Rough Set۵ġŨ. ѧ1998,21(5):393400
(Wang Jue, Wang Ren, Miao Duoqian Het al. Data enriching based on Rough set theory. Chinese Journal of Computers(in Chinese). 1998,21(5):393400)
4ݶǫ. Rough SetۼڻѧϰеӦо[ʿѧλ], йѧԺԶо,1997
(Miao Duoqian. Rough set theory and its application in machine learning(in Chinese). Institute of Automation, Chinese Academy of Sciences,Beijing1997)
5ang Jue, Miao Duoqian. Analysis on attribute reduction strategies of Rough set. Journal of Computer Science and Technology, 1998,13(2):189192
6iao Duoqian, Wang Jue. An information-based algorithm for reduction of knowledge. IEEE ICIPS '97. 1997.11551158
7ong S K M, Ziarko W. On optimal decision rules in decision tables. Bulletin of Polish Academy of Sciences, 1985,33:693696
8. ˹.ѧ磬1996
(Lu Ruqian. Artificial Intelligence(in Chinese). Beijing:Science Press, 1996)9ǫ, . ֲڼиϢʾ. ѧ1999,
(Miao Duoqian, Wang Jue. An information representation of concepts and operations in rough set theory.Journal of Software(in Chinese), 1999, 10(2): 113-116)
ոڣ1998-08-10
޸ڣ1998-11-26
